《线性表的类型定义、顺序表示和实现.pptx》由会员分享，可在线阅读，更多相关《线性表的类型定义、顺序表示和实现.pptx（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2章章 线性表线性表2.1 线性表的类型定义线性表的类型定义2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现l线性表是一种最简单的线性结构。线性表是一种最简单的线性结构。l什么是线性结构？简单地说，线性结构是一个数据元素的有什么是线性结构？简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：序（次序）集合。它有四个基本特征：l在数据元素的非空有限集中，在数据元素的非空有限集中，存在惟一的一个被称做第一个的数据元素；存在惟一的一个被称做最后一个的数据元素；除第一个之外，集合中的每个数据元素均只有一个前驱；除最后一个之外
2、，集合中的每个数据元素均只有一个后继。l这里的这里的有序有序仅指在数据元素之间存在一个仅指在数据元素之间存在一个领先领先或或落后落后的次序关系，而非指数据元素的次序关系，而非指数据元素值值的大小可比性。比较典型的大小可比性。比较典型的线性结构：线性表、栈、队列、串等。的线性结构：线性表、栈、队列、串等。2.1 线性表的类型定义线性表的类型定义2.1.1 线性表的定义线性表的定义l线性表(linear_list)是n个数据元素的有限序列，记作（a1,a2,ai,an）。l线性表的数学模型（形式定义）：线性表的数学模型（形式定义）：l含有n个数据元素的线性表是一个数据结构l LinearList=
3、（A,R）l其中：A=ai|aiElemType,1in,n0l R=rl r=|1in-1说明：说明：l线性表的数据元素可以是各种类型（整、实、记录类型等）线性表的数据元素可以是各种类型（整、实、记录类型等）l typedef int ElemType;l typedef char ElemType;l 等；等；l同一线性表中的数据元素必须具有相同的特性，属同一类同一线性表中的数据元素必须具有相同的特性，属同一类型；型；l关系关系r是一个有序偶对的集合，即对于非空的线性表（是一个有序偶对的集合，即对于非空的线性表（a1,a2,ai-1,ai,ai+1,an），），ai-1 领先于领先于ai，
4、表示了数据元素，表示了数据元素之间的相邻关系，称之间的相邻关系，称ai-1是是ai的直接前驱，的直接前驱，ai是是ai-1的直接后继；的直接后继；l序列中数据元素的个数序列中数据元素的个数 n 定义为线性表的定义为线性表的表长表长，n=0 时的时的线性表被称为线性表被称为空表空表；l称称i为数据元素在线性表中的为数据元素在线性表中的位序位序。2.1.2 线性表的抽象数据类型线性表的抽象数据类型ADT LinearList Data:一个线性表一个线性表L定义为定义为L=(a1,a2,an)，当，当L=（）时定义为一个空表。）时定义为一个空表。Operation:bool initList(&L
5、);/初始化线性表初始化线性表L，即把它设置为一个空表，即把它设置为一个空表void clearList(&L);/将将L重置为空表重置为空表int getSize(L);/返回返回L中数据元素的个数中数据元素的个数bool isEmpty(L);/判断判断L是否为空，若空则返回是否为空，若空则返回true，否则返回，否则返回falsevoid traverList(L,visit();/遍历线性表遍历线性表L，依次对，依次对L的每个数据元素调用函数的每个数据元素调用函数visit()ElemType&getElem(L,pos);/返回线性表第返回线性表第pos个数据元素的值个数据元素的值i
6、nt locateElem(&L,e,compare();/返回返回L中第中第1个与个与e满足关系满足关系compare()的数据元的数据元素的位序。若这样的数据元素不存在，则返回素的位序。若这样的数据元素不存在，则返回0bool insertElem(&L,e,pos);/在在L的的pos位置插入位置插入e，线性表，线性表L长度加长度加1bool deleteElem(&L,pos);/删除删除L的第的第pos个数据元素个数据元素bool createList(&L,n,visit();/创建有创建有n个元素的线性表个元素的线性表2.1.3 操作举例操作举例l例：假设利用两个线性表例：假设利
7、用两个线性表La和和Lb分别表示两分别表示两个集合个集合A和和B，求一个新的集合，求一个新的集合A=A B。l算法：算法：取得Lb中的1个元素；在La中查找这个元素；若不存在：插入La中；若存在，取Lb中下一个元素，重复、，直到取完Lb的每个元素。lvoid unionList(SqList&la,SqList lb)ll int lbSize=getSize(lb);l ElemType e;l for(int i=1;i=lbSize;+i)l l e=getElem(lb,i);l if(!locateElem(la,e,equal)l insertElem(la,e,la.size+1
8、);l llint equal(ElemType e1,ElemType e2)ll if(e1.id=e2.id)l return 1;l return 0;l算法的时间复杂度为O(La.sizeLb.size)。2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 线性表的顺序表示线性表的顺序表示l线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。l 表示为：A=(a1，a2，ai，ai
9、+1，an)第第i个元素的地址个元素的地址l假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(ai)：loc(ai)=loc(a1)+(i-1)kl其中loc(a1)称为基地址。线性表的顺序存储结构示意图线性表的顺序存储结构示意图顺序存储结构可以借助于高级程序设计语言中的一维数组来表示。用用C+语言描述的顺序表类型如下所示：语言描述的顺序表类型如下所示：sqlist.h#include using namespace std;struct Node /定义结点（数据元素）的类型定义结点（数据元素）的类型int id;i
10、nt age;typedef Node ElemType;/声明结点的类型名为声明结点的类型名为ElemTypestruct SqList /定义线性表的存储结构定义线性表的存储结构ElemType*list;int size;int maxSize;bool initList(SqList&L,int ms);void clearList(SqList&L);int getSize(SqList L);bool isEmpty(SqList L);bool isFull(SqList L);void traverList(SqList L,void(*visit)(ElemType&);El
11、emType&getElem(SqList L,int pos);int locateElem(SqList&L,ElemType e,int(*compare)(ElemType,ElemType);int findList(SqList L,ElemType e);bool insertElem(SqList&L,ElemType e,int pos);bool deleteElem(SqList&L,int pos);bool createList(SqList&L,int n,void(*visit)(ElemType&);2.2.2 线性表顺序存储结构上的基本运算线性表顺序存储结构上
12、的基本运算sqlist.cppl 初始化线性表初始化线性表初始化变量，申请空间；size赋值；maxsize赋值。lbool initList(SqList&L,int ms)ll L.list=new ElemTypems;l if(!L.list)l l cerrMemory allocation failure!endl;l exit(1);l l L.size=0;l L.maxSize=ms;l return true;ll 删除线性表的所有元素，使之成为空表删除线性表的所有元素，使之成为空表l在顺序存储方式下实现此操作只要将线性表的长度置在顺序存储方式下实现此操作只要将线性表的长度
13、置0即可。即可。lvoid clearList(SqList&L)ll L.size=0;ll 检查线性表是否为空检查线性表是否为空lbool isEmpty(SqList L)ll return L.size=0;ll 获取表元素的个数获取表元素的个数lint getSize(SqList L)ll return L.size;ll 检查线性表是否已满检查线性表是否已满lbool isFull(SqList L)ll return L.size=L.maxSize;ll 得到线性表中指定序号的元素得到线性表中指定序号的元素lElemType&getElem(SqList L,int pos)
14、ll if(posL.size)l l cerrpos is out range!endl;l exit(1);l l return L.listpos-1;ll 遍历线性表遍历线性表l遍历一个线性表就是从线性表的第一个元素起，按照元遍历一个线性表就是从线性表的第一个元素起，按照元素之间的逻辑顺序，依次访问每一个元素，并且每个元素只素之间的逻辑顺序，依次访问每一个元素，并且每个元素只被访问一次，直到访问完所有元素为止。被访问一次，直到访问完所有元素为止。lvoid traverList(SqList L,void(*visit)(ElemType&)ll for(int i=0;iL.size
15、;+i)l visit(L.listi);l coutendl;ll如要依次输出每个元素的值，如要依次输出每个元素的值，visit()的实参可定义如下：的实参可定义如下：lvoid print(ElemType&e)ll coutid:e.id age:e.ageendl;ll 查找线性表中满足给定条件的元素查找线性表中满足给定条件的元素lint locateElem(SqList&L,ElemType e,int(*compare)(ElemType,ElemType)ll for(int i=0;iL.size;+i)l if(compare(L.listi,e)=1)l return i
16、+1;l return 0;ll如要查找与如要查找与e的相等（某对应成员的值相等）的元素，则的相等（某对应成员的值相等）的元素，则compare()的实的实参可定义如下：参可定义如下：lint equal(ElemType e1,ElemType e2)ll if(e1.id=e2.id)l return 1;l return 0;ll算法的时间复杂度：算法的时间复杂度：l时间耗费主要在比较元素的次数上，而次数取决时间耗费主要在比较元素的次数上，而次数取决于待查找元素的位置。于待查找元素的位置。l最好情况最好情况:compare(L.list0,e)=1 O(1）l最坏情况最坏情况:compa
17、re(L.listn-1,e)=1 O(n)l平均情况平均情况:O(n)l 向线性表中的指定位置插入一个元素向线性表中的指定位置插入一个元素l原表：原表：a1，a2，ai-1，ai，ai+1，anl插入后的表：插入后的表：a1，a2，ai-1，b，ai，ai+1，anai-1和ai逻辑关系发生变化；因逻辑相邻的数据元素物理位置上也相邻，因此，除非i=n+1，否则必须将原表中位置n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，在该位置上插入新结点b。lbool insertElem(SqList&L,ElemType e,int pos)ll if(posL.size
18、+1)l l cerrpos is out range!=pos-1;-i)l L.listi+1=L.listi;l L.listpos-1=e;l +L.size;l return true;ll 从线性表中删除指定位置的元素从线性表中删除指定位置的元素l原表：原表：a1，a2，ai-1，ai，ai+1，anl删除后的表：删除后的表：a1，a2，ai-1，ai+1，ai+2，anai-1 和 ai逻辑关系发生变化需移动元素：i=n 只删 an即可 1in-1 将ai+1 an前移lbool deleteElem(SqList&L,int pos)ll if(posL.size)l l ce
19、rrpos is out range!endl;l return false;l l for(int i=pos-1;iL.maxSize)l return false;l for(int i=0;in;+i)l l visit(L.listi);l +L.size;l l return true;l2.2.3 顺序表应用例顺序表应用例l例：已知线性表例：已知线性表La和和Lb中的数据元素按值非中的数据元素按值非递减有序排列，现要将递减有序排列，现要将La和和Lb归并为一个新归并为一个新的线性表的线性表Lc，且，且Lc中的数据元素仍按值非递中的数据元素仍按值非递减排列。减排列。main.cpp
20、l#include sqlist.hlSqList mergeList(SqList La,SqList Lb);lvoid print(ElemType&e)ll coutid:e.id age:e.ageendl;llint main()ll SqList la,lb;l ElemType a1,a2,a3,b1,b2,b3,b4;l a1.id=1;l a2.id=3;l a3.id=6;l b1.id=2;l b2.id=4;l b3.id=5;l b4.id=7;l initList(la,10);l initList(lb,10);l insertElem(la,a1,1);l i
21、nsertElem(la,a2,2);l insertElem(la,a3,3);l insertElem(lb,b1,1);l insertElem(lb,b2,2);l insertElem(lb,b3,3);l insertElem(lb,b4,4);l traverList(la,print);l traverList(lb,print);l SqList lc=mergeList(la,lb);l traverList(lc,print);llSqList mergeList(SqList La,SqList Lb)ll SqList Lc;l initList(Lc,20);l i
22、nt i,j,k,laSize,lbSize;l ElemType ai,bj;l i=j=1,k=0;l laSize=getSize(La);l lbSize=getSize(Lb);l while(i=laSize)&(j=lbSize)l l ai=getElem(La,i);l bj=getElem(Lb,j);l if(compare(ai,bj)=1)l l insertElem(Lc,ai,+k);l +i;l l elsel l insertElem(Lc,bj,+k);l +j;l l l while(i=laSize)l l ai=getElem(La,i+);l ins
23、ertElem(Lc,ai,+k);l l while(j=lbSize)l l bj=getElem(Lb,j+);l insertElem(Lc,bj,+k);l l return Lc;l2.3 线性表的链式表示和实现线性表的链式表示和实现l线性表的链式存贮结构，也称为链表。其存贮方式线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元是：在内存中利用存贮单元(可以不连续可以不连续)来存放元素来存放元素值及它在内存的地址，各个元素的存放顺序及位置值及它在内存的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计都可以以任意顺序进行，原来相邻的元素存放
24、到计算机内存后不一定相邻，从一个元素找下一个元素算机内存后不一定相邻，从一个元素找下一个元素必须通过地址必须通过地址(指针指针)才能实现。故不能像顺序表一样才能实现。故不能像顺序表一样可随机访问，而只能按顺序访问。常用的链表有单可随机访问，而只能按顺序访问。常用的链表有单链表、循环链表、双向链表和多重链表等。链表、循环链表、双向链表和多重链表等。2.3.1 单链表结构单链表结构l在定义的链表中，若只含有一个指针域来存放下一在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为个元素地址，称这样的链表为单链表单链表或或线性链表线性链表。l线性链表中的结点结构可描述为：线性链表中的
25、结点结构可描述为：其中data 域用来存放结点本身信息，类型由具体问题而定，这里，我们也将其设定为ElemType类型，表示某一种具体的已知类型，next域用来存放下一个元素地址。l单链表可用单链表可用+描述为：描述为：lstruct LNodelElemType data;lLNode*next;l;l对上述线性表可设：对上述线性表可设：LNode*H;l其中：其中：lH为单链表的头指针，为单链表的头指针，H指向表中第一个结点，若指向表中第一个结点，若H=NULL,则线性表为则线性表为空表空表；l若一个指针域的值为空，则在图形中用若一个指针域的值为空，则在图形中用 表示；表示；l存储第一个元
26、素的结点称为表头结点，存储最后一个元素存储第一个元素的结点称为表头结点，存储最后一个元素的结点称为表尾结点，指向表头结点的指针的结点称为表尾结点，指向表头结点的指针(H)称为表头指针，称为表头指针，通常以表头指针命名一个链表，不能丢。通常以表头指针命名一个链表，不能丢。l为了方便插入和删除表头结点操作更方便，经常为了方便插入和删除表头结点操作更方便，经常在表头结点之前增加一个结点，称为表头附加结点在表头结点之前增加一个结点，称为表头附加结点（又称头结点）。（又称头结点）。l值得注意的是，若线性表为空，在不带头结点的情值得注意的是，若线性表为空，在不带头结点的情况下，头指针为空况下，头指针为空(
27、NULL)，但在带头结点的情况下，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指链表的头指针不为空，而是其头结点中指针域的指针为空。针为空。2.3.2 单链表中基本操作的实现单链表中基本操作的实现（带头结点）（带头结点）l设线性表为(a1，a2，ai，ai+1，an),其相应带有头结点的线性链表为：单链表类型定义如下：单链表类型定义如下：linklist.hl#include lusing namespace std;lstruct Elemllint id;lint age;l;ltypedef Elem ElemType;lstruct LNodellElemType
28、data;lLNode*next;l;ltypedef LNode*LinkList;void initList(LinkList&L);LinkList getRear(LinkList L);void createList(LinkList&L,int n,void(*visit)(ElemType&);void clearList(LinkList&L);int getSize(LinkList L);bool isEmpty(LinkList L);void traverList(LinkList L,void(*visit)(ElemType&);ElemType&getElem(L
29、inkList L,int pos);int locateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType);bool insertElem(LinkList&L,ElemType e,int pos);bool deleteElem(LinkList&L,int pos);LinkList mergeList(LinkList La,LinkList lb,int(*compare)(ElemType,ElemType);linklist.cpp 初始化单链表初始化单链表lvoid initList(LinkList&L)l
30、l L=new LNode;l if(!L)l exit(1);/存储空间分配失败存储空间分配失败l L-next=NULL;ll算法的时间复杂度为算法的时间复杂度为O(1)。获取链尾指针获取链尾指针lLinkList getRear(LinkList L)ll LinkList p=L;l while(p-next!=NULL)l p=p-next;l return p;l 创建单链表创建单链表lvoid createList(LinkList&L,int n,void(*visit)(ElemType&)ll LinkList p;l LinkList r=L;l for(int i=1;
31、idata);l p-next=NULL;l r-next=p;l r=r-next;l l 遍历单链表遍历单链表lvoid traverList(LinkList L,void(*visit)(ElemType&)ll LinkList p=L;l if(p-next=NULL)l coutlist is empty!next!=NULL)l l p=p-next;l visit(p-data);l l coutnext,p;l L-next=NULL;l while(r!=NULL)l l p=r;l r=r-next;l delete p;l ll算法的时间复杂度为算法的时间复杂度为O(
32、Listlength(L)。判断单链表是否为空判断单链表是否为空lbool isEmpty(LinkList L)ll if(L-next=NULL)l return true;l elsel return false;l 获取单链表长度获取单链表长度lint getSize(LinkList L)ll LinkList p=L;l int n=-1;l while(p!=NULL)l l p=p-next;l +n;l l return n;l 获取指定位置的元素获取指定位置的元素lElemType&getElem(LinkList L,int pos)ll LinkList p=L;l i
33、nt i=0;l if(posgetSize(L)l l coutpos is out range!endl;l exit(1);l l while(inext;l +i;l l return p-data;l 定位满足条件的元素定位满足条件的元素lint locateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType)ll LinkList p=L;l int i=0;l while(p-next!=NULL)l l p=p-next;l +i;l if(compare(p-data,e)=1)l return i;l l r
34、eturn 0;l 在指定位置插入元素在指定位置插入元素lbool insertElem(LinkList&L,ElemType e,int pos)ll LinkList p=L,s;l int i=0;l while(p!=NULL&inext;l +i;l l if(posdata=e;l s-next=p-next;l p-next=s;l return true;l 删除指定位置的元素删除指定位置的元素lbool deleteElem(LinkList&L,int pos)ll LinkList p=L,q;l int i=0;l if(posnext)=NULL)l return
35、false;l while(p-next)!=NULL&inext;l +i;l l q=p-next;l p-next=q-next;l delete q;l return true;l2.3.3 单链表算法例单链表算法例l例：将两个有序链表并为一个有序链表。例：将两个有序链表并为一个有序链表。lLinkList mergeList(LinkList La,LinkList lb,int(*compare)(ElemType,ElemType)ll LinkList Lc,pa,pb,pc;l pa=La-next;l pb=lb-next;l Lc=pc=La;l while(pa&pb)
36、l l if(compare(pa-data,pb-data)l l pc-next=pa;l pc=pa;l pa=pa-next;l l elsel l pc-next=pb;l pc=pb;l pb=pb-next;l l l pc-next=pa?pa:pb;l return Lc;lmain.cppl#include linklist.hlint comp1(ElemType e1,ElemType e2)ll if(e1.id=e2.id)l return 1;l elsel return 0;llint comp2(ElemType e1,ElemType e2)ll if(e1
37、.id=e2.id)l return 1;l elsel return 0;llvoid print(ElemType&e)ll coutid:e.id age:e.ageendl;llvoid inputElem(ElemType&e)ll coute.id;l coute.age;l coutendl;llint main()ll LinkList la,lb,lc;l initList(la);l initList(lb);l initList(lc);l ElemType a1,a2,a3,b1,b2,b3,b4;l a1.id=1;l a2.id=3;l a3.id=6;l b1.i
38、d=2;l b2.id=4;l b3.id=5;l b4.id=7;l insertElem(la,a1,1);l insertElem(la,a2,2);l insertElem(la,a3,3);l insertElem(lb,b1,1);l insertElem(lb,b2,2);l insertElem(lb,b3,3);l insertElem(lb,b4,4);l traverList(la,print);l traverList(lb,print);l coutr:endl;l lc=mergeList(la,lb,comp1);l traverList(lc,print);l
39、coutlocateElem(lc,b1,comp2)endl;l小结：小结：l从以上对链表的各种操作的讨论可知，链式存储结从以上对链表的各种操作的讨论可知，链式存储结构的优势在于：构的优势在于：能有效利用存储空间；用指针指示数据元素之间的后继关系，便于进行插入、删除等操作；l而其劣势则是不能随机存取数据元素。同时，它还而其劣势则是不能随机存取数据元素。同时，它还丢失了一些顺序表有的长处，如线性表的丢失了一些顺序表有的长处，如线性表的表长表长和和数据元素在线性表中的数据元素在线性表中的位序位序，在上述的单链表中，在上述的单链表中都看不见了。又如，不便于在表尾插入元素，需遍都看不见了。又如，不便
40、于在表尾插入元素，需遍历整个表才能找到插入的位置。历整个表才能找到插入的位置。l为了更突出链表的优势，需改进单链表结构的定义。为了更突出链表的优势，需改进单链表结构的定义。除了保留指向头结点的指针外，还应增设除了保留指向头结点的指针外，还应增设尾指针尾指针和和表长表长两个属性。两个属性。l同时，我们从上面讨论的链表基本操作的实现算法同时，我们从上面讨论的链表基本操作的实现算法中可以看出，在对链表进行操作时，经常需要一个中可以看出，在对链表进行操作时，经常需要一个指针在链表中巡游，由此可以设想，如果将这个在指针在链表中巡游，由此可以设想，如果将这个在操作中进行巡游的操作中进行巡游的指针指针以及它
41、所指结点的数据元以及它所指结点的数据元素在线性表中的素在线性表中的位序位序纳入链表结构中，作为链表纳入链表结构中，作为链表定义中的两个成员，必然会对链表的操作带来很多定义中的两个成员，必然会对链表的操作带来很多方便。方便。2.3.4 静态链表静态链表l某些语言无指针类型，某些语言无指针类型，如何使用链式存储？如何使用链式存储？l用用整数（又称游标整数（又称游标(cursor)）来模拟指针实现链来模拟指针实现链表。因需要为备用空间静态分配一个数组，故把这表。因需要为备用空间静态分配一个数组，故把这种用种用游标游标实现的链表称为实现的链表称为静态链表静态链表（static linkedlist）l
42、其方法是：定义一个规模较大的记录数组作为备用其方法是：定义一个规模较大的记录数组作为备用结点空间，当需要结点空间，当需要产生产生新结点时，从备用空间中新结点时，从备用空间中取出一个结点取出一个结点相当于生成新结点；当要释放结相当于生成新结点；当要释放结点时，将结点归还到备用空间中。点时，将结点归还到备用空间中。l数组中的元素：数组中的元素：l特点：特点：仍需静态分配一个较大空间插入和删仍需静态分配一个较大空间插入和删除时不需要移动元素，仅需修改指针，具有除时不需要移动元素，仅需修改指针，具有链式存储结构的主要优点。链式存储结构的主要优点。例：例：A=(44，50，57，62，68，75，83，
43、94)l利用来自数组中的结点（元素），动态产生一个单链表，利用来自数组中的结点（元素），动态产生一个单链表，称为称为静态链表静态链表；l静态链表也由一个头指针唯一指定；静态链表也由一个头指针唯一指定；l为便于结点的产生和释放，通常将为便于结点的产生和释放，通常将备用数组空间备用数组空间链成一个链成一个具有头指针的单链表，并称它为可用空间表或备用空间表。具有头指针的单链表，并称它为可用空间表或备用空间表。l静态链表同样可以借助一维数组来描述：静态链表同样可以借助一维数组来描述：lconst int MAXSIZE=100;lstruct SNodel l ElemType data;l int
44、cur;/指示其后继结点在数组中的位置指示其后继结点在数组中的位置l;ltypedef SNode SLinkListMAXSIZE;l/声明声明SLinkList为为SNode数组类型，包含数组类型，包含MAXSIZE个元素。个元素。lSLinkList S;lS0存放单链表的表头附加结点；存放单链表的表头附加结点；lS1存放空闲表的表头附加结点；存放空闲表的表头附加结点；l剩余空间剩余空间MAXSIZE-2个结点作为元素结点使用；个结点作为元素结点使用；l空闲表最后一个结点的空闲表最后一个结点的cur=0,表示空指针。表示空指针。初始化单链表：初始化单链表：l单链表：无元素，单链表：无元素
45、，S0.cur=0l空闲表：所有的空间空闲表：所有的空间lfor(int i=2;inext。lb.判定是否到链尾判定是否到链尾l单链表：单链表：p-next=NULL。l循环链表：循环链表：p-next=L。lc.链表的合并链表的合并l例：有两个带头结点的循环单链表例：有两个带头结点的循环单链表A、B，编，编写一个算法，将两个循环单链表合并为一个写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为循环单链表，其头指针为A。l算法思想算法思想1（非循环链表必需的方法）：先找（非循环链表必需的方法）：先找到两个链表的尾，并分别用指针到两个链表的尾，并分别用指针p、q指向它指向它们，然后将
46、第一个链表的尾与第二个表的第们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。使它的链域指向第一个表的头结点。l采用上面的方法，需要遍历链表，找到表尾，采用上面的方法，需要遍历链表，找到表尾，其执行时间是其执行时间是O(n)。l若在若在尾指针表示尾指针表示的单循环链表上实现，则只需要修的单循环链表上实现，则只需要修改指针，无需遍历，其执行时间是改指针，无需遍历，其执行时间是 O(1)。l/此算法将两个链表首尾连接起来此算法将两个链表首尾连接起来 lvoid merge(LNode*&A,LNode*
47、&B)l lLNode*p;lp=A-next;/保存链表保存链表A的头结点地址的头结点地址 lA-next=B-next-next;/链表链表B的开始结点链到链表的开始结点链到链表A的终端结点之后的终端结点之后 ldelete B-next;/释放链表释放链表B的头结点的头结点 lB-next=p;/链表链表A的头结点链到链表的头结点链到链表B的终端结点之后的终端结点之后lA=B;l2.3.5 双向链表双向链表l循环单链表的出现，虽然能够实现从任一结循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但时间耗点出发沿着链能找到其前驱结点，但时间耗费是费是O(n)。如果希望从表
48、中快速确定某一个。如果希望从表中快速确定某一个结点的前驱，另一个解决方法就是在单链表结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针的每个结点里再增加一个指向其前驱的指针域。域。这样形成的链表中就有两条方向不同的这样形成的链表中就有两条方向不同的链，我们可称之为双链，我们可称之为双(向向)链表链表(Double Linked List)。l双向链表结点结构：双向链表结点结构：l双链表的结构定义如下：双链表的结构定义如下：ltypedef struct DuLNodell ElemType data;l struct DuLNode*priorl struct DuL
49、Node*next;l DuLNode,*DuLinkList;l由于在双向链表中既有前向链又有后向链，寻找任由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常一个结点的直接前驱结点与直接后继结点变得非常方便。设指针方便。设指针p指向双链表中某一结点，则有下式成指向双链表中某一结点，则有下式成立：立：lp-prior-next=p=p-next-prior双链表的部分操作：双链表的部分操作：双向链表的前插操作双向链表的前插操作ls=new LNode;ls-data=c;/产生新结点产生新结点ls-prior=p-prior;/lp-prior-next=s;/ls-next=p;/lp-prior=s;/双向链表的删除操作双向链表的删除操作lp-prior-next=p-next;lp-next-prior=p-prior;ldelete p;例：设一个循环双链表例：设一个循环双链表L=（a,b,c,d）,编写一个算法编写一个算法,将链表将链表转换为转换为L=（b,a,c,d）。）。l算法思想：本题实际上是交换表中前两个元素的次算法思想：本题实际上是交换表中前两个元素的次序。序。l摘下摘下b（1）（2）l插入到插入到a前面（前面（3）（4）（5）（6）