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

《《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