白癜风治疗 http://www.hldxc.com/m/06线性表
知识结构：
图1知识结构1.线性表的定义与操作1.1线性表的定义
线性表（LinearList）是由
个相同类型的数据元素
组成的序列。即表中除首尾元素外，其它元素有且仅有一个直接前驱和直接后继。首元素仅有一个直接后继，尾元素仅有一个直接前驱，记为：
。
表中数据元素的个数称为表的长度。
例1：字母表
例2：学生成绩表
表1学生成绩表1.2线性表的操作随机存取：获取或设置指定索引处的数据元素值。（支持索引器）插入操作：将数据元素值插入到指定索引处。移除操作：移除线性表指定索引处的数据元素。查找操作：寻找具有特征值域的结点并返回其下标。得到表长：获取线性表中实际包含数据元素的个数。是否为空：判断线性表中是否包含数据元素。清空操作：移除线性表中的所有数据元素。图2线性表接口
usingSystem;namespaceLinearStruct{///summary///线性表的抽象数据类型////summary///typeparamname="T"线性表中元素的类型/typeparampublicinterfaceILinearListTwhereT:IComparableT{///summary///获取线性表中实际包含元素的个数////summaryintLength{get;}///summary///获取或设置指定索引处的元素////summary///paramname="index"要获取或设置的元素从零开始的索引/param///returns指定索引处的元素/returnsTthis[intindex]{get;set;}///summary///判断线性表中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnsboolIsEmpty();///summary///将元素插入到指定索引处////summary///paramname="index"从零开始的索引,应在该位置插入data./param///paramname="data"要插入的元素/paramvoidInsert(intindex,Tdata);///summary///移除线性表指定索引处的元素////summary///paramname="index"要移除元素从0开始的索引/paramvoidRemove(intindex);///summary///在线性表中寻找元素data.////summary///paramname="data"要寻找的元素/param///returns如果存在返回该元素在线性表中的位置,否则返回-1./returnsintSearch(Tdata);///summary///从线性表中移除所有元素////summaryvoidClear();}}2.线性表的顺序存储与实现
定义：利用顺序存储结构（即利用数组）实现的线性表，称为顺序表。
特点：逻辑结构与存储结构相同；具有随机存取的特点。
图3顺序表存储示意图
实现：
图4利用顺序存储结构实现线性表
usingSystem;namespaceLinearStruct{///summary///用顺序存储结构实现的线性表////summary///typeparamname="T"顺序表中元素的类型/typeparampublicclassSeqListT:ILinearListTwhereT:IComparableT{///summary///数据集合////summaryprotectedreadonlyT[]Dataset;///summary///获取SeqList中实际包含元素的个数////summarypublicintLength{get;privateset;}///summary///获取SeqList中最多包含元素的个数////summarypublicintMaxSize{get;}///summary///初始化SeqList类的新实例////summary///paramname="max"SeqList中最多包含元素的个数/parampublicSeqList(intmax){if(max=0)thrownewArgumentOutOfRangeException();MaxSize=max;Dataset=newT[MaxSize];Length=0;}///summary///获取或设置指定索引处的元素////summary///paramname="index"要获得或设置的元素从零开始的索引/param///returns指定索引处的元素/returnspublicTthis[intindex]{get{if(index0
indexLength-1)thrownewIndexOutOfRangeException();returnDataset[index];}set{if(index0
indexLength-1)thrownewIndexOutOfRangeException();Dataset[index]=value;}}///summary///判断SeqList中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){returnLength==0;}///summary///将元素插入到指定索引处////summary///paramname="index"从零开始的索引,应在该位置插入data./param///paramname="data"要插入的元素/parampublicvoidInsert(intindex,Tdata){if(index0
indexLength)thrownewIndexOutOfRangeException();if(Length==MaxSize)thrownewException("达到最大值");for(inti=Length;iindex;i--){Dataset=Dataset[i-1];}Dataset[index]=data;Length++;}///summary///移除SeqList指定索引处的元素////summary///paramname="index"要移除元素从0开始的索引/parampublicvoidRemove(intindex){if(index0
indexLength-1)thrownewIndexOutOfRangeException();for(inti=index;iLength-1;i++){Dataset=Dataset[i+1];}Length--;}///summary///在SeqList中寻找元素data.////summary///paramname="data"要寻找的元素/param///returns如果存在返回该元素在线性表中的位置,否则返回-1./returnspublicintSearch(Tdata){inti;for(i=0;iLength;i++){if(Dataset.CompareTo(data)==0)break;}returni==Length?-1:i;}///summary///从SeqList中移除所有元素////summarypublicvoidClear(){Length=0;}}}
应用：
usingSystem;usingLinearStruct;namespaceExampleList{classProgram{staticvoidMain(string[]args){ListTest(newSeqListstring());//2//a1//a3}privatestaticvoidListTest(ILinearListstringlst){lst.Insert(0,"a1");lst.Insert(1,"a2");lst.Insert(2,"a3");lst.Remove(1);Console.WriteLine(lst.Length);for(inti=0;ilst.Length;i++){Console.WriteLine(lst);}}}}3.线性表的链式存储与实现
利用指针方式实现的线性表称为链表（单链表、循环链表、双向链表）。它不要求逻辑上相邻的数据元素在物理位置上也相邻，即：逻辑结构与物理结构可以相同也可以不相同。
例3：将线性表
以链表的形式存储。
图5利用链式方式存储数据元素3.1单链表
定义：每个结点只含有一个链域（指针域）的链表。即：利用单链域的方式存储线性表的逻辑结构。
结构：
图6单链表存储结构
实现：
对结点的封装：
图7对单链表结点的封装
usingSystem;namespaceLinearStruct{///summary///单链表结点////summary///typeparamname="T"结点中数据元素的类型/typeparampublicclassSNodeTwhereT:IComparableT{///summary///获取或设置该结点的数据元素////summarypublicTData{get;set;}///summary///获取或设置该结点的后继结点////summarypublicSNodeTNext{get;set;}///summary///初始化SNode类的新实例////summary///paramname="data"该结点的数据元素/param///paramname="next"该结点的后继结点/parampublicSNode(Tdata,SNodeTnext=null){Data=data;Next=next;}}}
对单链表的封装：
图8对单链表的封装
usingSystem;namespaceLinearStruct{///summary///用链式存储结构实现的线性表--单链表////summary///typeparamname="T"单链表中元素的类型/typeparampublicclassSLinkListT:ILinearListTwhereT:IComparableT{///summary///存储头结点////summaryprotectedSNodeTPHead{get;set;}///summary///获取SLinkList中实际包含元素的个数////summarypublicintLength{get;privateset;}///summary///初始化SLinkList类的新实例////summarypublicSLinkList(){Length=0;PHead=null;}///summary///将元素插入到单链表的首部////summary///paramname="data"要插入的元素/parampublicvoidInsertAtFirst(Tdata){PHead=newSNodeT(data,PHead);Length++;}///summary///获得指定索引处的结点////summary///paramname="index"元素从零开始的索引/param///returns指定索引处的结点/returnsprivateSNodeTLocate(intindex){if(index0
indexLength-1)thrownewIndexOutOfRangeException();SNodeTtemp=PHead;for(inti=0;iindex;i++){temp=temp.Next;}returntemp;}///summary///将元素插入到单链表的尾部////summary///paramname="data"要插入的元素/parampublicvoidInsertAtRear(Tdata){if(PHead==null){PHead=newSNodeT(data);}else{Locate(Length-1).Next=newSNodeT(data);}Length++;}///summary///获取或设置指定索引处的元素////summary///paramname="index"要获得或设置的元素从零开始的索引/param///returns指定索引处的元素/returnspublicTthis[intindex]{get{if(index0
indexLength-1)thrownewIndexOutOfRangeException();returnLocate(index).Data;}set{if(index0
indexLength-1)thrownewIndexOutOfRangeException();Locate(index).Data=value;}}///summary///判断SLinkList中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){returnLength==0;}///summary///将元素插入到指定索引处////summary///paramname="index"从零开始的索引,应在该位置插入data./param///paramname="data"要插入的元素/parampublicvoidInsert(intindex,Tdata){if(index0
indexLength)thrownewIndexOutOfRangeException();if(index==0){InsertAtFirst(data);}elseif(index==Length){InsertAtRear(data);}else{SNodeTtemp=Locate(index-1);temp.Next=newSNodeT(data,temp.Next);Length++;}}///summary///移除SLinkList指定索引处的元素////summary///paramname="index"要移除元素从0开始的索引/parampublicvoidRemove(intindex){if(index0
indexLength-1)thrownewIndexOutOfRangeException();if(index==0){PHead=PHead.Next;}else{SNodeTtemp=Locate(index-1);temp.Next=temp.Next.Next;}Length--;}///summary///在SLinkList中寻找元素data.////summary///paramname="data"要寻找的元素/param///returns如果存在返回该元素在线性表中的位置,否则返回-1./returnspublicintSearch(Tdata){inti;SNodeTtemp=PHead;for(i=0;iLength;i++){if(temp.Data.CompareTo(data)==0)break;temp=temp.Next;}returni==Length?-1:i;}///summary///从SLinkList中移除所有元素////summarypublicvoidClear(){PHead=null;Length=0;}}}
应用：
usingSystem;usingLinearStruct;namespaceExampleList{classProgram{staticvoidMain(string[]args){ListTest(newSLinkListstring());//2//a1//a3}privatestaticvoidListTest(ILinearListstringlst){lst.Insert(0,"a1");lst.Insert(1,"a2");lst.Insert(2,"a3");lst.Remove(1);Console.WriteLine(lst.Length);for(inti=0;ilst.Length;i++){Console.WriteLine(lst);}}}}3.2循环链表
定义：是一种首尾相连的单链表。即：在单链表中，将尾结点的指针域null改为指向PHead，就得到单链形式的循环链表。
表现形式：
图9利用头指针表示循环链表
通常情况下，使用尾指针表示循环链表。
图10利用尾指针表示循环链表
实现：
对循环链表的封装：
图11对循环链表的封装
usingSystem;namespaceLinearStruct{///summary///用链式存储结构实现的线性表--循环链表////summary///typeparamname="T"循环链表中元素的类型/typeparampublicclassCLinkListT:ILinearListTwhereT:IComparableT{///summary///存储尾部结点////summaryprotectedSNodeTPRear{get;set;}///summary///获取CLinkList中实际包含元素的个数////summarypublicintLength{get;privateset;}///summary///获取或设置指定索引处的元素////summary///paramname="index"要获得或设置的元素从零开始的索引/param///returns指定索引处的元素/returnspublicTthis[intindex]{get{if(index0
indexLength-1)thrownewIndexOutOfRangeException();returnLocate(index).Data;}set{if(index0
indexLength-1)thrownewIndexOutOfRangeException();Locate(index).Data=value;}}///summary///初始化CLinkList类的新实例////summarypublicCLinkList(){Length=0;PRear=null;}///summary///判断CLinkList中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){returnLength==0;}///summary///将元素插入到循环链表的尾部////summary///paramname="data"要插入的元素/parampublicvoidInsertAtRear(Tdata){if(IsEmpty()){PRear=newSNodeT(data);PRear.Next=PRear;}else{SNodeTtemp=newSNodeT(data,PRear.Next);PRear.Next=temp;PRear=temp;}Length++;}///summary///将元素插入到循环链表的首部////summary///paramname="data"要插入的元素/parampublicvoidInsertAtFirst(Tdata){if(IsEmpty()){PRear=newSNodeT(data);PRear.Next=PRear;}else{SNodeTtemp=newSNodeT(data,PRear.Next);PRear.Next=temp;}Length++;}///summary///获得指定索引处的结点////summary///paramname="index"元素从零开始的索引/param///returns指定索引处的结点/returnsprivateSNodeTLocate(intindex){if(index0
indexLength-1)thrownewIndexOutOfRangeException();SNodeTtemp=PRear.Next;for(inti=0;iindex;i++){temp=temp.Next;}returntemp;}///summary///将元素插入到指定索引处////summary///paramname="index"从零开始的索引,应在该位置插入data./param///paramname="data"要插入的元素/parampublicvoidInsert(intindex,Tdata){if(index0
indexLength)thrownewIndexOutOfRangeException();if(index==0){InsertAtFirst(data);}elseif(index==Length){InsertAtRear(data);}else{SNodeTtemp=Locate(index-1);temp.Next=newSNodeT(data,temp.Next);Length++;}}///summary///移除CLinkList指定索引处的元素////summary///paramname="index"要移除元素从0开始的索引/parampublicvoidRemove(intindex){if(index0
indexLength-1)thrownewIndexOutOfRangeException();if(PRear==PRear.Next){PRear=null;}else{if(index==Length-1){SNodeTtemp=Locate(Length-2);temp.Next=PRear.Next;PRear=temp;}elseif(index==0){PRear.Next=PRear.Next.Next;}else{SNodeTtemp=Locate(index-1);temp.Next=temp.Next.Next;}}Length--;}///summary///在CLinkList中寻找元素data.////summary///paramname="data"要寻找的元素/param///returns如果存在返回该元素在线性表中的位置,否则返回-1./returnspublicintSearch(Tdata){inti;SNodeTtemp=PRear;for(i=0;iLength;i++){if(temp.Next.Data.CompareTo(data)==0)break;temp=temp.Next;}return(i==Length)?-1:i;}///summary///从CLinkList中移除所有元素////summarypublicvoidClear(){Length=0;PRear=null;}}}
应用：
usingSystem;usingLinearStruct;namespaceExampleList{classProgram{staticvoidMain(string[]args){ListTest(newCLinkListstring());//2//a1//a3}privatestaticvoidListTest(ILinearListstringlst){lst.Insert(0,"a1");lst.Insert(1,"a2");lst.Insert(2,"a3");lst.Remove(1);Console.WriteLine(lst.Length);for(inti=0;ilst.Length;i++){Console.WriteLine(lst);}}}}3.3双向链表
定义：每个结点含有两个链域（指针域）的链表。即：利用双链域的方式存储线性表的逻辑结构。
结构：
图12双链表存储结构
实现：
对结点的封装：
图13对双链表结点的封装
usingSystem;namespaceLinearStruct{///summary///双向链表结点////summary///typeparamname="T"结点中数据元素的类型/typeparampublicclassDNodeTwhereT:IComparableT{///summary///获取或设置该结点的前趋结点////summarypublicDNodeTPrior{get;set;}///summary///获取或设置该结点的后继结点////summarypublicDNodeTNext{get;set;}///summary///获取或设置该结点的数据元素////summarypublicTData{get;set;}///summary///初始化DNode类的新实例////summary///paramname="data"该结点的数据元素/param///paramname="prior"该结点的前趋结点/param///paramname="next"该结点的后继结点/parampublicDNode(Tdata,DNodeTprior=null,DNodeTnext=null){Prior=prior;Data=data;Next=next;}}}
对双向链表的封装：
图14对双向链表的封装
usingSystem;namespaceLinearStruct{///summary///用链式存储结构实现的线性表--双链表////summary///typeparamname="T"结点中数据元素的类型/typeparampublicclassDLinkListT:ILinearListTwhereT:IComparableT{///summary///存储头结点////summaryprotectedDNodeTPHead{get;set;}///summary///存储尾结点////summaryprotectedDNodeTPRear{get;set;}///summary///获取DLinkList中实际包含元素的个数////summarypublicintLength{get;privateset;}///summary///初始化DLinkList类的新实例////summarypublicDLinkList(){PHead=null;PRear=null;Length=0;}///summary///将元素插入到双链表的首部////summary///paramname="data"要插入的元素/parampublicvoidInsertAtFirst(Tdata){if(IsEmpty()){DNodeTtemp=newDNodeT(data);PHead=temp;PRear=temp;}else{DNodeTtemp=newDNodeT(data,null,PHead);PHead.Prior=temp;PHead=temp;}Length++;}///summary///将元素插入到双链表的尾部////summary///paramname="data"要插入的元素/parampublicvoidInsertAtRear(Tdata){if(IsEmpty()){DNodeTtemp=newDNodeT(data);PHead=temp;PRear=temp;}else{DNodeTtemp=newDNodeT(data,PRear,null);PRear.Next=temp;PRear=temp;}Length++;}///summary///获得指定索引处的结点////summary///paramname="index"元素从零开始的索引/param///returns指定索引处的结点/returnsprivateDNodeTLocate(intindex){if(index0
indexLength-1)thrownewIndexOutOfRangeException();DNodeTtemp=PHead;for(inti=0;iindex;i++){temp=temp.Next;}returntemp;}///summary///将元素插入到指定索引处////summary///paramname="index"从零开始的索引,应在该位置插入data./param///paramname="data"要插入的元素/parampublicvoidInsert(intindex,Tdata){if(index0
indexLength)thrownewIndexOutOfRangeException();if(index==0){InsertAtFirst(data);}elseif(index==Length){InsertAtRear(data);}else{DNodeTtemp1=Locate(index);DNodeTtemp2=newDNodeT(data,temp1.Prior,temp1);temp2.Prior.Next=temp2;temp2.Next.Prior=temp2;Length++;}}///summary///移除DLinkList指定索引处的元素////summary///paramname="index"要移除元素从0开始的索引/parampublicvoidRemove(intindex){if(index0
indexLength-1)thrownewIndexOutOfRangeException();if(Length==1){PHead=null;PRear=null;}else{if(index==0){PHead=PHead.Next;PHead.Prior=null;}elseif(index==Length-1){PRear=PRear.Prior;PRear.Next=null;}else{DNodeTtemp=Locate(index);temp.Prior.Next=temp.Next;temp.Next.Prior=temp.Prior;}}Length--;}///summary///判断DLinkList中是否包含元素////summary///returns如果包含元素返回false,否则返回true./returnspublicboolIsEmpty(){returnLength==0;}///summary///从DLinkList中移除所有元素////summarypublicvoidClear(){Length=0;PHead=null;PRear=null;}///summary///在DLinkList中寻找元素data.////summary///paramname="data"要寻找的元素/param///returns如果存在返回该元素在线性表中的位置,否则返回-1./returnspublicintSearch(Tdata){inti;DNodeTtemp=PHead;for(i=0;iLength;i++){if(temp.Data.CompareTo(data)==0)break;temp=temp.Next;}returni==Length?-1:i;}///summary///获取或设置指定索引处的元素////summary///paramname="index"要获得或设置的元素从零开始的索引/param///returns指定索引处的元素/returnspublicTthis[intindex]{get{if(index0
indexLength-1)thrownewIndexOutOfRangeException();returnLocate(index).Data;}set{if(index0
indexLength-1)thrownewIndexOutOfRangeException();Locate(index).Data=value;}}}}
应用：
usingSystem;usingLinearStruct;namespaceExampleList{classProgram{staticvoidMain(string[]args){ListTest(newDLinkListstring());//2//a1//a3}privatestaticvoidListTest(ILinearListstringlst){lst.Insert(0,"a1");lst.Insert(1,"a2");lst.Insert(2,"a3");lst.Remove(1);Console.WriteLine(lst.Length);for(inti=0;ilst.Length;i++){Console.WriteLine(lst);}}}}
后台回复「搜搜搜」，随机获取电子资源！欢迎
