数据结构课程设计.doc

数据结构课程设计内容：设计用单链表的存储形式解决两个集合相加减的算法要求：1. 有设计分析；2. 有源代码；3. 能够正确运行。1.课程设计思路通过对带头结点单链表的存储方式的研究，在进一步熟悉和掌握单链表的初始化、建立、插入、删除、更改、查询、输出等运算之后，根据本题的实际情况，特设计出如下算法对功能进行实现。1.1链式存储定义现假设链表结点仅含有一个数据域和一个指针域。数据域是为了描述集合的相关信息，定义集合的结点类型：typedef struct node /结点类型定义 int data; /结点数据域 struct node *next; /结点指针域ListNode;在此，我们将新的结点中数据域的数据类型定义为整型int。同时这个定义也是程序中链式存储结构的定义。typedef ListNode *LinkList; ListNode *p; /定义一个指向结点的指针变量 LinkList head; /定义指向单链表的头指针这里的LinkList 和ListNode* 是不同名字的同一指针类型，取不同的名是为了在概念上更明确。特别值得注意的是指针变量和指针指向的变量者两个不同的概念。2.功能定义为了实现集合运算管理的几种操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。2.1 主控菜单设计要求2.1.1 菜单内容程序运行后，给出6个菜单项的内容和输入提示：1集合A链表的建立2集合B链表的建立3集合链表的查询4两集合的差集5两集合的并集0.退出管理系统请选择 052.1.2 设计要求使用数字05来选择菜单项，其他输入则不起作用。2.2 设计实例首先编写一个主控菜单驱动程序，输入05以进入相应选择项。假设输入选择用变量sn存储，它作为menu_select函数的返回值提供给switch语句。使用for循环实现重复选择，并在函数main()中实现。void main() /主程序LinkList Heada,Headb,Headc,Headd;for ( ; ;) switch (menu_select( ) ) case 1: printf(*n); printf(* 集合A的建立 *n); printf(*n); Heada=CreateList(); printf(集合A建立完成n); printf(n); printf(n); printf(n); break; case 2: printf(*n); printf(* 集合B的建立 *n); printf(*n); Headb=CreateList(); printf(集合B建立完成n); printf(n); printf(n); printf(n); break; case 3: printf(*n); printf(* 查询集合 *n); printf(*n); printf(您输入的集合A是：n); Printf(Heada); printf(n); printf(您输入的集合B是：n); Printf(Headb); printf(n); printf(n); printf(n); break; case 4: printf(*n); printf(* 两集合的差集 *n); printf(*n); Headc=Difference(Heada,Headb); printf(两集合的差集是：n); Printf(Headc); printf(n); printf(n); printf(n); break; case 5: printf(*n); printf(* 两集合的并集 *n); printf(*n); Headd=Union(Heada,Headb); printf(两集合的并集是：n); Printf(Headd); printf(n); printf(n); printf(n); break; case 0 : printf(*t 再见！*n); return; 实际使用时，只要选择大于5或小于0的值，程序才能结束运行，这就要使用循环控制。这里使用for循环循环语句实现菜单的循环选择，为了结束程序的运行，使用了ruturn语句，也可以使用exit(0)语句。2.3 得到sn的合理值如前所示，应该设计一个函数用来输出提示信息和处理输入，这个函数应该返回一个数值sn，以便供给switch语句使用，假设函数名为menu_select，设计的程序如下：int menu_select( ) /主控菜单int sn; printf( 计算两集合的差集与并集 n); printf(=n); printf( 1. 集合A的建立 n); printf( 2. 集合B的建立 n); printf( 3. 查询集合 n); printf( 4. 两集合差集 n); printf( 5. 两集合并集 n); printf( 0. 退出管理系统 n); printf(=n); printf( 请选择 0-5 ： n); for ( ; ;)scanf( %d, &sn); if (sn 5)printf(nt 输入错误， 重选0-5 : ); else break; return sn;对于sn输入值，在switch中case语句对应数字15，对于不符合要求的输入，提示输入错并要求重新输入。将该函数与主函数合在一起，编译运行程序，即可检查并验证菜单选择是否正确。2.4功能函数设计在此，我们根据题目所述实际情况，将该程序中链表存储的功能分为链表的建立、链表的输出、链表差集计算、链表并集计算，接下来将分别进行介绍。2.4.1链表的建立要建立链表，首先要生成结点，因此，尾插法建立链表的算法描述如下：（1）使链表的头尾指针head, rear指向新生成的头结点（也是尾结点）；（2）置结束标志0（假）；（3）While (结束标志不为真) P指向新生成的结点； 读入一个通讯者数据至新结点的数据域； 将新结点链到尾结点之后； 使尾结点指向新结点； 提示：是否结束建表，读入一个结束标志； （4）尾结点指针域置空值NULL。具体算法实现如下：LinkList CreateList(void)/尾插法建立带头结点的通讯录链表算法 LinkList head = (ListNode * )malloc(sizeof(ListNode);/申请头结点 ListNode *p, *rear; int x; rear = head; /尾指针指向头结点 printf(请依次输入集合的元素（0为结束标志！）:n);scanf(%d,&x);while (x!= 0) p = (ListNode *)malloc(sizeof(ListNode);/申请新结点 p-data=x; p-next=NULL; rear-next=p; rear=p; scanf(%d,&x); return head;2.4.2 计算两集合的差集差集的计算是求集合A中有而集合B中没有的一个元素的集合，那么用两个for循环进行嵌套，将集合A链表和集合B链表从头到尾扫描一次，如果数据域元素不同则放入到新的集合C链表中，如果数据域元素相同，则跳出循环执行下一次循环。具体算法实现如下：LinkList Difference(LinkList heada,LinkList headb) /两集合差集LinkList headc;ListNode *pa,*pb,*pc,*temp;pa=heada-next;headc=(ListNode *)malloc(sizeof(ListNode);headc-next=NULL;pc=headc;for(pa;pa!=NULL;pa=pa-next) /通过双重for循环依次扫描A、B两个集合链表，数据相同则跳出循环，不同则输出，找出差集。for(pb=headb-next;pb!=NULL;pb=pb-next)if(pb-data!=pa-data & pb-next=NULL)temp=(ListNode *)malloc(sizeof(ListNode); /temp为一个临时变量temp-data=pa-data;temp-next=NULL;pc-next=temp;pc=temp;if(pb-data=pa-data)break;return headc;2.4.3 计算两集合的并集同计算两集合的差集相同的思路，两集合的并集是求集合A和集合B中所有的不重复的元素的一个数据集合，那么则可以在差集的基础上添加上求差集时被差掉的那个数据集合，组合起来的便是两个集合的并集。同样用两个for循环先求出差集，然后将被差的集合B中的元素组合在一起即可。具体算法实现如下：LinkList Union(LinkList heada,LinkList headb) /两集合并集LinkList headd;ListNode *pa,*pb,*pd,*temp,*temp1;pa=heada-next;headd=(ListNode *)malloc(sizeof(ListNode);headd-next=NULL;pd=headd;for(pa;pa!=NULL;pa=pa-next) /同差集算法for(pb=headb-next;pb!=NULL;pb=pb-next)if(pb-data!=pa-data & pb-next=NULL)temp=(ListNode *)malloc(sizeof(ListNode);temp-data=pa-data;temp-next=NULL;pd-next=temp;pd=temp;if(pb-data=pa-data)break;pb=headb-next; /在差集基础上，添加上B集合，则得到A、B集合的并集 dotemp1=(ListNode *)malloc(sizeof(ListNode);temp1-data=pb-data;temp1-next=NULL;pd-next=temp1;pd=temp1;pb=pb-next;while(pb!=NULL);return headd;2.4.4 集合的输出集合链表的输出相对来说比较简单，只要将表头指针赋给一个指针变量p,然后p向后扫描，直至表尾，p为空为止。因此，其输出链表算法如下：void Printf(LinkList headc) /集合输出ListNode *pc;pc=headc-next;while (pc!=NULL) /从头依次访问集合链表然后输出printf(%dt,pc-data);pc=pc-next;3.程序界面预览3.1 界面预览3.2集合A的建立3.3 集合B的建立3.4 查询集合3.5 两集合差集3.6 两集合并集3.7 退出系统4.完整的程序清单#include #include #include typedef struct node /结点类型定义 int data; /结点数据域 struct node *next; /结点指针域ListNode; typedef ListNode *LinkList; ListNode *p; /定义一个指向结点的指针变量 LinkList head; /定义指向单链表的头指针LinkList CreateList(void)/尾插法建立带头结点的通讯录链表算法 LinkList head = (ListNode * )malloc(sizeof(ListNode);/申请头结点 ListNode *p, *rear; int x; rear = head; /尾指针指向头结点 printf(请依次输入集合的元素（0为结束标志！）:n); scanf(%d,&x); while (x!= 0) p = (ListNode *)malloc(sizeof(ListNode);/申请新结点 p-data=x; p-next=NULL; rear-next=p; rear=p; scanf(%d,&x); return head;LinkList Difference(LinkList heada,LinkList headb) /两集合差集LinkList headc;ListNode *pa,*pb,*pc,*temp;pa=heada-next;headc=(ListNode *)malloc(sizeof(ListNode);headc-next=NULL;pc=headc;for(pa;pa!=NULL;pa=pa-next) /通过双重for循环依次扫描A、B两个集合链表，数据相同则跳出循环，不同则输出，找出差集。for(pb=headb-next;pb!=NULL;pb=pb-next)if(pb-data!=pa-data & pb-next=NULL)temp=(ListNode *)malloc(sizeof(ListNode);temp-data=pa-data;temp-next=NULL;pc-next=temp;pc=temp;if(pb-data=pa-data)break;return headc;LinkList Union(LinkList heada,LinkList headb) /两集合并集LinkList headd;ListNode *pa,*pb,*pd,*temp,*temp1;pa=heada-next;headd=(ListNode *)malloc(sizeof(ListNode);headd-next=NULL;pd=headd;for(pa;pa!=NULL;pa=pa-next) /同差集算法for(pb=headb-next;pb!=NULL;pb=pb-next)if(pb-data!=pa-data & pb-next=NULL)temp=(ListNode *)malloc(sizeof(ListNode);temp-data=pa-data;temp-next=NULL;pd-next=temp;pd=temp;if(pb-data=pa-data)break;pb=headb-next; /在差集基础上，添加上B集合，则得到A、B集合的并集 dotemp1=(ListNode *)malloc(sizeof(ListNode);temp1-data=pb-data;temp1-next=NULL;pd-next=temp1;pd=temp1;pb=pb-next;while(pb!=NULL);return headd;void Printf(LinkList headc) /集合输出ListNode *pc;pc=headc-next;while (pc!=NULL) /从头依次访问集合链表然后输出printf(%dt,pc-data);pc=pc-next;int menu_select( ) /主控菜单 int sn; printf( 计算两集合的差集与并集 n); printf(=n); printf( 1. 集合A的建立 n); printf( 2. 集合B的建立 n); printf( 3. 查询集合 n); printf( 4. 两集合差集 n); printf( 5. 两集合并集 n); printf( 0. 退出管理系统 n); printf(=n); printf( 请选择 0-5 ： n); for ( ; ;)scanf( %d, &sn); if (sn 5) printf(nt 输入错误， 重选0-5 : ); else break; return sn;void main() /主程序LinkList Heada,Headb,Headc,Headd;for ( ; ;) switch (menu_select( ) ) case 1: printf(*n); printf(* 集合A的建立 *n); printf(*n);