《数据结构课程设计》由会员分享,可在线阅读,更多相关《数据结构课程设计(30页珍藏版)》请在金锄头文库上搜索。
1、实习 1 线性表及其应用1集合的并、交和差/ js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js【实验目的】 编制一个能演示执行集合的并、交和差运算的程序【实验任务】1)集合的元素限定为小写字母; 2)演示程序以用户和计算机的对话方式执行。【概要设计】int Ini tlis t(linklis t & L)用来初始化线性链表
2、void makenode(linklist &L,char e) 生成结点int xiaoxie(char e,int flag) 判断输入的字符是否是小写字母void jiao(linklist &L,linklist m,linklist n) 求两个集合的交void bing(linklist &L,linklist m,linklist n) 求两个集合的并 void cha(linklist &L,linklist m,linklist n) 求两个集合的交*1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*
3、 *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* / c.cpp : Defines the entry point for the console application. /*【程序代码】*/#include stdafx.h#include malloc.h
4、#include iostream.htypedef char elemtype;#define TRUE 1;#define FALSE 0;typedef struct lnode/单链表存储结构elemtype data;struct lnode *next;lnode,*linklist;/初始化线性链表int Initlist(linklist &L)L=(linklist)malloc(sizeof(lnode);if(!L) return FALSE;L-next=NULL;return TRUE;void makenode(linklist &L,char e)/生成结点lin
5、klist s;s=(linklist)malloc(sizeof(lnode);s-data=e;s-next=L-next;L-next=s;int xiaoxie(char e,int flag) /判断输入的字符是否是小写字母if(ez)prin tf(输入错误!必须为小写字母!n);flag=0;return flag;voidjiao(linklist&L,linklistm,linklistn)/求两个集合的交,并且将其存入另一个链表中linklist p;Initlist(p);while(m-next)p=n; /使每次循环从 n 的第一个结点开始while(p-next)i
6、f(m-next-data=p-next-data)makenode(L,m-next-data);/有相等元素是将元素放入链表中跳出循环break;p=p-next;m=m-next;/whilevoid bing(linklist &L,linklist m,linklist n) /求两个集合的并,并且存入一个链 表中linklist J;Initlist(J);jiao(J,m,n);/利用上面所求的两个集合的交进行下一步运算linklist p;while(m-next)/先将其中一个集合的的元素存入链表makenode(L,m-next-data);m=m-next;while(n
7、-next) /再将另一个集合中不同于前一个集合的元素存入此链表中p=J;while(p-next)if(n-next-data=p-next-data)break;/当有相同元素时跳出循环p=p-next;/whileif(!p-next)makenode(L,n-next-data);n=n-next;/whilevoid cha(linklist &L,linklist m,linklist n) /利用两集合的交 J,将第一个集合中的 与 J 不同的元素放入链表linklist J;Initlist(J);jiao(J,m,n);/求交linklist p;while(m-next)p
8、=J;while(p-next)if(m-next-data=p-next-data)break;/当在交中有相同元素时,跳出循环p=p-next;/whileif(!p-next)makenode(L,m-next-data);m=m-next;/whileint main(int argc, char* argv)char a50,b50;/将两个数组的元素存入链表中int i;int flag=1;cout输入第一个集合A:;cina;/使两个集合中的元素全部限定为小写字母for(i=0;*(a+i)!=0&flag;i+)flag=xiaoxie(*(a+i),flag);cout输入
9、第二个集合B:;cinb;for(i=0;*(a+i)!=0&flag;i+)flag=xiaoxie(*(a+i),flag);if(flag=0)/如果输入不是小写字母则报错并终止cou t不能继续执行交并差的运算!;return 0;linklist m,n;Initlist(m);Initlist(n);for(i=0;*(a+i)!=0;i+)makenode(m,*(a+i);for(i=0;*(b+i)!=0;i+)makenode(n,*(b+i);linklist J,B,C;/J,B,C 分别为两集合的交,并,差/初始化链表,并且分别对其操作Initlist(J);Init
10、list(B);Initlist(C);jiao(J,m,n);bing(B,m,n);cha(C,m,n);linklist p;/以下为输出集合,并释放存储空间cout两个集合的交是:;p=J;while(p-next)coutp-next-data;p=p-next;coutendl;cout两个集合的并是:;p=B;while(p-next)coutnext-data;p=p-next;coutnext)coutp-next-data;p=p-next;coutendl;while(m-next!=NULL)p=m;m=m-next;free(p);while(n-next)p=n;n
11、=n-next;free(p);while(J-next)p=J;J=J-next;free(p);while(B-next)p=B;B=B-next;free(p);while(C-next)p=C;C=C-next; free(p);return 0;/ *X* *X* *X* *X*/【测试数据及结果分析】 第一组的测试数据为 wsxjtwbxt结果输入第一个集合 A:wsxjt 输入第二个集合 B:wbxt 两个集合的交是:wx t 两个集合的并是:bwsx jt 两个集合的差A-B是:sj 第二组的测试数据为ASDACD结果输入第一个集合 A:ASD 输入错误!必须为小写字母! 输入
12、第二个集合 B:ACD 不能继续执行交并差的运算!本程序可以较好的完成集合的交并差运算, 将集合的元素限定为小写字母.*i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* /实习 2 栈、队列和递归程序设计1. 求算术表达式的值。/ js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js
13、js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js【实验目的】 设计一个程序,演示用算符优先法对算术表达式求值的过程。【实验任务】以字符序列的形式从终端输入以#结束表达式。如果表达式正确计算表达式的值否则指出表达式中错误的类型。在输入的表达式中可以有加、减、乘、除和括号运算,输入的数据为实数。输出表达式的值, 并且输出在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程 【概要设计】void InitStack(SqStack &S)/栈的初始化void Push(SqStack &S,char e)/插入栈数据void Pop(SqStack&S,char &e)/删除头结点,并返回值char GetTop(SqStack S)/返回栈顶元素int In(char c)/限定运算符char Precede(char a,char b)/判断运算符的优先级*1* *1* *1* *1* *1*