双链表 |
您所在的位置：网站首页 › 正确睡觉枕枕头方式是什么 › 双链表 |
双链表
|
文章目录
双链表的定义双链表上的操作初始化插入操作建立双链表头插法建立双链表尾插法建立双链表
遍历操作求双链表的长度查找操作按值查找按位查找
删除操作判空操作
完整代码及实例总结
双链表的定义
为什么引入双链表？ 单链表的结点中只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。 双链表的结点中有两个指针prior和next，分别指向前驱结点和后继结点。 双链表中结点类型的描述： typedef struct DNode{ int data; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode, *DLinkList; 双链表上的操作 初始化双链表与单链表一样，为了操作方便也可以加入头结点，那么初始化双链表其实就是定义一个头结点，然后将指针域置空。
在双链表中p所指的结点之后插入结点*s，其指针的变化过程如下图所示： 当然，插入操作的语句并不只有这一种顺序，但必须保证1和2两步必须在4步之前，否则*p的后继结点的指针就会丢掉，导致插入失败。 建立双链表 头插法建立双链表每次在头结点的后面插入新结点。 实现代码： //头插法建立双链表 DLinkList HeadInsert(DLinkList &L){ InitList(L); //初始化 int x; cin>>x; while(x!=9999){ DNode *s = (DNode *)malloc(sizeof(DNode)); s->data = x; if(L->next == NULL){ s->next = NULL; s->prior = L; L->next = s; }else{ s->next = L->next; L->next->prior = s; s->prior = L; L->next = s; } cin>>x; } return L; } 尾插法建立双链表每次在双链表的尾部插入新结点，为此，应该声明一个尾指针r并始终指向尾结点。 实现代码： //尾插法建立双链表 DLinkList TailInsert(DLinkList &L){ InitList(L); DNode *s,*r=L; int x; cin>>x; while(x!=9999){ s = (DNode *)malloc(sizeof(DNode)); s->data = x; s->next = NULL; s->prior = r; r->next = s; r = s; cin>>x; } return L; } 遍历操作从单链表的第一个结点开始，依次遍历输出结点的数据直到最后一个结点。 实现代码： //遍历操作 void PrintList(DLinkList L){ DNode *p = L->next; while(p){ cout len++; p = p->next; } return len; } 查找操作 按值查找查找值x在L中的位置。与单链表的按值查找是一样的，不会用到前驱结点指针prior。 实现代码： //按值查找：查找x在L中的位置 DNode *LocateElem(DLinkList L, int x){ DNode *p = L->next; while(p && p->data != x){ p = p->next; } return p; } 按位查找查找在双链表L中第 i 个位置的结点。与单链表的按位查找是一样的，不会用到前驱结点指针prior。 实现代码： //按位查找：查找在双链表L中第i个位置的结点 DNode *GetElem(DLinkList L, int i){ int j=1; DNode *p = L->next; if(i==0)return L; if(i if(iLength(L)){ coutnext->prior = p; //2 free(q); } 判空操作判断双链表是否为空。 实现代码： //判空操作 bool Empty(DLinkList L){ if(L->next == NULL){ cout int data; struct DNode *prior,*next; }DNode, *DLinkList; //初始化 void InitList(DLinkList &L){ L = (DNode *)malloc(sizeof(DLinkList)); L->prior = NULL; L->next = NULL; } //遍历操作 void PrintList(DLinkList L){ DNode *p = L->next; while(p){ cout len++; p = p->next; } return len; } //头插法建立双链表 DLinkList HeadInsert(DLinkList &L){ InitList(L); //初始化 int x; cin>>x; while(x!=9999){ DNode *s = (DNode *)malloc(sizeof(DNode)); s->data = x; if(L->next == NULL){ s->next = NULL; s->prior = L; L->next = s; }else{ s->next = L->next; L->next->prior = s; s->prior = L; L->next = s; } cin>>x; } return L; } //尾插法建立双链表 DLinkList TailInsert(DLinkList &L){ InitList(L); DNode *s,*r=L; int x; cin>>x; while(x!=9999){ s = (DNode *)malloc(sizeof(DNode)); s->data = x; s->next = NULL; s->prior = r; r->next = s; r = s; cin>>x; } return L; } //按值查找：查找x在L中的位置 DNode *LocateElem(DLinkList L, int x){ DNode *p = L->next; while(p && p->data != x){ p = p->next; } return p; } //按位查找：查找在双链表L中第i个位置的结点 DNode *GetElem(DLinkList L, int i){ int j=1; DNode *p = L->next; if(i==0)return L; if(i DNode *s = (DNode *)malloc(sizeof(DNode)); s->data = x; s->next = p->next; p->next->prior = s; s->prior = p; p->next = s; } //删除操作:将双链表中的第i个结点删除 void Delete(DLinkList &L, int i){ if(iLength(L)){ coutnext->prior = p; free(q); } //判空操作 bool Empty(DLinkList L){ if(L->next == NULL){ cout //尾插法建立双链表，并遍历单链表 DLinkList L = TailInsert(L); cout |
实现代码：【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |