第2章 线性表new.ppt

《第2章 线性表new.ppt》由会员分享，可在线阅读，更多相关《第2章 线性表new.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 *翟音翟音 数据结构数据结构 *近近近近4 4 4 4周周周周上课上课上课上课内容内容内容内容第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 字符串字符串线性结构线性结构若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1,a,a2 2 ,a,an n）线性结构的定义：线性结构的定义：线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算）*线性结构的特点

2、：线性结构的特点：只有一个首结点和尾结点；只有一个首结点和尾结点；除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a a1 1,a,a2 2 ,a,an n）线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组、广义表等等，其中，最典型、最常用的是组、广义表等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的 *第第2 2章章线性表线性表1.了解线性结构的特点了解线性结构的特点2.2

3、.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3.3.掌握链表的定义、查找、插入和删除掌握链表的定义、查找、插入和删除 4.4.能够从时间和空间复杂度的角度比较两种能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合存储结构的不同特点及其适用场合 教学目标教学目标 *2.1线性表的概念线性表的概念(ADT)(ADT)2.2线性表的顺序表示和实现线性表的顺序表示和实现(顺序表顺序表)2.3线性表的链式表示和实现线性表的链式表示和实现(链表链表)2.4线性表实现方法的比较线性表实现方法的比较教学内容教学内容 *（a0,a1,ai-1，ai,ai1，,an-1

4、）线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai i的直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的概念线性表的概念2.1.12.1.1 线性表的抽象数据类型线性表的抽象数据类型 *例例例例11分析分析分析分析2626个英文字母组成的英文表个英文字母组成的英文表个英文字母组成的英文表个英文字母组成的英文表 （A,B,C,D,Z

5、）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级计算机级计算机1 1班班041810260041810260何仕鹏何仕鹏男男 20 200404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 190404级计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班：例例例例22分析学生情况登记表分析学生情况登记表分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录;元素间关系是线性元素间关系是线性数据元素都是字母

6、数据元素都是字母;元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性 *templateclasslist/线性表性表类模板模板list，模板参数，模板参数TvoidClear();/置空置空线性表性表boolisEmpty();/线性表性表为空空时，返回，返回trueboolappend(constTvalue);/尾附函数，在表尾加新元素尾附函数，在表尾加新元素value，表，表长加加1boolinsert(constintp,constTvalue);/插入函数，在位置插入函数，在位置p上插入元素上插入元素value，表，表长加加1boo

7、ldelete(constintp);/删除函数，除函数，删去位置去位置p上的元素，表上的元素，表长减减1boolgetValue(constintp,T&value);/读取，返回位置取，返回位置p的元素的元素值到到变量量value中中 boolsetValue()/用用value修改位置修改位置p的元素的元素值boolgetPos()/把把值为value的元素位置返回到的元素位置返回到变量量p中中；线性表的抽象数据类型的定义线性表的抽象数据类型的定义线性表的抽象数据类型的定义线性表的抽象数据类型的定义模板是模板是C+C+的软件复用的功能的软件复用的功能之一，此处定义的是模板类之一，此处定义

8、的是模板类T T通常是代表要处理通常是代表要处理的数据元素的类型的数据元素的类型2.1.22.1.2 线性表的存储结构线性表的存储结构 *线性表的存储结构主要有两类：（1 1）顺序表）顺序表定长存储结构（数组）定长存储结构（数组）（2 2）链表）链表变长存储结构（指针）变长存储结构（指针）*2.1.32.1.3 线性表运算分类线性表运算分类（1）创建线性表的一个实例。）创建线性表的一个实例。（2）线性表的析构函数）线性表的析构函数list()，消除线性表实例并，消除线性表实例并释放所占空间。释放所占空间。（3）获取有关当前线性表的信息，包括由内容寻）获取有关当前线性表的信息，包括由内容寻找位置

9、、由位置读取元素内容等，不改变线性表的内找位置、由位置读取元素内容等，不改变线性表的内容。容。（4）访问线性表并改变线性表的内容或结构；例）访问线性表并改变线性表的内容或结构；例如更新制定元素内容、添加元素、删除元素、清空线如更新制定元素内容、添加元素、删除元素、清空线性表等。性表等。（5）辅助管理操作，例如求表的当前长度等。）辅助管理操作，例如求表的当前长度等。*线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续的存储单元依次存储的存

