欢迎来到天天文库
浏览记录
ID:35527967
大小:82.58 KB
页数:8页
时间:2019-03-25
《c数据结构之链表复习资料》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、第3章链表一、复习要点本章复习的要点:1、基本知识点单链表是一种线性结构,链表各结点的物理存储可以是不连续的,因此各结点的逻辑次序与物理存放次序可以不一致。必须理解单链表的定义和特点,单链表的抽象数据类型和类定义,单链表成员函数,如构造函数、搜索、插入、删除等操作的实现,对比带表头结点单链表的搜索、插入、删除操作,比较其优缺点。其次是循环链表的定义和特点,它与单链表的差别,它的搜索、插入、删除操作的实现。最后是双向链表的定义,它的插入与删除操作的实现。2、算法设计>单链表的迭代求解算法,包括统计链表结
2、点个数,在链表中寻找与给定值mluc匹配的结点,在链表中寻找第i个结点,在链表中第i个位置插入新结点,删去第i个结点,单链表各结点顺序逆转算法,在单链表中按从左到右和从右到左的顺序遍历的逆转链算法。>带表头结点的单链表的迭代算法,包括统计链表结点个数,在链表中寻找与给定值value匹配的结点,在链表中寻找第i个结点,在链表中第i个位置插入新结点,删去第i个结点,连续删除链表中含有value值的结点,两个有序链表的合并。>循环链表的迭代算法:包括统计链表结点个数,在链表中寻找与给定值value匹配的结点
3、,在链表中寻找第i个结点,在链表中第i个位置插入新结点,删去第i个结点,将循环链表链入单链表的表头。二、难点和重点1、单链表:单链表定义、相应操作的实现。>单链表的两种定义方式(复合方式与嵌套方式)>单链表的搜索算法与插入、删除算法>单链表的递归与迭代算法2、循环链表:单链表与循坏链表的异同3、双向链表:带表头结点的双向循环链表>双向循坏链表的定义,带表头结点的优点>双向链表的搜索、插入与删除算法三、习题的解析3-1线性表可用顺序表或链表存储。试问:(1)两种存储表示各有哪些主要优缺点?(2)如果有n
4、个表同时并存,并且在处理过程屮各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下,应选用哪种存储表示?为什么?(3)若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时,应采用哪种存储表示?为什么?【解答】(1)顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期问不会发生改变,因此,不易扩充。同时,由于在插入或删除时,为保持原有次序,平均需要移动一半(或近一半)
5、元素,修改效率不高。链接存储表示的存储空I'可-•般在程序的运行过程中动态分配和释放,且只要存储器中还有空间,就不会产生存储溢出的问题。同时在插入和删除时不盂要保持数据元素原来的物理顺序,只需要保持原來的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高。(1)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下,应选用链接存储表示。如果采用顺序存储表示,必须在一个连续的可用空间中为
6、这n个表分配空间。初始时因不知道哪个表增长得快,必须平均分配空间。在程序运行过程中,有的表占用的空间增长得快,有的表占用的空间增长得慢;有的表很快就用完了分配给它的空间,有的表才用了少量的空间,在进行元素的插入时就必须成片地移动其他的表的空间,以空出位置进行插入;在元素删除时,为填补空白,也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示,一个表的存储空间可以连续,可以不连续。表的增长通过动态存储分配解决,只要存储器未满,就不会有表溢出的问题;表的收缩可以通过动态存储释放实现,释放的
7、空间还可以在以后动态分配给其他的存储申请要求,非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形,处理十分简便和快捷。所以选用链接存储表示较好。(2)应采用顺序存储表示。因为顺序存储表示的存取速度快,但修改效率低。若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时采用顺序存储表示较好。3-2针对带表头结点的单链表,试编写下列函数。(1)定位函数Locate:在单链表中寻找第i个结点。若找到,则函数返回第i个结点的地址:若找不到,则函数返回NULLo(2)求最大值函
8、数max:通过一趟遍历在单链表中确定值最大的结点。【解答】单链表的结点类(ListNodeclass)和链表类(Listclass)的类定义。〃将单链表定义在List.h〃前视的类定义〃链表结点类的定义//List类作为友元类定义//数据域〃链指针域〃仅初始化指针成员的构造函数#ifndefL1ST_H#dcfincLIST_Htemplatepe>classList;templatepe>classListNode{
此文档下载收益归作者所有