第2章 线性表3

1、12.1 线性表的逻辑结构线性表的逻辑结构2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 一元多项式的表示一元多项式的表示22.3 线性表的链式表示和实现特点：用一组地址特点：用一组地址任意任意的存储单元存放线性表中的数的存储单元存放线性表中的数据元素。据元素。（地址可以是连续的，也可以不连续）（地址可以是连续的，也可以不连续）一一. 单链表单链表指针域指针域(next)(next)数据域数据域(data)(data)32.3 线性表的链式表示和实现特点：用一组地址特点：用一组地址任意任意的存储单元存放线性表中的数的存储单元存放线

2、性表中的数据元素。据元素。（地址可以是连续的，也可以不连续）（地址可以是连续的，也可以不连续）一一. 单链表单链表数据域数据域(存储存储数据元素数据元素信息的域信息的域) +指针域指针域(存储存储直接后继直接后继存储位置的域存储位置的域) = 结点结点 (表示数据元素的表示数据元素的存储映象存储映象)指针域指针域(next)(next)数据域数据域(data)(data)4a1ana25ZHAOQIANSUNLIZHOUWUZHENGWANGH例例:线性表线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域数据域指针域指针域LI

3、QIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针6头结点头结点: :在单链表在单链表第一个结点前第一个结点前附设一个结点叫附设一个结点叫头结头结点点。令令头结点头结点中中指针域指针域的指针指向的指针指向第一个元素第一个元素结点，并结点，并令令头指针头指针指向指向头结点头结点。通常称这类单链表为通常称这类单链表为 带头结点的单链表带头结点的单链表 。a1an a2头结点头结点指针域指针域为为空，空，表示线性表为表示线性表为空表空表。7头结点头结点 a1 a2 . an 头指针头指针头指针空指针空指针线性表为空表时，线性表为空表时，头结点的指针域

4、为空头结点的指针域为空 带头结点链表的引入是为了使带头结点链表的引入是为了使算法算法判空判空和和处理处理一致。一致。如果不特别声明的话，那么以后各节中讨论的单链如果不特别声明的话，那么以后各节中讨论的单链表都指的是这种表都指的是这种带头结点带头结点的链表。的链表。 8Typedef struct LNode ElemType data; / 数据域数据域 struct Lnode *next; / 指针域指针域 LNode, *LinkList; 二二. 结点和单链表的结点和单链表的 C 语言描述语言描述LinkList L； / L 为单链表的为单链表的头指针头指针9data nextp 表

5、示所指向结点占据内存段的表示所指向结点占据内存段的起始地址起始地址(*p)表示表示p所指向的所指向的结点结点(*p).data p-data表示表示p所指向结点的所指向结点的数据域数据域(*p).next p-next表示表示p所指向结点的所指向结点的指针域指针域101112三、单链表操作的实现三、单链表操作的实现GetElem(L, i, &e) / 取第取第i i个数据元素个数据元素ListInsert(&L, i, e) / 插入插入数据元素数据元素ListDelete(&L, i, &e) / 删除删除数据元素数据元素ClearList(&L) / 重置线性表为重置线性表为空表空表In

6、itList(&L ) / 初始化初始化 DestroyList(&L) / 销毁销毁线性表线性表13单链表初始化操作实现：单链表初始化操作实现：OVERFLOW三、单链表操作的实现三、单链表操作的实现14单链表销毁结构操作实现：单链表销毁结构操作实现：/销毁以销毁以L为头指针为头指针的单链表，释放链表中的单链表，释放链表中所有结点空间所有结点空间L所指结点的所指结点的指针域指针域内容赋值给内容赋值给L.即即L指向指向L的后继结点的后继结点.为安全起见，置为安全起见，置L为为 “空空”，以防止对系统空间的访问。以防止对系统空间的访问。 15操作 ClearList(&L) 的实现：void C

7、learList(&L) / 将单链表置为一个将单链表置为一个空表空表/ 从从第第1个结点个结点开始依次删除开始依次删除 while (L-next) p=L-next; L-next=p-next; delete p; / free(p); / ClearList算法时间复杂度为算法时间复杂度为: O( ListLength(L) )p所指结点的所指结点的指针域指针域内容内容赋值给赋值给L的指针域。的指针域。即即L的指针域的指针域指向指向p的的后后继继结点结点.16线性表的操作 GetElem(L, i, &e) 的实现：例：查找第3个元素L211830754256pppj1 2 33017

