《数据结构和算法》chapter3 线性表

线性表的定义

线性表（list）：零个或多个数据元素的有限序列。

如果用数学语言来进行定义。可如下：

我们定义线性表为 $（a_1,…,a_i-1,a_i,ai+1…,a_n）$，其中元素$a_i-1$被称为 $a_{i-1}$ 的直接前驱元素，而 $a_{i+1}$ 则是 $a_i$ 的直接后继元素。

对于 $i = 1, 2, \ldots, n-1$，每个元素 $a_i$仅有一个直接后继；而对于 $i = 2, 3, \ldots, n$，每个元素 $a_i$ 仅有一个直接前驱。

线性表的长度 $n$（其中 $n \geq 0$ ）表示表中元素的总数。第一个数据元素为 $a_1$，最后一个数据元素为 $a_n$，而 $a_i$ 表示第 $i$个数据元素。在这种情况下，$i$ 称为数据元素 $a_i$ 在线性表中的位序。

线性表的抽象数据类型

​线性表的抽象数据类型定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
ADT 线性表（List）
Data
	线性表的数据对象集合为{a.1,a.2,......,a.n}，每个元素的类型均为DataType。其中，除第一个元素a.1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素a.n外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
	InitList(*L)：初始化操作，建立一个空的线性表L。
	ListEmpty(L)：若线性表为空，返回true，否则返回false。
	ClearList(*L)：将线性表清空。
	GetElem(L,i,*e)：将线性表L中的第i个位置元素值返回给e。
	LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
	ListInsert(*L,i,e)：在线性表L中的第i个位置插入新元素e。
	Listlength(L)：返回线性表L的元素个数。
endADT

​对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

​

[!TIP]

当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式。

如果需要被改动，则需要传递指向这个参数的指针。

如果不用被改动，可以直接传递这个参数。

​

线性表的顺序存储结构

顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储方式

既然线性表的每个数据元素的类型都相同，所以可以用C语言的一维数组来实现顺序存储结构。 

1
2
3
4
5
6
7
#define MAXSIZE 20			//存储空间初始分配量
#typedef int ElemType		//ElemType类型根据您实际情况而定，这里为int
#typedef struct				
{
	ElemType data[MAXSIZE];//数组，存储数据元素
	int length;				//线性表当前长度
}

顺序存储结构需要三个属性：

  • 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

  • 线性表的最大存储容量：数组长度MAXSIZE。

  • 线性表的当前长度：length。

数据长度与线性表长度的区别

​数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

地址计算方法

​存储器中的每个存储单元都有自己的编号，这个编号称为地址。

比如我们在图书馆占位，当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的。

如果我的座位编号为3，后面的10个人座位编号为几呢？当然是4，5，6等等。

由于每个数据元素，不管它是整型、实型、还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

$$
LOC(a_i+1)=LOC(a_i)+c
$$

所以对于第i个数据元素$a_i$的存储位置可以由$a_1$推算得出：

$$
LOC(a_i)=LOC(a_1)+(i-1)*c
$$

通过这个公式，你可以随时算出线性表中任意位置的地址。

顺序存储结构的插入与删除

获得元素操作

​实现GetElem操作，即将线性表L中的第i个元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define	OK	1
#define ERROR 0
//Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int Status;

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值，注意i是指位置，第1位置的数组是从0开始
Status GetElem(SqList L,int i,ElemType *e){
    if(L.length==0 || i<1 ||i>L.length){
        return ERROR;
    }
    *e=L.data[i-1]
    return OK;
}

插入操作

​实现在第i个位置插入新元素e。

插入算法的思路：

  1. 如果插入位置不合理，抛出异常；

  2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

  3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。

  4. 将要插入元素填入位置i处；

  5. 表长加1。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//初始条件：顺序线性表L中已存在，1<=i<=Listlength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(SqList *L,int i,ElemType e){
    int k;
    if(L->length==MAXSIZE){
        return ERROR;
    }
    if(i<1 || i>L->length+1){
        return ERROR;
    }
    if(i<=L->length){
        for(k=L->length-1;k>=i-1;k--){
            L->data[k+1]=L->data[k];
        }
    }
    L->data[i-1]=e;
    L->length++;
    return OK;
}

删除操作

