数据结构与算法第二章清华大学出版社赵玉兰学习教案.pptx

《数据结构与算法第二章清华大学出版社赵玉兰学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法第二章清华大学出版社赵玉兰学习教案.pptx（109页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)与算法第二章清华与算法第二章清华大学出版社赵玉兰大学出版社赵玉兰第一页，共109页。2.1 线性表线性表ADTADT线性表线性表线性表线性表n n线性表（Linear List）n n例1 26个大写英文字母组成的字母表n n （A，B，C，Z）n n例2 某个学生宿舍学生姓名(xngmng)n n （“wan”，“li”，“zhao”，“ye”，“hao”，“jia”）n n例3 学生信息情况登记表姓姓 名名学学 号号性性 别别年年 龄龄班班 级级家庭住址家庭住址陈陈 燕燕060001女女21计计06内蒙古内蒙古刘刘 伟伟060002男男21计计

2、06北京北京王树林王树林060003男男22计计06山东山东第1页/共109页第二页，共109页。2.1 线性表线性表ADTADT线性表线性表线性表线性表n n定义n n由 n(n0)个性质相同的数据元素(yun s)a1,a2,an 组成的有限序列n n数据元素(yun s)的个数 n(n0)定义为表的长度，当 n=0 时称为空表n n常常将非空的线性表（n0）记作：n n L=(a1,a2,ai,an)n n 注意：这里的数据元素(yun s)ai(1i n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。第2页/共109页第三页，共109页。2.1 线性表线性表ADTADT线性表线

3、性表线性表线性表n n线性表的逻辑特征n n有限性：线性表中数据元素的个数是有穷的n n相同性：线性表中数据元素的类型是同一的n n顺序性n n有且仅有一个(y)开始结点 a1，它没有前趋，而仅有一个(y)后继 a2 n n有且仅有一个(y)终端结点 an，它没有后继，而仅有一个(y)前趋 an-1n n其余的内部结点 ai(2i n-1)都有且仅有一个(y)前趋 ai-1 和一个(y)后继 ai+1 n n线性表的逻辑结构是一种典型的线性结构第3页/共109页第四页，共109页。2.1 线性表线性表ADTADT线性表线性表线性表线性表n n抽象数据(shj)类型线性表的定义n n ADT L

4、ist n n Data n n 数据(shj)元素表n n size：数据(shj)元素的个数n n Operationn n Constructorn n Process：创建空表n n Clearn n Process：清空线性表n nIsEmptyn n Process：判断线性表是否为空n n Output：若线性表为空，返回true，否则返回false第4页/共109页第五页，共109页。2.1 线性表线性表ADTADT线性表线性表线性表线性表 Length Length Process Process：求线性表中元素个数：求线性表中元素个数 Output Output：返回线性表

5、中元素个数：返回线性表中元素个数 GetElem GetElem Input Input：要取出的元素的位置：要取出的元素的位置 Process Process：取出指定位：取出指定位(dngwi)(dngwi)置上的元素置上的元素 Output Output：返回取出的元素值：返回取出的元素值 Locate Locate Input Input：要定位：要定位(dngwi)(dngwi)的元素的元素 Process Process：为指定元素定位：为指定元素定位(dngwi)(dngwi)Output Output：若线性表中有给定元素，返回元素位置，否则：若线性表中有给定元素，返回元素位置

6、，否则 返回返回-1-1第5页/共109页第六页，共109页。2.1 线性表线性表ADTADT线性表线性表线性表线性表 Insert Insert Input Input：被插入：被插入(ch r)(ch r)元素值及其位置元素值及其位置 Process Process：将给定元素插入：将给定元素插入(ch r)(ch r)指定位置指定位置 Delete Delete Input Input：被删除元素的位置：被删除元素的位置 Process Process：若线性表中有给定元素，则删除它：若线性表中有给定元素，则删除它 Prior Prior Input Input：要求前驱的元素：要求前驱

7、的元素 Process Process：求给定元素的直接前驱：求给定元素的直接前驱 Next Next Input Input：要求后继的元素：要求后继的元素 Process Process：求给定元素的直接后继：求给定元素的直接后继 /List /List 第6页/共109页第七页，共109页。2.1 线性表线性表ADTADT线性表线性表线性表线性表n n例4 假设利用线性表 LA 和 LB 分别表示两个集合A 和 B（线性表中的数据元素即为集合中的成员），现求一个新的集合 AB，并用(bn yn)LA表示结果集合。voidIntersection(ListLA,ListLB)inti=1;

8、while(i=LA.size)x=LA.GetElem(i);/在LA中取一元素k=LB.Locate(x);/在LB中搜索(susu)它if(k=-1)/在LB中未找到，则在LA中删除它LA.Delete(i);LA.size-;elsei+;/Intersection第7页/共109页第八页，共109页。2.1 线性表线性表ADTADT线性表线性表线性表线性表n n例5 假设(jish)利用线性表 LA 和 LB 分别表示两个集合A 和 B（线性表中的数据元素即为集合中的成员），现求一个新的集合 AB，并用LA表示结果集合。voidUnion(ListLA,ListLB)intn;for

9、(inti=1;i=LB.size;i+)x=LB.GetElem(i);/在LB中取一元素k=LA.Locate(x);/在LA中搜索(susu)它if(k=-1)/在LA中未找到，则在LA中插入它n=LA.size;LA.Insert(n,i);LA.size+;/Intersection第8页/共109页第九页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储顺序表顺序表定义定义顺序存储的线性表顺序存储的线性表把线性表的元素按逻辑顺序依次存放把线性表的元素按逻辑顺序依次存放(cnfng)(cnfng)在一组地址连续的存储单元里在一组地址连续

10、的存储单元里存储要点用一段地址连续的存储单元依次存储线性表中的数据元素a1a2ai-1aian第9页/共109页第十页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储n n例：（34,23,67,82）34236782存储空间的起始(qsh)地址基地址用什么属性来描述顺序表？顺序(shnx)表的容量（最大长度）顺序表的当前(dngqin)长度4第10页/共109页第十一页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储n n存储(cn ch)结构与逻辑结构的关系 存储地址存储地址 内存状态内存状

11、态线性表中线性表中的位序的位序LOC(a1)a11LOC(a1)+ma22LOC(a1)+(i-1)maiiLOC(a1)+(n-1)mann 空闲空闲顺序表存储结构示意图顺序表存储结构示意图LOC(ai)=LOC(a1)+(i-1)m基地址LOC(ai)=LOC(ai-1)+m一个数据元素所占存储量顺序表是一种随机存取的存储(cn ch)结构第11页/共109页第十二页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储u注意(zhy)u线性表的第i个元素ai存储在数组下标为i-1的位置u线性表的长度size与数组的长度MaxListSize是不

12、同的usize=n，大小可变uMaxListSize是数组的长度，大小不变usizeMaxListSize表的长度空闲anaiai-1a2a1datan-1 MaxListSize-1sizeMaxListSizei-1i-210下标如何实现顺序表的内存分配？顺序表一维数组第12页/共109页第十三页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储const int MaxListSize=100;const int MaxListSize=100;class SeqListclass SeqList DataType dataMaxListS

13、ize;DataType dataMaxListSize;int size;/int size;/元素的个数元素的个数 public:public:List()size=0;/List()size=0;/构造一个空线性表构造一个空线性表 void Clear();/void Clear();/清空顺序表清空顺序表 bool IsEmpty();/bool IsEmpty();/判断如果为空表，返回判断如果为空表，返回truetrue，否则，否则(f(f uz)uz)返回返回falsefalse DataType GetElem(int k)return datak-1;/DataType Ge

14、tElem(int k)return datak-1;/返回第返回第k k个元素个元素 int Locate(DataType e);/int Locate(DataType e);/返回第一个与元素返回第一个与元素e e匹配的元素匹配的元素 位序位序 DataType Prior(DataType e);/DataType Prior(DataType e);/返回元素返回元素e e 的前驱的前驱 DataType Next(DataType e);/DataType Next(DataType e);/返回元素返回元素e e 的后继的后继 void Insert(DataType e,in

15、t i);/void Insert(DataType e,int i);/在表中第在表中第 i i 个位置插入个位置插入e e DataType Delete(int i);/DataType Delete(int i);/删除第删除第i i个元素，并返回其值个元素，并返回其值；/SeqList/SeqList第13页/共109页第十四页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储基本操作在顺序表中的实现基本操作在顺序表中的实现定位操作定位操作算法算法(sun f(sun f)2.4 )2.4 定位定位int Locate(DataType

16、 e)int Locate(DataType e)int i=0;int i=0;while(i size&datai!=e)while(i =size)return-1;if(i =size)return-1;/没有找到没有找到 else else return i;return i;/找到此元素，返回其下标找到此元素，返回其下标/Locate/Locate 注意序号和下标之间的关系！第14页/共109页第十五页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储定位(dngwi)成功定位(dngwi)不成功e48e50第15页/共109页第十六

17、页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储n n定位(dngwi)算法的时间复杂度n n基本操作：比较n n成功时n n最好情况：比较1次（i=0），时间复杂度为O(1)n n最坏情况：比较n次（i=n-1），时间复杂度为O(n)n n平均情况：设定位(dngwi)每个数据元素的概率相等，则不成功(chnggng)时：比较n次第16页/共109页第十七页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储在在 i=4 处插入处插入 下标下标数据数据元素元素012 113 221 324 4

18、5 6 7 82528304277插入(chr)在顺序表中的第i个位置上插入(chr)eai和ai+1之间的逻辑关系发生(fshng)了变化存储位置(wizhi)要反映这个变化第17页/共109页第十八页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储算法算法2.2 2.2 插入插入(ch r)(ch r)void Insert(DataType e,int i)void Insert(DataType e,int i)if(i size|size=MaxListSize-1)if(i size|size=MaxListSize-1)exit;

19、exit;else else for(j=size;ji;j-)for(j=size;ji;j-)dataj=dataj-1;dataj=dataj-1;datai=e;/datai=e;/插入插入(ch r)(ch r)成功成功 size+;size+;/Insert/Insert什么时候不能插入？注意边界条件第18页/共109页第十九页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储n n插入算法的时间复杂度n n基本语句：移动元素n n最好情况：不移动（i=n），时间复杂度为O(1)n n最坏情况：移动 n 个元素（i=0），时间复杂度为

20、O(n)n n平均情况：设插入每个数据元素的概率(gil)相等，则第19页/共109页第二十页，共109页。2.1 线性表线性表线性表的顺序存储线性表的顺序存储线性表的顺序存储线性表的顺序存储n n删除n n删除顺序表中第 i 个位置上的元素(yun s)n nDataType Delete(int i)n n if(i=size)n n return nulldata;/被删除的元素(yun s)下标错n n else n n size-;n n e=datai;n n for(int j=i;jnext=NULL);/bool IsEmpty()return(head-next=NULL)

21、;/判断判断(pndun)(pndun)是否为空链表是否为空链表 DataType Prior(DataType e);/DataType Prior(DataType e);/返回返回e e 的前驱结点元素的前驱结点元素 DataType Next(DataType e);/DataType Next(DataType e);/返回返回e e 的后继结点元素的后继结点元素 void Insert(DataType x,int i);/void Insert(DataType x,int i);/在第在第i i个结点之前插入元素个结点之前插入元素值为值为x x的结点的结点 Datatype D

22、elete(int i);/Datatype Delete(int i);/删除第删除第i i个结点，并返回其元素值个结点，并返回其元素值 void Clear();/void Clear();/清空链表清空链表;/nextList;/nextList第29页/共109页第三十页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n取元素(yun s)n nDataType GetElem(int i)n nif(head-next=NULL)/空链表，返回空值n n return nulldata;n nelsen n p=head;k=0;n n while

23、(p&knext;k+;n n if(!p|k=0)return nulldata;/i超出链表元素(yun s)的范围n n else return p-data;n nn n/GetElem第30页/共109页第三十一页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n插入操作n n将值为 x 的新结点插入到表的第 i 个结点的位置(wi zhi)上，即插入到 ai-1 与 ai 之间n n插入过程：1）定位；2）插入。pai-1headaixa1newnodenewnodenext=pnext;pnext=newnode;第31页/共109页第三十二页

24、，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)void Insert(DataType x,int i)void Insert(DataType x,int i)/在第在第i i个结点位置个结点位置(wi zhi)(wi zhi)上插入元素值为上插入元素值为x x的结点的结点 Node*p=head;int k=0;Node*p=head;int k=0;if(isize)return nulldata;/if(isize)return nulldata;/插入位置插入位置(wi zhi)(wi zhi)错误错误 while(p&k i-1)while(p&k

25、next;k+;/p=p-next;k+;/找到插入位置找到插入位置(wi zhi)(wi zhi)if(!p)exit;if(!p)exit;Node*newnode=new Node();Node*newnode=new Node();newnode-data=x;newnode-data=x;newnode-next=p-next;newnode-next=p-next;p-next=newnode;p-next=newnode;size+;size+;/Insert/Insert第32页/共109页第三十三页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch

26、)n n删除操作(cozu)n n将表的第 i 个结点，即 ai 删去n n删除过程：1）定位；2）删除。pai-1headaia1ai+1qq=pnext;pnext=qnext;deleteq;第33页/共109页第三十四页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)DataType Delete(int i)/DataType Delete(int i)/删除第删除第i i个结点个结点 Node*p=head;int k=0;Node*p=head;int k=0;if(isize)/if(isize)/结点序号结点序号i i超出链表结点范围，返回超出

27、链表结点范围，返回(f(f nhu)nhu)空值空值 return nulldata;return nulldata;while(p&k i-1)/while(p&knext;k+;p=p-next;k+;if(p=NULL)if(p=NULL)cout “Invalid position for Deletion!n”;cout next;q=p-next;p-next=q-next;p-next=q-next;e=q-data;e=q-data;delete q;delete q;size-;return e;size-;return e;/Delete/Delete第34页/共109页第

28、三十五页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n建立单链表n n头插法建表n n该方法从一个空表开始，重复读入数据(shj)，生成新结点，将读入数据(shj)存放到新结点的数据(shj)域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。n n尾插法建表n n头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。第35页/共109页第三十六页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)头插法建表void Create(int n)head=new

29、Node();/创建(chungjin)头结点 head-next=NULL;for(i=n;i0;i-)p=new Node();if(p=NULL)exit;cinp-data;p-next=head-next;head-next=p;size=n;第36页/共109页第三十七页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n尾插法建表尾插法建表n n该方法是将新结点插入该方法是将新结点插入(ch r)(ch r)到当前到当前链表的表尾上，为此必须增加一个尾指链表的表尾上，为此必须增加一个尾指针针r r，使其始终指向当前链表的尾结点。，使其始终指向当前

30、链表的尾结点。n n （1 1）创建头结点）创建头结点 head head，使尾结点，使尾结点 r r 为为NULLNULL；n n （2 2）新建结点）新建结点 p p，如果，如果 head-next=head-next=NULLNULL，则，则 n n head-next=p head-next=p；r=pr=p；n n （3 3）否则，）否则，r-next=pr-next=p；r=pr=p；重复；重复（2 2），（），（3 3）n n （4 4）如果）如果r!=NULLr!=NULL；则；则r-next r-next=NULL=NULL第37页/共109页第三十八页，共109页。2.1

