cn/~dongeliu/dsa.html 刘东信息学院6系中国科学技术大学

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

针对特定存储结构的算法不具备通用性，但往往效率更高
算法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) {

算法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 8 0 9 9 0 10 head freespace 静态链表的实现结点静态链表 typedef struct { ElemType data; // 数据域 int next; // 指针域 } SLNode; 插入9、删除3 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 8 9 4 9 0 10 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 + 3x x20000 可以表示为： (<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) = x + 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章线性表

cn/~dongeliu/dsa.html 刘东信息学院6系中国科学技术大学

Similar presentations

Presentation on theme: "cn/~dongeliu/dsa.html 刘东信息学院6系中国科学技术大学"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学

Similar presentations

Presentation on theme: "cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学"— Presentation transcript:

Similar presentations

About project

反馈

cn/~dongeliu/dsa.html 刘东信息学院6系中国科学技术大学

Presentation on theme: "cn/~dongeliu/dsa.html 刘东信息学院6系中国科学技术大学"— Presentation transcript: