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

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

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

3、的并为4. 集合1与集合2的交为5. 集合1与集合2的差为6. 集合2与集合1的差为0 退出管理系统二、链表介绍1）建立单向链表在函数中首先为Head申请了个所指向的结点，该结点称为链表的首结点。开始链表的头指针和尾指针都指向头结点，以后每输入一个数则申请一个结点，将输入的数放到结点的信息域后。输入结束后，置链表最后一个结点的指针域为空，返回链表头指针。单向链表中插入结点在单向链表中插入一个结点要引起插入位置前面结点的指针的变化，在插入一个结点时首先要由（new pointer)向系统申请一个存储pointer类型变量的空间，并将该空间的首地址赋给指向新结点的指针head，在为该新结点的信息域

4、赋值后，先要将该结点插入位置后面一个结点的指针赋给该结点的指针域，然后才能将指向该结点的指针赋给其前一个结点的指针域，这样来完成插入过程。在单向链表中删除个结点同样要引起删除结点的前面结点的指针的变化。2）编历链表由于链表是一个动态的数据结构，链表的各个结点由指针链接在起，访问链表元素时通过每个链表结点的指针逐个找到该结点的下一个结点，直找到链表尾，链表的最后一个结点的指针为空。3）双向链表每个结点中只包括一个指向下个结点的指针域，这种链表称为单向链表。如果要在单向链表一个指针所指的当前位置插入一个新结点，就必须从链表头指针开始逐个遍历直到当前指针所指结点的前一结点，修改这个结点的指针。双向链

5、表的每个结点中包括两个指针域，分别指向该结点的前一个结点和后一个结点。在双向链表中由任何一个结点都很容易找到其前面的结点和后面的结点，而不需要在上述的插入(及删除)操作中由头结点开始寻找。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 *

6、head2, pointer *head3):求两有序集合的交。两个集合1和2，它们的交集为集合3 cha(pointer *head1,pointer *head2, pointer *head3):求两有序集合的差。两个集合1和2，它们的差集为集合3 main():首先建立单链表，再调用函数sort()构成有序单链表，最后求用有序单链表表示的两个集合的相关运算5）建立链表 要求建立一个带头结点的单链表。我们知道建立单链表有两种方法，一种称之为头插法，另一种称为尾插法。头插法是每次将新插入的结点插入在链表的表头，而尾插法是将新插入的结点插入在链表的表尾。在这里只介绍用尾插法建立链表的算法设计

7、思想及具体算法实现，头插法留给读者自己去做。要建立链表，首先要生成结点，因此，尾插法建立链表的算法描述如下：（1） 使链表的头尾指针head, rear指向新生成的头结点（也是尾结点）；（2） 置结束标志0（假）；（3） While (结束标志不为真) P指向新生成的结点； 读入一个通讯者数据至新结点的数据域； 将新结点链到尾结点之后； 使尾结点指向新结点； 提示：是否结束建表，读入一个结束标志； （4） 尾结点指针域置空值NULL。6）链表结点的插入 链表结点的插入，是要求将一个通讯者数据结点按其编号的次序插入有序通讯录表的相应位置，以保持通讯录表的有序性。插入结点的基本思想是：使用两个指针

8、变量p1和p2分别指向当前刚访问过的结点和下一个待访问的结点，循环顺序查找链表，寻找插入结点的位置，其中p1指向待插入位置的前一个结点。插入操作是非常简单的。其实现算法描述如下：（1）用p1指向原链表头结点，p2指向链表的第一个结点；（2） While (p2 != NULL && strcmp(p2->data.num, p->data.num) < 0) P1 = p2; /p1指向刚访问过的结点 P2 = p2->next; /p2指向表的下一个结点（3） 插入新结点7）链表的输出链表的输出相对来说比较简单，只要将表头指针赋给一个指针变量p,然后p

9、向后扫描，直至表尾，p为空为止三 程序代码及功能实现 程序代码如下： */#include<stdio.h> #include<stdlib.h> typedef struct pointer char dat; struct pointer *link; pointer; void readdata(pointer *head) /读集合 pointer *p; char tmp; printf("请输入任意字符串n"); scanf("%c",&tmp); while(tmp!='n') p=(poin

10、ter *)malloc(sizeof(struct pointer); p->dat=tmp; p->link=head->link; head->link=p; scanf("%c",&tmp); void sort(pointer *head)/单链表排序 pointer *p=head->link,*q,*r; if(p!=NULL) r=p->link; p->link=NULL; p=r; while(p!=NULL) r=p->link; q=head; while(q->link!=NULL&am

11、p;&q->link->dat<p->dat) q=q->link; /在有序表中找插入*p的前驱结点*q p->link=q->link; /将*p插到*q之后 q->link=p; p=r; void disp(pointer *head) /显示集合数据 pointer *p; p=head->link; while(p!=NULL) printf("%c ",p->dat); p=p->link; printf("n"); void bing(pointer *head1,

12、pointer *head2, pointer *head3) /计算集合1与集合2的并 pointer *p1,*p2,*p3; p1=head1->link; while(p1!=NULL) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p1->dat; p3->link=head3->link; head3->link=p3; p1=p1->link; p2=head2->link; while(p2!=NULL) p1=head1->link; while(p1!=NULL

13、)&&(p1->dat!=p2->dat) p1=p1->link; if(p1=NULL) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p2->dat; p3->link=head3->link; head3->link=p3; p2=p2->link; void jiao(pointer *head1,pointer *head2, pointer *head3) /计算集合1与集合2的交 pointer *p1,*p2,*p3; p1=head1->l

14、ink; while(p1!=NULL) p2=head2->link; while(p2!=NULL)&&(p2->dat!=p1->dat) p2=p2->link; if(p2!=NULL)&&(p2->dat=p1->dat) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p1->dat; p3->link=head3->link; head3->link=p3; p1=p1->link; void cha(pointer

15、*head1,pointer *head2, pointer *head3) /计算集合1与集合2的差 pointer *p1,*p2,*p3; p1=head1->link; while(p1!=NULL) p2=head2->link; while(p2!=NULL)&&(p2->dat!=p1->dat) p2=p2->link; if(p2=NULL) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p1->dat; p3->link=head3->link;

16、 head3->link=p3; p1=p1->link; int menu_select( ) int sn; printf(" 集合运算 n"); printf("=n"); printf(" 1. 集合1为 n"); printf(" 2. 集合2为 n"); printf(" 3. 集合1与集合2的并为 n"); printf(" 4. 集合1与集合2的交为 n"); printf(" 5. 集合1与集合2的差为 n"); printf

17、(" 6. 集合2与集合1的差为 n"); printf(" 0. 退出管理系统 n"); printf("=n"); printf(" 请选择 0-6 ： n"); for ( ; ;) scanf( "%d", &sn);if (sn < 0 | sn > 6) printf("nt 输入错误， 重选0-8 : ");else break; return sn;界面如下：void readdata(pointer *head);void sort(po

18、inter *head);void disp(pointer *head);void bing(pointer *head1,pointer *head2, pointer *head3);void jiao(pointer *head1,pointer *head2, pointer *head3);void cha(pointer *head1,pointer *head2, pointer *head3);int menu_select( );void main() pointer *head1,*head2,*head3; head1=(pointer *)malloc(sizeof(

19、struct pointer); head1->link=NULL; head2=(pointer *)malloc(sizeof(struct pointer); head2->link=NULL; head3=(pointer *)malloc(sizeof(struct pointer); head3->link=NULL;printf("* 输入集合1 *n");readdata(head1);printf("*n");printf("输入集合2：n"); printf("*n");rea

20、ddata(head2); for ( ; ;) switch (menu_select( ) ) case 1: printf("*n"); printf("集合1为：n"); printf("*n"); sort(head1); disp(head1); break; case 2: printf("*n"); printf("集合2为：n"); printf("*n"); sort(head2); disp(head2); break; case 3: printf("*n"); printf("集合1与集合2的并为: