数据结构--双链表(C语言) 数据结构

双链表：
双链表与单链表不同的是，其结构体中存在两个指针，“Next”指向直接后继，“Prior”指向直接前驱，链表的访问不再是单链表的单向访问(只能访问后继结点)，可以利用next和prior指针方便的进行双向访问(既可以访问后继结点也可以访问前驱结点)。

实现：

//结构体 typedef struct node{ int data; struct node *next; struct node *prior; }Node;

#include "Link2.h"//初始化链表头结点 //return:头结点地址 Node *init_list() { Node *head; head = (Node *)malloc(sizeof(Node)); if(!head) { printf("Error!\n"); exit(1); } head->data = https://www.it610.com/article/0; head->next = NULL; head->prior = NULL; //将头结点前驱结点置为NULL return head; }//队尾插入新结点 //@num:新结点个数 //@head:头结点 void add_node(int num,Node *head) { if(!head) {//判断链表是否存在 printf("The list is empty!\n"); return ; } Node *p,*q; p = head; q = head; while(q->next)//循环q至链表队尾 q=q->next; while(num--) { p = (Node *)malloc(sizeof(Node)); printf("input data to add:"); scanf("%d",&p->data); p->next = NULL; //新结点的next指针为NULL(即将成为尾结点) p->prior = q; //新结点的前驱结点指向尾结点q q->next = p; //将p结点"挂"到q上，使p成为新的尾结点 q = p; //q重新指向队尾 } }//根据结点位置删除结点 //@no:待删除结点位置 //@head:头指针 //return:成功返回删除结点的值，失败返回-1(默认没有结点的数据域为-1) int delete_node(int no,Node *head) { if(!head) { printf("The list is empty!\n"); return -1; } Node *p,*q; int value; p = head; while(no-- && p->next) { p = p->next; if(!p->next && no > 0) {//当p为队尾且no还大于0时，链表长度不够 printf("The length is less than \'no\'\n"); return -1; } } q = p->prior; //q为p的前驱结点 q->next = p->next; //q的next指针指向p的下一个节点,将p从链表中脱离 if(p->next)//若p不是队尾结点，则将p下一结点的prior指针指向q p->next->prior = q; value = https://www.it610.com/article/p->data; free(p); p = NULL; return value; }//根据结点位置修改结点的数据域 //@no:待修改值的结点位置 //@value:新值 //@head:头结点 //return:成功返回结点旧值，失败返回-1 int change_node(int no,int value,Node *head) { if(!head) { printf("The list is empty!\n"); return -1; } int oldvalue; Node *p = head; while(p->next && no--) { p = p->next; if(!p->next && no > 0) { printf("The list is less than no\n"); return -1; } } oldvalue = https://www.it610.com/article/p->data; p->data = https://www.it610.com/article/value; return oldvalue; }//根据结点位置查找结点 //@no:待查找结点位置 //@head:头结点 //return:成功返回结点值，失败返回-1 int search_node(int no,Node *head) { if(!head) { printf("The list is empty!\n"); return -1; } Node *p = head; while(p->next && no--) { p = p->next; if(!p->next && no > 0) { printf("The list is less than no!\n"); return -1; } } return p->data; }//销毁链表 //@head:头结点地址 void destroy_list(Node **head) { if(!*head) { printf("The list is empty!\n"); return ; } Node *p = *head; while(p->next) {//循环删除head的下一个结点，直到只剩head p = p->next; (*head)->next = p->next; p->next = NULL; p->prior = NULL; free(p); p = *head; } free(p); //释放头结点 p = NULL; *head = NULL; }//打印链表全部值 //@head:头结点 void print_list(Node *head) { if(!head) { printf("The list is empty!\n"); return ; } Node *p = head; while(p->next) { p = p->next; printf("%d\n",p->data); } }

【数据结构--双链表(C语言)】