逻辑结构--线性表的定义
线性表是具有数据类型的n(n
0)个数据元素的有限序列。n为表长，n=0时称为空表。
- 相同数据类型：每个元素所占空间一样大；
- 有限：长度必须有限，比如所有整数就不是个线性表
- 序列：必须有次序
- 是线性表的”第i个“元素线性表中的位序；
- 是表头元素，是表尾元素。注意线性表的位序是从1开始，数组下标是从0开始；
- 除表头外，每个元素都有直接前驱；除表尾外，每个元素都有直接后继；
运算--线性表的基本操作
基本操作是指最核心、最基本的操作。其他复杂操作都可以通过调用基本操作来实现。
所有基本操作都可以归结为创建、销毁、增删改查
- 创建和销毁：
- InitList(&L):初始化表。构造一个空的线性表L，分配内存空间；
- DestoryList(&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；
存储结构
顺序表
顺序表的定义
用顺序存储方式实现线性表的顺序存储。把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系用存储单元的邻接关系来体现。
顺序表的特点：
- 随机访问：因为在内存中连续存储，所以在时间内即可找到第i个元素,代码实现data[i-1];
- 存储密度高，每个节点只需要存储数据元素本身
- 拓展容量不方便，即使是动态存储，拓展长度的时间复杂度也很高，因为需要复制原来的元素；
- 插入、删除操作不方便，需要移动大量的元素；
静态分配
静态分配就是用数组的方式来实现顺序表。
1
2
3
4
5
6
| #define MaxSize 10
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void InitList(SqList& L) {
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0;
}
L.length = 0;
}
int main() {
SqList L;
InitList(L);
}
|
顺序表的局限性：顺序表的表长在刚开始确定后就无法更改。
动态分配
1
2
3
4
5
6
7
8
9
10
11
12
13
| #define InitSize 10
typedef struct {
ElemType *data;
int MaxSize;
int length;
}SeqList;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
L.data=new ElemType[InitSize];
|
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
| #define InitSize 10
typedef struct {
int *data;
int MaxSize;
int length;
}SeqList;
void InitList(SeqList& L) {
L.data = (int*)malloc(InitSize * sizeof(int));
L.length = 0;
L.MaxSize = InitSize;
}
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;
free(p);
}
int main() {
SeqList L;
InitList(L);
IncreaseSize(L, 5);
}
|
动态存储不是链表，物理结构没有发生变化，都是连续的地址空间。只是可以运行时动态决定分配的内存地址空间。
基本操作
插入
实现在顺序表L中的()位置插入元素。要注意代表线性表的位序，是从1开始的，而内部使用的数组下标是从0开始的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool ListInsert(SqList& L, int i, Elemtype e)
{
if (i<1 || i>L.length + 1)
return false;
if (L.length >= MaxSize)
return false;
for (int j = L.length; j >= i; j--)
{
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return true;
}
|
时间复杂度计算最深层循环，即元素后移时的次数
- 最好时间复杂度：表尾插入，i=n+1（length+1），不需要后移，时间复杂度;
- 最坏时间复杂度：表头插入，i=1,原有的n个元素都需要向后移动，时间复杂度；
- 平均时间复杂度：新元素插入到任何一个位置的概率都相同，即i=1,2,3,……,length+1的概率都是p=1/(n+1)，每个相加，等差数列求和，得n/2,所以时间复杂度;
删除
实现删除顺序表L中第（）个位置的元素，用引用变量e返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool ListDelete(Sqlist &L, int i, ElemType& e)
{
if(i < 1 || i > L.length)
return false;
e = L.data[i-1];
for(int j = i; j < L.length; j++)
{
L.data[j-1] = L.data[j];
}
L.length--;
return true;
}
|
时间复杂度的耗时和插入一样，在元素移动上：
- 最好时间复杂度：表尾删除，i=n，无需移动元素，时间复杂度为；
- 最坏时间复杂度：表头删除，i=1，需要移动除了表头外的所有元素，时间复杂为；
- 平均时间复杂度:；
按位查找
获取表L中第i个位置的元素的值。
如果顺序表是静态分配的，那么可以直接用数组下标来取。要注意数组下标和位序的区别。
1
2
3
4
5
6
7
8
9
10
11
| #define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int length;
}Sqlist;
ElemType GetElem(Sqlite L, int i)
{
return L.data[i-1];
}
|
动态分配时，依旧可以用数组下标来取值。
1
2
3
4
5
6
7
8
9
10
11
12
| #define InitSize 10
typedef struct{
ElemType *data;
int MaxSize;
int length;
}Seqlist;
ElemType GetElem(Seqlist L, int i)
{
return L.data[i-1];
}
|
按位查找的时间复杂度为。这就是顺序表随机存取的特性。顺序表在内存中都是连续存放的，可以根据起始地址和数据元素大小立即找到第个元素。
按值查找
在顺序表L中找到第一个元素等于的元素，并返回其位序。
1
2
3
4
5
6
7
8
9
| int LocateElem(Sqlite L, ElemType e)
{
int i;
for(i = 0; i < L.length; i++)
if(L.data[i] == e)
return i+1;
return 0;
}
|
注意：上面那个是伪代码，==只能用于基本数据类型，如果是类似于结构体那样的，C语言要自己挨个比较成员变量，C++需要重载==运算符。
时间复杂度：
- 最好时间复杂度：查找的元素在表头，只需要比较一次，时间复杂度；
- 最坏时间复杂度：查找的元素在表尾，循环比较n次，时间复杂度；
- 平均时间复杂度：;
链式存储
顺序表的优点是可以随机存取，存储密度高，但顺序表的缺点是要求大片的连续存储空间，改变容量很不方便，且插入和删除操作需要移动大量的元素。
链式存储的线性表，每个需要使用连续地址单元，通过链建立逻辑关系。每个节点除了存放数据元素之外，还存放指向下一个节点的指针。优点是不要求大片连续地址空间，改变容量方便，但缺点是不可随机存取，而且要耗费一定空间存放指针。
单链表
单链表定义
线性表的链式存储又称为单链表。
1
2
3
4
5
6
7
8
9
10
11
|
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LNode* L;
LinkLisk L;
|
单链表有两种实现方式，一种是带头节点，一种是不带头节点：
不带头节点的单链表初始化方式如下：
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(LinkList L)
{
if(L->next == NULL)
return true;
else
return false;
}
|
头指针和头结点的区别：
- 头指针始终指向链表中的第一个结点;
- 如果不带头结点，那头指针指向的就是存放数据的结点；如果带头结点，那么头指针指向的就是头结点，是不存放数据的；
之所以引入头结点，是为了写代码方便：
- 有头节点后，所有位置的操作算法统一，不再需要判断是否在第一个元素之前插入或删除第一个元素
- 不论链表是否为空，其头指针是指向头节点的非空指针，链表的头指针不变，因此空表和非空表的处理也就统一了
单链表基本操作
按位序插入
ListInsert(&L, i, e):在表L中的第i个位置插入指定元素e。
思路为找到待插入位置的前驱结点（第i-1），然后在其后面插入新结点。
带头结点的链表，不需要对第一个结点做特殊处理：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
bool ListInsert(LinkList &L, int i, ElemType e)
{
if(i < 1) return false;
LNode *p;
int j = 0;
p = L;
while(p != NULL && j < i-1){
p = p->next;
j++;
}
if(p == NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
|
这个算法的时间开销在于找到前驱结点的耗时，平均时间复杂度为
如果链表没有头结点，那么需要单独处理插入第一个元素时候的情况，需要把头指针的位置变更。后续的结点操作都一样
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
|
bool ListInsert(LinkList &L, int i, ElemType e)
{
if(i < 1) return false;
if(i == 1)
{
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s;
return true;
}
LNode *p;
int j = 1;
p = L;
while(p != NULL && j < i-1){
p = p->next;
j++;
}
if(p == NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
|
按照结点插入
链表的插入操作分为前插操作和后插操作，即给定结点p，在其之后或者之前插入一个结点。单链表的插入算法中，一般都选择后插操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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;
}
|
正常来说，链表的每个结点都只能找到其后面的元素，那如何实现在某结点的前面插入元素呢？其实不需要考虑的那么复杂，链表插入后位置就固定了，我们依旧可以在p结点之后插入一个新结点s，然后交换p和s的数据域，达到偷天换日的效果：
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
|
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->data = p->data;
p->data = e;
return true;
}
bool InsertPriorNode(LNode *p, LNode *s)
{
if(p == NULL || s == NULL)
return false;
s->next = p->next;
p->next = s;
ElemType temp = p->data;
p->data = s->data;
s->data=temp;
return true;
}
|
按位序删除
只分析带头结点的链表的删除操作。删除第i个位置的结点p，只需要找到第i-1个结点，让其指向第i+1的位置即可：
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
| bool ListDelete(LinkList &l, int i, ElemType &e)
{
if(i < 1)
return false;
LNode* p;
int j = 0;
p = L;
while(p != NULL && j < i-1){
p = p->next;
j++;
}
if(p == NULL)
return false;
if(p->next == NULL)
return false;
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
|
时间消耗主要在寻找前驱结点上，平均时间复杂度是。
删除指定结点
删除指定的结点p，可以参考前插操作的偷天换日方法。赋值p的后继结点给自身，这样p和p的后继，同时指向了p的后继的后继，然后删除p的后继结点：
1
2
3
4
5
6
7
8
9
10
11
12
|
bool DeleteNode(LNode *p)
{
if(p == NULL)
return false;
LNode* q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q)；
return true;
}
|
注意上面的代码是有缺陷的，不能删除最后的结点。因为最后的结点，他的后继是空，没有数据域了，会崩溃。如果要删除最后一个结点，那只能函数传递链表头指针，挨个遍历寻找p的前驱结点，时间复杂度是。这也体现出了单链表的局限性：无法实现逆向检索。
按位查找
只考虑带头结点的情况：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
LNode* GetElem(LinkList L, int i)
{
if(i < 0)
return NULL;
LNode *p;
int j = 0;
p = L;
while(p != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
|
平均时间复杂度
按值查找
只考虑带头结点的情况
1
2
3
4
5
6
7
8
9
10
|
LNode* LocateElem(LinkList L, ElemType e)
{
LNode* p = L->Next;
while(p != NULL && p->data != e){
p = p->next;
}
return p;
}
|
求表长
1
2
3
4
5
6
7
8
9
10
11
| int Length(LinkList L)
{
int len = 0;
LNode* p = L;
while(p->next != NULL)
{
p = p->next;
len++;
}
return len;
}
|
上面是带头结点的单链表求表长。如果不带头结点，需要单独处理一下空表的情况。
单链表的建立
给定指定数量的数据元素，要把他们存到一个单链表里面，操作步骤：
- 初始化一个单链表
- 每次取一个数据元素，插入到链表中
根据插入到链表表头还是表尾，可以分为头插法和尾插法。
尾插法，即新结点插入到链表的表尾，插入顺序和结点次序相同。插入不要用前面的按位插入，每次插入都要进行一次遍历，整体的时间复杂度会变成。所以新增一个尾指针。始终指向当前链表的尾结点，每次插入只需要针对尾指针进行插入即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
LinkList List_TailInsert(LinkList& L)
{
int x;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode* s = L;
LNode* r = L;
scanf("%d", &x);
while(x != 9999)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
return L;
}
|
头插法：每次输入元素的时候，都插入到单链表的表头。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| LinkList List_HeadInsert(LinkList& L)
{
LNode* s;
int x;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d", &x);
while(x != 9999)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
|
双链表
单链表只能从前往后遍历。如果要访问某结点的前驱，只能再次从前往后遍历一次。所以引入双链表，内部两个指针，分别指向前驱结点和后继结点。
以下我们讨论双链表，默认带头结点。
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
| typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}DNode, *DLinkNode;
bool InitDLinkList(DLinkList &L)
{
L = (DNode*)malloc(sizeof(DNode));
if(L == NULL)
return false;
L->prior = NULL;
L->next = NULL;
return true;
}
bool Empty(DLinkList L)
{
if(L->next == NULL)
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
|
bool InsertNextDNode(DNode *p, DNode *s)
{
if(p == NULL || s == NULL)
return false;
s->next = p->next;
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
17
18
19
20
|
bool DeleteNextDNode(DNode* p)
{
if(p == NULL)
return false;
DNode *q = p->next;
if(q == NULL)
return false;
p->next = q->next;
if(q->next != NULL)
q->next->prior = p;
free(q);
return true;
}
|
销毁双链表，不断调用销毁结点的方法即可
1
2
3
4
5
6
7
| void DestroyList(DLinkList &L)
{
while(L->next != NULL)
DeleteNextDNode(L);
free(L);
L = NULL;
}
|
双链表不可随机存取，按位查找、按值查找都只能用遍历的方法实现，时间复杂度为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
while(p != NULL){
p = p->next;
}
while(p != NULL){
p = p->prior;
}
while(p->prior != NULL){
p = p->prior;
}
|
循环链表
循环链表就是在单链表和双链表的基础上，做一点改变，变为循环单链表和循环双链表。
循环单链表
普通单链表最后一个结点指针指向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 = L;
return true;
}
bool Empty(LinkList L){
if(L->next == L)
return true;
else
return false;
}
bool IsTail(LinkList L, LNode *p){
if(p->next == L)
return true;
else
return false;
}
|
- 单链表从一个结点出发，只能找到后续的各个结点；
- 循环单链表从一个结点出发，可以找到其他任何一个结点；
链表的操作很多都是在头部或者尾部。循环单链表从头找到尾，时间复杂度为,但从尾找到头，时间复杂度仅为。所以很多时候循环单链表不设头指针，仅设尾指针，此时表头插入和表尾插入，时间复杂度都为。
循环双链表
- 双链表：表头结点的prior指向NULL，表尾结点的next指向NULL；
- 循环双链表：表头结点的prior指向表尾结点，表尾结点的next指向表头结点；
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 DNode{
ElemType data;
struct DNode *priot, *next;
}DNode, *DLinkList;
bool InitDLinkList(DLinkList &L){
L = (DNode*)malloc(sizeof(DNode));
if(L == NULL)
return false;
L->prior = L;
L->next = L;
}
bool Empty(DLinkList L){
if(L->next == L)
return true;
else
return false;
}
bool IsTail(DLinkLisk L, DNode* p){
if(p=>next == L)
return true;
else
return false;
}
|
普通双链表的插入和删除，都需要考虑尾结点，因为尾结点后继是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
|
bool InsertNextDNode(DNode *p, DNode *s)
{
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
}
bool DeleteNextDNode(DNode* p)
{
if(p == NULL)
return false;
DNode *q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
|
静态链表
对于普通单链表来说，各个结点在内存中星罗棋布，不连续；
静态链表：借助数组来描述链式存储结构，分配一整片连续的内存空间，各个节点集中安置。数组中分为数据域data和指针域next，这里的指针是指结点的数组下标--游标，next==-1时表示结束。
上图为例，假设每个结点共8B,数据元素占4B，游标占4B，则如果头结点的地址为addr，则存放e1的地址为addr+8*2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#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];
|
基本操作很少考察，代码实现相对动态链表来说，只需要修改指针，而不需要移动元素：
查找操作：
- 从头结点出发挨个往后遍历结点，时间复杂度;
插入位序为i的结点：
- 找到一个空结点，存入数据元素（初始化的时候，可以让next的值为一个特殊值，如-2，这样就知道哪个下标的值为空）；
- 从头结点出发找到位序为的结点；
- 修改新结点的next;
- 修改号结点的next;
删除某个结点：
- 从头结点出发找到前驱结点；
- 修改前驱结点的游标；
- 被删除结点的next设置为-2；
静态链表的优点：增删操作不需要大量移动元素
静态链表的缺点：不能随机存取，只能从头结点开始依次查询；容量固定不可变；
静态链表的适用场景：
- 不支持指针的低级语言；
- 数据元素数量固定不变的场景（如操作系统的文件分配表FAT）
顺序表和链表
逻辑结构
在逻辑结构上都同属于线性表，都是线性结构
存储结构
顺序表：
- 优点：
- 支持随机存取
- 只需要存数据，存储密度高
- 缺点：
- 需要分配大片连续空间；
- 改变容量麻烦
链表：
- 优点：
- 离散的小空间，分配方便
- 改变容量方便
- 缺点：
- 不可随机存取；
- 需要额外存储地址，存储密度低；
基本操作
基本操作分为创建销毁、增删改查
顺序表的创建需要预分配大片连续地址空间，若分配空间过小，则之后不方便扩展容量；若分配空间过大，则浪费内存资源。如果是静态分配，容量不可改；如果是动态分配，虽然可变容量，但需要移动大量元素，时间代价很高；
链表的创建只需要分配一个头结点，之后扩展很方便
顺序表的销毁操作只需要修改Length=0即可。对于静态分配的数据，等待系统自己回收空间；如果是动态分配的数组，那么需要手动free.
链表销毁时依次free结点
顺序表的插入和删除，需要将后续元素依次后移/前移，时间复杂度为，时间开销来自于移动元素。
链表的插入和删除只需要修改指针即可，时间复杂度也为,时间开销来自于查找目标元素。
虽然时间复杂度表示相同，但如果数据元素很大，则移动的时间代价很高，查找元素的时间代价更低。链表的效率要比顺序表高的多。
顺序表有随机存取特性，按位查找的时间复杂度是;链表只能一个一个遍历，时间复杂度为;
顺序表按值查找的时间复杂度为,如果元素有序，则可以利用一些算法在内找到；链表按值查找的时间复杂度为。
顺序表的查找效率更高。
取舍
表长难以预估，经常需要增删元素-------使用链表
表长可预估，查询操作较多--------使用顺序表
试卷中出现开放式题目，回答使用链表还是顺序表更好，可以通过框架来答题：
顺序表和链表的逻辑结构都是线性结构，都属于线性表。但二者存储结构不同，（分别说特点和优缺点），由于采用的存储方式不同，导致基本操作的效率也不一样，（分别说基本操作）
