数据结构(二)——线性表


线性表的定义和基本操作

我们先来分析数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构)

线性表的定义(逻辑结构)

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。

若用L命名线性表,则其一般表示为:L=(a1,a2,…,an)

几个概念:

  1. ai是线性表中的“第i个”元素线性表中的位序
  2. a1是表头元素,an是表尾元素
  3. 除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继

线性表的基本操作

  • InitList(&L):初始化表。构造一个空的线性表L,分配内存空间。
  • DestroyList(&L):销毁操作。销毁线性表,并释放线性表L所占用的内存空间。
  • ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
  • ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
  • LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
  • GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
  • Length(L):求表长。返回线性表L的长度,即L中数据元素的个数。
  • PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
  • Empty(L):判空操作。若L为空表,则返回true,否则返回false。

其实学到后面就更会发现,对数据的操作,主要就是创造销毁、增删改查。


线性表的存储/物理结构

顺序表(顺序存储)

定义

顺序表——用顺序存储的方式来实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。

静态分配的实现

静态分配的代码模板:

1
2
3
4
5
#define MaxSize 10   //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(静态分配方式)

给各个数据元素分配连续的存储空间,大小为MaxSize*sizeof(ElemType)

对于静态分配的顺序表,如果数组满了怎么办?
如果数组满了,那只能放弃了,因为顺序表的长度刚开始确定后就无法修改(存储空间是静态的)

动态分配的实现

动态分配的顺序表代码模板:

1
2
3
4
5
6
#define InitSize 10  //顺序表的初始长度
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义(动态分配方式)

C语言中使用malloc、free函数来实现动态资源的申请与释放,下面我们来一一了解:

  1. malloc函数可以在内存中申请以字节为单位个内存空间,并返回一个指向这片内存空间起始位置的指针(需要强制转换指针类型为你定义的数据元素类型指针)
  2. free即可以释放malloc申请的空间

下面是一段增加动态数组长度的函数,通过类似这样的函数,我们就可以实现动态地分配顺序表的空间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void IncreaseSize(SeqList &L,int len){
//一个局部指针,指向数据区
int *p=L.data;
//顺序表的指针指向一片新的内存空间
L.data=(int *)malloc(L.MaxSize+len)*sizeof(int));
//将原数据区的数据搬运到新的大的内存空间中
for(int i=0;i<L.length;i++){
L.data[i]=p[i];
}
//更改顺序表的最大长度
L.MaxSize=L.MaxSize+len;
//释放p指针所指向的内存空间(即原数据区)
free(p);
}

顺序表的特点

  1. 随机访问,即可以在O(1)时间内找到第i个元素
  2. 存储密度高,每个节点只存储数据元素
  3. 扩展容量不方便,静态分配方式不可以扩展容量;动态分配方式扩展容量需要的时间复杂度是比较高的
  4. 插入、删除操作不方便,需要移动大量的元素

各种操作具体实现

下面我们来依次实现线性表的各个常用操作

插入函数

ListInsert(&L,i,e):插入操作。在表L中的第i个位置(位序)上插入指定元素e。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MaxSize 10 //定义最大长度
typedef struct{
int data[MaxSize]; //用静态数组存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义

void ListInsert(SqList &L,int i,int e){
//将第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
}

int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
//…………
ListInsert(L,3,3);
return 0;
}

