考研数据结构复习---线性表

考纲内容
1.线性表的定义和基本操作
2.线性表的实现
顺序存储;链式存储;线性表的应用

本章知识框架

复习提示
线性表是考研命题的重点.这类算法题实现起来比较容易,代码量少,但是要求具有最优的性能(时间,空间复杂度),才能获得好的分数.

线性表目录

• 1.线性表的定义和基本操作
• • 1.1线性表的定义
  • 1.2线性表的基本操作
  • 试题精选
  • • 选择题
• 2.线性表的顺序表示
• • 2.1顺序表的定义
  • 2.2顺序表上基本操作的实现
  • • • • 1.插入操作
        • 2.删除操作
        • 3.按值查找(顺序查找)
  • 试题精选
  • • 选择题
• 3.线性表的链式表示
• • 3.1单链表的定义
  • 3.2单链表上基本操作的实现
  • • • • 1.采用头插法建立单链表
        • 2.采用尾插法建立单链表
        • 3.按序号查找结点值
        • 4.按值查找表结点
        • 5.插入结点操作
        • 6.删除节点操作
        • 7.求表长操作
  • 3.3双链表
  • • • • 1.双链表的插入操作
        • 2.双链表的删除操作
  • 3.4循环链表
  • • • • 1.循环单链表
        • 2.循环双链表
  • 3.5静态链表
  • 3.6顺序表和链表的比较

1.线性表的定义和基本操作

1.1线性表的定义

线性表是具有相同数据类型的n(n>0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表.若用L命名线性表,则其一般表示为

L=(a1,a2,...,ai,ai+1,...,an)
1

式中,a1是唯一的"第一个"数据元素,又称表头元素;an是唯一的"最后一个"数据元素,又称为表尾元素.除第一个元素外,每个元素都有且仅有一个直接前驱,除最后一个元素外，每个元素有且仅有一个直接后继，以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来，由此我们得出线性表的特点如下：

1.表中元素的个数有限
2.表中元素具有逻辑上的顺序性，表中元素有其先后次序。
3.表中元素都是数据元素，每个元素都是单个元素。
4.表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
5.表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容.

1.2线性表的基本操作

一个数据结构的基本操作是指其最核心,最基本的操作.其他较复杂的操作可通过调用其基本操作来实现，线性表的主要操作如下:

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

注意:
1.基本操作的实现取决于采用哪种存储结构,存储结构不同，算法的实现也不同.
2.&表示c++中的引用调用，若传入的变量是指针型变量，且在函数体内要对传入的指针进行改变，则会用到指针变量的引用型，在c中采用指针的指针也可达到同样的效果.

试题精选

选择题

1.线性表示具有n个(C)的有限序列.
A.数据表
B.字符
C.数据元素
D.数据项
1
2
3
4
5

1.C
线性表由具有相同数据类型的有限元数据元素组成的，数据元素由数据线组成的.

2.以下(B)是一个线性表
A.有n个实数组成的集合
B.有100个字符组成的序列
C.所有整数组成的序列
D.邻接表
1
2
3
4
5

2.B
线性表定义的要求为相同数据类型,有限序列
选项C的元素个数是无穷个,错误;
选项A集合中的元素没有前后驱关系,错误;
选项D属于存储结构，线性表是一种逻辑结构，不要将二者混为一谈.

3.在线性表中除开始元素外每个元素(A)
A.只有一个唯一的前驱元素
B.只有一个唯一的后期元素
C.有多个前驱元素
D.有多个后继元素
1
2
3
4
5

线性表中除最后一个或第一个元素外，每个元素只有一个后继或前驱元素。

2.线性表的顺序表示

2.1顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素ai在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。
假定线性表的元素类型为Elemtype，则线性表的顺序存储类型描述为，

#define Maxsize 50//定义线性表的最大程度
typedef struct{
	ElemType data[Maxsize];//顺序表的元素
	int length;//顺序表的当前长度
}SqList;//顺序表的类型定义
1
2
3
4
5

一维数组是可以静态分配的，也可以是动态分配的，在静态分配时，由于数组的大小和空间事先已经固定.一旦空间站满，在新加入数据将会产生溢出，进而导致程序崩溃.

而在动态分配时，存储数组的空间是在程序执行过程中，通过动态存储分配语句分配的，一旦空间占满时，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的，而不需要为线性表一次性的划分所有空间。

#define Maxsize 100//表长度的初始定义
typedef struct{
	ElemType *data;//指示动态分配数组的指针
	int MaxSize,length;//数组的最大容量和当前个数
}SqList;//动态分配数组顺序表的类型定义
1
2
3
4
5

#define Initsize 100
typedef struct{
	Element *data;//指示动态分配数组的指针
	int MaxSize,length;//数组的最大容量和当前个数
}SeqList;//动态分配数组顺序表的类型定义
1
2
3
4
5

C的初始动态分配语句为:

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
1

C++的动态分配语句为：

L.data=new ElemType(InitSize);
1

注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。

1.顺序表最主要的特点是随机访问，即通过首地址和元素序号，可在时间o（1）内找到指定的元素。
2.顺序表的存储密度高，每个节点只存储数据元素。
3.顺序表逻辑上相邻的元素，物理上也相邻，所以插入和删除操作需要移动大量元素.

2.2顺序表上基本操作的实现

1.插入操作

在顺序表L的第i个位置插入新元素e,若i的输入不合法则返回false，表示插入失败;否则将顺序表的第i个元素及其后的所有元素用一个位置腾出一个空位置插入新元素1，顺序表长度增加1，插入成功返回true.

bool ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1)//判断i的范围是否有效
		return false;
	if(L.length>=MaxSize)//当前存储空间已满，不能插入，
		return false;
	for(int j=L.length;j>=i;j--)//将第i个元素其之后的元素后移.
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;//在位置i处放入e。
	L.length++;//线性表长度加1。
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

