数据结构课程设计--单链表两个集合相加减的算法

《数据结构课程设计--单链表两个集合相加减的算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位:计算机051班学号:课程设计（计算机科学与技术专业）数据结构课程设计姓名：专业：计算机科学与技术指导教师：二○○八年六月一、课程设计设计题目：单链表两个集合相加减的算法为了实现单链表的几种运算功能，需要用到多张函数程序，例如：建表--readdata(pointer*head)，单链表元素排序--sort(pointer*head)，输出单链表L--disp(pointer*head)，求两有序集合的并。两个集合A和B，它们的并集为集合C--bing(pointer*head1,pointer*head2,pointe

2、r*head3)，求两有序集合的交。两个集合A和B，它们的交集为集合C--jiao(pointer*head1,pointer*head2,pointer*head3)，求两有序集合的差。两个集合A和B，它们的差集为集合C--cha(pointer*head1,pointer*head2,pointer*head3)，首先建立单链表，再调用函数sort()构成有序单链表，最后求用有序单链表表示的两个集合的相关运算--main()。首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。一、主控菜单设计1）

3、菜单内容程序运行后，给出7个菜单项的内容和输入提示：1.集合1为2.集合2为3.集合1与集合2的并为4.集合1与集合2的交为5.集合1与集合2的差为6.集合2与集合1的差为0．退出管理系统二、链表介绍1）建立单向链表在函数中首先为Head申请了—个所指向的结点，该结点称为链表的首结点。开始链表的头指针和尾指针都指向头结点，以后每输入一个数则申请一个结点，将输入的数放到结点的信息域后。输入结束后，置链表最后一个结点的指针域为空，返回链表头指针。单向链表中插入结点在单向链表中插入一个结点要引起插入位置前面结点的指针的变化，在插入

4、一个结点时首先要由（newpointer)向系统申请一个存储pointer类型变量的空间，并将该空间的首地址赋给指向新结点的指针head，在为该新结点的信息域赋值后，先要将该结点插入位置后面一个结点的指针赋给该结点的指针域，然后才能将指向该结点的指针赋给其前一个结点的指针域，这样来完成插入过程。在单向链表中删除个结点同样要引起删除结点的前面结点的指针的变化。2）编历链表由于链表是一个动态的数据结构，链表的各个结点由指针链接在起，访问链表元素时通过每个链表结点的指针逐个找到该结点的下一个结点，—直找到链表尾，链表的最后一个结点

5、的指针为空。3）双向链表每个结点中只包括一个指向下个结点的指针域，这种链表称为单向链表。如果要在单向链表一个指针所指的当前位置插入一个新结点，就必须从链表头指针开始逐个遍历直到当前指针所指结点的前一结点，修改这个结点的指针。双向链表的每个结点中包括两个指针域，分别指向该结点的前一个结点和后一个结点。在双向链表中由任何一个结点都很容易找到其前面的结点和后面的结点，而不需要在上述的插入(及删除)操作中由头结点开始寻找。4）本程序中包含如下函数readdata(pointer*head):建表sort(pointer*head):

6、单链表元素排序disp(pointer*head):输出单链表Lbing(pointer*head1,pointer*head2,pointer*head3):求两有序集合的并。两个集合1和2，它们的并集为集合3jiao(pointer*head1,pointer*head2,pointer*head3):求两有序集合的交。两个集合1和2，它们的交集为集合3cha(pointer*head1,pointer*head2,pointer*head3):求两有序集合的差。两个集合1和2，它们的差集为集合3main():首先建立单

7、链表，再调用函数sort()构成有序单链表，最后求用有序单链表表示的两个集合的相关运算5）建立链表要求建立一个带头结点的单链表。我们知道建立单链表有两种方法，一种称之为头插法，另一种称为尾插法。头插法是每次将新插入的结点插入在链表的表头，而尾插法是将新插入的结点插入在链表的表尾。在这里只介绍用尾插法建立链表的算法设计思想及具体算法实现，头插法留给读者自己去做。要建立链表，首先要生成结点，因此，尾插法建立链表的算法描述如下：（1）使链表的头尾指针head,rear指向新生成的头结点（也是尾结点）；（2）置结束标志0（假）；（3

8、）While(结束标志不为真){P指向新生成的结点；读入一个通讯者数据至新结点的数据域；将新结点链到尾结点之后；使尾结点指向新结点；提示：是否结束建表，读入一个结束标志；}（1）尾结点指针域置空值NULL。6）链表结点的插入链表结点的插入，是要求将一个通讯者数据结点按其编号的次序插入有序通