http://staff.ustc.edu. cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学 Data Structure and Algorithm 《数据结构及其算法》 http://staff.ustc.edu. cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学

第3章 线性表 3.1 线性表的基本概念 3.2 线性表的顺序表示 3.3 线性表的链式表示 3.4 线性结构的深入 2019/1/17 数据结构及其算法 第3章 线性表

3.1 线性表的基本概念 线性表(linear list，常简称list)：n个数据 元素的有限序列 线性表与集合的关系 如：大写字母表(A,B,…,Z) 如：学生信息登记表 线性表与集合的关系 集合中的元素无序，线性表中的元素有序 集合常用线性表表示 记录(record) 数据项(item) 2019/1/17 数据结构及其算法 第3章 线性表

线性表的数学模型：(a1,…,ai-1,ai,ai+1,…,an) 元素个数n称为线性表的长度，n=0时称为空表 1<i<=n时，ai-1是ai的（直接）前驱 1<=i<n时，ai+1是ai的（直接）后继 i是ai在线性表中的位序 线性表的操作： 创建、销毁、清空 计算长度、判断是否为空表 求前驱、求后继 根据位序取元素、查找元素的位序 插入、删除、修改元素 遍历(traverse)：对每个数据元素执行同样的操作 抽象数据类型：线性表 ADT List 课本PP.64~65 2019/1/17 数据结构及其算法 第3章 线性表