注意区别线性表的位置和数组下标。为何判断插入位置是否合法时，if语句中用length+1,而移动元素的for语句中只用length?
最好情况:在表尾插入(即i=n+1),元素后移与语句将不执行,时间复杂度为o(1).
最坏情况:在表头插入(即i=1),元素后移语句将执行n次时间复杂度为o(n)。
平均情况:假设pi是在第i个位置上插入一个节点的概率。则在长度为n的线性表中插入一个节点时。所需移动节点的平均次数为2/n。
因此线性表插入算法的平均时间复杂度为o(n)。

2.删除操作

删除顺序表L中i(l<=i<=L.length)的未知元素。成功返回true。并将被删除的元素用引用变量e返回。否则返回false。

bool ListDelete(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length)//判断i的范围是否有效
		return false;
	e=L.data[i-1]//将被删除的元素赋值给e
	for(int j=i;j<L.length;j++)//将第i个元素其之后的元素前移.
		L.data[j-1]=L.data[j];
	L.length--;//线性表长度减1。
	return true;
}
1
2
3
4
5
6
7
8
9

最好情况:删除表尾元素,无需移动元素，时间复杂度为o(1)。
最坏情况:删除表头元素,需移动第一个元素外的所有元素，时间复杂度为o(n)。
平均情况:线性表删除算法的平均时间复杂度为o(n)。

3.按值查找(顺序查找)

在顺序表l中查找第1个元素值等于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;//退出循环,说明查找失败
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最好情况:查找的元素就在表头,只需比较一次时间复杂度为o(1)。
最坏情况:查找的元素在表尾或不存在时,需要比较n次时间复杂度为o(n)。
平均情况:n-1/2。
线性表按值查找算法的平均时间复杂度为o(n)。

试题精选

选择题

1.下列叙述(A)是顺序存储结构的优点。
A存储密度大。
B插入运算方便。
C删除运算方便。
D方便的运用于各种逻辑结构的存储表示。
1
2
3
4
5

顺序表不像链表那样，要在节点中存放指针域。因此存储密度较大。A正确。B和C选项是链表的优点。D是错误的,比如对于树形结构顺序表显然不如列表表示起来方便。

2.线性表的顺序存储结构是一种(A)
A随机存取的存储结构。
B顺序存储的存储结构。
C索引存取的存储结构。
D散列存取的存储结构。
1
2
3
4
5

