数据结构第二章线性表

1、第第1 1章章 绪论绪论第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列 第第4 4章章 串串第第5 5章章 数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树 第第7 7章章 图图第第9 9章章 查找查找第第1010章章 排序排序目目 录录什么是什么是线性结构？线性结构？线性结构的定义线性结构的定义若结构是非空有限集，则有且仅有一个开始结点和一个终端结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（可表示为：（a a1 1 , a, a2 2

2、, , a, , an n） 简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个直除首尾结点外，其他结点只有一个直接前驱和一个直接后继。接后继。一对一一对一 (1:1)线性结构的逻辑类型线性结构的逻辑类型线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、线性表、堆栈、队列、字符串、数组数组等，其中最典型、最常用的是等，其中最典型、最常用的是-2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和实现（重线性表的顺序表示和实

3、现（重点）点）2.3 2.3 线性表的链式表示和实现（重点）线性表的链式表示和实现（重点）2.4 2.4 应用举例应用举例（a1, a2, ai-1，ai, ai1 ，, an）用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点2.1 线性表的逻辑结构 （ A, B, C, D, , ZA, B, C, D, , Z）分析：分析： 数据元素都是同类型（

4、数据元素都是同类型（字母字母），）， 元素间关系元素间关系是线性的。是线性的。例例1 1 分析分析26 26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。学号姓名性别年龄班级012003010622陈建武男 192003级电信0301班012003010704赵玉凤女 182003级电信0302班012003010813王 泽男 192003级电信0303班012003010906薛 荃男 192003级电信0304班012003011018王王 春春男男 192003级电信0305班： ：分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素之间关系是线

5、性的。），元素之间关系是线性的。1 1、“同一数据逻辑结构中的所有数据元素都具有相同一数据逻辑结构中的所有数据元素都具有相同的特性同的特性”是指数据元素所包含的是指数据元素所包含的数据项的个数数据项的个数都都相等。相等。试判断下列叙述的正误试判断下列叙述的正误2、线性结构就是线性表、线性结构就是线性表 线性表的物理结构类型线性表的物理结构类型 顺序存储结构与链式存储结构顺序存储结构与链式存储结构 在确定线性表物理结构的基础上，可以进行相关在确定线性表物理结构的基础上，可以进行相关的操作和编程，用函数实现。的操作和编程，用函数实现。逻辑结构是抽象的，独立于计算机的，无法进行具逻辑结构是抽象的，独

6、立于计算机的，无法进行具体的计算；体的计算；物理结构是具体的，包括顺序结构与链式结构，决物理结构是具体的，包括顺序结构与链式结构，决定了数据对象如何实现具体的运算。定了数据对象如何实现具体的运算。 例如数组与单链表就是两种不同的物理结构，在插例如数组与单链表就是两种不同的物理结构，在插入与删除操作时具体实现不一样入与删除操作时具体实现不一样2.2.1 2.2.1 顺序表的表示顺序表的表示2.2.2 2.2.2 顺序表的实现顺序表的实现2.2.3 2.2.3 顺序表的运算效率分析顺序表的运算效率分析用一组用一组地址连续地址连续的存储单元依次存的存储单元依次存储线性表的元素。储线性表的元素。把逻辑

7、上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像。或顺序映像。顺序存储方法：顺序存储方法：特点：特点： 逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-1顺序存储定义：顺序存储定义：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素

8、，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组元素存放位置亦可求出（利用数组an的下标）。的下标）。线性表顺序存储特点线性表顺序存储特点设首元素设首元素a a1 1的存放地址为的存放地址为LOC(aLOC(a1 1) )（称为首地址），设每个元称为首地址），设每个元素占用存储空间（地址长度）为素占用存储空间（地址长度）为L L字节，字节，则表中任一数据元素则表中任一数据元素的存放地址为：的存放地址为： LOC ( aLOC ( ai+1 i+1 ) = LOC( a) = LOC( ai i ) + L )

9、 + L 对上述公式的解释如图所示对上述公式的解释如图所示线性表顺序存储特点线性表顺序存储特点a1a2aiai+1an 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L线性表的顺序存储结构示意图线性表的顺序存储结构示意图设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数组元，每个数组元素用相邻的素用相邻的4 4个字节个字节存储。存储器按字节编址，设存储存储。存储器按字节编址，设存储数

