含义
零个或多个数据元素的有限序列。
在一个较复杂的线性表中，一个数据表可以由若干个数据项组成，比如：
| 学号 | 姓名 | 性别 | 出生年月 | 家庭住址 |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| … |
抽象数据类型定义
ADT 线性表(List)
Data
线性表的数据对象元素集合为{a1,a2,...,an}，每个元素的类型均为DataType。数据元素之间的关系都是一对一关系。
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
ListDelete(*L,i,*e) 删除线性表L中第i个位置元素，并用e返回
ListLength(L) 返回线性表L的元素个数
顺序存储结构
#define MAXSIZE 20
typedef int ElemType
typedef struct {
ElemType data[MAXSIZE]
int length
}SqList
需要三个属性：
- 存储空间的起始位置
- 最大存储容量，数组长度MAXSIZE
- 当前长度——length
| 操作 | 步骤 | 时间复杂度 |
|---|---|---|
| GetElem | a[i] = e | O(1) |
| ListInsert | 1. i不合法，抛错; | O(n) |
| 2. length >= MaxSize，抛错; | ||
| 3. a[i + 1] = a[i]; | ||
| 4. a[i] = e; | ||
| 5. L.length ++ | ||
| ListDelete | 1. i不合法，抛错; | O(n) |
| 2. e = a[i]; | ||
| 3. a[i] = a[i+1]; | ||
| 4. L.length -- |
| 优点 | 缺点 |
|---|---|
| 1. 无须为表示表中元素之间逻辑而增加额外的存储空间 | 1. 插入删除O(n) |
| 2, 可快速存取表中任一位置元素 | 2. 线性表长度变化较大，无法确定MaxSize |
| 3. 造成存储空间碎片 |
链式存储结构
1 -> 2 -> 3
为了表示每个数据元素ai与其后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，不仅要存储本身数据信息，还要存储指示其直接后继的指针。
头指针 —— 链表中第一个结点的存储位置
头结点 —— 为了方便对链表进行操作，会在单链表第一个结点前附设一个结点，数据域可以不存储任何信息
| | 0100| -> |a1|0700| ->...->|an|Null|
头结点 尾结点
| 头指针 | 头结点 |
|---|---|
| 指向链表第一个结点的指针，若有头结点，就指向头结点 | 为了操作方便和统一而设立，放在第一元素结点之前，一般无意义数据 |
| 头指针具有标识作用，常冠以链表名字 | 有了头结点，对第一元素的操作和其他结点一致 |
| 无论链表是否为空，头指针均不为空 | 不一定是链表必要元素 |
typedef struct Node {
ElemType data;
struct Node *next;
}Node
typedef struct Node *LinkList
image.png
| 操作 | 步骤 | 时间复杂度 |
|---|---|---|
| GetElem | 1. p = L->next j = 1 | O(n) |
| 2. p = p -> next j ++ while(j < i) | ||
| 3. 若p = Null 说明第i个元素不存在 | ||
| 4. *e = p -> next | ||
| ListInsert | 1. GetElem(L, i , *e) | 查找O(n) |
| 2. 查找成功，s->data = e | 插入O(1) | |
| 3. s->next = p->next p->next = s | ||
| 4. a[i] = e; | ||
| 5. L.length ++ | ||
| ListDelete | 1. GetElem(L, i , *e) | 查找O(n) |
| 2. 查找成功，q = p -> next | 删除O(1) | |
| 3. p -> next = q -> next | ||
| 4. e = q -> data | ||
| 5. free(q) | ||
| 整表创建——头插法 | 1. InitList(* L) *L -> next = Null | O(n) |
| 2. 循环将结点p插入头结点与前一个新结点之间 | ||
| 整表创建——尾插法 | 1. InitList(* L) *L -> next = Null | |
| 2. 循环将结点p插入尾部 | ||
| 3. 循环结束，p -> next = Null | ||
| ClearList | 1. LinkList p, q | O(n) |
| 2. p = (*L) -> next | ||
| 3. 循环： q = p -> next free(p) q = p | ||
| 4. 循环结束 (L*) -> next = Null |
单链表 VS 循环链表
| 单链表结构 | 顺序存储结构 | |
|---|---|---|
| 存储分配方式 | 任意存储单元存放元素 | 连续存储单元依次存放元素 |
| 时间性能：查找、插入、删除 | 查找O(n) 插入删除：找到位置后操作O(1) | 查找O(1) 插入删除O(n) |
| 空间性能 | 不需要分配存储空间，元素个数不受限制 | 需要预分配空间，会造成浪费式上溢 |
静态链表
用来满足没有指针的一些语言可以创建单链表
数组的元素都是由两个数据域组成：
- data：存放数据
- curr：相当于单链表中的next指针
#define MAXSIZE 1000
typedef struct {
ElemType data;
int curr;
} Component, StackLinkList[MAXSIZE]
约定：
- 数组的一个元素curr指向备用链表的第一个结点的下标；
- 数组的最后一个元素curr指向第一个有数据的元素的下标；
- 数组的第一个元素和最后一个元素不存储任何数据
image.png
如上图所示，这个是1000个元素的静态链表，第0个和第999个元素都不存储任何数据，其中第0个元素curr指向第一个没有数据的元素——坐标为4，第999个元素指向第一个有数据的元素——坐标为1，最后一个有数据的元素3指向头结点——坐标为0。
| 操作 | 步骤 | |
|---|---|---|
| ListInsert | 1. 将元素插入到备用链表的首位p | |
| 2. arr[0].curr = arr[p].curr | ||
| 3. 找到p前的元素q | ||
| 4. arr[q].curr = p | ||
| ListDelete | 1. 找到要删除的元素前一个元素的位置p | |
| 2. arr[p].curr = arr[q].curr | ||
| 3. arr[q].curr = arr[0].curr | ||
| 4. arr[0].curr = q |
| 优点 | 缺点 |
|---|---|
| 插入删除时，不需要移动元素 | 没有解决需要提前分配存储空间的问题；失去了顺序存储结构随机存取的特性 |
循环链表
空表.png
循环判断：p -> next == 头结点，则循环结束
双向链表
空表.png
| 操作 | 步骤 | |
|---|---|---|
| ListInsert | 1. s -> prior = p | |
| 2. s -> next = p -> next | ||
| 3. p -> next -> prior = s | ||
| 4. p -> next = s | ||
| ListDelete | 1. p -> prior -> next = p -> next | |
| 2. p -> next -> prior = p -> prior |
网友评论