第2章线性表课件

关于结构体类型与结构体变量（1）结构体类型与结构体变量是两个不同的概念，其区别如同int类型与int型变量的区别一样。（2）结构体类型中的成员名，可以与程序中的变量同名，它们代表不同的对象，互不干扰。1

如何访问结构体变量的成员?假设有结构体变量var,指针变量pointer指向结构变量var，则以下三种形式等价：

1）var.成员

2）pointer->成员

3）(*pointer).成员/*“*pointer”外面的括号不能省！*/注意：在格式（1）中，分量运算符左侧的运算对象，只能是结构体变量；而在格式（2）中，指向运算符左侧的运算对象，只能是指向结构体变量（或结构体数组）的指针变量。2C语言动态内存分配(1)库函数malloc()·用法：void*malloc(unsignedsize)·功能：在内存的动态存储区分配１个长度为

size的连续空间。·返回值：申请成功，则返回新分配内存块的起始地址；否则，返回NULL。·函数原型：malloc.h，stdlib.h。3malloc()函数的返回值是一个无类型指针，其特点是可以指向任何类型的数据。但在实际使用malloc()函数时，必须将其返回值强制转换成被赋值指针变量的数据类型，以免出错。C语言动态内存分配4(2)运算符sizeof·格式：sizeof(变量名／类型名)·功能：求变量／类型占用的内存字节数（正整数）。例如，在IBM-PC机上，sizeof(int)=2。C语言动态内存分配5（3）库函数free()·用法：voidfree(void*ptr)·功能：释放由ptr指向的内存块（ptr是调用malloc()函数的返回值）。·返回值：无。·函数原型：stdlib.h，malloc.h。C语言动态内存分配6typedef语句typedef语句(类型说明语句)的功能是利用某个已有的数据类型定义一个新的数据类型。其格式为:

typedef数据类型名新数据类型名如：typedefintinteger;integeri,j;

7typedef语句例：typedefstruct

/*学生信息结构体类型：由学号、姓名、性别和生日共4项组成*/{charno[7];charname[9];charsex[3];structdatebirthday;}

std_info;

其后的变量说明语句中可以省略结构体类型说明符struct:std_infostudent;8线性结构的定义：

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）

简言之，线性结构反映结点间的逻辑关系是

的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1:1)9第2章线性表2.1线性表抽象数据类型2.2线性表的顺序表示和实现2.3线性表的链式表示和实现10（a0,a1,…ai-1，ai,ai＋1

，…,an-1）线性表的逻辑结构：n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点11

（A,B,C,D,……,Z）学号姓名性别年龄班级012019010622陈建武男192019级电信0301班012019010704赵玉凤女182019级电信0302班012019010813王泽男192019级电信0303班012019010906薛荃男192019级电信0304班012019011018王春男192019级电信0305班：：：

：：例：分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。例：分析26个英文字母组成的英文表是什么结构。12线性表抽象数据类型

它包括两个方面：数据集合：｛a0,a1,…,an-1｝ai的数据类型为DataType

操作集合：(1)ListInitiate(L)初始化线性表

(2)ListInsert(L,i,x)插入数据元素

(3)ListLength(L)求当前数据元素个数

(4)ListDelete(L,i,x)删除数据元素

(5)ListGet(L,i,x)取数据元素13线性表的存储结构(1)顺序存储结构:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。特点：逻辑上相邻的元素，物理上也相邻。(2)链式存储结构:它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。特点：任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现的。142.2线性表的顺序表示和实现一、顺序表的存储结构二、顺序表的实现三、顺序表的运算效率分析152.2.1、顺序表的存储结构表示

1、顺序表：用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：

V[n]的有效范围是从V[0]～V[n-1]16若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组V[n]的下标）。设首元素a0的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：

LOC(ai

)=LOC(a0)+L*i对上述公式的解释如图所示2.2.1顺序表的存储结构表示17a0a1……aiai+1……an-1

地址内容元素在表中的位序0i1n-1空闲区i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(MaxSize-1)LLOC(ai)=LOC(a0)+L*i线性表的顺序存储结构示意图18设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？113LOC(M[3])=98+5×3=113解：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例:19用C语言描述：typedefstruct{DateTypelist[MaxSize];intsize;}SeqList;

/*MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size≤MaxSize，SeqList是该结构体的名字。*/2.2.2顺序表的实现20顺序表的操作(1)ListInitiate(L)初始化线性表

(2)ListInsert(L,i,x)插入数据元素

(3)ListLength(L)求当前数据元素个数

(4)ListDelete(L,i,x)删除数据元素

(5)ListGet(L,i,x)取数据元素212.顺序表操作的实现