10、组元素数组元素 的第一个字节的地址是的第一个字节的地址是，则，则 的第一个字节的地址是多少？的第一个字节的地址是多少？110但此题要注意下标起点略有不同：但此题要注意下标起点略有不同：LOC( M3 ) = 98 + 4 (4-1) =110解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）例例1 1 char V30;void build() /*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心语句：核心语句：法法1 Vi= Vi-1

11、+1;法法2 Vi=a+i;法法3 Vi=97+i;例例2 2 顺序表的操作顺序表的操作用数组用数组V V来存放来存放2626个英文字母组成的线性表（个英文字母组成的线性表（a a，b b，c c，z z），写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C C语言程序。语言程序。void main(void) /*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/ n=26; /* n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build( );display( );void display( ) /*

12、字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/ int i;for( i=0; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一个位置元素后移一个位置/ / 插入插入x x / / 表长加表长加1 1 核核心心语语句句2)2)插入插入在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242830427712345678123456789插入插入实现步骤：实现步骤：将第将第i+1i+1 至第至第n n 位的元素位的元素向前向前移动一个位置；移动一个位置；表长减表

13、长减1 1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i i 是否合法是否合法? ?应当有应当有1in 1in 或或 i=1, ni=1, n删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for ( j=i+1; j=1)i (i=1)位前位前 插入插入一个元素，则向后移动元素的次数一个元素，则向后移动元素的次数f(n)f(n)为为: :f(n) =f(n) = n i + 1推导：推导：假定在每个元素位置上插入假定在每个元素位置上插入x x的可能性都一样（即的可能性都一样（即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间

14、：若在首结点前插入，需要移动的元素最多，后移若在首结点前插入，需要移动的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1n-1; ;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1个元素；个元素；若在尾结点若在尾结点a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计：所有可能的元素移动次数合计： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/2故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2n(n+1)/2（n+1

15、n+1）n/2n/2 共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种! !2.2.3 2.2.3 顺序表的运算效率分析顺序表的运算效率分析讨论讨论2 2 删除元素删除元素同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T T（n)=(n-1)/2 n)=(n-1)/2 2.2.3 2.2.3 顺序表的运算效率分析顺序表的运算效率分析顺序表插入、删除算法的顺序表插入、删除算法的平均平均空间空间复杂度复杂度为多少？为多少？插入效率：插入效率：删除效率：删除效率：11111(1)(1)12nnisiiinEp ninin 1111()()

16、2nndliiinEq ninin因为没有因为没有占用辅助占用辅助空间！空间！含义：对于顺序表，含义：对于顺序表，插入、删除操作平均需要插入、删除操作平均需要移动一半元素移动一半元素( n / 2 )O(1)O(1)即插入、删除算法的平均即插入、删除算法的平均时间复杂度为时间复杂度为 O(n)2.2.3 2.2.3 顺序表的运算效率分析顺序表的运算效率分析1 1、顺序表的、顺序表的“宏观宏观”算法该如何书写？算法该如何书写？采用采用抽象数据类型抽象数据类型来表示来表示2 2、顺序表的存储结构是一维数组，如果插入的元素、顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？个数

17、超过数组定义的长度怎么办？采用采用动态分配动态分配的一维数组的一维数组 初始化、撤销、清空、判空；初始化、撤销、清空、判空； 求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继； 读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历； 插入、删除插入、删除线性表的定义线性表的定义（见教材（见教材P19P19）ADT ADT ListList 数据对象：数据对象：D=D=a ai i | a| ai iElemSet, i=1,2,n,n0ElemSet, i=1,2,n,n0数据关系：数据关系：R1=R1= a | a | ai 1i 1, a, ai i D, i=2,n

18、D, i=2,n基本操作：基本操作： ADT ListInitList( &L ); /建空表，初始化建空表，初始化DestoryList( &L ); /撤销表，释放内存撤销表，释放内存int LengthList( L ); /求表中元素个数，即表长求表中元素个数，即表长POSITION LocateElem (L,ElemType e，compare() );PriorElem( L, cur_e, &pre_e ); /求当前元素求当前元素e的前驱的前驱NextElem( L, cur_e, &next_e ); /求当前元素求当前元素e的后继的后继Li

19、stInsertBefore(&L, i, e ); /把把e插入到第插入到第i个元素之前个元素之前ListDelete( &L, i,&e ); /删除第删除第i个元素并个元素并“看看”此元素此元素ListTraverse( L, Visit() ); / “看看”表中全部元素（遍历）表中全部元素（遍历）l初始化、撤销、清空、判空；初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；l插入、删除插入、删除顺序表操作的典型例子顺序表操作的典型例子教材教材例例2-12-1

20、：求两个线性表的：求两个线性表的“并并”，即：，即：LA U LB = ?LA U LB = ?算法至少有两种：算法至少有两种： LALA和和LBLB都是都是无序表无序表，则从，则从LBLB中取元素逐一与中取元素逐一与LALA中所有元素比较，相同则不插入中所有元素比较，相同则不插入LALA； 若若LALA和和LBLB已经是已经是有序表有序表，则，则“归并归并”的时间的时间效率可以大大提高。效率可以大大提高。 先为顺序表空间设定一个初始分配量，一旦因插入元素而先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足空间不足时，可为顺序表增加一个时，可为顺序表增加一个固定长度的空间增量固定长度的

21、空间增量。#define LIST_INIT_SIZE 100 /存储空间存储空间的初始分配量的初始分配量#define LISTINCREMENT 10/存储空间的分配增量存储空间的分配增量typedef struct ElemType *elem; /表基址表基址( (用指针用指针*elemelem表示表示） int length; /表长度表长度（表中有多少个元素表中有多少个元素） int listsize; /当前分配的表尺寸当前分配的表尺寸（字节单位字节单位）SqList;注：三个分量可简写为：注：三个分量可简写为：L L.elem .elem L L.length .length

22、L L.listsize.listsize存储结构描述如下（存储结构描述如下（见教材见教材P22P22）：）：为什么不用为什么不用数组数组sizeof(x)sizeof(x)算符的意思是：算符的意思是：计算变量计算变量x x的长度的长度( (字节数字节数) )malloc (m)函数的意思是：新开函数的意思是：新开一片大小为一片大小为m字节字节的连续空间，的连续空间，并把该区首址作为函数值。并把该区首址作为函数值。Status InitList_Sq( SqList &L ) /创建一个空线性表创建一个空线性表 L.elem=(ElemType*)malloc(LIST_INIT_SI

23、ZE * sizeof(ElemType); If(!L.elem) exit(OVERFLOW); /分配失败，结束程序分配失败，结束程序 L.length=0; /暂无元素放入，空表暂无元素放入，空表 L.listsize=LIST_INIT_SIZE; /表尺寸表尺寸=初始分配量初始分配量 Return OK; /InitList_Sq动态创建一个空顺序表的算法动态创建一个空顺序表的算法realloc (realloc (* *p p, , newsizenewsize) )函数的意思是：新开一函数的意思是：新开一片大小为片大小为newsizenewsize的连续空间，并把以的连续空间，

24、并把以* *p p为为首址的原空间数据都拷贝进去。首址的原空间数据都拷贝进去。动态顺序表的插入算法动态顺序表的插入算法Status ListInsert_Sq(SqList &L, int i, ElemType e) /在顺序线性表中第在顺序线性表中第i个位置之前插入新的元素个位置之前插入新的元素eif( i L.length+1) return ERROR; / 检验检验i 值的合法性值的合法性 if ( L.length L.listsize ) /若表长超过表尺寸则要增加尺寸若表长超过表尺寸则要增加尺寸 newbase = ( ElemType* ) realloc ( L.e

25、lem , (L.listsize )* sizeof ( ElemType ) );if (newbase=NULL ) exit( OVERFLOW ) ; /分配失败则退出并报错分配失败则退出并报错 L.elem = newbase ; /重置新基址重置新基址 L.listsize = L.listsize ; /增加表尺寸增加表尺寸 q = &L.elemi-1 ; / q为插入位置指针为插入位置指针 for ( p = &L.elemL.length-1 ; p=q ; -p ) *(p+1) = *p ; /插入位置及之后的元素统统后移插入位置及之后的元素统统后移,

26、 p为元素位置为元素位置 *q= e ; /插入插入e +L.length ; /增加增加1个数据元素，则表长个数据元素，则表长+1 return OK ; /ListInsert_Sq动态数组的核心是realloc(void *ptr, newsize)函数！for (int k=L.length-1; k=i-1;k-) L.elemk+1=L.elemk;Status ListDelete_Sq(SqList &L, int i, ElemType &e) /在顺序表在顺序表L中删除第中删除第 i 个元素，用个元素，用 e 返回其值返回其值 if (i L.length)

27、 return ERROR; / i 值不合法，返回值不合法，返回 p=&L.elemi-1; / p 是被删除元素的位置是被删除元素的位置 e=*p; /被删除元素的值赋给被删除元素的值赋给 e q=L.elem+L.length-1; / q 是表尾的位置是表尾的位置 for(+p; pdata=; p-next= ; 方式方式3： p指向结点首地址，然后指向结点首地址，然后 (*p).data=； (*p).nextb设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针, ,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习

28、：p-dataai的值的值p-nextai+1的地址的地址附附1 1：介绍介绍C C的三个有用的库函数的三个有用的库函数/ /算符（都在算符（都在 中）：中）：sizeof(sizeof(x x) )计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(malloc(mm) ) 开辟开辟mm字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(free(p p) ) 释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。sizeof(x)计算x的长度malloc(m) 开m字节空间fr

29、ee(p) 删除一个变量问问1：自定义结构类型变量自定义结构类型变量node的长度的长度m是多少？是多少？问问2：结构变量结构变量node的首地址的首地址(指针指针p）是多少？）是多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长度为m字节字节pmsizeof(node) /单位是字节单位是字节p(node*)malloc(m)free(p) /只能借助只能借助node的指针删除！的指针删除！P-data=P-data=a a; p-next=q; p-next=q练习：练习： 类型定义和变量说明可以合写为：类型定义和变量说明可以合写为： LinkLi

30、st /LinkList是自定义结构类型名称是自定义结构类型名称 char data; /定义数据域的变量名及其类型定义数据域的变量名及其类型 LinkList *next; /定义指针域的变量名及其类型定义指针域的变量名及其类型node，*pointer; /node是是LinkList结构类型的类型替代结构类型的类型替代, *pointer是指针型的是指针型的LinkList结构类型的替代，也是数据类型结构类型的替代，也是数据类型*/ 对于指向结构类型的指针变量，可说明为：对于指向结构类型的指针变量，可说明为： *p, *q; /或用或用 struct *p , *q; pointer p

