[其它课程]线性表2012.ppt

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

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

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

3、00,1346,元素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);,例 一 两 个 矩 阵

4、 相 乘,void mult(int a, int b, int /for /mult,基本操作: 乘法操作,时间复杂度: O(n3),算法的存储空间需求,算法的空间复杂度定义为:,表示随着问题规模 n 的增大， 算法运行所需存储量的增长率 与 g(n) 的增长率相同。,S(n) = O(g(n),算法的存储量包括:,1输入数据所占空间,2程序本身所占空间；,3辅助变量所占空间。,若输入数据所占空间只取决与问题 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。,若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。,若所需存储量依赖于特定的输入， 则通常按

5、最坏情况考虑。,第二章 线性表,2.1 线性表的定义及逻辑结构 2.2 线性表的基本操作 2.3 线性表的顺序存储结构 2.4 基本操作在顺序表上的实现 2.5 应用举例及分析,2.1线性表的类型定义,线性表是n(n 0)个数据元素的有限序列。 线性表中数据元素的个数n（n0）定义为线性表的长度 当线性表的长度为0 时，称为空表。 第i个数据元素ai，称i为ai 在线性表中的位序。 例:一周的七天 (Sunday,MondaySaturday）；是一个长度为7的线性表，其中的每一天就是一个数据元素。Monday在此线性表中的位序为2。,每一个数据元素都是不可分割的，复杂的线性表中，每一个数据元

6、素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record）。,又如，一个学校的学生健康情况登记表，表中每一个学生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等六个数据项组成。,线性结构的基本特征是：,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,线性

8、表的基本操作,(1) INITIATE（L）初始化操作函数。生成一个空的线性表L。 (2) LENGTH（L） 求表长度的函数。函数值为线性表L中数据元素的个数。 (3) GET（L, i) 取表中元素的函数。当1 i LENGTH(L)时，函数值为线性表L中第i个数据元素，否则返回一特殊值。i是该数据元素在线性表中的位置序号。 (4) LOCATE（L, x) 定位函数。给定值x，在线性表L中若存在和x相等的数据元素，则函数返回和x相等的数据元素的位置序号，否则返回0。若线性表中存在一个以上的和x相等的数据元素，则函数返回多个位置序号中的最小值，也就是表中第一个和x相等的元素的位置序号。,线

9、性表的基本操作(续),(5) INSERT(L, b, i)插入操作。在给定线性表L中第i（1 i LENGTH(L) + 1）个数据元素之前插入一个新的数据元素b, 使原来线性表的长度n变成n + 1。 (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) 是加工型操

10、作，其他都是引用型操作。,2.3 线性表的实现顺序映象,线性表的顺序存储结构,顺序表,线性表的顺序存储是计算机中最简单、最常用的一种存储方式，即用一组地址连续的存储单元依次存放线性表的元素。,线性表的起始地址， 称作线性表的基地址LOC(a1),LOC(ai) = LOC(a1) + (i-1)C,LOC(ai) = LOC(ai-1) + C,C一个数据元素所占存储量(数据元素的类型相同),线性表的顺序(顺序表)存储的特点,表中相邻的元素ai 和 ai+1 所对应的存储地址 LOC(ai) 和地址LOC(ai+1)也是相邻的。 实现逻辑上相邻物理地址相邻 实现随机存取,线性表的起始地址， 称

11、作线性表的基地址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 , i , n-1 n 存储地址 h h+b h+2b h+(i-1)b h+(n-1)b,从计算公式可以看出，计算顺序表中每一个元素的存储起地址的时间是相同的，读取表中元素所花的时间也是一样的。 顺序表中任一元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 在这种结构上很容易

12、实现线性表的某些操作，如随机存取表中第i个元素等。但是，从下面对表中插入元素和删除元素的操作中可看到，因这些操作需要移动元素而要花去大量的时间。,顺序表的c语言描述,线性表是n(n 0)个数据元素的有限序列。 #defineDATATYPE1 int #define MAXSIZE 100 typedef struct DATATYPE1 datasMAXSIZE; int last; SEQUENLIST;,C回顾结构体 1、概念： 结构体属构造类型，是将不同类型的数据组合在一起。 一般这些不同类型的数据间是有联系的。 例：表示一个学生的有关信息（学号，姓名，性别，年龄，总分，地址） 可定义

13、结构体类型: struct student int num; （学号） char name10;（姓名） char sex;（性别） int age;（年龄） float aver;（总分） char addr30;（地址） ;,定义结构体类型及其变量 (1) 定义结构体类型格式： struct 结构体名 成员表列 ； 其中：struct 是关键字，不可缺省； 一当结构体类型名定了后 ，可定义结构体类型的变量。 (2) 定义结构体变量的方式： 先定义结构体类型，后定义变量。如： struct student stu1, stu2; 是struct student类 型的两个变量名 在定义结构体

14、类型同时，定义变量。如： 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 注： 1） 一个结构体变量在内存所占字节数是各成员 所占字节数总和。,引用格式： 结构体变量名成员名 成员运算符 ,级别最高 是一个整体, 对其操作与标准型 变量相同 如: stu1.num=100;

15、 stu2.num=101; stu1.birthday.year=1974; stu1.birthday.month=1; stu1.birthday.day=22; : : 注： 结构体类型变量不可做为一个整体加以引用，只可对其成员进行引用。 错误引用：stu1.birthday；stu1,结构体成员变量的引用,结构体与指针 当定义了结构体变量， 编译为其分配连续一批单元 准备存放各成员的值，而取结构体变量 的地址就是这批 单元在内存存放的首地址。 例： #define FMT “No.=%dt name:%st sex:%cn” main( ) sturct student2 int n

16、um; 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; struct student2 *p; p= ,线性表回顾,线性表是n(n 0)个数据元素的有限序列。 线性表中数

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

18、资就是一个记录，每个记录包含八个数据项职工号、姓名、基本工资。,复杂线性表职工工资表,记录 record1 record2 record3 record4 record60,线性表回顾,typedef struct DataType dataListSize; /定义数组域 int length; / 当前线性表中数据元素的个数 SqList; / 顺序表 SqList *L;,struct List DataType dataListSize; /定义数组域 int length; / 当前线性表中数据元素的个数 SqList; Struct List *L;,线性表回顾,SqList L;

19、 表长 = L.length ; 表中元素=L.data3 SqList *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-length

20、 = 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

21、) 改变为, ,(a1, , ai-1, e, ai, , an),例如：在线性表的第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

