第02章数据结构线性表1

回顾数据:是客观事物的符号表示，在计算机科学中指能输入计算机并能由计算机程序进行处理的符号总称。

数据元素:是数据的基本单位，在程序中通常是作为一个整体来进行考虑和处理的。

数据对象:是性质相同的数据元素的集合，是数据的一个子集。

数据结构:是相互之间存在的一种或多种特定关系的数据元素的集合。

数据和数据结构概念1第2章线性表第3章栈和队列第4章串第5章数组和广义表

线性结构

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）线性结构的定义：（逻辑、存储和运算）线性结构的特点：①只有一个首结点和尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构表达式：（a1,a2,……,an）线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是线性表简言之，线性结构反映结点间的逻辑关系是

一对一的第2章线性表1.了解线性结构的特点2.掌握顺序表的定义、查找、插入和删除3.掌握链表的定义、查找、插入和删除4.能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合

教学目标线性表重点：顺序表和链表上各种基本算法的实现及相关的时间性能分析难点：线性表应用的算法设计2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现教学内容2.1线性表的定义线性表(LinearList)是具有相同特性的数据元素的一个有限序列a1a2an-1an…该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1≤i≤n)。线性表的一般表示为:

其中a1为第一个元素,又称做表头元素,a2为第二个元素,an为最后一个元素,又称做表尾元素。例如,在线性表

(1,4,3,2,8,10)中,1为表头元素,10为表尾元素。(a1,a2,…ai,ai+1,…,an)2.1线性表的类型定义定义n(≥0)个数据元素的有限序列,记作(a1,…ai-1,ai,ai+1,…,an)其中，ai

是表中数据元素，n

是表长度(n=0时称为空表)逻辑特征n>0时有且仅有一个“第一个”数据元素有且仅有一个“最后一个”数据元素除第一个数据元素外，其它元素有且仅有一个直接前驱除最后一个数据元素外，其它元素有且仅有一个直接后继（a1,a2,…ai-1，ai,ai＋1

，…,an）线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点2.1线性表的类型定义例1分析26个英文字母组成的英文表

（A,B,C,D,……,Z）学号姓名性别年龄班级041810205于春梅女1804级计算机1班041810260何仕鹏男2004级计算机2班041810284王爽女1904级计算机3班041810360王亚武男1804级计算机4班：：：

：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性线性表的基本操作1.初始化线性表LInitList(L)2.销毁线性表LDestoryList(L)3.清空线性表LClearList(L)4.求线性表L的长度ListLength(L)5.判断线性表L是否为空IsEmpty(L)6.获取线性表L中的某个数据元素内容GetElem(L,i,e)7.检索值为e的数据元素LocateELem(L,e)

8.返回线性表L中e的直接前驱元素PriorElem(L,e)9.返回线性表L中e的直接后继元素NextElem(L,e)

10.在线性表L中插入一个数据元素ListInsert(L,i,e)11.删除线性表L中第i个数据元素ListDelete(L,i,e)(1)初始化线性表InitList(&L):构造一个空的线性表L。

(2)销毁线性表DestroyList(&L):释放线性表L占用的内存空间。线性表的运算

(3)判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。

(4)求线性表的长度ListLength(L):返回L中元素个数。

(5)输出线性表DispList(L):当线性表L不为空时,顺序显示L中各结点的值域。

(6)求线性表L中指定位置的某个数据元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))个元素的值。

(7)定位查找LocateElem(L,e):返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。

(8)插入数据元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。

(9)删除数据元素ListDelete(&L,i,&e):删除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。

例2.1假设有两个集合A和B分别用两个线性表LA和LB表示,即线性表中的数据元素即为集合中的成员。

编写一个算法求一个新的集合C=A∪B,即将两个集合的并集放在线性表LC中。