31、,q;/注：上面已经定义了注：上面已经定义了node为用户自定义的为用户自定义的LinkList类型。类型。单链表的抽象数据类型描述如下单链表的抽象数据类型描述如下（参见教材（参见教材P28P28）：typedef struct Lnode ElemType data; /数据域数据域 struct Lnode *next; /指针域指针域Lnode, *LinkList; / *LinkList为为Lnode类型的指针类型的指针至此应可看懂教材至此应可看懂教材P22P22关于顺序表关于顺序表动态分配动态分配的存储结构。的存储结构。其特点是：用结构类型和指针来表示顺序结构，更灵活。其特点是：用

32、结构类型和指针来表示顺序结构，更灵活。如何具体编程来建立如何具体编程来建立和访问链表？和访问链表？链表的实现链表的实现typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 教材P28P28对于线性表的单链表存储结构描述:Q1Q1：第一行的第一行的Lnode Lnode 与最后一行的与最后一行的LnodeLnode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LnodeLnode是结构名，后者是结构名，后者LnodeLnode是对整个是对整个structstruct类型的一种类型的一种“缩写

33、缩写”，是一种，是一种“新定义名新定义名”，它只是，它只是对现有类型名的补充，而不是取代。对现有类型名的补充，而不是取代。请注意：请注意：typedeftypedef不可能创造任不可能创造任何新的数据类型，而仅仅是在何新的数据类型，而仅仅是在原有的数据类型中命名一个新原有的数据类型中命名一个新名字，其目的是使你的程序更名字，其目的是使你的程序更易阅读和移植。易阅读和移植。typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; Q2Q2： 那为何两处要同名那为何两处要同名(Lnode(Lnode和和Lno

34、deLnode）？太不严谨了吧？）？太不严谨了吧？A2A2：同名是为了表述起来方便。例如，若结构名为同名是为了表述起来方便。例如，若结构名为studentstudent，其新定义名缩写也最好写成其新定义名缩写也最好写成studentstudent，因为描述的对象相同，因为描述的对象相同，方便阅读和理解。方便阅读和理解。Q3Q3：结构体中间的那个：结构体中间的那个structstruct LnodeLnode是何意？是何意？A3A3：在：在“缩写缩写” LnodeLnode还没出现之前，只能用原始的还没出现之前，只能用原始的struct Lnodestruct Lnode来进行变量说明。此处说明

35、了指针分量的数来进行变量说明。此处说明了指针分量的数据类型是据类型是structstruct LnodeLnode。typedef struct student char name; int age; student,*pointer; 教材问题讨论：教材问题讨论：2.3.1 2.3.1 链表的表示链表的表示2.3.2 2.3.2 链表的实现链表的实现2.3.3 2.3.3 链表的运算效率分析链表的运算效率分析（1 1） 单链表的建立和输出单链表的建立和输出（2 2） 单链表的修改单链表的修改（3 3） 单链表的插入单链表的插入（4 4） 单链表的删除单链表的删除例：用例：用单链表单链表结构来

36、存放结构来存放2626个英文字母组成的线性表（个英文字母组成的线性表（a a，b b，c c，z z）, ,请写出请写出C C语言程序。语言程序。算法实现思路：算法实现思路：先开辟头指针，然后陆续为每个结点开辟先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要存储空间并及时赋值，后继结点的地址要提前提前送给前面的送给前面的指针。指针。先挖先挖“坑坑”, ,后种后种“萝萝卜卜”！typedef struct nodetypedef struct nodechar data; char data; struct node struct node * *next;next;no

37、de; node; node node * *p,p,* *q,q,* *head; /head; /一般需要一般需要3 3个指针变量个指针变量int n ; / int n ; / 数据元素的个数数据元素的个数int m=sizeof(node); int m=sizeof(node); / /* *结构类型定义好之后，每个变量的结构类型定义好之后，每个变量的长度就固定了，长度就固定了，mm求一次即可求一次即可* */ /将全局变量及函数提前说明：将全局变量及函数提前说明：新手特别容易忘记！新手特别容易忘记！ int i; int i;head=(nodehead=(node* *)mall

38、oc(m); /m=sizeof(node) )malloc(m); /m=sizeof(node) 前面已求出前面已求出p=head;p=head;for( i=1; i26; i+) /for( i=1; idata=i+ p-data=i+a a-1; / -1; / 第一个结点值为字符第一个结点值为字符a ap-next=(nodep-next=(node* *)malloc(m); /)malloc(m); /为后继结点为后继结点“挖坑挖坑”！p=p-nextp=p-next； / /让指针变量让指针变量P P指向后一个结点指向后一个结点p-data=i+p-data=i+a a-1

39、; /-1; /最后一个元素要单独处理最后一个元素要单独处理p-next=NULL ; /p-next=NULL ; /单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void build( ) /字母链表的生成字母链表的生成。要一个个慢慢链入要一个个慢慢链入如何建立带头结点的单链表如何建立带头结点的单链表（1）创建单链表）创建单链表p=head;while (p) /当指针不空时循环，仅限于当指针不空时循环，仅限于无头结点无头结点的情况的情况 printf(%c,p-data); p=p-next; /让指针不断让指针不断“顺藤摸瓜顺藤摸瓜” 讨论：要统计链表中数据元素的个数，该如何

40、改写？讨论：要统计链表中数据元素的个数，该如何改写？ sum+;sum+;sum=0;sum=0;void display() /void display() /* *字母链表的输出字母链表的输出* */ /（2）单链表元素值显示）单链表元素值显示思路：思路：要修改第要修改第i i个数据元素，必须从头指针起一直找到该结个数据元素，必须从头指针起一直找到该结点的指针点的指针p p，然后才能执行，然后才能执行p-data=new_value p-data=new_value 。修改修改第第i i个数据元素的操作函数可写为：个数据元素的操作函数可写为：Status GetElem_L(LinkLis

41、t L, int i, ElemType &e)p=L-next; j=1; /带头结点的链表带头结点的链表while(p&jnext; +j;if( !p ji ) return ERROR; p-data =e; /若是读取则为：若是读取则为：e=p-data; return OK;/ GetElem_L缺点：缺点：想寻找单链表中第想寻找单链表中第i i个元素，只能从头指针开始逐一个元素，只能从头指针开始逐一查询（查询（顺藤摸瓜顺藤摸瓜），无法随机存取），无法随机存取 。在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xsabp链表插入的核心

42、语句：链表插入的核心语句：p-nexts-nextX X 结点的生成方式：结点的生成方式：s=(node*)malloc(m);s-data=X X ;s-next= ?bapX X 在链表中删除某元素在链表中删除某元素b b的示意图如下：的示意图如下：c a bp删除动作的核心语句删除动作的核心语句（要借助辅助指针变量（要借助辅助指针变量q q）：）：q = p-next; /首先保存首先保存b b的指针，靠它才能找到的指针，靠它才能找到c c；p-next=q-next; /将将a a、c c两结点相连，淘汰两结点相连，淘汰b b结点；结点；free(q) ； /彻底释放彻底释放b b结点

43、空间结点空间p-next思考：思考： 省略省略free(q)free(q)语句行不行？语句行不行？(p-next) - nextq（1 1） 查找查找 因线性链表只能顺序存取，即在查找时要从头指针找起，因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为查找的时间复杂度为 O(n)O(n)。时间效率分析时间效率分析（2 2） 插入和删除插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为间复杂度为 O(1)O(1)。但是，如果要在单链表中进行前插或删除操作，因为要但是，如果要在单链表中进行前插或删除操作，

44、因为要从头查找前驱结点，所耗时间复杂度将是从头查找前驱结点，所耗时间复杂度将是 O(n)O(n)。空间效率分析空间效率分析链表中每个结点都要增加一个指针空间，相当链表中每个结点都要增加一个指针空间，相当于总共增加了于总共增加了n n 个整型变量，空间复杂度为个整型变量，空间复杂度为 O(n)O(n)。在在n n个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点* *P P，需找到它，需找到它的的 ，其时间复杂度为，其时间复杂度为O(n)O(n)练习：练习：算法要求：算法要求：已知：线性表已知：线性表 A A和和B B，分别由单链表，分别由单链表 LaLa和和Lb Lb 存储，其中数存

45、储，其中数据元素按值非递减有序排列（即已经有序）；据元素按值非递减有序排列（即已经有序）；要求：将要求：将A A和和B B归并为一个新的线性表归并为一个新的线性表C , CC , C的数据元素仍的数据元素仍按值非递减排列。设线性表按值非递减排列。设线性表C C由单链表由单链表 Lc Lc 存储。存储。假设：假设：A=A=（3 3，5 5，8 8，11 11），），B=B=（2 2，6 6，8 8，9 9，11 11）预测：合并后的预测：合并后的C =C =（2, 3, 5, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，11 11）例例1 1：两个链表的归并两个链

46、表的归并（教材教材P31P31例例）重点是链表重点是链表 3 511 / 8 LaLa 2 611 / 8 LbLb 9 2 3 6 5 LcLc 8 811 / 911头结点头结点算法主要包括搜索、比较、插入三个操作：算法主要包括搜索、比较、插入三个操作：搜索：需要设立三个指针来指向搜索：需要设立三个指针来指向La La 、LbLb和和LcLc链表；链表；比较：比较比较：比较LaLa和和LbLb表中结点数据的大小；表中结点数据的大小；插入：将插入：将LaLa和和LbLb表中数据较小的结点插入新链表表中数据较小的结点插入新链表Lc Lc 。请注意链表的特点，仅改变指针请注意链表的特点，仅改变指

47、针便可实现数据的移动便可实现数据的移动, ,即即“数据不动，指针动数据不动，指针动”La3 5 8 11 Lb2 6 8 119 PaPbPaPbPaPa、PbPb用于搜索用于搜索LaLa和和LbLb， PcPc指向新链表当前结点。指向新链表当前结点。归并过程示意如下：归并过程示意如下：Lc=LaPbPaPaPb算法设计算法设计typedef struct Lnode /结点类型结点类型 Elemtype data; struct Lnode *next; *linkList;typedef struct /链表类型链表类型 link head, tail; /分别指向链表头尾结点分别指向链表

48、头尾结点 int len; /链表中元素个数（长度）链表中元素个数（长度） link;结点的结点的结构结构表结构表结构算法实现：算法实现： Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /已知单链线性表已知单链线性表LaLa和和LbLb的元素按值非递减排列。归并为的元素按值非递减排列。归并为LcLc后也按值非递减排列。后也按值非递减排列。 free(Lb); /释放释放LbLb的头结点的头结点 /MergeList_L pc-next = pa pa: pb ; /插入非空表的剩余段插入非空表的剩余段

49、while(pa&pb) /将将pa pa 、pbpb结点按大小依次插入结点按大小依次插入Lc中中 if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=LaLa-next; pb=LbLb-next; Lc=pc=La； /有头结点有头结点见见P31P31算法算法2.122.12? ?是条件运算符（是条件运算符（为真则取第为真则取第1 1项，项，见见P10P10条件赋值条件赋值）思思 考考（举一反三）编程实践题（举一反三）编程实践题1 1、不用、不用LcLc，直接把，直

50、接把LaLa表插到表插到LbLb表中；或者把表中；或者把LbLb表插到表插到LaLa表中，怎么修改？表中，怎么修改？2 2、重复的数据元素不需要插入，怎么修改？、重复的数据元素不需要插入，怎么修改？ else if (pa-data=pb-data) pc-next=pa; pc=pa; pa=pa-next; pb=pb-next; 讨论讨论：1. 1.一元多项式的数学通式？一元多项式的数学通式？2.2.用抽象数据类型如何描述它的定义？用抽象数据类型如何描述它的定义？3.3.用用C C语言如何描述它的定义？语言如何描述它的定义？4.4.如何编程实现两个一元多项式相加？如何编程实现两个一元多项

51、式相加？但当多项式的次数但当多项式的次数很高很高且且零系数项很多零系数项很多时，更适于用链表存储。时，更适于用链表存储。021021.)(eememxaxaxaxAmm机内存储方式？机内存储方式？一般用一般用顺序存储顺序存储a0a1a2am-2am-1链式存储链式存储am-1 em-1am-2 em-2 a0 e0 或或0.0 -1 am-1 em-1 a0 e0通常设计通常设计两个数据域两个数据域（系数项和指数项）和（系数项和指数项）和一个指针域一个指针域头结点头结点只存系数项（但零系数项也不能遗漏）只存系数项（但零系数项也不能遗漏）coefexponlinkP2000(x)= 1+ 3x1

52、000 + 5x2000123814xxa610141038xxxb3 142 81 0a8 143 1010 6b例：例：运算规则运算规则：两多项式中两多项式中指数相同的项对应系数相加指数相同的项对应系数相加，若和不为若和不为0,0,则构成多项式则构成多项式c(=a+b)c(=a+b)中的一项；中的一项；a a和和b b中所中所有有指数不相同的项均应拷贝到指数不相同的项均应拷贝到c c中。中。链表链表a a：链表链表b b：依次比较依次比较PaPa和和PbPb所指结点中的指数项，依所指结点中的指数项，依Pa-expon Pa-expon =、Pb-exponPb-expon等情况，等情况，再

53、决定是将再决定是将两系数域的数值相加（并判其和是否为两系数域的数值相加（并判其和是否为0 0），还是将较高指），还是将较高指数项的结点插入到新表数项的结点插入到新表c c中。中。3 142 81 0 aPaPa8 14-3 1010 6 bPbPb11 14-3 102 81 0 cPcPc10 6+(1)(1)系数相加系数相加0 0 加法次数加法次数 min(m, n)min(m, n)其中其中 mm和和n n分别表示表分别表示表A A和表和表B B的结点数。的结点数。(2)(2)指数比较指数比较 极端情况是极端情况是表表A A和表和表B B 没有一项指数相同，比没有一项指数相同，比 较次数

54、最多为较次数最多为m+n-1 m+n-1 (3)(3)新结点的创建新结点的创建极端情况是产生极端情况是产生m + nm + n 个新结点个新结点合计时间复杂度为合计时间复杂度为 O(m+n)O(m+n)（参见（参见P40P40） Polynomial Polynomial 数据对象：数据对象：D=aD=ai i|a|ai iTermSet,i=1,2,TermSet,i=1,2,m, m0,m, m0TermSetTermSet中的中的每个元素包含每个元素包含一个表示系数的一个表示系数的实数实数和表示指数的和表示指数的整数整数 数据关系：数据关系：R1= aR1=| a| ai-1, i-1,

55、 a ai i D,D, 且且a ai-1i-1中的指数值中的指数值=b b的指数值，分别返回的指数值，分别返回-1,0,+1-1,0,+1ha=qa; qa=NextPos(Pa,ha); break; /a/a的指数值小则链接，说明是升序的指数值小则链接，说明是升序case 0: / 若若a a的指数值等于的指数值等于b b，则系数相加，但和为，则系数相加，但和为0 0时不要时不要sum=a.coef+b.coef;If(sum!=0.0)SetCurElem(qa,sum); ha=qa; 教材第教材第4343页的算法页的算法2.232.23多项式加法多项式加法 elseDelFirst

56、(ha,qa); FreeNode(qa);/若系数为若系数为0，则两结点都删，则两结点都删 DelFirst(hb,qb); FreeNode(qb); /ab，应先链接（前插），应先链接（前插）b（保持升序）保持升序）DelFirst(hb,qb); InsFirst(ha,qb); / 此二动作不要调换此二动作不要调换qb=NextPos(Pb,hb); ha=NextPos(Pa,ha); break; /a表结点大，后移表结点大，后移/switch/while /直到查完直到查完a表表If(!ListEmpty(Pb) Append(Pa,qb); / 若若b表还不空，则剩表全部表还

57、不空，则剩表全部/链接到链接到a表中；表中；b表空时无需动作，因为此时表空时无需动作，因为此时a表已求和完毕。表已求和完毕。FreeNode(hb); /无论什么结局，最终无论什么结局，最终b表都是要废掉的。表都是要废掉的。/ AddPolyn教材第教材第4343页的算法页的算法2.232.23多项式加法多项式加法分析分析：要想让要想让an指向指向a an-1n-1, ,a a2 2指向指向a a1 1，一般有两种算法：一般有两种算法：替替换换法法：扫描扫描a a1 1a an n, , 将每个将每个ai的指针域指向的指针域指向ai -1。实际上是链实际上是链栈的概念栈的概念a1heada2思

58、路：后继变前驱思路：后继变前驱思路：头部变尾部思路：头部变尾部插入插入法：法：扫描扫描a a1 1a an n, , 将每个将每个ai插入到链表首部即可插入到链表首部即可。例例3 3：试用试用C C或类或类C C语言编写一个语言编写一个高效高效算法，将一循环单链算法，将一循环单链表就地逆置。表就地逆置。 p=head-next; /有头结点有头结点if(p!=head)q=p-next; p-next =head;p=q; /处理处理a1while(p!=head) /循环单链表循环单链表 q=p -next /保存原后继保存原后继 p -next= head-next; head-next=

59、p; p=q; /准备处理下一结点准备处理下一结点q=head;p=head-next; /有头结点有头结点while(p!=head) /循环单链表循环单链表 r=p-next; p-next=q; /前驱变后继前驱变后继 q=p; p=r; /准备处理下一结点准备处理下一结点head-next=q; / 以以an为首为首替换法的核心语句：替换法的核心语句：插入法的核心语句：插入法的核心语句：ai-1aiqai+1prheada1heada2pq请上机验证并分析效请上机验证并分析效率！率！1 1、试用试用C C或类或类C C语言编写一个语言编写一个高效高效算法，将一不带头结点单链算法，将一不

60、带头结点单链表就地逆置。表就地逆置。 举一反三举一反三2 2、试用试用C C或类或类C C语言编写一个语言编写一个高效高效算法，将一带头结点单链算法，将一带头结点单链表就地逆置。表就地逆置。 3 3、试用试用C C或类或类C C语言编写一个语言编写一个高效高效算法，将一不带头结点循算法，将一不带头结点循环单链表就地逆置。环单链表就地逆置。 静态链表静态链表双向链表双向链表循环链表循环链表具体实现方法：具体实现方法：定义一个结构型数组（每个元定义一个结构型数组（每个元素都含有素都含有数据域数据域和和指示域指示域），就可以完全描述），就可以完全描述链表，链表，指示域指示域就相当于动态链表中的指针。就相当于动态链表中的指针。指示域也常称为指示域也常称为“游标游标”2.5.1 静态链表静态链表 动态链表样式：动态链表样式：静态链表样式：静态链