数据结构Chapter02线性表

1、算法与数据结构12013.9-2013.12主讲教师：张翠肖联系方式：算法与数据结构2 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 线性结构线性结构 非线性结构非线性结构顺序存储顺序存储链式存储链式存储 线性表线性表栈栈队列队列树树图图数据结构数据结构( (物理结构物理结构) )数据结构：是相互之间存在一种或多数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。种特定关系的数据元素的集合。 逻辑结构：结构定义中的逻辑结构：结构定义中的“关系关系”描述的是数据描述的是数据元素之间的逻辑关系，因此称为数据的逻辑结构元素之间的逻辑关系，因此称为数据的逻辑结构。 存储结构：是数

2、据结构在计算机中的表示（又称映像）。存储结构：是数据结构在计算机中的表示（又称映像）。(2)算法与数据结构3 第第2 2章章 线性表线性表 第第3 3章章 栈和队列栈和队列 第第4 4章章 串、数组和广串、数组和广义表义表 线性结构线性结构若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1 , a, a2 2 , , , a, an n） （逻辑、存储（逻辑、存储和运算）和运算）算法与数据结构4

3、 只有一个首结点和尾结点；只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一除首尾结点外，其他结点只有一个直接前驱和一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a a1 1 , a, a2 2 , , , a, an n） 线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的算法与数据结构5第第2 2章章线性表线性表1. 了解线性结构的特点了解线性结构的特点

4、2.2.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3.3.掌握链表的定义、查找、插入和删除掌握链表的定义、查找、插入和删除 4.4.能够从时间和空间复杂度的角度比较两种能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合存储结构的不同特点及其适用场合 教学目标教学目标算法与数据结构62.1 线性表的类型定义线性表的类型定义2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 线性表的应用线性表的应用教学内容教学内容算法与数据结构7（a1, a2, ai-1，ai, ai1 ，, an）线性表的定

5、义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai i的直接前趋的直接前趋a ai i的直接后继的直接后继下标下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的类型定义线性表的类型定义算法与数据结构8 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级计算机级计算机1 1班班0418102600418

6、10260何仕鹏何仕鹏男男 20 200404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 190404级计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班： ：数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.

7、,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空表。数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序位序。算法与数据结构10 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT List算法与数据结构11 InitList( &L )操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操作算法与数据结构12 结构销毁操作结构销毁操作DestroyList( &L )初

8、始条件：操作结果：线性表 L 已存在。销毁线性表 L。算法与数据结构13ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e)引用型操作引用型操作: :算法与数据结构14 ListEmpty( L )初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）算法与数据结构15ListLength( L )初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表