22、e,int i) int j; if (L-Length = LISTSIZE ) printf(“List Full“); return ; /*表空间已满，不能插入*/ 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)。由此看出，所

23、需移动结点的次数不仅依赖于表长，还与插入位置有关。,当 i = length 时，由于循环变量的终值大于初值，不进行数据移动，这是最好情况，复杂度为O(1);,当 i = 1时，结点移动语句循环执行 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(

24、L, 5, e),Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sq,for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK;,算法时间复杂度为:,O( ListLength(L),p = / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,删除算法复杂度分析,与插入算法相同，其时间主要消耗在移动数据上。 若 i=n，则由于循环变量初值大于终值，无须移动结点，复杂度为

25、 O(1)。 若i=1，则移动语句循环执行n-1次，需移动除开始结点外的所有结点，复杂度为O(n)。,顺序表,1）优点 顺序表的结构简单 顺序表的存储效率高，是紧凑结构 顺序表是一个随机存储结构（直接存取结构） 2）缺点 在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。 对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。 原因：数组的静态特性造成,2.5 应用举例及分析,例2.1 将所有在顺序表lb中存在而在顺序表la中不存在的数据元素插入到la表中。 这个例子实现的思路是：从顺序表lb中依次取出每一个元素，并在顺序表la中查访，若在la表中

26、不存在，则可插到la表中。 而且每个插入到la中的元素均统一规定插在la表的尾部，这样可节省算法执行的时间。过程中的查访和插入可调用前面的locate和insert函数。,void unite (SEQUENLIST la, SEQUENLIST lb) int i ; for (i = 1 ; i = lb.last ; i +) if (! locate (la , lb.datas i -1) insert (la, lb.datas i -1, la.last + 1); ,例2：有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C,要求C的元素也是从小到

27、大的升序排列。 例如 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) InsertList(Lc,Lb-dataj,k+1); j+; k+; ,例 设线性表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。,原线性表,插入 x=18,46,35,26,20

28、,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) B=(b1, b2, , bn) 均为顺序表，试编写一个比较AB大小的算法。,分析：,1. 算法的目标是分析两个表的大小，则算法中不应当破坏原表；,2. 按题意，表