解:本算法思想是:先初始化线性表LC,将LA的所有元素复制到LC中,然后扫描线性表LB,若LB的当前元素不在线性表LA中,则将其插入到LC中。算法如下:voidunionList(ListLA,ListLB,List&LC){intlena,lenc,i;ElemTypee;InitList(LC);/*初始化线性表LC*/for(i=1;i<=ListLength(LA);i++) /*将LA的所有元素插入到LC中*/{ GetElem(LA,i,e); ListInsert(LC,i,e);}lenA=ListLength(LA);/*求线性表的长度*/lenB=ListLength(LB);

for(i=1;i<=lenB;i++) { GetElem(LB,i,e);

/*取LB中第i个数据元素赋给e*/ if(!LocateElem(LA,e)) ListInsert(LC,++lenC,e); /*LA中不存在和e相同者,则插入到LC中*/ }}

由于LocateElem(LA,e)运算的时间复杂度为O(ListLength(LA)),所以本算法的时间复杂度为:O(ListLength(LA)*ListLength(LB))2.2线性表的顺序存储2.2.1线性表的顺序存储—顺序表2.2.2顺序表基本运算的实现2.2线性表的顺序表示和实现线性表的顺序表示又称为顺序存储结构或顺序映像。简言之，逻辑上相邻，物理上也相邻顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。随机存取线性表中第一个元素的存储位置就是指定的存储位置第i+1个元素(1≤i≤n-1)的存储位置紧接在第i个元素的存储位置的后面假定线性表的元素类型为ElemType则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType)整个线性表所占用存储空间的大小为:

n*sizeof(ElemType)其中,n表示线性表的长度。顺序表示意图元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储顺序表的存储LOC(ai+1)=LOC(ai)+lLOC(a

i)=LOC(a1)+(i-1)*l

a1

a2

…a

i………an12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle线性表逻辑结构顺序表存储结构顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。688970674078

逻辑序号123456C数组下标012345陈述问题时用在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度由于数组的下标从0开始，线性表的第i个元素ai存放顺序表的第i-1位置上。为了清楚，将ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。2.2线性表的顺序存储结构---顺序表顺序表的特点容量固定1105106107108109110201202203204205206207208209210301302303304305306307308309310101102103104101102103104A班宿舍105106107108109B班宿舍安排A班40人住入宿舍安排B班50人住入宿舍2.2线性表的顺序存储结构---顺序表由于线性表中每个元素所占用的空间是相同的，只需按照公式计算便可以快速地访问指定元素。假设顺序表中第一个元素的位置是Loc，每个数据元素所占用的存储空间为n：顺序表的特点访问速度快2a1a2．．．ai．．．线性存储空间下标位置01i-1存储地址LocLoc+nLoc+(i–1)*n建立顺序表

其方法是将给定的含有n个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的成员。算法如下：

CreateList(SqList&L,ElemTypea[],intn)

/*建立顺序表*/

{

inti;for(i=0;i<n;i++) L.data[i]=a[i];

L.length=n;

}典型操作的算法实现1.初始化线性表L（参数用引用）intInitList(SqList&L){L.length=0;//空表长度置0L.listsize=LIST_INIT_SIZE;returnOK;//成功返回OK}1.初始化线性表L（参数用指针）intInitList(SqList*L){L.length=0;//空表长度置0 L.listsize=LIST_INIT_SIZE;returnOK;//成功返回OK}典型操作的算法实现2.销毁线性表LvoidDestroyList(SqList&L){if(L.elem)free(L.elem);//释放存储空间}3.清空线性表LvoidClearList(SqList&L){L.length=0;//将线性表的长度置为0}4.

求线性表L的长度intGetLength(SqList&L){return(L.length);}5.判断线性表L是否为空intIsEmpty(SqList&L){if(L.length==0)returnTRUE;/*或return(L.length==0);*/elsereturnFALSE;}6.输出线性表DispList(L)

该运算当线性表L不为空时,顺序显示L中各元素的值。

voidDispList(SqList&L){ inti; if(IsEmpty(L))return; for(i=0;i<L.length;i++)

输出L.data[i]; printf("\n");}

7.获取线性表L中的某个数据元素的内容//根据指定位置，获取相应位置数据元素的内容intGetElem(SqList&L,inti,ElemType&e){if(i<1||i>L.length)returnERROR;//判断i值是否合理，若不合理，返回ERROR

e=L.elem[i-1];

//第i-1的单元存储着第i个数据

returnOK;}查找（根据指定数据查找，返回数据所在的位置）

