软件设计的一些算法.docx

西安电子科技大学软件基础徐超龙 021010721.设有一个线性表E=e1, e2, , en-1, en，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E= en , en-1 , , e2 , e1 ，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。顺序表逆置/*顺序表逆置子程序*/void invert(sequenlist*L)int i,j;datatype k;i=L-last; for(j=1;jdataj; L-dataj=L-datai;L-datai=k;单链表逆置/*单链表逆置子程序*/void invert(linklist*&L)linklist*p,*r,*k,*heat;r=L;k=L-next;while(r-next!=NULL) r=r-next;heat=(linklist*)malloc(sizeof(linklist);heat-next=r; while(k-next!=NULL)p=L;while(p-next)!=r) p=p-next;p-next=NULL; r-next=p; r=p;L=heat; 2.已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。/*单链表分解子程序*/void resolve(linklist*L,linklist*&let,linklist*&dig,linklist*&oth)linklist*p1,*p2,*p3,*head1,*head2,*head3; p1=(linklist*)malloc(sizeof(linklist);p2=(linklist*)malloc(sizeof(linklist);p3=(linklist*)malloc(sizeof(linklist);head1=(linklist*)malloc(sizeof(linklist); head1-next=NULL;head2=(linklist*)malloc(sizeof(linklist);head2-next=NULL;head3=(linklist*)malloc(sizeof(linklist);head3-next=NULL;while(L!=NULL)if(L-datadata=48) if(head1-next=NULL) head1-next=L;elsep1-next=L;p1=L; L=L-next;p1-next=NULL;else if(L-datadata=65)|(L-datadata=97)if(head2-next=NULL)head2-next=L;elsep2-next=L;p2=L;L=L-next;p2-next=NULL;elseif(head3-next=NULL)head3-next=L;elsep3-next=L;p3=L;L=L-next;p3-next=NULL;p1-next=head1; p2-next=head2;p3-next=head3;let=head1;dig=head2;oth=head3;3设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。/*判断中心对称子程序*/int symmetry(linklist*head,stack*s)linklist*p=head;p=p-next;int n=length(head)/2; datatype dat; for(int i=0;idata);p=p-next;if(length(head)%2=1) p=p-next;while(p!=NULL) dat=pop(s);if(dat=p-data) p=p-next;else return 0;return 1;/判字符串是否中心对称4假设以数组sequm存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq-quelen=0；队满的条件：sq-quelen=m。/*入队*/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; /*出队*/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); 5串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（文件夹/*模式匹配子程序*/int Index(seqstring*L, seqstring*Sus) int i=1,j=1; while(ilen&jlen) if(L-stri-1=Sus-strj-1) i+; j+; else i=i-j+2; j=1; if(jSus-len) return(1); else return(-1); 6.若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法void SteDelete(char*S,int I,int m)，要求从S中删除从第i个字符开始的连续m个字符。若istrlen(S)，则没有字符被删除；若i+mstrlen(S)，则将S中从位置i开始直至末尾的字符均删除。/*删除子串子程序*/void strDelete(seqstring*L,int i,int m)char temmaxsize; if(i=L-len) printf(字符未被删除n);L-len=0;else if(ilen)strncpy(tem,L-str,i-1); strcpy(tem+i-1,L-str+i+m-1); strcpy(L-str,tem);if(ilen)if(i+m-1len) L-len=L-len-m; else L-len=L-len-i+1;7. 若在矩阵Amn中存在一个元素Aij，其满足Aij是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Amn ，设计算法求出矩阵中所有马鞍点。/*马鞍点子程序*/void minmax(array*p) int i,j,flag=0; for(i=1;imini=p-Ai1; for(j=2;jAijmini) p-mini=p-Aij; for (j=0;jmaxj=p-A1j; for(i=2;iAijp-maxj) p-maxj=p-Aij; for(i=1;i=m;i+) for(j=1;jmini=p-maxj) printf(马鞍点A%d%d=%dn,i,j,p-Aij); flag=1; if(!flag) printf(矩阵中没有马鞍点！n);8. A和B是两个nn阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。/*对称矩阵相乘子程序*/void mult(array*p)in