《第二章线性表(专科)》由会员分享，可在线阅读，更多相关《第二章线性表(专科)（67页珍藏版）》请在金锄头文库上搜索。
1、12.1线性表的定义线性表的定义2.2线性表的基本操作线性表的基本操作2.3线性表的顺序存储结构线性表的顺序存储结构2.4线性表的链式存储结构线性表的链式存储结构2.4.1线性链表线性链表2.4.2循环链表循环链表2.4.3双向链表双向链表2.5顺序表和链表的比较顺序表和链表的比较2.6应用举例应用举例2一、线性表定义一、线性表定义线性表线性表是是n(0)个数据元素个数据元素a1，a2，an的有限的有限序列序列；表中每个元素（除第一个和最后一个外），有；表中每个元素（除第一个和最后一个外），有且仅有一个直接前趋，有且只有一个直接后继。且仅有一个直接前趋，有且只有一个直接后继。即线性表或为一个即
2、线性表或为一个空表空表（n=0），），或为：或为：（a1，a2，,ai-1，ai，ai+1，an）（n0）其中数据元素的个数其中数据元素的个数n定义为定义为表的长度表的长度（表长）。（表长）。这里的数据元素这里的数据元素ai(1in)只是一个抽象的符号，其具体只是一个抽象的符号，其具体含义在不同的情况下可以不同。含义在不同的情况下可以不同。例例1、26个英文字母组成的字母表个英文字母组成的字母表（A，B，C、Z）2.1线性表的定义线性表的定义3例例2、学生健康情况登记表如下：、学生健康情况登记表如下：姓姓名名学学号号性性别别年龄年龄健康情况健康情况王小林王小林790631男男18健康健康陈陈红
3、红790632女女20一般一般刘建平刘建平790633男男21健康健康张立立张立立790634男男17神经衰弱神经衰弱.记录记录由若干个数据项组成的数据元素称为记录。由若干个数据项组成的数据元素称为记录。文件文件含大量记录的线性表称为文件。含大量记录的线性表称为文件。a1a2a3a4。2.1 2.1 线性表的定义线性表的定义4从以上例子可看出从以上例子可看出线性表的逻辑特征线性表的逻辑特征是：是：在非空的线性表，在非空的线性表，有且仅有一个开始元素有且仅有一个开始元素a1，它没有它没有直接前趋，而仅有一个直接后继直接前趋，而仅有一个直接后继a2；有且仅有一个终端元素有且仅有一个终端元素an，它
4、没有直接后继，而仅有它没有直接后继，而仅有一个直接前趋一个直接前趋an-1；其余的内部元素其余的内部元素ai(2ilast+1三、顺序表类型定义三、顺序表类型定义用数组用数组2.3.1 2.3.1 线性表的顺序存储结线性表的顺序存储结构构9注意：注意：C语言中的数组下标从语言中的数组下标从“0”开始，因此，若开始，因此，若L是是SeqList类型的顺序表，则表中第类型的顺序表，则表中第i个元素是个元素是L-datai-1。1、初始化操作初始化操作即构造一个空表；算法见（即构造一个空表；算法见（P9）2.3.2顺序表上基本运算的实现顺序表上基本运算的实现SeqList*init_SeqList(
5、)/*构造一个空的顺序表构造一个空的顺序表*/SeqList*L;L=(SeqList*)malloc(sizeof(SeqList);L-last=-1;/*置空表置空表*/returnL;/*返回返回*/*init_SeqList*/注：注：malloc函数的使用。函数的使用。void*malloc(unsignedintsize)动态分配一个长为动态分配一个长为size的连续空间，成功则返回其首地址，不成功则返回空指的连续空间，成功则返回其首地址，不成功则返回空指针针NULL。10问题：问题：在表的第在表的第i个元素前，插入一个新元素个元素前，插入一个新元素x。(1in+1)即使：即使：
6、(a1，ai-1，ai，an)（长度长度=n）解决方法解决方法：从表中从表中最后一个元素最后一个元素开始到开始到第第i个元素个元素，依次，依次后移后移一一个位置，空出插入位置；个位置，空出插入位置；插入新元素；插入新元素；修改修改last（相当修改表长）。相当修改表长）。变成变成(a1，ai-1，x，ai，an)（长度长度=n+1）2、顺序表的插入运算、顺序表的插入运算2.3.2 2.3.2 顺序表上基本运算的实顺序表上基本运算的实现现11intInsert_SeqList(SeqList*L,inti,datatypex)/*在顺序表在顺序表L中第中第i个元素前插入新的元素个元素前插入新的元
7、素x*/*i的合法值为的合法值为1iL的表长的表长+1*/intj;if(L-last=MAXSIZE-1)/*当前存储空间已满当前存储空间已满*/printf(“表满表满”);return(-1)；if(iL-last+2)printf(“位置错位置错”);return(0);/*i值不合法值不合法*/for(j=L-last;j=i-1;j-)L-dataj+1=L-dataj;/*元素后移元素后移*/L-datai1=x;/*插入新元素插入新元素*/L-last=L-last+1;/*表长增表长增1*/return(1);/*插入成功，返回插入成功，返回*/*Insert_SeqList
8、*/顺序表的插入算法：（注意顺序表的插入算法：（注意C语言数组下标是从语言数组下标是从0开始）开始）12解决方法：解决方法： 取被删元素；取被删元素； 然后从然后从然后从然后从第第第第i+1i+1i+1i+1个元素个元素个元素个元素开始至开始至开始至开始至最后最后最后最后 一个元素一个元素一个元素一个元素依次依次依次依次前移前移前移前移一个位置；一个位置；一个位置；一个位置； 最后最后最后最后修改修改last（相当相当相当相当表长减表长减表长减表长减1)1)1)1)。3 3、删除运算、删除运算 问题：问题：问题：问题：将表的第将表的第将表的第将表的第i(1in)i(1in)i(1in)i(1i
9、n)元素删除。元素删除。元素删除。元素删除。 即使：即使：即使：即使：（a a a a1 1 1 1，a a a ai-1i-1i-1i-1，a a a ai i i i，a a a ai+1i+1i+1i+1，a a a an n n n) ) ) )（长度长度=n） 注：注：应考虑一些特殊情况的处理。应考虑一些特殊情况的处理。（a a a a1 1 1 1，a a a ai-1i-1i-1i-1，a a a ai+1i+1i+1i+1，a a a an n n n) ) ) )（长度长度=n-1）变成变成2.3.2 2.3.2 顺序表上基本运算的实顺序表上基本运算的实现现13intDele
10、te_SeqList(SeqList*L,inti,datatype*y)/*在顺序表在顺序表L中删除第中删除第i个元素，并用个元素，并用y返回其值返回其值*/*i的合法值为的合法值为1iL的表长的表长*/intj;if(iL-last+1)/*i值不合法值不合法*/printf(“不存在第不存在第i个元素个元素”);return(0);*y=L-datai-1;/*取第取第i个元素值个元素值*/for(j=i;jlast;j+)L-dataj-1=L-dataj;/*元素前移元素前移*/L-last=L-last-1;/*表长减表长减1*/return(1);/*删除成功，返回删除成功，返回
11、*/*Delete_SeqList*/顺序表的删除算法：顺序表的删除算法：2.3.2 2.3.2 顺序表上基本运算的实顺序表上基本运算的实现现144.查找运算查找运算 问题：问题：问题：问题： 在线性表中查找值为在线性表中查找值为在线性表中查找值为在线性表中查找值为x x的元素，若找到则返回其的元素，若找到则返回其的元素，若找到则返回其的元素，若找到则返回其在表中存储下标；否则，返回在表中存储下标；否则，返回在表中存储下标；否则，返回在表中存储下标；否则，返回-1-1值。值。值。值。 解决方法：解决方法：解决方法：解决方法：从线性表的第一个元素起，逐个和从线性表的第一个元素起，逐个和从线性表的
12、第一个元素起，逐个和从线性表的第一个元素起，逐个和x x较，较，较，较，直到找到或表结束为止。直到找到或表结束为止。直到找到或表结束为止。直到找到或表结束为止。 查找算法：查找算法：查找算法：查找算法：intint Location_SeqListLocation_SeqList(SeqListSeqList*L;*L;datatypedatatypex)x)/*/*在顺序表在顺序表在顺序表在顺序表LL中查找第一个值为中查找第一个值为中查找第一个值为中查找第一个值为x x的元素，找到则返的元素，找到则返的元素，找到则返的元素，找到则返* */ /*/*回其在回其在回其在回其在L L中存储下标，
13、否则返回中存储下标，否则返回中存储下标，否则返回中存储下标，否则返回-1-1值值值值* */ /intinti=0;i=0;while(ilast&L-datai!=x)+i;while(ilast&L-datai!=x)+i;/*/*循环查找值为循环查找值为循环查找值为循环查找值为x x的元素的元素的元素的元素* */ /if(iL-last)return-1;if(iL-last)return-1;/*/*未未未未找到，返回找到，返回找到，返回找到，返回-1*/-1*/elsereturni;elsereturni;/*/*找到，返回其在表中存储下标找到，返回其在表中存储下标找到，返回其在
14、表中存储下标找到，返回其在表中存储下标* */ /*/*Location_SeqListLocation_SeqList*/*/2.3.2 2.3.2 顺序表上基本运算的实顺序表上基本运算的实现现151.插入运算算法分析插入运算算法分析算法主要工作是算法主要工作是“移动元移动元素素”这里的这里的问题规模是表的长度问题规模是表的长度，设它的值为，设它的值为n。该算该算法的时间主要花费在循环的元素后移语句上，该语句法的时间主要花费在循环的元素后移语句上，该语句的执行次数（即移动元素的次数）是的执行次数（即移动元素的次数）是n+1-i。由此可看由此可看出，所需移动结点的次数不仅依赖于表的长度，而且出
15、，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。还与插入位置有关。当当i=n+1时，时，由于循环变量的终值大于初值，元素后移语句将由于循环变量的终值大于初值，元素后移语句将不进行；这是最好情况，不进行；这是最好情况，其时间复杂度其时间复杂度O（1）；）；当当i=1时，时，元素后移语句将循环执行元素后移语句将循环执行n次，需移动表中所有结次，需移动表中所有结点，这是最坏情况，点，这是最坏情况，其时间复杂度为其时间复杂度为O（n）；）；2.3.3顺序表上运算的算法分析顺序表上运算的算法分析16在第在第1个元素前插入，需移动元素个元素前插入，需移动元素n次次在第在第2个元素前插入，需移
16、动元素个元素前插入，需移动元素n-1次次在第在第i个元素前插入，需移动元素个元素前插入，需移动元素n-i+1次次在第在第n个元素前插入，需移动元素个元素前插入，需移动元素1次次在第在第n+1个元素前插入，需移动元素个元素前插入，需移动元素0次次故故插入运算算法所需的平均移动次数插入运算算法所需的平均移动次数:E插插=PiTi=Pi(n+1-i)（p1=p2=p3=pn=pn+1=1/(n+1)）=1(n+1)(n+1-i)=1(n+1)i=n2O(n)多项式级多项式级Pi在第在第i个元素前插入的概率。个元素前插入的概率。Ti相应的移动次数。相应的移动次数。共有共有n+1种情况种情况设为等概率出
17、现设为等概率出现由于插入可能在表中任何位置上进行，因此需分析由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。算法的平均复杂度。插入算法的平均复杂度：插入算法的平均复杂度：17也就是说，也就是说，在顺序表上做插入或删除运算，平均要移动表上在顺序表上做插入或删除运算，平均要移动表上大约一半元素大约一半元素。当表长当表长n较大时，算法的效率相当低。就数量级较大时，算法的效率相当低。就数量级而言，而言，E插插和和E删删均是线性阶的，因此顺序表的插入、删除算法的均是线性阶的，因此顺序表的插入、删除算法的平均时间复杂度均为平均时间复杂度均为O(n)。删除第删除第1个元素，需移动元素个元素，需
18、移动元素n-1次次删除第删除第2个元素，需移动元素个元素，需移动元素n-2次次删除第删除第i个元素，个元素，需移动元素需移动元素n-i次次删除第删除第n个元素，需移动元素个元素，需移动元素0次次共有共有n种情况，种情况，设为等概率设为等概率故故删除运算算法所需的平均移动次数删除运算算法所需的平均移动次数:E删删=PiTi=Pi(n-i)（p1=p2=p3=pn=1/n）=1n(n-i)=1ni=(n-1)2O(n)多项式级多项式级Pi删除第删除第i个元素的概率。个元素的概率。Ti相应的移动次数。相应的移动次数。2.删除运算算法分析删除运算算法分析算法主要工作是算法主要工作是“移动元素移动元素”
19、183、线性表顺序存储的优缺点、线性表顺序存储的优缺点 特点特点：在：在逻辑上相邻逻辑上相邻的元素在的元素在物理物理 上也相邻上也相邻，即顺序存储是用，即顺序存储是用 物理位置物理位置上的邻接关系来表上的邻接关系来表 示元素间的逻辑关系；示元素间的逻辑关系； 优点优点：结构简单，存取方便、迅速；：结构简单，存取方便、迅速； 缺点缺点： 作插入、删除运算需移动作插入、删除运算需移动 大量数据；大量数据； 表难以扩充（因需一片连表难以扩充（因需一片连 续空间）续空间）2.3.3 2.3.3 顺序表上运算的算法分析顺序表上运算的算法分析19 链表是指用一组任意的存储单元来依次存放线性表的结点，这链表
20、是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为信息，这个信息称为指针指针或或链链。这两部分组成了链表中的结点结这两部分组成了链
21、表中的结点结构。因此单链表就是：构。因此单链表就是：2.4线性表的链式存储结构线性表的链式存储结构即即用一组用一组任意任意的存储单元存放线性表的数据元素。的存储单元存放线性表的数据元素。（地址可连续也可不连续）（地址可连续也可不连续）线性表的顺序表示的特点是用物理位置上的邻接关系来表示元素间线性表的顺序表示的特点是用物理位置上的邻接关系来表示元素间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得得插入和删除操作会移动大量的结点插入和删除操作会移动大量的结点. .为避免大量结点的移动，我们介为避免大量结点的移动，我们介
22、绍线性表的另一种存储方式绍线性表的另一种存储方式链式存储结构，简称为链式存储结构，简称为链表链表。一、单链表定义一、单链表定义2.4.1单链表单链表20 单链表单链表是由若干个结点组成，每个结点含两部是由若干个结点组成，每个结点含两部分：分：数据域数据域datadata和和指针域指针域nextnext；数据域数据域datadata存放数据存放数据元素的值，指针域元素的值，指针域nextnext存放下一个结点（直接后继）存放下一个结点（直接后继）在存储器中的地址。在存储器中的地址。n n个结点链结成一个链表，形成个结点链结成一个链表，形成线性表的链式存储结构。线性表的链式存储结构。datanex
23、t即线性链表是由如下形式的结点组成：即线性链表是由如下形式的结点组成： 数据域数据域: :用来存放结点的值用来存放结点的值; ;指针域（链域）指针域（链域）: :用来存放结点的直接用来存放结点的直接 后继的地址（或位置）。后继的地址（或位置）。 由于上述链表的每一个结只有一个链域，故将这种链由于上述链表的每一个结只有一个链域，故将这种链表称为表称为单链表单链表（Single Linked)Single Linked)。2.4.1单链表单链表21 显然，单链表中每个结点的存储地址是存放在其前趋显然，单链表中每个结点的存储地址是存放在其前趋结点结点nextnext域中，而开始结点无前趋，故应设域中
24、，而开始结点无前趋，故应设头指针变量头指针变量headhead指向开始结点指向开始结点。同时，由于最后一个结点无后继，。同时，由于最后一个结点无后继，故其指针域为空，即故其指针域为空，即NULLNULL（图示中也可用图示中也可用 表示表示) )。 几个常用名词：几个常用名词： 指针指针指针域中存放的信息称为指针或链；指针域中存放的信息称为指针或链； 头指针头指针指示链表第一个结点存储位置的变量；指示链表第一个结点存储位置的变量； 空标志空标志NULLNULL或或链表的结束标志。链表的结束标志。 表头结点表头结点第一个元素结点前附加的一个结点；第一个元素结点前附加的一个结点； 首元结点首元结点第
25、一个元素结点。第一个元素结点。2.4.1单链表单链表22二、单链表的表示二、单链表的表示一般图示法一般图示法例：设有线性表例：设有线性表(ZHAO、QIAN、SUN、LI、ZHOU、WU、ZHENG、WANG)其顺序存储：其顺序存储：ZHAOQIANSUNLIZHOUWUZHENGWANGLIQIANSUNWANGWUZHAO7 ZHANGZHOU地地址址数据域数据域指针域指针域1LI 437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU2531 其链式存储：其链式存储：其链式存储：其链式存储：（物理上无序，逻辑上有序）（物理上无序，逻辑上
26、有序）（物理上无序，逻辑上有序）（物理上无序，逻辑上有序）1 7 13 19 25 31 37 431 7 13 19 25 31 37 43 其物理状态表：其物理状态表：其物理状态表：其物理状态表： LaLa（头指针）头指针）头指针）头指针）头指针头指针头指针头指针LaLa2.4.1单链表单链表232.4.1单链表单链表La头指针头指针表头结点的链域表头结点的链域=NULL时，时，链表为空链表为空单链表的逻辑表示单链表的逻辑表示画成用指针箭头相链接的结点序列。画成用指针箭头相链接的结点序列。ZHA0QIANSUNWANGLIZHA0QIANSUNWANG不带头结点的单链表：不带头结点的单链表
27、：L头指针头指针L=NULL时，链表为空表，其长度时，链表为空表，其长度=0带头结点的单链表：带头结点的单链表：L头指针头指针表头结点表头结点其数据域可为空其数据域可为空或放某些特殊信息或放某些特殊信息链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是例如：若头指针名是L，则把链表称为表则把链表称为表L。第一个实在结点（首元结点）第一个实在结点（首元结点）链表中设置表头结点的好处：链表中设置表头结点的好处：在链表的开始结点之前附加一个结在链表的开始结点之前附加一个结点，并称它为点，并称它为表表头结点头结点，会带
28、来以下两个优点：，会带来以下两个优点：由于开始结点的位置被存放在头结点的指针域中，所以在链表的第由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处和在表的其它位置上的操作一致，无需进行特殊处理；理；无论链表是否为空，其头指针是指向头结点所在的非空指针（空表中无论链表是否为空，其头指针是指向头结点所在的非空指针（空表中头结点的指针域为空），头结点的指针域为空），因此使空表和非空表的处理也就统一了，方便因此使空表和非空表的处理也就统一了，方便了运算。了运算。24三、单链表的存储结构的描述：三、单链表的存储结构的
29、描述：用用C语言描述的单链表如下：语言描述的单链表如下：typedefstructnodedatatypedata;structnode*next;LNode,*LinkList;LNode*p，u;/*u是结构变量，是结构变量，p是结构指针变量是结构指针变量*/LinkListH,L,q;注意区分指针变量和结点变量这两个不同的概念及访问方法。注意区分指针变量和结点变量这两个不同的概念及访问方法。单链表类型单链表类型(结构指针类型结构指针类型)2.4.1单链表单链表几点说明：几点说明：25生成结点变量的标准函数生成结点变量的标准函数p=malloc(sizeof(structnode);/*函
30、数函数malloc分配了一个类型为分配了一个类型为structnode的结点的结点变变量的空间，并将其首地址放入指针变量量的空间，并将其首地址放入指针变量p中中*/。P为动态变量，它是在程序执行过程中，当需要时临时产生的。为动态变量，它是在程序执行过程中，当需要时临时产生的。释放结点变量空间的标准函数释放结点变量空间的标准函数free(p)；/*释放释放p所指的结点变量空间所指的结点变量空间*/结点分量的访问结点分量的访问指针变量指针变量p的值的值结点地址结点地址结点变量结点变量*p的值的值结点内容结点内容p-data的值的值p指针所指结点的指针所指结点的data域的值域的值p-next的值的
31、值结点结点p的后继结点的地址的后继结点的地址几点说明：几点说明：2.4.1单链表单链表26动态地建立单链表的常用方法有如下两种：动态地建立单链表的常用方法有如下两种：头插法头插法和和尾插法尾插法建立单链表。建立单链表。（1）头插法建立单链表（自学）头插法建立单链表（自学）该方法从一个空表开始，重复读入数据，该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。直到读入结束标志为止。1 1、建立单链表运算、建立单链表运算四、单链表
32、的基本运算四、单链表的基本运算2.4.1单链表单链表27LinkListCreat_LinkList1（）（）/*逆位序输入若干数据元素逆位序输入若干数据元素(以以-1为结束为结束)，建立带表头结点的单链表，建立带表头结点的单链表L*/LinkListL，s;intx;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/*先建立一个带头结点的空单链表先建立一个带头结点的空单链表*/scanf(“%d”,&x);while(x!=-1)s=(LNode*)malloc(sizeof(LNode);/*生成新结点生成新结点*/s-data=x;s-next=
33、L-next;L-next=s;/*插入到表头插入到表头*/scanf(“%d”,&x);/*输入元素值输入元素值*/returnL;/*Creat_LinkList1*/头插法建立单链表算法：头插法建立单链表算法：2.4.1单链表单链表28LinkListcreatelistf(void)charch;LinkListhead;LNode*p;head=null;ch=getchar();while(ch!=n）p=(LNode*)malloc(sizeof(LNode);pdata=ch;pnext=head;head=p;ch=getchar();return(head);假设线性表中假
34、设线性表中结点的数据类结点的数据类型是字符，我型是字符，我们逐个输入这们逐个输入这些字符型的结些字符型的结点，并以换行点，并以换行符符n为输为输入结束标记。入结束标记。头插法建表算头插法建表算法法2.4.1单链表单链表头插法建立单链表算法示例头插法建立单链表算法示例129LinkListcreatelist(intn)intdata;LinkListhead;LNode*phead=NULL;for(i=n;i0;-i)p=(LNode*)malloc(sizeof(LNode);scanf(%d，&pdata);pnext=head;head=p;return(head);头插法头插法建表算
35、法。建表算法。假设线性表假设线性表中结点的数中结点的数据类型是整据类型是整形，我们逐形，我们逐个输入这些个输入这些整形数据的整形数据的结点（设有结点（设有n个），建立个），建立单链表单链表。2.4.1单链表单链表头插法建立单链表算法示例头插法建立单链表算法示例230（2）尾插法建立线性链表尾插法建立线性链表头插法建立链表虽然算法简单，但生成的链表中结点头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。用尾插法建表。尾插法建立单链表尾插法建立单链表该方法从一个空表开始，重复读入数据，生成新该
36、方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾上，直到读入结束标志新结点插入到当前链表的表尾上，直到读入结束标志为止。为止。该方法是将新结点插入到当前链表的表尾上，该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针为此必须增加一个尾指针p p，使其始终指向当前链表的使其始终指向当前链表的尾结点。尾结点。2.4.1单链表单链表312.4.1单链表单链表问题：问题：新结点如何生成？被删除结点如何处理？新结点如何生成？被删除结点如何处理？（动态开辟单元）（动态开辟单元）（释放单
37、元）（释放单元）生成结点变量的标准函数生成结点变量的标准函数p=malloc(sizeof(structnode);/*函数函数malloc分配了一个类型为分配了一个类型为structnode的结点的结点变变量的空间，并将其首地址放入指针变量量的空间，并将其首地址放入指针变量p中；中；不成功，返回不成功，返回NULL。*/。P为动态变量，它是在程序执行过程中，当需要时临时产生的。为动态变量，它是在程序执行过程中，当需要时临时产生的。释放结点变量空间的标准函数释放结点变量空间的标准函数free(p)；/*释放释放p所指的结点变量空间所指的结点变量空间*/32LinkListCreat_LinkL
38、ist2（）（）/*顺位序输入若干数据元素顺位序输入若干数据元素(以以-1为结束为结束)，建立带表头结点的单链表，建立带表头结点的单链表L*/LinkListL,s,r;intx;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/*先建立一个带头结点的空单链表先建立一个带头结点的空单链表*/r=L;/*r用于指向生成链表的当前表尾结点用于指向生成链表的当前表尾结点*/scanf(“%d”,&x);while(x!=-1)s=(LNode*)malloc(sizeof(LNode);/*生成新结生成新结点点*/s-data=x;r-next=s;r=s;
39、/*新结点插入到表尾新结点插入到表尾*/scanf(“%d”,&x);/*输入元素值输入元素值*/r-next=NULL;returnL;/*Creat_LinkList2*/尾插法建立单链表算法：尾插法建立单链表算法：2.4.1单链表单链表33LinkLlistcreatelistr1()charch;LinkListhead=(LinkList)malloc(sizeof(LNode);LNode*p，*rr=head;while(ch=getchar()!=n）p=(LNode*)malloc(sizeof(LNode);pdata=ch;rnext=p;r=p;rnext=NULL;r
40、eturn(head);假设线性表假设线性表中结点的数中结点的数据类型是字据类型是字符，逐个输符，逐个输入这些字符，入这些字符，并以换行符并以换行符n为输为输入结束标记。入结束标记。尾插法建表尾插法建表算法算法尾插法建立单链表算法示例尾插法建立单链表算法示例算法里动态申请新结点空间时未加错误处算法里动态申请新结点空间时未加错误处理，可作下列处理：理，可作下列处理：p=(LNode*)malloc(sizeof(LNode)if(p=NULL)printf(“Nospace”);returnNULL;2.4.1单链表单链表342、求单链表的表长运算、求单链表的表长运算留作作业。留作作业。2.4.
41、1单链表单链表353、单链表的查找运算、单链表的查找运算问题：问题：在线性链表中查第在线性链表中查第i个数据元素，存在则送其个数据元素，存在则送其结点地址；否则返回空结点地址；否则返回空。分析：分析：顺链走到第顺链走到第i个结点，有两种可能：个结点，有两种可能：链表中无第链表中无第i个结点个结点(i表长表长)，查找失败，返回空指针；，查找失败，返回空指针；链表中有第链表中有第i个结点，则返回该结点的指针个结点，则返回该结点的指针。（1 1）按序号查找）按序号查找注：注：在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，也不能象顺序也不能象顺序表中那样直接按序号表中那样
42、直接按序号i i访问结点，而只能从链表的头指针出发，访问结点，而只能从链表的头指针出发，顺链域顺链域nextnext逐个结点往下搜索，直到搜索到第逐个结点往下搜索，直到搜索到第i i个结点为止。个结点为止。因此，链表不是随机存取结构。因此，链表不是随机存取结构。2.4.1单链表单链表36LNode*Get_LinkList(LinkListL,inti)/*在带表头结点的单链表在带表头结点的单链表L中，查找第中，查找第i个元素结点个元素结点*/*若找到则返回其指针，否则返回空若找到则返回其指针，否则返回空*/LNode*p;intj;p=L-next;/*初始化初始化,p指向首元结点（第一个元
43、素结点）指向首元结点（第一个元素结点）*/j=1;/*j为计数器为计数器*/while(p!=NULL&jnext;j+;/*顺指针向后查找，直到顺指针向后查找，直到p指向第指向第i个元素或个元素或p为空为空*/if(j=i)returnp;/*找到，返回其指针找到，返回其指针*/elsereturnNULL;/*未找到，返回空指针未找到，返回空指针*/*Get_LinkList*/单链表的查找算法：单链表的查找算法：2.4.1单链表单链表37（2 2）按值查找）按值查找 按值查找是在链表中，查找是否有结点值等于给定值按值查找是在链表中，查找是否有结点值等于给定值x x的结点，若的结点，若有的
44、话，则返回首次找到的其值为有的话，则返回首次找到的其值为x x的结点的存储位置；否则返回的结点的存储位置；否则返回NULLNULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值查找过程从开始结点出发，顺着链表逐个将结点的值和给定值x x作比较。其算法如下：作比较。其算法如下：该算法的执行时间亦与输入实例中的的取值该算法的执行时间亦与输入实例中的的取值x有关，其平均有关，其平均时间复杂时间复杂度的分析类似于按序号查找，也为度的分析类似于按序号查找，也为O(n)。LNode*Locate_LinkList(LinkListL,datatypex)/*在带表头结点的单链表在带表头结点的单链
45、表L中，查找值为中，查找值为x的的结点结点*/*若找到则返回其指针，否则返回空若找到则返回其指针，否则返回空*/LNode*p;p=L-next;/*初始化初始化,p指向首元结点（第一个元素结点）指向首元结点（第一个元素结点）*/while(p!=NULL&p-data!=x)p=pnext;/*顺指针向后查找，直到找到或表结束顺指针向后查找，直到找到或表结束*/returnp;/*Locate_LinkList*/2.4.1单链表单链表38 插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置个结点的位置上，即插入到上，即插入到a ai-1i-1与
46、与a ai i之间。因此，我们必须之间。因此，我们必须首先首先找到找到a ai-1i-1的存的存储位置储位置p p，然后然后生成一个数据域为生成一个数据域为x x的新结点的新结点* *s s，并令结点并令结点* *p p的的指针域指向新结点，新结点的指针域指向结点指针域指向新结点，新结点的指针域指向结点a ai i。从而实现三从而实现三个结点个结点a ai-1i-1，x x和和a ai i之间的逻辑关系的变化，即：之间的逻辑关系的变化，即：4、单链表的插入运算、单链表的插入运算问题：问题：在单链表的第在单链表的第i个元素位置前插入新元素个元素位置前插入新元素x。分析：分析：在链表第在链表第i个
47、元素前插入元素个元素前插入元素x，需做工作：需做工作：顺链寻找第顺链寻找第i-1个元素结点个元素结点p：找到：找到：生成新结点生成新结点s在第在第i-1和第和第i个元素结点间个元素结点间插入新结点插入新结点s（即修改两条链）；即修改两条链）；未找到：输入出错信息未找到：输入出错信息。2.4.1单链表单链表39intInsert_LinkList(LinkListL,inti,datatypex)/*在带头结点的单链表在带头结点的单链表L的第的第i个元素位置前插入新元素个元素位置前插入新元素x*/LNode*p,*s;intj;p=L;j=0;while(P!=NULL&jnext;j=j+1;
48、if(p=NULL)/*i大于表长大于表长*/printf(“参数参数i有错有错”；return0;elses=malloc(sizeof(LNode);/*生成新结点生成新结点*/sdata=x;snext=pnext;/*新结点插入链表中新结点插入链表中*/pnext=s;return1;/*Insert_LinkList*/单链表的插入算法：单链表的插入算法：2.4.1单链表单链表40删除运算是将表的第删除运算是将表的第i个元素结点删去。因为在单链表个元素结点删去。因为在单链表中结点中结点ai的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点ai-1的指针域的指针域next中，所以
49、我们必须首先找到中，所以我们必须首先找到ai-1的存储位置的存储位置p。然后令然后令pnext指向指向ai的直接后继结点，即把的直接后继结点，即把ai从链上摘下。最后从链上摘下。最后释放结点释放结点ai的空间，将其归还给的空间，将其归还给“存储池存储池”。即：即：5、单链表的删除运算、单链表的删除运算问题：问题：在单链表中删除第在单链表中删除第i个数据元素。个数据元素。分析：分析：在链表中删除第在链表中删除第i个元素结点个元素结点，需做工作：需做工作：顺链寻找第顺链寻找第i-1个元素结点个元素结点p：找到：找到：第第i个元素结点存在，则从链表中摘除，并个元素结点存在，则从链表中摘除，并将之送将
50、之送回系统回系统；未找到：删除位置不合理，输入出错信息未找到：删除位置不合理，输入出错信息。2.4.1单链表单链表41intDel_LinkList(LinkListL,inti)/*在带头结点的单链表在带头结点的单链表L中删除第中删除第i个元素结点个元素结点*/LinkListp,s;intj;p=L;j=0;while(P!=NULL&jnext;j=j+1;if(p=NULL)printf(“第第i-1个结点不存在个结点不存在”；return-1;elseif(p-next=NULL)printf(“第第i个结点不存在个结点不存在”；return0;elses=p-next;/*s指向第
51、指向第i个结点个结点*/pnext=snext;/*从表删除结点从表删除结点s*/free(s);/*释放结点释放结点s*/return1;/*Del_LinkList*/单链表的删除算法：单链表的删除算法：2.4.1单链表单链表42 设设单链表的单链表的长度为长度为n n，则删去第则删去第i i个结点仅当个结点仅当1in1in时是合法的。注意，当时是合法的。注意，当i=n+1i=n+1时，虽然时，虽然被删结点不存在，但其前趋结点却存在，它是被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋终端结点。因此被删结点的直接前趋* *p p存在并存在并不意味着被删结点就一定存在
52、，仅当不意味着被删结点就一定存在，仅当* *p p存在存在（即（即p!=NULLp!=NULL）且且* *p p不是终端结点不是终端结点 （即（即pnext!=NULLpnext!=NULL）时，才能确定被删结点时，才能确定被删结点存在。存在。 显然此算法的时间复杂度也是显然此算法的时间复杂度也是O(n)O(n)。 从上面的讨论可以看出，从上面的讨论可以看出，链表上实现插入和链表上实现插入和删除运算，无须移动结点，仅需修改指针删除运算，无须移动结点，仅需修改指针。2.4.1单链表单链表43a1an.h(非空表非空表)(空表空表,即即h-next=h)1、定义：、定义：仍是单链表，只是在最后一个
53、结点的链域中不仍是单链表，只是在最后一个结点的链域中不是放是放“NULL”，而是放上头结点的地址，形成环形。而是放上头结点的地址，形成环形。表形式：表形式：h2、特点：、特点：1）环形：可以从表中任一结点开始访问到其它任意结点；）环形：可以从表中任一结点开始访问到其它任意结点；2）不必提供头指针，也可找到表头结点，即表的开始位置；）不必提供头指针，也可找到表头结点，即表的开始位置；3）可简化某些运算。）可简化某些运算。2.4.2循环链表循环链表443、循环链表的运算（插、删、查）：、循环链表的运算（插、删、查）：与单链表的运算基本一致，差别只是循环条件的与单链表的运算基本一致，差别只是循环条件
54、的判别。判别。 由于循环链表中没有由于循环链表中没有NULLNULL指针，故涉及查找操作指针，故涉及查找操作时，其终止条件就不再像非循环链表那样判断时，其终止条件就不再像非循环链表那样判断p p或或p-nextp-next是否为空，而是判断它们是否等于某一指定是否为空，而是判断它们是否等于某一指定指针，如头指针指针，如头指针。 在很多实际问题中，表的操作常常是在表的首尾位置上在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便进行，此时头指针表示的单循环链表就显得不够方便. .如果如果改用尾指针改用尾指针rearrear来表示单循环链表，则查找开始结点
55、来表示单循环链表，则查找开始结点a a1 1和和终端结点终端结点a an n都很方便，它们的存储位置分别是都很方便，它们的存储位置分别是(rear-(rear-next)-nextnext)-next和和rearrear，显然，查找时间都是显然，查找时间都是O(1)O(1)。因此，因此，实际中多采用尾指针表示单循环链表。实际中多采用尾指针表示单循环链表。2.4.2循环链表循环链表45例、在链表上实现将两个线性表例、在链表上实现将两个线性表(a1，a2，a3，an)和和(b1，b2，b3，bn)链接成一个线性表的运算（设线链接成一个线性表的运算（设线性表分别用带尾指针的循环链表表示）。性表分别用
56、带尾指针的循环链表表示）。LinkListconnect(LinkListR1，LinkListR2)p=R1-next;R1-next=R2-next-next;free(R2-next);R2-next=p;return(R2);2.4.2循环链表循环链表46任给一点任给一点P P，线性链表：只能找到其后继结点，由线性链表：只能找到其后继结点，由P P得不到其前趋结点。得不到其前趋结点。循环链表：由循环链表：由P P其前趋、后继均能得到，但查其前趋、后继均能得到，但查P P的前趋要兜的前趋要兜圈子。圈子。 一、定义一、定义 在链表中，每个结点都有二个链域在链表中，每个结点都有二个链域 为为
57、方便查结点的前趋方便查结点的前趋双向循环链表双向循环链表priordatanext结点形式：结点形式： 前趋指针前趋指针指向直接前趋结点指向直接前趋结点 后继指针后继指针指向直接后继结点指向直接后继结点2.4.3双向循环链表双向循环链表47二、示意图：二、示意图： （见黑板）（见黑板）三、特点：三、特点： 对任一结点，找其前趋结点和后继结点都很容易；对任一结点，找其前趋结点和后继结点都很容易； 所需空间增加。所需空间增加。四、类型定义：四、类型定义：typedefstructdLNodedatatypedata;structdLNode*prior,*next;DLNode,*DLinkLis
58、t;2.4.3双向循环链表双向循环链表481、摘除操作、摘除操作p指向待删结点，则从双向链表中摘除结点指向待删结点，则从双向链表中摘除结点p需修改二条链。需修改二条链。五、双向循环链表的运算五、双向循环链表的运算2、插入操作、插入操作要在要在p指向结点的前面插入一个结点指向结点的前面插入一个结点q，则则需修改四条链。需修改四条链。注意：注意：与单链表的插入和删除操作不同的是，在双链表与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。中插入和删除必须同时修改两个方向上的指针。2.4.2循环链表循环链表49优点优点优点优点：结构简单，存取方便、迅速；：结构简单，存
59、取方便、迅速；：结构简单，存取方便、迅速；：结构简单，存取方便、迅速；缺点缺点缺点缺点： 作插入、删除运算需移动大量数据；作插入、删除运算需移动大量数据；作插入、删除运算需移动大量数据；作插入、删除运算需移动大量数据； 表难以扩充（因需一片连续空间）表难以扩充（因需一片连续空间）表难以扩充（因需一片连续空间）表难以扩充（因需一片连续空间）顺序存储结构顺序存储结构:链式存储结构链式存储结构:优点优点优点优点：结点的插入、删除操作比较方便。：结点的插入、删除操作比较方便。：结点的插入、删除操作比较方便。：结点的插入、删除操作比较方便。缺点缺点缺点缺点：需增设指示结点之间关系的指针域：需增设指示结点
60、之间关系的指针域：需增设指示结点之间关系的指针域：需增设指示结点之间关系的指针域, , , ,多多多多 占空间占空间占空间占空间; ; ; ;存取元素不如顺序表方便存取元素不如顺序表方便存取元素不如顺序表方便存取元素不如顺序表方便2.5顺序表和链表的比较顺序表和链表的比较502.6应用举例应用举例问问题题：设设一一线线性性表表以以顺顺序序存存储储结结构构存存储储，试试写写一一算算法法，尽尽可可能能快快地地将将顺顺序序表表逆逆置置（即即元元素素次次序序与与原原次次序序相相反反），并计算算法中移动元素次数。（要求用最少的附加空间）。并计算算法中移动元素次数。（要求用最少的附加空间）。方法一：方法一
61、： void reverse_Sreverse_SqList1(SeqList *L ) /*将顺序表将顺序表L逆序逆序*/inti,j;datatypetemp; for ( i=0,j=L-last; ilast; idatai; temp=L-datai; L-datai=L-dataj; L-datai=L-dataj; /* /*对应两元素交换对应两元素交换* */ / L-dataj=temp ; L-dataj=temp ; /*/*reverse_reverse_sqlist1*/ */ 例例1 1、顺序表的逆置顺序表的逆置51顺序表的逆置方法二：顺序表的逆置方法二： void
62、 reverse_Sreverse_SqList2(SeqList *L ) /*将顺序表将顺序表L逆序逆序*/inti;datatypetemp; for ( i=0; ilast+1)/2; i+ ) for ( i=0; ilast+1)/2; i+ ) temp=L-datai; temp=L-datai; /* /*对应两元素交换对应两元素交换* */ / L-datai=L-dataL-last-i; L-datai=L-dataL-last-i; L-dataL-last-i=temp ; L-dataL-last-i=temp ; /*/*reverse_Sreverse_Sq
63、List2*/*/2.6应用举例应用举例52问题：问题：设顺序表设顺序表L中的数据元素递增有序。试写一算中的数据元素递增有序。试写一算法法，将将元元素素x插插入入到到顺顺序序表表的的适适当当位位置置上上，以以保保持持该该表表的有序性。的有序性。(有序顺序表的插入有序顺序表的插入)算法思想：算法思想：（1）查找）查找x在顺序表中的插入位置，即求第一个满足在顺序表中的插入位置，即求第一个满足L-dataix的的i值（值（i的初值为的初值为0）;（2）将顺序表中的最后一个到第）将顺序表中的最后一个到第i个位置的元素依次后个位置的元素依次后移移一个位置一个位置;（3）将）将x插入到插入到L-datai
64、中且将中且将L-last增增1。例例2 2、有序顺序表的插入有序顺序表的插入2.6应用举例应用举例53有序顺序表的插入算法：有序顺序表的插入算法：voidInsertOrderList(SeqList*L,datatypex)/*将元素将元素x插入到递增排列的顺序表插入到递增排列的顺序表L中中*/inti,j;if(L-last=MAXSIZE-1)printf(“表满表满“);return;i=0;while(ilast&xL-datai)i+;if(ilast)/*插入位置在第一个至最后一个元素之间插入位置在第一个至最后一个元素之间*/for(j=L-last;j=i;j-)L-dataj
65、+1=L-dataj;/*元素后移元素后移*/L-datai=x;/*插入插入x*/elseL-datai=x;/*直接插入在表尾直接插入在表尾*/L-last+;/*InsertOrderList*/2.6应用举例应用举例54问题：问题：(P24例例2.2)有顺序表有顺序表A和和B，其元素均按从小到大的升序其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序排列，编写一个算法将它们合并成一个顺序C，要求要求C的元素也的元素也是从小到大升序排列。是从小到大升序排列。(有序顺序表的合并有序顺序表的合并) void void merge(SeqListmerge(SeqList A,Se
66、qListA,SeqList B,SeqListB,SeqList *C) *C) /* /*有序顺序表有序顺序表A A和和B B合并成一个递增有序表合并成一个递增有序表C*/C*/ intint i,j,ki,j,k; ; i=0; j=0; k=0; i=0; j=0; k=0; while( i= while( i=A.lastA.last & j= & j=B.lastB.last ) ) if ( if ( A.dataiA.datai datak = C-datak = A.dataiA.datai; ; i+; k+;i+; k+; else else C-datak = C-d
67、atak = B.datajB.dataj; ; j+; k+; j+; k+; while( i= while( idatak = C-datak = A.dataiA.datai; ; i+; k+; i+; k+; while( j= while( jdatak = C-datak = B.datajB.dataj; ; j+; k+; j+; k+; C-last=k-1; C-last=k-1; 例例3 3、两个有序顺序表的合并、两个有序顺序表的合并2.6应用举例应用举例55Ha1a2.an（）Hanan-1.a1（b）问题：问题：试写出一个将试写出一个将单链表逆转单链表逆转的算法。
68、即将下图的算法。即将下图（）中的链表修改成（）的形式。（）中的链表修改成（）的形式。例例4 4、单链表逆转单链表逆转2.6应用举例应用举例56单链表逆转算法单链表逆转算法：从链表中第一个结点开始，依次取下插入到：从链表中第一个结点开始，依次取下插入到表表头结点后。头结点后。void reverse_linklist3 ( void reverse_linklist3 ( LinkListLinkList H ) H ) /* /*对对H H所指的单链表所指的单链表( (带表头结点带表头结点) )进行逆置进行逆置* */ / LNodeLNode *p, *q; *p, *q; p=H-next
69、 ; p=H-next ; /*p/*p指向第一个数据结点指向第一个数据结点* */ / H-next=NULL ; H-next=NULL ; while ( p ) while ( p ) q=p; q=p; p=p-next; p=p-next; q-next=H-next ; q-next=H-next ; / /将将当前结点当前结点q q插入到头结点后插入到头结点后* */ / H-next=q ; H-next=q ; /*reverse_linklist3*/*reverse_linklist3*/2.6应用举例应用举例57问题：问题：试写出试写出有序链表的插入有序链表的插入算法
70、。设是链表头指算法。设是链表头指针，待插入元素为（设链表带表头结点）针，待插入元素为（设链表带表头结点）。算法思想：算法思想：生成新结点生成新结点s，其数据域置为其数据域置为x；顺链找到插入位置；插入。顺链找到插入位置；插入。voidinsert_linllist(LinkListLa;datatypex)/*在有序链表在有序链表La（带表头结点）中按序插入元素带表头结点）中按序插入元素x*/LNode*p,*s,*q;s=(LinkList)malloc(sizeof(LNode);s-data=x;q=La;/*为为s结点寻找插入位置，结点寻找插入位置，p指向待比较的结点指向待比较的结点*
71、/p=q-next;/*q指向指向p的前驱结点的前驱结点*/while(p!=NULL&p-datanext;s-next=p;q-next=s;/*insert_linklist*/例例5 5、有序链表的插入有序链表的插入2.6应用举例应用举例58问题：问题：两个递增有序单链表合并成一个递减链表。两个递增有序单链表合并成一个递减链表。 （P27P27例题例题2.6 2.6 自读，上机实习）自读，上机实习）LinkListmerge(LinkListA,LinkListB)LinkListC;LNode*p,*q,*s;p=A-next;q=B-next;C=A;C-next=NULL;whi
72、le(p&q)if(p-datadata)s=p;p=p-next;elses=q;q=q-next;s-next=C-next;C-next=s;/*从原从原A、B表上摘下较小者，插入到表上摘下较小者，插入到C表的头部表的头部*/if(p=NULL)p=q;while(p)s=p;p=p-next;s-next=C-next;C-next=s;returnC;/*merge*/例例6 6、两个递增有序链表合并成一个递减链表两个递增有序链表合并成一个递减链表59问题问题:将两个递增有序的单链表将两个递增有序的单链表A、B合并成一个递增合并成一个递增有序的链表有序的链表C。(有序链表的合并，从小
73、到大有序链表的合并，从小到大)LinkListmerge(LinkListA,LinkListB)LinkListC;LNode*p,*q,*s,*r;p=A-next;q=B-next;C=A;r=C;/*r指针始终指向合并表指针始终指向合并表C的当前表尾结点的当前表尾结点*/while(p&q)if(p-datadata)s=p;p=p-next;elses=q;q=q-next;r-next=s;r=s;/*从原从原A、B表上摘下较小者，插入到表上摘下较小者，插入到C表的表尾表的表尾*/if(p=NULL)p=q;r-next=p;returnC;/*merge*/例例7 7、两个递增有
74、序链合并成一个递增链表两个递增有序链合并成一个递增链表60问题问题:在以在以la为头指针的线性链表中，把元素插在元素为头指针的线性链表中，把元素插在元素值为值为a的结点紧后面，若表中无的结点紧后面，若表中无a，则把插在表头则把插在表头处。（设线性链表带表头结点）处。（设线性链表带表头结点）。voidinsert_x(LinkListla,datatypex,datatypea)/*在线性链表在线性链表la中，把元素插在元素值为的结点紧后面，若中，把元素插在元素值为的结点紧后面，若中无，则把插在表头处。中无，则把插在表头处。*/LNode*p,*s;s=(LinkList)malloc(size
75、of(LNode);s-data=x;p=la-next;while(p&p-data!=a)p=p-next;/*表表未结束且当前结点的值不等于未结束且当前结点的值不等于a，则续往前找则续往前找*/if(p)s-next=p-next;p-next=s;/*找到，找到，s插入插入p结点后结点后*/elses-next=la-next;la-next=s;/*未找到，未找到，s插入到头结点后插入到头结点后*/*insert_x*/例例8 8、单链表插入单链表插入61第二章第二章线性表小结线性表小结掌握线性表的定义及逻辑结构特性掌握线性表的定义及逻辑结构特性(即数据元素之间即数据元素之间存在着线
76、性关系存在着线性关系);掌握线性表的二种存储结构即：掌握线性表的二种存储结构即：顺序存储结构顺序存储结构线性链表线性链表链式存储结构链式存储结构循环链表循环链表双向循环链表双向循环链表了解链表中的表头结点、头指针、首元结点的区别；了解链表中的表头结点、头指针、首元结点的区别；掌握线性表在顺序存储结构下的定义，表示（描述方掌握线性表在顺序存储结构下的定义，表示（描述方法），法），熟练掌握熟练掌握在其上的插入、删除、查找等算法；在其上的插入、删除、查找等算法；熟练掌握熟练掌握单链表的：单链表的：定义、表示（数据域、链）定义、表示（数据域、链）和算法（建立，插入，删除、查找）；和算法（建立，插入，删
77、除、查找）；（注意指针注意指针P和结点和结点*P的对应关系，结点的后继表示，的对应关系，结点的后继表示，结点的前进，插、删时链域的修改等等结点的前进，插、删时链域的修改等等）62掌握循环链表：结构形式、特点；掌握循环链表：结构形式、特点；掌握双向循环链表：结构形式（数据域、前驱掌握双向循环链表：结构形式（数据域、前驱指针域、后继指针域），特点，插、删运算算法指针域、后继指针域），特点，插、删运算算法（注意怎样勾链及勾链顺序）；（注意怎样勾链及勾链顺序）；知道从时间复杂度角度比较线性表两种存储结构的知道从时间复杂度角度比较线性表两种存储结构的缺点及适用场合；缺点及适用场合；注意：链表是本章的重点
78、和难点，要求熟练掌握在注意：链表是本章的重点和难点，要求熟练掌握在各种链表结构上实现建表，插入，删除等算法，各种链表结构上实现建表，插入，删除等算法，重点：线性链表中插入和删除结点的算法。重点：线性链表中插入和删除结点的算法。632.6应用举例应用举例某百贷公司的仓库有一批电视机，按其价格从低某百贷公司的仓库有一批电视机，按其价格从低到高的顺序构成一个单向链表，存于计算机。链表到高的顺序构成一个单向链表，存于计算机。链表的每个结点指出同样价格的电视机有若干台，的每个结点指出同样价格的电视机有若干台，numcostnext现：现：1）有台价格为元的电视机需要进入仓库，）有台价格为元的电视机需要进
79、入仓库，试写出仓库电视机链表增加电视机的算法。（要求试写出仓库电视机链表增加电视机的算法。（要求向链表中每个结点的价格域的值不能相同）向链表中每个结点的价格域的值不能相同）2）有台、价格为元的电视机需要出仓库，）有台、价格为元的电视机需要出仓库，试写出可从仓库电视机链表减少电视机的算法（注：试写出可从仓库电视机链表减少电视机的算法（注：若出库后，该价格电视机数量为若出库后，该价格电视机数量为0，则要从链表中，则要从链表中删去该电视机结点）；删去该电视机结点）；数量数量价格价格链域链域64电视机链表结点设计：电视机链表结点设计：typedefstructnodeintcost;intnum;st
80、ructnode*next;tvnode,*tvLinkList;65电视机链表入库算法：电视机链表入库算法：voidinsert(tvLinkListhead,intm,inth)/*在以在以head为头为头指针的电视机链表中增加指针的电视机链表中增加m台，台，*/*价格为价格为h的的电视机（链表带表头结点）电视机（链表带表头结点）*/q=head;p=q-next;While(p!=NULL&p-costnext;/*顺链找增加位置顺链找增加位置*/if(p!=NULL&p-cost=h)p-num=p-num+m;else/*插入新电视机结点插入新电视机结点*/s=(structnode
81、*)malloc(sizeof(structnode);s-cost=h;s-num=m;q-next=s;s-next=p;/*insert*/66电视机链表出库算法：电视机链表出库算法：voiddelete(tvLinkListhead,intm,inth)/*从从以以head为为头头指指针针的的电电视视机机链链表表中中减减少少m台台，*/*价格为价格为h的电视机（链表带表头结点）的电视机（链表带表头结点）*/q=head;p=head-next;while(p!=NULL&p-cost!=h)q=p;p=p-next;/*顺顺链链找找价价格格为为h的的电电视视机机结结点点*/if(p=NULL)printf(“仓库中无价格为仓库中无价格为h的电视机的电视机”);elseif(p-num=m)p-num=p-num-m;if(p-num=0)q-next=p-next;elseprintf(“仓仓库库中中价价格格为为h的的电电视视机机只只有有”,p-num,“台台”);67