算法3.1 求两个集合的并集 void Union(List &La, List &Lb) { int La_len = ListLength(La); while (!ListEmpty(Lb)) { ElemType e; ListDelete(Lb, 1, e); if (!LocateElem(La, e)) ListInsert(La, ++La_len, e); } DestroyList(Lb); 2019/1/17 数据结构及其算法 第3章 线性表

算法3.2 求两个集合的差 void Minus(List &La, List &Lb) { while (!ListEmpty(Lb)) { ElemType e; int i; ListDelete(Lb, 1, e); if ((i=LocateElem(La, e)) != 0) ListDelete(La, i, e); } DestroyList(Lb); 2019/1/17 数据结构及其算法 第3章 线性表

ADT List定义了线性表的数学模型和基本操作 在实现这些基本操作时，既要考虑逻辑结构，又要 考虑存储结构 逻辑结构：ADT List 定义与实现 ADT List定义了线性表的数学模型和基本操作 在实现这些基本操作时，既要考虑逻辑结构，又要 考虑存储结构 逻辑结构：ADT List 存储结构 顺序存储->顺序表 链式存储->链表 同一基本操作，使用不同存储结构时，时空复杂度 往往差别很大 2019/1/17 数据结构及其算法 第3章 线性表

3.2 线性表的顺序表示 顺序表：使用一组地址连续 的存储单元依次存储线性表 的n个元素 元素地址计算方法 LOC(ai+1)=LOC(ai)+l LOC(ai)=LOC(a1)+(i-1)*l b=LOC(a1)称为基地址 逻辑上的先后对应于存储位 置的先后 给定位序，直接确定元素的 存储地址，称为随机存取 2019/1/17 数据结构及其算法 第3章 线性表

地址连续、随机存取->C语言中的数组 线性表需要插入删除->动态分配内存 顺序表的实现 地址连续、随机存取->C语言中的数组 线性表需要插入删除->动态分配内存 元素类型不同的顺序表，其数据类型不同，但主要 实现都是相同的 C++语言中引入模板(template)解决这一问题 typedef int ElemType; // 元素类型 typedef struct { ElemType *elem; // 基地址 int listsize; // 当前分配内存大小，单位是sizeof(ElemType) int length; // 当前线性表长度 } SqList; 2019/1/17 数据结构及其算法 第3章 线性表

思考：ClearList(&L)如何实现？ 顺序表基本操作的实现 算法3.3 算法3.4 思考：ClearList(&L)如何实现？ void InitList_sq(SqList &L, int msize) { L.elem = new ElemType[msize]; L.listsize = msize; L.length = 0; } void DestroyList_sq(SqList &L) { delete []L.elem; L.length = 0; L.listsize = 0; } 2019/1/17 数据结构及其算法 第3章 线性表

算法3.5 算法3.7 bool ListEmpty_sq(SqList L) { return (L.length == 0); } int ListLength_sq(SqList L) { return L.length; } 2019/1/17 数据结构及其算法 第3章 线性表

思考：如何实现“找出顺序表中所有等于e的元素的 位序”？ 算法3.9 算法3.8 思考：如何实现“找出顺序表中所有等于e的元素的 位序”？ void GetElem_sq(SqList L, int i, ElemType &e) { if (i<1 || i>L.length) ErrorMsg("Invalid i value"); e = L.elem[i-1]; } 特别注意：C语言数组下标从0开始，与线性表的位序差1 int LocateElem_sq(SqList L, ElemType e) { for (int i = 1; i <= L.length; ++i) if (L.elem[i-1] == e) return i; return 0; } 2019/1/17 数据结构及其算法 第3章 线性表

插入元素： ListInsert(&L,i,e) 数学描述：将线性表 (a1,…,ai-1,ai,ai+1,…,an) 变为 (a1,…,ai-1,e,ai,ai+1,…,an) 顺序表实现插入时，必须移动 元素才能“腾出”所需的存储空 间 2019/1/17 数据结构及其算法 第3章 线性表

算法3.10 顺序表插入元素 void ListInsert_sq(SqList &L, int i, ElemType e) { if (i<1 || i>L.length+1) ErrorMsg("Invalid i value"); if (L.length == L.listsize) Increment(L, 10); for (int j=L.length-1; j>=i-1; --j) L.elem[j+1] = L.elem[j]; L.elem[i-1] = e; ++L.length; } void Increment(SqList &L, int inc_size) { ElemType *a = new ElemType[L.listsize + inc_size]; for (int i=0; i<L.length; ++i) a[i] = L.elem[i]; delete []L.elem; L.elem = a; L.listsize += inc_size; } 2019/1/17 数据结构及其算法 第3章 线性表

算法分析 移动元素的次数为n-i+1 时间复杂度取决于输入i 如果需要扩容，时间复杂度再加上O(n) 最坏：n次，O(n) for (int j=L.length-1; j>=i-1; --j) L.elem[j+1] = L.elem[j]; for (int i=0; i<L.length; ++i) a[i] = L.elem[i]; 2019/1/17 数据结构及其算法 第3章 线性表

删除元素： ListDelete(&L,i,&e) 数学描述：将线性表 (a1,…,ai-1,ai,ai+1,…,an) 变为 (a1,…,ai-1,ai+1,…,an) 并令e=ai 顺序表实现删除时，必须移 动元素来“填补”不用的存储 空间 2019/1/17 数据结构及其算法 第3章 线性表

算法3.12 顺序表删除元素 void ListDelete_sq(SqList &L, int i, ElemType &e) { if (i<1 || i>L.length) ErrorMsg("Invalid i value"); e = L.elem[i-1]; for (int j=i; j<=L.length-1; ++j) L.elem[j-1] = L.elem[j]; --L.length; } 2019/1/17 数据结构及其算法 第3章 线性表

算法分析 移动元素的次数为n-i 时间复杂度取决于输入i 最坏：n-1次，O(n) for (int j=i; j<=L.length-1; ++j) L.elem[j-1] = L.elem[j]; 思考：如果将顺序表的实现修改为 则在频繁插入删除元素时，会有什么问题？ 能不能不记录“当前分配内存大小”这个信息？ typedef struct { ElemType *elem; // 基地址 int length; // 当前线性表长度，同时也是当前分配内存大小 } SqList; 2019/1/17 数据结构及其算法 第3章 线性表

顺序表实现算法3.1 算法分析：O(mn+n2) void Union(List &La, List &Lb) { int La_len = ListLength(La); while (!ListEmpty(Lb)) { ElemType e; ListDelete(Lb, 1, e); if (!LocateElem(La, e)) ListInsert(La, ++La_len, e); } DestroyList(Lb); 2019/1/17 数据结构及其算法 第3章 线性表

针对特定存储结构的算法不具备通用性，但往往效 率更高 算法3.13 顺序表求并集 算法分析：O(mn+n2/2) 针对特定存储结构的算法不具备通用性，但往往效 率更高 void Union_sq(SqList &La, SqList &Lb) { Increment(La, Lb.length); for (int i=0; i<Lb.length; ++i) { ElemType e = Lb.elem[i]; int j = 0; while(j<La.length && La.elem[j]!=e) ++j; if (j==La.length) { La.elem[La.length++] = e; } delete []Lb.elem; Lb.length = Lb.listsize = 0; 2019/1/17 数据结构及其算法 第3章 线性表

算法3.25~3.27 交换顺序表的前m个元素和后n个 元素，要求算法空间复杂度尽可能低 算法3.25 对每个bk (k=1…n)，暂存bk 将ai (i=1…m)逐个后移一位 将暂存的bk放到合适位置 算法3.26 逆置顺序表，即交换ai与an+1-i (i=1…n) 算法3.27 逆置原表 逆置前n个元素 逆置后m个元素 2019/1/17 数据结构及其算法 第3章 线性表

C++中的vector类是顺序表的一种实现 顺序表的特点 优点 随机存取：访问任一元素的时间复杂度均为O(1) 逻辑相邻<->物理相邻，便于查找前驱、后继 没有额外存储 缺点 插入、删除元素复杂：时间复杂度为O(n)，且需要移动 元素 预分配空间不易确定：分配少了会发生频繁的重新分配， 分配多了会浪费 C++中的vector类是顺序表的一种实现 2019/1/17 数据结构及其算法 第3章 线性表

3.3 线性表的链式表示 链表：用一组任意的存储单元存储线性表的数据元 素，用指针(pointer)或称链(link)来表示元素 之间的逻辑关系 单链表：每个数据元素附加一个指针来指向其直接 后继 数据域 指针域 结点 头指针：第一个结点的地址 最后一个结点的指针域为NULL 2019/1/17 数据结构及其算法 第3章 线性表

p->next是该结点的指针域，指向下一个结点 生成一个结点：p = new LNode; 回收一个结点：delete p; 单链表的实现 注意：头指针和结点中的指针类型是一样的 LinkList p; // p指向一个结点 p->data是该结点的数据域 p->next是该结点的指针域，指向下一个结点 生成一个结点：p = new LNode; 回收一个结点：delete p; typedef int ElemType; // 元素类型 typedef struct LNode { ElemType data; // 数据域 LNode *next; // 指针域 } *LinkList; data next p 2019/1/17 数据结构及其算法 第3章 线性表

头结点：有时在链表的第一个数据元素之前附设的 一个结点 优点： 可以在该结点中存储信息，例如链表的长度 可以简化程序 带头结点的单链表，是否为空？ L->next==NULL 不带头结点的单链表，是否为空？ L==NULL 2019/1/17 数据结构及其算法 第3章 线性表

思考：DestroyList(&L)如何实现？ 单链表基本操作的实现 算法3.14 算法3.15 思考：DestroyList(&L)如何实现？ void InitList_L(LinkList &L) { L = NULL; } int ListLength_L(LinkList L) { LNode *p = L; int j = 0; while (p) { p = p->next; ++j; } return j; 2019/1/17 数据结构及其算法 第3章 线性表

查找元素的位序 链表没有随机存储性质，位序不便使用 算法3.16 int LocateElem_L(LinkList L, ElemType e) { LNode *p = L; int j = 1; while (p && p->data != e) { p = p->next; ++j; } return p ? j : 0; LNode* LocateElem_L2(LinkList L, ElemType e) { LNode *p = L; while (p && p->data != e) p = p->next; return p; } 2019/1/17 数据结构及其算法 第3章 线性表

链表插入元素 给定位序插入元素 … … 时间复杂度：O(n) 思考：如果L带头结点，要做怎样的修改？ ai-1 next q ai next s void ListInsert_L(LinkList &L, int i, ElemType e) { LNode *s = new LNode; s->data = e; if (i == 1) { s->next = L; L = s; } else { LNode *q = L; int j = 1; while (q && j < i-1) { q = q->next; ++j; } if (!q || j > i-1) ErrorMsg("Invalid i value"); s->next = q->next; q->next = s; } 时间复杂度：O(n) 思考：如果L带头结点，要做怎样的修改？ 2019/1/17 数据结构及其算法 第3章 线性表

给定指针插入元素（后插） 算法3.17 给定指针插入元素（前插） 思考：前插能否借助后插来实现？ void ListInsert_L(LinkList &L, LNode *p, LNode *s) { s->next = p->next; p->next = s; } void ListInsert_L(LinkList &L, LNode *p, LNode *s) { if (p == L) { s->next = L; L = s; } else { LNode *q = L; while (q && q->next != p) q = q->next; if (!q) ErrorMsg("Invalid p value"); s->next = p; q->next = s; 思考：前插能否借助后插来实现？ 2019/1/17 数据结构及其算法 第3章 线性表

链表删除元素 算法3.18 给定指针删除元素 … … 时间复杂度：O(n) 思考：如果L带头结点，要做怎样的修改？ p ai-1 next q … ai next ai+1 next … void ListDelete_L(LinkList &L, LNode *p, ElemType &e) { if (p == L) L = L->next; else { LNode *q = L; while (q->next && q->next != p) q = q->next; if (!(q->next)) ErrorMsg("Invalid p value"); q->next = p->next; } e = p->data; delete p; 时间复杂度：O(n) 思考：如果L带头结点，要做怎样的修改？ 2019/1/17 数据结构及其算法 第3章 线性表

单链表实现算法3.1 算法分析：O(2mn+n2) void Union(List &La, List &Lb) { int La_len = ListLength(La); while (!ListEmpty(Lb)) { ElemType e; ListDelete(Lb, 1, e); if (!LocateElem(La, e)) ListInsert(La, ++La_len, e); } DestroyList(Lb); 2019/1/17 数据结构及其算法 第3章 线性表

算法3.19 单链表求并集 算法分析：O(mn+n2/2) void Union_L(LinkList &La, LinkList &Lb) { if (!La) {La = Lb; return;} while (Lb) { LNode *s = Lb; Lb = Lb->next; LNode *pre = NULL, *p = La; while (p && p->data != s->data) { pre = p; p = p->next; } if (p) delete s; else {pre->next = s; s->next = NULL;} 2019/1/17 数据结构及其算法 第3章 线性表

算法3.20 单链表求并集改进版 算法分析：O(mn) void Union_L2(LinkList &La, LinkList &Lb) { LNode *pa = La; while (Lb) { LNode *s = Lb; Lb = Lb->next; LNode *p = pa; while (p && p->data != s->data) { p = p->next; } if (p) delete s; else {s->next = La; La = s;} 2019/1/17 数据结构及其算法 第3章 线性表

顺序表和单链表的比较 相同点 顺序表特点 单链表特点 逻辑结构 线性表 存储结构 顺序存储结构： 动态数组 链式存储结构： 指针链接的结点 额外存储 无，存储中全是数据元素 （但是可能有未用的预分配空间） 有，数据元素后附加指针域 （不需要预先分配空间） 位序->元素 O(1) 随机存取 O(n) 非随机存取 查找前驱、后继 容易 后继容易 前驱困难 插入、删除 复杂度均为O(n) 时间用在“移动元素” 时间用在“定位元素” 2019/1/17 数据结构及其算法 第3章 线性表

3.4 线性结构的深入 单链表的改进 单链表存在一些使用上的不便 解决方案：充分利用指针的灵活性 丢失了头指针，就无法访问链表中的所有元素 表头插入删除容易，表尾插入删除困难 计算表长复杂度高 找后继容易、找前驱困难 解决方案：充分利用指针的灵活性 2019/1/17 数据结构及其算法 第3章 线性表

循环链表：整个链表形成一个环 经常与头结点配合使用 判断是否为空表： L->next == L 查找元素（修改算法3.16） 优点：从表中任一结点出发，均可找到表中其它结点 LNode* LocateElem_L3(LinkList L, ElemType e) { LNode *p = L->next; while (p != L && p->data != e) p = p->next; return p == L ? NULL : p; } 2019/1/17 数据结构及其算法 第3章 线性表

p->data=e; p->next=L->next; L->next=p; 尾指针：指向最后一个元素 设有尾指针的单链表： 表头插入元素： p->data=e; p->next=L->next; L->next=p; 表尾插入元素： p->data=e; p->next=NULL; tail->next=p; tail=p; tail p e tail tail p e NULL 2019/1/17 数据结构及其算法 第3章 线性表

循环链表+尾指针 循环链表一般只设尾指针，无需头指针 两个只设尾指针的循环链表首尾相接： temp = B->next; // B表头 B->next = A->next; // 新的表头 A->next = temp->next; // 头尾相接 A = B; //新的表尾 delete temp; //回收结点 2019/1/17 数据结构及其算法 第3章 线性表

单链表+尾指针+表长 算法3.23 从数组创建链表 思考：对于单链表如何实现该算法？ typedef struct { LinkList head, tail; int length; } AdvLinkList; void CreateList_AdvL(AdvLinkList &L, ElemType *A, int n) { L.head = L.tail = new LNode; L.head->next = NULL; L.length = 0; for (int i = 0; i < n; ++i) { LNode *s = new LNode; s->data = A[i]; s->next = NULL; L.tail->next = s; L.tail = s; L.length++; } 思考：对于单链表如何实现该算法？ 2019/1/17 数据结构及其算法 第3章 线性表

双向链表：每个结点有两个指针域，分别指向直接 前驱和直接后继 优点：查找前驱、后继都很方便 双向链表的特性： p->next->prior = p = p->prior->next 双向循环链表：整个链表形成两个环 typedef struct DLNode { ElemType data; DLNode *prior; DLNode *next; } *DLinkList; 2019/1/17 数据结构及其算法 第3章 线性表

双向链表插入元素 算法3.21 p … ai-1 ai … s e void ListInsert_DL(DLinkList &L, DLNode *p, DLNode *s) { s->prior = p->prior; s->next = p; p->prior->next = s; p->prior = s; } 2019/1/17 数据结构及其算法 第3章 线性表

双向链表删除元素 算法3.22 p … ai-1 ai ai+1 … void ListDelete_DL(DLinkList &L, DLNode *p, ElemType &e) { e = p->data; p->prior->next = p->next; p->next->prior = p->prior; delete p; } 2019/1/17 数据结构及其算法 第3章 线性表

链表中，位序的概念被淡化，“位置”（地址）的概 念被强化 链表的特点 优点 插入、删除元素较为简单：给定位序做插入删除，时间复 杂度为O(n)，但不需要移动元素，只需要修改指针 指针的用法非常灵活：循环链表、尾指针、双向链表…… 不需要预先分配空间 缺点 非随机存取 有额外存储（指针域） 链表中，位序的概念被淡化，“位置”（地址）的概 念被强化 C++中的list类是双向链表的一种实现， forward_list类是单链表的一种实现 2019/1/17 数据结构及其算法 第3章 线性表

当程序不允许动态分配内 存时，如何实现链表？ 有些高级语言(如Java)不 提供指针 静态链表：以预分配内存 的相对地址（数组下标） 替代绝对地址（指针）而 实现的链表 静态链表中如何管理内存？ 方案1：附设bool数组，记 录预分配内存是否已被占用 方案2：附设另一个静态链 表，管理尚未被占用的内存 数组下标 数据域 指针域 2 1 zhao 4 3 zhou 8 qian 6 5 li sun 7 zheng 9 wu wang -1 10 2019/1/17 数据结构及其算法 第3章 线性表

静态链表的实现 结点 静态链表 head 2 3 5 8 4 6 10 typedef struct { 0 0 1 1 2 2 2 3 3 3 5 4 4 8 5 5 4 6 6 6 7 7 10 -1 8 0 9 9 0 10 10 0 -1 head freespace 静态链表的实现 结点 静态链表 2 3 5 8 4 6 10 typedef struct { ElemType data; // 数据域 int next; // 指针域 } SLNode; 插入9、删除3 2 5 9 8 4 6 10 typedef struct { SLNode *space; // 预分配内存 int listsize; // 预分配内存大小（减去1） int head; // 链表的头指针（链表中有头结点） int freespace; // 空闲内存的头指针 } SLinkList; 0 0 1 1 2 3 2 3 9 3 5 8 4 8 5 5 4 6 6 6 7 7 10 -1 8 9 4 9 0 10 10 0 -1 head freespace 2019/1/17 数据结构及其算法 第3章 线性表

静态链表插入元素 void ListInsert_SL(SLinkList &L, int i, ElemType e) { int s = L.freespace; if (s == -1) ErrorMsg("List is full"); L.freespace = L.space[s].next; L.space[s].data = e; int q = L.head; int j = 0; while (q != -1 && j < i-1) { q = L.space[q].next; ++j; } if (q == -1 || j > i-1) ErrorMsg("Invalid i value"); L.space[s].next = L.space[q].next; L.space[q].next = s; 2019/1/17 数据结构及其算法 第3章 线性表

有序表：线性表中的元素按照值的非递减或非递增 有序排列 有序表既可以顺序存储，又可以链式存储 算法3.24 有序表的纯化（去除重复元素） void purge(SqList &L) { int i = -1, j = 0; while (j < L.length) { if (j == 0 || L.elem[j] != L.elem[i]) L.elem[++i] = L.elem[j]; ++j; } L.length = i+1; 2019/1/17 数据结构及其算法 第3章 线性表

算法3.28 有序表求并集（有头结点的单链表） 思考：试比较各种实现的求并集算法 void Union_ord(LinkList &La, LinkList &Lb) { LNode *pa = La->next, *pb = Lb->next, *rc = La; while (pa && pb) { if (pa->data < pb->data) { rc->next = pa; rc = pa; pa = pa->next; } else if (pa->data > pb->data) { rc->next = pb; rc = pb; pb = pb->next; else { LNode *qb = pb; pb = pb->next; delete qb; if (!pb) rc->next = pa; else rc->next = pb; delete Lb; 思考：试比较各种实现的求并集算法 2019/1/17 数据结构及其算法 第3章 线性表

Pn(x) = p0 + p1x + p2x2 + … + pnxn 可以表示为线性（有序）表： (p0, p1, p2,…, pn) 线性表应用举例：一元多项式运算 如何表示一元多项式？ Pn(x) = p0 + p1x + p2x2 + … + pnxn 可以表示为线性（有序）表： (p0, p1, p2,…, pn) 如果系数中非零元很少，为了节省存储空间，可以 只存储非零元的系数和指数 例如：S(x) = 1 + 3x10000 + 2x20000 可以表示为： (<1,0>, <3,10000>, <2,20000>) 2019/1/17 数据结构及其算法 第3章 线性表

一元多项式求和 A(x) = 7 + 3x + 9x8 + 5x17 B(x) = 8x + 22x7 + (-9)x8 C(x) = A(x) + B(x) = 7 + 11x + 22x7 + 5x17 类似于有序表的归并 2019/1/17 数据结构及其算法 第3章 线性表

一元多项式及其加法的实现 typedef struct { double coef; // 系数 int expn; // 指数 } ElemType; typedef struct LNode { ElemType data; LNode *next; } *Polynomial; void add(Polynomial &La, Polynomial &Lb) { LNode *pa = La->next, *pb = Lb->next, *rc = La; while (pa && pb) { // 见下页 } if (!pb) rc->next = pa; else rc->next = pb; delete Lb; 2019/1/17 数据结构及其算法 第3章 线性表

一元多项式求和的实现（修改算法3.28） while (pa && pb) { if (pa->data.expn < pb->data.expn) { rc->next = pa; rc = pa; pa = pa->next; } else if (pa->data.expn > pb->data.expn) { rc->next = pb; rc = pb; pb = pb->next; else { double sum = pa->data.coef + pb->data.coef; if (fabs(sum) < 1e-9) { LNode *qa = pa; pa = pa->next; delete qa; pa->data.coef = sum; LNode *qb = pb; pb = pb->next; delete qb; 2019/1/17 数据结构及其算法 第3章 线性表

本章复习提纲 线性表的基本概念 顺序表和单链表 链表的高级形态 有序表及其操作 存储结构及其特点 基本操作的实现 循环链表、尾指针 双向链表 静态链表 有序表及其操作 2019/1/17 数据结构及其算法 第3章 线性表

作业 3.3, 3.4, 3.5, 3.8 (顺序表、带头结点的单 链表), 3.9 3.3 顺序表的有序插入算法 3.4 单链表的有序插入算法 3.5 顺序表的逆置算法 3.8 分离奇偶算法 3.9 双向循环链表改造算法 2019/1/17 数据结构及其算法 第3章 线性表