实习报告集合的并、交和差运算

1、 一、需求分析 1.本演示程序中，集合的元素限制在小写字母a-z之间。集合的大小不限制，集合的输入形式为一个以“回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。 2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。 3.程序的执行命令有：1）选择操作 2）任意键清屏 4.数据测试 （1） Set1=”magazine”, Set2=paper”, Set1Set2=”aegimnprz”,Set1Set2=”ae”,Se

2、t1-Set2=”gimnz”; (2) Set1=”012oper4a6tion89”,Set2=”error data”,Set1Set2=”adeinoprt”,Set1Set2=”aeort”, Set1-Set2=”inp”.二、概要设计为实现上述功能，需要顺序表这个抽象数据类型。1.顺序表抽象数据类型定义ADT sqlist 数据对象：D=ai|aiElemset,i=1,2,3,n,n>=0 数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2, n 基本操作： InitList(&l) 操作结果：构造一个空的顺序表l。 ListLength(l

3、) 初始条件：顺序表l已存在。 操作结果：返回l中的元素个数。 ListInsert_Sq(&L, i, e) 初始条件：顺序表l已存在。 操作结果：在l中第i个元素前面插入元素e。 CreatSqList(&l, a,n) 初始条件：顺序表l已存在。 操作结果：将数组an每个元素赋给顺序表l。 GetElem(L, i, &e) 初始条件：顺序表l已存在。操作结果：返回l中第i个元素的值 LocateElem_Sq(L, e, Status (*compare)() 初始条件：顺序表l已存在。 操作结果：依次遍历l中每个元素带入函数。 ListDelete(&

4、L,i, &e) 初始条件：顺序表l已存在。 操作结果：删除顺序表中第i个元素。 Outputlist(&L)初始条件：顺序表l已存在。 操作结果：输出顺序表的每个元素值。ADT sqlist三、详细设计/ 程序的头文件#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>/ 函数返回值#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#de

5、fine OVERFLOW -2#define NULL 0#define LIST_INIT_SIZE 100 /顺序表的初始大小#define LISTINCREMENT 10 /顺序表的递增大小typedef int Status; /返回状态类型typedef char ElemType; /元素类型 typedef struct ElemType *elem; int length; int listsize; SqList; /结点类型 指针类型Status InitList(SqList &l) /初始化顺序表l.elem=(ElemType*)malloc(LIST_I

6、NIT_SIZE*sizeof(ElemType);if(!l.elem) exit(OVERFLOW);l.length=0;l.listsize=LIST_INIT_SIZE;return OK;int ListLength(SqList l) /求顺序表的长度return(l.length);Status ListInsert_Sq(SqList &L,int i, ElemType e)/在顺序表L的第i个位置前插入元素e,i的合法值为1.L.length+1 if(i<1|i>L.length+1) return ERROR; if(L.length>=L.

7、listsize) ElemType*newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; ElemType *q=&L.elemi-1, *p=&L.elemL.length-1; while(p>=q) *(p+1)=*p; -p; /插入位置后的元素右移 *q=e; +L.length; return OK;Status

8、 CreatSqList(SqList &l,ElemType a,int n) /创建顺序表int len=ListLength(l);for(int i=0;i<n;i+)if(ai>='a'&&ai<='z')ListInsert_Sq(l,+len,ai);return OK;Status GetElem(SqList L,int i,ElemType &e)/ 返回顺序表中元素 if(i<=0|i>L.length)return ERROR;elsee=*(L.elem+i-1);retur

9、n OK;Status equal(ElemType e1,ElemType e2) if(e1=e2)return TRUE; else return FALSE; int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType,ElemType) ElemType *p=L.elem; /p指向第一个元素 int i=1; /i始终为p所指向元素的位序 while(i<=L.length&&!(*compare)(*p+,e)+i; if(i<=L.length) return(i); els

10、e return 0;Status ListDelete(SqList &L,int i,ElemType &e)/在顺序表中删除第个元素，用返回其值 if(i<1|i>L.length) return ERROR;/删除位置不合理 ElemType *p=&L.elemi-1,*q=L.elem+L.length-1; e=*p; while(p<q)*p=*(p+1); +p; /删除位置后的元素左移 -L.length; return OK;void Union(SqList &La,SqList Lb)/将所有在线性表Lb中而不在La中

11、的元素插入Laint la_len , lb_len;ElemType e; la_len=ListLength(La); lb_len=ListLength(Lb); for(int i=1;i<=lb_len;+i)GetElem(Lb,i,e); if(LocateElem_Sq(La,e,equal)=0) ListInsert_Sq(La,+la_len,e);Status JiaoJi(SqList l1,SqList l2, SqList &l3) /求集合的交集int l1_len, l2_len,l3_len,i=1,j=1;ElemType e,u;l1_le

12、n=ListLength(l1);l2_len=ListLength(l2);l3_len=ListLength(l3);for(i=1;i<=l1_len;i+)GetElem(l1,i,e);for(j=l2_len;j>=1;j-)GetElem(l2,j,u);if(e=u) ListInsert_Sq(l3,+l3_len,u); break;elsecontinue;return OK;Status ChaJi(SqList &l1,SqList l2) /求顺序表的差集SqList lc;int count=0,lc_len,l1_len,l2_len;Ele

13、mType e,u,f;InitList(lc);JiaoJi(l1,l2,lc);lc_len=ListLength(lc);l1_len=ListLength(l1);l2_len=ListLength(l2);for(int i=1;i<=lc_len;i+)GetElem(lc,i,e);for(int j=1;j<=l1_len;j+) GetElem(l1,j,u);if(u=e)ListDelete(l1,j,f);return OK;void Outputlist(SqList &L)if(0=L.length)printf("空集!")

14、;else for(int i=0;i<L.length;+i) printf("%c",*(L.elem+i);/程序的主函数void main()system("title 集合的并交叉运算");for(1;)system("color a1");int c; printf("*n"); printf(" # 执行程序: 1 # 退出程序: 2n");printf("*n"); printf("请按键选择: "); scanf("%d&

15、quot;,&c); getchar();printf("n"); if(c=1)SqList l1,l2,l3,la; int n1,n2,i,j; char a130, a230; InitList(l1); InitList(l2); InitList(l3); InitList(la); printf("请输入第一个集合: "); gets(a1); n1=strlen(a1); for(i=n1-1;i>=0;i-) /从最后一个开始依次与前面的比较 重复赋值为0 for(j=0;j<i;j+) if(a1j=a1i) a1

16、i=0; CreatSqList(l1,a1,n1); la=l1; printf("请输入第二个集合: "); gets(a2); n2=strlen(a2); for(i=n2-1;i>=0;i-) /同上 for(j=0;j<i;j+) if(a1j=a1i) a1i=0; CreatSqList(l2,a2,n2); printf("集合的交集是: "); JiaoJi(l1,l2,l3); Outputlist(l3); printf("n"); printf("集合的并集是: "); Uni

17、on(l1,l2); Outputlist(l1); printf("n"); printf("集合的差集是: "); ChaJi(la,l2); Outputlist(la);printf("nn*按*任*意*键*清*屏!*"); system("pause>null"); system("cls");elseexit(0);四、调试分析 1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。 2.将数据存入数组再转入链表，可以忽略

18、输入集合的长度，设计更加巧妙，便于用户使用。 3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。五、用户手册 1.本程序的运行环境为DOS操作系统，可执行文件为：集合的并交差运算.exe 2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。 3.进入演示程序后即显示文本形式的用户界面：六、测试结果 执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2 执行命令“2”：退出程序运行魔王语言翻译实习报告题目：编制一个演示魔王语言的翻译程序班级：姓名：

19、 学号：完成日期：2010.5.27一、需求分析1. 本演示程序中，魔王语言限制在小写字母a-z之间，且必须限制在括号内以及大写字母A和B。且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。2. 魔王语言遵守如下规则： （123n）ànn-11BàtAdA Aàsae 3. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。4. 程序的执行命令有：1）选择操作 2）任意键清屏5. 数据测试 B(ehnxgz)B解释成：tsaedsaeeze

20、gexenehetsaedsae二、概要设计为实现上述功能，需要栈和队列两个抽象数据类型。1. 栈抽象数据类型定义ADT stack 数据对象：D=ai|aiElemset,i=1,2,3,n,n>=0 数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2, n 基本操作： InitStack(&s) 操作结果：构造一个空栈s。Push(&s, e)初始条件：栈s已存在。操作结果：插入元素e为新的栈顶元素。Pop(&s, &e)初始条件：栈s已存在且非空。操作结果：删除栈s的栈顶元素，并用e返回其值。StackLenth(&s)

21、初始条件：栈s已存在。操作结果：返回s的元素个数，即栈的长度。ClearStack(&s)初始条件：栈s已存在。操作结果：将s清为空栈。DestoryStack(&s)初始条件：栈s已存在。操作结果：栈s被销毁。StackEmpty(&s)初始条件：栈s已存在。操作结果：若是为空栈，则返回TRUE,否则返回FALSE。Traverse(&s,void(*visit)()初始条件：栈s已存在。操作结果：依次遍历栈s中的元素，依次调用函数，一旦失败，则操作失败。ADT stack2. 队列抽象数据类型定义ADT Queue 数据对象：D=ai|aiElemset,i

22、=1,2,3,n,n>=0 数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2, n 基本操作： InitQueue(&q)操作结果：构造一个空队列Q。EnQueue(&q, e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。QueueLenth(&q)初始条件：队列已存在。操作结果：返回Q的元素个数，即队列的长度。DeQueue(&q, &e)初始条件：队列已存在。操作结果：删除Q的队尾元素，并用e返回其值。QueueEmpty(&q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，

23、否则返回FALSE.ClearQueue(&q)初始条件：队列Q已存在。操作结果：清空队列Q。DestoryQueue(&q)初始条件：队列Q已存在。操作结果：队列Q被销毁。不再存在。QueueTraverse(&q,Status(*visit)()初始条件：队列Q已存在。操作结果：依次遍历队列Q的元素，依次调用函数，一旦失败，则操作失败。ADT Queue三、详细设计/ 程序的头文件#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>

24、;#include<windows.h>/函数的返回值#define OK 1#define ERROR 0#define TURE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2#define SMAXSIZE 100#define QMAXSIZE 100#define INCREMENT 50 Typedef int Status;typedef char SElemtype; /栈元素的类型typedef char QElemtype; /队列元素的类型typedef struct StackSElemtyp

25、e *base;SElemtype *top;int Stacksize;Stack; /栈的定义typedef struct QueueQElemtype *data;int front;int rear;Queue; /队列的定义Status InitStack(Stack &s) /初始化一个空栈s.base=(SElemtype*)malloc(sizeof(SElemtype)*SMAXSIZE);if(!s.base)exit(OVERFLOW);s.Stacksize=SMAXSIZE;s.top=s.base;return OK;Status Push(Stack &a

26、mp;s,SElemtype e) /将元素e入栈，SElemtype *newbase;if(s.top-s.base)>=s.Stacksize)newbase=(SElemtype*)realloc(s.base,(s.Stacksize+INCREMENT)*sizeof(SElemtype);if(!newbase)exit(OVERFLOW);s.base=newbase;s.top=s.base+s.Stacksize;s.Stacksize+=INCREMENT;*s.top=e;s.top+;return OK;Status Pop(Stack &s,SElem

27、type &e) /出栈，并用元素e返回其值if(s.top=s.base)return ERROR;e=*(-s.top);return OK;int StackLenth(Stack &s) /返回栈的长度return (s.top-s.base);Status ClearStack(Stack &s) /清空栈ss.top=s.base;return OK;Status DestoryStack(Stack &s) /销毁栈sfree(s.base);s.base=NULL;s.top=NULL;return OK;Status StackEmpty(St

28、ack &s) /判断栈空if(s.base=s.top)return TURE;elsereturn FALSE;void PrintS(SElemtype elem) printf("%c",elem);Status Traverse(Stack &s,void(*visit)(SElemtype) /遍历栈sSElemtype* temp=s.base;while(temp!=s.top) visit(*temp); +temp;putchar('n');return OK;Status InitQueue(Queue &q)

29、/初始化队列qq.data=(QElemtype*)malloc(QMAXSIZE*sizeof(QElemtype);if(!q.data)exit(OVERFLOW);q.front=q.rear=0;return OK;Status EnQueue(Queue &q,QElemtype e) /元素e入队列qif(q.rear+1)%QMAXSIZE=q.front)return ERROR;q.dataq.rear=e;q.rear=(q.rear+1)%QMAXSIZE;return OK;Status DeQueue(Queue &q,QElemtype &

30、e) /出队列，并用e返回其值if(q.front=q.rear)return ERROR;e=q.dataq.front;q.front=(q.front+1)%QMAXSIZE;return OK;int QueueLenth(Queue &q) /返回队列的长度return (q.rear+QMAXSIZE-q.front)%QMAXSIZE);Status QueueEmpty(Queue &q) /判断队列是否为空if(q.front=q.rear)return TURE;elsereturn FALSE;Status ClearQueue(Queue &q)

31、 /清空队列qq.rear=q.front;return OK;Status DestoryQueue(Queue &q) /销毁队列qfree(q.data);q.front=q.rear=0;return OK;Status PrintQ(QElemtype e)printf("%c",e);return OK;Status QueueTraverse(Queue &q,Status(*visit)(QElemtype) /遍历队列qint t=q.front;if(!QueueEmpty(q) for(;t!=q.rear;t=(t+1)%QMAXSI

32、ZE) visit(q.datat); return OK;elsereturn ERROR;void Transelate(char str) /魔王语言的翻译SElemtype e1,flag,e,e2;QElemtype y,z,w,h;Stack s,temp,s1,s2;int lenth=strlen(str);Queue q;InitStack(s);InitStack(s1);InitStack(s2);InitStack(temp);InitQueue(q);for(int i=lenth-1;i>=0;-i)Push(s,stri);while(!StackEmpty

33、(s)Pop(s,e1);switch(e1) case 'A': EnQueue(q,'s'); EnQueue(q,'a'); EnQueue(q,'e'); break; case 'B':EnQueue(q,'t');EnQueue(q,'s'); EnQueue(q,'a'); EnQueue(q,'e'); EnQueue(q,'d'); EnQueue(q,'s'); EnQueue(q,'a

34、9;); EnQueue(q,'e'); break; case '(': Pop(s,flag); if(flag=')') Pop(s,flag); else if(flag>='a'&&flag<='z') EnQueue(q,flag);Pop(s,e);while(e!=')'&&!StackEmpty(s)Push(temp,e);Pop(s,e);if(StackEmpty(s)&&e!=')')ClearSt

35、ack(temp);while(!QueueEmpty(q)DeQueue(q,y);Push(s1,y);Pop(s1,z);while(!StackEmpty(s1)Pop(s1,w);Push(s2,w);while(!StackEmpty(s2)Pop(s2,h);EnQueue(q,h);while(!StackEmpty(temp)Pop(temp,e2);EnQueue(q,e2);EnQueue(q,flag); default : continue;printf("n魔王的意思是: ");if(QueueEmpty(q)printf("输入有误!

36、无法翻译!");else QueueTraverse(q,PrintQ); printf("n");DestoryQueue(q);DestoryStack(s);/程序的主函数void main() system("title 魔王语言翻译");for(1;) system("color a1");char str100;int c; printf("*n"); printf(" # 执行程序: 1 # 退出程序: 2n");printf("*n"); print

37、f("请按键选择: "); scanf("%d",&c);getchar();printf("n"); if(c=1) printf("输入魔王语言: "); gets(str); Transelate(str);printf("n*按任意键清屏!*"); system("pause>null"); system("cls");elseexit(0);四、调试分析 1. 本程序模块化比较明确，用队列和栈来实现魔王语言的整个流程。 2. 获得用

38、户输入时用到了字符串，不需用户输入字符串的长度，便于用户使用。 3. 本实习作业采用数据抽象的程序设计方法，使得设计思路清晰，实现时调试顺利。4. 各模块具有较好的可重复性，而且互不影响。五、用户手册 1.本程序的运行环境为DOS操作系统，可执行文件为：魔王语言翻译.exe 2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。 3.进入演示程序后即显示文本形式的用户界面：六、测试结果 执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2 执行命令“2”：退出程序运行最小生成树问题实习报告题目：编制一个求最小生成树的程序班级：姓名： 学号：完成日期：2010.5.31一、需求分析 1

39、. 要在n个城市间建设通信网络，只需要架设n-1条线路即可，建立的最小生成树即能实现付出最低的经济代价。2. 程序利用的是克鲁斯卡尔算法求网的最小生成树。3.输出结果为文本形式的生成树和他们之间的权值。4. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。5. 程序的执行命令有：1）选择操作 2）任意键清屏6. 数据测试 a，b4 a，c3 b，c5 b，e9 b，d5 c，d5 c，h5 d，e7 d，f6 d，g5 d，h4 e，f3 f，g2 g，h6二、概要设计为实现上述功能，需要图这个抽象数据类型。1

40、. 图抽象数据类型定义ADT Graph 数据对象：D=ai|aiElemset,i=1,2,3,n,n>=0 数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2, n 基本操作： CreatGraph(&G，v，vr)初始条件：v是图的顶点集，vr是图中弧的集合。操作结果：按v和vr的定义构建图。DestroyGRaphael（&G）初始条件：图G存在。操作结果：销毁图G。GetVex（G，v）初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex（&G，v，value）初始条件：图G存在，v是G中某个顶点。操作结果：对v

41、赋值value。InsertVex（&G，v）初始条件：图G存在，v和图中某个顶点有相同特点。操作结果：在图G中增添新顶点v。ADT Graph三、详细设计/ 程序的头文件#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<windows.h>#define OK 1#define ERROR 0#define TURE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2#define M 20#defin

42、e MAX 20typedef int Status;typedef struct /定义边结构体 int begin; /开始点 int end; int weight;edge;typedef struct /邻接矩阵int adj; /权值类型 int weight;AdjMatrixMAXMAX;typedef structAdjMatrix arc; /邻接矩阵 int vexnum, arcnum; /顶点数 弧数MGraph;Status CreatGraph(MGraph *G)int i, j,n, m,te; printf("请输入边数和顶点数:n");

43、 scanf("%d %d",&G->arcnum,&G->vexnum); for (i=1; i<=G->vexnum; i+) /初始化图for ( j=1; j<=G->vexnum; j+)G->arcij.adj=G->arcji.adj=0; for ( i=1; i<=G->arcnum; i+) /输入边和权值printf("请输入有边的2个顶点n"); scanf("%d %d",&n,&m);if(n>m)te=n;

44、n=m;m=te; while(n<0|n>G->vexnum|m<0|m>G->vexnum|m=n)printf("输入错误! 请重新输入:n"); scanf("%d%d",&n,&m); G->arcnm.adj=G->arcmn.adj=1; getchar(); printf("请输入%d与%d之间的权值: ", n, m); scanf("%d",&G->arcnm.weight); printf("n邻接矩阵为:

45、n"); for ( i=1; i<=G->vexnum; i+)for ( j=1; j<=G->vexnum; j+)printf("%d ",G->arcij.adj); printf("n");return OK;Status Swapn(edge *edges,int i, int j) /交换权值 以及边的 头和尾int temp; temp=edgesi.begin; edgesi.begin=edgesj.begin; edgesj.begin=temp; temp=edgesi.end; edgesi.end=edgesj.end; edgesj.end=temp; temp=edgesi.weight; edgesi.weight=edgesj.weight; edgesj.weight=temp;return OK;Status Sort(edge edges,MGraph *G) /对每个权值进行排序int i, j; for ( i=1; i<G->arcnum; i+)for ( j=i+1; j<=G->arcnum; j+)if (edgesi.weight > edgesj.weight)Swapn(edges, i, j); pri