?、目录总览
1、线性表
定义：线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n = 0 时线性表是一个空表。若用L命名线性表，则其一般表示为：
L = (a1,a2,....,ai,ai+1,.....,an)
线性表的特点：
- 线性表中的元素的个数是有限的
- 线性表中的元素有先后次序
- 线性表中的数据类型都相同，这意味着每个元素占有相同大小的存储空间
- ai 是线性表中的 “第i个” 元素线性表中的位序（位序是从1开始，数组下标从0开始）
- a1是表头元素，an是表尾元素
- 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
2、顺序表
定义：把用顺序存储的方式实现的线性表叫做顺序表
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表有两种实现方式：静态分配实现和动态分配实现
2.1、静态分配实现
#define MaxSize 10; //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(静态分配方式)
2.2.1、初始化顺序表
#include<stdio.h>
#define MaxSize 10; //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
// 基本操作-初始化一个顺序表
void InitList(SqList &L){
for(int i=0;i<MaxSize;i++)
{
L.data[i] = 0; //将所有数据元素设置为默认初始值
}
L.length = 0; //顺序表初始长度为0
}
int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
return 0;
}
2.2、动态分配实现
#define MaxSize 10; //定义最大长度
typedef struct{
ElemType *data; //指针指向第一个数据元素
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义(动态分配方式)
2.2.1、初始化顺序表
#define MaxSize 10; //定义最大长度
#include<stdio.h>
#include<stdlib.h>
typedef struct{
ElemType *data; //指针指向第一个数据元素
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义
// 基本操作-初始化一个顺序表
void InitList(SeqList &L){
//用malloc函数申请一片连续的存储空间
L.data=(ElemType *)malloc(sizeof(ElemTyoe)*InitSize);
L.length = 0; //顺序表初始长度为0
L.MaxSize = InitSize; //顺序表的最大长度
}
// 增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
int *p = L.data; //让指针p指向顺序表中的第一个数据元素
L.data=(ElemType *)malloc(sizeof(ElemType)*(L.MaxSize+len));
for(int i=0; i<L.length; i++){
L.data[i] = p[i]; //将数据复制到新区域
}
L.MaxSize = L.MaxSize + len; //顺序表最大长度增加 len
free(p); //释放原来的内存空间
}
int main(){
SeqList L; //声明一个顺序表
InitList(L);//初始化顺序表
// 往顺序表中随便插入几个元素
IncreaseSize(L,5);
return 0;
}
2.3、顺序表的特点
-
随机访问：即可以在O(1)时间内中找到第i个元素
-
存储密度高，每个节点只存储数据元素
-
扩展容量不方便
-
插入、删除操作不方便，需要移动大量元素
2.4、顺序表的插入
ListInsert(&L,i,e) ：插入操作，在表L中的第 i 个位置上插入指定元素e
#define MaxSize 10; //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(静态分配方式)
// 插入操作:在L的位序 i 处插入元素e
bool ListInsert(SqList &L,int i,int e){
if(i<1 || i>L.length+1) //判断i的范围是否有效
return false;
if(L.length >= MaxSize) //当前存储空间已满,不能插入
return false;
//将第i个元素及之后的元素后移
for(int j=L.length;j>=i;j--)
{
L.data[j] = L.data[j-1];
}
L.data[i-1]=e; //在位置i处放入e,注意位序、数组下标的关系
L.length++; //长度加1
return true;
}
int main(){
SqList L; //声明一个顺序表
InitList(L);//初始化顺序表
//...此处省略一些代码,插入几个元素
ListInsert(L,3,3);
return 0;
}
2.4.1、插入操作时间复杂度
只需关注最深层循环语句的执行次数与问题规模n的关系
//将第i个元素及之后的元素后移
for(int j=L.length;j>=i;j--)
{
L.data[j] = L.data[j-1];
}
- 最好情况：新元素插入到表尾，不需要移动元素，时间复杂度O(1)
- 最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动，循环n次，时间复杂度O(n)
- 平均情况：假设新元素插入到任何一个位置的概率相同，时间复杂度O(n)
2.5、顺序表的删除
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
bool ListDelete(SqList &L,int i,int &e){
if(i<1 || i>L.length+1) //判断i的范围是否有效
return false;
e = L.data[i-1]; //将被删除的元素赋值给e
//将第i个位置后的元素前移
for(int j=i;j<length;j++)
{
L.data[j-1] = L.data[j];
}
L.length--; //线性表长度减1
return true;
}
int main(){
SqList L; //声明一个顺序表
InitList(L);//初始化顺序表
//...此处省略一些代码,插入几个元素
int e = -1; //用变量e把删除的元素"带回来"
if(ListDelete(L,3,e)){
print("已删除第3个元素,删除元素值为=%d\n",e);
}else{
print("位序i不合法,删除失败\n");
}
return 0;
}
- 这里函数定义中的参数e加了引用符号，目的是使得在此时声明的变量e和main函数中声明的变量e是同一片内存空间
2.5.1、删除操作时间复杂度
只需关注最深层循环语句的执行次数与问题规模n的关系
//将第i个位置后的元素前移
for(int j=i;j<length;j++)
{
L.data[j-1] = L.data[j];
}
- 最好情况：删除表尾元素，不需要移动其他元素，最好时间复杂度O(1)
- 最坏情况：删除表头元素，需要将后续的 n-1 个元素全都向前移动。循环n-1 次，最坏时间复杂度O(n)
- 平均情况：平均时间复杂度O(n)
2.5.2、总结
2.6、顺序表的查找
2.6.1、静态分配按位查找
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值
typedef struct{
ElemType data[MaxSize]; //用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(静态分配方式)
ElemType GetElem(SqList L,int i){
return L.data[i-1];
}
2.6.2、动态分配按位查找
#define InitSize 10; //顺序表的初始长度
typedef struct{
ElemType *data; //指针指向第一个数据元素
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义(动态分配方式)
ElemType GetElem(SqList L,int i){
return L.data[i-1]; //和访问普通数组的方法一样
}
2.6.3、按位查找时间复杂度
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素?"随机存取"特性，按位查找的时间复杂度为O(1)
2.6.4、按值查找
LocateElem(L,e)：按值查找操作。在表L中查找值为e的元素
#define InitSize 10; //顺序表的初始长度
typedef struct{
ElemType *data; //指针指向第一个数据元素
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义(动态分配方式)
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ElemType e){
for(int i=0;i<L.length;i++)
{
if(L.data[i]==e)
{
return i+1; //数组小标为i的元素值等于e,返回其位序i+1
}
return 0; //退出循环,说明查找失败
}
}
2.6.5、按值查找时间复杂度
关注最深层循环语句的执行次数与问题规模n的关系，问题规模n=L.length（表长）
int LocateElem(SeqList L,ElemType e){
for(int i=0;i<L.length;i++)
{
if(L.data[i]==e)
{
return i+1; //数组小标为i的元素值等于e,返回其位序i+1
}
return 0; //退出循环,说明查找失败
}
}
- 最好情况：目标元素在表头，只需要循环1次，最好的时间复杂度为O(1)
- 最坏情况：目标元素在表尾，需要循环n次，最坏时间复杂度为O(n)
- 平均情况：O(n)
2.6.6、总结
3、单链表
顺序表：用顺序存储结构实现的线性表叫做顺序表
- 顺序表优点：可随机存取，存储密度高
- 顺序表缺点：要求大片连续空间，改变容量不方便
链表：用链式存储结构实现的线性表叫做链表，链表分为：
- 单链表
- 双链表
- 循环链表
- 静态链表
单链表优点：不要求大片连续空间，改变容量方便
单链表缺点：不可随机存取，要耗费一定空间存放指针
3.1、单链表的定义
typedef struct LNode{ //定义单链表结点类型
ElemType data; //定义单链表结点类型(数据域)
struct LNode * next; //每个节点存放一个数据元素(指针域)
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
//增加一个新的结点:在内存中申请一个结点所需空间,并用指针p指向这个结点
LNode *p =(LNode *)malloc(sizeof(LNode));
// 上述定义代码等价于
struct LNode{
ElemType data;
struct LNode *next;
};
typedef struct LNode LNode; //struct LNode = LNode
typedef struct LNode * LinkList; //struct LNode *= LinkList
//增加一个新的结点:在内存中申请一个结点所需空间,并用指针p指向这个结点
struct LNode *p =(struct LNode *)malloc(sizeof(struct LNode))
要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
LNode *L; //声明一个指向单链表的第一个结点的指针
LinkList L; //声明一个指向单链表的第一个结点的指针
上述两种声明方式有什么区别呢？
LNode *： 强调这是一个结点LinkList：强调这是一个单链表
3.2、初始化不带头结点的单链表
typedef struct LNode{ //定义单链表结点类型
ElemType data; //定义单链表结点类型(数据域)
struct LNode * next; //每个节点存放一个数据元素(指针域)
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
// 初始化一个空的单链表
bool InitList(LinkList &L){
L = NULL; //空表,暂时还没有任何结点
return true;
}
void test(){
LinkList L; //声明一个指向单链表的指针
//初始化一个空表
InitList(L);
}
3.3、不带头结点的单链表是否为空
//判断单链表是否为空
bool Empty(LinkList L){
return (L==NULL);
}
3.4、初始化带头结点的单链表
typedef struct LNode{ //定义单链表结点类型
ElemType data; //定义单链表结点类型(数据域)
struct LNode * next; //每个节点存放一个数据元素(指针域)
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
//初始化一个单链表(带头结点)
bool InitList(LinkList &L){
//用malloc申请一片空间存一个结点
//并且把malloc返回的地址赋给头指针L,也就是说头指针L是指向了这个结点
L =(LNode *)malloc(sizeof(LNode));
if(L==NULL) //分配不足,分配失败
{
return false;
}
L->next = NULL; //头节点之后暂时还没有结点
return true;
}
void test(){
LinkList L; //声明一个指向单链表的指针
//初始化一个空表
InitList(L);
}
3.5、带头结点的单链表是否为空
//判断单链表是否为空(带头结点)
bool Empty(LinkList L){
if(L->next == NULL){
return true;
}else{
return false;
}
}
3.6、单链表的插入
3.6.1、带头结点按位序插入
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e
(找到第i-1个结点，将新结点插入其后)
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1){
return false;
}
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点,头结点是第0个结点(不存是数据)
while(P!=NULL && j<i-1){ //循环找到第 i-1 个结点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
{
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data=e;
//将s指向结点的next指针指向p指向结点的next指针
s->next = p->next;
p->next = s; //将p指向结点的next指针指向s
return true; //插入成功
}
分析：
- 如果 i=1(也就是在表头插入元素)：时间复杂度O(1)
- 如果 i = 3(也就是在表中插入元素)
- 如果 i = 5(也就是在表尾插入元素)：时间复杂度O(n)
3.6.2、不带头结点按位序插入
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e
(找到第i-1个结点，将新结点插入其后)
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1)
{
return false;
}
if(i==1) //插入第1个结点的操作与其他结点操作不同
{
LNode *s =(LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s; //头指针指向新结点
return true;
}
LNode *p; //指针p指向当前扫描到的结点
int j=1; //当前p指向的是第几个结点
p = L; //p指向第1个结点(注意:不是头结点)
while(P!=NULL && j<i-1){ //循环找到第 i-1 个结点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
{
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data=e;
//将s指向结点的next指针指向p指向结点的next指针
s->next = p->next;
p->next = s; //将p指向结点的next指针指向s
return true; //插入成功
}
}
- 结论：不带头结点写代码不方便，推荐用带头结点
- 注意：考试中带头、不带头都有可能考察，注意审题
3.7、指定结点的后插操作
后插操作：在结点之后插入元素
//后插操作:在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
if(p==NULL)
{
return false;
}
LNode *s =(LNode *)malloc(sizeof(LNode));
if(s==NULL) //某些情况下有可能分配失败,比如内存不足
{
return false;
}
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
3.8、指定结点的前插操作
前插操作：在结点之前插入元素
//前插操作:在p结点之前插入元素e
bool InsertPriorNode(LNode *p,ElemType e){
if(p==NULL)
{
return false;
}
LNode *s =(LNode *)malloc(sizeof(LNode));
if(s==NULL) //内存分配失败
{
return false;
}
s->next = p->next;
p->next = s; //新结点 s 连接到 p 之后
s->data = p->data; //将p中元素复制到s中
p->data = e; //p中元素覆盖为e
return true;
}
王道书中的版本：
//前插操作:在p结点之前插入结点s
bool InsertPriorNode(LNode *p,LNode *s){
if(p==NULL || s==NULL)
{
return false;
}
s->next = p->next;
p->next = s; //s连到p之后
ElemType temp = p->data; //交换数据域部分
p->data = s->data;
s->data = temp;
return true;
}
3.9、单链表的删除
3.9.1、带头结点按位序删除
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值(找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点)
bool ListDelete(LinkList &L,int i,ElemType &e){
if(i<1)
{
return false;
}
LNode *p; //指针p指向当前扫描到的结点
int j = 0; //当前p指向的是第几个结点
p = L; //L指向头结点,头结点是第0个结点(不存数据)
while(p!=NULL && j<i-1) //循环找到第 i-1 个结点
{
p = p->next;
j++
}
if(p==NULL) // i值不合法
{
return false;
}
if(p->next == NULL) //第 i-1 个结点之后已无其他结点
{
return false;
}
LNode *q = p->next; //令q指向被删除结点
e = q->data; //用e返回元素的值
p->next = q->next; //将*q结点从链中断开
free(q); //释放结点的存储空间
return true; //删除成功
}
3.9.2、指定结点的删除
bool DeleteNode(LNode *p)：删除结点p
//删除指定结点p
bool DeleteNode(LNode *p){
if(p==NULL)
{
return false;
}
LNode *q = p->next; //令q指向*p的后继结点
p->data = p->next->data;//和后继结点交换数据域
p->next = q->next; //将*q结点从链中"断开"
free(q); //释放后继结点的存储空间
return true;
}
3.10、单链表的查找
3.10.1、按位查找
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
//按位查找,返回第i个元素(带头结点)
LNode *GetElem(LinkList L,int i){
if(i<0)
{
return NULL;
}
LNode *p; //指针p指向当前扫描到的结点
int j = 0; //当前p指向的是第几个急待你
p = L; //L指向头结点,头结点是第0个结点(不存数据)
while(p!=NULL && j<i) //循环找到第i个结点
{
p = p->next; //让p指针依次向后移
j++;
}
return p;
}
- 如果i=0
- 如果 i = 8(i大于链表长度)
王道书版本：
LNode *GetElem(LinkList L,int i){
int j=1;
LNode *p = L->next;
if(i==0)
{
return L;
}
if(i<1)
{
return NULL;
}
while(p!=NULL && j<i)
{
p = p->next;
j++;
}
return p;
}
3.10.2、按值查找
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
//按值查找,找到数据域 ==e的结点
LNode *LocateElem(LinkList L,ElemType e){
LNode *p = L->next;
//从第1个结点开始查找数据域为e的结点
while(p != NULL && p->data != e)
{
p = p->next;
}
return p; //找到后返回该结点指针,否则返回NULL
}
3.10.3、求单链表长度
//求表的长度
int Length(LinkList L)
{
int len = 0; //统计表长
LNode *p = L;
while(p->next !=NULL)
{
p = p->next;
len++;
}
return len;
}
3.10.4、总结
3.11、单链表的建立
如果给你很多个数据元素，要把它们存到一个单链表里边，咋弄呢？
- 初始化一个单链表
- 每次取一个数据元素，插入到表尾/表头
3.11.1、尾插法建立单链表
LinkList List_TailInsert(LinkList &L) //正向建立单链表
{
int x; //设ElemType为整型
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
LNode *s,*r=L; //r为表尾指针
scanf("%d",&x); //输入结点的值
while(x!=9999)
{
s=(LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾结点
scanf("%d",&x);
}
r->next = NULL; //尾结点指针置空
return L;
}
尾插法的时间复杂度：O(n)
3.11.2、头插法
头插法:对头结点进行后插操作
LinkList List_HeadInsert(LinkList &L){
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode)); //创建头结点
L->next = NULL; //初始化为空链表(初始化单链表,都先把头指针指向NULL)
scanf("%d",&x); //输入结点的值
while(x!=9999) //输入9999表示结束
{
s = (LNode *)malloc(sizeof(LNode)); //创建新结点
s->data = x;
s->next = L->next;
L->next = s; //将新结点插入表中,L为头指针
scanf("%d",&x);
}
return L;
}
3.11.3、总结
4、双链表
4.1、双链表的定义
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinklist;
4.2、双链表的初始化
//初始化双链表(带头结点)
bool InitDLinkList(DLinklist &L){
L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
if(L==NULL) //内存不足,分配失败
{
return false;
}
L->prior = NULL; //头结点的prior永远指向NULL
L->next = NULL; //头结点之后暂时还没有结点
return true;
}
viod testDLinkList(){
//初始化双链表
DLinklist L;
InitDLinkList(L);
}
DLinklist等价于DNode *DLinklist强调这是一个链表DNode *强调这是一个结点
4.3、判断双链表是否为空
判断双链表是否为空：判断头结点的下一个是否为空
//判断双链表是否为空(带头结点)
bool Empty(DLinklist L){
if(L->next == NULL)
{
return true;
}else{
return false;
}
}
4.4、双链表的插入
4.4.1、后插操作
如果p结点是最后一个结点(特殊情况)：
//在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是中间一个结点：
4.4.2、按位序插入
按位序插入：只需从头结点开始，找到某一个位序的前驱结点，然后对这个前驱结点执行后插操作
4.4.3、前插操作
前插操作：只需找到此结点的前驱结点，然后对其前驱结点进行后插操作，即为前插操作
4.5、双链表的删除
当q结点不是最后一个结点时：
//删除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(q); //释放结点空间
return true;
}
当q结点是最后一个结点时：
4.6、双链表的销毁
void DestoryList(DLinklist &L){
//循环释放各个数据结点
while(L->next !=NULL)
{
DeleteNextDNode(L);
}
free(L); //释放头结点
L=NULL; //头指针指向NULL
}
4.7、双链表的遍历
后向遍历：
while(p != NULL){
//对结点p做相应处理
p = p->next;
}
前向遍历：
while(p != NULL){
//对结点p做相应处理
p = p->prior;
}
前向遍历(跳过头结点)：
while(p->prior!=NULL){
//对结点p做相应处理
p = p->prior;
}
4.8、总结
5、循环链表
- 单链表：表尾结点的next指针指向NULL
- 循环单链表：表尾结点的next指针指向头结点
5.1、循环单链表
头结点next指针指向头结点：
5.1.1、初始化循环单链表
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;
}
5.1.2、判断循环单链表是否为空
判断循环单链表是否为空：判断头结点的next指针是否指向它自己
bool Empty(LinkList L){
if(L->next == L)
{
return true;
}else{
return false;
}
}
5.1.3、判断循环单链表表尾结点
//判断结点p是否是循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
if(p->next == L)
{
return true;
}else{
return false;
}
}
5.2、循环双链表
- 双链表：表头结点的prior指向NULL，表尾结点的next指向NULL
- 循环双链表：表头结点的prior指向表尾结点，表尾结点的next指向头结点
5.2.1、初始化循环双链表
初始化循环双链表：让头结点的prior和next指针都指向头结点
bool InitDLinkList(DLinklist &L){
L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
if(L == NULL) //内存不足,分配失败
{
return false;
}
L->prior = L; //头结点的prior指向头结点
L->next = L; //头结点的next指向头结点
return true;
}
void testDLinkList(){
//初始化循环双链表
DLinklist L;
InitDLinkList(L);
}
5.2.2、判断循环双链表是否为空
判断循环双链表是否为空：头结点的next指针是否指向了它自身
//判断循环双链表是否为空
bool Empty(DLinkList L){
if(L->next == L)
{
return true;
}else{
return false;
}
}
5.2.3、判断循环双链表表尾结点
判断循环双链表表尾结点:这个结点的next指针是否指向了头结点
//判断结点p是否是循环双链表的表尾结点
bool isTail(DLinkList L,DNode *p){
if(p->next == L)
{
return true;
}else{
return false;
}
}
5.3、循环双链表的插入
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
s->next = p->next; //将结点*s插入到结点*p之后
p->next->prior = s;
s->prior = p;
p->next = s;
}
5.4、循环双链表的删除
//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);
5.5、总结
6、静态链表
单链表：各个结点在内存中星罗棋布、散落天涯。
静态链表：分配一整片连续的内存空间，各个结点集中安置。静态链表中的每个结点包含数据元素和下一个结点的数组下标。
我们看上图：
- 静态链表中数组下标为 0 的结点充当头结点的角色，而头结点的下一个结点是存储在数组下标为 2 的位置，数组下标为 2 的位置结点数据元素为 e1，下一个结点为数组下标为 1 的结点，也就是数据元素为 e2 的结点。
- 单链表中表尾指针是指向NULL，静态链表中游标为 -1 表示已经到达表尾。
- 假如每个数据元素 4B，每个游标 4B(每个结点共8B)，设起始地址为 addr，则 e1 的存放地址为 addr + 8 * 2
6.1、代码定义静态链表
#define MaxSize 10 // 静态链表的最大长度
typedef struct{ // 静态链表结构类型的定义
ElemType data; // 存储数据元素
int next; // 下一个元素的数组下标
}SLinkList[MaxSize];
上述代码其实等价于下面代码：
#define MaxSize 10 // 静态链表的最大长度
struct Node{ // 静态链表结构类型的定义
ElemType data; // 存储数据元素
int next; // 下一个元素的数组下标
};
typedef struct Node SLinkList[MaxSize]; // 给 struct Node 起别名为 SLinkList[MaxSize]
// 可以用 SLinkList 定义 "一个长度为MaxSize的Node型数组"
SlinkList a;
// 这个数组元素有 MaxSize 这么多,每个数组元素类型都是 struct Node
// 等价于 struct Node a[MaxSize]
7、第一章总结
- 顺序表和链表都是线性结构，都属于线性表
| 线性表 | 优点 | 缺点 |
|---|---|---|
| 顺序表(顺序存储) | 支持随机存取、存储密度高 | 大片连续空间分配不方便，改变容量不方便 |
| 链表(链式存储) | 离散的小空间分配方便，改变容量方便 | 不可随机存取，存储密度低 |
- 创建
- 销毁
- 增删
- 查找
-
表长难以预估、经常要增加/删除元素——链表
-
表长可预估、查询（搜索）操作较多——顺序表
