相关文献：
数据结构与算法(一)：基础理论
数据结构与算法(二)：线性表的实现
数据结构与算法(三)：线性表算法设计练习
数据结构与算法(四)：斐波那契数列
数据结构与算法(五)：LRU
数据结构与算法(六)：栈
数据结构与算法(七)：栈/队列的算法解题思想
数据结构与算法(八)：队列
数据结构与算法(九)：树形结构/二叉树/线索化二叉树
数据结构与算法(十)：哈夫曼树
数据结构与算法(十一)：图形结构
数据结构与算法(十二)：图的应用-最小生成树-Prim/Kruskal
数据结构与算法(十三)：图的应用-最短路径-Dijkstra/Floyd
数据结构与算法(十四)：图的应用-拓扑排序/关键路径
数据结构与算法(十五)：查找算法-顺序查找/二分查找/二叉搜索树/平衡二叉树/散列表查找
数据结构与算法(十六)：排序算法
本章节探究：
1.线性表的概念
2.线性表的顺序存储实现
3.单链表的 创建/遍历/插入/查找/删除 算法实现
4.单向循环链表的 创建/遍历/插入/查找/删除 算法实现
5.双向链表的 创建/遍历/插入/删除 算法实现
6.双向循坏链表 创建/遍历/插入/删除 算法实现
一、线性表
线性表中数据元素之间的关系是一对一的逻辑结构关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，注意：这句话只适用大部分线性表，而不是全部。比如，循环链表 逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
对于非空的线性表和线性结构，特点如下：
- 存在唯一的被称作“第一个”的数据元素；
- 存在唯一的被称作“最后一个”的数据元素；
- 除了第一个之外，结构中的每个元素均有一个前驱；
- 除了最后一个之外，结构中的每个元素均有一个后继。
存储分配方式：
-
顺序存储结构⽤⼀段连续的存储单元依次存储线性表的数据元素; -
链式存储结构⽤⼀组任意的存储单元存放线性表的元素。
时间性能：
- 顺序存储 O(1)
- 单链表O(n)
插⼊和删除：
- 存储结构需要平均移动⼀个表⻓⼀半的元素,时间O(n)
- 单链表查找某位置后的指针后,插⼊和删除为 O(1)
空间性能：
- 顺序存储结构需要预先分配存储空间,分太⼤,浪费空间;分⼩了,发⽣上溢出；
- 单链表不需要分配存储空间,只要有就可以分配, 元素个数也不受限制;
线性表的总结
1.线性表-顺序存储
线性表->顺序存储（逻辑相邻、物理存储地址相邻）
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 1
typedef int ElementType;
typedef int Status;
typedef struct {
ElementType *data;
int length;
}sqlist;
// 1，初始化
Status InitList(sqlist *L) {
L->data = malloc(sizeof(ElementType) * MAXSIZE);
if(!L->data) return ERROR;
L->length = 0;
return OK;
}
// 遍历线性表
Status TraverseList(sqlist L) {
int i;
for (i = 0; i < L.length; i++) {
printf("%d\n", L.data[i]);
}
printf("\n");
return OK;
}
// 插入：
// 1. 位置是否合法
// 2.找到位置，进行位移，修改length
Status ListInsert(sqlist *L, int i ,ElementType e) {
// i值是否合法
if ((i < 1) || (i > L->length+1)) return ERROR;
// 存储空间已满
if (L->length == MAXSIZE) return ERROR;
// 插入数据不在表尾，则先移动出空余位置
if (i <= L->length) {
for (int j = L->length-1; j >= i-1; j--) {
// 插入位置以及之后的位置后移动1位
L->data[j+1] = L->data[j];
}
}
// 将新元素e，放在i的位置上
L->data[i-1] = e;
// 长度+1
++L->length;
return OK;
}
// 删除
// 1.顺序线性表L已存在 1<=i<=ListLength(L)
// 删除L的第i个元素，L的长度-1
Status ListDelete(sqlist *L, int i) {
// 线性表为空
if (L->length == 0) return ERROR;
// i值是否合法
if ((i < 1) || (i > L->length+1)) return ERROR;
for (int j = i; j < L->length; j++) {
// 被删除元素之后的元素向前移动
L->data[j-1] = L->data[j];
}
// 长度-1
L->length--;
return OK;
}
// 查
ElementType ListCheck(sqlist *L, int i) {
// 线性表为空
if (L->length == 0) return ERROR;
// i值是否合法
if ((i < 1) || (i > L->length+1)) return ERROR;
return L->data[i];
}
// 清空循序表
Status ListClear(sqlist *L) {
L->length = 0;
return OK;
}
二、单向链表
1.线性表-链式存储（单向链表）
单链表的线性表的特点：
1.首指针；
2.数据+指针=节点；
3.尾节点的指针为空；
4.节点的指针指向下一个节点;
5.存储地址不需要相邻。
单链表-不带头结点
注意：首指针可以指向首元结点也可以头结点。
头结点它只是一个链表开头的标志，它不存放任何数据。
单链表-带头结点
为什么首指针设计出指向头结点呢？
1.便于首元结点处理；2.便于空表和非空表的统一处理。
插入链表
删除链表
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElementType;/* ElemType类型根据实际情况而定，这里假设为int */
// 定义链表节点
typedef struct Node{
ElementType data; // 数据域
struct Node *next; // 指针域
}Node;
typedef struct Node *LinkList;
// 1.初始化
Status InitList(LinkList *L) {
// *L 首地址
*L = (LinkList)malloc(sizeof(Node));// 头结点
if (*L == NULL) return ERROR;
(*L)->next = NULL; // 空表的头结点的指针域为NULL
return OK;
}
// 2.遍历单链表
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status TraverseList(LinkList L) {
LinkList node = L->next; // 取出头结点
while(node)
{
printf("%d ",node->data); // 打印数据域
node = node->next; // 并获取下一个节点
}
printf("\n");
return OK;
}
// 3.单链表插入
Status InsertList(LinkList *L, int i, ElementType e) {
int j; // 记录遍历到第几个节点
LinkList p, s; // p:遍历到i的前一个节点，s:创建新节点
p = *L;
j = 1;
// 查找到需要插入的位置的那个节点
while (p && j<i) {
p = p->next;
++j;
}
if (!p || j>i) return ERROR;
// 创建新的节点
s = (LinkList)malloc(sizeof(Node));
s->data = e;
// 插入
s->next = p->next; // p->next 就是下一个节点，让s的指针域去指向
p->next = s; // 当前的节点指针域去指向s节点
return OK;
}
// 4.单链表取值
Status GetElement(LinkList L, int i, ElementType *e){
int j; // 记录遍历到第几个节点
LinkList p; // p:遍历到i的前一个节点
//将结点p 指向链表L的第一个结点;
p = L->next;
//j计算=1
j = 1;
//p不为空,且计算j不等于i,则循环继续
while (p && j<i) {
//p指向下一个结点
p = p->next;
++j;
}
//如果p为空或者j>i,则返回error
if(!p || j > i) return ERROR;
// e = p 所指的结点的data
*e = p->data;
return OK;
}
// 5.单链表删除
Status DeleteList(LinkList *L, int i, ElementType *e) {
int j; // 记录遍历到第几个节点
LinkList p, q; // p:遍历到i的前一个节点，q:保存要删除的节点，因为它的next需要被p的指针去指向
//将结点p 指向链表L的第一个结点;
p = (*L)->next;
//j计算=1
j = 1;
//查找第i-1个结点,p指向该结点(将p定位到i的前一个节点)
while (p->next && j<(i-1)) {
p = p->next;
++j;
}
//当i>n 或者 i<1 时,删除位置不合理
if(!(p->next) || (j>i-1)) return ERROR;
// q指向要删除的节点
q = p->next;
// 将p的next指向q的后继节点
p->next = q->next;
// 将q的数据域赋值给e
*e = q->data;
// 释放q
free(q);
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* 头结点指针域为空 */
return OK;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
// 这两种创建方式都是等价的
// LinkList L1;
// struct Node *L2;
// L1 = (LinkList)malloc(sizeof(Node));
// L2 = (LinkList)malloc(sizeof(Node));
// L1->data = 1;
// L2->data = 2;
// printf("%d,%d\n", L1->data, L2->data);
Status iStatus;
LinkList L1,L;
struct Node *L2;
ElementType e;
//2.1 单链表初始化
iStatus = InitList(&L);
printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
//2.2 单链表插入数据
for(int j=1; j<=10; j++) {
iStatus = InsertList(&L, 1, j);
}
printf("插入后：");
TraverseList(L);
//2.3 删除第5个元素
iStatus = DeleteList(&L, 5, &e);
printf("被删除的第5个元素的值为：%d\n", e);
printf("删除后：");
TraverseList(L);
// 头插法
CreateListHead(&L1, 20);
printf("前插法：\n");
TraverseList(L1);
// 尾插法
CreateListTail(&L1, 20);
printf("尾插法：\n");
TraverseList(L1);
return 0;
}
头插法
// 头插法
void CreateListHead(LinkList *L, int n) {
LinkList p;
// 创建一个带头结点的单链表
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for (int i=0; i<n; i++) {
// 创建节点
p = (LinkList)malloc(sizeof(Node));
p->data = i; // 这里只做随意的数据演示
p->next = (*L)->next;
(*L)->next = p;
}
}
尾插法
// 尾插法
void CreateListTail(LinkList *L, int n) {
LinkList p, r; // p: 要插入的节点；r:记录最后一个节点
// 创建一个带头结点的单链表
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for (int i = 0; i < n; i++) {
// 创建节点
p = (LinkList)malloc(sizeof(Node));
p->data = i;
r->next = p;
r = p;
}
r->next = NULL; //注意：最后一个节点r->next要指向null
}
三、单向循环链表
单向循环链表和单向链表的结构差不多，只是单向循环链表的尾节点指针需要指向首元节点。
非空单向循环链表
只有一个节点时，首元结点的指针指向自己
单向循环链表首元结点
1.单向循环链表的创建
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
// 定义节点
typedef struct Node {
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;
// 1.循环链表的创建
Status CreateList(LinkList *L) {
int item; // 输入的数据
LinkList newNode = NULL; // 要插入的新节点
LinkList targetNode = NULL; // 记录插入前的最后一个节点
printf("输入节点的值，输入0结束:\n");
// 每输入一次，则添加一个节点
while (1) {
scanf("%d", &item); // 输入数据存入item
if (item == 0) break;// 输入0则结束输入
if (*L == NULL) {
// 需要创建首元结点
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) return ERROR; // 防止初始化错误
(*L)->data = item; // 输入的数据存储到data
(*L)->next = *L; // 指针域指向自己
} else {
// 已经有首元结点
// 找到尾结点
for(targetNode = *L; targetNode->next != *L; targetNode = targetNode->next);
// 创建一个新的结点作为尾结点
newNode = (LinkList)malloc(sizeof(Node));
if (!newNode) return ERROR;
newNode->data = item;
newNode->next = *L;
targetNode->next = newNode;
}
}
return OK;
}
2.遍历单向循环链表
// 2.打印单向链表
void printfList(LinkList L) {
//如果链表是空
if(L == NULL){
printf("打印的链表为空!\n");
return;
}else{
LinkList temp;
temp = L;
do{
printf("%5d",temp->data);
temp = temp->next;
}while (temp != L);
printf("\n");
}
}
3.单向循环链表插入节点
注意：
插入到第一个位置，需更新尾节点的指向新节点；
插入到其它位置是跟单向链表一样的。
（由于我们没有使用头结点，在插入/删除的时候，需要做一层判断。）
// 3.单向循环列表插入
Status ListInsert(LinkList *L, int place, int data) {
LinkList newNode;
LinkList targetNode;
// 创建新节点
newNode = (LinkList)malloc(sizeof(Node));
if (newNode == NULL) return ERROR;;
newNode->data = data;
if (place == 1) { // 插入到第一个位置
// 单纯找到尾结点，让targetNode临时引用它
for (targetNode = *L; targetNode->next != *L; targetNode = targetNode->next);
// 让新节点成为头结点（新节点指向 之前的首节点L；尾结点指向新节点）
newNode->next = *L;
targetNode->next = newNode;
*L = newNode; // 最后首元结点去引用新节点
} else { // 插入的不是第一个位置
int i; // 计数
// 不能循环多次，就找到place对应的节点
for (i = 1, targetNode = *L; targetNode->next != *L && i != place; targetNode = targetNode->next, i++);
// 插入newNode
newNode->next = targetNode->next;
targetNode->next = newNode;
}
return OK;
}
4. 单向循环链表删除
注意：
在删除头结点的时候需要将第二个节点成为首元节点，让尾节点指向新的首元结点，需要释放被删除的节点；
删除别的节点就和单向链表是一样的。
// 4. 单向循环链表删除
Status ListDelete(LinkList *L, int place) {
if (*L == NULL || place < 1) return ERROR;
LinkList temp,target; //temp记录要删的旧结点； target尾结点
int i;
//temp 指向链表首元结点
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
//②.链表还有很多数据,但是删除的是首结点;
//1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
//2. 新结点做为头结点,则释放原来的头结点
for (target = *L; target->next != *L; target = target->next);
temp = *L;
// 让第二个节点成为新的首元结点
*L = (*L)->next;
// 让尾结点指向新的首元节点
target->next = *L;
// 释放旧节点
free(temp);
} else {
// 删除其他节点
//1. 找到要删除结点的前一个结点，用target保存
for(i = 1 ,target = *L; target->next != *L && i != place-1; target = target->next,i++) ;
//2. 使得target->next 指向下一个结点
temp = target->next;
target->next = temp->next;
//3. 释放需要删除的结点temp
free(temp);
}
return OK;
}
5.单向循环链表查询索引
// 5.单向循环链表查询索引
int getValue(LinkList L, int data) {
int index = 1;
LinkList p;
p = L;
while (p->data != data && p->next != L) {
index++;
p = p->next;
}
if (p->next == L && p->data != data) {
return -1;
}
return index;
}
int main(int argc, const char * argv[]) {
LinkList head = NULL;
int place, num;
int iStatus;
/** 测试创建 */
iStatus = CreateList(&head);
printf("原始链表：\n");
printfList(head);
/** 测试插入 */
printf("输入要插入的 位置 数据，用空格隔开: ");
scanf("%d %d", &place, &num); // 输入 位置 数据
iStatus = ListInsert(&head, place, num);
printfList(head);
printf("输入要插入的 位置 数据，用空格隔开: ");
scanf("%d %d", &place, &num); // 输入 位置 数据
iStatus = ListInsert(&head, place, num);
printfList(head);
printf("输入要插入的 位置 数据，用空格隔开: ");
scanf("%d %d", &place, &num); // 输入 位置 数据
iStatus = ListInsert(&head, place, num);
printfList(head);
/** 测试删除 */
printf("输入要删除的 位置: ");
scanf("%d", &place);
iStatus = ListDelete(&head, place);
printfList(head);
printf("输入要查找的数据：");
scanf("%d", &num);
int index = getValue(head, num);
printf("该数据的位置在：%d \n", index);
return 0;
}
四、双向链表
在单向链表的时候，我们通过遍历找到一个Target节点，但后来我们需要用到Target节点的前驱，则又必须要从头结点开始再次遍历一次。这个时间复杂度达到O(n)。
双向链表就是为了解决这样一个多次遍历的问题。它的节点指针域设计成前驱指针和后继指针。但是它的头结点前驱指针和尾结点后继指针为NULL。
双向链表节点结构
双向链表-带头结点
ps: 我们双向链表在插入的时候会更加简单，在插入到第一个位置和其它位置的逻辑是一样的，无需做额外的判断，所以接下来代码演示这个。
双向链表-不带头结点
1.双向链表的创建
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
// 定义节点
typedef struct Node {
ElemType data;
struct Node *prior; // 前驱
struct Node *next; // 后继
}Node;
typedef struct Node *LinkList;
// 1.双向链表的创建
Status createList(LinkList *L) {
// 分配内存
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) return ERROR;
(*L)->prior = NULL;
(*L)->next = NULL;
(*L)->data = -1; // 不会使用它
LinkList p = *L; // 使用头结点
// 2.随便新增节点
for (int i = 0; i < 10; i++) {
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->prior = NULL;
temp->next = NULL;
temp->data = i;
// 建立双向链表的关系
p->next = temp;
temp->prior = p;
p = p->next; // p去移动到每个创建的节点
}
return OK;
}
// 遍历双向链表的内容
void display(LinkList L) {
LinkList temp = L->next;
if (temp == NULL) { printf("双向链表为NULL"); return; }
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
2.双向链表的插入
注意：
必须先操作要插入数据的后继一端，再操作其前驱一端；
插入到最尾部的时候需要注意尾结点的next是空的情况。
双向链表的插入 - 中间节点
// 2.双向链表的插入
Status ListInsert(LinkList *L, int index, ElemType data) {
if (index < 1) return ERROR; // ps: 这里设计0不是头结点，1表示第一位
// 新建节点
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data = data;
temp->next = NULL;
temp->prior = NULL;
LinkList p = (*L);
// 找到要插入位置的 前一个位置
for(int i = 1; i < index && p; i++) {
p = p->next;
}
if (p == NULL) return ERROR;
// 将新节点插入链表
if (p->next == NULL) {
// 插入的是尾结点
p->next = temp;
temp->prior = p;
} else {
// 插入的不是尾结点
p->next->prior = temp; // 1
temp->next = p->next; // 2
p->next = temp; // 3
temp->prior = p; // 4
}
return OK;
}
3.双向链表的删除
3.1 双向链表的删除 - 通过索引删除
通过索引的方式删除
// 3.1 双向链表的删除 - 通过索引删除
Status ListDelete_Index(LinkList *L, int index, ElemType *data) {
if (*L == NULL) return ERROR;;
int i = 1;
LinkList p = (*L)->next;
// 找到要删除节点的前一个节点
while (i < index && p != NULL) {
p = p->next;
i++;
}
if (i > index || p == NULL) return ERROR;
// 记录待删除的节点
LinkList delTemp = p->next;
*data = delTemp->data; // 把要删除的数据传递出去
// 断了与delTemp的引用
p->next = delTemp->next;
if (delTemp->next != NULL) { // 判断删除的是尾结点
delTemp->next->prior = p;
}
// 释放
free(delTemp);
return OK;
}
3.2 双向链表的删除 - 通过节点删除
通过删除节点的方式删除
// 3.2 双向链表的删除 - 通过节点删除
Status ListDelete_Value(LinkList *L, ElemType data) {
if (*L == NULL) return ERROR;;
LinkList p = NULL;
// 遍历每一个节点
for (p = *L; p->next != NULL; p = p->next) {
if (p->data == data) { // 对比节点的数据一致，则删除
// 删除
p->prior->next = p->next;
if (p->next != NULL) { // 判断删除的是尾结点
p->next->prior = p->prior;
}
free(p);
}
}
return OK;
}
4.双向链表中查找元素的索引
// 4.双向链表中查找元素的索引
int ListSelect(LinkList L, ElemType data) {
if (L == NULL) return ERROR;;
LinkList p = L->next;
int index = 1;
while (p) {
if (p->data == data) {
return index;
}
index++;
p = p->next;
}
return -1;
}
5.双向链表中更新节点的数据
// 5.双向链表中更新节点的数据
Status ListUpdate(LinkList *L, int index, ElemType newData) {
if (L == NULL) return ERROR;
if (index < 1) return ERROR; // ps: 这里设计0不是头结点，1表示第一位
LinkList p = (*L)->next;
// 找到index所在的节点
for (int i = 1; i < index; i++) {
p = p->next;
}
// 更新数据
p->data = newData;
return OK;
}
int main(int argc, const char * argv[]) {
Status iStatus = 0;
LinkList L;
int index, data ,e;
// 1.测试创建双向链表
iStatus = createList(&L);
display(L);
// 2.测试双向链表插入节点
printf("请输入插入的位置和数据(空格隔开)：");
scanf("%d %d", &index, &data);
iStatus = ListInsert(&L, index, data);
printf("打印插入后的链表数据：\n");
display(L);
printf("请输入插入的位置和数据(空格隔开)：");
scanf("%d %d", &index, &data);
iStatus = ListInsert(&L, index, data);
printf("打印插入后的链表数据：\n");
display(L);
// 3.测试双向链表删除节点
printf("请输入要删除的位置：");
scanf("%d", &index);
iStatus = ListDelete_Index(&L, index, &data);
printf("删除的节点： 位置：%d; 数据：%d\n", index, data);
printf("删除之后的双向链表：\n");
display(L);
printf("请输入要删除的数据：");
scanf("%d", &data);
iStatus = ListDelete_Value(&L, data);
printf("删除之后的双向链表：\n");
display(L);
return 0;
}
五、双向循环链表
双向循环链表是在双向链表的基础上让它的头结点前驱指针指向尾结点；尾结点的后继指针指向头结点；而只有单节点的双向循环链表它的前驱后继都指向自己。
所以双向循环链表的数据结构和双向链表的是一样的。
空的双向循环链表
非空的双向循环链表-使用头结点
1.创建双向循环链表
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
// 双向循环链表的头结点前驱指针指向尾结点；尾结点的后继指针指向头结点
// 定义节点
typedef struct Node {
ElemType data;
struct Node *prior; // 前驱
struct Node *next; // 后继
}Node;
typedef struct Node *LinkList;
// 1.创建双向循环链表
Status createList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
if(*L == NULL) return ERROR;
(*L)->prior = (*L); // 前驱指向自己
(*L)->next = (*L); // 后继指向自己
return OK;
}
// 遍历双向循环链表
Status display(LinkList L) {
if (L == NULL) {
printf("双向循环链表为NULL!\n");
return ERROR;
}
printf("双向循环链表的内容为：");
LinkList p = L->next;
while (p != L) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
2.双向循环链表插入
// 2.双向循环链表插入节点
Status insertList(LinkList *L, int index, ElemType data) {
if (*L == NULL) return ERROR; // 头结点不能为空
LinkList p = (*L);
// 获取到要插入位置的 前一个的节点
int i = 1; // 记录当前循环到第几个，从第一个开始
while (i < index) {
p = p->next;
i++;
}
if (i > index) return ERROR;
// 新建插入的节点
LinkList new = (LinkList)malloc(sizeof(Node));
if (new == NULL) return ERROR;
new->data = data;
// 建立双线循环链表关系
new->prior = p;
new->next = p->next;
p->next = new;
if (*L != new->next) { // 插入的不是最后一个节点
new->next->prior = new;
}
return OK;
}
// 3.双向循环链表删除节点
// 3.双向循环链表删除节点
Status deleteList(LinkList *L, int index, ElemType *data) {
if (*L == NULL) return ERROR; // 头结点不能为空
LinkList p = (*L)->next;
int i = 1; // 记录当前循环到第几个，从第一个开始
if (p->next == *L) { // 说明除了头结点外，只有一个节点
free(p->next);
p->next = NULL;
free(*L);
(*L) = NULL;
return OK;
}
// 找到要删除的节点，用p去指向
while (i < index) {
p = p->next;
i++;
}
*data = p->data; // 把要删除节点的数据传递出去
// 重新绑定双向循环关系
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
int main(int argc, const char * argv[]) {
LinkList L;
Status iStatus;
ElemType index, data;
// 测试双向链表的创建
iStatus = createList(&L);
// 测试插入辅助数据
for (int i = 1; i <= 10; i++) {
iStatus = insertList(&L, i, i);
}
display(L);
printf("输入要插入的位置和数据(空格隔开)：");
scanf("%d %d", &index, &data);
iStatus = insertList(&L, index, data);
display(L);
printf("输入要插入的位置和数据(空格隔开)：");
scanf("%d %d", &index, &data);
iStatus = insertList(&L, index, data);
display(L);
// 测试双向链表的删除
printf("输入要删除的位置:");
scanf("%d", &index);
iStatus = deleteList(&L, index, &data);
printf("删除第%d个节点，该节点的数据域为：%d", index, data);
display(L);
return 0;
}