31、线性表线性表线性表的链式存线性表的链式存储储(cn ch)尾插法建表void Create(int n)void Create(int n)head=new Node();head=new Node();head-next=NULL;head-next=NULL;r=head;r=head;for(i=n;i0;i-)for(i=n;i0;i-)p=new Node();p=new Node();if(p=NULL)exit;if(p=NULL)exit;cinp-data;cinp-data;rnext=p;rnext=p;r=p;r=p;size=n;size=n;第38页/共109页第三

32、十九页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n双向链表（Double nexted list）n n每个结点中有两个(lin)指针域n n指向其直接前趋结点n n指向其直接后继结点n n每个结点结构第39页/共109页第四十页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n带头(di tu)结点的双向链表 heada1a2anheadu结点(jidin)指针的指向p=p-prior-next=p-next-prior空表非空表p-priorp-nextp第40页/共109页第四十一页，共109页。2.1 线性表

33、线性表线性表的链式存线性表的链式存储储(cn ch)n n带头(di tu)结点的双向链表类的定义n nclass DNode n n DataType data;n n DNode*prior;/指向前驱的指针n n DNode*next;/指向后继的指针n n public:n n DNode(DataType d=nulldata)n n data=d;prior=next=NULL;n n friend class DBList;n n;/DNode第41页/共109页第四十二页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)class DBListcl

