《软件技术基础上机作业》由会员分享，可在线阅读，更多相关《软件技术基础上机作业（32页珍藏版）》请在金锄头文库上搜索。
1、实验一、顺序表逆置和单链表逆置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 te
2、mp; /定义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：重复Ste
3、p1 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
4、;/ 原链表最后一个结点变为新链表的头结点1.2.3 运行结果1.2.4 存在的问题与顺序表逆置一样，逆置表中的元素只能是单个元素，不能进行多位数的逆置，如下图所示实验二、分解单链表2.1 问题的提出已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。2.2 算法分析Step1：将单链表中的头结点与字母比较，判断是否在A,Z或者a,z之间；Step2：在A,Z或者a,z之间，则将它写入字母的单链表中,否则转Step3；Step3：将单链表中的头
5、结点与字母比较，判断是否在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-ne
6、xt; 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 运行结果 字符串不是中心对称时结果 字符串是
7、中心对称时结果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-qu
8、elen=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
9、+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
10、-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
11、个字符。若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是第