顺序查找图示253457164809

012345data查找

16i253457164809

i253457164809

i253457164809

i查找成功顺序查找第1个值域与e相等的元素的位序。若这样的元素不存在,则返回0。2534571648

01234data查找50i2534571648

i2534571648

i2534571648

i2534571648

i查找失败查找算法时间效率分析？？？8.在线性表L中查找值为e的数据元素intLocateELem(SqList&L,ElemType&e){for(i=0;i<L.length;i++)if(L.elem[i]==e)returni+1;return0;}查找成功的平均比较次数(pi为各项的查找概率)

若查找概率相等，则

查找不成功数据比较n

次查找算法时间效率分析

2512478936141234567892512479989361499插入251247893614251247893614251247893614插第4个结点之前，移动6－4+1

次插在第i个结点之前，移动n-i+1

次插入（插在第i个结点之前）

实现步骤：事先应判断:插入位置i是否合法?表是否已满?应当为：1≤i≤n+1或i=[1,n+1]将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。9.在线性表L中第i个数据元素之前插入数据元素e

intListInsert(SqList&L,inti,ElemType&e){if(i<1||i>L.length+1)returnERROR;//检查i值是否合理

for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//将第i个之后的依次向后移动

L.elem[i-1]=e;//将新元素放入第i个位置

L.length++;returnOK;}若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？算法时间主要耗费在移动元素的操作上插入算法时间效率分析

…251247893614123456789251247361425124736142512473614删除删除（删除第i个结点）

删除第4个结点，移动6－4

次删除第i个结点，移动n-i

次实现步骤：事先需要判断，删除位置i是否合法?应当有1≤i≤n或i=[1,n]将第i+1至第n位的元素向前移动一个位置；表长减1。10.将线性表L中第i个数据元素删除intListDelete(SqList&L,inti,ElemType&e){if(IsEmpty(L))returnERROR;//检测是否为空

if(i<1||i>L.length)returnERROR;//检查i值是否合理

e=L.elem[i-1];//将欲删除的元素保留在e中

for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j];//依次将第i+1后的元素向前移

L.length--;

returnOK;}若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中n-1个元素全部前移（特别慢）；若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？算法时间主要耗费在移动元素的操作上删除算法时间效率分析

显然，顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）查找、插入、删除算法的平均时间复杂度为O(n)（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致顺序表（顺序存储结构）的特点这种存取元素的方法被称为随机存取法（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等

设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构即顺序表)的适当位置上,并保持线性表的有序性。

解:先通过比较在顺序表L中找到存放x的位置i,然后将x插入到L.data[i]中,最后将顺序表的长度增1。练习voidInsert(SqList&L,ElemTypex){inti=0,j;

while(i<L.length&&L.data[i]<x) i++;

for(j=L.length-1;j>=i;j--) L.data[j+1]=L.data[j];L.data[i]=x;L.length++;}查找插入位置元素后移一个位置a0…ai-1ai…an-1……逻辑位序

1

ii+1nMaxSize

设计一个算法,将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。

求解思路:将两个顺序表进行二路归并。

例题归并到顺序表r中←k记录r中元素个数

1(i=0)2(j=0)

将1(i=1)插入r(k=1)3(i=1)2(j=0)将2(j=1)插入r(k=2)3(i=1)4(j=1)将3(i=2)插入r(k=3)5(i=2)4(j=1)将4(j=2)插入r(k=4)5(i=2)10(j=2)将5(j=3)插入r(k=5)

将q中余下元素插入r中。

顺序表p：1

3

5i顺序表q：2

4

10

20j顺序表r：1

