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

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

2、2=”ae”,Set1-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,aiD,i=2, n 基本操作： InitList(&l) 操作结果：构造一个空的顺序表l。 ListLength(l) 初始条件：顺序表l已存在

3、。 操作结果：返回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(&L,i, &e) 初始条件：顺序表l已存在。 操作结果：删除

4、顺序表中第i个元素。 Outputlist(&L)初始条件：顺序表l已存在。 操作结果：输出顺序表的每个元素值。ADT sqlist三、详细设计/ 程序的头文件#include#include#include#include/ 函数返回值#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0#define LIST_INIT_SIZE 100 /顺序表的初始大小#define LISTINCREMENT 10 /顺序表的递增大小t

5、ypedef int Status; /返回状态类型typedef char ElemType; /元素类型 typedef struct ElemType *elem; int length; int listsize; SqList; /结点类型 指针类型Status InitList(SqList &l) /初始化顺序表l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!l.elem) exit(OVERFLOW);l.length=0;l.listsize=LIST_INIT_SIZE;return OK;int L

6、istLength(SqList l) /求顺序表的长度return(l.length);Status ListInsert_Sq(SqList &L,int i, ElemType e)/在顺序表L的第i个位置前插入元素e,i的合法值为1.L.length+1 if(iL.length+1) return ERROR; if(L.length=L.listsize) ElemType*newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLO

7、W); 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 CreatSqList(SqList &l,ElemType a,int n) /创建顺序表int len=ListLength(l);for(int i=0;i=a&ai=z)ListInsert_Sq(l,+len,ai);return OK;Status GetE

8、lem(SqList L,int i,ElemType &e)/ 返回顺序表中元素 if(iL.length)return ERROR;elsee=*(L.elem+i-1);return 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所