上述“插入”代码其实健壮性并不好,有可能插入位置是一个非法位置、有可能插入时顺序表已经满了……这些都应该被考虑进去,故我们可以加强一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool ListInsert(SqList &L,int i,int e){
//插入范围合法性判断
if(i<1||i>L.length+1){
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;
}

好的代码,应该具有健壮性,能够处理异常情况

下面我们来分析时间复杂度:

  • 最好情况:新元素插入到表尾,不需要移动元素,循环0次,最好时间复杂度=O(1)
  • 最坏情况:新元素插入到表头,需要将原有的n个元素全都向后移动,循环n此,最坏时间复杂度=O(n)
  • 平均情况:假设新元素插入到任何一个位置的概率相同,即i=1,2,3……length+1的概率都是p=1/(n+1)。i=1,循环n次;i=2,循环n-1次;i=3,循环n-2次……i=n+1时,循环0次。平均循环次数=n*p+(n-1)*p+……+1*p=n/2,故平均时间复杂度也就是O(n)

删除函数

ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define MaxSize 10 //定义最大长度
typedef struct{
int data[MaxSize]; //用静态数组存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义

void ListDelete(SqList &L,int i,int &e){
//判断i的范围是否合法
if(i<1||i>L.length) {
return false;
}
e=L.data[i-1]; //将被删除的元素赋值给e
//将第i个位置后面的元素前移
for(int j=i;j<L.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))
printf("删除成功,删除的元素值为%d\n",e);
else
printf("删除位置不合法\n");
return 0;
}

下面我们来分析时间复杂度:

  • 最好情况:删除表尾元素,不需要移动元素,循环0次,最好时间复杂度=O(1)
  • 最坏情况:删除表头元素,需要将原有的n个元素全都向后移动,循环n此,最坏时间复杂度=O(n)
  • 平均情况:假设删除任何一个元素的概率相同,即i=1,2,3……length+1的概率都是p=1/(n+1)。i=1,循环n-1次;i=2,循环n-2次;i=3,循环n-3次……i=n时,循环0次。平均循环次数=(n-1)*p+(n-2)*p+……+1*p=(n-1)/2,故平均时间复杂度也就是O(n)

按位查找

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

1
2
3
ElemType GetElem(SeqList L,int i){
return L.data[i-1];
}

由于顺序表的各个数据元素在内存中连续存放,因此可以根据其实地址和数据元素大小立即找到第i个元素,故按位查找的时间复杂度是O(1)–“随机存取”特性。

按值查找

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

1
2
3
4
5
6
7
8
int LocateElem(SeqList L,int e){
for(int i<0;i<L.length;i++){
if(L.data[i]==e){
return i+1;
}
}
return 0;
}

有编程常识的我们都知道,“==”可以用来判断基本数据类型,而不能判断结构体类型(除非C++重载运算符),但是请了解:在《数据结构》考研初试中,手写代码可以直接用“==”判断结构体类型

下面我们来分析时间复杂度:

  • 最好情况:O(1)
  • 最坏情况:O(n)
  • 平均情况:假设目标出现在任意一个位置的概率都相同,即i=1,2,3……length的概率都是p=1/n。i=1,循环1次;i=2,循环2次;i=3,循环3次……i=n时,循环n次。平均循环次数=1*p+2*p+……+n*p=(n+1)/2,故平均时间复杂度也就是O(n)

单链表(链式存储)

简介

单链表中每个结点除了存放数据元素外,还要存储指向下一个节点的指针。

  • 优点:不要求大片连续空间,改变容量方便
  • 缺点:不可随机存取,要耗费一定空间存放指针

代码实现

1
2
3
4
struct LNode{               //定义单链表结点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
};

这样我们就可以动态地操作链表,例如需要增加结点时:

1
2
//增加一个新的结点:在内存中申请一个结点所需空间,并用指针p指向这个结点
struct LNode *p=(struct LNode*)malloc(sizeof(struct LNode));

上面我们写类型的时候使用了struct LNode,确实是有点麻烦,这里我们可以使用关键字 typedef,来将数据类型重命名:
typedef <数据类型> <别名>

即下面的两段代码是等价的:

1
2
3
4
>typedef struct LNode{    //定义单链表结点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
>}LNode,*LinkList;
1
2
3
4
5
6
>struct LNode{        //定义单链表结点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
>};
>typedef struct LNode LNode;
>typedef struct LNode *LinkList;

各种操作具体实现

不带头结点的单链表初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct LNode{
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
L=NULL; //空表,暂时还没有任何结点
return true;
}

void test(){
//注意,此处并没有创建一个结点
LinkList L; //声明一个指向单链表的指针
//初始化一个空表
InitList(L);
//…………后续代码…………
}

//判断单链表是否为空
bool Empty(LinkList L){
return (L==NULL);
}

带头结点的单链表初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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=NULL; //头结点之后暂时还没有结点
return true;
}

void test(){
//注意,此处并没有创建一个结点
LinkList L; //声明一个指向单链表的指针
//初始化一个空表
InitList(L);
//…………后续代码…………
}

//判断单链表是否为空(带头结点)
bool Empty(){
if(L->next==NULL)
return true;
else
return false;
}

那么带不带头结点具体有什么区别呢?

  • 不带头结点,写代码更麻烦,对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑;对空表和非空表的处理需要用不同的代码逻辑。
  • 带头结点,写代码会更方便一些,故一般情况下我们都会使用带头结点的单链表。

带头结点的单链表按位序插入

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//在第i个位置插入元素e(带头结点)
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;
p-next=s; //将结点s连到p之后
return true;
}