（1）初始化ListInitiate(L)voidListInitiate(SeqList*L) {L->size=0; /*定义初始数据元素个数*/}

（2）求当前数据元素个数ListLength(L)intListLength(SeqListL) {returnL.size;}

22线性表操作

ListInsert(L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？23

(a0,…,ai-1,ai,…,an-1)改变为a0a1

…ai-1ai

…an-1a0a1

…ai-1

…aiean-1<ai-1,ai><ai-1,e>,<e,ai>表的长度增加(a0,…,ai-1,e,ai,…,an-1)24插入算法ListInsert(L,i,x)描述算法功能：在线性表（n个元素）的第i个位置前插入一个元素输入：顺序表输出：插入元素后的顺序表1.判断表是否满，如果满则显示提示信息2.判断插入的位置i是否合法(n>i>=0)，如果不合法，则显示错误信息3.将第n-1至第i

位的元素向后移动一个位置4.将要插入的元素写到第i个位置；5.表长加1。25（3）插入数据元素ListInsert(L,i,x)关键代码

intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];/*依次后移*/

L->list[i]=x; /*插入x*/ L->size++; /*元素个数加1*/ return1;}26线性表操作

ListDelete(L,i,e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？27

(a0,…,ai-1,ai,ai+1,…,an-1)改变为ai+1…an-1<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a0a1

…ai-1ai

ai+1

…

an-1a0a1

…ai-1

(a0,…,ai-1,ai+1,…,an-1)28删除算法ListDelete(L,i,x)描述算法功能：删除线性表（n个元素）的第i个位置上的元素输入：顺序表输出：删除的元素1.判断删除的位置i是否合法(n-1>i>=0)，如果不合法，则显示错误信息2.将第i+1至第n-1位的元素向前移动一个位置；3.表长减1。29（4）删除数据元素ListDelete(L,i,x)关键代码intListDelete(SeqList*L,inti,DataType*x) {intj;

*x=L->list[i];/*保存删除的元素到x中*/

for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];/*依次前移*/

L->size--; /*数据元素个数减1*/

return1;}30查找元素算法ListGet(L,i,x)描述算法功能：查找线性表（n个元素）的第i个位置上的元素输入：顺序表输出：查找到的元素1.判断查找的位置i是否合法(n-1>i>=0)，如果不合法，则显示错误信息2.直接取出第i个位置的元素31（5）取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("参数i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}32例2-1：建立一个线性表，先依次输入数据元素1，2，3，4，…，10，然后删除５，最后依次显示当前线性表中的数据元素。假设该线性的数据元素个数最坏情况下不会超过100个。

33实现方法：

1、采用直接编写一个主函数实现。

2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList.h的文件中，通过#include“SeqList.h”

）程序设计如下：#include<stdio.h> #defineMaxSize100 typedefintDataType;#include"SeqList.h"

34voidmain(void){SeqListmyList;inti,x;

ListInitiate(&myList);for(i=0;i<10;i++)

ListInsert(&myList,i,i+1);

ListDelete(&myList,4,&x);for(i=0;i<ListLength(myList);i++){ListGet(myList,i,&x);printf(“%d”,x);}}程序运行结果：1234678910351.头文件分为系统头文件自定义头文件2.头文件的处理：先把被包含的文件内容复制到引用头文件的语句处，形成一个新的源程序，再编译成一个目标文件。C语言头文件362.2.3顺序表操作的效率分析算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）

T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。时间效率分析:37推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移n次；若在a1后面插入，要后移n-1个元素，后移次数为n-1;……若在an-1后面插入，要后移1个元素；若在尾结点an之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+…+n=n(n+1)/2

故插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)

共有多少种插入形式?——连头带尾有n+1种!38

顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复杂度都为O(1)主要优点是算法简单，空间单元利用率高；主要缺点是需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。主要优缺点39思考题P22页，删除算法的效率Edl是如何计算出来的？402.5算法设计举例例2-4设计一个顺序表的删除函数，把顺序表L中的数据元素x删除。算法思想：首先，找到要删除元素的位置，然后，从这个位置到最后一个元素，逐个前移，最后，把元素个数减1。41intListDataDelete(SeqList*L,DataTypex){inti,j;for(i=0;i<L->size;i++) if(x==L->list[i])break;

if(i==L->size)return0; else {for(j=i;j<L->size;j++) L->list[j]=L->list[j+1];

L->size--; return1;}}