注意存取方式是指读写方式顺序表示一种支持随机存取的存储结构，根据起始地址加上元素的序号，可以很方便的访问任意一个元素，这就是随机存取的概念。所以线性表的顺序存储结构是一种随机存取的存储结构。

3.一个顺序表所占用的存储大小与(B)无关。
A表的长度。
B元素的存放顺序。
C元素的类型。
D元素中各字段的类型。
1
2
3
4
5

顺序表占用的空间=表长*sizeof(元素的类型)。元素的类型显然会影响到存储空间的大小。对于同一元素类型的顺序表,表越长所占存储空间就越大。

4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值。为了提高效率,应采用(D)的存取方式
A单链表。
B双向链表。
C单循环列表。
D顺序表。
1
2
3
4
5

A,B,C都只能从头节点依次顺序查找，时间复杂度为o(n)。顺序表可以按序号随机存取，时间复杂度为o(1)。

5.一个线性表最常用的操作是存取任意指定序号的元素并在最后进行插入删除操作,则利用(A)存储方式可以节省时间.
A顺序表。
B双向链表。
C带头节点的双循环链表。
第单循环链表。
1
2
3
4
5

只有顺序表可以按信号随机存取。且在最后进行插入和删除操作，不需要移动任何元素。

6.N个元素的线性表的数组表示中,时间复杂度为o(1)的操作是(1,2)
1.访问第i个节点和求第i个节点的直接前驱。
2.在最后一个节点后插入一个新的节点。
3.删除第1个节点。
4.在第i个节点后插入一个节点。
1
2
3
4
5

2.在最后位置插入新结点不需要移动元素。时间复杂度为o(1)。
3.被删节点后的节点需第依次前移,时间复杂度为o(n)。
4.需后移n-1个节点，时间复杂度为o(n)。

7.设线性表有n个元素,严格说来以下操作中(1,2)在线性表上实现要比链表上实现的效率高。
1.输出第i个元素值。
2.交换第3个元素和第4个元素的位置。
3.顺序输出这n个元素的值。
1
2
3
4

1.需依次顺序访问，每个元素时间复杂度相同。
2.顺序表上实现仅需三次交换操作。
链表上则需分别找到两个节点前驱,第4个节点链断后，再插入到第2个节点后面,效率较低。

8.把一个长度为n的顺序表中，删除i个元素时,需要向前移动几个元素(n-1).
1

需要将ai+1-an元素前移一位,共移动n-(i+1)+1=n-1个元素。

9.对于顺序表,访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为(o(1),o(n))
1

第i个位置插入一个元素需要移动n-i+1个元素,时间复杂度为o(n)

10.若长度为n的非空线性表采用顺序结构,在表的第i个位置插入一个数据元素,i的合法值应该(1<i<n+1)
1

线性表元素的序号是从1开始。而在第n+1个位置插入，相当于在表尾追加。

11.顺序表的插入算法中,当n个空间已满时,可在申请增加分配m的空间。如果申请失败,则说明系统没有(n+m)可分配的存储空间
1

顺序存储需要连续的存储空间,在申请时需要申请n+m个连续的存储空间,后将线性表原来的n元素复制到新申请的n+m个连续的存储空间和前n个单元。

3.线性表的链式表示

顺序表可以随时存取表中的任意一个元素,它的存储位置可以用一个简单直观的公式表示,但插入和删除操作需要移动大量元素.链式存储线性表时,不需要使用地址连续的存储单元,不要求逻辑上相邻的元素在物理位置上也相邻,通过"链"建立起数据元素之间的逻辑关系,因此插入和删除操作不需要移动元素,而只需要修改指针,但也会失去顺序表可随机存取的优点.

3.1单链表的定义

单链表是指通过一组任意的存储单元来存储线性表中的数据元素.为了建立数据元素之间的线性关系,对每个链表节点,除存放元素自身的信息外,还需要存放一个指向其后继的指针.单链表节点中,date为数据,存放数据元素.next为指针域,存放其后继节点的地址.
单链表中节点类型的描述如下:

typedef struct LNode{//定义单链表的结构类型
    ElemType data;//数据域
    struct LNode *next;//指针域
}LNode ,*LinkList;
1
2
3
4

