课件教案数据结构严蔚敏第2章线性表(完整版)

1、 第第2 2章章 线性表线性表 第第3 3章章 栈和队列栈和队列 第第4 4章章 串、数组和广义表串、数组和广义表 线性结构线性结构若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1 , a, a2 2 , , a, , an n） （逻辑、存储（逻辑、存储和运算）和运算） 只有一个首结点和尾结点；只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一除首尾结点外，其他结点只有一个

2、直接前驱和一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a a1 1 , a, a2 2 , , a, , an n） 线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的第第2 2章线性表章线性表1. 1. 了解线性结构的特点了解线性结构的特点2. 2.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3. 3.掌握链表的定义、创建、查找、插入和删除掌握链

3、表的定义、创建、查找、插入和删除 4. 4.能够从时间和空间复杂度的角度比较两种存储结能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合构的不同特点及其适用场合 教学目标教学目标2.1 2.1 线性表的定义和特点线性表的定义和特点2.2 2.2 案例引入案例引入2.3 2.3 线性的类型定义线性的类型定义2.4 2.4 线性表的顺序表示和实现线性表的顺序表示和实现2.5 2.5 线性表的链式表示和实现线性表的链式表示和实现2.6 2.6 顺序表和链表的比较顺序表和链表的比较2.7 2.7 线性表的应用线性表的应用2.8 2.8 案例分析与实现案例分析与实现教学内容教学内容（a1

4、, a2, ai-1，ai, ai1 ，, an）线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai i的直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的定义和特点线性表的定义和特点 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级

5、计算机级计算机1 1班班041810260041810260何仕鹏何仕鹏男男 20 200404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 190404级计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班： ：数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性2.2 2.2 案例引入案例引入Pn(x) = p0 + p1x + p2

6、x2 + + pnxn线性表线性表P = (p0,p1,p2,pn)指数（下标i）01234系数pi105-432P(x) = 10 + 5x - 4x2 + 3x3 + 2x4数组表示数组表示（每一项的指数（每一项的指数i隐含隐含在其系数在其系数pi的序号中）的序号中）Rn(x) = Pn(x) + Qm(x)线性表线性表R = (p0 + q0,p1 + q1,p2 + q2,pm + qm,pm+1,pn)稀疏多项式稀疏多项式S(x) = 1 + 3x10000 + 2x20000北京林业大学信息学院下标i0123下标i012系数ai7395系数bi822-9指数01817指数178多项

7、式非零项非零项的数组表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 9x8 线性表线性表P =(p1, e1), (p2, e2),(pm, em)l创建一个创建一个新数组新数组c cl分别从头遍历比较分别从头遍历比较a a和和b b的每一项的每一项指数相同指数相同，对应系数相加，若其和不为零，则在，对应系数相加，若其和不为零，则在c c中增加一个新项中增加一个新项指数不相同指数不相同，则将指数较小的项复制到，则将指数较小的项复制到c c中中l一个多项式已遍历一个多项式已遍历完毕完毕时，将另一个剩余项依次复制到时，将另一个剩余项依次复制

8、到c c中即可中即可A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapbl顺序存储结构存在问题顺序存储结构存在问题存储空间分配不灵活存储空间分配不灵活运算的空间复杂度高运算的空间复杂度高链式存储结构链式存储结构A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x

9、+22x7-9x8181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapb（1 1）查找）查找（2 2）插入）插入（3 3）删除）删除（4 4）修改）修改（5 5）排序）排序（6 6）计数）计数图书顺序表图书顺序表图书链表图书链表l线性表中数据元素的类型可以为简单类型，也可以为复杂类型。线性表中数据元素的类型可以为简单类型，也可以为复杂类型。l许多实际应用问题所涉的基本操作有很大相似性，不应为每个具许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编

10、写一个程序。体应用单独编写一个程序。l从具体应用中从具体应用中抽象出共性的逻辑结构和基本操作抽象出共性的逻辑结构和基本操作（抽象数据类抽象数据类型型），然后实现其存储结构和基本操作。），然后实现其存储结构和基本操作。线性表的重要基本操作线性表的重要基本操作1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除2.3 2.3 线性表的类型定义线性表的类型定义2.4 2.4 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻

11、辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组VnVn来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储#define MAXSIZE 100 /#define M