不带头结点的单链表按位序插入

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1){
return false;
}
//插入第1个结点的操作与其他结点操作不同
if(i==1){
LNode *s=(LNode *)mallac(sizeof(LNode));
s->data=e;
s->next=L;
L=s; //头指针指向新结点
return true;
}
LNode *p; //指针p指向当前扫描到的结点
int j=1; //当前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;
p-next=s; //将结点s连到p之后
return true;
}

指定结点的后插操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//后插操作:在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保存数据元素e
s->next=p->next;
p->next=s; //将结点s连到p之后
return true;
}

指定结点的前插操作

单链表的前插操作,往往需要传入头结点,但是我们下面的示例代码,不需要这样,下面的示例代码是将数据给了一个后继结点,狸猫换太子,而且时间复杂度是常数阶,非常聪明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//前插操作:在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->data=p->next;
p->next=s; //将新结点s连接到p的后面
s->data=p->data; //将p中元素复制到s中
p->data=e; //p中元素覆盖为e
return true;
}

按位序删除(带头结点)

ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
删除思路:找到第i-1个结点,将其指针指向第i+1个结点,并释放第i个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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){
p=p->next;
j++;
}
if(p==NULL){ //i值不合法
return false;
}
//第i-1个结点之后已无其他结点
if(p->next==NULL){
return false;
}
LNode *q=p->next; //令q指向被删除结点
e=q->data; //令q指向被删除结点
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放结点的存储空间
return true; //删除成功
}

最坏时间复杂度和平均时间复杂度:O(n)
最好时间复杂度:O(1)

指定结点的删除

关于指定的结点的删除,一般我们也是用链表指针开始一个个去找,找到符合条件的之后就进行删除。下面我们来一个不利用头结点的,但是这种方法在处理最后一个结点时会出现bug,这里可以进行特殊处理

1
2
3
4
5
6
7
8
9
10
11
//删除指定结点 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;
}

单链表查找(带头结点)

  • GetElem(L,i):按位查找操作。获取表L的第i个位置的元素的值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    LNode * GetELem(LinkList L,int i){
    if(i<0)
    return NULL;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0; //当前指针p指向的是第几个结点
    p=L; //L指向头结点,头结点是第0个结点(不存数据)
    //循环找到第i个结点
    while(p!=NULL&&j<i){
    p=p->next;
    j++;
    }
    return p;
    }
    平均时间复杂度:O(n)



  • LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
    1
    2
    3
    4
    5
    6
    7
    8
    LNode * LocateElem(LinkLIst L,ElemType e){
    LNode *p=L->next;
    //从第1个结点开始查找数据域为e的结点
    while(p!=NULL&&p->data!=e)
    p=p->next;
    //找到后返回该结点指针,否则返回NULL
    return p;
    }
    平均时间复杂度:O(n)

带头结点的表的长度

1
2
3
4
5
6
7
8
9
int Length(LinkList L){
int len=0; //统计表长
LNode *p=L;
while(p->next!=NULL){
p=p->next;
len++;
}
return len;
}

时间复杂度:O(n)

单链表的建立(带头结点)

  • 尾插法建立单链表
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //正向建立单链表
    LinkLIst LIst_TailInsert(LinkList &L){
    int x; //设ElemType为整型
    L=(LinkList)malloc(sizeof(LNode)); //建立头结点
    LNode *s,*r=L; //r为表尾指针
    scanf("%d",&x); //输入结点的值
    //输入9999代表结束
    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;
    }
  • 头插法建立单链表
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //逆向建立单链表
    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;
    }

    头插法、尾插法:核心就是初始化操作、指定结点的后插操作。

双链表(链式存储)

简介

双链表就是在单链表的基础上,再增加一个指向前驱结点的前驱指针。

代码实现

1
2
3
4
5
//定义双链表结点类型
typedef struct DNode{
ElemType data; //数据域
struct DNode * prior,*next; //前驱和后继指针
}DNode,*DLinklist;

各种操作具体实现

双链表的初始化(带头结点)

1
2
3
4
5
6
7
8
9
//初始化双链表
bool InitDLinkList(DLinklist &L){
L=(DNode *)malloc(sizeof(DNode)); //分配一个头结点
if(L==NULL) //内存不足,分配失败
return false;
L->prior=NULL; //头结点的prior永远指向NULL
L->next=NULL; //头结点之后暂时没有结点
return true;
}

判空操作

1
2
3
4
5
6
7
//判断双链表是否为空(带头结点)
bool Empty(DLinklist L){
if(L->next==NULL)
return true;
else
return false;
}

双链表的插入(带头结点)

