线性表(余云)

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章线性表章线性表教教 学学 目目 标标1. 了解线性结构的特点了解线性结构的特点2.2.掌握

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

4、：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai i的直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点引引 例例 （ A, B, C, D, , ZA, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级计算机级计算机1 1班班041810260041810260何仕鹏何仕鹏男男 20 20

5、0404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 190404级计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班： ：数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性数据元素都是数据元素都是字母字母; ; 元素间元素间关系是线性关系是线性抽象数据类型的定义为抽象数据类型的定义为线性表的基本操作线性表的基本操作1. 1. 初始化线性表初始化线性表L InitList(L) L InitList(

6、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的数据元素的数据元素 Loc

7、ateELem(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.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续

8、的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组elemnelemn来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。 元素元素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 MAXSIZE 100 /

9、最大长度最大长度typedef struct typedef struct ElemType ElemType * *elem; /elem; /指向数据元素的基地址指向数据元素的基地址 int length; /int length; /线性表的当前长度线性表的当前长度 SqListSqList；数据结构基本运算操作有：数据结构基本运算操作有：查找、插入、删除查找、插入、删除malloc(malloc(m m) )：开辟：开辟m m字节长度的地址空间，字节长度的地址空间，并返回这段空间的首地址并返回这段空间的首地址sizeof(sizeof(x x) )：计算变量：计算变量x x的长度的长度

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

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

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

13、; cinab; p1=&a; p2=&b; swap(p1, p2);coutaendlbendl;#include void swap(float *m,float *n)float t; t=*m; *m=*n; *n=t;形参变化影响实参形参变化影响实参2）传地址方式指针变量作参数）传地址方式指针变量作参数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;

14、t=m; m=n; n=t;形参变化不影响实参？形参变化不影响实参？3)传地址方式传地址方式引用类型作参数引用类型作参数引用：它用来给一个对象提供一个替代的名字。引用：它用来给一个对象提供一个替代的名字。#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;传地址传地址方式方式引用类型作参数引用类型作参数3）传地址方式引用类型作参数）传地址方式引用类型

15、作参数（1 1）传递引用给函数与传递指针的效果是一）传递引用给函数与传递指针的效果是一样的，样的，形参变化实参也发生变化形参变化实参也发生变化。（2 2）引用类型作形参，在内存中并没有产生）引用类型作形参，在内存中并没有产生实参的副本，它实参的副本，它直接对实参操作直接对实参操作；而一般变；而一般变量作参数，形参与实参就占用不同的存储单量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。元，所以形参变量的值是实参变量的副本。因此，当因此，当参数传递的数据量较大参数传递的数据量较大时，用引用时，用引用比用一般变量传递参数的时间和空间效率都比用一般变量传递参数的时间和空间效

16、率都好。好。引用类型作形参的三点说明引用类型作形参的三点说明3）传地址方式引用类型作参数）传地址方式引用类型作参数引用类型作形参的三点说明引用类型作形参的三点说明（3）指针参数虽然也能达到与使用引用的效）指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用果，但在被调函数中需要重复使用“* *指针指针变量名变量名”的形式进行运算，这很容易产生错的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用函数的调用点处，必须用变量的地址作为实变量的地址作为实参参。4）传地址方式数组名作参数）传地址方式数组名作参数#i

17、ncludevoid sub(char);void main（void ） char a10=“hello”; sub(a); coutaendl;void sub(char 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

18、; n=b0; for(i=1;iN;i+)if(nbi) n=bi; return n;用数组作函数的参数，求用数组作函数的参数，求10个整数的最大数个整数的最大数练习：练习：用数组作为函数的参数，将数组中用数组作为函数的参数，将数组中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 ( )

19、 int a10,i;for(i=0;iai;sub(a);for(i=0;iN;i+)cout elem=new ElemTypeMAXSIZE; /为顺序表分配空间为顺序表分配空间 if(! L- elem) exit(OVERFLOW); /存储分配失败存储分配失败 L- length=0; /空表长度为空表长度为0 return OK;2. 2. 销毁线性表销毁线性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) delet

20、eL.elem; /释放存储空间释放存储空间 3. 3. 清空线性表清空线性表L Lvoid ClearList(SqList &L) L.length=0; /将线性表的长度置为将线性表的长度置为04.4. 求线性表求线性表L L的长度的长度int GetLength(SqList L) return (L.length); 5.5.判断线性表判断线性表L L是否为空是否为空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0; 6. 6. 获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容/根

21、据指定位置，获取相应位置数据元素的内容根据指定位置，获取相应位置数据元素的内容int 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 O

22、K;return OK; 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 16 48 查找失败查找失败查找算法时间效率分析查找算法时间效率分析7. 7. 在线性表在线性表

23、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;niniicp 1=ACN212)(11)2(111=1nnnnnninni ACN查找算法时间效率分析查找算法时间效率分析2512478936141234567892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插

24、在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次插入插入（插在第（插在第 i i 个结点之前）个结点之前）（1 1）判断）判断插入位置插入位置i i 是否合法是否合法。（2 2）判断顺序表的）判断顺序表的存储空间是否已满存储空间是否已满。 （3 3）将第）将第n n至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空，空出第出第i i个位置。个位置。（4 4）将要插入的新元素）将要插入的新元素e e放入第放入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回OKOK。【算法思想】【算法思想】8. 8. 在线性表

25、在线性表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+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /将新元素将新元素e放入第放入第i个位置个位置

26、 +L.length; /表长增表长增1 return OK;【算法描述】【算法描述】221)(1)(1 0)1(11)(11=1nnnnnn1inn1niAMN若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【算法分析】【算法分析】251247893

27、614123456789251247361425124736142512473614删除删除删除删除（删除第（删除第 i i 个结点）个结点）删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i i 个结点，移动个结点，移动 n-in-i 次次（1 1）判断）判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为1in1in）。）。（2 2）将欲删除的元素保留在）将欲删除的元素保留在e e中。中。 （3 3）将第）将第i+1i+1至第至第n n 位的元素依次位的元素依次向前移动一个位置向前移动一个位置。（4 4）表长减表长减1 1，删除成功返回，删除成功

28、返回OKOK。【算法思想】【算法思想】9. 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.L1. 1. 初始化线性表初始化线性表L InitList(L) L InitList(L) 2. 2. 销毁线性表销毁线性表

29、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的数据元素的数据元素 LocateELem(L,e)LocateE

30、Lem(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 单链表基本操作的实现单链表基本操作的实现【算法思想】【算法思想】（1）生成新结点作头结点，用头指针）生成新结点作头结点，用头指针L指向头结点。指向头结点。（2）头结点的指针域置空。）头结点的指针域置空。L【算法描述】【算法描述】LinkList InitList_L(Link

31、List &L) L=new LNode; L-next=NULL; return L; 1.1.初始化初始化( (构造一个空表构造一个空表 ) )void DestroyList_L(LinkList &L) LinkList p; while(L) p=L; L=L-next; delete p; 2.2.销毁销毁a1ana2.Lpint ClearList(LinkList & & L) / / 将将L L重置为空表重置为空表 LinkList p,q; p=L-next; /p/p指向第一个结点指向第一个结点 while(p) /没到表尾没到表尾 q=p

32、-next; delete p; p=q; L-next=NULL; /头结点指针域为空头结点指针域为空 return 1; 3.3.清空清空a1a2.anLqpppppint ListLength_L(LinkList L)/返回返回L L中数据元素个数中数据元素个数 LinkList p; p=L-next; /p/p指向第一个结点指向第一个结点 int i=0; while(p) /遍历单链表遍历单链表, ,统计结点数统计结点数 i+; p=p-next; return i; 4.4.求表长求表长int ListEmpty(LinkList L) /若若L L为空表，则返回为空表，则返回

33、1 1，否则返回，否则返回0 0 if(L-next) /非空非空 return 0; else return 1; 5. 5. 判断表是否为空判断表是否为空 按序号查找按序号查找 按值查找按值查找6. 6. 查找查找 思考：链表里如何找到第思考：链表里如何找到第i i个元素？个元素？ 链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构按序号查找按序号查找从第从第1 1个结点（个结点（L-nextL-ne

34、xt）顺链扫描，用指针）顺链扫描，用指针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个结点。个结点。【算法思想】【算法思想】按序号查找按序号查找6.6.获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容LinkList GetElem_L

35、(LinkList L,int i) p=L-next; j=1; /初始化初始化 while(p&jnext; +j; if(!p | ji) return NULL; /第第i个元素不存在个元素不存在 return p; /GetElem_L 按序号查按序号查找找【算法描述】【算法描述】从第一个结点起，依次和从第一个结点起，依次和e e相比较。相比较。如果找到一个其值与如果找到一个其值与e e相等的数据元素，则返回其相等的数据元素，则返回其在链表中的在链表中的“位置位置”；如果查遍整个链表都没有找到其值和如果查遍整个链表都没有找到其值和e e相等的元素相等的元素，则返回，则返回“N

36、ULLNULL”。【算法思想】【算法思想】按值查找按值查找7.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 按值查找按值查找【算法描述】【算法描述】 将值为将值为x x的新结点插入到的新结点插入到p p结点后，结点后， 如何插入？如何插入？8.8.插入插入（在（在p p结点后插入元

37、素结点后插入元素x x）s-next=p-next; 思考：步骤和能互换么？思考：步骤和能互换么？a1ana3.Lpa2xss=new LNode; s-data=x; p-next=s；【算法思想】【算法思想】（1 1）生成一个新结点生成一个新结点*s（2 2）将新结点将新结点*s的数据域置为的数据域置为x（3 3）新结点新结点*s的指针域指向结点的指针域指向结点p的后继的后继（4 4）令结点）令结点* *p p的指针域指向新结点的指针域指向新结点* *s s？将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上，即插入到个结点的位置上，即插入到a ai-1i-1与

38、与a ai i之间。之间。8.8.插入插入（插在第（插在第 i i 个结点之前）个结点之前）查查 找找【算法思想】【算法思想】（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 ss-next=p-next;p-next=s；8.8.在在L L中第中第i i个元素之前插入数据元素个元素之前插入数据元素e e

39、 LinkList ListInsert_L(LinkList L,int i,ElemType e) LinkList p=L; int j=0; while(p&jnext;+j;/寻找第寻找第i1个结点个结点 if(!p|ji1)return NULL;/i大于表长大于表长 + 1或者小于或者小于1 LinkList s=new LNode;/生成新结点生成新结点s s-data=e; /将结点将结点s的数据域置为的数据域置为e s-next=p-next; /将结点将结点s插入插入L中中 p-next=s; return L; /ListInsert_L 【算法描述】【算法描述

40、】 将表的第将表的第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的空间的空间9.9.删除删除（删除第（删除第 i i 个结点）个结点）p-next = p-next-next ?ai-1ai-1aiaiai+1ai+1pq删除前删除前删除后删除后删除删除（删除第（删除第 i i 个结点）个结点）【算法思想】【算法思想】（1 1）找到）找到a ai-1i-1存储位

41、置存储位置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的空间的空间9.9.将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除 LinkList ListDelete_L(LinkList L,int i,ElemType *e) LinkList p=L,q; int j=0; while(p-next &jnext; +j; if(!(p-

42、next)|ji-1) return NULL; /删除位置不合理删除位置不合理 q=p-next; /临时保存被删结点的地址以备释放临时保存被删结点的地址以备释放 p-next=q-next; /改变删除结点前驱结点的指针域改变删除结点前驱结点的指针域 *e=q-data; /保存删除结点的数据域保存删除结点的数据域 delete q; /释放删除结点的空间释放删除结点的空间 return L; /ListDelete_L 【算法描述】【算法描述】1. 查找查找: 因线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间

43、复杂度为 O(n)。2. 插入和删除插入和删除: 因线性链表不需要移动元素，只要因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行前插或删除操作，但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。链表的运算时间效率分析链表的运算时间效率分析n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：u生成新结点生成新结点u将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中u将该新结点插入到链表的前端将该新结点插

44、入到链表的前端单链表的建立（前插法）单链表的建立（前插法） L L L L L e e a b L d c e d e b c d e c d LpLanan-1anLp单链表的建立（前插法）单链表的建立（前插法）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; /插入到表头插入到表头

45、 /CreateList_F 【算法描述】【算法描述】n从一个空表从一个空表L开始，将新结点逐个插入到链表的尾部，尾指开始，将新结点逐个插入到链表的尾部，尾指针针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 2.3.3 2.3.3 循环链表循环链表L-n

46、ext=L.H(a) (a) 非空单循环链表非空单循环链表LH(b) (b) 空表空表L.BAp=B-next-next; B-next=A-next;A-next=p.A.B循环链表的合并循环链表的合并priordatanextdatanexttypedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList2.3.4 2.3.4 双向链表双向链表L(a) (a) 空双向循环链表空双向循环链表LABC(b) (b) 双向循环链表双向循环链表d-next-

47、prior = d-prior-next = dL-next=Lab.p双向链表的插入双向链表的插入1. s-prior=p-prior;a ab bx x.1 1p ps s22. p-prior-next=s;33. s-next=p;44. p-prior=s;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

48、-prior=s; return OK;双向链表的插入双向链表的插入ab.pc双向链表的删除双向链表的删除1. p-prior-next=p-next;ab.12pc2. p-next-prior=p-prior;Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e) if(!(p=GetElemP_DuL(L,i) return ERROR; e=p-data; p-prior-next=p-next; p-next-prior=p-prior; delete p; return OK;双向链表的删除双向链表的删除2.4

49、2.4 线性表的应用线性表的应用2.4.12.4.1线性表的合并线性表的合并问题描述：问题描述： 假设利用两个线性表假设利用两个线性表LaLa和和LbLb分别表示两分别表示两个集合个集合A A和和B,B,现要求一个新的集合现要求一个新的集合 A=ABLa=(7, 5, 3, 11)Lb=(2, 6, 3)La=(7, 5, 3, 11, 2, 6) 依次取出依次取出Lb Lb 中的每个元素，执行以下操作：中的每个元素，执行以下操作：在在LaLa中查找该元素中查找该元素如果找不到，则将其插入如果找不到，则将其插入La的最后的最后【算法思想】【算法思想】void union(List &L

50、a, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i=Lb_len;i+) GetElem(Lb,i,e); if(!LocateElem(La,e) ListInsert(&La,+La_len,e); )()(LBListLengthLAListLengthO【算法描述】【算法描述】问题描述：问题描述： 已知线性表已知线性表La La 和和LbLb中的数据元素按值中的数据元素按值非递减非递减有有序排列序排列, ,现要求将现要求将LaLa和和LbLb归并为一个新的线性表归并为一个新的线性表LcLc, ,

51、且且LcLc中的数据元素仍按值非递减有序排列中的数据元素仍按值非递减有序排列. .La=(1 ,7, 8)Lb=(2, 4, 6, 8, 10, 11)Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) .2.4.22.4.2有序表的合并有序表的合并(1) (1) 创建一个空表创建一个空表LcLc(2) 依次从依次从 La La 或或 Lb Lb 中中“摘取摘取”元素值较小元素值较小的结点插入到的结点插入到 Lc Lc 表的最后，直至其中一个表表的最后，直至其中一个表变空为止变空为止(3) (3) 继续将继续将 La La 或或 Lb Lb 其中一个表的剩余结点其中一个表的剩余

52、结点插入在插入在 Lc Lc 表的最后表的最后【算法思想】【算法思想】有序的顺序表合并有序的顺序表合并void MergeList_Sq(SqList LA,SqList LB,SqList &LC) pa=LA.elem; pb=LB.elem; /指针指针pa和和pb的初值分别指向两个表的第一个元素的初值分别指向两个表的第一个元素 LC.length=LA.length+LB.length; /新表长度为待合并两表的长度之和新表长度为待合并两表的长度之和 LC.elem=new ElemTypeLC.length; /为合并后的新表分配一个数组空间为合并后的新表分配一个数组空间 p

53、c=LC.elem; /指针指针pc指向新表的第一个元素指向新表的第一个元素 pa_last=LA.elem+LA.length-1; /指针指针pa_last指向指向LA表的最后一个元素表的最后一个元素 pb_last=LB.elem+LB.length-1; /指针指针pb_last指向指向LB表的最后一个元素表的最后一个元素 while(pa=pa_last & pb=pb_last) /两个表都非空两个表都非空 if(*pa=*pb) *pc+=*pa+; /依次依次“摘取摘取”两表中值较小的结点插入到两表中值较小的结点插入到 LC表的最后表的最后 else *pc+=*pb+; while(pa=pa_last) *pc+=*pa+; /LB表已到达表尾，依次将表已到达表尾，依次将LA的剩余元素插