42算法练习题1.编写算法实现顺序表的逆置，要求把顺序表A中的数据元素序列（a0,a1,a2,…..an-1）逆置为（an-1,…..a2,a1,a0），并存储到顺序表B中。43算法练习题2.编写算法实现顺序表的就地逆置，把数据元素序列（a0,a1,a2,…..an-1）逆置为（an-1,…..a2,a1,a0）。442.3线性表的链式表示和实现一、单链表的存储结构二、单链表的操作实现三、链表的运算效率分析45１、单链式及表示方法(1)单链表:构成链表的结点只有一个指向直接后继结点的指针。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！让每个存储结点都包含两部分：数据域和指针域指针域数据域nextdata或样式：数据域：存储元素数值数据指针域：存储直接后继的存储位置设计思想：牺牲空间效率换取时间效率一、单链表的存储结构46例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）链表存放示意图如下：a1heada2/\an……讨论1：每个存储结点都包含两部分：数据域和

。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由

指示。其直接前驱结点的链域的值指针域(链域)47

线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=

Y=

Z=

,

首址=

末址=

。例：481）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head(2)与链式存储有关的术语：494）头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；首元结点是指链表中存储线性表第一个数据元素a０的结点。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。示意图如下：50答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！51一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31２、带头结点单链表和不带头结点单链表的比较例：52上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点头结点不计入链表长度！53对比带头结点的单链表的插入、删除过程和不带带头结点的单链表的插入、删除过程，可以得知：

●若设计的单链表带头结点，则无论是在第一个数据元素结点前插入还是在其他数据元素结点前插入都不会改变头指针的数值。

●若设计的单链表不带头结点，则在第一个数据元素结点前插入与在其他数据元素结点前插入其算法的处理方法不同。

●在单链表中删除一个结点时类似。

因此，单链表一般构造成带头结点的单链表。54讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：以26个字母的链表为例，每个结点都有两个分量：字符型指针型设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，以下两个分量赋值方法是否正确？p*nextdatanode方式1：直接表示为

node.data＝'a'；node.next=q方式2：p指向结点首地址，然后p->data='a';p->next=q;方式3：p指向结点首地址，然后(*p).data='a'；(*p).next＝q‘a’‘b’qp55sizeof(x)——计算x的长度malloc(m)—开m字节空间free(p)——删除一个变量问1：自定义结构类型变量node的长度m是多少？问2：结构变量node的首地址(指针p）是多少？问3：怎样删除结构变量node？*nextdatanode，长度为m字节pm＝sizeof(node)//单位是字节p＝(node*)malloc(m)free(p)//只能借助node的指针删除！56②对于指向结构类型的指针变量，可说明为：

SLNode*p,*q;//或用

structNode*p,*q;//注：上面已经定义了SLNode为用户自定义的Node类型。①类型定义可以写为：typedefstructNode//Node是自定义结构类型名称{DataTypedata;//定义数据域的变量名及其类型

structNode*next;//定义指针域的变量名及其类型}SLNode，*p;//SLNode是Node结构类型的类型替代,

*p是指针型的Node结构类型的替代

此结构数据类型的C表示法57单链表基本操作1.初始化2.求单链表中元素个数3.插入元素4.删除元素5.取数据元素6.撤消单链表二、单链表的操作实现58１、初始化voidListInitiate(SLNode**head)／*初始化*/{ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/

*head=(SLNode)malloc(sizeof(SLNode));(*head)->next=NULL; }59２、求单链表中数据元素的个数

intListLength(SLNode*head)

{

SLNode*p=head;

/*p指向头结点*/

intsize=0;

/*size初始为0*/

while(p->next!=NULL)/*循环计数*/

{

p=p->next;

size++;

}

returnsize;

}60在链表中插入一个元素X的示意图如下：Xqabp链表插入的核心语句：Step1：q->next=p->next;Step2：p->next=q；p->nextq->next思考：Step1和2能互换么？X结点的生成方式：m=sizeof(SLNode);q=(SLNode*)malloc(m);q->data=X;q->next=?bap插入X３、向单链表中插入一个元素61intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q; intj; p=head; j=-1;(1)while(p->next!=NULL&&j<i-1){ p=p->next;j++; }

if(j!=i-1){ printf("插入位置参数错！"); return0;}(2)

q=(SLNode*)malloc(sizeof(SLNode)); q->data=x;q->next=p->next;

p->next=q;(4) return1;}

注：此单链表是带头结点的62在链表中删除某元素b的示意图如下：cabp删除动作的核心语句（可以借助辅助指针变量s）：s=p->next;//首先保存b的指针，靠它才能找到c；p->next=s->next;

//将a、c两结点相连，淘汰b结点；free(s)；//彻底释放b结点空间p->next思考：省略free(s)语句行不行？(p->next)->next××s４、从单链表中删除一个元素63intListDelete(SLNode*head,inti,DataType*x)