34、ass DBList DNode*head;DNode*head;int size;int size;public:public:DBList()head=new DNode();size=0;/DBList()head=new DNode();size=0;/构造函数，创建空链表构造函数，创建空链表 void Create(int n);/void Create(int n);/创建长度为创建长度为n n的双链表的双链表 DataType GetElem(int i);/DataType GetElem(int i);/取得第取得第i i个元素个元素 Dnode*Locate(DataTyp

35、e e);/Dnode*Locate(DataType e);/返回第一个与返回第一个与e e匹配的结点匹配的结点(ji di(ji di n)n)指针指针 bool IsEmpty();/bool IsEmpty();/判断是否为空链表判断是否为空链表 void Insert(DataType e,int i);/void Insert(DataType e,int i);/在第在第i i个结点个结点(ji di(ji di n)n)前插入值为前插入值为e e的结点的结点(ji di(ji di n)n)DataType Delete(int i);/DataType Delete(int

36、i);/删除第删除第i i个结点个结点(ji di(ji di n)n)，并返回其元素值，并返回其元素值 void Clear();/void Clear();/清空链表清空链表;/DBList;/DBList第42页/共109页第四十三页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n定位(dngwi)定位成功head定位不成功head第43页/共109页第四十四页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n插入(ch r)操作（在结点 p 之前插入(ch r)结点 s）s-prior=p-prior;p-pri