8、查找第查找第 i 个数据元素的基本操作为：个数据元素的基本操作为：移动指针移动指针p，比，比较较 j 和和 i 。 单链表是一种单链表是一种顺序存取顺序存取的结构，整个链表的存取必的结构，整个链表的存取必须须从头指针从头指针开始进行，为找第开始进行，为找第 i 个数据元素，必须先个数据元素，必须先找到第找到第 i-1 个数据元素。个数据元素。因此，不论因此，不论 i 为多少，都必须为多少，都必须从头结点从头结点开始开始“点数点数”， 一直数到第一直数到第 i 个为止。个为止。头结点头结点可看成是可看成是第第0个结点个结点。单链表是单链表是非随机存储非随机存储的结构。的结构。令指针令指针 p 始

9、终指向始终指向线性表中线性表中第第 j 个个数据元素。数据元素。18Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素 p = L-next; j = 1; / p指向第一个结点，指向第一个结点，j为计数器为计数器 while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p 指向第指向第 i 个元素或个元素或 p 为空为空 if ( !p | ji ) return ERROR; / 第第 i 个元素不存在个元素不存

10、在 e = p-data; / 取得第取得第 i 个元素个元素 return OK; / GetElem_L基本操作：比较基本操作：比较i和和j并后移指针并后移指针p算法时间复杂度为算法时间复杂度为: O( ListLength(L) )19ai-1线性表的操作 ListInsert(&L, i, e) 的实现：加工型操作，修改对象的加工型操作，修改对象的逻辑结构逻辑结构；逻辑结构逻辑结构 变为变为 和和 ；在单链表中，意味着一个指针变为两个指针。在单链表中，意味着一个指针变为两个指针。 eaiai-120因此，在单链表中第因此，在单链表中第 i 个结点之前进行插入的个结点之前进行插入的基本操

11、基本操作作为：找到线性表中为：找到线性表中第第i-1个个结点，然后结点，然后修改修改其指向其指向后后继继的指针。的指针。可见，为插入数据元素可见，为插入数据元素e，首先要生成一个，首先要生成一个数据域为数据域为e的结点的结点，然后插入在单链表中。，然后插入在单链表中。在链表中在链表中插入结点插入结点只需要只需要修改指针修改指针。但同时，若要。但同时，若要在在第第 i 个结点个结点之前插入元素，修改的是之前插入元素，修改的是第第 i-1 个结点个结点的的指针。指针。21Status ListInsert_L(LinkList &L, int i, ElemType e) / L 为带头结点的单链

