[其它课程]线性表.ppt

《[其它课程]线性表.ppt》由会员分享，可在线阅读，更多相关《[其它课程]线性表.ppt（198页珍藏版）》请在三一办公上搜索。

1、线性表,绪论回顾,数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构。数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示。一种逻辑结构通过映像可以得到它的存储结构。一个算法的设计取决于选定的逻辑结构，而算法的实现则依赖于采用的存储结构。,主要的逻辑结构,数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关

2、系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。,数据的存储结构（物理结构）,顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。,索引存储结构：该方法通常在存储结点信息的同时，还建立附加索引表，索引表中的每一项称为索引项，它的一般形式为：（关键字，地址）。,数据结构在计算机中有两种不同的表示方法：顺序表示 和 非顺序表示。细分为4种不同的存储结构：,“关系”的映象,1536,元素2,1400,1346,元素

3、3,元素4,1345,h,链式存储,h,元素1,时间复杂度,从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。,时间复杂度,例1 程序段for(i=1;i=n;+i)+x;s+=x;语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。,时间复杂度,例2 程序段for(i=1;i n;i+)for(j=1;jn;j+)c=aij;aij=bij;bij=c;程序功能：实现两个二维数组内容互换。时间复杂度：O(n2);,例一两个矩阵相乘,void mult(int a,int b,int/for/mult,基本操

4、作:乘法操作,时间复杂度:O(n3),算法的存储空间需求,算法的空间复杂度定义为:,表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n)的增长率相同。,S(n)=O(g(n),算法的存储量包括:,1输入数据所占空间,2程序本身所占空间；,3辅助变量所占空间。,若输入数据所占空间只取决与问题 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。,若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。,若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,第二章 线性表,2.1线性表的定义及逻辑结构2.2线性表的基本操作2.3线性表的顺序存储结构2

5、.4基本操作在顺序表上的实现2.5应用举例及分析,2.1线性表的类型定义,线性表是n(n 0)个数据元素的有限序列。线性表中数据元素的个数n（n0）定义为线性表的长度当线性表的长度为0 时，称为空表。第i个数据元素ai，称i为ai 在线性表中的位序。例:一周的七天(Sunday,Monday.Saturday）；是一个长度为7的线性表，其中的每一天就是一个数据元素。Monday在此线性表中的位序为2。,每一个数据元素都是不可分割的，复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record）。,又如，一个学校的学生健康情况登记表，表中每一个学生的

6、情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等六个数据项组成。,线性结构的基本特征是：,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个“最后元素”,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,举例,例 26个大写英文字母表（A,B,C,Z）的表长是26，起始结点A没有直接前趋，A的唯一的直接后继是B；终端结点Z没有直接后继，Z的唯一的直接前趋是Y；而对于B,C,D,Y中的任意一个字母，都有一个唯一的直接前趋和一个唯一的直接后继。,线性表中的数据元素可以是各种各样的，但同一表中的元素必定具有相同特性。表中的一个数据元素可以由若干个数

7、据项组成，也可以只由一个数据项组成，通常把数据元素称为记录，有大量记录的线性表称为文件。,线性表的长度 n（n 0）就是表中数据元素的个数。n=0 时，称为空表，n 0时，线性表的表示形式为（a1,a2,，an）。,线性表具有线性结构的特点，表中ai元素的直接前驱元素是ai-1，ai元素的直接后继元素是ai+1。数据元素在线性表中的位置只取决于它的序号。线性表（a1,a2,a3,，an-1,an)序号 1 2 3 n-1 n,线性表的基本操作,(1)INITIATE（L）初始化操作函数。生成一个空的线性表L。(2)LENGTH（L）求表长度的函数。函数值为线性表L中数据元素的个数。(3)GET

8、（L,i)取表中元素的函数。当1 i LENGTH(L)时，函数值为线性表L中第i个数据元素，否则返回一特殊值。i是该数据元素在线性表中的位置序号。(4)LOCATE（L,x)定位函数。给定值x，在线性表L中若存在和x相等的数据元素，则函数返回和x相等的数据元素的位置序号，否则返回0。若线性表中存在一个以上的和x相等的数据元素，则函数返回多个位置序号中的最小值，也就是表中第一个和x相等的元素的位置序号。,线性表的基本操作(续),(5)INSERT(L,b,i)插入操作。在给定线性表L中第i（1 i LENGTH(L)+1）个数据元素之前插入一个新的数据元素b,使原来线性表的长度n变成n+1。(

9、6)DELETE(L,i)删除操作。删除在给定线性表L中第i（1 i LENGTH(L)）个数据元素，使原来线性表的长度n变成n-1。(7)EMPTY(L)判空表函数。若L为空表，则返回布尔值“真”，否则返回布尔值“假”。（8)CLEAR(L)表置空操作。不管原来的线性表L是空表还是非空表，操作结果将L表置空。以上基本操作中，(1)，(5)，(6)，(8)是加工型操作，其他都是引用型操作。,2.3 线性表的实现顺序映象,线性表的顺序存储结构,顺序表,线性表的顺序存储是计算机中最简单、最常用的一种存储方式，即用一组地址连续的存储单元依次存放线性表的元素。,线性表的起始地址，称作线性表的基地址LO

