《第2章线性表(MR).ppt》由会员分享，可在线阅读，更多相关《第2章线性表(MR).ppt（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构第第2 2章章 线性表线性表2学习重点学习重点线性表的概念及表示方法线性表的概念及表示方法线线性性表表的的顺顺序序存存储储方方式式及及操操作作的的实实现算法现算法线线性性表表的的链链式式存存储储方方式式及及操操作作的的实实现算法现算法3线性结构线性结构1结构中有且仅有一个结构中有且仅有一个“开始元素开始元素”，它没它没有前驱而仅有一个后继；有前驱而仅有一个后继；2结构中有且仅有一个结构中有且仅有一个“最后元素最后元素”，它，它没有后继而仅有一个前驱；没有后继而仅有一个前驱；3除最后元素之外，均有除最后元素之外，均有唯一的后继唯一的后继；4除开始元素之外，均有除开始元素之外，均有
2、唯一的前驱唯一的前驱。42.1线性表的逻辑结构线性表的逻辑结构线性表线性表是一种最简单的是一种最简单的线性结构，线性结构，线性表线性表L是是n（n0）个具有相同属性的数据元素）个具有相同属性的数据元素a1,a2,an组成的组成的有限序列有限序列，一个非空的线性表，一个非空的线性表可表示为可表示为L=（a1，a2，ai，ai+1，an）其中，其中，线性表中数据元素个数线性表中数据元素个数n称为称为线性表的长线性表的长度度，当，当n0时称为时称为空表空表。ai(1in)是线性表的是线性表的第第i个元素，它后面的元素个元素，它后面的元素ai+1称为称为直接后继直接后继，前，前面的元素面的元素ai-1
3、称为称为直接前驱直接前驱。52.1线性表的逻辑结构线性表的逻辑结构线性表有以下特点：线性表有以下特点：o在非空的线性表中，存在在非空的线性表中，存在唯一的唯一的一个被称为一个被称为“第第一个一个”的数据元素，又称为的数据元素，又称为表头元素表头元素；存在；存在唯一唯一的的一个被称为一个被称为“最后一个最后一个”的元素，又称为的元素，又称为表尾表尾元素元素。o线性表中数据的位置先后是有序的。除表头元素线性表中数据的位置先后是有序的。除表头元素外，线性表中的每一个元素外，线性表中的每一个元素有且仅有一个前驱有且仅有一个前驱；除表尾元素外，线性表中的每一个元素除表尾元素外，线性表中的每一个元素有且仅
4、有有且仅有一个后继。表头元素一个后继。表头元素只有一个后继而没有前驱，只有一个后继而没有前驱，表尾元素表尾元素只有一个前驱而没有后继。只有一个前驱而没有后继。o线性表中的线性表中的数据的类型是相同的数据的类型是相同的。表的长度。表的长度n的取的取值是个有限数，值是个有限数，最小为最小为0。6例如：例如：2626个英文字母组成的字母表个英文字母组成的字母表 （A A，B B，C C、Z Z）例如：例如：表表2-1 学生信息表学生信息表学号学号姓名姓名班班级级年年龄龄宿舍宿舍080101张张阳阳软软件件080120J309080102苏苏南南软软件件080121K502080103刘超刘超软软件件
5、080120J309080104王王帅帅软软件件080119J309080105张军张军软软件件080121J3117 2.1.2线性表的基本运算线性表的基本运算数据结构的运算是定义在逻辑结构层次上的，数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。而运算的具体实现则是建立在存储结构上的。(1)初始化线性表：初始化线性表：InitList(L)构造一个空的线性表构造一个空的线性表L，即表的初始化。，即表的初始化。(2)求线性表的长度求线性表的长度GetLength(L)求表中结点的个数，即为求表的长度。求表中结点的个数，即为求表的长度。8 2.1.2线性表的基本
6、运算线性表的基本运算(3)按序号取元素按序号取元素:GetNode（L，i）读取线性表读取线性表L第第i个数据元素，要求满足个数据元素，要求满足1iGetLength(L)。(4)按值查找按值查找Locate(L,x)在在L中查找值为中查找值为x的结点，并返回该结点在的结点，并返回该结点在L中的中的位置位置。若。若L中有中有多个结点的值和多个结点的值和x相同相同，则返回则返回首次首次找到的结点位置；若找到的结点位置；若L中中没有没有结点结点的值为的值为x，则返回一个，则返回一个特殊值特殊值表示表示查找失败查找失败。92.1.2线性表的基本运算线性表的基本运算(5)在线性表中插入新元素：在线性表
7、中插入新元素：InsertList（L,i,e）在线性表在线性表L的第的第i个位置上插入一个值为个位置上插入一个值为e的新结点，使得原编号为的新结点，使得原编号为i，i+1，n的结的结点变为编号为点变为编号为i+1，i+2，n+1的结点。这的结点。这里里1in+1，而，而n是原表是原表L的长度。插入后，的长度。插入后，表表L的长度加的长度加1。102.1.2线性表的基本运算线性表的基本运算（6）在线性表中删除元素：）在线性表中删除元素：Delete（L，i）删除线性表删除线性表L的第的第i个结点，使得原编号为个结点，使得原编号为i+1，i+2，n的结点变成编号为的结点变成编号为i，i+1，n-
8、1的结点。这里的结点。这里1in，而，而n是原表是原表L的的长度。删除后表长度。删除后表L的长度减的长度减1。（7）把已有线性表置为空表：）把已有线性表置为空表：ClearList（L）112.2线性表的顺序结构及运算实现线性表的顺序结构及运算实现2.2.1线性表的顺序存储结构线性表的顺序存储结构2.2.2顺序表上基本运算的实现顺序表上基本运算的实现122.2.1线性表的顺序存储结构线性表的顺序存储结构顺序存储方式是指在内存中开辟顺序存储方式是指在内存中开辟连续连续的存储单元的存储单元，按元素的，按元素的逻辑顺序逻辑顺序依次依次存放在其中，即顺序存放线性表。存放在其中，即顺序存放线性表。特点：
9、特点：在逻辑上相邻的数据元素，它们的在逻辑上相邻的数据元素，它们的物理位置也是相邻。物理位置也是相邻。例如：线性表（例如：线性表（a1,a2,a3,an）13 假假设设线线性性表表中中的的第第一一个个数数据据元元素素的的存存储储地地址址（首首地地址址）为为LOC(a1)，每每一一个个数数据据元元素素占占k个个字字节节，则则各元素的存储地址有如下关系：各元素的存储地址有如下关系：LOC（a2）=LOC(a1)k LOC（a3）=LOC(a2)k LOC（ai）=LOC(ai-1)k （2in）因因此此，线线性性表表中中第第i个个元元素素ai在在计计算算机机中中的的存存储储地地址为：址为：LOC(
10、ai)=LOC(a1)+(i-1)k（1in）1415练习练习已知一顺序表的起始地址为已知一顺序表的起始地址为26502650，顺，顺序表长为序表长为100100，每个元素占，每个元素占6 6个字节，个字节，求第求第1111个元素的起始地址（其开始结个元素的起始地址（其开始结点为第一个元素）。点为第一个元素）。162.2.1线性表的顺序存储结构线性表的顺序存储结构在顺序存储结构中，线性表中每一个数在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址据元素在计算机存储空间中的存储地址由该元素在线性表中的序号惟一确定。由该元素在线性表中的序号惟一确定。也就是说，也就是说，在线性表中
11、只要确定了起始在线性表中只要确定了起始地址，任一元素均可随机存取。地址，任一元素均可随机存取。17 在具体实现时，一般用高级语言中的在具体实现时，一般用高级语言中的数组数组来对来对应连续的存储空间。设最多可存储应连续的存储空间。设最多可存储MaxLen个元素，个元素，在在C语言中可用数组语言中可用数组dataMaxLen来存储数据元来存储数据元素，为保存线性表的长度需定义一个整型变量素，为保存线性表的长度需定义一个整型变量length。线性表的第线性表的第l，2，n个元素分别存放个元素分别存放在此数组下标为在此数组下标为0，1，length-1数组元素中，数组元素中，如下图如下图所示所示:18
12、 这样，一个线性表的顺序存储结构需要两个分量。这样，一个线性表的顺序存储结构需要两个分量。为体现数组为体现数组data和和length之间的内在联系，通常将它们之间的内在联系，通常将它们定义在一个结构类型中。此处的元素类型用定义在一个结构类型中。此处的元素类型用DataType来表示。来表示。综上所述，综上所述，在在C C语言中可用下述类型定义来描语言中可用下述类型定义来描述顺序表：述顺序表：#define MaxLen 100 /线性表的容量线性表的容量 typedef int DataType；typedef struct DataType dataMaxLen;/定义存储表元素的数组定义
13、存储表元素的数组 int length;/线性表的实际长度线性表的实际长度 SeqList;SeqList L;/定义表结构的变量定义表结构的变量192.2.2顺序表上基本运算的实现顺序表上基本运算的实现1初始化顺序表初始化顺序表InitList(L)的实现的实现 顺序表的初始化即构造一个空表，顺序表顺序表的初始化即构造一个空表，顺序表L是否为空取决于其元素个数是否为是否为空取决于其元素个数是否为0，因此，因此，只要将表只要将表L中的表长度置为中的表长度置为0，就可以实现建，就可以实现建空表的功能。空表的功能。voidInitList(SeqList*L)L-length=0;202.2.2顺
14、序表上基本运算的实现顺序表上基本运算的实现 2求线性表长度求线性表长度GetLength(L)的实现的实现 只要将表示线性表长度的只要将表示线性表长度的length返回即可：返回即可：intGetLength(SeqList*L)returnL-length;该算法的时间复杂度为该算法的时间复杂度为O(1)212.2.2顺序表上基本运算的实现顺序表上基本运算的实现 3按序号取元素按序号取元素GetNode(L,i)的实现的实现 按按前前面面的的约约定定，序序号号为为i的的元元素素存存储储在在数数组组下下标标为为i-1的的数数组组元元素素中中，所所以以可可直直接接从从该该数数组组元元素素中中取取
15、得得值值。i的的有有效效值值应应大大于于等等于于1和和小小于于等等于于线线性性表的实际长度表的实际长度。int GetNode(SeqList*L,int i)if(iL-length)printf(“position error”);exit(1);return L-datai-1;222.2.2顺序表上基本运算的实现顺序表上基本运算的实现4查找运算查找运算Locate(L,e)的实现的实现 要要确定值为确定值为e的元素在的元素在L表中的位置，需要表中的位置，需要依次比较各元素。当查询到第一个满足条依次比较各元素。当查询到第一个满足条件的数据元素时，返回其序号，否则返回件的数据元素时，返回其
16、序号，否则返回-1，表示查找失败。，表示查找失败。23L.data回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值假设给定值 e=64,要求要求 L.datak=e,问问:i=?iiii7242.2.2顺序表上基本运算的实现顺序表上基本运算的实现查找操作的具体实现算法如下：查找操作的具体实现算法如下：intLocate(SeqList*L,inte)inti=0;if(ilength)returni;elsereturn-1;while(ilength&L-datai!=e)i+;252.2.2顺序表上基本运算的实现顺序表上基本运算的实现查找运算查找运算Locate(L,e)的时间复杂度
17、的时间复杂度由算法可知，对于表长为由算法可知，对于表长为n的顺序表，的顺序表，在查找过程中，数据元素比较次数最少为在查找过程中，数据元素比较次数最少为1，最多为，最多为n，元素比较次数的平均值为，元素比较次数的平均值为(n+1)/2，时间复杂度为，时间复杂度为 O(n)。262.2.2顺序表上基本运算的实现顺序表上基本运算的实现5顺序表的插入算法顺序表的插入算法InsertList(L,e,i)的实现的实现顺序表的插入是指在表的第顺序表的插入是指在表的第i个位置上插入一个位置上插入一个值为个值为e的新元素，插入后使原表长为的新元素，插入后使原表长为n的表：的表：(a1，a2，ai-1，ai，a
18、i+1，an)，成为表长为，成为表长为n+1的表：的表：(a1，a2，ai-1，e，ai，ai+1，an),i的取值范围为的取值范围为1iin+1。27(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加128void InsertList(SeqList*L,Datatype e,int i)int j;if(iL-length+1)printf(“position error!”);/插入位置出错插入位置出错 exit(1);L-datai-1=e;/插入插入e L-length+;/表长度
19、加表长度加1 for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/数据元素后移数据元素后移 if(L-length=MaxLen)printf(“overflow!”);/表已满表已满 exit(1);29考虑移动元素的平均情况考虑移动元素的平均情况:假设在第 i 个元素之前插入的概率为 ，则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：302.2.2顺序表上基本运算的实现顺序表上基本运算的实现
20、6顺序表的删除运算顺序表的删除运算DeleteList(L,i)的实现的实现 顺序表的删除运算是指将表中第顺序表的删除运算是指将表中第i个元素个元素从线性表中去掉，原表长为从线性表中去掉，原表长为n的线性表的线性表(a1，a2，ai-1，ai，ai+1，an)。进行删除。进行删除以后的线性表表长变为以后的线性表表长变为n-1的表的表(a1，a2，ai-1，ai+1，an)，i的取值范围为：的取值范围为：1in。31(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的长度减少1a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 322
21、1 18 30 75 42 56 8721 18 30 75L.length-10jjjL-length-18756for(j=i;jlength-1;j+)L-dataj-1=L-dataj;例如：DeleteList(SeqList*L,5)j33voidDeleteList(SeqList*L,inti)/删除线性表中第删除线性表中第i个位置上的元素个位置上的元素intj;if(iL-length)/检查空表及删除位置的合法性检查空表及删除位置的合法性printf(“positionerror”);exit(1);L-length-;for(j=i;jlength-1;j+)L-data
22、j-1=L-dataj;/向前移动元素向前移动元素34考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第假设删除第 i 个元素的概率为个元素的概率为 ,则在长度为则在长度为n 的线性表中的线性表中删除一个元素删除一个元素所需所需移动元素次数的期望值移动元素次数的期望值为：为：若假定在线性表中任何一个位置上进行删除若假定在线性表中任何一个位置上进行删除的的概率概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：35【例例2-12-1】将顺序表（将顺序表（a1,a2,a1,a2,anan）重新排列成以）重新排列成以a1a1为界的两部分：为界的两部分：a1a1前面的值均比前面
23、的值均比a1a1小，小，a1a1后面的值均后面的值均比比a1a1大（这里假定数据类型具有可比性，例如整型），大（这里假定数据类型具有可比性，例如整型），这一操作称为划分，这一操作称为划分，a1a1也称为基准。也称为基准。基本思路：基本思路：从第二个元素开始到最后一个元素，逐从第二个元素开始到最后一个元素，逐一向后扫描，当数据元素一向后扫描，当数据元素aiai比比a1a1大时，表明它已经大时，表明它已经在在a1a1的后面，不必改变其位置；当数据元素的后面，不必改变其位置；当数据元素aiai比比a1a1小时，需要把它调整到小时，需要把它调整到a1a1前面去，把前面去，把a1a1前面的元素前面的元素
24、依次向下移动一个位置，然后把它置于最上方。依次向下移动一个位置，然后把它置于最上方。36void part(Seqlist *L)int i,j;DataType x,y x=L-data0;for(i=1;ilength;i+)if(L-dataidatai;for(j=i-1;j=0;j-)L-dataj+1=L-dataj;L-data0=y;作业（选作）作业（选作）写一个程序完成基准划分：在线性表中，写一个程序完成基准划分：在线性表中，将第一个数据元素将第一个数据元素作为作为“枢轴枢轴”，凡表中凡表中元素元素小于枢轴小于枢轴的均的均移动至该元素之前，移动至该元素之前，反反之，凡之，凡表
25、中元素大于枢轴表中元素大于枢轴的均的均移动至该元移动至该元素之后素之后。（可以参考教材。（可以参考教材P255P255算法算法9-59-5）38【例例2-22-2】利用线性表的基本运算，编写在线性表利用线性表的基本运算，编写在线性表A A中删除线性表中删除线性表B B中出现的元素的算法。中出现的元素的算法。void delete(SeqList*A,SeqList*B)int i,k;DataType x;for(i=1;i0)DeleteList(A,k);/若在线性表若在线性表A中找到了，将其删除中找到了，将其删除 39线性表的顺序存储结构的特点线性表的顺序存储结构的特点优点：优点：顺序表
26、中的任意数据元素的存储地址可由公式顺序表中的任意数据元素的存储地址可由公式直接导出，因此顺序表可以随机存取其中的任意元素。直接导出，因此顺序表可以随机存取其中的任意元素。不足：不足：（1 1）需预先分配相应的存储空间；存储空间不便于）需预先分配相应的存储空间；存储空间不便于扩充。当一个线性表分配顺序存储空间后，若线性表扩充。当一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生的存储空间已满，但还需要插入新的元素，则会发生“上溢上溢”错误。错误。（2 2）插入与删除运算的效率很低，插入、删除操作）插入与删除运算的效率很低，插入、删除操作时需移动大量数据。时需移动
27、大量数据。40 链表：链表：链表是动态进行存储分配的一种结构。若干数链表是动态进行存储分配的一种结构。若干数据据(每个数据组称为一个结点每个数据组称为一个结点)按一定的原则连接起按一定的原则连接起来。来。单向链表QianSunLiZhouWuWangHead7131432537以上链表结构中只有一个方向的指针，因此又称以上链表结构中只有一个方向的指针，因此又称为单链表，简称为链表。为单链表，简称为链表。411249A1356B1475C1021DNULLhead1249135614751021简单的链表:设置一指针变量，存放第一个结点的地址，设置一指针变量，存放第一个结点的地址，称为头指针，一
28、般以称为头指针，一般以headhead命名。命名。最后一个结点的地址项不指向任何结点，最后一个结点的地址项不指向任何结点，赋以值赋以值NULLNULL。链表中每一个元素称为一个结点链表中每一个元素称为一个结点,结点是结点是一组数据一组数据,包括用户需要的实际数据和下包括用户需要的实际数据和下一个结点的地址。一个结点的地址。前一个结点指向下一个结点前一个结点指向下一个结点,只有通过前只有通过前一个结点才能找到下一个结点。一个结点才能找到下一个结点。struct student int num;char name10;char department20;struct student *next;4
29、3mallocmalloc函数函数函数原型：函数原型：作用作用:void *malloc(unsigned int size)void *malloc(unsigned int size)；在内存的动态存储区中分配一个长度为在内存的动态存储区中分配一个长度为sizesize的的连续存储空间。其中，形参连续存储空间。其中，形参sizesize为无符号整数，为无符号整数，是函数是函数mallocmalloc要求分配存储空间的字节个数。要求分配存储空间的字节个数。函数返回值为一个指针，它指向所分配存储空函数返回值为一个指针，它指向所分配存储空间的起始地址。若函数返回值为间的起始地址。若函数返回值为0
30、 0，则表示未，则表示未能成功申请到内存空间。函数类型为能成功申请到内存空间。函数类型为voidvoid，表，表示返回的指针不指向任何具体的类型示返回的指针不指向任何具体的类型.44mallocmalloc函数函数malloc函数的使用函数的使用:malloc(8)malloc(8)开辟长度为开辟长度为8 8个字节的存储空间个字节的存储空间,若其若其起始地址为起始地址为1268,1268,则则malloc(8)malloc(8)的返回值为的返回值为1268,1268,且且返回的指针值指向返回的指针值指向voidvoid型型.将此地址赋给一个指向将此地址赋给一个指向longlong型的指针变量型
31、的指针变量:p=(long*)malloc(8);p=(long*)malloc(8);long*lplong*lp；lp=(long*)malloc(12)lp=(long*)malloc(12)；head=(struct student*)malloc(sizeof(struct head=(struct student*)malloc(sizeof(struct student)student)；45o函数函数free:函数的原型:函数作用:函数的使用:void free(void *ptr)void free(void *ptr)；释放由指针变量释放由指针变量ptrptr为所指示的内存
32、区域。其中，为所指示的内存区域。其中，ptrptr一个指针变量，指向最近一次调用函数一个指针变量，指向最近一次调用函数mallocmalloc或或calloccalloc时所时所分配的连续存储空间的首地址。通过函数分配的连续存储空间的首地址。通过函数freefree将已分配的内将已分配的内存区域交还系统，使系统可以重新对其进行分配。存区域交还系统，使系统可以重新对其进行分配。long *plong *p；p=(long *)malloc(8)p=(long *)malloc(8)；.free(p)free(p)；462.3线性表的链式存储和运算实现线性表的链式存储和运算实现2.3.1链表的存储
33、结构链表的存储结构2.3.2单向链表单向链表2.3.3循环链表循环链表2.3.4双向链表双向链表2.3.5循环双链表循环双链表2.3.6静态链表静态链表47 用一组用一组地址任意地址任意的存储单元存放线的存储单元存放线性表中的数据元素。性表中的数据元素。2.3.1链表的存储结构链表的存储结构以以元素元素(数据元素的映象数据元素的映象)+指针指针(指示后继元素存储位置指示后继元素存储位置)=结点结点 (表示数据元素表示数据元素 或或 数据元素的映象数据元素的映象)采用链式存储结构表示的线性表采用链式存储结构表示的线性表 称作称作链表链表48 以线性表中第一个数据元素 的存储地址作为线性表的地址，
34、称作线性表的头指针。头结点头结点 a1 a2 .an 头指针头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空 49 typedef struct node DataType data;/数据域数据域 struct node *next;/指针域指针域 ListNode,*LinkList;结点和单链表的结点和单链表的 C 语言描述语言描述LNode *Head；50例例:假设有一个线性表为（假设有一个线性表为（A,B,C,D,E），存储空间具有），存储空间具有10个存储结点，该线性表在存储空间中的存储情况个
35、存储结点，该线性表在存储空间中的存储情况如图所示。如图所示。图图 链链表表结结构构示示意意图图512.3.2单向链表单向链表 单链表分为带头结点和不带头结点两种单链表分为带头结点和不带头结点两种类型。类型。对于空链表，头结点的指针域为空。图对于空链表，头结点的指针域为空。图2-52-5是带头结点的链表示方式：是带头结点的链表示方式：图图2-52-5（a a）为带头结点的空链）为带头结点的空链 (b)(b)为带头结点的单链表为带头结点的单链表521.建立单链表建立单链表头插法建表头插法建表尾插法建表尾插法建表 53头插法建表头插法建表LinkListCreatListF(void)/*返回单链表
36、的头指针返回单链表的头指针*/charch;ListNode*s;/*结点指针结点指针*/LinkListhead=(ListNode*)malloc(sizeof(ListNode);head-next=NULL;ch=getchar();/*读入第读入第1个字符个字符*/while(ch!=n)s=(ListNode*)malloc(sizeof(ListNode);s-data=ch;/*将读入的数据放入新结点的数据域中将读入的数据放入新结点的数据域中*/s-next=head-next;head-next=s;ch=getchar();returnhead;ListNode*ListN
37、ode*54尾插法建表尾插法建表LinkListCreatListR1(void)/*用尾插法建立的单链表用尾插法建立的单链表*/charch;ListNode*s,*r;/*结点指针结点指针*/LinkListhead=(ListNode*)malloc(sizeof(ListNode);r=head;/*尾指针初值也指向头结点尾指针初值也指向头结点*/ch=getchar();/*读入第读入第1个字符个字符*/while(ch=getchar()!=n)s=(ListNode*)malloc(sizeof(ListNode);s-data=ch;/*将读入的数据放入新结点的数据域中将读入的
38、数据放入新结点的数据域中*/r-next=s;r=s;r-next=NULL;returnhead;55练习练习:求线性表长度求线性表长度GetLength(L)GetLength(L)的实现的实现 设设计计思思路路：设设置置一一个个初初值值为为0 0的的计计数数器器变变量量和和一一个个跟跟踪踪链链表表结结点点的的指指针针p p。初初始始时时p p指指向向链链表表中中的的第第一一个个结结点点，然然后后顺顺着着nextnext域域依依次次指指向向每每个个结结点点，每每指指向向一一个个结结点点计计数数器器变变量量加加1 1。当当p p为为NULLNULL时时，结结束束该该过过程程。其其时时间间复复
39、杂度为杂度为O(n)O(n)。56算法如下算法如下:int GetLength(LinkList L)int num=0;ListNode*p;p=L-next;while(p!=NULL)num+;p=p-next;return(num);时间复杂度为时间复杂度为O(n)O(n)。572.单链表的查找运算单链表的查找运算按序号查找元素按序号查找元素按值查找按值查找58按序号取元素按序号取元素GetNode(L,i)GetNode(L,i)的实现的实现 根根据据前前面面的的讨讨论论，对对单单链链表表中中的的结结点点只只能能顺顺序序存存取取，即即访访问问前前一一个个结结点点后后才才能能接接着着访
40、访问问后后一一个个结结点点，所所以以要要访访问问单单链链表表中中第第i i个个元元素素值值，必必须须从从头头指指针针开开始始遍遍历历链链表表，依依次次访访问问每每个个结结点点，直直到到访访问问到到第第i i个个结结点点为为止止。同同顺顺序序表表一一样，也需注意存取的位置是否有效。样，也需注意存取的位置是否有效。59L 线性表的操作线性表的操作:GetNode(L,i)在单链表中取出第在单链表中取出第i个元素个元素,若第若第i个元素存个元素存在则用函数名返回在则用函数名返回,否则返回否则返回Null211830754256ppp返回1 2结点结点pj3GetNode(L,3)60 因此，查找第因
41、此，查找第 i 个数据元素的基本个数据元素的基本操作为：操作为：移动指针，比较移动指针，比较 j 和和 i。单链表是一种链式存取的结构，为找单链表是一种链式存取的结构，为找第第 i 个数据元素，必须先找到第个数据元素，必须先找到第 i-1 个数个数据元素。据元素。不断移动指针不断移动指针p p,同时同时j j不断加不断加1 1。61ListNode*GetNode(LinkList L,int i)ListNode*p;int j;if(iGetLength(L)exit(1);p=L-next;j=1;while(p!=NULL&jnext;j+;return p;时间复杂度为时间复杂度为O
42、(n)O(n)。62按值查找运算按值查找运算Locate(L,x)Locate(L,x)的实现的实现设设置置一一个个跟跟踪踪链链表表结结点点的的指指针针p p，初初始始时时p p指指向向链链表表中中的的第第一一个个结结点点，然然后后顺顺着着nextnext域域依依次次指指向向每每个个结结点点，每每指指向向一一个个结结点点就就判判断断其其值值是是否否等等于于x x，若若是是则则返返回回该该结结点点地地址址。否否则则继继续续往往后后搜搜索索，直直到到p p为为NULLNULL，表表示示链链表表中中无无此元素，返回此元素，返回NULLNULL。其时间复杂度为。其时间复杂度为O(n)O(n)。63L
43、线性表的操作:Locate(L,x)在单链表中查找值为x的元素,若找到了，则返回该元素的地址，否则返回Null211830754256pppLocate(L,30)return p;64L 线性表的操作:locate(L,x)在单链表中查找值为x的元素,若找到了，则返回该元素的地址，否则返回Null211830754256ppplocate(L,90)p=p-next;return p;p65 ListNode*Locate(LinkList L,DataType x)LNode*p=L-next;while(p&p-data!=x)p=p-next;return p;时间复杂度为时间复杂度为
44、O(n)O(n)。p!=NULL663 3链表的插入算法链表的插入算法InsertList(L,InsertList(L,x,i)x,i)的实现的实现 单链表结点的插入是利用修改结单链表结点的插入是利用修改结点指针域的值，使其指向新的结点位点指针域的值，使其指向新的结点位置来完成的插入操作，而置来完成的插入操作，而无需移动任无需移动任何元素何元素。67ai-1 线性表的操作 InsertList(L,x,i)在单链表中的实现：有序对有序对 改变为改变为 和和 xaiai-1pqs68 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为:找到线
45、性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但同时，若要在第指针。但同时，若要在第 i 个结点之前个结点之前插入元素，插入元素，修改的是第修改的是第 i-1 个结点的指个结点的指针。针。69链表的插入算法链表的插入算法具体步骤：具体步骤：o找到找到ai-1存储位置存储位置*q,并并*p指向结点指向结点aio生成一个数据域为生成一个数据域为x的新结点的新结点*so新结点的指针域指向结点新结点的指针域指向结点ai(即即*p)o令结点令结点*q的指针域指向新结点的指针域指向
46、新结点70void InsertList(LinkList head,DataType x,int i)LNode*p,*q,*s;int j=1;p=head;if(iGetLength(head)+1)exit(1);while(jnext;j+;71s=(ListNode*)malloc(sizeof(ListNode);/生成新结点s-data=x;s-next=q-next;q-next=s;/插入 xai-1aiai-1sqp算法的算法的时间复杂度时间复杂度为:O(n)724 4链表的删除运算链表的删除运算DeleteList(head,i)DeleteList(head,i)的实
47、现的实现在单链表中找到删除位置在单链表中找到删除位置前一个结点前一个结点，并用指针并用指针p p指向它指向它指针指针q q指向要删除的结点指向要删除的结点将将*p p的指针域修改为待删除结点的指针域修改为待删除结点*q q的的后继结点的地址后继结点的地址删除后的结点需动态的释放。删除后的结点需动态的释放。73线性表的操作deleteList(L,i)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-174 在单链表中删除第在单链表中删除第 i i 个结点的基本个结点的基本操作为操作为:找到线性表中第找到线性表中第i-1i-1个结点个结点，修，修改其指向后继的指针。改其
48、指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;free(q);pq75void DeleteList(LinkList head,int i)ListNode*q,*p;int j=1;p=head;算法的算法的时间复杂度时间复杂度为:O(n)if(iGetLength(head)exit(1);q=p-next;p-next=q-next;free(q);while(jnext;j+;76练习练习:链表元素输出运算链表元素输出运算DispList(L)的实现的实现 从从第第一一个个结结点点开开始始，顺顺着着指指针针链链依依次次访访问问每每一个结点并
49、输出。一个结点并输出。void DispList(LinkList L)ListNode*p;p=L-next;while(p!=NULL)printf(%4d,p-data);p=p-next;printf(n);时间复杂度为时间复杂度为O(n)O(n)。77【例例2-3】已知单链表已知单链表L，写一算法，删除其重复结点。，写一算法，删除其重复结点。算法思路：用指针算法思路：用指针p p指向第一个数据结点，从指向第一个数据结点，从它的后继结点开始到表的结束，找与其值相它的后继结点开始到表的结束，找与其值相同的结点并删除；同的结点并删除；p p指向下一个，依此类推，指向下一个，依此类推，p p
50、指向最后结点时算法结束。指向最后结点时算法结束。78【算法算法2-15】删除单链表中的重复结点删除单链表中的重复结点voiddelete_list(LinkListL)ListNode*p,*q,*s;p=L-next;/*p指向头结点之后的第一个结点指向头结点之后的第一个结点*/if(p=NULL)exit(1)；while(p-next!=NULL)q=p;while(q-next)/*从从*p的后继开始找重复结点的后继开始找重复结点*/if(q-next-data=p-data)s=q-next;q-next=q-next-next;free(s);elseq=q-next;p=p-ne