12、AXSIZE 100 /最大长度最大长度typedef struct typedef struct ElemType ElemType * *elem; /elem; /指向数据元素的基地址指向数据元素的基地址 int length; /int length; /线性表的当前长度线性表的当前长度 SqListSqList；顺序表的类型定义顺序表的类型定义#define MAXSIZE 10000/图书表可能达到的最大长度图书表可能达到的最大长度 typedef struct/图书信息定义图书信息定义 char no20;/图书图书ISBN char name50;/图书名字图书名字 float

13、 price; /图书价格图书价格Book; typedef struct Book *elem;/存储空间的基地址存储空间的基地址 int length;/图书表中当前图书个数图书表中当前图书个数 SqList;/图书表的顺序存储结构类型为图书表的顺序存储结构类型为SqList图书表的顺序存储结构类型定义图书表的顺序存储结构类型定义malloc(malloc(m m) )：开辟：开辟m m字节长度的地址空间，字节长度的地址空间，并返回这段空间的首地址并返回这段空间的首地址sizeof(sizeof(x x) )：计算变量：计算变量x x的长度的长度free(free(p p) )：释放指针：

14、释放指针p p所指变量的存储空间所指变量的存储空间，即彻底删除一个变量，即彻底删除一个变量补充：补充：C C语言的动态分配函数（语言的动态分配函数（ ）new new 类型名类型名T T（初值列表）（初值列表）功能：功能：申请用于存放申请用于存放T T类型对象的内存空间，并依初值列表赋以初值类型对象的内存空间，并依初值列表赋以初值结果值：结果值：成功：成功：T T类型的指针，指向新分配的内存类型的指针，指向新分配的内存失败：失败：0 0（NULLNULL）int *p1= new int;或或 int *p1 = new int(10);delete delete 指针指针P P功能：功能：释

15、放指针释放指针P P所指向的内存。所指向的内存。P P必须是必须是newnew操作的返回值操作的返回值delete p1;补充：补充：C+C+的动态存储分配的动态存储分配n函数调用时传送给形参表的实参必须与形参在类函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致型、个数、顺序上保持一致n参数传递有两种方式参数传递有两种方式n传值方式传值方式（参数为整型、实型、字符型等）（参数为整型、实型、字符型等）n传地址传地址参数为指针变量参数为指针变量参数为引用类型参数为引用类型参数为数组名参数为数组名补充：补充：C+C+中的参数传递中的参数传递void main()float a,b;

16、 cinab; swap(a,b);coutaendlbendl;#include void swap(float m,float n)float temp; temp=m; m=n; n=temp;传值传值方式方式把实参的值传送给函数局部工作区相应的副把实参的值传送给函数局部工作区相应的副本中本中，函数使用这个副本执行必要的功能。，函数使用这个副本执行必要的功能。函数修改的是函数修改的是副本的值副本的值，实参的值不变实参的值不变传地址传地址方式方式指针变量作参数指针变量作参数void main()float a,b,*p1,*p2; cinab; p1=&a; p2=&b;

17、swap(p1, p2);coutaendlbendl;#include void swap(float *m,float *n)float t; t=*m; *m=*n; *n=t;形参变化影响实参形参变化影响实参 18:40 传地址传地址方式方式指针变量作参数指针变量作参数void main()float a,b,*p1,*p2; cinab; p1=&a; p2=&b; swap(p1, p2);coutaendlbendl;#include void swap(float *m,float *n)float *t; t=m; m=n; n=t;形参变化不影响实参？形参变

18、化不影响实参？传地址传地址方式方式引用类型作参数引用类型作参数引用：它用来给一个对象提供一个替代的名字。引用：它用来给一个对象提供一个替代的名字。#includevoid main()int i=5;int &j=i;i=7;couti=i j=ab; swap(a,b);coutaendlbendl;#include void swap(float m,float n)float temp; temp=m; m=n; n=temp;传地址传地址方式方式引用类型作参数引用类型作参数（1 1）传递引用给函数与传递指针的效果是一）传递引用给函数与传递指针的效果是一样的，样的，形参变化实参也

