数据结构课程设计报告集合运算.doc

数据结构课程设计报告设计题目： 集合运算专 业 班 级 学 生 学 号 指导教师 2011年5月目 录一.设计题目2（一）.题目：集合运算2（二）.问题描述和分析2二.设计内容3(一). 数据结构设计3(二). 算法设计3三.概要设计4(一).程序结构图4（二）.具体程序设计4四.算法分析5源代码5五.结果分析16六.心得体会21七.参考文献22一.设计题目（一）.题目：集合运算功能：使用链表来表示集合，完成集合的合并，求交集等操作。主要包含以下内容：1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2完成最低要求； 3进一步要求：要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。（二）.问题描述和分析 本课程设计中，链表长度不能超过100，集合输入的形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤。输出的运算结果字符串中将不含重复字符或非法字符。 问题描述： 有两个集合A、B，要求它的交集、并集。用两个链表L1、L2存储集合A、B。描 述该问题的存储结构，算法，并通过编写程序来实现。 问题分析： 1. 定义一个链表来存储集合元素； 2. 链表L包括数据域和指针域，数据域中存储集合元素，指针域中存储下一个集合元素的位置； 3. 创建若干个基本函数，通过函数调用对链表进行作，实现集合的交、并运算。 二.设计内容(一). 数据结构设计 1. 数据结构设计考虑 创建三个带头结点的单链表，用来存储两个集合中的元素和最终的结果，为实现集合的交，并运算功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。 2. 逻辑结构存储结构 逻辑结构： 创造一个带结点的单链表包括（头结点L，结点若干，尾结点） 单链表中每个结点包括（*next 表示指针data表示域） (二). 算法设计 程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤输入中的非法字符）和运算结果显示在其后。 程序执行的命令包括： a) 构造集合A； b) 构造集合B； c) 求交集； d) 求并集； e) 结束。 “构造集合A”和“构造集合B”时，需以字符串的形式键入集合元素。三.概要设计(一).程序结构图Main函数InterSect交函数Union并函数Sort链表排序函数CreateList尾插法建表DispList输出函数（二）.具体程序设计1.定义链表 typedef int ElemType；typedef struct Lnode2.返回链表长度3.返回指定节点的值4.定位制定值的节点的值5.显示链表 void display(struct Lnode *L)6.创建链表，并设置链表为空 void creat(struct Lnode *L)7.向链表中插入元素 void insert(struct Lnode *L,int n,ElemType x)8.插在第n个节点的前面9.删除指定位置的节点10.初始化链表 void init(struct Lnode *L,int len)11.复制链表L1到L2 void copy(struct Lnode *L1,struct Lnode *L2 )12.求交集 void intersection(struct Lnode *L1,struct Lnode *L2,struct Lnode *L3)13.求并集unionset(struct Lnode *L1,struct Lnode *L2,struct Lnode *L3)14.把L1复制到L3，然后比较L2和L3，得到L2与L3中没有的元素，并插入15.插在排序的位置上insert(&*L3,k,t2->data); 16.插在链尾四.算法分析源代码如下：#include <stdio.h>#include <stdlib.h>#include <alloc.h>#define null 0#define M 100typedef int ElemType;/*定义链表*/typedef struct Lnode    ElemType data;    struct Lnode *next;int lenth(struct Lnode *L)    int n=0;    struct Lnode *t;    t=*L;    while(t!=null)                   n+;           t=t->next;            return n;ElemType get(struct Lnode *L,int n)      int i=1;      struct Lnode *t;      t=*L; while (i<n&&t!=null)     t=t->next;    i+;    if(t!=null)             return(t->data);        else          printf("The %dth Lnode haven't find !n",n);      int locate(struct Lnode *L,ElemType x )      int n=1;  struct Lnode *t;      t=*L; while (t!=null&&t->data!=x)     t=t->next;    n+;    if(t=null)          return(0);        else          return(n);      void display(struct Lnode *L)/*显示链表*/   struct Lnode *t;    t=*L;    if(t=null)            printf("The link is null!");        else      do                      printf("%d>>",t->data);            t=t->next;    while(t!=null);        printf("n");void creat(struct Lnode *L)/*创建链表*/    *L=null;void insert(struct Lnode *L,int n,ElemType x)/*向链表中插入元素*/    struct Lnode *t1,*t2;    int j=1;    t1=(struct Lnode *)malloc(sizeof(struct Lnode);    t1->data=x;    t2=*L;    if(n=1)           t1->next=t2;       *L=t1;        else             while(j<n-1&&t2->next!=null)                           t2=t2->next;               j+;                    if(j=n-1)                            t1->next=t2->next;                t2->next=t1;                    else                            printf("Insert error!");                void delete(struct Lnode *L,int n)      int i=1;  struct Lnode *t1,*t2;      t1=*L;  if(n=1)       t2=t1;    *L=t1->next;     else       while(i<n-1&&t1->next!=null)           t1=t1->next;       i+;           if(t1->next!=null&&i=n-1)               t2=t1->next;        t1->next=t2->next;             else                      printf("Delete error!n");                   if(t2=null)       free(t2);      void init(struct Lnode *L,int len)/*初始化链表*/    int dM,i,j,k,ti;    struct Lnode *t;input:    for(i=1;i<=len;i+)         scanf("%d",&di);        for(j=1;j<=len;j+)      for(k=j+1;k<=len;k+)                 if(dj>dk)                          ti=dj;              dj=dk;              dk=ti;                        for(i=1;i<len;i+)                if(di=di+1)                     printf("Don't allow the same data! Please reinput!");           goto input;                     creat(&*L);    for(i=1;i<=len;i+)                insert(&*L,i,di);           printf("The data of the linktable is:  ");    display(&*L);    void copy(struct Lnode *L1,struct Lnode *L2 )/*复制链表L1到L2*/  int i,len;  ElemType t;  len=lenth(&*L1);  creat(&*L2);    for(i=1;i<=len;i+)                t=get(&*L1,i);         insert(&*L2,i,t);       void intersection(struct Lnode *L1,struct Lnode *L2,struct Lnode *L3)/*求交集*/        int i,j,k=1;     struct Lnode *t1,*t2;     t1=*L1;     t2=*L2;     creat(&*L3);     for(i=1;i<=lenth(&*L1);i+)             for(j=1;j<=lenth(&*L2);j+)                  if(t1->data=t2->data)                          insert(&*L3,k,t1->data);              k+;                      t2=t2->next;              t1=t1->next;      t2=*L2;     unionset(struct Lnode *L1,struct Lnode *L2,struct Lnode *L3)/*求并集*/  int i,j,k;  struct Lnode *tt,*t2,*t3;  creat(&*L3);  copy(&*L1,&*L3);  t2=*L2;  t3=*L3;  for(i=1;i<=lenth(&*L2);i+)             k=1;       for(j=1;j<=lenth(&*L3);j+)                  if(t2->data=t3->data)                        k=0;             break;                     else if(t2->data<t3->data)                        break;                     else if(t2->data>t3->data)                        k+;             if(k<=lenth(&*L3)                           t3=t3->next;                                       if(k>0&&k<=lenth(&*L3)                insert(&*L3,k,t2->data);              else if(k>lenth(&*L3)                tt=(struct Lnode *)malloc(sizeof(struct Lnode);         tt->data=t2->data;         tt->next=null;         t3->next=tt;              t2=t2->next;       t3=*L3;      void diffrenceset(struct Lnode *L1,struct Lnode *L2,struct Lnode *L3)  int i,t,n;  creat(&*L3);  copy(&*L1,&*L3);  for(i=1;i<=lenth(&*L2);i+)        t=get(&*L2,i);     n=locate(&*L3,t);     if(n)           delete(&*L3,n);        main() int len1,len2;char r;static struct Lnode *head1,*head2,*head3,*head4;printf("/*the begin*/n");printf("Please input the lenth of the first linktable! ");scanf("%d",&len1);printf("The lenth of the first linktable is %d,please input %d datas! ",len1,len1);init(&head1,len1);printf("/-/n");printf("Please input the lenth of the second linktable! ");scanf("%d",&len2);printf("The lenth of the second linktable is %d,please input %d datas! ",len2,len2);init(&head2,len2);printf("nn/-/n");intersection(&head1,&head2,&head3);printf("The intersection of two linktable: ");display(&head3);unionset(&head1,&head2,&head4);printf("The union set of two linktable: ");display(&head4);printf("/*the end*/n");五.结果分析1.在turboc2.01环境中输入源代码2.按Atl+F9编译文件得到以下结果，发现无错误。3.由提示按任意键，后按Ctrl+F9编译运行，得到以下结果。给第一个链表的长度设为5后按Enter程序开始（the begin）4.输入以下数字：10 25 78 99 1000 5.输完数字后按Enter,得到以下结果，第一个链表输入完毕。6.由提示任意给定第二个链表长度为17。7.屏幕提示链表长度已定，并要求输入17个数字。8.输入以下17个数字：1 2 3 4 5 6 7 8 9 28 78 86 99 100 120 150 100009.按Enter屏幕显示如下10.按Alt+F5查看输出结果得出交集：78 99并集：1 2 3 4 5 6 7 8 9 10 25 28 78 86 99 100 120 150 1000 10000程序结束(the end)六.心得体会通过实践才发现C语言程序设计的掌握直接关系到数据结构上机实验效果。C语言程序设计是编程的基础。尤其，指针、结构体和函数等知识点是“程序设计基础与C语言”中的学习难点，自己普遍理解不深，难以在编程中灵活应用，但这些知识点在数据结构课程中频繁应用。对这些知识点的熟练掌握是在数据结构课程中理解理论算法和完成上机实验的重要保证。为此，我在学习中注意做到以下两点：1.与“程序设计基础与C语言”知识做好课程之间的衔接，将数据结构课程中经常用到的知识点上机实践。2.在学数据结构算法之前复习C语言中的指针、结构体和函数等知识点。具体形式可以是在课堂上以程序实例的形式对这些知识点进行复习，尤其是难理解、容易混淆和犯错误的地方；适当做些涉及这些知识点的课外编程作业，通过作业发现自己存在的问题然后集体重点复习；特别是指针、结构体和函数等知识。七.参考文献1.催俊凯。计算机软件基础。机械工业出版社。2007.72.唐发根。数据结构教程（第二版）。北京航空航天大学出版社。2005.53.谭浩强。C程序设计（第三版）。清华大学出版社。20054.严蔚敏，吴伟民。数据结构（C语言版）。北京：清华大学出版社。20055.王宏生，宋继红。数据结构。北京：国防工业出版社，2006.16.李建学，李光元，吴春芳。数据结构课程设计案例精编（用C/C+描述）。北京：清华大学出版社。2007.2