kSqList*merge(SqList*p,SqList*q){SqList*r;inti=0,j=0,k=0;while(i<p.length&&j<q.length){ if(p.data[i]<q.data[j]) {r.data[k]=p.data[i]; i++;k++; } else {r.data[k]=q.data[j]; j++;k++; }}

while(i<p.length) {r.data[k]=p.data[i]; i++;k++; }while(j<q.length){r.data[k]=q.data[j]; j++;k++; } r.length=k;/*或p.length+q.length*/ return(r);}线性表的应用－－线性表合并（算法2.1）问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合

A=ABLa=(7,5,3,11)Lb=(2,6,3)La=(7,5,3,11,2,6).依次取出Lb中的每个元素，执行以下操作：

在La中查找该元素如果找不到，则将其插入La的最后线性表合并－－操作步骤voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(&La,++La_len,e);

}}线性表合并（算法2.1）问题描述：

已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列.La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,

2,

4,6,7,8,8,10,11).有序表合并（算法2.2）(1)Lc为空表(2)

依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变空为止(3)继续将La或Lb其中一个表的剩余结点插入在Lc表的最后有序表合并－－操作步骤voidMergeList(ListLa,ListLb,List&Lc){

InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){

GetElem(La,i,ai);

GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}

while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}有序表合并（算法2.2）(1)创建一个空表Lc(2)

依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变空为止(3)继续将La或Lb其中一个表的剩余结点插入在Lc表的最后有序的顺序表合并－－操作步骤voidMergeList(SqListLa,SqListLb,SqList&Lc)ElemType*pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;/*不用InitList()创建空表Lc*/pc=(*Lc).elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last)/*表La和表Lb均非空*/{if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)/*表La非空且表Lb空*/*pc++=*pa++;/*插入La的剩余元素*/while(pb<=pb_last)/*表Lb非空且表La空*/*pc++=*pb++;/*插入Lb的剩余元素*/}有序的顺序表合并（算法2.7)T(n)=S(n)=O(n)#defineN10intmax(inta[]);voidmain(){ inta[10]; inti,m; for(i=0;i<N;i++)

输入a[i]; m=max(a);

输出"themaxnumberis:"m;}intmax(intb[]){inti,n;n=b[0];for(i=1;i<N;i++) if(n<b[i])n=b[i];returnn;}练习：求10个整数的最大数练习：将数组中n个整数按相反的顺序存放#include<iostream.h>#defineN10voidsub(intb[]){ inti,j,temp,m; m=N/2; for(i=0;i<m;i++){j=N-1-i;temp=b[i]; b[i]=b[j];b[j]=temp; } return;}voidmain(){ inta[10],i; for(i=0;i<N;i++) cin>>a[i]; sub(a); for(i=0;i<N;i++) cout<<a[i];}顺序表的优缺点缺点：在插入、删除某一元素时，需要移动大量元素浪费存储空间属于静态存储形式，数据元素的个数不能自由扩充链表为克服这一缺点优点：存储密度大（结点本身所占存储量/结点结构所占存储量）可以随机存取表中任一元素单链表静态链表循环链表双向链表其他

2.3线性表的链式表示和实现2.3线性表的链式表示和实现链式存储结构结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻线性表的链式表示又称为非顺序映像或链式映像。特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点

数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点2.3线性表的链式存储结构在链式存储中,每个存储结点不仅包含有所存元素本身的信息(称之为数据域)而且包含有元素之间逻辑关系的信息,即前驱结点包含有后继结点的地址信息,这称为指针域这样可以通过前驱结点的指针域方便地找到后继结点的位置,提高数据查找速度。2.3.1线性表的链式存储—链表一般地,每个结点有一个或多个这样的指针域。若一个结点中的某个指针域不需要任何结点,则仅它的值为空,用常量NULL表示。链表定义结点-数据元素的存储映像，包括数据域和指针域（其信息称为指针或链）头指针-链表存取的开始；空(NULL)-最后一个结点的指针

2.3.1线性链表数据域指针域LI43QIAN13SUN1WANGNULLWU37ZHAO7ZHENG19ZHOU25存储地址1713192531374331头指针ZHAOQIANSUNLIZHOUWUZHENGWANG^H线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针链表定义

