【数据结构】双向链表

1. 双向链表

1.1特性

1.2双向链表相关操作

1.3 双向循环链表

1. 双向链表

1.1特性

逻辑结构：线性结构

存储结构：链式存储

操作：增删改查

typedef int datatype;
typedef struct node
{datatype data;      //数据域struct node *next;  //指向后继节点指针struct node *prior; //指向前驱节点指针
} link_node_t, *link_node_p;//将头尾指针封装到一个结构体里,思想上有点像链式队列
typedef struct doublelinklist
{link_node_p head; //链表头指针link_node_p tail; //链表尾指针int len;          //用来保存当前链表的长度
} doublelinklist_t, *doublelinklist_p;

1.2双向链表相关操作

创空：

插入：

删除：

删除指定数据

需要注意的是，与单链表不同，双链表创建过程中，每创建一个新节点都要与其前驱节点建立两次联系，分别是：

(1) 将新节点的 prior 指针指向直接前驱节点。

(2) 将直接前驱节点的 next 指针指向新节点。

#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node
{datatype data;      //数据域struct node *next;  //指向后继节点指针struct node *prior; //指向前驱节点指针
} link_node_t, *link_node_p;//将头尾指针封装到一个结构体里,思想上有点像链式队列
typedef struct doublelinklist
{link_node_p head; //链表头指针link_node_p tail; //链表尾指针int len;          //用来保存当前链表的长度
} doublelinklist_t, *doublelinklist_p;//创建一个空双向链表
doublelinklist_p createEmptyDoubleLinkList()
{//1.申请空间存放头尾指针结构体doublelinklist_p p = (doublelinklist_p)malloc(sizeof(doublelinklist_t));if (NULL == p){perror("p malloc err");return NULL;}//2. 初始化结构体空间p->len = 0;p->head = p->tail = (link_node_p)malloc(sizeof(link_node_t));if (NULL == p->head){perror("p->head malloc err");return NULL;}//3. 初始化头节点p->head->next = NULL;p->head->prior = NULL;return p;
}//向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(doublelinklist_p p, int post, datatype data)
{int i;link_node_p temp = NULL;//1. 容错判断if (post < 0 || post > p->len){printf("insertIntoDoubleLinkList err\n");return -1;}//2. 新建一个节点，用来保存数据link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));if (NULL == pnew){perror("pnew malloc err");return -1;}pnew->data = data;pnew->next = NULL;pnew->prior = NULL;//3. 将新节点链接到链表中//分情况：尾插和中间插入if (post == p->len) //尾插{//将新节点链接到链表尾部pnew->prior = p->tail;p->tail->next = pnew;//移动尾指针p->tail = pnew;}else //中间插入（分前后半段）{//(1) 将temp移动到插入位置if (post < p->len / 2) //前半段{temp = p->head;for (i = 0; i <= post; i++)temp = temp->next;}else //后半段{temp = p->tail;for (i = p->len - 1; i > post; i--)temp = temp->prior;}//（2）将新节点插入到链表中（先连前面，再连后面）pnew->prior = temp->prior;temp->prior->next = pnew;pnew->next = temp;temp->prior = pnew;}//长度加一p->len++; //新多了节点，链表长+1return 0;
}//遍历双向链表
void showDoubleLinkList(doublelinklist_p p)
{link_node_p temp = NULL;//正向遍历printf("正向遍历： ");temp = p->head;while (temp->next != NULL) //类似于遍历有头单向链表{temp = temp->next;printf("%d ", temp->data);}printf("\n");//反向遍历printf("反向遍历： ");temp = p->tail;while (temp != p->head) //类似于遍历无头单向链表{printf("%d ", temp->data);temp = temp->prior;}printf("\n");
}//判断双向链表是否为空
int isEmptyDoubleLinkList(doublelinklist_p p)
{return p->len == 0;
}//删除双向链表指定位置数据
int deletePostDoubleLinkList(doublelinklist_p p, int post)
{int i;//1. 容错判断if (isEmptyDoubleLinkList(p) || post < 0 || post >= p->len){printf("deletePostDoubleLinkList err\n");return -1;}//2. 对删除位置进行分析，分两种情况if (post == p->len - 1) //删除尾巴节点{//(1)往前移动尾指针p->tail = p->tail->prior;//（2）释放要被删除节点，也就是此时尾指针所指节点后一个节点free(p->tail->next);//（3）此时尾巴节点next为空p->tail->next = NULL;}else //中间删除{//定义一个指针，移动到被删除节点link_node_p temp = NULL;if (post < p->len / 2) //前半段{temp = p->head;for (i = 0; i <= post; i++)temp = temp->next;}else //后半段{temp = p->tail;for (i = p->len - 1; i > post; i--)temp = temp->prior;}//进行删除操作，也就是跨过要被删除节点。temp->prior->next = temp->next;temp->next->prior = temp->prior;free(temp);temp = NULL;}//3.长度-1p->len--;
}//修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(doublelinklist_p p, int post, datatype data)
{int i;link_node_p temp = NULL;//1. 容错判断if (isEmptyDoubleLinkList(p) || post < 0 || post >= p->len){printf("deletePostDoubleLinkList err\n");return -1;}//2. 将指针temp移动到要修改节点if (post < p->len / 2) //前半段{temp = p->head;for (i = 0; i <= post; i++)temp = temp->next;}else //后半段{temp = p->tail;for (i = p->len - 1; i > post; i--)temp = temp->prior;}//3. 修改数据temp->data = data;return 0;
}//查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(doublelinklist_p p, datatype data)
{link_node_p temp = p->head;int post = 0;while (temp->next != NULL){temp = temp->next;if (temp->data == data)return post;post++;}return -1;
}//删除双向链表中的指定数据 data代表删除所有出现的data数据
//思想：从头节点后节点开始用指针h遍历，相当于遍历无头链表，遇到需要删除节点的就用h指向它然后删除，如果不需要删除则h继续往后走一个。这里因为是双向链表可以找到前驱，所以不需要每次指向被删除节点的前一个然后跨过了。
void deleteDataDoubleLinkList(doublelinklist_p p, datatype data)
{link_node_p pdel = NULL;       //用于删除节点link_node_p h = p->head->next; //用于相当于遍历无头链表//相当于遍历无头链表，遇见相等的就删除，否则向后遍历while (h != NULL){if (h->data == data) //相等{if (h == p->tail) //尾节点{//删除尾巴节点p->tail = p->tail->prior;free(p->tail->next);p->tail->next = NULL;}else //删除中间节点{h->prior->next = h->next;h->next->prior = h->prior;pdel = h;h = h->next; //释放前要让h向后走一个以便继续遍历free(pdel);}p->len--;}else //不等{h = h->next; //往后继续遍历}}
}int main(int argc, char const *argv[])
{doublelinklist_p p = createEmptyDoubleLinkList();insertIntoDoubleLinkList(p, 0, 1);insertIntoDoubleLinkList(p, 1, 2);insertIntoDoubleLinkList(p, 2, 3);insertIntoDoubleLinkList(p, 3, 4);showDoubleLinkList(p);deletePostDoubleLinkList(p, 3);showDoubleLinkList(p);changeDataDoubleLinkList(p, 2, 100);showDoubleLinkList(p);printf("post = %d\n", searchPostDoubleLinkList(p, 100));insertIntoDoubleLinkList(p, 3, 1);deleteDataDoubleLinkList(p, 1);showDoubleLinkList(p);return 0;
}