10、C(a1),LOC(ai)=LOC(a1)+(i-1)C,LOC(ai)=LOC(ai-1)+C,C一个数据元素所占存储量(数据元素的类型相同),线性表的顺序(顺序表)存储的特点,表中相邻的元素ai 和 ai+1 所对应的存储地址 LOC(ai)和地址LOC(ai+1)也是相邻的。实现逻辑上相邻物理地址相邻实现随机存取,线性表的起始地址，称作线性表的基地址LOC(a1),LOC(ai)=LOC(a1)+(i-1)C,LOC(ai)=LOC(ai-1)+C,下面是顺序表的逻辑表示和对表中元素存储地址计算的分析示意：逻辑表示（a1,a2,a3,ai,an-1,an)元素在表中的位置序号 1 2 3

11、,i,n-1 n存储地址 h h+b h+2b h+(i-1)b h+(n-1)b,从计算公式可以看出，计算顺序表中每一个元素的存储起地址的时间是相同的，读取表中元素所花的时间也是一样的。顺序表中任一元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。在这种结构上很容易实现线性表的某些操作，如随机存取表中第i个元素等。但是，从下面对表中插入元素和删除元素的操作中可看到，因这些操作需要移动元素而要花去大量的时间。,顺序表的c语言描述,线性表是n(n 0)个数据元素的有限序列。#defineDATATYPE1 int#define MAXSIZE 100typedef struc

12、t DATATYPE1 datasMAXSIZE;int last;SEQUENLIST;,C回顾结构体1、概念：结构体属构造类型，是将不同类型的数据组合在一起。一般这些不同类型的数据间是有联系的。例：表示一个学生的有关信息（学号，姓名，性别，年龄，总分，地址）可定义结构体类型:struct student int num;（学号）char name10;（姓名）char sex;（性别）int age;（年龄）float aver;（总分）char addr30;（地址）;,定义结构体类型及其变量(1)定义结构体类型格式：struct 结构体名 成员表列；其中：struct 是关键字，不可缺

13、省；一当结构体类型名定了后，可定义结构体类型的变量。(2)定义结构体变量的方式：先定义结构体类型，后定义变量。如：struct student stu1,stu2;是struct student类 型的两个变量名 在定义结构体类型同时，定义变量。如：struct data int year;int month;int day;da1,da2;,允许成员也可是结构体变量。如：struct student1 int num;char name10;char sex;struct date birthday;stu1,stu2;birthday num name sex year month day

14、 注：1）一个结构体变量在内存所占字节数是各成员所占字节数总和。,引用格式：结构体变量名成员名 成员运算符,级别最高 是一个整体,对其操作与标准型 变量相同 如:stu1.num=100;stu2.num=101;stu1.birthday.year=1974;stu1.birthday.month=1;stu1.birthday.day=22;:注：结构体类型变量不可做为一个整体加以引用，只可对其成员进行引用。错误引用：stu1.birthday；stu1,结构体成员变量的引用,结构体与指针 当定义了结构体变量，编译为其分配连续一批单元 准备存放各成员的值，而取结构体变量 的地址就是这批 单