{ SLNode*p,*s; intj;(1)p=head;

j=-1; while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)

{

p=p->next; j++; }

if(j!=i-1) {

printf(“插入位置参数错！”);

return0; }(2)

s=p->next;*x=s->data;(3)

p->next=s->next;

free(s);

return1;

} 645.取数据元素ListGet(head,i,x)intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;

p=head;j=-1;

while(p->next!=NULL&&j<i){p=p->next; j++; }

if(j!=i){printf(“取元素位置参数错！”); return0;}

*x=p->data;return1;}

65（6）撤消单链表Destroy(head)voidDestroy(SLNode**head){SLNode*p,*p1;

p=*head;while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}66三、单链表的操作效率分析（1）查找

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为

O(n)。时间效率分析（2）插入和删除

因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为

O(1)。但是，如果要在单链表中进行在某结点前插或删除操作，因为要从头查找前驱结点，所以一般情况下，单链表插入和删除操作的时间复杂度是O(n)（同顺序表）。67单链表操作的效率分析（P34页）单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：删除一个数据元素时比较数据元素的平均次数为：另外，单链表求数据元素个数操作的时间复杂度为O(n)。68和顺序表相比主要优点是不需要预先确定数据元素的最大个数，插入和删除操作不需要移动数据元素；主要缺点是查找数据元素时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素。另外，每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。单链表和顺序表相比，单链表的优点和缺点正好相反。69四、应用举例例2-3编程实现：建立一个单链表，首先依次输入数据元素１,２,…,10，然后删除数据元素５，最后依次显示当前表中的数据元素。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefintDataType; #include"LinList.h"重点是链表70

voidmain(void){SLNode*head;inti,x;

ListInitiate(&head);

for(i=0;i<10;i++)

ListInsert(head,i,i+1);

ListDelete(head,4,&x);

for(i=0;i<ListLength(head);i++){ListGet(head,i,&x); printf(“%d”,x); }

Destroy(&head);}程序运行结果：123467891071

最后一个结点的指针域的指针又指回第一个结点的链表a1a2…...an1.循环链表

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。五、其它形式的链表72

2.双向链表a1a2…...an^^73双向循环链表空表非空表a1a2…...an74（１）双向循环链表的存储结构双向循环链表：链表中每个结点除后继指针域和数据域外还有一个前驱指针域。其结点的结构为：双向链表结点的结构体定义如下：

typedefstructNode{DataTypedata;structNode*next;structNode*prior;}DLNode;priordatanext75（2）双向链表的操作实现(1)前插设p已指向第i元素，请在第i元素前插入元素xx

sai-1

ai

p指针域的变化：①ai-1的后继从ai(指针是p)变为x（指针是s):s->next=p;

p->prior->next=s;

②ai的前驱从ai-1(指针是p->prior)变为x(指针是s);

s->prior=p->prior;p->prior=s;76

p指针域的变化：

后继方向：ai-1的后继由ai(指针p)变为ai+1(指针p->next

);p->prior->next

=

p->next;

前驱方向：ai+1的前驱由ai(指针p)变为ai-1(指针p->prior);p->next->prior

=p->prior;(2)双向链表的删除操作设p指向第i个元素，删除第i个元素ai-1

ai

ai+1

772.4静态链表静态链表：在数组中增加一个（或两个）指针域，这些指针域用来存放下一个（或上一个）数据元素在数组中的下标，从而构成用数组构造的单链表（或双链表）。静态链表中的指针又称仿真指针。78例：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur说明1：假设S为SLinkList型变量，则S[MAXSIZE]

为一个静态链表；S[0].next则表示第1个结点在数组中的位置。说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；S[i].next

表示第k+1个结点(即k的直接后继)的位置。i头结点79例2-6设头指针为head，并设带头结点单链表中的数据元素递增有序，编写算法将数据元素x插入到带头结点单链表的适当位置上，要求插入后保持单链表数据元素的递增有序。算法思想：从链表的第一个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。2.5算法设计举例80voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;

curr=head->next;pre=head;

while(curr!=NULL&&curr->data<=x){pre=curr; curr=curr->next;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;

q->next=pre->next;pre->next=q;}81算法设计说明：（1）在循环定位插入位置时，循环条件必须首先是curr!=NULL，然后是curr->data<=x。如果次序颠倒，则当curr为空（即等于链表结束标记NULL）时,将因为curr->data不存在而出错；次序不颠倒时，当curr等于NULL时将退出循环，不会进行后边条件curr->data<=x的比较。（2）当比较到最后一个结点仍有data小于等于x时，此时有pre指向最后一个结点，curr等于NULL，则上述算法把新结点插入