1.3 双向循环链表

doublecirclelink.c

#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node_t
{datatype data;struct node_t * prior;struct node_t * next;
}link_node_t,*link_node_p;typedef struct doublelinklist
{link_node_p head;link_node_p tail;
}double_node_t,*double_list_t;int main(int argc, const char *argv[])
{int i;int all_num = 8;//猴子总数int start_num = 3;//从3号猴子开始数int kill_num = 3;//数到几杀死猴子 link_node_p h = NULL;link_node_p pdel = NULL;//用来指向被杀死猴子的节点printf("请您输入猴子的总数，开始号码，出局号码:\n");scanf("%d%d%d",&all_num,&start_num,&kill_num);//1.创建一个双向的循环链表double_list_t p = (double_list_t)malloc(sizeof(double_node_t));//申请头指针和尾指针if(NULL == p){perror("malloc failed");return -1;}p->head = p->tail = (link_node_p)malloc(sizeof(link_node_t));if(NULL == p->tail){perror("p->tail malloc failed");return -1;}p->head->data = 1;p->head->prior = NULL;p->head->next = NULL;//将创建n个新的节点，链接到链表的尾for(i = 2; i <= all_num; i++){link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));if(NULL == pnew){perror("pnew malloc failed");return -1;}pnew->data = i;pnew->prior = NULL;pnew->next = NULL;//(1)将新的节点链接到链表的尾p->tail->next = pnew;pnew->prior = p->tail;//(2)尾指针向后移动，指向当前链表的尾p->tail = pnew;}//(3)形成双向循环链表 p->tail->next = p->head;p->head->prior = p->tail;//调试程序 #if 0while(1){printf("%d\n",p->head->data);p->head = p->head->next;sleep(1);}#endif//2.循环进行杀死猴子h = p->head;//(1)先将h移动到start_num处，也就是开始数数的猴子号码处for(i = 1; i < start_num; i++)h = h->next;printf("start is:%d\n",h->data);while(h->next != h)//当h->next == h 就剩一个节点了，循环结束{//(2)将h移动到即将杀死猴子号码的位置for(i = 1; i < kill_num; i++)h = h->next;//(3)进行杀死猴子，经过上面的循环后，此时的h指向即将杀死的猴子h->prior->next = h->next;h->next->prior = h->prior;pdel = h;//pdel指向被杀死猴子的位置printf("kill is -------%d\n",pdel->data);h = h->next;//需要移动，从杀死猴子后的下一个位置开始数free(pdel);}printf("猴王是%d\n",h->data);return 0;
}

单向链表与双向（循环）链表的区别：

存储空间方面：双向存储空间大，因为每个节点中有两个指针。

效率方面：双向链表效率高，因为可以从后往前遍历。

请完成如下双向链表的删除过程: （云尖软件开发笔试试题）