29、的大小指的是“词典次序”，则不应当先比较两个表的长度；,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.Length) return 1; else return -1;,返回,例 将顺序表（a1,a2,an）重新排列以a

30、1为界的两部分：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-data0; /*将基准元素a1置入x中*/ for(i=1;iLength;i+) if( L-da

31、tai 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(SqList *L) int i=0, j= L-Length-1 , k;

32、 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 线性表的实现链式映象,上节回顾,线性表顺序存储的特点是： 物理位置上相邻的元素在逻辑关系上

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

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

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

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

37、指针。因此单链表可以用头指针的名字来命名。 例如，头指针的名字是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 函数向系统申请分配链表结点的存储空间，该函数返回

38、存储区的首地址。 如：声明动态变量 p 以及为p分配空间的语句如下： ListNode *p; /指针p指向一个新分配的结点。 p=(ListNode *) malloc ( sizeof ( ListNode ) ) ; 如果要把此结点归还给系统，则用函数free(p)来实现。,指针变量和结点变量,上面定义的变量head是类型为LinkList 的指针变量，若head的值非空(head ! = NULL)，则head中放的是类型为LinkList 的某个结点的地址。,Typedef struct LNode ElemType data; / 数据域 struct Lnode *next; /

39、 指针域 LNode, *LinkList; LinkList head;,head所指向的结点变量是在算法运行过程中动态生成的，当需要时才产生，又称为动态变量。它是通过标准函数malloc生成，即 head = malloc (sizeof (LinkList )； 函数malloc分配一个类型为LinkList 的结点变量的空间，并将起始地址放入指针变量head中。一旦所指向的结点变量不再需要了，又可通过标准函数free(head) 释放 head所指向的结点变量占用的空间。,通过指针来访问结点变量是链表操作的基本概念。head = malloc (sizeof (LinkList)语句执

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

41、 struct Lnode *next; / 指针域 LNode, *LinkList;,typedef struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList;,类型定义： typedef int ElemType;,Struct LNode H;,typedef struct LNode LNode;,LNode H; Linklist L;,创建链表,算法分析 第一个结点的处理方法与其他结点不同，原因是第一个结点加入时链表为空，它没有直接的前驱结点，它的地址就是整个链表的指针，因此需要放到链

42、表的头指针变量中； 其他结点都有直接前驱结点，因此其地址直接放到其前驱结点的next域中即可。,这种问题在插入结点、删除结点等操作中都会遇到，为此，我们提出一种解决方案：增加头结点。,last-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

43、= p;,s = p;,else s-next = p;,在链表的开始结点之前附加一个结点，并称之为头结点，那么会带来两个优点：,(1) 由于开始结点的位置被存放在头结点的指针域中，所以链表的第一个位置上的操作就和其他位置上的操作一样，无需进行特殊处理。,(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 = he

44、ad;,head =(ListNode*)malloc(sizeof(ListNode);,head,创建带头结点的链表,main( ) LINKLIST *head, *last, *t; char ch; t = malloc(sizeof(LINKLIST);/ 建立表头结点 head = t; last = t; t-next = NULL; while (ch = getchar() != ) t = malloc(sizeof(LINKLIST); / 对应图3.5中的 t-data = ch; / 对应图3.5中的 last-next = t; / 对应图3.5中的 last =

45、 t; / 对应图3.5中的 t-next = NULL; ,注：今后如不做特殊说明，我们所指单链表都是带头结点的。,在C语言中，对指针所指向结点的成员进行访问时，通常用运算符“-”来表示。例如取上面结构中的两个分量，可以写成head-data和head-next。如图3.3所示。,若指针变量head的值为空(NULL)，则它不指向任何结点，也可以把head看成指向一个空表。,1.建立单链表,（1）建立空单链表 链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始。,（2）建立包含n个数据的单链表 设线性表中结点的数据类型为字符，依次输入这些字符，并以“”作为输入结束标志符。动态地建立单链表的常用方法有下面两种：,(1) 头插入法建表 该方法的思路是从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插到当前链表的表头上，直至读到结束标志符为止。例如：输入数据为（a,b,c,d）,main( ) LINKLIST *head = NULL, *t; char ch; while(ch = getchar()!=