利用单列表可以解决顺序表需要大量连续存储单元的缺点,但单链表附加指针域,也存在浪费存储结构的缺点.由于单链表的元素离散的分布在存储空间中,所以单链表是非随机存取的存储结构.不能直接找到表中某个特定的节点.查找某个特定的节点时,需要从表头开始遍历,依次查找.
通常用头指针来标识一个单链表.如单链表L,头指针为NULL时表示一个空表.此外为了操作上的方便,在单链表第1个节点之前附加一个节点,称为头节点.头节点的数据欲可以不设任何信息,也可以记录表长等信息.头结点的指针域指向线性表的一个元素节点.

头节点和头指针的区分:不管带不带头节点,头指针始终指向链表的第一个节点,而头结点是带头节点的链表中的第一个节点,节点内通常不存储信息.
头结点带来的两个优点

1.由于第1个数据节点的位置被存放在头节点的指针域中,所以在列表的第1个位置上的操作和代表的其他位置上的操作一致，无需进行特殊处理.
2.无论链表是否为空,头指针都指向头节点的非空指针(空表中头节点的指针域为空),因此空表和非空表的处理也就得到了统一.

3.2单链表上基本操作的实现

1.采用头插法建立单链表

该方法从一个空表开始,生成新节点,并将读取到的数据元素存放到新节点的数据域中,然后将新结点插入到当前链表的表头,即头结点之后.

头插法建立单链表的算法如下:

LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    L->next=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
6
7
8
9
10
11
12
13
14
15

采用头插法建立单链表时,读入数据的顺序与生成的列表中的元素的顺序是相反的.每个结点插入的时间复杂度为o(1),设单链表长为n,则总时间复杂度为o(n).

2.采用尾插法建立单链表

头插法建立单链表的算法有一个缺点,生成的链表中结点的次序和输入数据的顺序不一致.若需要两者次序一致,可采用尾插法.该方法将新结点插入到当前列表的表尾,为此必须增加一个表与指针r,让其始终指向当前链表的尾结点.