typedefstructLNode{

ElemTypedata;

//数据域

structLNode*next;

//后向指针域

}LNode,*LinkList;2.3.1线性链表例画出26个英文字母表的链式存储结构链式存储结构：逻辑结构：（a,b,…,y,z）aheadb/\z……各结点由两个域组成：数据域：存储元素数值数据指针域：存储直接后继结点的存储位置指针数据与链式存储有关的术语1、结点：数据元素的存储映像。由数据域和指针域两部分组成2、链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构a1heada2an……head循环链表示意图：3、单链表、双链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表有两个指针域的链表，称为双链表首尾相接的链表称为循环链表4、头指针、头结点和首元结点

头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点的指针首元结点是指链表中存储第一个数据元素a1的结点头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息例：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是31上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①

无头结点②有头结点讨论1.如何表示空表？有头结点时，当头结点的指针域为空时表示空表非空表 空表0ana0headhead^表头结点第一个结点讨论2.在链表中设置头结点有什么好处？⒈便于首元结点的处理首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;⒉便于空表和非空表的统一处理无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

讨论3.头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。头结点的数据域H（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻链表（链式存储结构）的特点（2）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等这种存取元素的方法被称为顺序存取法优点数据元素的个数可以自由扩充插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高链表的优缺点缺点存储密度小存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）链表的优缺点练习1.链表的每个结点中都恰好包含一个指针。2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。3.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。4.线性表若采用链式存储时，结点之间和结点内部的存储空间都是可以不连续的。5.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型×

×

×

×

×

由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素,即数据元素之间是一对一的逻辑关系,所以当进行链式存储时,一种最简单也最常用的方法是:在每个结点中除包含有数据域外,只设置一个指针域,用以指向其后继结点,这样构成的链接表称为线性单向链接表,简称单链表；如何实现？通过指针来实现单链表的存储映像free(a)可利用存储空间a0a2a1a3freefirst(b)经过一段运行后的单链表结构带头结点单链表示意图

在线性表的链式存储中,为了便于插入和删除算法的实现,每个链表带有一个头结点,并通过头结点的指针惟一标识该链表。

在单链表中,由于每个结点只包含有一个指向后继结点的指针所以当访问过一个结点后,只能接着访问它的后继结点,而无法访问它的前驱结点

单链表非空表空表单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名若头指针名是L，则把链表称为表L

typedefstructLnode{ElemTypedata;//数据域

structLNode*next;//指针域}LNode,*LinkList;

//*LinkList为Lnode类型的指针单链表的存储结构定义初始化单链表StatusInitList_L(LinkList&L){

//构造一个空的线性表Lif(!L)returnOVERFLOW;L.next=NULL;returnOK;}销毁单链表StatusDestroyList_L(LinkList&L){LinkListp;while(L){p=L;L=L.next;free(p);}returnOK;}单链表基本运算的实现

1.建立单链表先考虑如何建立单链表。假设我们通过一个含有n个数据的数组来建立单链表。建立单链表的常用方法有如下两种:

(1)头插法建表该方法从一个空表开始,读取字符数组a中的字符,生成新结点。将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。采用头插法建表的算法如下:从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端单链表的建立（头插法）abcdi=0i=1i=2i=3∧head采用头插法建立单链表的过程heada∧headba∧headcba∧headdcba∧第1步:建头结点第2步:i＝0,新建a结点,插入到头结点之后第3步:i＝1,新建d结点,插入到头结点之后第4步:i＝2,新建c结点,插入到头结点之后第5步:i＝3,新建b结点,插入到头结点之后单链表的建立p.data=anp.data=an-1L.next=pp.next=L.nextvoidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L.next=NULL;for(i=0;i<n;i++){s.data=a[i];s.next=L.next; /*将s插在原开始结点之前,头结点之后*/L.next=s;}}

(2)尾插法建表头插法建立链表虽然算法简单,但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致,可采用尾插法建立。该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下:bcdai=0i=1i=2i=3head头结点adcb∧b采用尾插法建立单链表的过程voidCreateListR(LinkList*&L,ElemType