19、发生变化形参变化实参也发生变化。（2 2）引用类型作形参，在内存中并没有产生）引用类型作形参，在内存中并没有产生实参的副本，它实参的副本，它直接对实参操作直接对实参操作；而一般变；而一般变量作参数，形参与实参就占用不同的存储单量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。元，所以形参变量的值是实参变量的副本。因此，当因此，当参数传递的数据量较大参数传递的数据量较大时，用引用时，用引用比用一般变量传递参数的时间和空间效率都比用一般变量传递参数的时间和空间效率都好。好。引用类型作形参的三点说明引用类型作形参的三点说明（3）指针参数虽然也能达到与使用引用的效）指针参数虽

20、然也能达到与使用引用的效果，但在被调函数中需要重复使用果，但在被调函数中需要重复使用“* *指针指针变量名变量名”的形式进行运算，这很容易产生错的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用函数的调用点处，必须用变量的地址作为实变量的地址作为实参参。引用类型作形参的三点说明引用类型作形参的三点说明传地址传地址方式方式数组名作参数数组名作参数#includevoid sub(char);void main（void ） char a10=“hello”; sub(a); coutaendl;void sub(cha

21、r b ) b =“world”;传递的是数组的首地址传递的是数组的首地址对形参数组所做的任何改变都将反映到实参数组中对形参数组所做的任何改变都将反映到实参数组中北京林业大学信息学院#include #define N 10int max(int a);void main ( ) int a10;int i,m;for(i=0;iai;m=max(a);coutthe max number is:m;int max(int b) int i,n; n=b0; for(i=1;iN;i+)if(nbi) n=bi; return n;用数组作函数的参数，求用数组作函数的参数，求10个整数的最大数

22、个整数的最大数练习：练习：用数组作为函数的参数，将数组中用数组作为函数的参数，将数组中n个整数按相反的顺序存个整数按相反的顺序存放，要求输入和输出在主函数中完成放，要求输入和输出在主函数中完成#include #define N 10void sub(int b )int i,j,temp,m;m=N/2;for(i=0;im;i+) j=N-1-i; temp=bi; bi= bj; bj=temp;return ;void main ( ) int a10,i;for(i=0;iai;sub(a);for(i=0;iN;i+)cout elem=new ElemTypeMAXSIZE; /

23、为顺序表分配空间为顺序表分配空间 if(! L- elem) exit(OVERFLOW); /存储分配失败存储分配失败 L- length=0; /空表长度为空表长度为0 return OK; 销毁线性表销毁线性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /释放存储空间释放存储空间 清空线性表清空线性表L Lvoid ClearList(SqList &L) L.length=0; /将线

24、性表的长度置为将线性表的长度置为0补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现求线性表求线性表L L的长度的长度int GetLength(SqList L) return (L.length); 判断线性表判断线性表L L是否为空是否为空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0;补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除线性表的重要基本操作线性表的重要基本操作int

25、GetElem(SqList L,int int GetElem(SqList L,int i,ElemType &ei,ElemType &e) ) if (iL.length) return ERROR; if (iL.length) return ERROR; / /判断判断i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=L.elemi-1;e=L.elemi-1; / /第第i-1i-1的单元存储着第的单元存储着第i i个数据个数据 return OK;return OK; 2. 2. 取值取值（根据位置（根据位置i i获取相应位置数

26、据元素的内容）获取相应位置数据元素的内容）随机存取获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容3.3.查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i查找成功查找成功25 34 57 16 48 0 1 2 3 4data查找 50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57

27、 16 48 i查找失败查找失败3. 3. 查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）查找算法时间效率分析查找算法时间效率分析在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素int LocateELem(SqList L,ElemType e) for (i=0;i L.length;i+) if (L.elemi=e) return i+1; return 0;3. 3. 查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置）2512478936141234567892512479989361499插入插入25124

28、7893614251247893614251247893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次4. 4. 插入插入（插在第（插在第 i i 个结点之前）个结点之前）（1 1）判断）判断插入位置插入位置i i 是否合法是否合法。（2 2）判断顺序表的）判断顺序表的存储空间是否已满存储空间是否已满。 （3 3）将第）将第n n至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空，空出第出第i i个位置。个位置。（4 4）将要插入的新元素）将要插入的新

29、元素e e放入第放入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回OKOK。【算法步骤算法步骤】4. 4. 在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e Status ListInsert_Sq(SqList &L,int i ,ElemType e) if(iL.length+1) return ERROR; /i值不合法值不合法 if(L.length=MAXSIZE) return ERROR; /当前存储空间已满当前存储空间已满 for(j=L.length-1;j=i-1;j-) L.elemj

30、+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /将新元素将新元素e放入第放入第i个位置个位置 +L.length; /表长增表长增1 return OK;【算法描述算法描述】221)(1)(1 0)1(11)(11=1nnnnnn1inn1niAMN若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动

31、次数，该如何计算？数，该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【算法分析算法分析】251247893614123456789251247361425124736142512473614删除删除5. 5. 删除删除（删除第（删除第 i i 个结点）个结点）删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i i 个结点，移动个结点，移动 n-in-i 次次（1 1）判断）判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为1in1in）。）。（2 2）将欲删除的元素保留在）将欲删除的元素保留在e e中。中。 （3

32、3）将第）将第i+1i+1至第至第n n 位的元素依次位的元素依次向前移动一个位置向前移动一个位置。（4 4）表长减表长减1 1，删除成功返回，删除成功返回OKOK。【算法步骤算法步骤】5. 5. 将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除Status ListDelete_Sq(SqList &L,int i) if(iL.length) return ERROR; /i值不合法值不合法 for (j=i;jdata=ai, 则则p-next-data=ai+1 a1a2an.L 18:40 2.5.2 2.5.2 单链表基本操作的实现单链表基本操作的实现1.

33、1. 初始化初始化2. 2. 取值取值3. 3. 查找查找4. 4. 插入插入5. 5. 删除删除 18:40 1.1.初始化初始化( (构造一个空表构造一个空表 )【算法步骤算法步骤】（1）生成新结点作头结点，用头指针）生成新结点作头结点，用头指针L指向头结点。指向头结点。（2）头结点的指针域置空。）头结点的指针域置空。L【算法描述算法描述】Status InitList_L(LinkList &L) L=new LNode; L-next=NULL; return OK; 18:40 销毁销毁Status DestroyList_L(LinkList &L) LinkLis

34、t p; while(L) p=L; L=L-next; delete p; return OK; 补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现 18:40 清空清空Status ClearList(LinkList & & L) / / 将将L L重置为空表重置为空表 LinkList p,q; p=L-next; /p/p指向第一个结点指向第一个结点 while(p) /没到表尾没到表尾 q=p-next; delete p; p=q; L-next=NULL; /头结点指针域为空头结点指针域为空 return OK; 补充：几个简单基本操作的算法实现补

35、充：几个简单基本操作的算法实现 18:40 pLa1a2. pi01p2pn=NULLan求表长求表长p=L-next; i=0; while(p)i+;p=p-next; 补充：几个简单基本操作的算法实现补充：几个简单基本操作的算法实现“数数”结点：结点：指针指针p依次指向各个结点依次指向各个结点从第一个元素开始从第一个元素开始“数数” 一直一直“数数”到最后一个结点到最后一个结点 18:40 求表长求表长int ListLength_L(LinkList L)/返回返回L L中数据元素个数中数据元素个数 LinkList p; p=L-next; /p/p指向第一个结点指向第一个结点 i=

36、0; while(p)/遍历单链表遍历单链表, ,统计结点数统计结点数 i+; p=p-next; return i; “数数”结点：结点：指针指针p依次指向各个结点依次指向各个结点从第一个元素开始从第一个元素开始“数数” 一直一直“数数”到最后一个结点到最后一个结点 18:40 判断表是否为空判断表是否为空int ListEmpty(LinkList L) / / /若若L L为空表，则返回为空表，则返回1 1，否则返回，否则返回0 0 if(L-next) / / /非空非空 return 0; else return 1; 1. 1. 初始化初始化2. 2. 取值取值3. 3. 查找查找

37、4. 4. 插入插入5. 5. 删除删除线性表的重要基本操作线性表的重要基本操作 18:40 思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？ 链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构2. 2. 取值取值（根据位置（根据位置i i获取相应位置数据元素的内容）获取相应位置数据元素的内容） 18:40 85L211830754256pppj1 2 3pp1i=3i=156p7例

38、：分别取出表中例：分别取出表中i=3和和i=15的元素的元素从第从第1 1个结点（个结点（L-nextL-next）顺链扫描，用指针）顺链扫描，用指针p p指向当指向当前扫描到的结点，前扫描到的结点，p p初值初值p p = = L-nextL-next。j j做计数器，累计当前扫描过的结点数，做计数器，累计当前扫描过的结点数，j j初值为初值为1 1。当当p p指向扫描到的下一结点时，计数器指向扫描到的下一结点时，计数器j j加加1 1。当当j j= = i i时，时，p p所指的结点就是要找的第所指的结点就是要找的第i i个结点。个结点。【算法步骤算法步骤】 18:40 北京林业大学信息学

39、院/获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容Status GetElem_L(LinkList L,int i,ElemType &e) p=L-next;j=1; /初始化初始化 while(p&jnext; +j; if(!p | ji)return ERROR; /第第i个元素不存在个元素不存在 e=p-data; /取第取第i个元素个元素 return OK; /GetElem_L 2. 2. 取值取值（根据位置（根据位置i i获取相应位置数据元素的内容）获取相应位置数据元素的内容） 18:40 从第一个结点起，依次和从第一个结点起，依次和

40、e e相比较。相比较。如果找到一个其值与如果找到一个其值与e e相等的数据元素，则返回其相等的数据元素，则返回其在链表中的在链表中的“位置位置”或地址或地址；如果查遍整个链表都没有找到其值和如果查遍整个链表都没有找到其值和e e相等的元素相等的元素，则返回，则返回0 0或或“NULLNULL”。L211830753056pj1x=30p2p3找到，返回找到，返回i ix=51p1p6p7未找到，返回03.3.查找查找（根据指定数据获取数据所在的位置）（根据指定数据获取数据所在的位置） 18:40 /在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素LNode *LocateE

41、Lem_L (LinkList L，Elemtype e) /返回返回L中值为中值为e的数据元素的的数据元素的地址地址，查找失败返回，查找失败返回NULL p=L-next; while(p &p-data!=e) p=p-next; return p; 【算法描述算法描述】 18:40 /在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素int LocateELem_L (LinkList L，Elemtype e) /返回返回L中值为中值为e的数据元素的的数据元素的位置序号位置序号，查找失败返回，查找失败返回0 p=L-next; j=1; while(p &am

42、p;p-data!=e) p=p-next; j+; if(p) return j; else return 0; 【算法描述算法描述】 18:40 将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位个结点的位置上，即插入到置上，即插入到a ai-1i-1与与a ai i之间之间3. 3. 插入插入（插在第（插在第 i i 个结点之前）个结点之前）s-next=p-next; p-next=s思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？ 18:40 【算法步骤算法步骤】（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）生成一个新结点）生成

43、一个新结点* *s s（3 3）将新结点）将新结点* *s s的数据域置为的数据域置为x x（4 4）新结点）新结点* *s s的指针域指向结点的指针域指向结点a ai i（5 5）令结点）令结点* *p p的指针域指向新结点的指针域指向新结点* *s s 18:40 /在在L L中第中第i i个元素之前插入数据元素个元素之前插入数据元素e e Status ListInsert_L(LinkList &L,int i,ElemType e) p=L;j=0; while(p&jnext;+j;/寻找第寻找第i1个结点个结点 if(!p|ji1)return ERROR;/i大

44、于表长大于表长 + 1或者小于或者小于1 s=new LNode;/生成新结点生成新结点s s-data=e; /将结点将结点s的数据域置为的数据域置为e s-next=p-next; /将结点将结点s插入插入L中中 p-next=s; return OK; /ListInsert_L 【算法描述算法描述】 18:40 将表的第将表的第i i个结点删去个结点删去 步骤：步骤：（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）保存要删除的结点的值）保存要删除的结点的值（3 3）令）令p-p-nextnext指向指向a ai i的直接后继结点的直接后继结点（4 4）释放结点）释

45、放结点a ai i的空间的空间5. 5. 删除删除（删除第（删除第 i i 个结点）个结点） 18:40 5. 5. 删除删除（删除第（删除第 i i 个结点）个结点） 18:40 5. 5. 删除删除（删除第（删除第 i i 个结点）个结点）p-next = p-next-next ?ai-1ai-1aiaiai+1ai+1pq删除前删除前删除后删除后 18:40 【算法步骤算法步骤】（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）临时保存结点）临时保存结点a ai i的地址在的地址在q q中，以备释放中，以备释放（3 3）令）令p-nextp-next指向指向a ai

46、 i的直接后继结点的直接后继结点（4 4）将）将a ai i的值保留在的值保留在e e中中（5 5）释放）释放a ai i的空间的空间 18:40 /将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e) p=L;j=0; while(p-next &jnext; +j; if(!(p-next)|ji-1) return ERROR; /删除位置不合理删除位置不合理 q=p-next; /临时保存被删结点的地址以备释放临时保存被删结点的地址以备释放 p-ne

47、xt=q-next; /改变删除结点前驱结点的指针域改变删除结点前驱结点的指针域 e=q-data; /保存删除结点的数据域保存删除结点的数据域 delete q; /释放删除结点的空间释放删除结点的空间 return OK; /ListDelete_L 【算法描述算法描述】 18:40 1. 查找查找: 因线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间复杂度为 O(n)。2. 插入和删除插入和删除: 因线性链表不需要移动元素，只要因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为修改指针，一般情况下时

48、间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。链表的运算时间效率分析链表的运算时间效率分析 18:40 n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：u生成新结点生成新结点u将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中u将该新结点插入到链表的前端将该新结点插入到链表的前端单链表的建立（前插法）单链表的建立（前插法） L L L L L e e a b L d c e d e b c d e c d 18:

49、40 LpLanan-1anLp单链表的建立（前插法）单链表的建立（前插法） 18:40 void CreateList_F(LinkList &L,int n) L=new LNode; L-next=NULL; /先建立一个带头结点的单链表先建立一个带头结点的单链表 for(i=n;i0;-i) p=new LNode; /生成新结点生成新结点 cinp-data; /输入元素值输入元素值 p-next=L-next;L-next=p; /插入到表头插入到表头 /CreateList_F 【算法描述算法描述】 18:40 n从一个空表从一个空表L开始，将新结点逐个插入到链表的尾部，

50、尾指开始，将新结点逐个插入到链表的尾部，尾指针针r指向链表的尾结点。指向链表的尾结点。n初始时，初始时，r同同L均指向头结点。每读入一个数据元素则申请一均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，个新结点，将新结点插入到尾结点后，r指向新结点。指向新结点。单链表的建立（尾插法）单链表的建立（尾插法） L L L L L L a r r a b r a c r b a e r b c d a d r b c 18:40 void CreateList_L(LinkList &L,int n) /正位序输入正位序输入n个元素的值，建立带表头结点的单链表个元素的

51、值，建立带表头结点的单链表L L=new LNode; L-next=NULL; r=L; /尾指针尾指针r指向头结点指向头结点 for(i=0;ip-data; /输入元素值输入元素值 p-next=NULL; r-next=p; /插入到表尾插入到表尾 r=p; /r指向新的尾结点指向新的尾结点 /CreateList_L 【算法描述算法描述】 18:40 2.5.3 2.5.3 循环链表循环链表L-next=L.H(a) (a) 非空单循环链表非空单循环链表LH(b) (b) 空表空表L说明说明从循环链表中的任何一个结点的位置都可从循环链表中的任何一个结点的位置都可以找到其他所有结点，而

52、单链表做不到；以找到其他所有结点，而单链表做不到；循环条件：循环条件：p!=NULLp!=L p-next!=NULLp-next!=L循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环.H 18:40 对循环链表，有时不给出头指针，而给出对循环链表，有时不给出头指针，而给出尾指针尾指针可以更方便的找到可以更方便的找到第一个和最后一个第一个和最后一个结点结点reara1ai-1anai如何查找开始结点和终端结点？如何查找开始结点和终端结点？开始结点：开始结点：rear-next-next终端结点：终端结点：rear说明说明TaTaa a1 1a an nTbTbb

53、b1 1b bn n循环链表的合并循环链表的合并a a1 1a an nb b1 1b bn npTaTaTbTb示例示例 18:40 a a1 1a an nb b1 1b bn npTaTaTbTbLinkList Connect(LinkList Ta,LinkList Tb)/假设假设Ta、Tb都是非空的单循环链表都是非空的单循环链表 /p p存表头结点存表头结点 /TbTb表头连结表头连结TaTa表尾表尾 /释放释放TbTb表头结点表头结点 /修改指针修改指针 return Tb;p=Ta-next;Ta-next=Tb-next-next;deleteTb-next; Tb-nex

54、t=p; 示例示例 18:40 著名犹太历史学家著名犹太历史学家 Josephus在罗马人占领乔塔帕特后在罗马人占领乔塔帕特后39 个犹太人与个犹太人与Josephus及他的朋友躲及他的朋友躲到一个洞中到一个洞中39个犹太人决定宁愿死也不要被敌人个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式抓到，于是决定了一个自杀方式41个人个人排成一个圆圈，由第排成一个圆圈，由第1个人开个人开始报数，每报数到第始报数，每报数到第3人该人就必须自人该人就必须自杀，然后再由下一个重新报数，直到杀，然后再由下一个重新报数，直到所有人都自杀身亡为止所有人都自杀身亡为止然而然而Josephus 和他的朋友

55、并不想遵从和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，要他的朋友先假装遵从，他将朋友与自己安排在第他将朋友与自己安排在第16个与第个与第31个位置，于是逃过了这场死亡游戏个位置，于是逃过了这场死亡游戏 约瑟夫问题约瑟夫问题约瑟夫问题约瑟夫问题void Josephus ( int n, int m ) Firster ( ); /检验指针指向第一个结点检验指针指向第一个结点 for ( int i = 0; i n- -1; i+ ) /执行执行n- -1次次 for ( int j = 0; j m- -1; j+ ) Next ( ); /循环循环m次使次使current指

56、向被删除结点指向被删除结点 cout “出列的人是出列的人是” GetElem_L ( ) next-prior = d-prior-next = dL-next=L 18:40 ab.pxs双向链表的插入双向链表的插入 18:40 1. s-prior=p-prior;双向链表的插入双向链表的插入a ab bx x.1 1p ps s 18:40 双向链表的插入双向链表的插入1. s-prior=p-prior;2. p-prior-next=s;abx.12ps 18:40 双向链表的插入双向链表的插入abx.123ps1. s-prior=p-prior;2. p-prior-next=

57、s;3. s-next=p; 18:40 双向链表的插入双向链表的插入4. p-prior=s;abx.1234ps1. s-prior=p-prior;2. p-prior-next=s;3. s-next=p; 18:40 Status ListInsert_DuL(DuLinkList &L,int i,ElemType e) if(!(p=GetElemP_DuL(L,i) return ERROR; s=new DuLNode; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK;

58、双向链表的插入双向链表的插入 18:40 ab.pc双向链表的删除双向链表的删除 18:40 ab.1pc1. p-prior-next=p-next;双向链表的删除双向链表的删除 18:40 双向链表的删除双向链表的删除ab.12pc1. p-prior-next=p-next;2. p-next-prior=p-prior; 18:40 Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e) if(!(p=GetElemP_DuL(L,i) return ERROR; e=p-data; p-prior-next=p-n

59、ext; p-next-prior=p-prior; delete p; return OK;双向链表的删除双向链表的删除北京林业大学信息学院2.6 2.6 顺序表和链表的比较顺序表和链表的比较存储结构比较项目顺序表链表空间存储空间预先分配，会导致空间闲置或溢出现象动态分配，不会出现存储空间闲置或溢出现象存储密度不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1需要借助指针来体现元素间的逻辑关系，存储密度小于1时间存取元素随机存取，按位置访问元素的时间复杂度为O(1)顺序存取，按位置访问元素时间复杂度为O(n)插入、删除平均移动约表中一半元素，时间复杂度为O(n)不需移动元素，确定

60、插入、删除位置后，时间复杂度为O(n)适用情况 表长变化不大，且能事先确定变化的范围 很少进行插入或删除操作，经常按元素位置序号访问数据元素 长度变化较大 频繁进行插入或删除操作 18:40 2.7 2.7 线性表的应用线性表的应用 18:40 2.7.1 2.7.1 线性表的合并线性表的合并问题描述：问题描述： 假设利用两个线性表假设利用两个线性表LaLa和和LbLb分别表示两分别表示两个集合个集合A A和和B,B,现要求一个新的集合现要求一个新的集合 A=ABLa=(7, 5, 3, 11)Lb=(2, 6, 3)La=(7, 5, 3, 11, 2, 6) . 18:40 依次取出依次取出Lb Lb 中的每个元素，执行以下操作：中的每个元素，执行以下操作：在在LaLa中查找该元素中查找该元素如果找不到，则将其插入如果找不到，则将其插入La的最后的最后【算法步骤算法步骤】 18:40 void union(List &La, List Lb) La_