10、储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组anan来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。2.2 2.2 线性表的顺序表示和实现（顺序表）线性表的顺序表示和实现（顺序表）2.2.12.2.1 顺序表的类定义顺序表的类定义 *元素元素n-1n-1.元素元素i i.元素元素1 1元素元素0 0LoLo+mLo+i*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+i*m顺序存储顺序存储 *TempateClassarrL

11、ist：publicListprivate:T*aList;/T T类型的指针，存储线性表实例类型的指针，存储线性表实例 int maxSize;/实例的最大长度实例的最大长度 int curLen;/实例的当前长度实例的当前长度 int position;/当前处理位置当前处理位置 public:arrList(constintsize)maxSize=size;aList=newTmaxSize;curLen=position=0;arrList()deleteaList;boolAppend(constTvalue)aListposition=value;position+;curLen

12、+;顺序表的类定义顺序表的类定义 *2.2.22.2.2 顺序表的运算实现顺序表的运算实现查找查找-又称为检索又称为检索（根据指定数据查找，返回数据所在的位置）（根据指定数据查找，返回数据所在的位置）按值查找和按位置查找按值查找和按位置查找插入插入（插在第（插在第 i i 个结点之前）个结点之前）删除删除（删除第（删除第 i i 个结点）个结点）*查找查找（根据指定数据查找，返回数据所在的位置）（根据指定数据查找，返回数据所在的位置）顺序查找图示顺序查找图示253457164809012345data查找查找 16 i253457164809i253457164809i253457164809

