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

单 位: 计算机051班 学 号: 课程设计 （计算机科学与技术专业） 数据结构课程设计 姓 名： 专 业： 计算机科学与技术 指导教师： 二○○八年六月 一、课程设计 设计题目：单链表两个集合相加减的算法 为了实现单链表的几种运算功能，需要用到多张函数程序，例如：建表--readdata(pointer *head)，单链表元素排序--sort(pointer *head)，输出单链表L --disp(pointer *head)，求两有序集合的并。两个集合A和B，它们的并集为集合C--bing(pointer *head1,pointer *head2, pointer *head3)，求两有序集合的交。两个集合A和B，它们的交集为集合C-- jiao(pointer *head1,pointer *head2, pointer *head3)，求两有序集合的差。两个集合A和B，它们的差集为集合C-- cha(pointer *head1,pointer *head2, pointer *head3)，首先建立单链表，再调用函数sort()构成有序单链表，最后求用有序单链表表示的两个集合的相关运算-- main()。首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 一、主控菜单设计 1）菜单内容 程序运行后，给出7个菜单项的内容和输入提示： 集合1为 集合2为 集合1与集合2的并为 集合1与集合2的交为 集合1与集合2的差为 集合2与集合1的差为 退出管理系统 二、链表介绍 1）建立单向链表 在函数中首先为Head申请了—个所指向的结点，该结点称为链表的首结点。开始链表的头指针和尾指针都指向头结点，以后每输入一个数则申请一个结点，将输入的数放到结点的信息域后。输入结束后，置链表最后一个结点的指针域为空，返回链表头指针。单向链表中插入结点在单向链表中插入一个结点要引起插入位置前面结点的指针的变化，在插入一个结点时首先要由（new pointer)向系统申请一个存储pointer类型变量的空间，并将该空间的首地址赋给指向新结点的指针head，在为该新结点的信息域赋值后，先要将该结点插入位置后面一个结点的指针赋给该结点的指针域，然后才能将指向该结点的指针赋给其前一个结点的指针域，这样来完成插入过程。在单向链表中删除个结点同样要引起删除结点的前面结点的指针的变化。 2）编历链表 由于链表是一个动态的数据结构，链表的各个结点由指针链接在起，访问链表元素时通过每个链表结点的指针逐个找到该结点的下一个结点，—直找到链表尾，链表的最后一个结点的指针为空。 3）双向链表 每个结点中只包括一个指向下个结点的指针域，这种链表称为单向链表。如果要在单向链表一个指针所指的当前位置插入一个新结点，就必须从链表头指针开始逐个遍历直到当前指针所指结点的前一结点，修改这个结点的指针。双向链表的每个结点中包括两个指针域，分别指向该结点的前一个结点和后一个结点。在双向链表中由任何一个结点都很容易找到其前面的结点和后面的结点，而不需要在上述的插入(及删除)操作中由头结点开始寻找。 4）本程序中包含如下函数 readdata(pointer *head):建表 sort(pointer *head) : 单链表元素排序 disp(pointer *head) :输出单链表L bing(pointer *head1,pointer *head2, pointer *head3):求两有序集合的并。两个集合1和2，它们的并集为集合3 jiao(pointer *head1,pointer *head2, pointer *head3):求两有序集合的交。两个集合1和2，它们的交集为集合3 cha(pointer *head1,pointer *head2, pointer *head3):求两有序集合的差。两个集合1和2，它们的差集为集合3 main():首先建立单链表，再调用函数sort()构成有序单链表，最后求用有序单链表表示的两个集合的相关运算 5）建立链表 要求建立一个带头结点的单链表。我们知道建立单链表有两种方法，一种称之为头插法，另一种称为尾插法。头插法是每次将新插入的结点插入在链表的表头，而尾插法是将新插入的结点插入在链表的表尾。在这里只介绍用尾插法建立链表的算法设计思想及具体算法实现，头插法留给读者自己去做。 要建立链表，首先要生成结点，因此，尾插法建立链表的算法描述如下： 使链表的头尾指针head, rear指向新生成的头结点（也是尾结点）； 置结束标志0（假）； While (结束标志不为真)