37、or-next=s;s-next=p;p-prior=s;考虑：哪些(nxi)语句可以交换位置？哪些(nxi)不能交换？esabps=newDNode(e);第44页/共109页第四十五页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n删除操作(cozu)（删除结点 p）p-next-prior=p-prior;aiai+1ai-1pp-prior-next=p-next;deletep;第45页/共109页第四十六页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n注意n n与单链表的插入和删除操作不同的是，在双向链表

38、中插入和删除必须同时(tngsh)修改两个方向上的指针。第46页/共109页第四十七页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n循环链表n n是线性链表的变形n n表尾结点的 next 指针不为 NULL，而是指向(zh xin)了链表的头结点n n特点n n从表中任一结点出发，均可访问表中其他任一结点headhead第47页/共109页第四十八页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n循环(xnhun)链表基本操作的实现n n基本操作与单链表类似 n n在循环(xnhun)链表中遍历的终止条件是什么？终

39、止(zhngzh)p-next=NULL;或p=NULL;终止应该是p-next=head;或p=head;开始p=head-next;或p=head;第48页/共109页第四十九页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n单链表的应用：一元(y yun)多项式求和n n一元(y yun)多项式在计算机中，可以用一个(y)线性表来表示P=(p0,p1,pn)但是对于下述多项式，该表示方法并不合适P(x)=1+3x100002x20000第49页/共109页第五十页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n一