LinkList List_TailInsert(LinkList &L){//正向建立单链表
    int x;
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    LNode *s,*r=L;//r为表尾指针
    scanf("%d",&x);//输入结点的值
    while(x!=9999){//输入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

因为附设了一个指向表尾节点的指针,故时间复杂度和头插法的相同

3.按序号查找结点值

在单链表中，从第1个节点出发,顺指针next域逐个往下搜索,直到找到第i个节点为止,否则返回最后一个节点指针域NULL.
按序号查找节点的算法如下:

//按位查找
LNode *GetElem(LinkList L,int i){
    int j=1;//计数,初始为1
    LNode *p=L->next;//p节点刚开始的时候并不是指向第0个结点
    //而是指向了第一个数据节点
    if(i==0)
        return L;
        //如果i的值是0,那么给他返回头结点
    if(i<1){
        return NULL;
    }
    //当p指针依次往后移动,j的值也会依次递增
    while(p!=NULL && j<i){//循环找到第i个结点
        p=p->next;//p指针指向下一个节点
        j++;//j自增
    }
    return p;//当不满足while循环的时候 直接返回一个p指针当前指向的位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

另一种方法:

//按位查找
LNode * GetElem(LinkList L,int i){
    if(i<0)
        return NULL;
    int j=0;//指针p指向当前扫描到的结点
    p=L;//L指向头结点,头结点就是滴0个结点(不存数据)
    while(p!=NULL && j<i){//循环找到第i个结点
        p=p->next;//p指针指向下一个节点
        j++;//j自增
    }
    return p;//当不满足while循环的时候 直接返回一个p指针当前指向的位置
}
1
2
3
4
5
6
7
8
9
10
11
12

按序号查找操作的时间复杂度为o(n)

4.按值查找表结点

从单列表的第1个节点开始,由前往后依次比较表中各点数据域的值,若某节点数据的值等于给定值e,则返回该节点的指针;若整个单列表中没有这样的节点,则返回null
按着查找表节点的算法如下:

//按值查找,找到数据域==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.
}
1
2
3
4
5
6
7
8
9

按值查找操作的时间复杂度为o(n).

5.插入结点操作

插入节点操作将值为x的新节点插入到单列表的第i个位置上.先检查插入位置的合法性,然后找到带插入位置的前驱节点,即第i-1个结点,然后在其后插入新结点.

算法中语句2和3的顺序不能颠倒,否则先执行p->next=s后,指向其原后继的指针就不存在,再执行s->next=p->next时,相当于执行了s->next=s,显然是错误的.本算法的主要时间嗯开销在于查找第i-1个元素,时间复杂度为o(n).若在给定的结点后面插入新结点,则时间复杂度为o(1).

对某一结点进行前插操作

//前插操作:在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;
}
//时间复杂度o(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6.删除节点操作

删除结点操作时间单列表的第i个结点删除.先检查删除位置的合法性,后检查表中第i-1个节点,即被删除节点的前驱结点,再将其删除.

假设结点p找到的被删除结点的前驱节点.为实现这一操作后的逻辑的变化,仅需修改p的指针域,即将p的指针域next指向q的下一个节点.
实现删除结点的代码片段如下:

p=GetElem(L,i-1);//查找删除位置的前驱结点
q=p->next;//令q指向被删除结点
p->next=q->next;//将*q结点从链中"断开"
free(q);//释放结点的存储空间
1
2
3
4

和插入算法一样,该算法的主要时间也耗费在查找操作上,时间复杂度为o(n).

扩展:删除结点*p

q=p->next;//令q指向*p的后继结点
p->data=p->next->data;//和后继结点交换数据域
p->next=q-next;//将*q结点从链中"断开"
free(q);//释放后继结点的存储空间
1
2
3
4

7.求表长操作

求表长操作就是计算单列表中数据节点的个数,需要从第1个节点开始顺序依次访问表中的每个节点,为此需要设置一个计数器变量,没访问一个节点,计数器加1,直到访问到空姐的位置.算法的时间复杂度为o(n)
需要注意的是,因为单列表的长度是不包括同几点的,因为不带头节点和带头节点的单链表在求表长操作上会略有不同.最不带头，经典的单链表,当表为空时,要单独处理.

3.3双链表

单链表的缺陷:单链表结点中只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历.要访问某个结点的前驱结点(插入和删除操作时),只能从头开始遍历,访问后继节点的时间复杂度为o(1),访问前驱结点的时间复杂度是o(n).
为了克服单链表的上述缺点,引入双链表,双链表结点中有两个指针prior和next,分别指向其前驱结点和后继结点
双链表结点类型的描述:

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

双链表的插入和删除操作的时间复杂度仅为o(1)

1.双链表的插入操作

//在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;
}
1
2
3
4
5
6
7
8
9
10
11

2.双链表的删除操作

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

3.4循环链表

1.循环单链表

循环单链表和单链表的区别
循环单链表中最后一个结点的指针不是NULL,而改为指向头结点,从而整个链表形成一个环.
循环单链表的判空条件
不是头结点的指针是否为空,而是它是否等于头指针.
表尾便利
正是因为循环单链表是一个环,因此在任何一个位置上的插入和删除操作都是等价的,无须判断是否为表尾.
遍历便利
在单链表中只能从表头结点开始往后顺序遍历整个链表,而循环单链表可以从表中的任意一个结点开始遍历整个链表.从而使得操作效率更高.原因是:若设的是头指针,对表尾进行操作需要o(n)的时间复杂度,而若设的是尾指针r,r->next即为头指针,对于表头与表尾进行操作都只需要o(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;
 }
 //判断循环单链表是否为空
 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;
 }
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

2.循环双链表

双链表和循环双链表的区别

双链表:表头结点的prior指向NULL 表尾结点的next指向NULL
循环双链表:表头结点的prior指向表尾结点 表尾结点的next指向头结点

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;
}
//判断循环双链表是否为空
void testDLinkList(){
    //初始化循环链表
    DLinkList L;
    InitDLinkList(L);
    //...后续代码
}
//判断循环双链表是否为空
bool Empty(DLinkList L){
    if(L->next==L)
        return true;//说明这是一个空表
    else
        return false;
}
//判断结点p是否为循环双链表的表尾结点
bool isTall(DLinkList L,DNode *p){
    if(p->next==L)
        return true;
    else
        return false;
}
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
32
33
34

