1、国际教育学院国际教育学院 第第2 2章章 线性表线性表 第第3 3章章 栈和队列栈和队列 第第4 4章章 串串 第第5 5章章 数组和广义表数组和广义表 线性结构线性结构若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1,a,a2 2 ,a,an n）（逻辑、存储（逻辑、存储和运算）和运算）国际教育学院国际教育学院 只有一个首结点和尾结点；只有一个首结点和尾结点；除首尾结点外，其他结点只有一个直
2、接前驱和一除首尾结点外，其他结点只有一个直接前驱和一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a a1 1,a,a2 2 ,a,an n）线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的国际教育学院国际教育学院第第2 2章章线性表线性表1.了解线性结构的特点了解线性结构的特点2.2.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3.3.掌握链表的定
3、义、查找、插入和删除掌握链表的定义、查找、插入和删除 4.4.能够从时间和空间复杂度的角度比较两种能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合存储结构的不同特点及其适用场合 教学目标教学目标国际教育学院国际教育学院2.1 线性表的类型定义线性表的类型定义2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现教学内容教学内容国际教育学院国际教育学院（a1,a2,ai-1，ai,ai1，,an）线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元素线性起点线性起点a
4、i的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的类型定义线性表的类型定义国际教育学院国际教育学院 （A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级计算机级计算机1 1班班041810260041810260何仕鹏何仕鹏男男 20 200404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 190404级
5、计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班：数据元素都是记录数据元素都是记录;元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母;元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性国际教育学院国际教育学院线性表的基本操作线性表的基本操作1.1.初始化线性表初始化线性表L InitList(LL InitList(L)2.2.销毁线性表销毁线性表L DestoryList(LL DestoryList(L)3.3.清空线性表清空线性表L ClearLis
6、t(LL ClearList(L)4.4.求线性表求线性表L L的长度的长度 ListLength(LListLength(L)5.5.判断线性表判断线性表L L是否为空是否为空 IsEmpty(LIsEmpty(L)6.6.获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,eGetElem(L,i,e)7.7.检索值为检索值为e e的数据元素的数据元素 LocateELem(L,eLocateELem(L,e)8.8.返回线性表返回线性表L L中中e e的直接前驱元素的直接前驱元素 PriorElem(L,ePriorElem(L,e)9.9.返回线
7、性表返回线性表L L中中e e的直接后继元素的直接后继元素 NextElem(L,eNextElem(L,e)10.10.在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,eListInsert(L,i,e)11.11.删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,eListDelete(L,i,e)国际教育学院国际教育学院算法算法2.12.1、2.22.2、2.72.7、2.122.12放在放在后面统一讲解后面统一讲解国际教育学院国际教育学院2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表
8、的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组VnVn来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。国际教育学院国际教育学院元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m
9、存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储国际教育学院国际教育学院#define LIST_INIT_SIZE 100 /#define LIST_INIT_SIZE 100 /最大长度最大长度#define LISTINCREMENT 10#define LISTINCREMENT 10 /分配增量分配增量typedef structtypedef struct ElemType ElemType *elemelem;/;/指向数据元素的基地址指向数据元素的基地址 intint length;/length;/线性表的当前长度线性表的当前长度
10、int listsizeint listsize；/当前分配的存储容量当前分配的存储容量 SqListSqList；顺序表的类型定义顺序表的类型定义数据结构基本运算操作有：数据结构基本运算操作有：查找、插入、删除查找、插入、删除国际教育学院国际教育学院malloc(malloc(m m)：开辟：开辟m m字节长度的地址空间，字节长度的地址空间，并返回这段空间的首地址并返回这段空间的首地址sizeof(sizeof(x x)：计算变量：计算变量x x的长度的长度free(free(p p)：释放指针：释放指针p p所指变量的存储空间所指变量的存储空间，即彻底删除一个变量，即彻底删除一个变量补充：
11、补充：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功能：功能：释放指针释放指针P P所指向的内存。所指向的内存。P P必须是必须是newnew操作的
12、返回值操作的返回值delete p1;补充：补充：C+C+的动态存储分配的动态存储分配国际教育学院国际教育学院n函数调用时传送给形参表的实参必须与形参在类函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致型、个数、顺序上保持一致n参数传递有两种方式参数传递有两种方式n传值方式传值方式（参数为整型、实型、字符型等）（参数为整型、实型、字符型等）n传地址传地址参数为指针变量参数为指针变量参数为引用类型参数为引用类型参数为数组名参数为数组名补充：补充：C+C+中的参数传递中的参数传递国际教育学院国际教育学院void main()float a,b;cinab;swap(a,b);co
13、utaendlbendl;#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;swap(p1,p2);coutaendlbe
14、ndl;#include void swap(float*m,float*n)float t;t=*m;*m=*n;*n=t;形参变化影响实参形参变化影响实参国际教育学院国际教育学院传地址传地址方式方式指针变量作参数指针变量作参数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;形参变化不影响实参？形参变化不影响实参？国际教育学院国际教育学院传地址传地址方式方式引用类型作参数引用类型作参数
15、引用：它用来给一个对象提供一个替代的名字。引用：它用来给一个对象提供一个替代的名字。#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）传递引用给函数与传递指针的效果是一）传递引用给函数与传递指针的效果是一样的，样的，形参变化实参也发生变化形参变化实参也发生变化。（2 2）引用类型作形参
16、，在内存中并没有产生）引用类型作形参，在内存中并没有产生实参的副本，它实参的副本，它直接对实参操作直接对实参操作；而一般变；而一般变量作参数，形参与实参就占用不同的存储单量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。元，所以形参变量的值是实参变量的副本。因此，当因此，当参数传递的数据量较大参数传递的数据量较大时，用引用时，用引用比用一般变量传递参数的时间和空间效率都比用一般变量传递参数的时间和空间效率都好。好。引用类型作形参的三点说明引用类型作形参的三点说明国际教育学院国际教育学院（3）指针参数虽然也能达到与使用引用的效）指针参数虽然也能达到与使用引用的效果，但在
17、被调函数中需要重复使用果，但在被调函数中需要重复使用“*指针指针变量名变量名”的形式进行运算，这很容易产生错的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用函数的调用点处，必须用变量的地址作为实变量的地址作为实参参。引用类型作形参的三点说明引用类型作形参的三点说明国际教育学院国际教育学院传地址传地址方式方式数组名作参数数组名作参数#includevoid sub(char);void main（void）char a10=“hello”;sub(a);coutaendl;void sub(char b)b=“wor
18、ld”;传递的是数组的首地址传递的是数组的首地址对形参数组所做的任何改变都将反映到实参数组中对形参数组所做的任何改变都将反映到实参数组中国际教育学院国际教育学院#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个整数的最大数个整数的最大数国际教育学院国际教育学院练
19、习：练习：用数组作为函数的参数，将数组中用数组作为函数的参数，将数组中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+)coutelemL-elem=(ElemType=(ElemType*)malloc(LIST_INI
20、T_SIZE)malloc(LIST_INIT_SIZE*sizeof(ElemTypesizeof(ElemType););/分配空间分配空间 if(L-elemif(L-elem=NULL)exit(OVERFLOW);/=NULL)exit(OVERFLOW);/分配失败分配失败 L-length=0;/L-length=0;/空表长度置空表长度置0 0 return OK;/return OK;/成功返回成功返回OKOK 典型操作的算法实现典型操作的算法实现国际教育学院国际教育学院2.2.销毁线性表销毁线性表L Lvoid DestroyList(SqListvoid DestroyL
21、ist(SqList&L)&L)if(L.elem if(L.elem)free(L.elem)free(L.elem);/);/释放存储空间释放存储空间 3.3.清空线性表清空线性表L Lvoid ClearList(SqList&L)L.length=0;/将线性表的长度置为将线性表的长度置为0国际教育学院国际教育学院4.4.求线性表求线性表L L的长度的长度int GetLength(SqList&L)return(L.length);5.5.判断线性表判断线性表L L是否为空是否为空int IsEmpty(SqList&L)if(L.length=0)return TRUE;else
22、return FALSE;国际教育学院国际教育学院6.6.获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容/根据指定位置，获取相应位置数据元素的内容根据指定位置，获取相应位置数据元素的内容intint GetElem(SqList GetElem(SqList&L,int&L,int i,ElemTypei,ElemType&e&e)if(iL.length)return ERROR;if(iL.length)return ERROR;/判断判断i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=L.elemi-1;e=L.elemi-1;
23、/第第i-1i-1的单元存储着第的单元存储着第i i个数据个数据 return OK;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
24、 57 16 48 i25 34 57 16 48 i查找失败查找失败国际教育学院国际教育学院查找算法时间效率分析查找算法时间效率分析7.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;国际教育学院国际教育学院niniicp 1=ACN212)(11)2(111=1nnnnnninni ACN查找算法时间效率分析查找算法时间效率分析国际教育学院国际教育学院2512478936141234567
25、892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次插入插入（插在第（插在第 i i 个结点之前）个结点之前）国际教育学院国际教育学院实现步骤：实现步骤：事先应判断事先应判断:插入位置插入位置i i 是否合法是否合法?表是否已满表是否已满?应当有应当有1in+1 1in+1 或或 i=1,n+1i=1,n+1将第将第n n至第至第i i 位的元素向后移动一个位的元素向后移动一
26、个位置；位置；将要插入的元素写到第将要插入的元素写到第i i个位置；个位置；表长加表长加1 1。国际教育学院国际教育学院8.8.在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e intint ListInsert(SqList ListInsert(SqList&L,int&L,int i,ElemType i,ElemType&e)&e)if(L.length=LIST_INIT_SIZE)return ERROR;if(L.length=LIST_INIT_SIZE)return ERROR;/检查是否有剩余空间检查是否有剩余空间 if(iL.
27、length+1)if(iL.length+1)return ERROR;/return ERROR;/检查检查i i值是否合理值是否合理 for(j=L.length-1;j=i-1;j-)for(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj L.elemj+1=L.elemj;/;/将第将第i i个之后的依次向后移动个之后的依次向后移动 L.elemi-1=e;/L.elemi-1=e;/将新元素放入第将新元素放入第i i个位置个位置 L.length+;L.length+;return OK;return OK;国际教育学院国际教育学院若插入在尾结点之后
28、，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上插入算法时间效率分析插入算法时间效率分析221)(1)(1 0)1(11)(11=1nnnnnn1inn1niAMN国际教育学院国际教育学院25124789361412345678925124736142512473614
29、2512473614删除删除删除删除（删除第（删除第 i i 个结点）个结点）删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i i 个结点，移动个结点，移动 n-in-i 次次国际教育学院国际教育学院实现步骤：实现步骤：事先需要判断，事先需要判断，删除位置删除位置i i 是否合是否合法法?应当有应当有1in 1in 或或 i=1,ni=1,n将第将第i+1i+1至第至第n n 位的元素向前移动位的元素向前移动一个位置；一个位置；表长减表长减1 1。国际教育学院国际教育学院9.9.将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除intint Li
30、stDelete(SqList ListDelete(SqList&L,int&L,int i,ElemType i,ElemType&e)&e)if(IsEmpty(L if(IsEmpty(L)return ERROR;/)return ERROR;/检测是否为空检测是否为空 if(iL.length)return ERROR;/if(iL.length)return ERROR;/检查检查i i值是否合理值是否合理 e=L.elemi-1;/e=L.elemi-1;/将欲删除的元素保留在将欲删除的元素保留在e e中中 for(j=i;j=L.length-1;j+)for(j=i;jda
31、ta=ai,则则p-next-data=ai+1 a1a2an.L国际教育学院国际教育学院线性表的基本操作线性表的基本操作1.1.初始化线性表初始化线性表L InitList(LL InitList(L)2.2.销毁线性表销毁线性表L DestoryList(LL DestoryList(L)3.3.清空线性表清空线性表L ClearList(LL ClearList(L)4.4.求线性表求线性表L L的长度的长度 ListLength(LListLength(L)5.5.判断线性表判断线性表L L是否为空是否为空 IsEmpty(LIsEmpty(L)6.6.获取线性表获取线性表L L中的某
32、个数据元素内容中的某个数据元素内容 GetElem(L,i,eGetElem(L,i,e)7.7.检索值为检索值为e e的数据元素的数据元素 LocateELem(L,eLocateELem(L,e)8.8.返回线性表返回线性表L L中中e e的直接前驱元素的直接前驱元素 PriorElem(L,ePriorElem(L,e)9.9.返回线性表返回线性表L L中中e e的直接后继元素的直接后继元素 NextElem(L,eNextElem(L,e)10.10.在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,eListInsert(L,i,e)11.11
33、.删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,eListDelete(L,i,e)国际教育学院国际教育学院1.1.初始化单链表初始化单链表Status InitList_L(LinkListStatus InitList_L(LinkList&L)&L)/构造一个空的线性表构造一个空的线性表L L L=(LinkList L=(LinkList)malloc(sizeof(LNode)malloc(sizeof(LNode););if(!L)return OVERFLOW;if(!L)return OVERFLOW;/3/3 L-next=NUL
34、L;L-next=NULL;return OK;return OK;国际教育学院国际教育学院2.2.销毁单链表销毁单链表Status DestroyList_L(LinkListStatus DestroyList_L(LinkList&L)&L)LinkList LinkList p;p;while(L)while(L)p=L;p=L;L=L-next;L=L-next;free(p);free(p);return OK;return OK;国际教育学院国际教育学院3.3.清空单链表清空单链表Status ClearList(LinkList&L)/将将L L重置为空表重置为空表 LinkL
35、ist p,q;p=L-next;/p/p指向第一个结点指向第一个结点 while(p)/没到表尾没到表尾 q=p-next;free(p);p=q;L-next=NULL;/头结点指针域为空头结点指针域为空 return OK;国际教育学院国际教育学院4.4.求线性表求线性表L L的长度的长度int ListLength_L(LinkList L)/返回返回L L中数据元素个数中数据元素个数 LinkList p;p=L-next;/p/p指向第一个结点指向第一个结点 i=0;while(p)/遍历单链表遍历单链表,统计结点数统计结点数 i+;p=p-next;return i;国际教育学院
36、国际教育学院5.5.判断线性表判断线性表L L是否为空是否为空Status ListEmpty(LinkList L)/若若L L为空表，则返回为空表，则返回TRUETRUE，否则返回，否则返回FALSE FALSE if(L-next)/非空非空 return FALSE;else return TRUE;国际教育学院国际教育学院 按序号查找按序号查找 按值查找按值查找查找查找国际教育学院国际教育学院 思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至
37、逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构按序号查找按序号查找国际教育学院国际教育学院 计数器计数器j j置为置为1 1，指针，指针p p从首元结点顺链扫描从首元结点顺链扫描 当当p p扫描下一结点时，扫描下一结点时，j j相应地加相应地加1 1 j=ij=i时，时，p p所指结点就是要找的第所指结点就是要找的第i i个结点个结点 p p为为nullnull且且jiji时，表示时，表示i i大于表长大于表长 jiji时，表示时，表示i i小于小于1 1按序号查找的思想按序号查找的思想国际教育学院国际教育学院6.6.获
38、取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容（算法（算法2.8）Status GetElem_L(LinkList L,int i,Elemtype&e)LinkList p;p=L-next;/初始化初始化,p,p指向第一个结点指向第一个结点 j=1;/j/j为计数器为计数器 while(p&jnext;+j;if(!p|ji)return ERROR;/i/i大于表长或小于大于表长或小于1 1 e=p-data;/取第取第i i个元素个元素 return OK;按序号查找按序号查找国际教育学院国际教育学院从首元结点出发，顺着链逐个将结点的值从首元结点出发，顺着链逐个
39、将结点的值和给定值和给定值keykey作比较作比较若有结点与若有结点与keykey相等，则返回值为相等，则返回值为keykey的结点位置的结点位置否则返回否则返回NULLNULL按值查找的思想按值查找的思想国际教育学院国际教育学院7.7.在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素LNode*LocateELem(LinkList L,Elemtype e)LinkList p;p=L-next;while(p&p-data!=e)p=p-next;/寻找满足条件的结点寻找满足条件的结点 return(p);/返回返回L L中值为中值为e e的数据元素的位置的数据元素的
40、位置按值查找按值查找国际教育学院国际教育学院8.8.返回线性表返回线性表L L中中e e的直接前驱元素的直接前驱元素 Status PriorElem(LinkList L,ElemType cur_e,ElemType*pre_e)/若若cur_e是是L的数据元素的数据元素,且不是第一个且不是第一个,则用则用pre_e返回它的前驱返回它的前驱,返回返回OK;否则操作失败否则操作失败,pre_e无定义无定义,返回返回INFEASIBLE LinkList q,p=L-next;/p指向第一个结点指向第一个结点 while(p-next)/p所指结点有后继所指结点有后继 q=p-next;if(
41、q-data=cur_e)*pre_e=p-data;return OK;p=q;/*p向后移向后移*/return INFEASIBLE;国际教育学院国际教育学院9.9.返回线性表返回线性表L L中中e e的直接后继元素的直接后继元素 Status NextElem(LinkList L,ElemType cur_e,ElemType*next_e)/若若cur_e是是L的数据元素，且不是最后一个，则用的数据元素，且不是最后一个，则用next_e返回它返回它的后继的后继,返回返回OK;否则操作失败，否则操作失败，next_e无定义，返回无定义，返回INFEASIBLE*/LinkList p
42、=L-next;/*p指向第一个结点指向第一个结点*/while(p-next)/*p所指结点有后继所指结点有后继*/if(p-data=cur_e)*next_e=p-next-data;return OK;p=p-next;return INFEASIBLE;国际教育学院国际教育学院 将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置个结点的位置上，即插入到上，即插入到a ai-1i-1与与a ai i之间之间 步骤：步骤：（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）生成一个新结点）生成一个新结点*s s（3 3）将新结点）将新结点*s
43、s的数据域置为的数据域置为x x（4 4）新结点）新结点*s s的指针域指向结点的指针域指向结点a ai i（5 5）令结点）令结点*p p的指针域指向新结点的指针域指向新结点*s s插入插入（插在第（插在第 i i 个结点之前）个结点之前）国际教育学院国际教育学院s-next=p-next;p-next=s插入插入（插在第（插在第 i i 个结点之前）个结点之前）思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？国际教育学院国际教育学院10.10.在在L L中第中第i i个元素之前插入数据元素个元素之前插入数据元素e e （算法（算法2.9）Status ListInsert_L(Li
44、nkList&L,int i,ElemType e)p=L;j=0;while(p&jnext;+j;/寻找第寻找第i-1个结点个结点 if(!p|ji-1)return ERROR;/i大于表长加大于表长加1或小于或小于1 s=(LinkList)malloc(sizeof(LNode);/生成新结点生成新结点 s-data=e;/插入插入L中中 s-next=p-next;p-next=s;return OK;插入插入（插在第（插在第 i i 个结点之前）个结点之前）国际教育学院国际教育学院 将表的第将表的第i i个结点删去个结点删去 步骤：步骤：（1 1）找到）找到a ai-1i-1存储
45、位置存储位置p p（2 2）保存要删除的结点的值）保存要删除的结点的值（3 3）令）令p-p-nextnext指向指向a ai i的直接后继结点的直接后继结点（4 4）释放结点）释放结点a ai i的空间的空间删除删除（删除第（删除第 i i 个结点）个结点）国际教育学院国际教育学院删除删除（删除第（删除第 i i 个结点）个结点）国际教育学院国际教育学院删除删除（删除第（删除第 i i 个结点）个结点）p-next=p-next-next?ai-1ai-1aiaiai+1ai+1pq删除前删除前删除后删除后国际教育学院国际教育学院11.11.将线性表将线性表L L中第中第i i个数据元素删除
46、个数据元素删除（算法（算法2.10）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-next=q-next;/删除并释放结点删除并释放结点 e=q-data;free(q);return OK;删除删除（删除第（删除第 i i 个结点）个结点）国际教育学院国际教育学院1.查找查找:因线性链表只能顺序存取，即在查找时要因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时
47、间复杂度为从头指针找起，查找的时间复杂度为 O(n)。2.插入和删除插入和删除:因线性链表不需要移动元素，只要因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为修改指针，一般情况下时间复杂度为 O(1)。但是，如果要在单链表中进行前插或删除操作，但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为由于要从头查找前驱结点，所耗时间复杂度为 O(n)。链表的运算链表的运算时间时间效率分析效率分析国际教育学院国际教育学院n从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：u生成新结点生成新结点u将读入数据存放到新结点的数据域中将读入数据存放到新结点
48、的数据域中u将该新结点插入到链表的前端将该新结点插入到链表的前端单链表的建立（前插法）单链表的建立（前插法）国际教育学院国际教育学院L单链表的建立单链表的建立pLanan-1anLp国际教育学院国际教育学院void CreatList_L(LinkList&L,int n)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表先建立一个带头结点的单链表 for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);/生成新结点生成新结点 scanf(&p-data);/输入元素值输入元素值 p-ne
49、xt=L-next;L-next=p;/插入到表头插入到表头 单链表的建立单链表的建立国际教育学院国际教育学院线性表的应用线性表的应用线性表合并线性表合并问题描述：问题描述：假设利用两个线性表假设利用两个线性表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
50、的最后的最后线性表合并线性表合并国际教育学院国际教育学院void union(List&La,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中的数据元素按值中的数据元素按值非递减非递减有有序排列序排列,现要求将现
