双向链表

双向链表

      在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表头指针出 发。换句话说,在单链表中,NextElem的执行时间是o(1),而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点,可利用双 向链表。

       双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。

//线性表的双向链表存储结构
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;  //直接前驱指针
    struct DulNode *next;   //直接后继指针
}DulNode , *DuLinkList;

      双向链表既然是比单链表多了如可以反向遍历查找等数据结构,那么也就需要付出一些小的代价:在插入和删除时,需要更改两个指针变量。

插入操作

     插入操作,其实并不复杂,不过顺序很重要,千万不能写反了。假设存储元素e的结点s,要实现将结点s插入到结点p和p->next之间需要下面几步,如下图所示。

s->prior = p;           //把p赋值给s的前驱,如图中1所示
s->next = p->next;      //把p->next赋值给s的后继,如图中2所示
p->next->prior = s;     //把s赋值给p->next的前驱,如图中3所示
p->next = s;            //把s赋值给p的后继,如图中4所示

      关键在于他们的顺序,由于第2步和第3步都用到了p->next。如果第4步先执行,则会使得p->next提前变成了s,使得插入的工作玩不成。所以不妨把上面这种图在理解的基础上记忆,顺序是先搞定s的前驱和后继,再搞定后结点的前驱,最后解决前结点的后继

删除操作

      如要删除结点p,只需要下面两个步骤,如下图所示。

p->prior->next = p->next;       //把p->next赋值给p->prior的后继,如图中1所示
p->next->prior = p->prior;      //把p->prior赋值给p->next的前驱,如图中2所示
free(p);                        //释放结点

双链循环线性表的表示与实现代码:

  1 //双链循环线性表的表示与实现
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 /******************************************************************************
  6 /* 数据类型和常量定义
  7 /******************************************************************************/
  8 #define TURE         1
  9 #define FALSE        0
 10 #define OK           1
 11 #define ERROR        0
 12 #define OVERFLOW    -2
 13 
 14 typedef int Status;
 15 typedef int ElemType;
 16 
 17 /******************************************************************************
 18 /* 数据结构声明
 19 /******************************************************************************/
 20 /* 线性表的双向链表存储结构 */
 21 typedef struct DuLNode {
 22     ElemType data;
 23     struct DuLNode *prior;
 24     struct DuLNode *next;
 25 } DuLNode, *DuLinkList;
 26 
 27 //初始化双链循环线性表
 28 Status InitList_DuL(DuLinkList &L) {
 29     L = (DuLinkList)malloc(sizeof(DuLNode));
 30     L->next = L->prior = L;
 31     return OK;
 32 }
 33 
 34 //获取双链循环线性表中的元素
 35 DuLNode * GetElemP_Dul(DuLinkList L, int i) {
 36     int j;    struct DuLNode *p = L;
 37     if (i < 1)   //非法i值
 38         return NULL;
 39     if (p->next == L) //空双向循环链表
 40         return L;
 41     p = L->next; j = 1;   //初始化, p指向第一个结点, j为计数器
 42     while(p != L && j < i) {  //顺指针向后查找, 直到p指向第i个元素或p指向头结点
 43         p = p->next; ++j;
 44     }
 45     return p;
 46 }
 47 
 48 //插入元素
 49 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
 50     //在带头结点的双链循环线性表L中第i个位置之前插入元素e
 51     //i的合法值为1 <= i <= 表长 + 1
 52     struct DuLNode *p = NULL;
 53     struct DuLNode *s = NULL;
 54     if (!(p = GetElemP_Dul(L, i)))
 55         return ERROR;
 56     if(!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
 57     s->data = e;
 58     s->prior = p->prior; p->prior->next = s;
 59     s->next = p;         p->prior = s;
 60     return OK;
 61 }
 62 
 63 //删除元素
 64 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
 65     //在带头结点的双链线性表L中, 删除第i个元素, 并由e返回其值
 66     //i的合法值为1 <= i <= 表长
 67     struct DuLNode *p = NULL;
 68     if (!(p = GetElemP_Dul(L, i)) || L == GetElemP_Dul(L, i))
 69         return ERROR;
 70     e = p->data;
 71     p->prior->next = p->next;
 72     p->next->prior = p->prior;
 73     free(p); return OK;
 74 }
 75 
 76 //遍历线性表
 77 Status ListTraverse_DuL(DuLinkList &L, Status (*Visit)(ElemType)) {
 78     printf("traverse list: ");
 79     struct DuLNode *p = L->next; //略过头结点
 80     while (p != L) {
 81         Visit(p->data);
 82         p = p->next;
 83     }
 84     return OK;
 85 }
 86 
 87 //访问线性表中的元素
 88 Status Visit(ElemType e)
 89 {
 90     printf("%d ", e);
 91     return OK;
 92 }
 93 
 94 //测试函数
 95 void main()
 96 {
 97     DuLinkList L;  ElemType e;
 98     InitList_DuL(L);
 99     
100     //插入元素
101     if (OK == ListInsert_DuL(L, 0, 55)) printf("insert 55 succeed!\n");
102     if (OK == ListInsert_DuL(L, 1, 56)) printf("insert 56 succeed!\n");
103     ListTraverse_DuL(L, Visit); printf("\n");
104     if (OK == ListInsert_DuL(L, 2, 57)) printf("insert 57 succeed!\n");
105     if (OK == ListInsert_DuL(L, 1, 58)) printf("insert 58 succeed!\n");
106     ListTraverse_DuL(L, Visit); printf("\n");
107 
108     //删除元素
109     if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1);
110     if (OK == ListDelete_DuL(L, 3, e)) printf("the %drd elem deleted!\n", 3);
111     if (OK == ListDelete_DuL(L, 4, e)) 
112         printf("the %dth elem deleted!\n", 4);
113     else
114         printf("delete the %dth elem failed!\n", 4);
115     if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1);
116     ListTraverse_DuL(L, Visit); printf("\n");
117     if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1);
118     ListTraverse_DuL(L, Visit); printf("\n");
119 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zhisheng

SimpleDateFormat 如何安全的使用?

看到这条我立马就想起了我实习的时候有个项目里面就犯了这个错误,记得当时是这样写的:

1071
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

1331
来自专栏开发 & 算法杂谈

PAT Advanced 1043

A Binary Search Tree (BST) is recursively defined as a binary tree which has th...

903
来自专栏程序生活

Leetcode-Easy 543. Diameter of Binary Tree

543. Diameter of Binary Tree 描述: 求二叉树最长路径长度 ? 思路: 深度优先搜索 代码 # Definit...

3174
来自专栏陈树义

Java ConcurrentModificationException异常原因和解决方法

Java ConcurrentModificationException异常原因和解决方法   在前面一篇文章中提到,对Vector、ArrayList在迭代的...

3874
来自专栏数据处理

leetcode222求完全二叉树节点个数

3774
来自专栏IT笔记

ArrayList和LinkedList的区别

首先来看ArrayList和LinkedList的集成类和接口的区别。 public class ArrayList<E> extends AbstractLi...

3298
来自专栏趣学算法

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R...

3123
来自专栏日常分享

通过BitSet完成对单词使用字母的统计

  BitSet类实现了一组位或标记(flag),这些位可被分别设置或清除。当需要跟踪一组布尔值时,这种类很有用。

1162
来自专栏趣学算法

数据结构 第12讲 二叉树的层次遍历

二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示:

1153

扫码关注云+社区

领取腾讯云代金券