40、般情况下，一元稀疏多项式可写成n n Pn(x)=p1xe1+p2xe2+pmxemn n 其中(qzhng)：pi 是指数为ei 项的非零系数，n n 0e1 e2 term.expn;b=pb-term.expn;/a=pa-term.expn;b=pb-term.expn;/指数指数n n if(ab)/if(anext=pa;pc=pa;pa=pa-next;/pa pc-next=pa;pc=pa;pa=pa-next;/pa指针后移指针后移n n n n else if(ab)/else if(ab)/多项式多项式bhbh中当前结点的指数值小中当前结点的指数值小n n pc-nex

41、t=pb;pc=pb;pb=pb-next;/pb pc-next=pb;pc=pb;pb=pb-next;/pb指针后移指针后移n n n n else if(pa.coef+pb.coef0.0001)/else if(pa.coef+pb.coefnext;delete p;p=pb;pb=pb-next;delete p;p=pa;pa=pa-next;delete p;p=pb;pb=pb-next;delete p;n n n n else/else/将将pbpb结点的系数结点的系数(xsh)(xsh)加入加入papa结点结点n n pa-coef=pa.coef+pb.coef;

42、pc-next=pa;pc=pa;pa=pa-next;pa-coef=pa.coef+pb.coef;pc-next=pa;pc=pa;pa=pa-next;n n p=pb;pb=pb-next;delete p;p=pb;pb=pb-next;delete p;n n n n /while /whilen n if(pa)pc-next=pa;else pc-next=pb;if(pa)pc-next=pa;else pc-next=pb;n n return ah;return ah;n n 第54页/共109页第五十五页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储

43、储(cn ch)n n例2 非递减有序线性表的归并n n已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求(yoqi)将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。n n如 LA=（3,5,8,11）LB=（2,6,8,9,11,15,20）n n 则LC=（2,3,5,6,8,8,9,11,11,15,20)第55页/共109页第五十六页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n归并(gubng)算法n nvoid MergeList(LinkList&La,LinkList&Lb,LinkList&Lc)

44、n n pa=La.head-next;pb=Lb.head-next;n n Lc=La;pc=Lc.head;n n while(pa&pb)n n if(pa-datadata)n n pc-next=pa;pc=pa;pa=pa-next;n n n n else n n pc-next=pb;pc=pb;pb=pb-next;n n n n n n pc-next=pa?pa:pb;n n delete Lb.head;n n/end MergeList第56页/共109页第五十七页，共109页。2.1 线性表线性表线性表的链式存线性表的链式存储储(cn ch)n n例3 约瑟夫环问

45、题n nn(n0)个人(grn)围成一个圆圈，从第1个人(grn)开始顺时针报数，报到第m个人(grn)，令其出列。然后再从其下一个人(grn)开始重新报数，报到第m个人(grn)再令其出列，如此下去,直到圆圈中只剩一个人(grn)为止。n n例n=8 m=3第57页/共109页第五十八页，共109页。2.1 线性表线性表顺序顺序(shnx)表表和链表的比较和链表的比较n n顺序表n n没有附加存储空间开销n n随机取得任一元素n n预先申请固定长度的数组n n插入、删除需要移动元素，运算时间代价O(n)n n链表n n插入、删除运算时间代价O(1)，但找第 i 个元素个元素时间代价O(n)n

46、 n在运行(ynxng)时动态为表中新的元素分配存储空间n n顺序取得某一元素n n每个元素都有附加存储空间开销第58页/共109页第五十九页，共109页。2.1 线性表线性表顺序顺序(shnx)表表和链表的比较和链表的比较n n根据应用选择顺序表和链表n n顺序表n n结点总数目(shm)大概可以估计n n表中结点比较稳定（插入、删除操作少）n n链表n n结点数目(shm)无法预知n n线性表中结点动态变化（插入、删除操作多）第59页/共109页第六十页，共109页。2.2 数组数组数组数组数组数组n n数组的定义n n是由一组具有(jyu)相同类型的数据元素构成的有限序列，且存储在一块地

47、址连续的内存单元中n n数据元素可以是简单类型，也可以是构造类型n n数据元素在数组中的相对位置由其下标确定第60页/共109页第六十一页，共109页。2.2 数组数组数组数组数组数组n n一维数组n n只有一个下标的数组n n特点n n连续(linx)存储（别名 向量）n n除第一个元素外，其它每一个元素有且仅有一个直接前驱n n除最后一个元素外，其它每一个元素有且仅有一个直接后继第61页/共109页第六十二页，共109页。2.2 数组数组数组数组数组数组n n存储(cn ch)第62页/共109页第六十三页，共109页。2.2 数组数组数组数组数组数组n n二维数组 Anm n n每个数据

48、元素都有两个(lin)下标n n行下标 n n列下标n n二维数组是一个数据元素值为一维数组的一维数组n=4m=6mn第63页/共109页第六十四页，共109页。2.2 数组数组数组数组数组数组n n二维数组中的元素(yun s)aij可以看成属于两个向量：即第 i 行的向量Ai 和第 j 列的向量Bja00没有前驱结点，称之为开始结点；an-1,m-1没有后继结点，称之为终端(zhndun)结点aij（1in-2,1jm-2）有两个前驱结点ai,j-1,ai-1,j两个后继结点ai,j+1,ai+1,j第0行的元素a0j(j=1,m-1)只有一个前驱a0,j-1第0列的元素ai0(i=1,n

49、-1)只有一个前驱ai-1,0第n-1行的元素an-1,j(j=0,m-2)只有一个后继an-1,j+1第m-1列的元素ai,m-1(i=0,n-2)只有一个后继ai+1,m-1第64页/共109页第六十五页，共109页。2.2 数组数组数组数组数组数组n n存储(cn ch)有次序问题约定的次序不同，则计算元素地址的公式也有所不同C和PASCAL中采用行优先(yuxin)顺序；FORTRAN中采用列优先(yuxin)顺序第65页/共109页第六十六页，共109页。2.2 数组数组数组数组数组数组a00a01.a0m-1a10a11.a1m-1an-10an-11an-1m-1.以行序为主序a

50、n-1m-1an-11an-10a1m-1a11a10a0m-1a01a00n*m-1(n-1)*m1*mm-110以行序为主序存储的地址(dzh)公式为：LOC(aij)=LOC(a00)+(im+j)l第66页/共109页第六十七页，共109页。2.2 数组数组数组数组数组数组以列序为主序a00a01.a0m-1a10a11.a1m-1an-10an-11an-1m-1.an-1m-1a1m-1a0m-1an-11a11a01an-10a10a00n*m-1(m-1)*n1*nn-110以列序为主序存储的地址(dzh)公式为：LOC(aij)=LOC(a00)+(jn+i)l第67页/共1