大话数据结构-4 双向链表
``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <malloc.h> /* 双向链表:每一个节点有两个指针域 双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针 最后的结点->next=NULL */ typedef struct Node { int data;//数据域 struct Node *prior;//直接前驱指针 struct Node *next;//直接后继指针 } NODE,*PNODE; //struct Noode,struct Noode * PNODE create_list();//创建双向链表 void traverse_list(PNODE pHead);//遍历 int main() { PNODE pHead = NULL; pHead = create_list();//创建一个双向链表 traverse_list(pHead); return 0; } PNODE create_list() { int len=0;//有效节点的个数 int i; int val;//用来存放用户输入的节点的值 //1.分配了一个链表所需的头结点 PNODE pHead = (PNODE)malloc(sizeof(NODE)); //判断头结点是否分配了空间 if(NULL == pHead) { printf("分配失败,程序终止!\n"); exit(-1); } //对节点进行初始化 pHead->data = NULL; pHead->next = NULL; pHead->prior = NULL; //使pTail永远指向尾节点 PNODE pTail = pHead; pTail->next = NULL; //需要多少了节点 printf("需要生成的链表节点的个数:len = "); scanf("%d",&len); //循环输入各节点的data,形成链表 for(i=0; i<len; i++) { printf("请输入第%d个节点的值:",i+1); scanf("%d",&val); //生成一个新的节点,存放data,连接链表 PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew) { printf("分配失败,程序终止!\n"); exit(-1); } pNew->data=val; pNew->next = NULL; pNew->prior = NULL; //新节点与链表最后一个节点建立关系 pTail->next=pNew; pNew->prior=pTail; //pTail永远指向链表中最后一个节点 pTail = pTail->next; } return pHead; } void traverse_list(PNODE pHead) { PNODE p = pHead->next; while(p){ if(p->next==NULL){ printf("%d\n",p->data); }else{ printf("%d <-> ",p->data); } p=p->next; } } ```
双链表中对数据进行 "增删查改" 操作
``` #include <stdio.h> #include <stdlib.h> typedef struct line{ struct line * prior; int data; struct line * next; }line; //双链表的创建 line* initLine(line * head); //双链表插入元素,add表示插入位置 line * insertLine(line * head,int data,int add); //双链表删除指定元素 line * delLine(line * head,int data); //双链表中查找指定元素 int selectElem(line * head,int elem); //双链表中更改指定位置节点中存储的数据,add表示更改位置 line *amendElem(line * p,int add,int newElem); //输出双链表的实现函数 void display(line * head); int main() { line * head=NULL; //创建双链表 head=initLine(head); display(head); //在表中第 3 的位置插入元素 7 head=insertLine(head, 7, 3); display(head); //表中删除元素 2 head=delLine(head, 2); display(head); printf("元素 3 的位置是:%d\n",selectElem(head,3)); //表中第 3 个节点中的数据改为存储 6 head = amendElem(head,3,6); display(head); return 0; } line* initLine(line * head){ head=(line*)malloc(sizeof(line)); head->prior=NULL; head->next=NULL; head->data=1; line * list=head; for (int i=2; i<=5; i++) { line * body=(line*)malloc(sizeof(line)); body->prior=NULL; body->next=NULL; body->data=i; list->next=body; body->prior=list; list=list->next; } return head; } line * insertLine(line * head,int data,int add){ //新建数据域为data的结点 line * temp=(line*)malloc(sizeof(line)); temp->data=data; temp->prior=NULL; temp->next=NULL; //插入到链表头,要特殊考虑 if (add==1) { temp->next=head; head->prior=temp; head=temp; }else{ line * body=head; //找到要插入位置的前一个结点 for (int i=1; i<add-1; i++) { body=body->next; } //判断条件为真,说明插入位置为链表尾 if (body->next==NULL) { body->next=temp; temp->prior=body; }else{ body->next->prior=temp; temp->next=body->next; body->next=temp; temp->prior=body; } } return head; } line * delLine(line * head,int data){ line * temp=head; //遍历链表 while (temp) { //判断当前结点中数据域和data是否相等,若相等,摘除该结点 if (temp->data==data) { temp->prior->next=temp->next; temp->next->prior=temp->prior; free(temp); return head; } temp=temp->next; } printf("链表中无该数据元素"); return head; } //head为原双链表,elem表示被查找元素 int selectElem(line * head,int elem){ //新建一个指针t,初始化为头指针 head line * t=head; int i=1; while (t) { if (t->data==elem) { return i; } i++; t=t->next; } //程序执行至此处,表示查找失败 return -1; } //更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值 line *amendElem(line * p,int add,int newElem){ line * temp=p; //遍历到被删除结点 for (int i=1; i<add; i++) { temp=temp->next; } temp->data=newElem; return p; } //输出链表的功能函数 void display(line * head){ line * temp=head; while (temp) { if (temp->next==NULL) { printf("%d\n",temp->data); }else{ printf("%d->",temp->data); } temp=temp->next; } } ```