第二章 线性表 ￡2.4 线性表的应用 ￡2.1 线性表的类型定义 ￡2.2 线性表的顺序存储结构 ￡2.3 线性表的链式存储结构

Presentation on theme: "第二章 线性表 ￡2.4 线性表的应用 ￡2.1 线性表的类型定义 ￡2.2 线性表的顺序存储结构 ￡2.3 线性表的链式存储结构"— Presentation transcript:

1 第二章 线性表 ￡2.4 线性表的应用 ￡2.1 线性表的类型定义 ￡2.2 线性表的顺序存储结构 ￡2.3 线性表的链式存储结构
第二章 线性表 ￡2.4 线性表的应用 ￡2.1 线性表的类型定义 ￡2.2 线性表的顺序存储结构 ￡2.3 线性表的链式存储结构 ￡2.4.1 集合运算 ￡2.4.2 一元多项式的表示及相加 ￡2.3.1 线性链表 ￡2.3.2 循环链表 ￡2.3.3 双向链表

2 ￡2.1 线性表的类型定义 一个线性表是n个数据元素的有限序列 。线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。例如： 例一：（A,B,C,…,Z） 例二：（6,17,28,50,92,188） 例三： 001 高等数学 樊映川 S01 … 002 理论力学 罗远祥 L01 003 华罗庚 004 线性代数 栾汝书 S02 在表 中 领先于 , 领先于 ，称 是 的直接前驱元素， 是 的直接后继元素。当i＝1,2,…,n-1时， 有且仅有一个直接后继，当i＝2,3,…,n时， 有且仅有一个直接前驱。