3.5静态链表

静态链表和单链表的比较

单链表:各个结点在内存中星罗棋布,散落天涯.
静态链表:分配一整片连续的内存空间,各个结点集中安置
0号结点充当"头结点"
游标充当指针
下一个节点的数组下标(游标)
游标为-1表示已经到达表尾
每个数据元素4B,每个游标4B(每个结点共8B),设起始地址为 addr
e1的存放地址为addr+8*2

静态链表的插入,删除操作与动态链表的相同,只需要修改指针,而不需要移动元素.总体来说,静态链表没有单链表使用起来方便,但在一些不支持指针的高级语言中(Basic),静态链表是一种非常巧妙的设计方法.
用代码定义一个静态链表

#define MaxSize 10//静态链表的最大长度
struct Node{//静态链表结构类型的定义
    ElemType data;//存储数据元素
    int next;//下一个元素的数组下标
}
void testSLinkList(){
    struct Node a[MaxSize];//数组a作为静态链表
}

#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];
//可用SLinkList定义"一个长度为MaxSize"的Node型数组长度 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

对猜想的验证

#include <iostream> 
#define MaxSize 10//静态链表的最大长度
using namespace std; 
struct Node{//静态链表结构类型的定义
	int data;//存储数据元素
	int next; //下一个数据元素的数组下标
};
typedef struct{
	int data;
	int next; 
}SLinkList[MaxSize];
int main(){
	struct Node x;
	printf("sizeX=%d\n",sizeof(x));
	
	struct Node a[MaxSize];
	printf("sizeA=%d\n",sizeof(a));
	
	SLinkList b;
	printf("sizeB=%d\n",sizeof(b));
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.6顺序表和链表的比较

1.存取(读写)方式

顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素.

2.逻辑结构与物理结构

采用顺序存储时,逻辑上相邻的元素,对应的物理存储位置也相邻.而采用链式存储时,逻辑上相邻的元素,物理存储位置则不一定相邻,对应的逻辑关系是通过指针链接来表示的.

3.查找,插入和删除操作

1.对于按值查找,顺序表无序时,两者的时间复杂度均为o(n)
顺序表有序时,可采用折半查找,此时的时间复杂度是o(log2n)
2.对于按序号查找,顺序表支持随机访问,时间复杂度仅为o(1),而链表的平均时间复杂度是o(n).
顺序表的插入,删除操作,平均需要移动半个表长的元素,链表的插入,删除操作,只需修改相关节点的指针域即可.优于链表的每个节点都带有指针域,故而存储密度不够大.

4.空间分配

顺序存储在静态存储分配情形下,一旦存储空间装满就不能扩充,若再加入新元素,则会出现内存溢出,因此需要预先分配足够大的存储空间.预先分配过大,可能会导致顺序表后部大量闲置;
预先分配过小,又会造成溢出.动态存储分配虽然存储空间可以扩充,但需要移动大量的元素,导致操作效率降低,而且若内存中没有大量连续的存储空间,则会导致分配失败.链式存储的结点空间只在需要时申请分配,只要内存有空间就可以分配,操作灵活,高效.

在实际中应该怎么选取存储结构呢?
1.基于存储的考虑

难以估计线性表的长度或者存储规模时,不宜采用顺序表;
链表不用事先估计存储的规模,但链表的存储密度较低,显然链式存储结构的存储密度是小于1的.

2.基于运算的考虑

在顺序表中按序号访问ai的时间复杂度是o(1)
链表中按序号访问ai的时间复杂度是o(n)
因此若经常做的运算是按序号访问数据元素,顺序表优于链表

在顺序表中进行插入,删除时,平均移动表中的一半元素,当表中数据量比较大或者表比较长的时候,这一点是不可忽略的;
在链表中进行插入,删除时,虽然也要找插入位置,但操作只要是比较操作,从这个角度来说,链表是优于顺序表结构的.

3.基于环境的考虑

顺序表容易实现,在任何的高级语言中都有数组类型;
链表的操作是基于指针的,相对来说,顺序表的实现较为简单

通常较稳定的线性表选择顺序存储,而频繁的进行插入和删除操作的线性表(动态性较强)宜选择链式存储