13、i查找成功查找成功 *253457164801234data查找 50i2534571648i2534571648i2534571648i2534571648i查找失败查找失败在顺序表中查找值为在顺序表中查找值为valuevalue的元素的位置的元素的位置/在表中查找值为在表中查找值为valuevalue的元素，成功则返回的元素，成功则返回truetrue，/并将该元素所在的下标记录在参数并将该元素所在的下标记录在参数p p中，中，/失败则返回失败则返回falsefalsetemplateboolarrList:getPos(int&p,constTvalue)inti;for(i=0;in;

14、i+)if(value=aListi)p=i;returntrue;returnfalse;*查找成功查找成功的平均比较次数的平均比较次数(p(pi i为各项的查找概率为各项的查找概率为各项的查找概率为各项的查找概率)若查找概率相等，则若查找概率相等，则查找不成功查找不成功数据比较数据比较n次次查找算法时间效率分析查找算法时间效率分析 *2512478936140123456782512479989361499插入插入251247893614251247893614251247893614插第插第 3 3 个结点之前，移动个结点之前，移动 6 63 3 次次插在第插在第 i i 个结点之前，移

15、动个结点之前，移动 n-in-i 次次插入插入（插在第（插在第 i i 个结点之前）个结点之前）*（1 1）判断）判断插入位置插入位置i i 是否合法是否合法。（2 2）判断顺序表的）判断顺序表的存储空间是否已满存储空间是否已满。（3 3）将第）将第n-1n-1至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空出第空出第i i个位置。个位置。（4 4）将要插入的新元素）将要插入的新元素e e放入第放入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回TRUETRUE。【插入算法思想插入算法思想】*若插入在尾结点之后，则根本无需移动（特别快）

16、；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【插入算法分析插入算法分析】【插入算法描述插入算法描述】算法算法2.4书书P32 *251247893614012345678251247361425124736142512473614删除删除删除删除（删除第（删除第 i i 个结点）个结点）删除

17、第删除第 3 3 个结点，移动个结点，移动 6 63+13+1 次次删除第删除第 i i 个结点，移动个结点，移动 n-i+1n-i+1次次 *（1 1）判断）判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为0in-10in-1）（2 2）将欲删除的元素保留在）将欲删除的元素保留在e e中。中。（3 3）将第）将第i+1i+1至第至第n-1 n-1 位的元素依次位的元素依次向前移动一个位置向前移动一个位置（4 4）表长减表长减1 1，删除成功返回，删除成功返回OKOK。【删除算法思想删除算法思想】*若删除尾结点，则根本无需移动（特别快）；若删除尾结点，则根本无需移动（特别快）；

18、若删除首结点，则表中若删除首结点，则表中n-1n-1个元素全部前移（特别慢）；个元素全部前移（特别慢）；若要考虑在各种位置删除（共若要考虑在各种位置删除（共n n种可能）的平均移动次数，种可能）的平均移动次数，该如何计算？该如何计算？算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上【删除算法分析删除算法分析】【删除算法描述删除算法描述】算法算法2.5书书P33 *显然，顺序表的显然，顺序表的空间空间复杂度复杂度S(n)=S(n)=O(1)O(1)（没有占用辅助空间）（没有占用辅助空间）查找、插入、删除算法的平均查找、插入、删除算法的平均时间时间复杂度为复杂度为O(n)O(n

19、)*（1 1）利用数据元素的存储位置表示线性表中相邻数）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的据元素之间的前后关系，即线性表的逻辑结构与逻辑结构与存储结构一致存储结构一致顺序表（顺序存储结构）的特点顺序表（顺序存储结构）的特点这种存取元素的方法被称为这种存取元素的方法被称为随机存取法随机存取法（2 2）在访问线性表时，可以快速地计算出任何一个）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，数据元素的存储地址。因此可以粗略地认为，访访问每个元素所花时间相等问每个元素所花时间相等顺序表的优缺点顺序表的优缺点 缺点：缺点：在插入、删

20、除某一元素时，需要移动大量元素在插入、删除某一元素时，需要移动大量元素浪费存储空间浪费存储空间属于静态存储形式，数据元素的个数不能自由扩属于静态存储形式，数据元素的个数不能自由扩充充链表链表为克服这一缺点为克服这一缺点优优点：点：存储密度大存储密度大（结点本身所占存储量（结点本身所占存储量/结点结构所占存储量）结点结构所占存储量）可以可以随机存取随机存取表中任一元素表中任一元素 *2.3 2.3 链表链表链式存储结构链式存储结构结点在存储器中的位置是结点在存储器中的位置是任意任意的，的，即逻辑逻辑上相邻的数据元素在物理上不一定相邻上相邻的数据元素在物理上不一定相邻线性表的链式表示又称为线性表的

21、链式表示又称为非顺序映像非顺序映像或或链式映像链式映像。*如何实现？如何实现？通过通过指针指针来实现来实现单链表的存储映像单链表的存储映像free(a)可利用存储空间可利用存储空间a0a2a1a3 freehead(b)经过一段运行后的单链表结构经过一段运行后的单链表结构 *例例画出画出26个英文字母表的链式存储结构个英文字母表的链式存储结构链式存储结构：链式存储结构：逻辑结构：逻辑结构：（a,b,a,b,y,z,y,z）aheadb/z链式存储结构链式存储结构特点特点u每个元素每个元素(表表项)由由结点点(Node)构成。构成。u线性性结构构u结点之点之间可以可以连续，可以不，可以不连续存存

22、储u结点的点的逻辑顺序与物理序与物理顺序可以不一致序可以不一致u表可表可扩充充单链表单链表 (Singly Linked List)(Singly Linked List)data nexta0a1a2a3a4head32单链表的结构定义单链表的结构定义在在C中定中定义单链表的表的结构十分构十分简单：typedefintT;/结点数据的点数据的类型型typedefstructnode/结点点结构定构定义Tdata;/结点数据域点数据域structnode*link;/结点点链接指接指针域域LinkNode;/结点命名点命名这是一个是一个递归的定的定义。在在结构定构定义时不考不考虑操作，以后在定

23、操作，以后在定义和和实现链表操作表操作时直接使用直接使用结构的成分。构的成分。33单链表的类定义单链表的类定义使用面向使用面向对象方法，要把数据与操作一起定象方法，要把数据与操作一起定义和封装，用多个和封装，用多个类表达一个表达一个单链表。表。u链表表结点点(Link)类u链表表(InkList)类定定义方式方式u复合方式复合方式u嵌套方式嵌套方式u继承方式承方式u结构方式构方式链表结点的类定义链表结点的类定义templateclassLinkpublic:Tdata;/结点的数据域结点的数据域Link*next;/结点的指点的指针域域Link(constTinfo,constLink*nex

24、tValue=NULL)/具有两个参数的具有两个参数的LinkLink构造函数构造函数data=info;next=nextValue;Link(constLink*nextValue)/具有一个参数的具有一个参数的LinkLink构造函数构造函数next=nextValue;*头指针头指针head和尾指针和尾指针tail10head8/1650taill指针指针headhead指向单链表开始结点的指针。指向单链表开始结点的指针。l指针指针tailtail指向单链表尾结点的指针。指向单链表尾结点的指针。加速对链表尾端的访问，加速对链表尾端的访问，append()append()可在常数可在常数

25、时间内完成。时间内完成。templateclassInkList:publicLink/继承结点类继承结点类private:Link*head,*tail;/定义头、尾指针定义头、尾指针Link*setPos(constintp);/返回单链表返回单链表InkList中指向第中指向第p个元素的指针值个元素的指针值public:InkList()/用用classLink的构造函数来初始化的构造函数来初始化head和和tailhead=tail=newLink;linkList()/析构函数，释放链表析构函数，释放链表Link*tmp;while(head!=NULL)/从头结点开始，释放结点从头

26、结点开始，释放结点tmp=head;head=head-next;deletetmp;；链表的类定义链表的类定义添加头结点的作用？添加头结点的作用？*讨论讨论1.1.如何表示如何表示空表空表？有头结点时，有头结点时，当头结点的指针域为空当头结点的指针域为空时表示空表时表示空表非空表非空表 空表空表0ana0headhead表头表头结点结点第一个第一个结点结点带头结点：带头结点：head-next=Null不带头结点：不带头结点：head=Null *讨论讨论2 2.在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？便于便于首元结点首元结点的处理的处理首元结点的地址保存在头结点的指针域

27、中首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理一致，无须进行特殊处理;便于便于空表和非空表空表和非空表的统一处理的统一处理无论链表是否为空，头指针都是指向头结无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就点的非空指针，因此空表和非空表的处理也就统一了。统一了。例如在第一个结点前插入结点的操作例如在第一个结点前插入结点的操作 *讨论讨论3.3.头结点的头结点的数据域数据域内装的是什么？内装的是什么？头结点的头结点的数据域数据域可以为空，也可存放线性表可以为空，也可存放线性

28、表长度长度等附加信息，但此结点不能计入链表长度值。等附加信息，但此结点不能计入链表长度值。头结点的数据域头结点的数据域H H *思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构按序号查找按序号查找l链表的检索（查找）链表的检索（查找）*l从第从第0 0个结点（个结点（head-nexthead-next）顺链扫描，用指针）顺链扫描，用

29、指针p p指向指向当前扫描到的结点，当前扫描到的结点，p p初值初值p p=head-next-next。l用用count count 做计数器，累计当前扫描过的结点数，做计数器，累计当前扫描过的结点数，countcount 的初值为的初值为0 0。l当当p p指向扫描到的下一结点时，计数器指向扫描到的下一结点时，计数器countcount加加1 1。l当当countcount=i i时，时，p p所指的结点就是要找的第所指的结点就是要找的第i i个结点。个结点。l单链表实际长度单链表实际长度ii时，返回时，返回Null;Null;li=-1i=-1时，返回指向头结点的指针时，返回指向头结点的

30、指针headhead【算法思想算法思想】按序号查找按序号查找i的取值按照的取值按照C/C+的数组下标编号规则，从的数组下标编号规则，从0到到n-1，头结点的编号为，头结点的编号为-1。42算法算法2.9单链表的检索算法单链表的检索算法templateLink*InkList:setPos(inti)/函数返回表中第函数返回表中第i个元素的地址。若个元素的地址。若i=-1,返返/回回head;若若i超出超出表中结点个数，则返回表中结点个数，则返回NULL。intcount=0;if(i=-1)returnhead;/i为为-1定位到头结点定位到头结点Link*p=new Link (head-n

31、ext);while(p!=NULL&count next;count+;returnp;/返回第返回第i结点结点地址或地址或NULL;算法时间复杂度算法时间复杂度为为O(n)。单链表中的插入与删除操作单链表中的插入与删除操作插入插入uu第一种情况：在第一种情况：在链表最前端表最前端插入（插入（头插法）插法）headp-next=head-nexthead-next=pl l从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：从一个空表开始，重复读入数据：l l生成新结点生成新结点生成新结点生成新结点l l将读入数据存放到新结点的数据域中将读入数据存放到新

32、结点的数据域中将读入数据存放到新结点的数据域中将读入数据存放到新结点的数据域中l l将该新结点插入到链表的前端将该新结点插入到链表的前端将该新结点插入到链表的前端将该新结点插入到链表的前端l l直到读入结束符为止。直到读入结束符为止。直到读入结束符为止。直到读入结束符为止。uu第二种第二种情况：在情况：在链表末尾表末尾插入（尾插法）插入（尾插法）headtail-next=p;p-next=NULL;tail=p;l l每次将新结点加在插到链表的表尾；每次将新结点加在插到链表的表尾；l l尾指针尾指针tail总是指向表中最后一个结点，新结点总是指向表中最后一个结点，新结点插在它的后面；插在它的

33、后面；l l尾指针尾指针tail初始时置为指向表头结点地址初始时置为指向表头结点地址head。u第三种情况：在第三种情况：在链表中表中间插入插入将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位个结点的位置上，即插入到置上，即插入到a ai-1i-1与与a ai i之间（图之间（图2.72.7）(1)p-next=pre-next(2)pre-next=pheadprep思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？*【插入算法思想插入算法思想】（1 1）找到）找到a ai i 的前驱的前驱a ai-1i-1,用用p p指针指向指针指向a ai-1i-1（2

34、2）生成一个新结点）生成一个新结点*q q（3 3）将新结点）将新结点*q q的数据域置为的数据域置为valuevalue（4 4）新结点）新结点*q q的指针域指向结点的指针域指向结点a ai i (q-next=p-next)(q-next=p-next)（5 5）令结点）令结点*p p的指针域指向新结点的指针域指向新结点*q q算法2.10见书P38单链表结点的删除算法headpre-next=dele-nextDeletedele *将单链表的第将单链表的第i i个结点删除个结点删除算法思想：算法思想：（1 1）找到）找到a ai-1i-1存储位置存储位置p p（2 2）临时保存结点）

35、临时保存结点a ai i的地址在的地址在q q中，以备释放中，以备释放（3 3）令）令p-nextp-next指向指向a ai i的直接后继结点的直接后继结点（4 4）将）将a ai i的值保留在的值保留在e e中中（5 5）释放）释放a ai i的空间的空间单链表的删除算法单链表的删除算法算法2.11见书P39 *1.查找查找:因单链表只能顺序存取，即在查找时要从因单链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为头指针找起，查找的时间复杂度为O(n)。2.插入和删除插入和删除:因单链表不需要移动元素，只要修因单链表不需要移动元素，只要修改指针，一般情况下时间复杂度为改指针，一

36、般情况下时间复杂度为O(1)。但是，如果要在单链表的位置但是，如果要在单链表的位置i进行插入或删除进行插入或删除操作，需要先定位查找前驱结点操作，需要先定位查找前驱结点i-1，定位操作的，定位操作的平均时间代价为平均时间代价为O(n)，所以在这种情况下单链表，所以在这种情况下单链表的插入删除算法的时间复杂度为的插入删除算法的时间复杂度为O(n)。链表的运算时间效率分析链表的运算时间效率分析2.3.2双链表双链表双链表每个结点由数据域和指针域构成，指每个结点由数据域和指针域构成，指针域包含指向后继和前驱的两个指针。针域包含指向后继和前驱的两个指针。a3a1a4a2后继指针前驱指针head 双链表

37、结点的类定义双链表结点的类定义template class doubleLinkpublic:T data;/结点的数据域doubleLink *next;/结点的后继指针doubleLink *pre;/结点的前驱doubleLink(T info,doubleLink *nextValue=NULL，doubleLink *preValue=NULL)/具有三个参数的List构造函数data=info;next=nextValue;pre=preValue；doubleLink(doubleLink *nextValue=NULL，doubleLink *preValue=NULL)/具有

38、两个参数的List构造函数next=nextValue;pre=preValue；;三、链表三、链表 双链表的类定义双链表的类定义template class doubleList:public doubleLink /继承结点类private:doubleLink *head;/定义头指针int len;/存储链表的长度public:doubleList()head=new doubleLink;len=0;linkList()Link*p;while(head!=NULL)p=head;head=head-next;delete p;；三、链表三、链表双链表结点的删除算法headp-nex

39、t-pre=p-pre；P-pre-next=p-next；3 3 3 31 1 1 12 2 2 2pppp双链表结点的删除算法head3 3 3 31 1 1 1P-next=NULL;P-pre=NULL;Deletep；双链表双链表结点的插入算法结点的插入算法(非尾结点）非尾结点）headnewq;q-data=newValue;q-next=p-next;q-pre=p;P-next=q;P-next-pre=q;3 3 3 31 1 1 1 p2 2 2 24 4 4 4q q q q（2）双链表结点的插入算法（尾结点）headP-next=q;q-pre=p;31 p24q（3）

40、循环链表结构同单链表，最后一个结点的指针指向头结点a3a2a4a1优势：顺着任何一个结点的指针都可以找到其它结点优势：顺着任何一个结点的指针都可以找到其它结点应用实例：可用于实现多个进程共享资源应用实例：可用于实现多个进程共享资源head（3）循环链表各类操作同单链表基本一致，差别在于判空、最后结点判断条件head循环链表的空表形式循环链表的空表形式head-next=head最后一个结点的判断最后一个结点的判断p-next=headpa0a1an head循环链表的应用循环链表的应用约瑟夫问题约瑟夫问题据据说著名犹太著名犹太历史学家史学家Josephus有有过以下的故事：在以下的故事：在罗马

41、人占人占领乔塔帕特后，塔帕特后，39个犹太人与个犹太人与Josephus及他的朋及他的朋友友躲到一个洞中，到一个洞中，39个犹太人决定宁愿死也不要被个犹太人决定宁愿死也不要被敌人抓人抓到，于是决定了一个自到，于是决定了一个自杀方式，方式，41个人排成一个个人排成一个圆圈，由圈，由第第1个人开始个人开始报数，每数，每报数到第数到第3人人该人就必人就必须自自杀，然后，然后再由下一个重新再由下一个重新报数，直到所有人都自数，直到所有人都自杀身亡身亡为止。止。然而然而Josephus和他的朋友并不想遵从，和他的朋友并不想遵从，Josephus要他的要他的朋友先假装遵从，他将朋友与自己安排在第朋友先假装

42、遵从，他将朋友与自己安排在第16个与第个与第31个个位置，于是逃位置，于是逃过了了这场死亡游死亡游戏。约瑟夫问题算法思想约瑟夫问题算法思想输入人数，间隔数，剩余人数按人数创建循环链表按人数创建循环链表开始按间隔数删除链表中的结点直到剩余人数开始按间隔数删除链表中的结点直到剩余人数本章要求本章要求熟练掌握顺序表和单链表的各类运算的实现；了解双链表和循环链表的原理及相关算法。第二章习题第二章习题开始练习1经常需要随机查找第i个元素及其前驱的值，则采用（）存储方法节省时间 A、单链表B、双链表C、单循环链表 D、顺序表2 链表不具有的特点是（）。A、可随机访问任一元素B、插入删除不需要移动元素C、不

43、必事前估计存储空间D、所需空间与线性表长度成正比第一大题：单项选题3 线性表采用链式存储，其地址（）A、必须是连续的B、一定是不连续的 C、部分地址必须是连续的D、连续与否都可以4 单链表中，若*p不是尾结点，在其后插入*s的操作是（）。A、s-next=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;D、p-next=s;s-next=p5 在一个长度为n的顺序表中，向第i个元素（0inext=pB、p-next-next=p-next C、p-next-next=pD、p-next=p-next-next7一个双链表中，在*p

44、结点后插入一个结点*s的操作顺序是（）。A、s-prior=p;p-next=s;p-next-prior=s;s-next=p-next B、p-next=s-next;p-next-prior=s;p-next=s;s-prior=p;C、p-next=s;s-prior=p;D、p-next-prior=s;s-next=p-next;s-prior=p;p-next=s;8 在一个双链表中，删除*p结点后的一个结点的 操作顺序是（）。A、p-next=p-next-next;p-next-next-prior=p B、p-next-prior=p p-next=p-next-next;

45、C、p-next=p-next-next;p-next-prior=p D、p-next-next=p-next;p-next-prior=p第二大题：多项选题1 在带头结点在带头结点head的单循环链表中至少有一个的单循环链表中至少有一个结点的条件是（结点的条件是（）尾结点）尾结点*p的条件是。的条件是。A、head-next!=NULLB、head-next!=headC、p=NULL D、p-next=head2在一个单链表的在一个单链表的*p结点之前插入一个结点之前插入一个*s结点，结点，可执行如下操作：可执行如下操作：S-next=();p-next=();t=p-data;p-da

46、ta=();s-data=();A、t B、sC、p-next D、s-data作业作业 *根据单链表的头插法和尾插法的算法思想（幻灯片43，44），写出单链表的头插法和尾插法的算法new new 类型名类型名T T（初值列表）（初值列表）功能：功能：申请用于存放申请用于存放T T类型对象的内存空间，并依初值列表赋以初值类型对象的内存空间，并依初值列表赋以初值结果值：结果值：成功：成功：T T类型的指针，指向新分配的内存类型的指针，指向新分配的内存失败：失败：0 0（NULLNULL）int*p1=newint;或或int*p1=newint(10);delete delete 指针变量名指针

47、变量名功能：功能：释放指针释放指针P P所指向的内存。所指向的内存。deletep1;补充：补充：C+C+的动态存储分配（的动态存储分配（125125页）页）*n函数调用时传送给形参表的实参必须与形参在类型、函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致个数、顺序上保持一致n参数传递有两种方式参数传递有两种方式n传值方式传值方式（参数为整型、实型、字符型等）（参数为整型、实型、字符型等）n传地址传地址参数为指针变量参数为指针变量参数为引用类型参数为引用类型参数为数组名参数为数组名补充：补充：C+C+中的参数传递中的参数传递 *voidmain()floata,b;cinab

48、;swap(a,b);coutaendlbendl;#includevoidswap(floatm,floatn)floattemp;temp=m;m=n;n=temp;传值传值方式方式把实参的值传送给函数局部工作区相应的副把实参的值传送给函数局部工作区相应的副本中本中，函数使用这个副本执行必要的功能。，函数使用这个副本执行必要的功能。函数修改的是函数修改的是副本的值副本的值，实参的值不变实参的值不变 *传地址传地址方式方式指针变量作参数指针变量作参数voidmain()floata,b,*p1,*p2;cinab;p1=&a;p2=&b;swap(p1,p2);coutaendlbendl;

49、#includevoidswap(float*m,float*n)floatt;t=*m;*m=*n;*n=t;形参变化影响实参形参变化影响实参 *传地址方式引用类型作参数（传地址方式引用类型作参数（137137页）页）引用：它用来给一个对象提供一个替代的名字。引用：它用来给一个对象提供一个替代的名字。#includevoidmain()inti=5;int&j=i;i=7;couti=ij=ab;swap(a,b);coutaendlbendl;#includevoidswap(floatm,floatn)floattemp;temp=m;m=n;n=temp;传地址传地址方式方式引用类型作参数引用类型作参数 *（1 1）传递引用给函数与传递指针的效果是一）传递引用给函数与传递指针的效果是一样的，样的，形参变化实参也发生变化形参变化实参也发生变化。（2 2）引用类型作形参，在内存中并没有产生）引用类型作形参，在内存中并没有产生实参的副本，它实参的副本，它直接对实参操作直接对实参操作；引用不占用新的地址，当引用不占用新的地址，当参数传递的数参数传递的数据量较大据量较大时，用引用比用一般变量传递参数时，用引用比用一般变量传递参数的时间和空间效率都好。的时间和空间效率都好。引用类型作形参的三点说明引用类型作形参的三点说明