1
2
3
4
5
6
7
8
9
10
11
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
if(p==NULL||s==NULL)
return false;
s->next=p->next; //将结点*s插入到结点*p之后
if(p->next!=NULL)
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}

双链表删除(带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除结点p的后继结点
bool DeleteNextDNode(DNode *p){
if(p==NULL)
return false;
//找到p的后继结点q
DNode *q=p->next;
if(q==NULL)
return false;
p->next=q->next;
//q结点不是最后一个结点
if(q->next!=NULL)
q->next->prior=p;
//释放结点空间
free(q);
return true;
}

销毁链表(带头结点)

1
2
3
4
5
6
7
8
void DestroyList(DLinklist &L){
//循环释放
while(L->next!=NULL){
DeleteNextDNode(L);
}
free(L); //释放头结点
L=NULL; //头指针指向NULL
}

遍历双链表(带头结点)

1
2
3
4
5
6
7
8
//展示所有元素
void ShowElement(DLinklist L){
while(L->next){
//对结点L->next的各种操作
L=L->next;
}
printf("\n");
}

双链表不可随机存取,按位查找、按值查找操作都只能使用遍历的方式实现,时间复杂度O(n)

循环链表

我们学习的单链表和双链表,最后的指针都指向了NULL,而我们的循环链表,就是将表尾结点的next指针指回了头结点。

循环单链表

  • 当初始化时,我们的头结点指针应该指向自己。

    1
    2
    3
    4
    5
    6
    7
    8
    //初始化一个单链表(带头结点)
    bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode)); //分配一个头结点
    if(L==NULL) //内存不足,分配失败
    return false;
    L->next=L; //头结点之后暂时还没有结点
    return true;
    }
  • 当判空时,直接检测头结点的下一个结点是不是自身即可。

    1
    2
    3
    4
    5
    6
    7
    //判断单链表是否为空(带头结点)
    bool Empty(){
    if(L->next==L)
    return true;
    else
    return false;
    }
  • 对于查找操作,单链表的某一结点不能再找到其前驱的所有结点;而循环单链表则可以再次找到。

  • 我们经常进行头尾结点的操作(头插法、尾插法),我们可以直接将头结点指针L指向链表的最后一个结点,这样只需O(1)的时间复杂度就可以回到头位置进行头操作,而我们的尾操作也可以直接进行,而不需要以前从头移到尾再操作。

循环双链表

  • 初始化操作:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //初始化双链表
    bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode)); //分配一个头结点
    if(L==NULL) //内存不足,分配失败
    return false;
    L->prior=L;
    L->next=L;
    return true;
    }
  • 判空操作

    1
    2
    3
    4
    5
    6
    7
    //判断双链表是否为空(带头结点)
    bool Empty(DLinklist L){
    if(L->next==L)
    return true;
    else
    return false;
    }
  • 双链表的插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //在p结点之后插入s结点
    bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL)
    return false;
    s->next=p->next; //将结点*s插入到结点*p之后
    p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
    }
  • 双链表的删除

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //删除结点p的后继结点
    bool DeleteNextDNode(DNode *p){
    if(p==NULL)
    return false;
    //找到p的后继结点q
    DNode *q=p->next;
    if(q==NULL)
    return false;
    p->next=q->next;
    //q结点不是最后一个结点
    q->next->prior=p;
    //释放结点空间
    free(q);
    return true;
    }

静态链表

什么是静态链表

分配一整片连续的内存空间,各个结点集中安置,每个结点中通过游标来寻找下一个结点。

静态链表是一种用数组来实现的链表,各个逻辑上相邻的结点在物理上不一定相邻

静态链表不能随机存取,只能从头结点开始依次往后查找;容量固定不可变,故静态链表往往只适用于一些不支持指针的低级语言,或是数据元素数量固定不变的场景(如操作系统的文件分配表FAT)

用代码定义一个静态链表

1
2
3
4
5
6
7
8
9
#define MaxSize 10  //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
};

void testSLinkList(){
struct Node a[MaxSize]; //数组a作为静态链表
}

其中,我们可以直接将数组作为一种类型,即:

1
2
3
4
5
>#define MaxSize 10;
>typedef struct{
ElemType data;
int next;
>}SLinkList[MaxSize];

如上代码也就等价于:

1
2
3
4
5
6
>#define MaxSize 10;
>struct Node{
ElemType data;
int next;
>};
>typedef struct Node SLinkList[MaxSize];




商业转载 请联系作者获得授权,非商业转载 请标明出处,谢谢