一、双向链表
1.1 创建及添加新数据
1、开辟一个头节点(也可以不用头节点，这里用到头节点是为了更加简单、方便插入数据，使得在任意位置都是同一操作即可)；
2、用p来表示*L，简便书写
3、创建一个新节点temp；
4、将temp的piror指向p；
5、将p的next指向temp；
6、用p来记录 最后节点 的位置，方便下一次插入。
双向链表的创建及添加数据.png
//1.1 创建双向链表
Status LinkListInit (LinkList *L) {
//判断是否是创建过的表
if (*L) {
printf("表已存在");
return ERROR;
}
//给L表开辟一个头节点
*L = (LinkList)malloc(sizeof(Node));
//判断是否创建成功
if (*L == NULL) return ERROR;
//刚开始的头节点的piror、next都为空
(*L)->next = NULL;
(*L)->piror = NULL;
(*L)->data = -1;//无用数据，随便赋值或不赋值都可
//为了简便，不重复写(*L)，临时创建一个p
LinkList p = *L;
//给表添加数据
for (int i = 1; i < 10; i++) {
//创建一个新的节点
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
//刚创建的节点的piror、next应都为空
temp->piror = NULL;
temp->next = NULL;
temp->data = i;
//给头节点和新的节点建立双向链表关系
p->next = temp;
temp->piror = p;
//p指向尾节点
p = p->next;
}
return OK;
}
//打印循环链表的元素
Status displayList (LinkList L){
//如果表为空
if (L == NULL) return ERROR;
LinkList p = L->next;//这里的表有头节点，所以从首元节点开始打印，
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return OK;
}
问题：有无头节点的区别？
有头节点的更加简单、方便，插入的数据在任何位置都是同一处理；没有头节点的，插入的数据在首元节点前的，指针需重新指向，更加麻烦
1.2 插入
1、创建新节点
temp;
2、寻找插入位置的前个节点p;
3、如果插入的位置是尾节点，则直接p->next = temp,temp->piror = temp即图中的4、5即可;
4、如果插入的位置不是尾节点，则p->next->piror = temp,temp->next = p->next,p->next = temp,temp->piror = p即执行图中的2、3、4、5;
双向链表插入元素.png
Status LinkListInsert (LinkList *L,int i,ElemType e){
//先判断表是否为空
if (*L == NULL) return ERROR;
//判断插入的位置是否非法
if (i < 1) return ERROR;//0既不是头节点，也不是位置，位置应当从1开始
//创建新的节点
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->piror = NULL;
temp->next = NULL;
temp->data = e;
LinkList p = *L;
//寻找要插入位置的前节点
for (int j = 1;j < i && p ;j++) {
p = p->next;
}
//判断找到的p是否为空
if (p == NULL) return ERROR;
//判断插入的位置是否是尾节点
if (p->next == NULL) {
temp->piror = p;
p->next = temp;
} else {
//如果插入的位置不是尾节点
//原先i位置的节点的前驱指向新节点temp
p->next->piror = temp;
//新节点temp的next指向原先i位置的节点
temp->next = p->next;
//和i位置的前一个节点建立关系
p->next = temp;
temp->piror = p;
}
return OK;
}
1.3 删除
1.3.1 删除指定位置上的节点
1、先获取到删除节点的上一个节点
p;
2、删除节点用一个临时节点deleTemp来指向，
3、p的next指向deleTemp的next；即图中的2⃣️
4、获取要删除节点的数据*e；
5、判断删除节点是否是尾节点，如果不是，则将deleTemp的next的piror直接指向p；即图中1⃣️
6、释放deleTemp
双向链表删除指定位置上的元素.png
Status LinkListDelete (LinkList *L,int place,ElemType *e) {
//判断表是否存在
if (*L == NULL) return ERROR;
//判断删除的节点位置是否合法
if (place < 1) return ERROR;
//用来记录删除的前一个节点位置
int j = 1;
LinkList p = *L;
//获取要删除的前一个节点
for (j = 1; j < place && place; j++) {
p = p->next;
}
if (p == NULL || j > place) return ERROR;
//定义一个临时节点deleTemp记录要删除的节点
LinkList deleTemp = p->next;
//获取要删除位置的元素值
*e = deleTemp->data;
//用p指向删除节点的下一个节点
p->next = deleTemp->next;
//判断删除的节点是否是最后一个节点
if (deleTemp->next != NULL) {
//如果不是最后一个节点，那么删除节点的下一个节点不为空，存在前区
deleTemp->next->piror = p;
}
//释放删除的节点
free(deleTemp);
return OK;
}
1.3.2 删除指定元素的节点
1、遍历整个表，寻找元素相同的节点；
2、如果找到元素相同的节点，则重新建立该节点前后节点的联系
3、找到相同元素的节点：
3.1 将deleTemp的上一个节点直接指向deleTemp的下一个节点；
3.2 不是尾节点的话，将下一节点的前驱指向删除节点的上一个节点
3.3 释放节点，退出循环
4、没找到的话，将deleTemp指向下一个节点
Status LinkListDelete2 (LinkList *L,int data) {
//判断表是否存在
if (*L == NULL) return ERROR;
LinkList deleTemp = *L;
//遍历整个表，寻找元素相同的节点
while (deleTemp) {
//如果找到元素相同的节点，则重新建立该节点前后节点的联系
if (deleTemp->data == data) {
deleTemp->piror->next = deleTemp->next;
//判断该节点是否是尾节点
if (deleTemp->next != NULL) {
//不是尾节点的话，将下一节点的前驱指向删除节点的上一个节点
deleTemp->next->piror = deleTemp->piror;
}
//释放
free(deleTemp);
//退出循环
break;
}
deleTemp = deleTemp->next;
}
return OK;
}
1.4 查找
int selecElem(LinkList L,ElemType elem){
//判断表是否存在
if (L == NULL) ERROR;
//从头节点后的节点开始
LinkList temp = L->next;
int place = 1;
while (temp) {
//找到相同元素的话，直接返回该元素的位置
if (temp->data == elem) {
return place;
}
//没找到的话，继续下一个
place++;
temp = temp->next;
}
return -1;
}
1.5 更新(替换)
Status LinkListReplace (LinkList *L,ElemType elem,ElemType replaceElem) {
//判断表是否存在
if (*L == NULL) return ERROR;
LinkList replaceTemp = (*L)->next;
while (replaceTemp) {
if (replaceTemp->data == elem) {
replaceTemp->data = replaceElem;
break;
}
replaceTemp = replaceTemp->next;
}
return OK;
}
二、双向循环链表
因为 双向循环链表 和 双向链表 大同小异，所以不在画图展示。
2.1 创建
1、创建临时的结点
temp；
2、为新增的结点建立双向链表关系
Status creatLinkList(LinkList *L){
if (*L != NULL) {
printf("该表已存在，不需要重新创建");
return ERROR;
}
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) {
return ERROR;
}
(*L)->next = (*L);
(*L)->prior = (*L);
//新增数据
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.创建1个临时的结点
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->data = i;
//2.为新增的结点建立双向链表关系
//① temp 是p的后继
p->next = temp;
//② temp 的前驱是p
temp->prior = p;
//③ temp的后继是*L
temp->next = (*L);
//④ p 的前驱是新建的temp
p->prior = temp;
//⑤ p 要记录最后的结点的位置,方便下一次插入
p = p->next;
}
return OK;
}
2.2 插入
Status LinkListInsert(LinkList *L, int index, ElemType e){
//双向循环链表为空,则返回error
if (*L == NULL) return ERROR;
//创建指针p,指向双向链表头
LinkList p = *L;
int j = 1;
//寻找要插入节点的上一个节点
for (j = 1; j < index; j++) {
p = p->next;
}
//如果j>index 则返回error
if (j > index) return ERROR;
LinkList temp = (LinkList)malloc(sizeof(Node));
//将生成的新结点temp数据域赋值e.
temp->data = e;
//将结点temp 的前驱结点为p;
temp->prior = p;
//temp的后继结点指向p->next;
temp->next = p->next;
//p的后继结点为新结点temp;
p->next = temp;
//如果temp 结点不是最后一个结点
if (p->next != (*L)) {
//temp节点的下一个结点的前驱为temp 结点
temp->next->prior = temp;
} else {
(*L)->prior = temp;
}
return OK;
}
2.3 删除
Status LinkListDelete(LinkList *L,int index,ElemType *e){
//双向循环链表为空,则返回error
if (*L == NULL) return ERROR;
int i = 1;
LinkList temp = (*L)->next;
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if(temp->next == *L){
free(*L);
(*L) = NULL;
return OK;
}
//1.找到要删除的结点
while (i < index) {
temp = temp->next;
i++;
}
//2.给e赋值要删除结点的数据域
*e = temp->data;
//3.修改被删除结点的前驱结点的后继指针 图1️⃣
temp->prior->next = temp->next;
//4.修改被删除结点的后继结点的前驱指针 图2️⃣
temp->next->prior = temp->prior;
//5. 删除结点temp
free(temp);
return OK;
}