删除算法的思路：

  1. 如果删除位置不合理，抛出异常。

  2. 取出删除元素；

  3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。

  4. 表长减1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status ListDelete(SqList *L,int i,ElemType *e){
	int k;
	if(L->length==0)
		return ERROR;
	if(i<1 || i>L->length)
		return ERROR;
	*e=L->data[i-1];
	if(i<L->length){
		for(k=i;k<L->length;k++){
			L->data[k-1]=L->data[k];
		}
	}
	L->length--;
	return OK;
}

线性表顺序存储结构的优缺点

优点 缺点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间 插入和删除操作需要移动大量元素
可以快速地存取表中任一位置的元素 当线性表长度变化较大时，难以确定存储空间的容量
造成存储空间的“碎片”

线性表的链式存储结构

顺序存储结构不足的解决方法

所有的元素都不考虑相邻位置了，哪有空位就到哪里，而只是让每个元素知道它下一个元素的位置在那里，这样，我们可以在第一个元素时，就知道第二个元素的位置（内存地址），而找到它。

线性表链式存储结构定义

链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储位置。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素a.i的存储映像，称为结点（Node）。

n个结点（a.i的存储映像）链结成一个链表，即为线性表（$a_1,a_2,…,a_n$）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所有叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。

线性链表的最后一个结点为空。

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个节点前附设一个结点，称为头结点。

头结点的数据源可以不存储任何信息。

头结点的指针域指向第一个结点的指针。

头指针与头节点的异同

头指针 头结点
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
头指针具有标志作用，所有常用头指针冠以链表的名字 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
无论链表是否为空，头指针均不为空。头指针是链表的必要元素 头结点不一定是链表必需要素

线性表链式存储结构代码描述

​若线性表为空表，则头结点的指针域为空。

单链表中，我们在C语言中可用结构指针来描述。

1
2
3
4
5
6
//线性表的单链表存储结构
typedef struct Node{
	ElemType data;
	struct Node *next;
}Node;
typedef struct Node *LinkList;//定义LinkList

从这个结构定义中，我们也就知道，结点由存储数据元素的数据域和存储后继结点的指针域组成。

单链表的读取

获得链表第i个数据的算法思路：

  1. 声明一个指针p指向链表第一个结点，初始化j从1开始；

  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；

  3. 若到链表末尾p为空，则说明第i个结点不存在。

  4. 否则查找成功，返回结点p的数据

实现代码算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//初始条件：链式线性表L已存在，1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值
Status GetElem(LinkList L,int i,ElemType *e){
	int j;
	LinkList p;		//声明一结点
	p=L->next;		//让p指向链表L的第一个结点
	j=1;			//j为计数器
	while(p && j<i){
		p=p->next;	//让p指向下一个结点
        ++j;
	}
    if(!p || j>i)
        return ERROR;	//第i个元素不存在
    *e=p->data;
    return OK;
}

单链表的插入与删除

单链表的插入

单链表第i个数据插入结点的算法思路：

  1. 明一指针指向链表头结点，初始化j从i开始

  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累计1；

  3. 若到链表末尾p为空，则说明第个结点不存在；

  4. 否则查找成功，在系统中生成一个空结点s；

  5. 将数据元素e赋值给s->data；

  6. 单链表的插入标准语句s->next=p->next；p->next=s；

  7. 返回成功

实现代码算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//初始条件：链式线性表L已存在，i<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(LinkList *L,int i,ElemType e){
	int j;
	LinkeList p,s;
	p=*L;
	j=1;
	while(p && j<i){		//寻找第i个结点
		p=p-next;
		++j;
	}
	if(!p || j>i){
		return ERROR;		//第i个元素不存在
	}
	s=(LinkList)malloc(sizeof(Node));	//生成新结点（C语言标准函数）
	s->data=e;
	s-next=p->next;			//将p的后继节点赋值给s的后继
	p->next=s;				//将s赋值给p的后继
	return OK;
}

单链表的删除

单链表第i个数据删除结点的算法思路：

  1. 声明一指针p指向链表头结点，初始化j从1开始；

  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；

  3. 若到链表末尾p为空，则说明第i个结点不存在；

  4. 否则查找成功，将欲删除的结点p->next赋值给q；

  5. 单链表的删除标准语句p->next=q-next；

  6. 将q结点中的数据赋值给e，作为返回；

  7. 释放q结点；

  8. 返回成功。

实现代码算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//初始条件：链式线性表已存在，1<=i<=Listlengeh(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete(LinkList *L,int i,ElemType *e){
	int j;
	LinkList p,q;
	p=*L;
	j=1;
	while(p-next && j<i){	//遍历寻找第i个元素
		p=p->next;
		++j;
	}
	if(!(p->next)|| j>i){
		return ERROR;	//第i个元素不存在
	}
	q=p->next;
	p->next=q->next;	//将q的后继赋值给p的后继
	*e=q->data;			//将q结点中的数据给e
	free(q);			//让系统回收此结点，释放内存
	return OK;
}

对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。

单链表的整表创建

单链表整表创建的算法思路：

  1. 声明一指针p和计数器变量i。

  2. 初始化一空链表L。

  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表。

  4. 循环：

1.生成一新节点赋值给p；

2.随机生成一数字赋值给p的数据域p->data；

3.将p插入到头结点与前一新结点之间。

实现代码算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）
void CreateListHead(LinkList *L,int n){
	LinkList p;
	int i;
	srand(time(0));						//初始化随机数种子
	*L=(LinkList)malloc(sizeof(Node));
	(*L)->next=NULL;					//先建立一个带头结点的单链表
	for(i=0;i<n;i++){
		p=(LinkList)malloc(sizeof(Node));//生成新结点
		p->data=rand()%100+1;			//随机生成100以内的数字
		p->next=(*L)->next;
		(*L)->next=p;					//插入到表头
	}
}

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。我也可以把这种算法简称为头插法。

我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。

实现代码算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//随机产生n个元素的值，建立带表头结点的单链表线性表L（尾插法）
void CreateListTail(LinkList *L,int n){
    LinkList p,r;
    int i;
    srand(time(0));
    *L=(LinkList)malloc(sizeof(Node));
    r=*L;
    for(i=0;i<n;i++){
        p=(Node *)malloc(sizeof(Node));
        p->data=rand()%100+1;
        r->next=p;
        r=p
    }
    r->next=NULL;
}

注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

单链表的整表删除

当我们不打算使用这个单链表时，我们需要把他销毁，其实也就是在内存中将它释放掉，以便于留出空间给其它程序或软件使用。

单链表整表删除的算法思路如下：

  1. 声明一指针p和q。

  2. 将第一个结点赋值给p。

  3. 循环：

(1)将下一结点赋值给q；

(2)释放p；

(3)将q赋值给p。

实现代码算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
//初始条件：链式线性表L已存在。操作结果：将L重置为空表
Status ClearList(LinkList *L){
	LinkList p,q;
	p=(*L)->next;
	while(p){
		q=p->next;		//p指向第一个结点
		free(p);		//没到表尾
		p=q;
	}
	(*L)->next=NULL;	//头结点指针域为空
	return OK;
}

单链表结构与顺序存储结构的优缺点

对比单链表结构和顺序存储结构

存储分配方式 时间性能 空间性能
顺序

通过上面的对比，我们可以得出一些经验性的结论：

  • 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
  • 当线性表中的元素个数变化比较大或者根本不知道有多大时，最后用单链表结构。

静态链表

由于有些编程语言没有指针，所以理论上无法实现链表结构。

但是智慧的人们想出了用数组来代替指针描述单链表。

首先让我们数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和cur。数据域data用来存放数据元素，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫作游标。

我们把这种用数组描述的链表叫作静态链表，这种描述方法还有起名叫作游标实现法。

我们俩方便插入数据，我们通常会把数据建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

1
2
3
4
5
6
7
8
#define MAXSIZE 1000 //存储空间初始分配量

//线性表的静态链表存储结构

typedef struct{
	ElemType data;
	int cur;             //游标(Cursor)，为0的表示无指向
}Component,StaticLinkList[MAXSIZE];

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。

为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。

1
2
3
4
5
6
p=rearA->next;                  //保存A表的头结点
rearA->next=rearB->next->next;  //将本是指向B表的第一个结点
                                //赋值给reaA-next
q=rearB->next;                  
rearB->next=p;                  //将原A表的头结点赋值给rearB->next
free(q);                        //释放q

双向链表

双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

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