数据结构之线性表

第二章线性表线性结构

是

一个数据元素的有序（次序）集线性表的基本特征存在惟一的一个被称做“第一个”的数据元素；存在惟一的一个被称做“最后一个”的数据元素；除第一个之外，集合中的每个数据元素均只有一个前驱；除最后一个之外，集合中的每个数据元素均只有一个后继。2.1线性表的类型定义2.2线性表类型的实现

——顺序映像2.3线性表类型的实现

——链式映像2.4一元多项式的表示抽象数据类型线性表的定义ADTList{

数据对象：

D={ai|ai

ElemSeti=1,2,..,nn≥0}{称n为线性表的表长，称n=0时的线性表为空表}

数据关系：

R1={<ai,ai+1>|ai,ai+1ElemSet,i=1,2,..,n-1≥0}{称i为ai在线性表中的位序}(a1,a2,...,ai-1,ai,ai+1,…,an)基本操作：

{结构初始化}

InitList(&L)

操作结果：构造一个空的线性表L{销毁结构}

DetroyList(&L)

初始条件：线性表L已经存在操作结果：销毁线性表L{引用型操作}ListEmpty(L)ListLength(L)

PriorElem(L,cur_e,&pre_e)

NextElem(L,cur_e,&next_e)GetElem(L,i,&e)

LocateElem(L,e,compare())ListTraverse(L,visit())

ListEmpty(L)

操作结果：若线性表L为空表，则返回True，否则返回FalseListLength(L)

操作结果：返回线性表L中元素的个数

PriorElem(L,cur_e,&pre_e)

操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败

NextElem(L,cur_e,&next_e)

操作结果：若cur_e是L中的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败

GetElem(L,i,&e)

操作结果：用e返回L中第i个元素的值，其中1<=i<=ListLength(L)

LocateElem(L,e,compare())

操作结果：返回第一个与e满足compare()关系的数据元素的位序。若不存在这样的元素，则返回0ListTraverse(L,visit())

操作结果：遍历线性表L，对每个元素执行函数visit(){加工型操操作}ClearList(&L)PutElem(L,i,&e)ListInsert(&L,i,e)ListDelete(&l,i,&e)ClearList(&L)初始条件件：线性性表L已经存在在操作结果果：将L重至为空空表PutElem(L,i,&e)初始条件件：线性性表L已存在，，其中1<=i<=LengthList(L)操作结果果：L中的第i个元素赋赋值为e的值ListInsert(&L,i,e)初始条件件：线性性表L已存在，，其中1<=i<=LengthList(L)+1操作结果果：在L的第i个元素之之前插入入一个新新的元素素e，L的长度增增加1ListDelete(&l,i,&e)初始条件件：线性性表L已存在并并且非空空，其中中1<=i<=LengthList(L)操作结果果：将L的第i个元素删删除，并并将之，，L的长度增增加1利用上述述定义的的线性表可以完成成更复杂杂的操作作例2-1假设有两两个集合合A和B，分别用用两个线线性表LA和LB来表示（（即：线线性表中中的数据据元素为为集合中中的成员员）现求一个个新的集集合A=A∪∪B上述问题题可以演演绎为，，要求对线线性表作作如下操操作：扩大线性性表LA，将存在在于线性性表LB中而不存存在于线线性表LA中的数据据元素插插入到线线性表LA中EBFHVDALAASFGLBVSGijjjjjjiiii从线性表表LB中依次取取得每个个数据元元素：GetElem(LB,i)→e依值在线线性表LA中进行查查访：LocateElem(LA,e,Equal())若不存在在，则插插入之，，ListInsert(LA,n+1,e)VoidUnion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表表的长度度for(i=0;i<Lb_len;i++){GetElem(Lb,i,e);//取Lb中的第i个元素赋赋给eif(!LocateElem(La,e,equal()))ListInsert(La,La_len++,e)//若La中不存在在和e相同的值值，则插插入之}}例2-2已知一个个非纯集集合B，试构造造一个纯纯集合A，使A中只包含含B中所有值值各不相相同的数数据元素素EBEHDALBBDBELAEBHDAVoidPurge(List&La,ListLb){InitList(La);//设置空的的线性表表LaLa_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表表的长度度for(i=0;i<Lb_len;i++){GetElem(Lb,i,e);//取Lb中的第i个元素赋赋给eif(!LocateElem(La,e,equal()))ListInsert(La,La_len++,e)//若La中不存在在和e相同的值值，则插插入之}}EBEHDALBBDBELAEBHDAVoidPurge(List&La,ListLb){InitList(La);//设置空的的线性表表LaLa_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表表的长度度for(i=0;i<Lb_len;i++){GetElem(Lb,i,e);//取Lb中的第i个元素赋赋给eif(!ListEmpty(La)||!equal(en,e)){ListInsert(La,La_len++,e);//若La中不存在在和e相同的值值，则插插入之en=e;}}}例2-3归并两个个“其数数据元素素按值非非递减有有序排列列的”线线性表LA和LB，求求得线性性表LC也具有有同样特特性。不会BLEBLBDLGCGIFALADHLCABBCDDEFGGHILL设La=(a1,….,ai,….,an)Lb=(b1,….,bj,….,bn)Lc=(c1,….,ck,….,cm+n)则ck中的k为1，2，……m+n1、分别从La和Lb中取得当前元元素ai和bj2、若ai≤bj，则将ai插入Lc中去，否则将将bj插入到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()While(i<=la_len){GetElem(La,i++,ai);ListInsert(Lc,k++,ai);}While(j<=lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,k++,aj);}}习题：1、有线性表LA和LB均为有序线性性表，试构造造线性表LA1和LB1分别为LA和LB中除去最大共共同前缀后的的子表。比如：LA=(a,b,c,e,f)LB=(a,b,d,e,f)则LA1=(c,e,f)LB1=(d,e,f)注意：LA和LB有一个是空表表LA和LB相等构造线线性表表LA1和LB1InitList(LA1),InitList(LB1)分别从从LA和LB中取得得第i个数据据元素素GetElem(LA,i,ai),GetElem(LB,i,bi)比较ai和bi是否相相等，，若相相等继继续取取第i+1个数据据元素素；若若不相相等，，则已已经找找到最最大前前缀，，为前前i-1项，退退出将从第第i项开始始的LA和LB分别存存放到到LA1和LB1中即可可VoidwipePrefix(ListLA,ListLB,List&LA1,List&LB1){InitList(LA1);InitList(LB1);//初始化化LA1和LB1inti=1;La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性性表的的长度度while(i<=La_len||i<=Lb_len){GetElem(LA,i,ai);GetElem(LB,i,bi);if(ai==bi)i++;//比较ai和bi是否相相等，，若相相等继继续取取第i+1个数据据元素素,否则退退出elsebreak;}j=i;While(j<=La_len){GetElem(LA,j,aj);ListInsert(LA1,j,aj);}j=i;While(j<=Lb_len){GetElem(LB,j,bj);ListInsert(LB1,j,bj);}}2、线性性表LA和LB均为递递增有有序的的线性性表，，要求求对LA做如下下操作作，删删除在在LB中出现现的元元素。。要求：(1)、用学学到的的线性性表抽抽象数数据类类型中中提供供的操操作编编写算算法，，完成成上述述两题题功能能。(2)、分析析所写写算法法的时时间复复杂度度2.2线性表表类型型的实实现——顺序映映像用一组组地址址连续续的存存储单单元依依次存存放线线性表表中的的数据据元素素a1a2ai-1aian…………线性表表的起起始地地址称作线线性表表的基基地址址线性表表的起起始地地址称作线线性表表的基基地址址以“存存储位位置相相邻””表示示有序序对<ai-1,ai>即：LOC(ai)=LOC(ai-1)+C所有数数据元元素的的存储储位置置均取取决于于第一一个数数据元元素的的存储储位置置LOC(ai)=LOC(a1)+(i-1)×C一个数数据元元素所所占存存储量量基地址即在顺顺序存存储结结构中中，线线性表表中每每一个个数据据元素素在计计算机机存储储空间间中的的存储储地址址由该该元素素在线线性表表中的的序号号惟一一确定定。一一般来来说，，长度度为n的线线性性表表(a1，a2，…，an)在计计算算机机中中的的结结构构如如下下：：顺序序存存储储结结构构的的特特点点（1）利利用用数数据据元元素素的的存存储储位位置置表表示示线线性性表表中中相相邻邻数数据据元元素素之之间间的的前前后后关关系系，，即即线线性性表表的的逻逻辑辑结结构构与与存存储储结结构构（（物物理理结结构构））一一致致；；（2）在在访访问问线线性性表表时时，，可可以以利利用用上上述述给给出出的的数数学学公公式式，，快快速速地地计计算算出出任任何何一一个个数数据据元元素素的的存存储储地地址址。。因因此此，，我我们们可可以以粗粗略略地地认认为为，，访访问问每每个个数数据据元元素素所所花花费费的的时时间间相相等等。。这这种种存存取取元元素素的的方方法法被被称称为为随机机存存取取法法，使使用用这这种种存存取取方方法法的的存存储储结结构构被被称称为为随机机存存储储结结构构。在具具体体实实现现时时，，一一般般用用高高级级语语言言中中的的数组组来对对应应连连续续的的存存储储空空间间。。设设最最多多可可存存储储MaxLen个元元素素，，在在C语言言中中可可用用数数组组data[MaxLen]来存存储储数数据据元元素素，，为为保保存存线线性性表表的的长长度度需需定定义义一一个个整整型型变变量量length。线线性性表表的的第第l，2，…，n个元元素素分分别别存存放放在在此此数数组组下下标标为为0，1，…，length-1数组组元元素素中中，，如如下下图图所所示示顺序序映映像像的的C语言言描描述述#defineMaxLen80//线性性表表存存储储空空间间的的初初始始分分配配量量typedefintElemType//在实实际际应应用用中中，，将将ElemType定义义成成实实际际类类型型typedefstruct{ElemTypedata[MaxLen];//定义存储储表中元元素的数数组intlength;//当前长度度}SqList;sqListL;//定义表结结构的变变量顺序映像像的C#语言描述述publicclassSqList{privateintmaxSize;//顺序表表的容量量privateint[]data;//数组，，用于存存储数据据元素privateintlast;//指示顺顺序表最最后一个个元素的的位置publicintLast//最最后一个个数据元元素位置置属性{get{returnlast;}}publicintMaxSize//最最大容量量{get{returnmaxSize;}set{maxSize=value;}}publicSqList(intsize)//构造造器{data=newint[size];maxSize=size;last=-1;}}线性表在在顺序存存储结构构下的运运算实现现1．初始始化顺序序表Initlist(L)的实现现顺序表的的初始化化即构造造一个空空表，顺顺序表L是否为为空取决决于其元元素个数数是否为为0，因因此，要要将表L中的表表长度置置为0publicSqList(intsize)//构造造器{data=newint[size];maxSize=size;last=-1;}该算法的的时间复复杂度为为O(1)2．求线线性表长长度Getlength(L)的实实现求线性表表的长度度算法如如下：publicintGetLength(){returnlast+1;}该算法的的时间复复杂度为为O(1)3．判断断线性表表是否为为空IsEmpty()的实实现判断线性性表是否否为空算算法如下下：publicboolIsEmpty(){if(last==-1)returntrue;elsereturnfalse;}该算法的的时间复复杂度为为O(1)4．按序序号取元元素GetElem(L,i)的实实现按前面的的约定，，序号为为i的元元素存储储在数组组下标为为i-1的数组组元素中中，所以以可直接接从该数数组元素素中取得得值。i的有效效值应大大于等于于1和小小于等于于线性表表的实际际长度。。publicintGetElem(inti){if(IsEmpty()||(i<1)||(i>last+1)){Console.WriteLine("ListisEmptyorPositioniserror!");return0;}elsereturndata[i-1];}5．查找运运算LocateElem(L,e)的实现publicintLocate(intitem){if(IsEmpty()){Console.WriteLine("ListisEmpty!");return-1;}inti=0;for(i=0;i<=last;i++)if(item.Equals(i))break;if(i>last)return-1;returni+1;}要确定值值为e的元素在在L表中的位位置，需需要依次次比较各各元素。。当查询询到第一一个满足足条件的的数据元元素时，，返回其其序号，，否则返返回-1，表示查查找失败败。算法复杂杂度：在查找过过程中，，数据元元素比较较次数最最少为1，最多为为n元素比较较次数的的平均值值为(n+1)/2时间复杂杂度为O(n)6．顺序表表的插入入算法InsertElem(L,i,x)的实现顺序表的的插入是是指在表表的第i个位置上上插入一一个值为为x的新元素素，插入入后使原原表长为为n的表：(a0，a1，…，ai-2，ai-1，ai，…，an-1)，成为表表长为n+1的表：(a0，a1，…，ai-2，x，ai-1，ai，…，an),i的取值范范围为1≤i≤n+1。下图表表示一个个顺序表表中的数数组在进进行插入入运算前前后，数数据元素素在数组组中的下下标变化化。

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

ai-1

i+1

ai

i+2

ai+1┇┇

n

an-1

插入x插入前插入后

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

x

i+1

ai-1

i+2

ai┇┇

n+1

an-1

publicvoidInsert(intitem,inti){if(IsFull()){Console.WriteLine("TheListisfull!");return;}if(i<1||i>last+2){Console.WriteLine("Thepositioniserror!");return;}if(i==last+2)//若是是向最后后一个元元素之后后插入,直接插插入即可可data[last+1]=item;else//若若在中间间插入,则需要要将后面面的所有有元素一一一后撤撤{for(intj=last;j>=i-1;--j)data[j+1]=data[j];data[i-1]=item;}last++;}该算法的的时间主主要花费费在移动动数据元元素上，，移动个个数取决决于插入入位置i和表的的长度度n。所以以可以以用数数据元元素的的移动动操作作来估估计算算法的的时间间复杂杂度。。在第第i个位置置上插插入x，共需需要移移动n-i+1个元素素，i的取值值范围围为：：1≤i≤n+1，即有有n+1个位置置可以以插入入。当i=n+1时，不不需要要移动动结点点；当i=1时需要要移动动n个结点点。。由此可可以看看出，，算法法在最最好的的情况况下时时间复复杂性性为O(1)，最坏坏的时时间复复杂性性是O(n)。由于插插入的的位置置是随随机的的，因因此，，需要要分析析执行行该算算法移移动数数据元元素的的平均均值。。设在在第i个位置置上作作插入入的概概率为为Pi，则平平均移移动数数据元元素的的次数数：假设表表中任任何位位置插插入概概率是是均等等的,即Pi=1/(n+1),Em=n/2由此可可以看看出，，在线线性表表上做做插入入操作作需要要移动动表中中一半半的数数据元元素，，当n较大时时，算算法的的效率率是比比较低低的，，所以以在线线性表表上进进行插插入操操作的的时间间复杂杂度为为Ｏ(n)。7．顺序序表的的删除除运算算ListDelete(L,i)的实现现顺序表表的删删除运运算是是指将将表中中第i个元素素从线线性表表中去去掉，，原表表长为为n的线性性表(a1，a2，…，ai-1，ai，ai+1，…，an)。进行行删除除以后后的线线性表表表长长变为为n-1的表(a1，a2，…，ai-1，ai+1，…，an)，i的取值值范围围为：：1≤i≤n。删除删除前前删除后后

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

ai-1

i+1

ai

i+2

ai+1┇┇

n

an-1

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

ai

i+1

ai+1

i+2

ai+2┇┇

n-1

an-1

在线性性表上上完成成上述述运算算通过过以下下两个个操作作来实实现：：(1)线性表表中第第i+1个至第第n个元素素（共共n-i个元素素）依依次向向前移移动一一个位位置。。将所所删除除的元元素ai-1覆盖掉掉，从从而保保证逻逻辑上上相邻邻的元元素物物理位位置也也相邻邻。(2)修改线线性表表长度度，使使其减减1。publicintDelete(inti){inttemp=newint();if(IsEmpty()){Console.WriteLine("TheListisempty!");returntemp;}if(i<1||i>last+1){Console.WriteLine("Positioniserror!");returntemp;}if(i==last+1)//如如果是最后后一个元素素，则直接接删除即可可temp=data[last];else//若不是是最后一个个元素，则则删除后须须将后面元元素一一前前移{temp=data[i-1];for(intj=i-1;j<last;++j)data[j]=data[j+1];}last--;returntemp;}删除算法的的时间性能能分析：与插入运算算相同，删删除运算的的时间也主主要消耗在在移动表中中数据元素素上，删除除第i个元素时，，其后面的的元素ai+1～an都要向前移移动一个位位置，共移移动了n-i个元素，所所以在等概概率的情况况下，在线线性表中删删除数据元元素所需移移动数据元元素的期望望值，即平平均移动数数据元素的的次数为：：由此可以看看出，在线线性表上删删除数据元元素时大约约需要移动动表中一半半的元素，，显然该算算法的时间间复杂度为为Ｏ(n)。通常情况下下，我们认认为在线性性表中任何何位置删除除元素是等等概率的，，即pi=1/n，则：【例2-1】利用线线性表的基基本运算，，编写在线线性表A中中删除线性性表B中出出现的元素素的算法。。【解】本本题的算法法思路是：：依次检查查线性表B中的每个个元素，看看它是否在在线性表A中。若在在线性表A中，则将将其从A中中删除。本题的算法法如下：staticpublicvoidDelete(SqListlistA,SqListlistB){for(inti=1;i<=listB.GetLength();i++){intx=listB.GetElem(i);//依次查查找ListB中的的值，存入入x中intp=listA.Locate(x);//判断x是否在ListA中，若不不在返回-1，若在在返回位置置if(p!=-1)listA.Delete(p);}}线性表的顺顺序存储结结构中任意意数据元素素的存储地地址可由公公式直接导导出，因此此顺序存储储结构的线线性表是可可以随机存存取其中的的任意元素素。但是，顺序序存储结构构也有一些些不方便之之处，主要要表现在：：（1）数据元素素最大个数数需预先确确定，使得得高级程序序设计语言言编译系统统需预先分分配相应的的存储空间间；（2）插入与删删除运算的的效率很低低。为了保保持线性表表中的数据据元素顺序序，在插入入操作和删删除操作时时需移动大大量数据。。对于插入入和删除操操作频繁的的线性表、、将导致系系统的运行行速度难以以提高。（3）存储空间间不便于扩扩充。当一一个线性表表分配顺序序存储空间间后，若线线性表的存存储空间已已满，但还还需要插入入新的元素素，则会发发生“上溢溢”错误。。2.2线性表类型型的实现——链式映像线性表的顺顺序表示的的特点是用用物理位置置上的邻接接关系来表表示结点间间的逻辑关关系，故可可以随机存存取表中的的任一结点点；但在插插入和删除除操作时需需移动大量量的结点。。为避免大量量结点的移移动，介绍绍线性表的的另一种存存储方式:链式存储结结构，简称链表(LinkedList)。线性表的链链式存储结结构就是用用一组任意意的存储单单元（可以以是不连续续的）存储储线性表的的数据元素素。对线性性表中的每每一个数据据元素，都都需用两部部分来存储储：一部分分用于存放放数据元素素值，称为为数据域；另一部分分用于存放放直接前驱驱或直接后后继结点的的地址（指指针），称称为指针域，称这种存存储单元为为结点。链式存储方方式可用于于表示线性性结构，也也可用于表表示非线性性结构。链式式存存储储结结构构是是利利用用任任意意的的存存储储单单元元来来存存放放线线性性表表中中的的元元素素，，存存储储数数据据的的单单元元在在内内存存中中可可以以连连续续，，也也可可以以零零散散分分布布。。由于于线线性性表表中中各各元元素素间间存存在在着着线线性性关关系系，，每每一一个个元元素素有有一一个个直直接接前前驱驱和和一一个个直直接接后后继继。。为为了了表表示示元元素素间间的的这这种种线线性性关关系系，，在在这这种种结结构构中中不不仅仅要要存存储储线线性性表表中中的的元元素素，，还还要要存存储储表表示示元元素素之之间间逻逻辑辑关关系系的的信信息息。。所所以以用用链链式式存存储储结结构构表表示示线线性性表表中中的的一一个个元元素素时时至至少少需需要要两两部部分分信信息息，，除除了了存存储储每每一一个个数数据据元元素素值值以以外外，，还还需需存存储储其其后后继继或或前前驱驱元元素素所所在在内内存存的的地地址址。。两两部部分分信信息息一一起起构构成成链链表表中中的的一一个个结结点点。。结结点点的的结结构构如如下下所所示示。。C#语语言言采采用用类的的嵌嵌套套数据据类类型型描描述述结结点点如如下下：：publicclassListNode{privateintdata;//数数据据域域privateListNodenext;//指指针针域域}在此此结结构构中中，，用用数数据据域域data存存储储线线性性表表中中数数据据元元素素。。指指针针域域next，，它它给给出出下下一一个个结结点点的的存存储储地地址址。。结点点的的指指针针域域将将所所有有结结点点按按线线性性表表的的逻逻辑辑次次序序链链接接成成一一个个整整体体，，形形成成一一个个链链表表。。由于于链链表表中中第第一一个个结结点点没没有有直直接接前前驱驱，，所所以以必必须须设设置置一一个头头指指针针head存储储第第一一个个结结点点的的地地址址。。最最后后一一个个结结点点没没有有直直接接后后继继，，其其指指针针域域应应为为空空指指针针，，C#语语言言用用NULL来来表表示示，，在在图图中中表表示示为为““∧”。。假设有一个线线性表为（A,B,C,D,E），存储空间间具有10个存储结点，，该线性表在在存储空间中中的存储情况况如下图所示示。头指针headABCDE47291∧(b)线性表的逻辑状态从图中可见，，每个结点的的存储地址存存放在直接前前驱的指针域域中。链表这种顺着着指针链依次次访问数据元元素的特点，，表明链表是是一种顺序存取结构构，只能顺序操操作链表中元元素。不能像像顺序表（数数组）那样可可以按下标随机存取。在链表存储结结构中，不要要求存储空间间的连续性，，数据元素之之间的逻辑关关系由指针来来确定。由于于链式存储的的灵活性，这这种存储方式式既可用于表表示线性结构构，也可以用用来表示非线线性结构。怎样才能访问问到数据元素素C？单向链表每个结点只有有一个指向后后继的指针。。也就是说访访问数据元素素只能由链表表头依次到链链表尾，而不不能做逆向访访问。称这种种链表为单向向链表或线性性链表。这是是一种最简单单的链表。单链表是由表表头唯一确定定。（a）为带头结点点的空链(b)为带头结点的的单链表C语言描述单链链表：typedefcharElemType;typedefstructLNode{ElemTypedata;//结点值structLNode*next;//存储下一个结结点的地址}LNode;typedefLNode*LinkList;LNode*p;LinkListhead;publicclassListNode{privateintdata;//数据域privateListNodenext;//指针域publicintData//数据域域属性{get{returndata;}set{data=value;}}publicListNodeNext//指针域属属性{get{returnnext;}set{next=value;}}}C#语言描述单链链表的结点：：publicListNode(intval,ListNodep){//构造一一个有数据域域和指针域的的普通节点data=val;next=p;}publicListNode(intval){//构造一一个有数据域域但没有指针针域的节点，，一般为线性性表的最后一一个元素data=val;next=null;}publicListNode(ListNodep){//构造一一个没有数据据域只有指针针域的节点，，一般用作线线性表的头节节点data=0;next=p;}publicListNode(){//构造一一个没有数据据域，没有指指针域的节点点，一般为构构造空线性表表时使用data=0;next=null;}重载概念：重载是是在一个类中中用相同的名名称但是不同同的参数类型型创建一个以以上的过程、、实例构造函函数或属性。重载（overroad）：构造函数数的重载，需需要遵守一下下的规则：方法的名称一一定要一样传递的参数类类型一定要不不一样C#语言描述单链链表：publicclassLinkList{privateListNodehead;//单链链表的头引用用//构造函数数publicLinkList()//求单链表表的长度publicintGetLength()//清空单链链表publicvoidClear()//判判断断单单链链表表是是否否为为空空publicboolIsEmpty()//将将单单链链表表中中的的第第i个个数数据据元元素素的的值值改改为为itempublicvoidPutElem(intitem,inti)//获获得得单单链链表表的的第第i个个数数据据元元素素publicintGetElem(inti)//获获得得第第i个个数数据据元元素素的的前前驱驱publicListNodePriorElem(inti)//获获得得第第i个个数数据据元元素素的的后后继继publicListNodeNextElem(inti)//查查找找运运算算，，查查找找数数值值为为item的的数数据据元元素素的的位位置置publicintLocateElem(intitem)//在在单单链链表表的的第第i个个数数据据节节点点的的位位置置前前插插入入一一个个值值为为item的的结结点点publicvoidInsert(intitem,inti)//删删除除单单链链表表的的第第i个个数数据据元元素素publicintDelete(inti)}由于于链链表表是是一一种种动动态态管管理理的的存存储储结结构构，，每每个个结结点点需需动动态态产产生生。。1．．初初始始化化链链表表Initlist(L)的的实实现现建立立一一个个空空的的带带头头结结点点的的单单链链表表。。所所谓谓空空链链表表就就是是指指表表长长为为0的的表表。。在在这这种种情情况况下下，，链链表表中中没没有有元元素素结结点点。。但但应应有有一一个个头头结结点点，，其其指指针针域域为为空空。。publicLinkList(){head=newListNode();}2．．求求线线性性表表长长度度Getlength(L)的的实实现现设计思路路：设置置一个初初值为0的计数数器变量量和一个个跟踪链链表结点点的指针针p。初初始时p指向链链表中的的头结点点，然后后顺着next域依次次指向每每个结点点，每指指向一个个结点计计数器变变量加1。当p的指针针域为Null时，结结束该过过程。publicintGetLength(){ListNodep=head;intlength=0;while(p.Next!=null){length++;p=p.Next;}returnlength;}时间复杂杂度为O(n)3．按序序号取元元素GetElem(L,i)的实实现根据前面面的讨论论，对单单链表中中的结点点只能顺顺序存取取，即访访问前一一个结点点后才能能接着访访问后一一个结点点。所以以要访问问单链表表中第i个元素素值，必必须从头头指针开开始遍历历链表，，依次访访问每个个结点，，直到访访问到第第i个结结点为止止。同顺顺序表一一样，也也需注意意存取的的位置是是否有效效。publicintGetElem(inti){if(IsEmpty()||i<1||i>GetLength()){//首首先判断断线性表表是否为为空，i的位置置是否正正确Console.WriteLine("ListisEmptyorPositioniserror!");return0;}ListNodep=head;for(intj=1;j<=i;j++)p=p.Next;returnp.Data;}时间复杂杂度为O(n)4．查找运运算LocateElem(intitem)的实现设计思路路：设置置一个跟跟踪链表表结点的的指针p，初始时时p指向链表表中的头头结点，，然后顺顺着next域依次指指向每个个结点，，每指向向一个结结点就判判断其值值是否等等于item，若是则则返回该该结点地地址。否否则继续续往后搜搜索，直直到p.Next为Null，表示链链表结束束，返回回0。publicintLocateElem(intitem){if(IsEmpty()){//首首先判断断是否为为空链表表Console.WriteLine("ListisEmpty!");return0;}ListNodep=head;intj=1;intlen=GetLength();//获获得链链表长长度for(j=1;j<=len;j++)p=p.Next;//依次次访问问每一一个结结点returnp.Data;}时间复复杂度度为O(n)5．链表表的插插入算算法ListInsert(inti,intitem)的实现现单链表表结点点的插插入是是利用用修改改结点点指针针域的的值，，使其其指向向新的的链接接位置置来完完成的的插入入操作作，而而无需需移动动任何何元素素。假定在在链表表中值值为ai的结点点之前前插入入一个个新结结点，，要完完成这这种插插入必必须首首先找找到所所插位位置的的前一一个结结点，，再进进行插插入。。假设设指针针q指向待待插位位置的的前驱驱结点点，指指针s指向新新结点点，则则完成成该操操作的的过程程如下下图所所示。。a1a2…………ai-1ai……an^head1、首先先找到到插入入位置置2、申请请新节节点s，数据据域置置为x3、修改改指针针域，，将s插入到到线性性表中中qpxspublicvoidInsert(intitem,inti){if(i<1||i>(GetLength()+1)){Console.WriteLine("Positioniserror!");return;}ListNodeq=head;ListNodeInVal=newListNode(item);ListNodes=newListNode();intj=1;for(j=1;j<i&&q.Next!=null;j++)//找到要要插入元素素的前一个个元素//当q.Next为空时，，表示在最最后一个元元素之后插插入新元素素q=q.Next;if(j==i){s=q.Next;q.Next=InVal;InVal.Next=s;}elseq.Next=InVal;}6．链表的删删除运算ListDelete(inti)的实现要删除链表表中第i个结点，首首先在单链链表中找到到删除位置置前一个结结点，并用用指针q指向它，指指针p指向要删除除的结点。。将q的指针域修修改为待删删除结点p的后继结点点的地址。。如下图所所示：x=p->data；(b)返回被删除结点数据xxpheada1a2...ai-1q...aian∧(a)找到删除位置pheada1...(c)修改指针域，将结点p删除qai-1pai...an∧ai+1①②关键语句：q->next=p->next；publicListNodeDelete(inti){if(IsEmpty()||i<1||i>GetLength()){Console.WriteLine("ListisEmptyorPositioniserror!");return0;}ListNodep=head;intj=1;while(j<i)//查找找要删除的的元素的前前一个数据据元素{p=p.Next;j++;}ListNodes=p.Next;p.Next=s.Next;returns;}7．链表元元素遍历运运算ListTraverse(L)的实实现从第一个结结点开始，，顺着指针针链依次访访问每一个个结点。publicvoidTraverse(){ListNodep=head.Next;intlen=1;while(p!=null){Console.WriteLine("第{0}个数数据元素的的值为{1}",len,p.Data);p=p.Next;len++;}}【例2-1】将两个个单链表首首尾相接进进行合并，，La为第第一个单链链表头指针针，Lb为为第二个单单链表头指指针，合并并后La为为新链表的的头指针。。【解】算法法思路：对两个单循循环链表La，Lb进行的连连接操作，，是将Lb的第一个个数据结点点接到La的尾部。。操作时需需要从La的头指针针开始找到到La的尾尾结点。staticpublicvoidMergeList(LinkListlistA,LinkListlistB){ListNodep=listA.Head;while(p.Next!=null)p=p.Next;//找到到listA中的最最后一个结结点p.Next=listB.Head.Next;//listA的的将最后一一个结点的的指针域指指向listB的第第一个结点点}循环链表在单链表中中，最后一一个结点的的指针域为为空（NULL）。访问单单链表中任任何数据只只能从链表表头开始顺顺序访问，，而不能进进行任何位位置的随机机查询访问问。如要查查询的结点点在链表的的尾部也需需遍历整个个链表。所所以单链表表的应用受受到一定的的限制。循环链表(CircularLinkedList)是另一种形形式的链式式存储结构构。它将单单链表中最最后一个结结点的指针针指向链表表的头结点点，使整个个链表头尾尾相接形成成一个环形形。这样，，从链表中中任一结点点出发，顺顺着指针链链都可找到到表中其它它结点。循循环链表的的最大特点点是不增加加存储量，，只是简单单地改变一一下最后一一个结点的的指针指向向，就可以以使操作更更加方便灵灵活。带头结点的的单循环链链表的操作作算法和带带头结点的的单链表的的操作算法法很相似，，差别仅在在于算法中中的循环条条件不同。。在循环单单链表上实实现上述基基本运算的的改动如下下：1．初始化链链表initlist(L)创建的头结结点指针域域next不为空，而而是指向自自身，L->next=L2．求线性表表长度Getlength(L)函数、查找找运算LocateElem(L,x)函数、链表表元素输出出运算ListTraverse(L)函数中，循循环遍历是是否进行的的条件由p!=NULL改为p!=L;在循环链表表中，除了了有头指针针head外，有时还还可加上一一个尾指针针tail。尾指针tail指向最后一一结点，沿沿最后一个个结点的指指针又可立立即找到链链表的第一一个结点。。在实际应应用中，使使用尾指针针来代替头头指针进行行某些操作作往往会更更简单。publicclassCirLinkList{privateListNodehead;//