线性表之双向链表 （建立和基本）

大家好，我是考研的球球。今天我完成了双向链表的学习及程序编写，如果有错误，欢迎评论区指出，谢谢您的阅读！！！您的点赞和关注是我最大的动力，谢谢大家！！！

---

附上我的几篇博文，有关顺序表和链表的：

线性表之顺序表（引用实现） Cpp数据结构单链表（线性链表）的建立与基础

 

 

---

总结一下双向链表，就是链表的扩展，最大区别是每个节点加入了一个向前的指针prior,从而可以实现双向访问。   链表还可以进一步变成循环链表，这时判断是否循环一圈的方法是首指针head是否等于当前节点指针。

 代码的每个函数都包含讲解，在程序中。

结构体： typedef struct DList { int data; struct DList *next; struct DList *prior; }DList;

 

运行截图

代码：

#include<iostream> #include<stdlib.h> using namespace std; typedef struct DList { int data; struct DList *next; struct DList *prior; }DList; void creatDlist(DList *&L); void findNode(DList *L); void insertNode(DList *&L); void deleteNode(DList *&L); void Print(DList *L); int Len(DList *L); void creatDlist(DList *&L) //创建双向链表 { int x; int a[100]; printf("请输入初始数据数量："); scanf("%d",&x); DList *s,*r; L->next=NULL; L->prior=NULL; r=L; r->prior=NULL; for(int i=0;i<x;i++) { s=(DList *)malloc(sizeof(DList)); scanf("%d",&s->data); //将 s 插入 r 的尾部 r->next=s; s->next=NULL; r=r->next; } r->next=NULL; } void findNode(DList *L) //找到某个值的节点 { DList *s=L->next;//首指针 L 里面不存放data int yy=0; printf("输入你想找的数："); scanf("%d",&yy); while((s!=NULL)&&(s->data!=yy))//找不到就一直循环 { s=s->next; } if(s==NULL) { printf("双链表里面没有该数据!!\n"); } else { printf("链表里有该数据！！\n"); } } //在第n个位置插入 void insertNode(DList *&L) { int n=0; int len=Len(L); printf("请输入插入数据位置(正整数)："); scanf("%d",&n); while(n>len) { printf("数字过大！！！\n重新输入位置："); scanf("%d",&n); } DList *s=L; if(s->next==NULL) { printf("链表为空！\n"); return; } for(int i=1;i<n;i++) { s=s->next; } DList *r=(DList *)malloc(sizeof(DList)); printf("请输入插入的数："); scanf("%d",&r->data); //一下4行插入 数据节点 r->next=s->next; r->next->prior=r; r->prior=s; s->next=r; } // 删除第 n 个位置的节点 void deleteNode(DList *&L) { int n,len; DList *r,*s=L; len=Len(L); printf("请输入删除的位置（正整数）："); scanf("%d",&n); while(n>len) { printf("数字过大！！！\n重新输入位置："); scanf("%d",&n); } for(int i=1;i<n;i++) { s=s->next; } //一下为删除语句 r=s->next->next; free(s->next); s->next=r; if(r!=NULL)//当删除位置是最后一个 if就不执行了 { r->prior=s; } } void Print(DList *L)//输出链表所有内容 { DList *r=L->next; while(r!=NULL) { printf("%d ",r->data); r=r->next; } printf("\n"); } int Len(DList *L) //确定链表长度 { int sum=0; DList *r; r=L->next; while(r!=NULL) { sum++; r=r->next; } return sum; } int main() { DList *L=(DList*)malloc(sizeof(DList)); creatDlist(L); printf("输出所有节点："); Print(L); insertNode(L); printf("输出插入后的链表："); Print(L); deleteNode(L); printf("输出删除后的链表："); Print(L); findNode(L); int sum=Len(L); printf("链表长度为:%d",sum); return 0; }