12、表的头指针，为带头结点的单链表的头指针，/ 在第在第 i 个结点之前插入新的数据元素个结点之前插入新的数据元素 e p = L; j = 0; while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点 if (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 s = (LinkList) malloc (sizeof (LNode); / 生成新结点生成新结点 s （空结点）（空结点） s = new LNode; （C+） If(!s) exit(OVERFLOW);/存储分配失败存储分配失败（下页）（下页）22 s-

13、data = e; / 为新结点为新结点 s 赋值赋值(e) s-next = p-next; / 修改新结点修改新结点 s 指针指针 p-next = s; / 插入新结点插入新结点 s return OK; / ListInsert_L算法时间复杂度为算法时间复杂度为: O( ListLength(L) ) eai-1aiai-1sp23线性表的操作 ListDelete (&L, i, &e) 的实现：加工型操作加工型操作，修改对象为，修改对象为逻辑结构；逻辑结构；逻辑结构逻辑结构 和和 改变为改变为 ；在单链表中，意味着两个指针变为一个指针。在单链表中，意味着两个指针变为一个指针。ai

14、-1aiai+1ai-124删除一个结点，删除一个结点，删除结点数据元素删除结点数据元素的同时，还要的同时，还要删除删除该结点的指针该结点的指针。但是，不能因为结点的删除造成单链表的但是，不能因为结点的删除造成单链表的脱节脱节，所以，所以，删除操作的关键在于单链表删除操作的关键在于单链表内部关系的调整内部关系的调整。在单链表中删除第在单链表中删除第 i 个结点的个结点的基本操作基本操作为：为：找到线性找到线性表中第表中第i-1个结点个结点，修改其指向，修改其指向后继后继的指针。的指针。25ai-1aiai+1ai-1pqq = p-next; p-next = q-next; e = q-da

15、ta; delete q;26Status ListDelete_L(LinkList &L, int i, ElemType &e) / 删除以删除以 L 为头指针为头指针(带头结点带头结点)的单链表中第的单链表中第 i 个结点个结点 p = L; j = 0; while(p-next & j next; +j; / 寻找第寻找第 i 个结点，并令个结点，并令 p 指向其前趋指向其前趋(ai-1) if (!(p-next) | j i-1) return ERROR; / 删除位置不合理删除位置不合理 q = p-next; p-next = q-next; / 修改指针修改指针 e =

16、 q-data; delete q; / free(q);(C+) 释放结点释放结点 return OK; / ListDelete_L算法时间复杂度为算法时间复杂度为: O( ListLength(L) )27链表是一个链表是一个动态的结构动态的结构，它不需要预分配连续的存储，它不需要预分配连续的存储空间，因此生成链表的过程是一个空间，因此生成链表的过程是一个结点结点“逐个插入逐个插入” 的过程。的过程。【例】逆位序输入【例】逆位序输入 n 个数据元素的值，建立带头结点的个数据元素的值，建立带头结点的单链表。单链表。28操作步骤：操作步骤：1. 建立一个空表；建立一个空表；2. 输入数据元素

17、输入数据元素an，建立结点并插入；建立结点并插入；3. 输入数据元素输入数据元素an-1，建立结点并插入；建立结点并插入；ananan-14. 依次类推，直至输入依次类推，直至输入a1为止。为止。29void CreateList_L(LinkList &L, int n) /C+版版/ 逆序输入逆序输入 n 个数据元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 L = new LNode; if (!L) exit(1); L-next = NULL; / 先建立一个带头结点的单链表先建立一个带头结点的单链表 for (i = n; i 0; -i) p = new LNode;

18、 if (!p) exit(1); / 创建结点创建结点 cin p-data; / 输入数据元素值输入数据元素值 p-next = L-next; L-next = p; / 插入结点插入结点 / CreateList_L算法时间复杂度为算法时间复杂度为: O( ListLength(L) )30void CreateList_L(LinkList &L, int n) /C版版/ 逆序输入逆序输入 n 个数据元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一个带

19、头结点的单链表先建立一个带头结点的单链表 for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); / 创建结点创建结点 scanf(&p-data); / 输入数据元素值输入数据元素值 p-next = L-next; L-next = p; / 插入结点插入结点 / CreateList_L算法时间复杂度为算法时间复杂度为: O( ListLength(L) )3132分析：分析：设设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且已由且

20、已由(a1, , ai-1)和和(b1, ,bj-1)归并得归并得 (c1, , ck-1)则则 jijjiikbabbaack = 1, 2, , m+n33/已知单链线性表已知单链线性表 La 和和 Lb 的元素按值非递减排列。的元素按值非递减排列。 /本算法归并本算法归并 La 和和 Lb 得到新的单链线性表得到新的单链线性表 Lc， Lc /的元素也按值非递减排列。操作之后的元素也按值非递减排列。操作之后 La 和和 Lb 消失消失/ 建空表，建空表，Lc 为头指针，为头指针，rc指示指示 Lc 表当前的表尾表当前的表尾 /pa和和pb分别指向分别指向La表和表和Lb表中第一个结点。表

21、中第一个结点。34/ 将将 *pa 插入插入Lc表，指针表，指针 pa 后移后移/ if/ 将将 *pb 插入插入Lc表，指针表，指针 pb 后移后移/ else/ while/ 插入剩余段插入剩余段/释放释放La和和Lb的头结点的头结点/ MergeList_L35单链表优点：单链表优点：(1) 能能有效利用有效利用存储空间；存储空间；(2) 用用“指针指针”指示数据元素之间的后继关系，便于进行指示数据元素之间的后继关系，便于进行“插入插入”、“删除删除”等操作。等操作。单链表缺点：单链表缺点：(1)不能随机存取不能随机存取数据元素数据元素 ；(2)它还丢失了一些顺序表有的长处，如线性表的它

22、还丢失了一些顺序表有的长处，如线性表的“表长表长”（单链表中表长是一个隐含值，必须从前到后遍历整（单链表中表长是一个隐含值，必须从前到后遍历整个表才能得到）个表才能得到）和数据元素在线性表中的和数据元素在线性表中的“位序位序”；(3)不便于在表尾插入元素不便于在表尾插入元素，需遍历整个表才能找到插入，需遍历整个表才能找到插入的位置。的位置。 36【例【例2-1】假设】假设:有两个集合有两个集合 A 和和 B 分别用两个线性表分别用两个线性表 LA 和和 LB 表示。现求一个新的集合表示。现求一个新的集合AAB。void union(List &La, List Lb) La_len = Lis

23、tLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); if (!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e); /for / union控制结构：控制结构：基本操作：基本操作：GetElemLocateElemListInsertfor 循环循环37void union( SqList &la, SqList lb) la_len=la.length; lb_len=lb.length;bool find=false;for( int i=0;i=lb_len-1;i+) for( int j=0;jnext; LNode * pre=lb;while(q) p=la-next;while(p) if(q-data= =p-data) break; else p=p-next;if(!p) pre-next=q-next; q-next=la-next; la-next=q; else pre=q; q=pre-next;当以当以链式映像链式映像实现抽象数据类型线性表时为实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) )单单链链