15、元在内存存放的首地址。例：#define FMT“No.=%dt name:%st sex:%cn”main()sturct student2 int num;char name10;char sex;struct student2 stu;struct student2*p;p=,用指向结构体变量的指针变量，访问成员。有两种形式：指针变量 成员名 结构体变量名 成员名#define FMT“No.=%dt name:%st sex:%cn”main()static struct student2 int num;char name10;char sex;stu=9909,”Li Lin”,F

16、;struct student2*p;p=,线性表回顾,线性表是n(n 0)个数据元素的有限序列。线性表中数据元素的个数n（n0）定义为线性表的长度当线性表的长度为0 时，称为空表。第i个数据元素ai，称i为ai 在线性表中的位序。线性表的基本特征:1.如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素；2.ai（0in-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前；,线性表回顾,一周的七天(Sunday,Monday.Saturday）；每一个数据元素都是不可分割的，复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将

17、数据元素称为记录（record）。例如，某单位职工工资表就是一个线性表，表中每一个职工的工资就是一个记录，每个记录包含八个数据项职工号、姓名、基本工资。,复杂线性表职工工资表,记录record1record2record3record4record60,线性表回顾,typedef struct DataType dataListSize;/定义数组域int length;/当前线性表中数据元素的个数 SqList;/顺序表SqList*L;,struct ListDataType dataListSize;/定义数组域int length;/当前线性表中数据元素的个数 SqList;Struc

18、t List*L;,线性表回顾,SqList L;表长=L.length;表中元素=L.data3SqList*p;/p是一个指针变量。线性表的存储空间通过p=malloc(sizeof(SqList);操作来获得。p中存放的是顺序表的地址，表长=p-length。表中元素=p-data3,1.顺序表的初始化,顺序表的初始化即构造一个空表，将L设为指针参数，首先动态分配存储空间，然后，将表的length指针置为0,表示表中没有数据元素。SqList*initSqList()SqList*L;L=malloc(sizeof(SqList);if(L=NULL)return NULL;L-leng

19、th=0;return L;,typedef struct DataType dataListSize;int length;SqList;SqList*L;,Typedef struct DATATYPE1 datasMAXSIZE;int last;SEQUENLIST;,Void init_sequelist(SEQUENLIST a)a.last=0;return;,2.插入运算,在顺序表L中根据指定的位置i插入元素e。,首先分析:,InsertList(L,i,e),插入元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,an)改变为,(a1,ai-1,e,ai,an),

20、例如：在线性表的第i个位置插入一个新结点e,data0,插入运算,顺序表完成插入运算的操作步骤总结如下：,int j;for(j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/*数据元素后移*/,L-datai-1=e;,（1）将 ai an 顺序向下移动，为新元素让出位置。,（2）将 e 置入空出的第i个位置。,（3）修改length表长，使之指向最后一个元素。,L-length+;,void InsertList(SqList*L,DataType e,int i)int j;if(L-Length=LISTSIZE)printf(List Full);re

21、turn;/*表空间已满，不能插入*/if(i L-Length+1)printf(Position error);return;/*插入位置不正确*/for(j=L-Length-1;j=i-1;j-)L-dataj+1=L-dataj;/*移动结点*/L-datai-1=e;L-Length+;,插入算法复杂度分析,该表的长度为n,算法的时间主要消耗在数据的移动语句上，该语句的执行次数为(n i+1)。由此看出，所需移动结点的次数不仅依赖于表长，还与插入位置有关。,当 i=length 时，由于循环变量的终值大于初值，不进行数据移动，这是最好情况，复杂度为O(1);,当 i=1时，结点移动

22、语句循环执行 n 次，这是最坏的情况，复杂度为O(n);,线性表操作 ListDelete(&L,i,&e)的实现：,首先分析：,删除元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,ai+1,an)改变为,ai+1,an,表的长度减少,(a1,ai-1,ai+1,an),L.length-1,0,87,56,p=,例如：ListDelete_Sq(L,5,e),Status ListDelete_Sq(SqList&L,int i,ElemType&e)/ListDelete_Sq,for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/

23、表长减1return OK;,算法时间复杂度为:,O(ListLength(L),p=/表尾元素的位置,if(i L.length)return ERROR;/删除位置不合法,删除算法复杂度分析,与插入算法相同，其时间主要消耗在移动数据上。若 i=n，则由于循环变量初值大于终值，无须移动结点，复杂度为 O(1)。若i=1，则移动语句循环执行n-1次，需移动除开始结点外的所有结点，复杂度为O(n)。,顺序表,1）优点顺序表的结构简单顺序表的存储效率高，是紧凑结构顺序表是一个随机存储结构（直接存取结构）2）缺点在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。对长度变化较大的线性表，

24、或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。原因：数组的静态特性造成,2.5 应用举例及分析,例2.1将所有在顺序表lb中存在而在顺序表la中不存在的数据元素插入到la表中。这个例子实现的思路是：从顺序表lb中依次取出每一个元素，并在顺序表la中查访，若在la表中不存在，则可插到la表中。而且每个插入到la中的元素均统一规定插在la表的尾部，这样可节省算法执行的时间。过程中的查访和插入可调用前面的locate和insert函数。,void unite(SEQUENLIST la,SEQUENLIST lb)int i;for(i=1;i=lb.last;i+)if(!loca

25、te(la,lb.datas i-1)insert(la,lb.datas i-1,la.last+1);,例2：有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C,要求C的元素也是从小到大的升序排列。例如 A=（a,c,d,e,h,j,k），B=（b,c,f,g）,则，C=（a,b,c,d,e,f,g,h,j,k）,i=j=0;k=0;while(iLength-1,Lc,a,b,c,c,d,f,h,j,k,La,Lb,while(iLength-1)InsertList(Lc,La-datai,k+1);i+;k+;while(jLength-1)Inser

26、tList(Lc,Lb-dataj,k+1);j+;k+;,例 设线性表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。,原线性表,插入 x=18,46,35,26,20,16,11,11,9,3,13,12,11,10,9,8,7,6,5,4,3,2,1,46,35,26,20,18,1.确定插入位置,for(i=1;iLength,应该插入到线性表的第 6 号位置，即i=6,2.插入：移动+赋值,void InsertIncreaseList(SqList*L,DataType x)int i;for(i=1;iLength,实现代码,例题,已知 A=(a1,a2,am

27、)B=(b1,b2,bn)均为顺序表，试编写一个比较AB大小的算法。,分析：,1.算法的目标是分析两个表的大小，则算法中不应当破坏原表；,2.按题意，表的大小指的是“词典次序”，则不应当先比较两个表的长度；,3.算法中的基本操作为：同步比较两个表中相应的数据元素。,while(iLa.Length&iLb.Length),int compare(SqList La,SqList Lb),if(La.elemi=Lb.elemi)i+;else if(La.elemiLb.elemi)return-1;else return 1;,i=0;,if(iLa.length,else if(iLb.L

28、ength)return 1;else return-1;,返回,例 将顺序表（a1,a2,an）重新排列以a1为界的两部分：a1前面的值均小于a1,a1后面的均大于a1(设数据元素的类型为整型)。,基本思路：,（1）当前数据元素ai比a1大时，表明它已经在a1的后面，不必改变它与a1的位置，继续比较下一个。,（2）当前结点若比a1小，说明它应该放在a1的前面，此时，将它前面的元素都依次向后移动一个位置，然后插入该结点。,例如：（5，6，2，1，3，7，4）,（2，1，3，4，5，6，7）,调整为：,void Part(SqList*L)int i,j;DataType x,y;x=L-dat

29、a0;/*将基准元素a1置入x中*/for(i=1;iLength;i+)if(L-datai datai;for(j=i-1;j=0;j-)/*移动*/L-dataj+1=L-dataj;L-data0=y;,算法时间复杂度：O(n2),练习1 已知线性表a0,a1,an-1按顺序存储，且每个元素都是不相等的整数。设计把所有的奇数移到所有的偶数前边的算法。,解题思路：（1）从左到右找到偶数L.datai,从右到左找到奇数L.dataj，将两者交换。（2）循环过程1，直到 ij为止。,例如：（5，6，2，1，3，7，4）,（5，7，3，1，2，6，4）,调整为：,void Move(SqLis

30、t*L)int i=0,j=L-Length-1,k;DataType temp;while(idatai%2=0)i+;while(L-dataj%2=1)j-;if(idatai;/*交换i 于 j 中的数据*/L-datai=L-dataj;L-dataj=temp;,思考题,已知长度为n的非空线性表A采用顺序存储结构，请写一个算法找到该线性表中的最小数据元素。已知长度为n的非空线性表A采用顺序存储结构，并且每个数据元素均为一个无符号整数，请写一个程序删除线性表中原来序号为奇数的那些数据元素。,2.3 线性表的实现链式映象,上节回顾,线性表顺序存储的特点是：物理位置上相邻的元素在逻辑关系

31、上也是相邻的，这就是物理关系和逻辑关系的一致性。这一特点使顺序表有以下的优点：可以方便地随机读取表中任一元素，读取任一元素所花的时间相同。存储空间连续，不必增加额外的存储空间。,顺序存储的缺点也很明显：插入和删除运算时除特殊位置外一般要移动大量的元素，所花时间较多，效率较低。由于顺序表要求连续的存储空间，存储分配只能预先进行。因此当表长经常变化时，难以确定合适的存储空间量。若按可能达到的最大长度预先分配表空间，则会造成一部分空间长期闲置而得不到充分利用，若事先对表长估计不足，则插入操作可能使表长超过了预先分配的空间而造成溢出。总之，表的容量难以预先确定，容易引起浪费或难以扩充。,X,顺序表的插

32、入,顺序存储结构的插入时间主要耗费在移动数据元素上。移动元素的次数取决于插入元素的位置。,顺序表的尾插入,X,X,能否利用顺序表的尾插入，实现任意位置的插入操作？,关键问题：是如何保持数据间的逻辑线性关系？,该方法浪费了一定的空间，但提升插入删除等操作的效率。,1,链表在内存中的存储,110 130 135 160 165 170 200 205,002,起始点,指针,数据,一、单链表,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、一个带头结点的单链表类型,五、其它形式的链表,六、有序表类型,单链表,特点：用一组任意的存储单元存储线性表的数据元素利用指针实现：用不相邻

33、的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置,一、单链表,以“结点的序列”表示线性表 称作链表由于结点中只包含一个指针域，故又称线性链表为单链表。,54,13,10,53,11,12,51,0,例1 线性表:(a1，a2，a3，a4，a5，a6，a7，a8)的单链表示意图如下：,单链表(Singly Linked List),first 头指针last 尾指针,指针为空单链表由头指针唯一确定，因此常用头指针的名字来命名。如表first.,单链表中除第一个结点外的每个结点的存储地址都存放在其直接前

34、驱结点的next域中。,设头指针head指向开始结点，即存放第一个结点的起地址。终端结点无后继结点，因此终端结点的next域为空，即NULL(也可以用表示)。,图3.1是线性表L对应的单链表存储结构示意图。L=(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)。设每个数据元素占用5个内存单元，指针占用1个单元，链表头指针head=78。,讨论时，我们通常用箭头来表示链域中的指针，将链表画成用箭头链接起来的结点序列。,每个单链表必须有一个头指针，指向(存放)表中第一个结点(地址)。已知一单链表，就是已知了链表的起地址，即头指针。因此单链表可以用头指针的名字来命名。例如，头

35、指针的名字是head，则把链表称为表head。,head,例2 线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,Typedef struct LNode ElemType data;/数据域 struct Lnode*next;/指针域 LNode,*LinkList;,二、结点和单链表的 C 语言描述,LinkList L；/L 为单链表的头指针,在C语言中，用户可以利用 malloc 函数向系统申请分配链表结点的存储空间，该函数返回存储区的首地址。如：声明动态变量 p 以及为p分配空间的语句如下：Li

36、stNode*p;/指针p指向一个新分配的结点。p=(ListNode*)malloc(sizeof(ListNode);如果要把此结点归还给系统，则用函数free(p)来实现。,指针变量和结点变量,上面定义的变量head是类型为LinkList 的指针变量，若head的值非空(head!=NULL)，则head中放的是类型为LinkList 的某个结点的地址。,Typedef struct LNode ElemType data;/数据域 struct Lnode*next;/指针域 LNode,*LinkList;LinkList head;,head所指向的结点变量是在算法运行过程中动态

37、生成的，当需要时才产生，又称为动态变量。它是通过标准函数malloc生成，即 head=malloc(sizeof(LinkList)；函数malloc分配一个类型为LinkList 的结点变量的空间，并将起始地址放入指针变量head中。一旦所指向的结点变量不再需要了，又可通过标准函数free(head)释放 head所指向的结点变量占用的空间。,通过指针来访问结点变量是链表操作的基本概念。head=malloc(sizeof(LinkList)语句执行以后，即得到一个结点变量*head，地址在指针变量head中。,单链表特点：用一组任意的存储单元存储线性表的数据元素利用指针实现：用不相邻的存

38、储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置,上节回顾,以“结点的序列”表示线性表 称作链表由于结点中只包含一个指针域，故又称线性链表为单链表。,54,13,10,53,11,12,51,0,线性表:(a1，a2，a3，a4，a5，a6，a7，a8)的单链表示,存储地址,链表结点的结构体,struct LNode int data;/数据域 struct Lnode*next;/指针域 LNode,*LinkList;,typedef struct LNode ElemType data;/数据域

39、struct Lnode*next;/指针域 LNode,*LinkList;,类型定义：typedef int ElemType;,Struct LNode H;,typedef struct LNode LNode;,LNode H;Linklist L;,创建链表,算法分析第一个结点的处理方法与其他结点不同，原因是第一个结点加入时链表为空，它没有直接的前驱结点，它的地址就是整个链表的指针，因此需要放到链表的头指针变量中；其他结点都有直接前驱结点，因此其地址直接放到其前驱结点的next域中即可。,这种问题在插入结点、删除结点等操作中都会遇到，为此，我们提出一种解决方案：增加头结点。,las

40、t-next=t;last=t;,if(head=NULL)head=t;last=t;,LinkList head;ListNode*p,*s;head=NULL;s=NULL;,s,p,head,p=(ListNode*)malloc(sizeof(ListNode);,p-data=ch;,head,s,p,p,if(head=NULL)head=p;,s=p;,else s-next=p;,在链表的开始结点之前附加一个结点，并称之为头结点，那么会带来两个优点：,(1)由于开始结点的位置被存放在头结点的指针域中，所以链表的第一个位置上的操作就和其他位置上的操作一样，无需进行特殊处理。,(

41、2)无论链表是否为空，其头指针是指向头结点所在的非空指针，因此空表和非空表的处理也就统一了。,空链表,LinkList head;ListNode*p,*s;,s,p,p=(ListNode*)malloc(sizeof(ListNode);,p-data=ch;,s,p,p,s-next=p;,s=p;,s=head;,head=(ListNode*)malloc(sizeof(ListNode);,head,创建带头结点的链表,main()LINKLIST*head,*last,*t;char ch;t=malloc(sizeof(LINKLIST);/建立表头结点 head=t;last

42、=t;t-next=NULL;while(ch=getchar()!=)t=malloc(sizeof(LINKLIST);/对应图3.5中的 t-data=ch;/对应图3.5中的 last-next=t;/对应图3.5中的 last=t;/对应图3.5中的 t-next=NULL;,注：今后如不做特殊说明，我们所指单链表都是带头结点的。,在C语言中，对指针所指向结点的成员进行访问时，通常用运算符“-”来表示。例如取上面结构中的两个分量，可以写成head-data和head-next。如图3.3所示。,若指针变量head的值为空(NULL)，则它不指向任何结点，也可以把head看成指向一个空

43、表。,1.建立单链表,（1）建立空单链表链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始。,（2）建立包含n个数据的单链表设线性表中结点的数据类型为字符，依次输入这些字符，并以“”作为输入结束标志符。动态地建立单链表的常用方法有下面两种：,(1)头插入法建表该方法的思路是从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插到当前链表的表头上，直至读到结束标志符为止。例如：输入数据为（a,b,c,d）,main()LINKLIST*head=NULL,*t;c

44、har ch;while(ch=getchar()!=)t=malloc(sizeof(LINKLIST);/对应图3.4中的 t-data=ch;/对应图3.4中的 t-next=head;/对应图3.4中的 head=t;/对应图3.4中的,(2)尾插入法建表头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插入法建表，即每次将新结点插在链表的表尾。为此必须增加一个指针last，使其始终指向当前链表的尾结点。,图3.5给出了在空链表head中插入a，b，c之后，将d插到当前链表表尾上的情况。,三、单链表操作的实现,GetElem(L,i,e

45、)/取第i个数据元素,ListInsert(&L,i,e)/插入数据元素,ListDelete(&L,i,e)/删除数据元素,ClearList(&L)/重置线性表为空表,CreateList(&L,n)/生成含 n 个数据元素的链表,线性表的操作 GetElem(L,i,&e)在单链表中的实现:,j,1,2,3,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i,单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。,令指针 p 始终指向线性表中第 j 个数据元素,Status GetElem_L(LinkList L,int i,ElemT

46、ype&e)/L是不带头结点的链表的头指针，以 e 返回第 i 个元素/GetElem_L,算法时间复杂度为:,O(ListLength(L),p=L;j=1;/p指向第一个结点，j为计数器,while(p/顺指针向后查找，直到 p 指向第 i 个元素/或 p 为空,if(!p|ji)return ERROR;/第 i 个元素不存在e=p-data;/取得第 i 个元素return OK;,查找运算按值查找ListNode*GetListItem(LinkList list,DataType e)ListNode*p=list;while(p,求表长：,由于在结点中没有保存链表的长度，因此，要

47、获得表长，必须对链表进行一次完整的遍历。,算法思路：设计一个移动指针p和计数器c，初始化后，p所指结点的next域如果不为空，则向后移动指针p并且计数器加1。,求带头结点的单链表的长度 int ListLength(LinkList L)int len=0;LinkList*temp;temp=L;while(temp-next!=NULL)len+;temp=temp-next;return len;本算法时间复杂度为O(n)，其中n是链表的长度。,练习题,已知长度为n的非空线性表A采用链式存储结构，请写一个算法找到该线性表中的最小数据元素。,Status GetMinElem(LinkLi

48、st L,int&e)/L是不带头结点的链表的头指针，以 e 返回最小元素/GetMinElem,p=L;/p指向第一个结点,e=p-data;while(p)/顺指针向后查找，直到 p 指向第 i 个元素 if(p-datadata;p=p-next;if(L=NULL)return ERROR;/或 p 为空 else return OK;,4.插入运算,线性表的操作 ListInsert(L,i,e)在单链表中的实现：,有序对 改变为 和,可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。因此，在单链表中第 i 个结点之前进

49、行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。,如：设p指向单链表中的第i-1个元素结点，s指向新建立的元素结点，则插入操作的算法描述为：s-next=p-next;p-next=s;,Status ListInsert_L(LinkList L,int i,DataType e)/L 为带头结点的单链表的头指针，本算法/在链表中第i 个结点之前插入新的元素 e/LinstInsert_L,p=L;j=0;while(p/寻找第 i-1 个结点,if(!p|j i-1)return ERROR;/i应该为1,表长+1,p=L;j=0;while(p,i=3,s=(L

50、inkList)malloc(sizeof(ListNode);if(s=NULL)return ERROR;s-data=e;s-next=p-next;p-next=s;/插入return OK;,s,p,练习题,已知长度为n的非空线性表A采用链式存储结构，请写一个算法找到该线性表中的最小数据元素并在其后添加一个比它小1的数据元素。,Status GetMinElem_Insert(LinkList L)/L是不带头结点的链表的头指针/GetElem_L,LinkList p=L;/p指向第一个结点LinkList q=p;/q指向最小值结点int e=q-data；/e存放最小值,whi