《c程序设计实例教程》下ppt

《c程序设计实例教程》下ppt

ID:40007779

大小:1.78 MB

页数:155页

时间:2019-07-17

《c程序设计实例教程》下ppt_第1页
《c程序设计实例教程》下ppt_第2页
《c程序设计实例教程》下ppt_第3页
《c程序设计实例教程》下ppt_第4页
《c程序设计实例教程》下ppt_第5页
资源描述:

《《c程序设计实例教程》下ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、《C程序设计实例教程》下梁立第7章动态组织数据 第8章综合应用第七章动态组织数据7.1建立链表的过程设想一下,我们看杂志时碰到有篇文章3页不够放,4页又空着太多。这时,编辑往往先给这篇文章(且称它为文章a)排3页(且称这3页为a.part1),接着排其他文章,等什么时候有空的页面还够安排a剩下的部分(且称它为a.part2)时,就把a.part2排进去。由于文章a在排版时被分成了不连续的两块,读者怎样才能找到第二个逻辑块呢?编辑在a.part1的末尾加进了一个线索“下接XX页”,读者顺着这个线索很容易就找到了a.part2。如此一来,a.part1放的不仅

2、仅有文章本身,还有指示下一个逻辑块在哪里的线索。通过这个线索,a.part1和a.part2就联系在一起了。那么,读者又是怎么知道a.part2的后面还有没有另外一个逻辑块呢?其实每种杂志的每篇文章的最后都有一个特殊的符号,读者看到这个符号就知道这已经是最后一个逻辑块了。而厚厚的一本书中,读者又怎样找到文章a呢?翻翻目录就知道了,那里有文章a所在页码的信息。图7.1两个结点构成的链表文章a......下接xx页a.part1......完a.part2文章axx页......目录这样,a.part1和a.part2就组成了由两个结点构成的链表:目录中的页码

3、指向链表a的第一个结点,这个页码信息通常称为头指针,只要有这个头指针就能找到整个链表;a.part1后面的线索就是指针域,指示下一个逻辑块在哪里;a.part2的指针域指示后面不再有其他结点,称为尾结点。如图7.1所示。链表是一种重要并且很常用的数据结构,可以动态地组织数据。链表不要求两个元素在物理上相邻,元素的物理顺序与逻辑顺序可以不同,只要在元素结构中加一个指针项,用来指向下一个元素的地址便可。组成链表的基本单元是结点,所谓结点至少由2个域组成,一个是数据域,一个是指针域,数据域存储结点本身的信息,指针域指向后继结点。每个元素都有一个指针指向下一个元素

4、,如此环环相扣下去,就组成了一个链表。链表的第一个结点也代表着这个链表的起始元素,通过这个结点的指针,可以一直访问完链表。所以,有必要定义一个头指针来指向链表的第一个元素。尾结点的指针域置为“NULL(空)”,作为链表结束的标志。常见的链表有两种结构,如图7.2所示:a1a2a3a4a1a2a3a4head(b)带头结点的单链表图7.2链表示意图^^(a)不带头结点的单链表图7.2中,符号“^”表示空指针,在C语言中用“NULL”表示空指针,这个空指针表示尾结点没有后继,链表到此结束。图中所示链表有4个结点,ai表示数据部分,可以是基本类型或构造类型的数据

5、。不带头结点的单链表头指针head直接指向链表的第一个结点,而带头结点的单链表头指针head则指向一个附加的结点,这个附加结点的指针域才指向链表的第一个结点。由于这个附加结点的存在,无论怎么操作链表,头指针的指向总是不变。此处以不带头结点的单链表为例讲解链表的基本操作。所谓单链表就是每个结点只有一个指针域。【例7-1】用链表实现通信录的管理。【分析】通信录中每个联系人的信息,一般应该包括姓名、电话号码和其他一些信息。为了方便查找和更新,经常要对通信录中添加新的记录、删除无效记录和调整记录位置,用链表来实现通信录的管理比较方便。链表的每个结点的数据域对应着一

6、条通信录所包含的数据信息,用一个结构体变量来表示,例子中包含联系人的姓名和电话。为了把两个结点的连接起来,结点中还应该有一个指向下一结点的指针域,这个指针的类型为结点的结构数据类型。在创建的过程中,添加一个结点的时候要知道之前添加的那个结点,定义一个指针q来指向之前添加的那个结点,即链表的最后一个结点,定义指针变量p指向当前结点,q指针所指结点为当前结点的前驱结点,p就叫做q的后继。当我们添加完成一个结点后,再将指针q指向当前链表的最后一个结点,为添加下一个结点作准备。从head开始,通过各结点指针能够访问到链表的每一个元素。链表的创建过程如图7.3所示:

7、图7.3链表的创建过程q…headNULLa1headqheada1a2qNULLheada1a2a3…ana2pNewa3pNew如图7.3所示,链表创建的过程就像在穿一条珠链:有一根线头能将整串珠链提起,称头指针head。刚开始时没有任何珠子,只有一根空线头head;第一颗珠子(头结点)接到head上,而第一颗珠子后有一根线头(指针域next)可以接下一颗珠子;每次总把新加入的珠子pNew(结点)接到最后一颗珠子后的线头上。为了能快速找到最后一颗珠子,令指针q指向每次最新接入的珠子,则新珠子接到q的线头上:q->next=pNew。当不再需要接入其他珠

8、子时,把最后一一颗珠子后的线头q->next打上结:q->next

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。