软件大作业教材

《软件大作业教材》由会员分享，可在线阅读，更多相关《软件大作业教材（13页珍藏版）》请在装配图网上搜索。

1、软件大作业班级:学号:姓名:实验一线性表一、实验目的1.熟悉线性表的顺序和链式存储结构2.掌握线性表的基本运算3.能够利用线性表的基本运算完成线性表应用的运算二、实验内容1.设有一个线性表E=ei,e2,.,en-i,en,设计一个算法，将线性表逆程，即使元素排列次 序颠倒过来，成为逆线性表E= en,_.,e2,e, ,要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆巻、 单链表逆置）顺序表逆置算法：代码#include#include#dcfine maxsize 1024typcdef int datatype;typcdcf st

2、nictdatatype datamaxsize; int last;)sequenlist;sequenlist*InitList();int Lcngth(sequenlist*);int Insert(scquenlist*,datatypeJnt);int Locate(sequenlist*,datatype);int Delete(sequenlist*jnt);void del_node(sequenlist*,datatype);void PrintList(sequenlist*);void main() sequenlist*L; int i=0;int m,n;datat

3、ype x,y;L=InitList();primf(输入若干整数数据，建立顺序表，输入-1结束：n);scanf(M%d&x);while(x!=-l)i+;if(!Insert(L,x,i) exit(O);scanf(,%d,&x);PrintList(L);for(m=l ;mlast;m+)y=L-dataL-last;for(n=L-last-l ;n=m;n-) L-datan+l =L-datan;L-datam=y;PrintList(L);void PrintList(sequenlist*L)int i;for(i=l ;iIast;i+) primf(%

4、5cT,L-da(ai);printfCXn);void del_node(scquenlist*L,datatype x)int k;k=Locate(L,x);while(k)if(Dclete(Uk)=O) break;k=Locate(L.x);int Insert(sequenlist*L,datatype x.int i)在新柠点插入顺序表的第i个位置intj;if(L-last=maxsize-1)printf(n表已满”);return 0;elsefor(j=L-last;j=i;j-) L-dataj+l =L-dataj;L-datai=x;L-last+;return

5、1;int Locate(sequenlist*L,datatype x)在顺序表中查找第一个与x相同的元素int i=l;while(ilast)if(L-datai!=x) i+;else return i;return 0;)int Delete(sequcnlist*L.int i)/删除int j;if(iL-last)printfC1非法删除位置J;return 0;elsefor(j=i:jlast-1 ;j+) L-dataj=L-dataj+l ; L-last-;return 1;sequenlist*InitList() sequenlist*L=(sequenlist*

6、)malloc(sizeof(sequenlist); L-last=0;return L;int Length(sequenlist*L)return L-last;st *F:yCilcscccccccno.lDrbugtcs输入若干整数数据,12 3 4 5 6 -1123654Press any key to单链表逆置代码: 算法：/添加单链表逆置算法void invert(linklist*&head)datatype q;linklist *a,*b,*c;c=head;while(c-next!=NULL)(c=c-next;while(c !=head-next)a=h

7、cad-next;b=head;while(a!=c)q=a-data; a-data=a-next-data; a-next-data=q;a=a-next;b=b-next;)c=b;结果:建立顺序表,456321continuec fxlesd2inlx2inbx2a b c d eg *abcde gg edcbaPiess anilkey tocontinue.2.已知由不具有头结点的单链表表示的线性表中， 含有三类字符的数据元素 （字母、 数字 和苴他字符） ，试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类 的字符，且利用原表中的结点空间，头结点可另辟空间。（文件

8、夹：分解单链表）算法：代码：添加按字母、数字、其它字符分解单链表算法void resolve(linklist*headJinklist*&lcUcrinklist*&digitJinklist*&othcr)linklist*p,*a,*b,*c,*al=letten*bl=digit*cl=other;p=head-next;while(p!=NULL)(if(p-data=48 & p-datadata=p-data;al-next=a;a-next=letter;al=a;)else if(p-data=65 & p-datadata=97 &a

9、mp; p-datadata=p-data;bl-next=b;b-next=digit;bl=b;else /其他c=(linklist*)malloc(sizeof(linklist); c-data=p-data;clnext=c;c-next=other;cl=c;p=p-next;结果：-C:USERSADM1NISTRATORDESKnhcdl234?eB12bu$输入数括：ahcdl234!y12bc予母表：123412数字妄ahcdbc其他小科Press any key to cuntInue实验二栈和队列一、实验目的1.熟悉栈和队列的顺序和链式存储结构2.掌握栈和队列的基本运

10、算3.能够利用栈和队列的基本运算完成栈和队列应用的运算二、实验内容1.设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出 栈与单链表中的另一半字符进行比较。）（文件夹：判字符串中心对称）2.假设以数组sequm存放循环队列的元素，同时设变量rear和quclcn分别指示循环队列 中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。 提示：队空的条件：sq-quelen=O：队满的条件：sq-quelen=mo（文件夹：循环队列）算法b代码判字符串中心对称添加判字符

11、串是否中心对称算法int symmetry(linklist*head,stack*s) int nj.a; linklist *r;n=length(head); r=head-next;for(i= 1 ;idata); r=r-next; while(r!=NULL)if(r-data=pop(s) r=r-next; a=l；elsea=0; break;)return(a);CzXDOCUMEITS AMD SETTIIGSADIibcdc cdcba cibudcf ggf edcba字符串Mabcdefggfedcba-中心对称Press any key to continue.

12、*C:DOCU1EHTS AHP SETTIKGS abcdefg ctbcdcf g字符串abcdefg*1是中心对称HPress any key to continue.2、循环队列入队出队 算法：添加入队算法void enqueue(qu *sq, datatype x) if(sq-quelenrear)sq-sequ| sq-quelen=x; sq-quelen+:else printf(H队列上溢”)；)添加出队算法datatype *dequeue(qu *sq)datatype *a;if(sq-quelen=O) printf(H队列下溢J; else(sq-quelen-

13、; a=sq-sequ+sq-quelen;rcturn(a);c *C:DOCUMENTS AMD SETTI!iGSADlI!iISTRATOR1.Enter Queue2.Delete Queue-1.Quit：1Fntei* the Bata :121.Enter Queue2.Delete Queue1.Quit：2121-Enter Queue2.Delotc Queue-1-Quit：-lPrc33 cmy he to cont inuc实验三串一、实验目的1.熟悉串的顺序存储结构2.掌握串的基本运算及应用二、实验内容1.串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存

14、在给泄的子串。（文 件夹：模式匹配）算法：添仙页序串的补素模式匹配算法int lndex( (seq5trlng*stseqstrlngsubs)int i=1.J=1;while(ilen & jlen)stri-1l=subs-strj-1)/D匹配FT移着Lr else设直下一轮比较的幵始1F(jsubs-len) )return(l); else return(O):结果C:USERSADMINISTRATORDESKTOPI输入虽：a b c d f e型人子吕：&b c尷己咸功!Press any key to continue2.若S是一个采用顺序结构存储的串，利

15、用C的库函数strlen和strcpy(或s(mcpy)编写 一算法voidSteDeIete(char*S,int Lint m),要求从S中删除从第i个字符开始的连续m个 字符。若istrlen(S),则没有字符被删除：若i+mstrlen(S),则将S中从位置i开始直 至末尾的字符均删除。(文件夹：删除子串)global members |(No members - Create New Class.,.弋结果istrlen(S)谕入串:abc drf s ahedrf gabedrfgPress any k&y to continue实验四数组一、实验目的1.熟悉数组的结构2.

16、掌握矩阵的压缩存储3.能够对数组和矩阵的压缩存储进行运算添加删除子串算法uoid strDelete(spqstring*Sint itint in) str) ); int j,k=9;For(j=1：j=n：j+*)strj-1; k+;C:USERSADMlNlSTRATORDESKTC输入虽abcdefg ahcdefg 1051=2adef gPress any key to continuei+mstrlen(S) C:USERSADMINISTRATORADESKTistrcpy(S-str ,aa);iF(i+nK=n) )s-ien=n-in;else if(in) S-le

17、n=i; elseS-len=n:输入串：cbcdrfs abcdrf g abedPress ansi key to continueC:USERSADMINISTRATORDESKTC二、实验内容1.若在矩阵Am“中存在一个元素Aij,其满足是第i行元素中最小值， 且又 是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Am“，设计算法求岀矩阵中所有马鞍点。（文件夹：找马鞍点）算法：代码：/添加找马鞍点算法void minmax(array*pa)int i=0, j=0, k, h=0;int Bm = 0;for (i二0; iUm; i+) /找岀每行的最小值p

18、a-min il =pa-Ai j; for(j=l;jminipa-Aij)pa-mini=pa-Aij;j二0;i=j=0;for (j二0; jAi j;for(i=0;imaxjAij)pa-maxjZ=pa-Aij;i二0;if (m=n) k=n;/k为行 列的最小值else k=m;for(i=0;i=k;i+)/比较行的最小值与列的最大值得出马鞍点for(j=0;jminLi=pa-maxj)Bh=pa-mini;h+；if (B 01=0)printf (w没有马鞍垫点n);elseprintfC马鞍点有：)；h=h-l;for (i=0; iUh; i+)/输出马鞍点pri

19、ntf (*%dn/z, Bi);结果：C:USERSADMINISTRATORDESKTOPMY FILESCigsTEST；22 33 11 44 55 77 19 65 5 H 88 IRA 9 77目鞍点有Press any key to continueJ C:USERSADMINISTRATORDESKTOPMY FILESCiSsTEST222 33 11 44 55 77 99 65 5 9 IB 8 88 Iflfl 9 77展有马鞍垫点anp key to cont inne2.A和B是两个nXn阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储 存入一维数组A和B

20、,编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。（文件夹：对称矩阵相乘）算法：对称矩阵以下三角，行的形式存储到一维矩阵向量中，则在矩阵中第i行j列的元素 （讐+j ij为：Ak,其中 匾+：代码：添加对称矩阵相乘算法void mult（array*pa）int i.j,k; datatype m;for(i=0;in;i+)for(j=0;jCij=O;for(k=0;k=k&k=j)从A B矩阵中找出需要的元素m=pa-Ai*(i+1 )/2+k pa-Bk*(k+1 )/2+j;else if(i=k&kA i*(i+l )/2+k *pa- B j * (j +1 )/2+k ;else if(i=j) m=pa-Ak*(k+1 )/2+i*pa-Bk*(k+1 )/2+j;m=pa-Ak*(k+1 )/2+i*pa-B j*(j+1 )/2+k; pa-Cil(j=pa.CiU+m;结果: