我们都知道,单链表只有一个指向下一个结点的指针,当我们想要找到前一个结点时就比较麻烦,而双链表拥有两个指针
总的来说:
定义双链表结点类型
typedef struct DNode{ ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinklist;
定义一个 InitLinklist 函数,参数为双链表的引用,加引用是因为要改变这个双链表
注意:头结点的前驱指针永远指向 NULL
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct DNode{ ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinklist; //初始化双链表 bool InitLinklist(DLinklist &L) { L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点 if (L == NULL) return false; //内存不足,分配失败 L->prior = NULL; //头结点的 prior 永远指向 NULL L->next = NULL; //头结点之后暂时还没有结点 return true; } //判断双链表是否为空(带头结点) bool Empty(DLinklist L) { if (L->next == NULL) return true; else return false; } void testDLinklist() { //初始化双链表 DLinklist L; InitLinklist(L); }
后插法
//在p结点之后插入s结点 bool InsertNextDNode(DNode *p, DNode *s) { if (p == NULL || s == NULL) return false; //非法参数 s->next = p->next; if (p->next != NULL) //如果p结点有后继结点 p->next->prior = s; s->prior = p; p->next = s; return true; }
学会了后插操作,我们也就学会了按位序插入和前插法,大概思路为找到目标结点的前驱结点,然后对其进行后插操作
//删除p结点的后继结点 bool DeleteNextDNode(DNode *p) { if (p == NULL) return false; DNode *q = p->next; //找到p结点的后继结点q if (q == NULL) return false; //p没有后继 p->next = q->next; if (q->next != NULL) //q结点不是最后一个结点 q->next->prior = p; free(p); //释放结点空间 return true; } //销毁双链表 void DestoryList(DLinklist &L) { //循环释放各个数据结点 while (L->next != NULL) { DeleteNextDNode(L); } free(L); //释放头结点 L = NULL; //头指针指向NULL }
由于双链表不可随机存取,所以按位查找、按值查找等操作都只能用遍历的方式实现,时间复杂度为 O(n)
//后向遍历 while (p != NULL) { //对结点p做相应处理,比如打印 p = p->next; } //前向遍历 while (p != NULL) { //对结点p做相应处理 p = p->prior; } //前向遍历(跳过头结点) while (p->prior != NULL) { //对结点p做相应处理 p = p->prior; }
我们都知道,单链表的表尾结点的 next 指针是指向 NULL,顾名思义,循环单链表的表尾结点的 next 指针就是指向头结点的
循环单链表的优点:从一个结点出发可以找到其他任何一个结点
typedef int ElemType; typedef struct LNode{ ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode, *LinkList; //初始化一个循环单链表 bool InitList(LinkList &L) { L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点 if (L == NULL) return false; //内存不足,分配失败 L->next = L; //头结点next指针指向头结点 return true; } //判断循环单链表是否为空 bool Empty(LinkList L) { if (L->next == L) return true; else return false; } //判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L, LNode *p) { if (p->next == L) return true; else return false; }
双链表:
循环双链表
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct DNode{ ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinklist; //初始化空的循环双链表 bool InitDLinklist(DLinklist &L) { L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点 if (L == NULL) return false; //内存不足,分配失败 L->prior = L; //头结点的 prior 指向头结点 L->next = L; //头结点的 next 指向头结点 return true; } //判断循环双链表是否为空 bool Empty(DLinklist L) { if (L->next == L) return true; else return false; } //判断结点p是否为循环双链表的表尾结点 bool isTail(DLinklist L, DNode *p) { if (p->next = L) return true; else return false; } void testDLinklist() { //初始化双链表 DLinklist L; InitDLinklist(L); }
//在p结点之后插入s节点 bool InsertNextDNode(DNode *p, DNode *s) { s->next = p->next; p->next->prior = s; s->prior = p; p->next = s; return true; }
//删除p的后继结点q p->next = q->next; q->next->prior = p; free(q);
单链表:各个结点在内存中星罗棋布、散落天涯
静态链表:分配一整片连续的内存空间,各个结点集中安置,0 号结点充当 “头结点”,下一个结点的数组下标(也称为游标)充当 “指针”,游标为 -1 时表示已经到达表尾
静态链表是用数组的方式来实现的链表,其优点为 —— 增、删操作不需要大量移动元素;缺点为 —— 不能随机存取,只能从头结点开始依次往后查找;容量固定不可变
#define MaxSize 10 //静态链表的最大长度 struct Node{ ElemType data; //存储数据元素 int next; //下一个元素的数组下标 };
或者
#define MaxSize 10 //静态链表的最大长度 typedef struct { ElemType data; //存储数据元素 int next; //下一个元素的数组下标 } SLinkList[MaxSize];
SLinkList a 相当于 struct Node a[MaxSize]
初始化
把 a[0] 的 next 设置为 -1
把空的结点的 next 设置为 -2
查找
从头结点出发依次往后遍历结点
插入位序为 i 的结点
删除某个结点
顺序表和链表的比较
从逻辑结构来说,顺序表和链表都属于线性表,都是线性结构
从存储结构来说,顺序表采用顺序存储,而链表采用链式存储
顺序表
优点:支持随机存取,存取密度高
缺点:大片连续空间分配不方便,改变容量不方便
链表:
优点:离散的小空间分配方便,改变容量方便
缺点:不可随机存取,存储密度低
从基本操作来看
创
销
增删
查
综上所述