9、指向元素的位序 while(i=L.length&!(*compare)(*p+,e)+i; if(i=L.length) return(i); else return 0;Status ListDelete(SqList &L,int i,ElemType &e)/在顺序表中删除第个元素，用返回其值 if(iL.length) return ERROR;/删除位置不合理 ElemType *p=&L.elemi-1,*q=L.elem+L.length-1; e=*p; while(pq)*p=*(p+1); +p; /删除位置后的元素左移 -L.length; return OK;void

10、 Union(SqList &La,SqList Lb)/将所有在线性表Lb中而不在La中的元素插入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_

11、len,l3_len,i=1,j=1;ElemType e,u;l1_len=ListLength(l1);l2_len=ListLength(l2);l3_len=ListLength(l3);for(i=1;i=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;ElemType e,u,f;Init

12、List(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(空集!);else for(int i=0;i=0;i-) /从最后一个开始依次与前面的

13、比较 重复赋值为0 for(j=0;j=0;i-) /同上 for(j=0;jnull); system(cls);elseexit(0);四、调试分析 1.本程序的模块划分比较合理，且尽可能的将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较成功。 2.将数据存入数组再转入链表，可以忽略输入集合的长度，设计更加巧妙，便于用户使用。 3.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：元素结点、有序链表、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。五、用户手册 1.本程序的运行环境为DOS操作系统，可执行文件

14、为：集合的并交差运算.exe 2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。 3.进入演示程序后即显示文本形式的用户界面：六、测试结果 执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2 执行命令“2”：退出程序运行魔王语言翻译实习报告题目：编制一个演示魔王语言的翻译程序班级：姓名： 学号：完成日期：2010.5.27一、需求分析1. 本演示程序中，魔王语言限制在小写字母a-z之间，且必须限制在括号内以及大写字母A和B。且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。2. 魔王语言遵守如下规则： （123n）nn-11BtAdA

15、 Asae 3. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。4. 程序的执行命令有：1）选择操作 2）任意键清屏5. 数据测试 B(ehnxgz)B解释成：tsaedsaeezegexenehetsaedsae二、概要设计为实现上述功能，需要栈和队列两个抽象数据类型。1. 栈抽象数据类型定义ADT stack 数据对象：D=ai|aiElemset,i=1,2,3,n,n=0 数据关系：R1=|ai-1,aiD,i=2, n 基本操作： InitStack(&s) 操作结果：构造一个空栈s。Push(&s

16、, e)初始条件：栈s已存在。操作结果：插入元素e为新的栈顶元素。Pop(&s, &e)初始条件：栈s已存在且非空。操作结果：删除栈s的栈顶元素，并用e返回其值。StackLenth(&s)初始条件：栈s已存在。操作结果：返回s的元素个数，即栈的长度。ClearStack(&s)初始条件：栈s已存在。操作结果：将s清为空栈。DestoryStack(&s)初始条件：栈s已存在。操作结果：栈s被销毁。StackEmpty(&s)初始条件：栈s已存在。操作结果：若是为空栈，则返回TRUE,否则返回FALSE。Traverse(&s,void(*visit)()初始条件：栈s已存在。操作结果：依次遍

17、历栈s中的元素，依次调用函数，一旦失败，则操作失败。ADT stack2. 队列抽象数据类型定义ADT Queue 数据对象：D=ai|aiElemset,i=1,2,3,n,n=0 数据关系：R1=|ai-1,aiD,i=2, n 基本操作： InitQueue(&q)操作结果：构造一个空队列Q。EnQueue(&q, e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。QueueLenth(&q)初始条件：队列已存在。操作结果：返回Q的元素个数，即队列的长度。DeQueue(&q, &e)初始条件：队列已存在。操作结果：删除Q的队尾元素，并用e返回其值。QueueEmpty

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

19、OR 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 StackSElemtype *base;SElemtype *top;int Stacksize;Stack; /栈的定义typedef

20、 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 &s,SElemtype e) /将元素e入栈，SElemtype *newbase;if(s.top-s.base)=s.

21、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,SElemtype &e) /出栈，并用元素e返回其值if(s.top=s.base)return ERROR;e=*(-s.top);return OK

22、;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(Stack &s) /判断栈空if(s.base=s.top)return TURE;elsereturn FALSE;void PrintS(SElemtype elem) pr

23、intf(%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) /初始化队列qq.data=(QElemtype*)malloc(QMAXSIZE*sizeof(QElemtype);if(!q.data)exit(OVERFLOW);q.front=q.rear=0;return OK;Status En

24、Queue(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 &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) /返回队列的长度

25、return (q.rear+QMAXSIZE-q.front)%QMAXSIZE);Status QueueEmpty(Queue &q) /判断队列是否为空if(q.front=q.rear)return TURE;elsereturn FALSE;Status ClearQueue(Queue &q) /清空队列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)

26、;return OK;Status QueueTraverse(Queue &q,Status(*visit)(QElemtype) /遍历队列qint t=q.front;if(!QueueEmpty(q) for(;t!=q.rear;t=(t+1)%QMAXSIZE) 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);Que

27、ue q;InitStack(s);InitStack(s1);InitStack(s2);InitStack(temp);InitQueue(q);for(int i=lenth-1;i=0;-i)Push(s,stri);while(!StackEmpty(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);

28、 EnQueue(q,a); EnQueue(q,e); break; case (: Pop(s,flag); if(flag=) Pop(s,flag); else if(flag=a&flagnull); system(cls);elseexit(0);四、调试分析 1. 本程序模块化比较明确，用队列和栈来实现魔王语言的整个流程。 2. 获得用户输入时用到了字符串，不需用户输入字符串的长度，便于用户使用。 3. 本实习作业采用数据抽象的程序设计方法，使得设计思路清晰，实现时调试顺利。4. 各模块具有较好的可重复性，而且互不影响。五、用户手册 1.本程序的运行环境为DOS操作系统，可执行文

29、件为：魔王语言翻译.exe 2.为了界面更加友好特将背景颜色设计为绿色，字体为黑色。 3.进入演示程序后即显示文本形式的用户界面：六、测试结果 执行命令“1”：进入执行程序界面，提示用户输入集合1和集合2 执行命令“2”：退出程序运行最小生成树问题实习报告题目：编制一个求最小生成树的程序班级：姓名： 学号：完成日期：2010.5.31一、需求分析 1. 要在n个城市间建设通信网络，只需要架设n-1条线路即可，建立的最小生成树即能实现付出最低的经济代价。2. 程序利用的是克鲁斯卡尔算法求网的最小生成树。3.输出结果为文本形式的生成树和他们之间的权值。4. 演示程序以用户和计算机对话的形式进行，即

30、在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。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. 图抽象数据类型定义ADT Graph 数据对象：D=ai|aiElemset,i=1,2,3,n,n=0 数据关系：R1=|ai-1,aiD,i=2, n 基本操作： CreatGraph(&G，v，vr)初始条件：v是图的顶点集，vr是图中弧

31、的集合。操作结果：按v和vr的定义构建图。DestroyGRaphael（&G）初始条件：图G存在。操作结果：销毁图G。GetVex（G，v）初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex（&G，v，value）初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。InsertVex（&G，v）初始条件：图G存在，v和图中某个顶点有相同特点。操作结果：在图G中增添新顶点v。ADT Graph三、详细设计/ 程序的头文件#include#include#include#include#define OK 1#define ERROR 0#define TU

32、RE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2#define M 20#define 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;S

33、tatus CreatGraph(MGraph *G)int i, j,n, m,te; printf(请输入边数和顶点数:n); scanf(%d %d,&G-arcnum,&G-vexnum); for (i=1; ivexnum; i+) /初始化图for ( j=1; jvexnum; j+)G-arcij.adj=G-arcji.adj=0; for ( i=1; iarcnum; i+) /输入边和权值printf(请输入有边的2个顶点n); scanf(%d %d,&n,&m);if(nm)te=n;n=m;m=te; while(nG-vexnum|mG-vexnum|m=n)

34、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邻接矩阵为:n); for ( i=1; ivexnum; i+)for ( j=1; jvexnum; j+)printf(%d ,G-arcij.adj); printf(n);return OK;Status Swapn(edge *edges,int i, int j) /交换权值 以及边的 头和尾

35、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; iarcnum; i+)for ( j=i+1; jarcnum; j+)if (edgesi.weight edgesj.weight)Swapn(edges, i, j); printf(n权排序之后的为:n);for (i=1; iarcnum; i+)printf( %dn