9、的长度）算法与数据结构16 PriorElem( L, cur_e, &pre_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）算法与数据结构17NextElem( L, cur_e, &next_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）算法与数据结构18GetElem( L, i, &e ) 初始条件： 操作结果：线性表L已存在，且 1iLengthLis

10、t(L)。用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）算法与数据结构19LocateElem( L, e)初始条件：操作结果：线性表L已存在，e为给定值返回L中第中第1个个与e相等相等的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）算法与数据结构20加工型操作加工型操作 ClearList( &L )ListInsert( &L, i, e )ListDelete(&L, i, &e) 算法与数据结构21ClearList( &L )初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）算法与数据结构22 ListInsert( &L, i, e )初

11、始条件：操作结果：线性表L已存在， 且 1iLengthList(L)+1 。在L的第i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）算法与数据结构23ListDelete(&L, i, &e)初始条件：操作结果：线性表L已存在且非空， 1iLengthList(L) 。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）算法与数据结构242.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺

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

13、XSIZE 100 /最大长度最大长度typedef struct typedef struct ElemType ElemType * *elem; /elem; /指向数据元素的基地址指向数据元素的基地址 int length; /int length; /线性表的当前长度线性表的当前长度 SqListSqList；顺序表的类型定义顺序表的类型定义数据结构基本运算操作有：数据结构基本运算操作有：查找、插入、删除查找、插入、删除算法与数据结构27malloc(malloc(m m) )：开辟：开辟m m字节长度的地址空间，字节长度的地址空间，并返回这段空间的首地址并返回这段空间的首地址siz

14、eof(sizeof(x x) )：计算变量：计算变量x x的长度的长度free(free(p p) )：释放指针：释放指针p p所指变量的存储空间所指变量的存储空间，即彻底删除一个变量，即彻底删除一个变量补充：补充：C C语言的动态分配函数（语言的动态分配函数（ ）算法与数据结构28new new 类型名类型名T T（初值列表）（初值列表）功能：功能：申请用于存放申请用于存放T T类型对象的内存空间，并依初值列表赋以初值类型对象的内存空间，并依初值列表赋以初值结果值：结果值：成功：成功：T T类型的指针，指向新分配的内存类型的指针，指向新分配的内存失败：失败：0 0（NULLNULL）int

15、 *p1= new int;或或 int *p1 = new int(10);delete delete 指针指针P P功能：功能：释放指针释放指针P P所指向的内存。所指向的内存。P P必须是必须是newnew操作的返回值操作的返回值delete p1;补充：补充：C+C+的动态存储分配的动态存储分配算法与数据结构29n函数调用时传送给形参表的实参必须与形参在类函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致型、个数、顺序上保持一致n参数传递有两种方式参数传递有两种方式n传值方式传值方式（参数为整型、实型、字符型等）（参数为整型、实型、字符型等）n传地址传地址参数为指针变量

16、参数为指针变量参数为引用类型参数为引用类型参数为数组名参数为数组名补充：补充：C+C+中的参数传递中的参数传递算法与数据结构30void main()float a,b; cinab; swap(a,b);coutaendlbendl;#include void swap(float m,float n)float temp; temp=m; m=n; n=temp;传值传值方式方式把实参的值传送给函数局部工作区相应的副把实参的值传送给函数局部工作区相应的副本中本中，函数使用这个副本执行必要的功能。，函数使用这个副本执行必要的功能。函数修改的是函数修改的是副本的值副本的值，实参的值不变实参的值

17、不变算法与数据结构31传地址传地址方式方式指针变量作参数指针变量作参数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;形参变化影响实参形参变化影响实参算法与数据结构32传地址传地址方式方式引用类型作参数引用类型作参数引用：它用来给一个对象提供一个替代的名字。引用：它用来给一个对象提供一个替代的名字。#includevoid main()int i=5;int

18、&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;传地址传地址方式方式引用类型作参数引用类型作参数算法与数据结构34（1 1）传递引用给函数与传递指针的效果是一）传递引用给函数与传递指针的效果是一样的，样的，形参变化实参也发生变化形参变化实参也发生变化。（2 2）引用类型作形参，在内存中并没有产生）引用类型作形参，在内存中并没有产生实参的副本，它实参的副本，它直接对实参操作直接对实参操作；而一般变；而一般变量作参数，

19、形参与实参就占用不同的存储单量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。元，所以形参变量的值是实参变量的副本。因此，当因此，当参数传递的数据量较大参数传递的数据量较大时，用引用时，用引用比用一般变量传递参数的时间和空间效率都比用一般变量传递参数的时间和空间效率都好。好。引用类型作形参的三点说明引用类型作形参的三点说明算法与数据结构35（3）指针参数虽然也能达到与使用引用的效）指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用果，但在被调函数中需要重复使用“* *指针指针变量名变量名”的形式进行运算，这很容易产生错的形式进行运算，这很容易产生错误且程

20、序的阅读性较差；另一方面，在主调误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用函数的调用点处，必须用变量的地址作为实变量的地址作为实参参。引用类型作形参的三点说明引用类型作形参的三点说明算法与数据结构36传地址传地址方式方式数组名作参数数组名作参数#includevoid sub(char);void main（void ） char a10=“hello”; sub(a); coutaendl;void sub(char b ) b =“world”;传递的是数组的首地址传递的是数组的首地址对形参数组所做的任何改变都将反映到实参数组中对形参数组所做的任何改变都将反映到实参数组中

21、算法与数据结构37 11:25 #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个整数的最大数个整数的最大数算法与数据结构38练习：练习：用数组作为函数的参数，将数组中用数组作为函数的参数，将数组中n个整数按相反的顺序存个整数按相反的顺序存放，

22、要求输入和输出在主函数中完成放，要求输入和输出在主函数中完成#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; /为顺序表分配空间为顺序表分配空间 if(! L- elem) exit(OVERFLOW); /存储分配失败存储分配失败 L- le

23、ngth=0; /空表长度为空表长度为0 return OK;算法与数据结构422. 2. 销毁线性表销毁线性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /释放存储空间释放存储空间 3. 3. 清空线性表清空线性表L Lvoid ClearList(SqList &L) L.length=0; /将线性表的长度置为将线性表的长度置为0算法与数据结构434.4. 求线性表求线性表L L的长度的长度int GetLen

24、gth(SqList L) return (L.length); 5.5.判断线性表判断线性表L L是否为空是否为空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0;算法与数据结构446. 6. 获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容/根据指定位置，获取相应位置数据元素的内容根据指定位置，获取相应位置数据元素的内容int GetElem(SqList L,int int GetElem(SqList L,int i,ElemType &ei,ElemType &e) ) if (iL.le

25、ngth) 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; 算法与数据结构45查找查找（根据指定数据查找，返回数据所在的位置）（根据指定数据查找，返回数据所在的位置）25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57

26、 16 48 09 i25 34 57 16 48 09 i查找成功查找成功算法与数据结构4625 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 16 48 i查找失败查找失败算法与数据结构47例如：顺序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。算法与数据结构48查找算法时间效率分析查找算法时间效率分析7.

27、7. 在线性表在线性表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;算法与数据结构49niniicp 1=ACN212)(11)2(111=1nnnnnninni ACN查找算法时间效率分析查找算法时间效率分析算法与数据结构50 O( n )查找算法查找算法的的时间复杂度时间复杂度为为： O( ListLength(L) )算法与数据结构51线性表操作 ListInsert(&L, i, e)的实现

28、：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？算法与数据结构52 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的长度增加算法与数据结构53算法算法1：在线性表中指定位置前插入一个元素：在线性表中指定位置前插入一个元素 插入元素时，线性表的逻辑结构由插入元素时，线性表的逻辑结构由(a1, , ai-1, ai, , an)改变为改变为(a1, , ai-1, b, ai, , an),在第在第i-1个数个数据元素和第据元素和第i个

29、数据元素之间插入新的数据元素。个数据元素之间插入新的数据元素。 变成长度为n+1的线性表niiaaeaaa,1,21 需将第i至第n共（n-i+1)个元素后移niiaaaaa,1,21内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1e, 算法与数据结构551 1 2 1 1 2 2 1 3 2 1 3 3 2 1 3 2 1 4 2 4 4 2 4 5 2 8 5 2 5 6 3 0 6 2 8 7 4 2 7 3 0 8 7 7 8 4 2 9 7 7 图图 线

30、性表插入前后的状况线性表插入前后的状况(a)(a)插入前插入前n=8; (b)n=8; (b)插入后插入后n=9n=9插入插入2525算法与数据结构562512478936141234567892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次插入插入（插在第（插在第 i i 个结点之前）个结点之前）算法与数据结构57（1 1）判断）判断插入位置插入位置i i 是否合法是否合法

31、。（2 2）判断顺序表的）判断顺序表的存储空间是否已满存储空间是否已满。 （3 3）将第）将第n n至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空，空出第出第i i个位置。个位置。（4 4）将要插入的新元素）将要插入的新元素e e放入第放入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回OKOK。【算法思想算法思想】算法与数据结构588. 8. 在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e Status ListInsert_Sq(SqList &L,int i ,ElemType e

32、) if(iL.length+1) return ERROR; /i值不合法值不合法 if(L.length=MAXSIZE) return ERROR; /当前存储空间已满当前存储空间已满 for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /将新元素将新元素e放入第放入第i个位置个位置 +L.length; /表长增表长增1 return OK;【算法描述算法描述】算法与数据结构59若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；

33、若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【算法分析算法分析】考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定假定

34、在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：算法与数据结构61插入插入 算法时间复杂度算法时间复杂度为为: :O( ListLength(L) ) O( n )算法与数据结构62线性表操作 ListDelete(&L, i, &e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？算法与数据结构63 (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 算法与数据结构6425

35、1247893614123456789251247361425124736142512473614删除删除删除删除（删除第（删除第 i i 个结点）个结点）删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i i 个结点，移动个结点，移动 n-in-i 次次算法与数据结构65（1 1）判断）判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为1in1in）。）。（2 2）将欲删除的元素保留在）将欲删除的元素保留在e e中。中。 （3 3）将第）将第i+1i+1至第至第n n 位的元素依次位的元素依次向前移动一个位置向前移动一个位置。（4 4）表长减表长

36、减1 1，删除成功返回，删除成功返回OKOK。【算法思想算法思想】算法与数据结构669. 9. 将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除Status ListDelete_Sq(SqList &L,int i,ElemType &e) if(iL.length) return ERROR; /i值不合法值不合法 e=L.elemi-1; /将欲删除的元素保留在将欲删除的元素保留在e中中 for (j=i;jdata=ai, 则则p-next-data=ai+1 a1a2an.L算法与数据结构931. 1. 初始化线性表初始化线性表L InitList(L) L Init

37、List(L) 2. 2. 销毁线性表销毁线性表L DestoryList(L) L DestoryList(L) 3. 3. 清空线性表清空线性表L ClearList(L) L ClearList(L) 4. 4. 求线性表求线性表L L的长度的长度 ListLength(L)ListLength(L)5. 5. 判断线性表判断线性表L L是否为空是否为空 IsEmpty(L) IsEmpty(L) 6. 6. 获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,e) GetElem(L,i,e) 7. 7. 检索值为检索值为e e的数据元素的数据元

38、素 LocateELem(L,e)LocateELem(L,e) 8. 8. 在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,e)ListInsert(L,i,e)9. 9. 删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,e)ListDelete(L,i,e)2.3.2 2.3.2 单链表基本操作的实现单链表基本操作的实现算法与数据结构941.1.初始化初始化( (构造一个空表构造一个空表 )【算法思想算法思想】（1）生成新结点作头结点，用头指针）生成新结点作头结点，用头指针L指向头结点。指向头结点。（2）

39、头结点的指针域置空。）头结点的指针域置空。L【算法描述算法描述】Status InitList_L(LinkList &L) L=new LNode; L-next=NULL; return OK; 算法与数据结构952.2.销毁销毁Status DestroyList_L(LinkList &L) LinkList p; while(L) p=L; L=L-next; delete p; return OK; 算法与数据结构963.3.清空清空Status ClearList(LinkList & & L) / / 将将L L重置为空表重置为空表 LinkList p,q; p=L-next

40、; /p/p指向第一个结点指向第一个结点 while(p) /没到表尾没到表尾 q=p-next; delete p; p=q; L-next=NULL; /头结点指针域为空头结点指针域为空 return OK; 算法与数据结构974.4.求表长求表长int ListLength_L(LinkList L)/返回返回L L中数据元素个数中数据元素个数 LinkList p; p=L-next; /p/p指向第一个结点指向第一个结点 i=0; while(p) /遍历单链表遍历单链表, ,统计结点数统计结点数 i+; p=p-next; return i; 算法与数据结构985. 5. 判断表是

41、否为空判断表是否为空int ListEmpty(LinkList L) /若若L L为空表，则返回为空表，则返回1 1，否则返回，否则返回0 0 if(L-next) /非空非空 return 0; else return 1; 算法与数据结构99 按序号查找按序号查找 按值查找按值查找查找查找算法与数据结构100 思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？ 链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，

42、链表不是随机存取结构随机存取结构按序号查找按序号查找算法与数据结构101L 线性表的操作 GetElem(L, i, &e)在单链表中的实现:211830754256pppj1 2 3算法与数据结构102从第从第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

43、j= = i i时，时，p p所指的结点就是要找的第所指的结点就是要找的第i i个结点。个结点。【算法思想算法思想】按序号查找按序号查找算法与数据结构1036.6.获取线性表获取线性表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 按序号查找按序

44、号查找【算法描述算法描述】算法与数据结构104复杂度分析复杂度分析 查找第查找第 i 个数据元素的基本操作为：个数据元素的基本操作为：移动移动指针，比较指针，比较 j 和和 i 若若1i n,频度为频度为i-1. 若若in,频度为频度为n O(n)算法与数据结构105从第一个结点起，依次和从第一个结点起，依次和e e相比较。相比较。如果找到一个其值与如果找到一个其值与e e相等的数据元素，则返回其相等的数据元素，则返回其在链表中的在链表中的“位置位置”；如果查遍整个链表都没有找到其值和如果查遍整个链表都没有找到其值和e e相等的元素相等的元素，则返回，则返回“NULLNULL”。【算法思想算法

45、思想】按值查找按值查找算法与数据结构1067.7.在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素LNode *LocateELem_L (LinkList L，Elemtype e) p=L-next; while(p &p-data!=e) p=p-next; return p; /返回返回L中值为中值为e的数据元素的位置，查找失败返回的数据元素的位置，查找失败返回NULL 按值查找按值查找【算法描述算法描述】O(n)算法与数据结构107ai-1 线性表的操作 ListInsert(&L, i, e) 在单链表中的实现： 有序对有序对 改变为改变为 和和 eaiai-1

46、算法与数据结构108 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。 可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但同时，若要在第指针。但同时，若要在第 i 个结点之前个结点之前插入元素，修改的是第插入元素，修改的是第 i-1 个结点的指个结点的指针。针。算法与数据结构109 将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位个结点的位置上，即插入到置上，即插入到a ai-1i-

47、1与与a ai i之间之间插入插入（插在第（插在第 i i 个结点之前）个结点之前）s-next=p-next; p-next=s思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？算法与数据结构110 11:25 【算法思想算法思想】（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）生成一个新结点）生成一个新结点* *s s（3 3）将新结点）将新结点* *s s的数据域置为的数据域置为x x（4 4）新结点）新结点* *s s的指针域指向结点的指针域指向结点a ai i（5 5）令结点）令结点* *p p的指针域指向新结点的指针域指向新结点* *s s算法与数据结构

48、1118.8.在在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大于表长大于表长 + 1或者小于或者小于1 s=new LNode;/生成新结点生成新结点s s-data=e; /将结点将结点s的数据域置为的数据域置为e s-next=p-next; /将结点将结点s插入插入L中中 p-next=s; return OK; /ListIn

49、sert_L 【算法描述算法描述】 eai-1aiai-1sp算法的算法的时间复杂度时间复杂度为:O(ListLength(L)算法与数据结构112线性表的操作ListDelete (&L, i, &e)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1算法与数据结构113 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq

50、算法与数据结构114 将表的第将表的第i i个结点删去个结点删去 步骤：步骤：（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）保存要删除的结点的值）保存要删除的结点的值（3 3）令）令p-p-nextnext指向指向a ai i的直接后继结点的直接后继结点（4 4）释放结点）释放结点a ai i的空间的空间删除删除（删除第（删除第 i i 个结点）个结点）算法与数据结构115删除删除（删除第（删除第 i i 个结点）个结点）算法与数据结构116删除删除（删除第（删除第 i i 个结点）个结点）p-next = p-next-next ?ai-1ai-1aiaiai+1ai

51、+1pq删除前删除前删除后删除后算法与数据结构117【算法思想算法思想】（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）临时保存结点）临时保存结点a ai i的地址在的地址在q q中，以备释放中，以备释放（3 3）令）令p-nextp-next指向指向a ai i的直接后继结点的直接后继结点（4 4）将）将a ai i的值保留在的值保留在e e中中（5 5）释放）释放a ai i的空间的空间算法与数据结构118 11:25 9.9.将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除 Status ListDelete_L(LinkList &L,int i,

52、ElemType &e) p=L;j=0; while(p-next &jnext; +j; if(!(p-next)|ji-1) return ERROR; /删除位置不合理删除位置不合理 q=p-next; /临时保存被删结点的地址以备释放临时保存被删结点的地址以备释放 p-next=q-next; /改变删除结点前驱结点的指针域改变删除结点前驱结点的指针域 e=q-data; /保存删除结点的数据域保存删除结点的数据域 delete q; /释放删除结点的空间释放删除结点的空间 return OK; /ListDelete_L 【算法描述算法描述】算法与数据结构1191. 查找查找: 因

53、线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间复杂度为 O(n)。2. 插入和删除插入和删除: 因线性链表不需要移动元素，只要因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。链表的运算时间效率分析链表的运算时间效率分析算法与数据结构120如何从线性表得到单链表？如何从线性表得到单链

54、表？ (创建单链表创建单链表)链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” ” 的过程。的过程。算法与数据结构121n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：u生成新结点生成新结点u将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中u将该新结点插入到链表的前端将该新结点插入到链表的前端单链表的建立（前插法）单链表的建立（前插法） L L L L L e e a b L d c e d e b c d e c d 算法与数据结构122LpLanan

55、-1anLp单链表的建立（前插法）单链表的建立（前插法）算法与数据结构123void 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 【算法描述算法描述】算法与数据结构124n从一个空表从一个空表L开始，将新结点逐个插入到链表的尾部，尾指开始，将新结

56、点逐个插入到链表的尾部，尾指针针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 算法与数据结构125void CreateList_L(LinkList &L,int n) /正位序输入正位序输入n个元素的值，建立带表头结点的单链表个元素的值，建立带表头结

57、点的单链表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 【算法描述算法描述】算法与数据结构126思考思考 链表的输出算法与数据结构127不带头结点的单链表不带头结点的单链表( (自学自学) )算法与数据结构1281 建立单链表建立单链表: 设成员数据域为字符型（1）头插法建表头插法建表：依次插入新结点，并置于表头 a head b a he

58、ad b c a head b c 规律：新增加的结点指针域指向原head指向的结点，然后将原head指向新结点算法与数据结构129头插法建立单链表头插法建立单链表head 建立新节点 向新节点中添入内容 使新节点指向链首 改变头指针s算法与数据结构130头插法建立单链表头插法建立单链表linklist *CREATELIST() char ch; linklist *head,*s;headNULL; chgetchar(); while (ch!=$) smalloc(sizeof(linklist); s-datach; s-nexthead; heads; chgetchar(); r

59、eturn(head);head从键盘输入 o产生一个指针变量s1s1的数据域为ohead指向s1再输入k产生指针变量s2s2的数据域为ks2的指针域为s1head指向s2算法与数据结构131(2) 尾插法建表尾插法建表：插入的新结点置于表尾 产生一个新结点； 新结点的数据域为插入字符； 原尾结点（由尾指针指定）的指针域为新结点； 尾指针指向新结点； 新结点的指针域为空 a head a head b a head b c tailtailtail算法与数据结构132尾插法建立单链表尾插法建立单链表head 建立新节点 向新节点中添入内容 将新节点链入链尾 改变尾指针s算法与数据结构133li

60、nklist *CREATELISTR() char ch; linklist *head,*s,*r; headNULL; rNULL; chgetchar(); while(ch!=$) smalloc(sizeof(linklist); s-datach; if (head=NULL) heads; else r-nexts; rs; chgetchar(); 尾插法建立单链表尾插法建立单链表 if (r!=NULL) r-nextNULL; return head;算法与数据结构134 算法与数据结构135算法与数据结构136 单链表特点单链表特点它是一种动态结构，整个存储空间为多它是