软件技术基础上机作业.doc

实验一、顺序表逆置和单链表逆置1.1 问题的提出设有一个线性表E=e1, e2, , en-1, en，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E= en , en-1 , , e2 , e1 ，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。 顺序表逆置1.1.1 算法分析Step1：将顺序表位置i的元素与位置L-last-i+1的元素进行互换；Step2：重复Step1，直到i=L-last/2，结束。1.1.2 问题的程序代码/顺序表逆置void invert(sequenlist*L) int i; datatype temp; /定义i和temp的类型 for(i=1;ilast/2;i+)/for循环语句，其中的L-last/2当L-last为奇数时，相当于向下取整 temp=L-datai; L-datai=L-dataL-last-i+1; L-dataL-last-i+1=temp;/将位置i和位置L-last-i+1的元素进行互换 1.1.3 运行结果1.1.4 存在的问题逆置表中的元素只能是单个元素，不能进行多位数的逆置，如下图所示 单链表逆置1.2.1 算法分析Step1：将p指针指向头结点，q指针指向头结点的下一个结点；Step2：将p和q逆置，并将它们分别后移一个结点；Step3：重复Step1 Step2，直到指针r指向空域，结束。1.2.2 问题的程序代码/单链表逆置void invert(linklist *head) linklist *p,*q,*r; p=head-next;/p指针指向头结点 q=p-next; /q指针指向头结点的下一个结点 while(q!=NULL)/当q指针非空时，进行while循环 r=q-next; q-next=p;/将r指针指向q的下一个结点，而q指针指向p p=q; q=r;/将p指针指向q，q指针指向r，实现p和q的逆置 head-next-next=NULL;/原链表的第一个结点指针置空，变为新链表的尾结点head-next=p;/ 原链表最后一个结点变为新链表的头结点1.2.3 运行结果1.2.4 存在的问题与顺序表逆置一样，逆置表中的元素只能是单个元素，不能进行多位数的逆置，如下图所示实验二、分解单链表2.1 问题的提出已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。2.2 算法分析Step1：将单链表中的头结点与字母比较，判断是否在A,Z或者a,z之间；Step2：在A,Z或者a,z之间，则将它写入字母的单链表中,否则转Step3；Step3：将单链表中的头结点与字母比较，判断是否在0,9之间；Step4：在0,9之间，则将它写入数字的单链表中否则转Step5；Step5：将它写入其他字符的单链表中；Step6：取下一结点，重复Step1 Step5，直到结点完全进入3个新的单链表，结束。2.3 问题的程序代码/按字母、数字、其它字符分解单链表void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) linklist *p; while(head-next!=NULL) p=head-next;/p指针指向头结点 head-next=head-next-next; if(p-data=A&p-datadata=a&p-datadata=0&p-datanext; n=length(head);/n表示字符串的长度datatype j;for(i=1;idata);p=p-next;if(n%2=1) p=p-next; /若字符串长度是奇数，指针p从向后移一位while(p!=NULL) /判断字符串出栈与另外一半字符串比较是否相等，相等返回1，否则返回0j=pop(s);if(j!=p-data) /j与p中的元素不相等时返回1return 1;else p=p-next; return 0;3.4 运行结果 字符串不是中心对称时结果 字符串是中心对称时结果3.5 存在的问题注意字符串长度为奇数时的判定即可。实验四、循环队列4.1 问题的提出假设以数组sequm存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq-quelen=0；队满的条件：sq-quelen=m。4.2 算法分析Step1：先进行入队操作，判断是否队满，队未满时将x入队尾；Step2：再进行出队操作，判断是否队空，队列非空时将队头元素出队。4.3 问题的程序代码/入队void enqueue(qu *sq, datatype x) if(sq-quelen=m) printf(queue is fulln);/队列上溢 else sq-quelen+; sq-rear=(sq-rear+1)%m; sq-sequsq-rear=x;/队列未满时，将x入队尾/出队datatype *dequeue(qu *sq) datatype *temp; if(sq-quelen=0) printf(queue is emptyn); return NULL; /队列为空 else temp=(datatype*)malloc(sizeof(datatype); sq-quelen-; *temp=sq-sequ(sq-rear-sq-quelen+m)%m; return (temp); /队列非空时，将队头元素出队 4.4 运行结果4.5 存在的问题注意队空和队满时的情况即可。实验五、模式匹配5.1 问题的提出串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。5.2 算法分析Step1：从位序为1时开始将其与目标串进行匹配；Step2：当一趟的字符串完全匹配时，返回i-T-len，匹配成功；否则返回-1，匹配失败。5.3 问题的程序代码/顺序串的朴素模式匹配int Index(seqstring*S, seqstring*T) int i=1,j=1; /位序从1开始 while(ilen&jlen) if(S-stri-1=T-strj-1) i+; j+; /继续比较后面的字符 else i=i-j+2; j=1; /本趟不匹配，设置下一趟匹配的起始位序 if(jT-len) return(i-T-len); /匹配成功 else return(-1); /匹配不成功 5.4 运行结果 匹配成功时的结果 匹配失败时的结果5.5 存在的问题未发现问题的存在。实验六、删除子串6.1 问题的提出若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法void SteDelete(char*S,int I,int m)，要求从S中删除从第i个字符开始的连续m个字符。若istrlen(S)，则没有字符被删除；若i+mstrlen(S)，则将S中从位置i开始直至末尾的字符均删除。6.2 算法分析Step1：先建立一个存储数组，并将串中的前i个字符进行复制到temp中；Step2：串S中除去要求删除的m个字符，把后面的字符连接到temp中； Step3：将temp中的字符复制到S中，并修改字符串长度加1。6.3 问题的程序代码/删除子串void strDelete(seqstring*S,int i,int m)char tempmaxsize; /建立存储数组if(ilen)strncpy(temp,S-str,i-1); /把串S的前i个字符复制到temp中strcpy(temp+i-1,S-str+i+m-1); /串S中除要删除的m个字符，把后面的字符连接到temp中strcpy(S-str,temp); / temp中的字符复制到S中if(ilen)if(i+m-1len) S-len=S-len-m;else S-len=S-len-i+1; /修改字符串长度加16.4 运行结果6.5 存在的问题未发现问题。实验七、找马鞍点7.1 问题的提出若在矩阵Amn中存在一个元素Aij，其满足Aij是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Amn ，设计算法求出矩阵中所有马鞍点。7.2 算法分析Step1：先分别找出m行的最小值；Step2：再分别找出n行的最大值；Step3：若Step1和Step2存在相等的位置，则是一个马鞍点；否则不存在马鞍点。7.3 问题的程序代码/找马鞍点void minmax(array*p)/找马鞍点int i,j,have=0; for (i=1;imini=p-Ai1; for(j=2;jAijmini) p-mini=p-Aij; /分别找出m行的最小值 for(j=1;jmaxj=p-A1j; for(i=2;iAijp-maxj) p-maxj=p-Aij; /分别找出n行的最大值 for(i=1;i=m;i+) for(j=1;jmini=p-maxj)/若相等，则是一个马鞍点 printf(n马鞍点为：%dn位置为：(%d,%d)n,p-Aij,i,j);/输出马鞍点 have=1; if(!have)printf(矩阵中没有马鞍点!);7.4 运行结果 存在马鞍点的结果 不存在马鞍点的结果7.5 存在的问题注意不存在马鞍点的判断，即不存在列最小值和行最大值共同存在的情况。实验八、对称矩阵相乘8.1 问题的提出A和B是两个nn阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。8.2 算法分析Step1：对称存储A，B的下三角矩阵； Step2：将对称存储A，B的下三角矩阵进行相乘并将其存储在矩阵C中。8.3 问题的程序代码/对称矩阵相乘void mult(array*p)int i,j,k,t1,t2;datatype s;for(i=0;in;i+) for(j=0;jn;j+)s=0;for(k=0;k=k)t1=i*(i+1)/2+k;else t1=k*(k+1)/2+i;if(k=j)t2=k*(k+1)/2+j;else t2=j*(j+1)/2+k;s=s+p-At1*p-Bt2;p-Cij=s;8.4 运行结果8.5 存在的问题注意如何存储对称的A，B的下三角矩阵的方式。实验九、交换左右二叉子树9.1 问题的提出已知二叉树采用二叉链表存储结构，如果左、右子树非空，且左子树根结点大于右子树根结点，则交换根结点的左、右子树。即按要求交换二叉树及子树的左、右子树。9.2 算法分析Step1：先判断是否遍历根结点及子树的左、右子树，是，转Step2； Step2：交换根结点及子树的左、右子树，并得出左、右子树的标志变量。9.3 问题的程序代码/交换左右子树void swap(bitree*p)bitree*t;if(p!=NULL)if(p-lchild!=NULL&p-rchild!=NULL&p-lchild-datap-rchild-data) /遍历根结点及子树的左、右子树t=p-lchild;p-lchild=p-rchild;p-rchild=t;/交换根结点及子树的左、右子树swap(p-lchild);swap(p-rchild); /得出左、右子树的标志变量9.4 运行结果9.5 存在的问题左右子树与根结点要确定遍历，之后交换左右子树即可。实验十、统计二叉树的结点10.1 问题的提出采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。10.2 算法分析Step1：先统计结点总数，利用结点的遍历使其结点数加1的方法即可； Step2：再统计叶子结点总数，分别统计左、右子树中叶子结点个数，相加即得出叶子结点总数leaf。10.3 问题的程序代码/统计结点总数int countleaf(bitree *p) static int n=0; /n为结点个数if(p!=NULL)n+; /每遍历一个结点，n加1countnode(p-lchild); countnode(p-rchild); /遍历根结点及子树的左、右子树return n; /统计叶子结点总数static int leaf =0; if(p!=NULL) leaf = countleaf( p-lchild ); /统计左子树中叶子结点个数if (p-lchild=NULL)&(p-rchild=NULL) leaf=leaf+1;leaf=countleaf(p-rchild); /统计右子树中叶子结点个数 return leaf; 10.4 运行结果10.5 存在的问题统计结点总数时要确定遍历完全部的结点，并且统计叶子结点总数要确定左右叶子个子树的完全统计。实验十一、无向图邻接矩阵11.1 问题的提出无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。11.2 算法分析Step1：确定出发点为，开始进行深度优先搜索； Step2：当被访问过时，利用visitedi=1进行标记；Step3：并从未被访问的邻接点出发进行深度优先搜索遍历即可。11.3 问题的程序代码/添加深度优先搜索遍历算法void dfsa(int i)int j;printf(出发点%cn,g-vexsi); /从出发点为开始进行深度优先搜索visitedi=1; /标记已被访问for(j=0;jarcsij=1)&(visitedj=0)dfsa(j);/从未被访问的邻接点出发进行深度优先搜索遍历11.4 运行结果11.5 存在的问题注意确定开始进行深度优先搜索的出发点为，并且标记已被访问和从未被访问的邻接点的确定。实验十二、希尔排序12.1 问题的提出采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序的结果。12.2 算法分析Step1：先设置T个监视哨，并且每一趟增加相应的常量； Step2：通过Step1设置不同的常量，可得出输出一趟的排序结果，结束。12.3 问题的程序代码/希尔排序void shellsort(rectype r,int d)int i,j,k,h;rectype temp;int maxint=32767;for(i=0;iD1;i+)ri.key=-maxint;/设置T个监视哨k=0;doh=dk;/取一趟的增量for(i=h+D1;iN+D1;i+)temp=ri;j=i-h;while(temp.key=i+1;j-)/最多进行n-1趟的排序if(rj.keyrj-1.key)noswap=1;temp=rj;rj=rj-1;rj-1=temp;/将最大的量进行“下沉”for(j=i+1;jrj+1.key)noswap=1;temp=rj;rj=rj+1;rj+1=temp;/将最大的量进行“下沉”for(int k=1;k=n;k+)printf(%5d,rk.key);printf(n);i+;/输出排序后的结果13.4 运行结果13.5 存在的问题一次扫描可以将最重的“气泡”进行“下沉”，而当进行上浮时比较简单时应利用上浮进行排序，这比较难以判定。实验十四、分块查找14.1 问题的提出18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、49、86、53，编写分块查找的算法进行查找。14.2 算法分析Step1：在索引表较大时，应先利用折半查找的方法确定关键字所在的块； Step2：再利用顺序查找的方法即可查找出关键字所在的确定位置即可。14.3 问题的程序代码/分块查找int blksearch(record r,index idx,keytype k,int n)int i,low=0,high=n-1,mid,bh,find=0;/折半查找索引表while(low=high&!find)mid=(low+high)/2;if(kidxmid.key)low=mid+1; else high=mid-1; find=1; if(lown)i=idxlow.low;/块的起始地址bh=idxlow.high;/块的终止地址/块内顺序查找while(ilchild);if(p-keyk) k=p-key;/当二叉树的左子树的值均小于相应的根结点的值，且右子树的值均大于相应的根结点的值为二叉排序树else printf(不是二叉排序树！n); exit(0);inorder(p-rchild);15.4 运行结果 不是二叉排序树时的结果 是二叉排序树时的结果15.5 存在的问题 判断是否二叉排序树时应注意p-keyk的判定和k=p-key的赋值步骤。大作业：模拟简单计算器程序1) 程序功能简介计算机程序能进行简单的加减乘除，取绝对值，开平方和三角函数的计算，可以用退格键修改输入，输入错误的话计算器会提示错误，并要求重新输入。如果想退出计算机也可以按键退出。2) 程序运行条件与操作提示1、VC+6.0，C+运行环境；2、本程序是用C语言编写的，利用VC+6.0编译器进行编译的，在DOS界面下运行的。运行时输入要注意程序能处理的数据最长为6位，输入0则结束程序，输入有误则提示输入错误；输入正确则可得到计算结果。3) 程序设计过程输入的时候将一个算术表达式放入一个数组中，将数组中的操作和数字分离。在转换时，运用堆栈对运算符进行处理，使其变换成后缀表达式。在对后缀表达式进行处理的时候，定义一个堆栈存放操作数。并将运算结果存入该栈中。两个堆栈的数据结构如下：然后定义了三个函数change函数、jisuan函数、meun函数实现，三个函数均包含在main函数当中。程序的流程图如下：4) 详细的程序清单及程序注释：#include iostream#include math.h#include string#include stdlib.h#include windows.h#define derror 1234567#define Maxlen 400using namespace std; struct char dataMaxlen; int top; optr;/定义运算符栈，并定义全局变量struct double dataMaxlen; int top; opnd;/定义操作数栈，并定义全局变量void main() char p400,q400; double k;void meun(); /声明菜单函数int change(char *p, char q);/声明转换函数double jisuan(char *q);/声明计算函数meun(); for(;) /循环执行 cout p; if (strcmp(p,0)=0) return; if (change(p,q)=1) k=jisuan(q); if(k=derror)cout; else coutThe results is：kendl;system(pause); /控制输出格式system(cls); meun(); void meun() /菜单函数system(color 0a);couttt *endl;cout Welcome endl;couttt *endl;coutendl;coutPress 0 to exitendl;/转换函数int change(char *p, char q) /将算术表达式p转换成表达式后缀表达式q int i=0; /i作为q的下标 int dh=1; /dh=1表示是负号 optr.top=-1; /初始化运算符栈 while (*p!=0) /p表达式未扫描完时循环 switch(*p) /判断各种情况,并做相应的处理 case (: optr.top+;optr.dataoptr.top=*p; dh=1;p+;break; case ): while (optr.dataoptr.top!=() qi=optr.dataoptr.top; optr.top-; i+; optr.top-; p+; dh=0; break; case +: case -: if (dh=1) / +,-是正负号 if (*p=-) optr.top+;optr.dataoptr.top=; p+; break; while (optr.top!=-1 & optr.dataoptr.top!=() qi=optr.dataoptr.top; optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break; case *: case /: while (optr.dataoptr.top=* | optr.dataoptr.top=/| optr.dataoptr.top=s) qi=optr.dataoptr.top; optr.top-; i+; optr.top+;optr.dataoptr.top=*p; p+; dh=0; break; case : while (optr.dataoptr.top=) qi=optr.dataoptr.top; optr.top-;i+; optr.top+;optr.dataoptr.top=*p;p+;dh=0;break;case %: while (optr.dataoptr.top=%) qi=optr.dataoptr.top; optr.top-;i+; optr.top+;optr.dataoptr.top=*p;p+;dh=0;break; case : p+; break; /消除空格 case s: case S: if(*(p+1)=i | *(p+1)=I)&(*(p+2)=n | *(p+2)=N) optr.top+;optr.dataoptr.top=s; p+=3; dh=0; break; else if(*(p+1)=q|*(p+1)=Q)&(*(p+2)=r| *(p+2)=R)&(*(p+3)=t | *(p+3)=T) optr.top+;optr.dataoptr.top=q;p+=4;dh=0;break; else coutendlErrorendl; return derror; case c: case C: if(*(p+1)=o | *(p+1)=O)&(*(p+2)=s | *(p+2)=S) optr.top+;optr.dataoptr.top=c; p+=3; dh=0; break; else coutendlErrorendl; return derror; case T: case t:if(*(p+1)=a| *(p+1)=A)&(*(p+2)=n | *(p+2)=N) optr.top+;optr.dataoptr.top=t; p+=3;dh=0; break; else coutendlErrorendl; return derror; case e: case E:if(*(p+1)=x| *(p+1)=X)&(*(p+2)=p | *(p+2)=P) optr.top+;optr.dataoptr.top=e; p+=3;dh=0; break; else coutendlErrorendl; return derror; case