3 线性表的长度：线性表中元素的个数n（>=0）。当n＝0时，称为空表。
数据元素在线性表中的位序：在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素。称i为数据元素ai在线性表中的位序。 抽象数据类型线性表的定义如下： ADT List{ 数据对象：D={ ai| ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1＝{< ai-1, ai >|ai-1,ai ∈D,i=2,…,n} 基本操作： InitList(&L) 操作结果：构造一个空的线性表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ClearList(&L) 操作结果：将L重置为空表。 ListEmpty(L) 操作结果：若L为空表，则返回TRUE，否则返回FALSE。

4 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。 GetElem(L, i, &e) 初始条件：线性表L已存在，1≤i≤ListLength(L)。 操作结果：用e返回L中第i个数据元素的值。 LocateElem(L, e, compare()) 初始条件：线性表L已存在, compare()是数据元素判定函数。 操作结果：返回L中第1个与e满足关系compare()的数据元素 的位序。若这样的数据元素不存在，则返回值为0。 PriorElem(L, cur_e, &pre_e) 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。 NextElem(L, cur_e, &next_e) 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e 返回它的后继，否则操作失败，next_e无定义。 ListInsert(&L, i, e) 初始条件：线性表L已存在, 1≤i≤ListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1. ListDelete(&L, i, &e) 初始条件：线性表L已存在且非空, 1≤i≤ListLength(L)。 操作结果：删除L中第i个数据元素，并用e返回其值，L的长度减1.

5 例2-1 已知线性表LA和LB分别表示两个集合A和B。求一个新的集合A=A∪B。
ListTraverse(L, visit()) 初始条件：线性表L已存在。 操作结果：依次对L的每个数据元素调用函数visit()。一旦visit() 失败，则操作失败。 }ADT List 例2-1 已知线性表LA和LB分别表示两个集合A和B。求一个新的集合A=A∪B。 算法2.1如下： void union(List &La, List Lb){ //将所有在线性表Lb中但不在La中的数据元素插入到La中 La_len=ListLength(La); //求线性表的长度 Lb_len=ListLenght(Lb); for (i=1;i<=Lb_len; i++) { GetElem (Lb, i, e); //取Lb中第i个数据元素赋给e If (! LocateElem (La, e, equal)) ListInsert (La, ++La_len, e); //La中不存在和e相同的数据元素， //则插入之。 } 时间复杂度为O(ListLength(LA)×ListLength(LB)) 例 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。

6 算法2.2如下： void MergeList (List La, List Lb, List &Lc){ //已知线性表La和Lb中的数据元素按值非递减排列。 //归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列。 InitList (Lc); i=j=1; k=0; La_len=ListLength (La); Lb_len=ListLenght (Lb); while ((i<=La_len) && (j<=Lb_len)) { //La和Lb均非空 GetElem (La, i, ai); GetElem (Lb, j, bj); if (ai<=bj) {ListInsert (Lc, ++k, ai); ++i ;} else {ListInsert (Lc, ++k, bj); ++j ;} } while (i<=La_len) { GetElem (La, i++, ai); ListInsert (Lc, ++k; ai); while (j<=Lb_len) { GetElem (Lb, j++, bj); ListInsert (Lc, ++k; bj); } //MergeList 时间复杂度为: O(ListLength(LA)+ListLength(LB))

7 ￡2.2 线性表的顺序存储结构 （1）线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。如下图2.1所示：
存储地址 内存状态 数据元素在线性表中的位序 b a b+l a2 2 … … … b+(i-1)l ai i b+(n-1)l an n b+nl … 空闲 b+(maxlen-1)l 特点：以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系 线性表的这种机内表示称做线性表的顺序存储结构或顺序映像(sequential mapping)。 通常称这种存储结构的线性表为顺序表。

8 （2）求址公式 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址 作为数据元素的存储位置。 线性表中第i＋1个数据元素的存储位置 和第i个数据元素的存储位置 之间满足下列关系： 线性表的第i个数据元素ai的存储位置为： 式中 是线性表的第一个数据元素 的存储位置，通常称做线性表的起始位置 或基地址。 只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取。线性 表的顺序存储结构是一种随机存取的存储结构。 （3）线性表的动态分配顺序存储结构的C语言描述 #define LIST_INIT_SIZE //线性表存储空间的初始分配量 #define LISTINCREMENT //线性表存储空间的分配增量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 //（以sizeof(ElemType)为单位） }SqList；

9 序号 数据元素 序号 数据元素 序号 数据元素 序号 数据元素 1 12 1 12 1 12 1 12
（4）线性表的插入和删除运算 序号 数据元素 序号 数据元素 序号 数据元素 序号 数据元素 (a) (b) (a) (b) 图2.2 线性表插入前后的情况 图2.3 线性表删除前后的情况 (a)插入前n＝ (a)删除前n＝8 (b)插入后n＝ (b)删除后n＝7 插入25 删除24

10 插入运算 算法2.3如下： Status ListInsert_Sq (SqList &L, int i, ElemType e) { //在顺序线性表L中第i个位置之前插入新的元素e， //i的合法值为1≤i≤ListLength_Sq(L)+1 if (i<1|| i>L.length+1) return ERROR; //i值不合法 if (L.length>=L.listsize) { //当前存储空间已满，增加分配 newbase = (ElemType *) realloc (L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); //存储分配失败 L.elem = newbase; //新基址 L.listsize += LISTINCREMENT; //增加存储容量 } q = & (L.elem[i－1]); //q为插入位置 for (p = & (L.elem[L.length－1]); p>=q; ――p) * (p+1) = *p; //插入位置及之后的元素右移 * q = e; //插入e ++L.length; //表长增1 return OK; } //ListInsert_Sq

11 删除运算 算法2.4如下： Status ListDelete_Sq (SqList &L, int i, ElemType &e) { //在顺序线性表L中删除第i个元素，并用e返回其值 //i的合法值为1≤i≤ListLength_Sq(L) if (i<1|| i>L.length) return ERROR; //i值不合法 p = & (L.elem[i－1]); //p为被删除元素的位置 e = *p; //被删除元素的值赋给e q = L.elem + L.length－1; //表尾元素的位置 for (++p; p<=q; ++p) * (p－1) = *p; //被删除元素之后的元素左移 ――L.length; //表长减1 return OK; } //ListDelete_Sq

12 （5）时间复杂度 从上述算法可见，当在顺序存储结构的线性表中某个位置上插入或删除一个数据 元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位 置。 假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一 个元素时所需移动元素次数的期望值为： 不失一般性，若在线性表的任何位置插入元素都是等概率的，即 ， 上式可化简为： 对于删除过程，假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一 同样假设是等概率的情况，即 ，则有： 结论：由此可见，在顺序存储结构的线性表中插入或删除一个数据元素，平均 约移动表中一半元素。若表长为n，则算法ListInsert_Sq和ListDelete_Sq的时间复杂 度为O(n)。

13 （6）顺序表的 算法2.5如下： void MergeList_Sq (SqList La, SqList Lb, SqList &Lc){ //已知顺序线性表La和Lb中的数据元素按值非递减排列。 //归并La和Lb得到新的顺序线性表Lc，Lc的数据元素也按值非递减排列。 pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length + Lb.length; pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType)); if (!Lc.elem) exit (OVERFLOW); //存储分配失败 pa_last = La.elem + La.length – 1; pb_last = Lb.elem + Lb.length – 1; while (pa <= pa_last && pb <= pb_last) { //归并 if (*pa <= *pb) *pc++ = *pa++; else *pc++ = *pb++; } while (pa <= pa_last) *pc++ = *pa++; //插入La的剩余元素 while (pb <= pb_last) *pc++ = *pb++; //插入Lb的剩余元素 } //MergeList_Sq 合并算法

14 ￡2.3 线性表的链式存储结构 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上
也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单、直观 的公式来表示。其主要缺点有下面两个： （1）作插入或删除操作时，需移动大量元素。 （2）在为长度变化较大的线性表预先分配存储空间时，必须按最大可能空 间分配（在某些情况下最大空间甚至是不可知的）。存储空间不能得 到充分利用。 而链式存储结构，它不要求逻辑上相邻的元素在物理位置上也相邻，因此 它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。

15 ￡2.3.1 线性链表 （1）定义 特点：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是 连续的，也可以是不连续的）。
为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，除了 存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组 成数据元素 的存储映像，即结点（node）。如图2.4所示： 数据域 指针域 图2.4 结点结构 数据域：存储数据元素的信息。 指针域：存储直接后继的存储位置。 n个结点（ （1≤i≤n））链结成一个链表，即为线性表 的 链式存储结构。由于此链表的每个结点中只包含一个指针域，故又称线性链表或 单链表。

16 例如：线性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）共8个数据元素。
其链式存储结构如图2.5所示： 存储地址 数据域 指针域 LI 头指针H QIAN SUN WANG NULL WU ZHAO ZGENG ZHOU 图2.5 线性链表示例 注意：①整个链表的存取必须从头指针开始进行； ②头指针指示链表中第一个结点的存储位置； ③线性链表中最后一个结点的指针为“空”（NULL）。

17 （2）线性表的单链表存储结构的C语言描述 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; （3）线性表的带头结点的单链表存储结构的图形表示 ①带头结点的“空”单链表 L NULL ②带头结点的“非空”单链表 L a a an ^

18 在单链表中插入或删除一个结点时，仅需修改指针而无需移动元素。
（4）单链表的插入和删除运算 P a b (a)插入前 a b s x (b)插入后 图2.6 在单链表中插入结点时指针变化情况 用语句描述如下：s－>next = p－>next; p－>next = s; a b c 图2.7 在单链表中删除结点时指针变化情况 用语句描述如下：p－>next ＝ p－>next－>next； 在单链表中插入或删除一个结点时，仅需修改指针而无需移动元素。

19 单链表的插入运算 算法2.6如下： Status ListInsert_L (LinkList &L, int i, ElemType e) { //在带头结点的单链线性表L中第i个位置之前插入元素e p = L; j=0; while (p && j < i－1) { //寻找第i－1个结点 p = p－>next; ++j; } if (!p || j > i－1) return ERROR; //i小于1或者大于表长 s = (LinkList) malloc (sizeof (LNode)); //生成新结点 s－>data = e; //插入L中 s－>next = p－>next; p－>next = s; return OK; }//ListInsert_L

20 单链表的删除运算 算法2.7如下： Status ListDelete_L (LinkList &L, int i, ElemType &e) { //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 p = L; j=0; while (p－>next && j < i－1) { //寻找第i－1个结点，并令p指向其前驱 p = p－>next; ++j; } if (!(p－>next) || j > i－1) return ERROR; //删除位置不合理 q = p－>next; //删除并释放结点 p－>next = q－>next; e = q－>data; free (q)； return OK; }//ListDelete_L

21 （5） 算法2.8如下： void MergeList_L (LinkList &La, LinkList &Lb, LinkList &Lc){ //已知单链线性表La和Lb中的数据元素按值非递减排列。 //归并La和Lb得到新的单链线性表Lc，Lc的数据元素也按值非递减排列。 pa = La－>next; pb = Lb－>next; Lc = pc = La; while (pa && pb) { //归并 if (pa－>data<= pb－>data){ pc－>next = pa; pc = pa; pa = pa－>next; } else { pc－>next = pb; pc = pb; pb = pb－>next; pc－>next = pa ? pa : pb; //插入剩余段 free (Lb); //释放Lb的头结点 } //MergeList_L 单链表的合并算法

22 （6）静态链表 ①C语言描述 #define MAXSIZE 100 //链表的最大长度 typedef struct { ElemType data; int cur; }component, SLinkList[MAXSIZE]; ②图形表示 例如： 数组下标 数据域 指针域 1 ZHAO 2 2 QIAN 3 3 SUN 4 4 LI 9 5 ZHOU 6 WU 7 ZHENG 8 8 WANG 0 9 SHI 5 这种存储结构仍需要预先分配一个较大的空间，但在作线性表的插入和删除操作时不需要移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

23 ￡2.3.2 循环链表 （1）定义 循环链表（circular linked list）是另一种形式的链式存储结构。
特点：①表中最后一个结点的指针域指向头结点，整个链表形成一个环。 ②从表中任一结点出发均可找到表中其他结点。 （2）图形表示 H (a) 非空表 (b)空表 图2.8 单循环链表 循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是 p或p－>next是否为空，而是它们是否等于头指针。

24 ￡2.3.3 双向链表 （1）定义 双向链表（double linked list）：双向链表的结点中有两个指针域，其一指
向直接后继，另一指向直接前驱。 前驱 数据元素 后继 图2.9 结点结构 （2）图形表示 L (a) 空的双向循环链表 L A B C (b) 非空的双向循环链表 图2.10 双向链表示例

25 （3）C语言描述 typedef struct DulNode { ElemType data; struct DulNode *prior; struct DulNode *next; }DulNode, * DuLinkList; （4）双向循环链表的插入和删除运算 P a b ① ② ④ ③ x s 图2.11 在双向链表中插入一个结点时指针的变化情况 ① P a b c ② 图2.12 在双向链表中删除结点时指针的变化情况

26 双向循环链表的插入运算 算法2.9如下： Status ListInsert_DuL (DuLinkList &L, int i, ElemType e) { //在带头结点的双链循环线性表L中第i个位置之前插入元素e， //i的合法值为1≤i≤表长＋1。 if (!(p = GetElemP_DuL(L, i))) //在L中确定第i个元素的位置指针p return ERROR; //p＝ NULL，即第i个元素不存在 if (!(s =(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s－>data = e; s－>prior = p－>prior; p－>prior－>next = s; s－>next = p; p－>prior = s; return OK; } //ListInsert_DuL

27 双向循环链表的删除运算 算法2.10如下： Status ListDelete_DuL (DuLinkList &L, int i, ElemType &e) { //删除带头结点的双链循环线性表L中第i个元素， //i的合法值为1≤i≤表长。 if (!(p = GetElemP_DuL(L, i))) //在L中确定第i个元素的位置指针p return ERROR; //p＝ NULL，即第i个元素不存在 e = p－>data; p－>prior－>next = p－>next; p－>next－>prior = p－>prior; free (p); return OK; } //ListDelete_DuL

28 ￡2.4 线性表的应用 ￡2.4.1 集合运算 例：求解（A－B）∪（B－A）
链表S，而后在输入集合B的元素的同时查找S表，若存在和B相同的元素，则从 S表中删除之，否则将此元素插入S表。 为算法的清晰可见，我们先给出3个过程： 1，将整个数组空间初始化成一个链表。 算法2.11如下： void InitSpace_SL (SLinkList &space) { //将一维数组space中各分量链成一个备用链表，space[0].cur为头指针 //“0”表示空指针 for (i = 0; i < MAXSIZE－1; ++i) space[i].cur = i + 1; space[MAXSIZE－1].cur = 0; } //InitSpace_SL

29 2，从备用空间取得一个结点。 算法2.12如下： int Malloc_SL (SLinkList &space) { //若备用空间链表非空，则返回分配的结点下标，否则返回0 i = space[0].cur; if (space[0].cur) space[0].cur = space[i].cur; return i; } //Malloc_SL 3，将空闲结点链结到备用链表上。 算法2.13如下： void Free_SL (SLinkList &space, int k) { //将下标为k的空闲结点收回到备用链表 space[k].cur = space[0].cur; space[0].cur = k; } //Free_SL

30 算法2.14如下： void difference (SLinkList &space, int &S) { //依次输入集合A和B的元素，在一维数组space中建立表示集合(A－B)∪(B－A) //的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为其头指针。 InitSpace_SL(space); //初始化备用空间 S = Malloc_SL(space); //生成S的头结点 r = S; //r指向S的当前最后结点； scanf (m,n); //输入A和B的元素个数 for (j = 1; j <= m; ++j) { //建立集合A的链表 i = Malloc_SL (space); //分配结点 scanf (space[i].data); //输入A的元素值 space[r].cur = i; //插入到表尾 r = i; } //for space[r].cur = 0; //尾结点的指针为空 for (j = 1; j <= n; ++j) { //依次输入B的元素，若不在当前 //表中则，插入，否则，删除 scanf(b); p = S; k = space[S].cur; //k指向集合A中第一个结点 集合运算

31 while (k !=space[r].cur && space[k].data!=b) { //在当前表中查找
p = k; k = space[k].cur; } //while if (k = = space[r].cur) { //当前表中不存在该元素，插入在 // r所指结点之后，且r的位置不变 i = Malloc_SL (space); space[i].data = b; space[i].cur = space[r].cur; space[r].cur = i; } //if else { //该元素已在表中删除之 space[p].cur = space[k].cur; Free_SL (space, k); if (r = = k) r = p; //若删除的是r所指结点， //则需修改尾指针 } //else } //for } //difference

32 ￡2.4.2 一元多项式的表示及相加 在数学上，一个多项式可表示为： 。用 线性表可表示为 。 假设 是一元m次多项式： （m<n）。
在数学上，一个多项式可表示为： 。用 线性表可表示为 。 假设 是一元m次多项式： （m<n）。 则两个多项式相加的结果： 。用线性表可表示 为： 。 若对P,Q,R采用顺序存储结构，则问题很简单： p q p0 + q0 p q p1 + q1 … … … pm qm pm + qm … … pn pn

33 然而，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结
构的最大长度很难确定。例如：。就要用一长度为20001的线性表来表示，而表中 仅有3个非零元素，这种对内存空间的浪费是应该避免的。 为此我们可以用单链表来实现。在单链表中每个结点有两个数据项（系数项和 指数项）。 例如： 和 相加。 A ^ B ^ C ^ 22 7 图2.14 多项式相加链式存储结构示例

34 多项式相加 void AddPolyn (Polynomial &Pa, Polynomial &Pb) { //多项式加法：Pa = Pa + Pb，利用两个多项式的结点构成“和多项式”。 ha = GetHead (Pa); //ha和hb分别指向Pa和Pb的头结点 hb = GetHead (Pb); qa = NextPos (Pa, ha); //qa和qb分别指向Pa和Pb中当前结点 qb = NextPos (Pb, hb); while (qa && qb) { //qa和qb均非空 a = GetCurElem (qa); //a和b为两表中当前比较元素 b = GetCurElem (qb); switch (*cmp(a, b)) { case -1: //多项式PA中当前结点的指数值小 ha = qa; qa = NextPos (Pa, qa); break; case 0: //两者的指数值相等 sum = a.coef + b.coef; if (sum != 0.0) { //修改多项式PA中 //当前结点的系数值 SetCurElem (qa, sum); } 算法2.15如下：

35 else { //删除多项式PA中当前结点 DelFirst (ha, qa); FreeNode (qa); } DelFirst (hb, qb); FreeNode (qb); qb = NextPos (Pb, hb); qa = NextPos (Pa, ha); break; case 1: //多项式PB中当前结点的指数值小 InsFirst (ha, qb); ha = NextPos (Pa, ha); } //switch } //while if (!ListEmpty (pb)) Append (Pa, qb); //链接Pb中剩余结点 FreeNode (hb); //释放Pb的头结点 } //AddPolyn

36 两个一元多项式相乘的算法，可以利用两个一元多项式相加的算法来实现，
因为乘法运算可以分解为一系列的加法运算。假设A(x)和B(x)为多项式： 则：M(x) = A(x) × B(x) = A(x) × = 其中每一项都是一个一元多项式。