【笔记】数据结构_线性表
本帖最后由 sphao 于 2017-10-18 16:02 编辑**【概要】**
+ （一）线性表的定义和基本操作
+ （二）线性表的实现
+ 顺序存储
+ 链式存储
+ 线性表应用
---
# 线性表定义和基本操作
## 线性表定义
线性表是具有相同数据类型的n（n>0）个元素的有限序列。
n为表长，n = 0时为空表。
除第一个元素外，每个元素**有且仅有一个**直接前驱；
除最后一个元素外，每个元素**有且仅有一个**直接后继。
## 线性表的基本操作
初始化、求表长、查找、插入、删除、输出...
---
# 线性表的顺序表示
## 顺序表的定义
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻。
线性表顺序存储类型描述（静态分配）：
```
#define MaxSize 50; //定义线性表的最大长度
typedef struct
{
Elemtype data; //顺序表的元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
```
动态分配：
```
#define InitSize 100 //表长度的初始定义
typedef struct{
Elemtype *data; //指示动态分配数组的指针
int MaxSize, length; //数组的最大容量和当前个数
}SeqList; //动态分配数组顺序表的类型定义
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize); //初始动态分配语句
```
---
**顺序表的优缺点**：
优点：
+ 随机访问
+ 存储密度高，每个结点之存储数据元素
缺点：
+ 插入删除操作需要移动大量元素。
---
## 顺序表上基本操作的实现
1. 插入操作
```
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 = L.data;
L.data = e; //在位置i处放入e
L.length++; //线性表长度加1
return true;
}
```
插入算法的平均移动次数 = n / 2。
插入算法的时间复杂度 = O(n)。
---
2. 删除操作
```
bool ListDelete(SqList &L, int i, int &e)
{
if(i < 1 || i> L.length) //判断i的范围是否有效
retutn false;
e = L.date; //将被删除的元素赋值给e
for(int j = i; j < L.length; j++) //将第i个位置之后的元素前移
L.data = L.data;
L.length--; //线性表长度减1
return true;
}
```
删除算法的平均移动次数 =（n-1）/ 2。
删除算法的平均时间复杂度 = O(n)。
---
3. 按值查找（顺序查找）
```
int LocateElem(SqList L, ElemType e)
{
int i;
for(i = 0; i < L.length; i++)
if(L.data == e)
return i + 1; //下标为i的元素值等于e，返回其位序i + 1
return 0; //退出循环，说明查找失败
}
```
查找操作的平均比较次数 = （n+1）/ 2。
查找操作的时间复杂度 = O(n)。
---
# 线性表的链式表示
## 单链表的定义
线性表的链式存储又称单链表。通过指针来建立起数据元素之间的线性关系。
单链表中结点类型的描述：
```
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
```
---
**单链表的优缺点**：
优点：
+ 不需要大量的连续存储空间
+ 插入、删除操作不需要移动大量结点
缺点：
+ 单链表附加的指针域存在浪费存储空间的缺点
+ 查找操作为顺序查找，不能直接找到表中某个特定的结点
---
通常用头指针来标识一个链表，为了操作方便，在单链表的第一个结点之前附加一个头结点。
**引入头结点的优点**：
+ 链表第一个位置上的操作和其他位置上的操作一致，无须特殊处理
+ 无论链表是否为空，其头指针为指向头结点的非空指针，空表和非空表的处理也统一
---
## 单链表上基本操作的实现
1. 采用头插法建立单链表
头插法建立链表的算法：
```
LinkList CreatList1(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);
} //while结束
return L;
}
```
头插法建立单链表，读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为O(1)，若单链表长为n，则总的时间复杂度为O(n)。
---
2. 尾插法建立单链表
头插法虽然简单，但生成链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。若采用尾插法，则必须增加一个尾指针r，使其始终指向当前链表的尾结点。
尾插法建立单链表的算法：
```
LinkList CreatList2(LinkList &L)
{
int x;
L = (LinlList)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;
}
```
因为设置了一个尾指针，故时间复杂度与头插法相同。
---
3. 按序号查找结点值
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否者返回最后一个结点指针域NULL。
按序号查找结点值的算法：
```
LNode *GetElem(LinkList L, int i)
{
int j = 1; //计数，初始为1
LNode *p = L->next; //头结点指针赋给p
if(i == 0)
return L; //若i = 0，则返回头结点
if(i < 1)
return NULL; //若i无效，则返回NULL
while(p && j < i) //从第1个结点开始找，查找第i个结点
{
p = p->next;
j++;
}
return p; //返回第i个结点的指针；若i大于表长，p = NULL
}
```
其时间复杂度为O(n)。
---
4. 按值查找表结点
从单链表第一个结点开始，由前往后依次比较表中个结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针 ；若整个链表中没有这样的结点，返回NULL。
按值查找结点的算法：
```
LNode *LocateElem(LinkList L, ElemType e)
{
LNode *p = L->next;
while(p != NULL && p->data != e) //从第一个结点开始查找data域为e的结点
p = p->next;
return p; //找到后返回该点指针，否则返回NULL
}
```
其时间复杂度为O(n)。
---
5. 插入结点操作
插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点（i-1），在其后插入新结点。
实现插入结点的代码片段:
```
p = GetElem(L, i - 1);
s->next = p->next; //图中1
p->next = s; //图中2
```
算法中，行2、3的语句不能颠倒，先连后断。
上述算法利用GetElem()函数将前插操作转换为后插操作，复杂度为O(n)。
我们可以采用另一种方式将其转换为后插操作来实现，设待插入结点为`*s`，将`*s`插入到`*p`的前面。我们仍然将`*s`插入到`*p`后面，然后将p->data与s->data交换即可，这样既满足了逻辑关系，又能使得时间复杂度为O(1)。
代码片段：
```
s->next = p->next; //先连
p->next = s; //后断
temp = p->data; //交换数据域部分
p->data = s->data;
s->data = temp;
```
---
6. 删除结点操作
删除操作是将单链表第i个结点删除。先检测删除位置的合法性，然后查找表中第i-1个结点，再将其删除。
实现删除结点的代码片段：
```
p = GetElem(L, i - 1); //查找删除位置的前驱结点
q = p->next; //令q指向被删除结点
p-next = q->next; //将*q结点从链中“断开”
free(q); //释放结点的存储空间
```
与插入算法一样，其主要时间耗费在查找操作上，时间复杂度为O(n)。
若要实现删除某一给定结点*p，通常是从链表的表头找到其前驱结点，然后再执行删除操作，算法的时间复杂度为O(n)。
我们可以利用删除*p的后继结点操作来实现，实质就是将其后继节点的值赋予自身，然后删除后继节点，也能使时间复杂度为O(1)。
```
q = p->next; //令q指向*p的后继结点
p->data = q->next->data; //和后继结点交换数据域
p->next = q->next; //断开
free(q); //释放后继结点的存储空间
```
---
7. 求表长操作
求表长操作就是计算单链表中的数据结点（不包含头结点）的个数，需要从第一个结点开始顺序依次访问表中的每一个节点，为此需要设置一个计数器变量，每访问一个结点，计数器加1，直到访问到空结点为止。算法的时间复杂度为O(n)。
因为单链表的长度不包括头结点，因此，不带头结点和带头结点的单链表在求表长操作上有所不同。对不带头结点的单链表，当表为空时，要单独处理。
---
## 双链表
双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。
双链表中结点类型：
```
typedef struct DNode //定义双链表结点类型
{
ElemType data; //数据域
struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinklist;
```
双链表仅在结点中增加了一个指向其前驱结点的指针prior，因此，在双链表中执行按值查找和按位查找的操作和单链表相同。但在插入和删除操作上，因为“链”变化时也需要对prior指针进行修改，和单链表不同。其关键在于保证**在修改过程中不断链**。此外，由于双链表可以很方便的找到其前驱结点，因此，插入，删除结点算法的时间复杂度仅为O(1)。
---
1. 双链表的插入操作
在双链表p所指的结点之后插入结点*s，代码片段及指针变化图如下：
```
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
```
上述代码顺序不是唯一的，但也不是任意的，1、2两步必须在4之前，否则*p的后继结点的指针就丢掉了，导致插入失败。
---
2. 双链表的删除操作
删除操作的代码片段：
```
p->next = q->next;
q->next->prior = p;
free(q);
```
---
建立双链表的操作中，也可以采用如同单链表的头插法和尾插法，但是在操作上需要注意指针的变化和单链表有所不同。
## 循环链表
1. 循环单链表
循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。
在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此循环链表的判空条件不是头结点指针是否为空，而是它是否等于头指针。
循环单链表的插入、删除算法与单链表的几乎一样，所不同的是如果操作是在表尾进行，则执行的操作不相同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个 “环”，因此，在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。
在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任一结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的，此时可**对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高**。
---
2. 循环双链表
由循环单链表的定义不难推出循环双链表，不同的是在循环双链表中，头结点的prior 指针还要指向表尾结点。
在循环双链表L中，某结点*p为尾结点时，p->next=L；当循环双链表为空表时，其头结点的prior域和next域都等于L。
##静态链表
静态链表是借助数组（结构数组）来描述线性表的链式存储结构，结点也有数据域data和指针域 next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称为游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。
静态链表结构类型描述：
```
#define MaxSize 50 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList;
```
静态链表以next==-1作为其结束的标志。静态链表的插入、删除操作与动态链表相同，只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，但是在一些不支持指针的高级语言（如Basic）中，这又是一种非常巧妙的设计方法。
## 顺序表和链表的比较
1. 存取方式
顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
2. 逻辑结构和物理结构
釆用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而釆用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻，其对应的逻辑关系是通过指针来链接的。这里请注意**区别存取方式和存储方式**。
3. 查找、插入和删除操作
对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为O(n)；而当顺序表有序时，可釆用二分查找，此时时间复杂度为O(log2n)。
对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。
顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作时，只需要修改相关结点的指针域即可。由于链表每个结点带有指针域，因而在存储空间上比顺序存储要付出较大的代价，存储密度不够大。
4. 空间分配
顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，如果再加入新元素将出现内存溢出，需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间将导致分配失败。链式存储的结点空间只在需要的时候申请分配，只要内存有空间就可以分配，操作灵活、高效。
---
**在实际中应该怎样选取存储结构呢？**
1. 基于存储的考虑
对线性表的长度或存储规模难以估计时，不宜釆用顺序表;链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的。
2. 基于运算的考虑
在顺序表中按序号访问 ai 的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。
在顺序表中做插入、删除操作时，平均移动表中一半的元素当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中做插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。
3. 基于环境的考虑
顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素。
总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁做插入、删除操作的线性表（即动态性较强）宜选择链式存储。 谢谢分享，学习到新的知识了 谢谢分享，学习了 谢谢分享 问下左侧目录是怎么做到的 cqr2287 发表于 2017-10-19 19:09
问下左侧目录是怎么做到的
用markdown发布就自动生成了 谢谢分享请问楼主是自己学的还是看教程的可以分享下教程吗 hdh9583 发表于 2017-10-19 21:34
谢谢分享请问楼主是自己学的还是看教程的可以分享下教程吗
看书整理的 考研的教材 sphao 发表于 2017-10-19 21:40
看书整理的 考研的教材
王道的吗？因为我也准备考研所以问一下 hdh9583 发表于 2017-10-19 22:33
王道的吗？因为我也准备考研所以问一下
的确是王道，配合课本看。
页:
[1]
2