数据结构-实验四-字符串、稀疏矩阵实验

1、实验编号：4四川师大数据结构实验报告2016年11月12_日实验四字符串、稀疏矩阵实验一实验目的及要求熟悉字符串类型的实现方法，并完成串的一些基本操作；掌握稀疏矩阵的三元组顺序表存储表示，并实现矩阵的转置运算。二实验内容编程实现两个串S1和S2的比较。（要求自己设计串的存储结构，并编写比较函数，不要调用系统提供的函数）编程实现稀疏矩阵的三元组顺序表示方法及基本操作的实现（建立、输出、转置等）。编程实现稀疏矩阵的十字链表存储表示及基本操作的实现（建立、输出等）。注：（2）必做，（1）（3）选做。三主要仪器设备及软件PC机DevC+,VisualC+,VS2010等四实验主要流程、基本操作或核心代

2、码、算法片段（该部分如不够填写，请另加附页）（1）编程实现两个串S1和S2的比较。（要求自己设计串的存储结构，并编写比较函数，不要调用系统提供的函数）a代码部分：/Main.cpp:#includeSString.hintmain()SStringT1,T2;inti,n;T10=T20=0;coutn;T10=n;aspuinjoj)(OlOll)JJOSH(ittmnpi)(Ol!=!)JOJ、:叨epZLjndmujnoogOEiuupiu：9ZTSZljndmujnoo(Jllup)(+!：u=!=!)JOJ、:叨ep11jndmujnoofor(inti=l；iT2i)(return

3、elseif(TliT2i)(returnreturn/SString.h:#includeusingnamespacestd;constintMAX=255;typedefunsignedcharSStringMAX+1;charCompare(SStringT1,SStringT2);A运行结果:inputT1size:5inputT1data:abcdeinputT2size：5inputT2data：abcdfTKT2Pressanykeytocontinue编程实现稀疏矩阵的三元组顺序表示方法及基本操作的实现(建立、输出、转置等)。代码部分：/Main.cpp#includeTSMa

4、trix.hintmain()TSMatrixT,M;intcount;coutv/输入矩阵的行数，列数，非零元个数：”；cinM.muM.nuM.tu;for(count=1;count=M.tu;count+)cout请输入第count个非零元的行数，列数，数据M.datacount.iM.datacount.jM.datacount.e;TransposeSMatrix(M,T);coutijeendl;for(count=1;count=T.tu;count+)coutT.datacount.iT.datacount.jT.datacount.eendl;return0;/TSMatr

5、ix.cpp#includeTSMatrix.hStatusTransposeSMatrix(TSMatrixM,TSMatrix&T)intcol,p,q;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;+col)for(p=1;p=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;returnOK;TSMatri.#includeusingnamespacestd;constintMAXSIZ

6、E=12500;constintOK=1;constintERROR=0;typedefintElemType;typedefintStatus;typedefstructinti,j;ElemTypee;Triple;typedefstructTripledataMAXSIZE+l;intmu,nu,tu;TSMatrix;StatusTransposeSMatrix(TSMatrixM,TSMatrix&T);运行结果：输入矩阵的行数，列数，非零元个数：76请输入第1个非零元的行数,列数,数据1212请输入第2个非零元的行数,列数,数据1?Q请输入第M个非零元的行数,列数,数据31-,：请

7、输入第4个非零元的行数,列数,数据3614请输入第5个非零元的行数,列数,数据4324请输入第6个非零元的行数,列数,数据5218请输入第7个非零元的行数,列数,数据6115请输入第g个非零元的行数,列数,数据64-7iJe13-3161521122518319342446-76314编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列)。代码部分：A：链式储存：/Main.cpp:#includeQNode.hintmain()LinkQueueQ;InitQueue(Q);Menu(Q);DestroyQueue(Q);return0;/QNode.cpp#inc

8、ludeQNode.hStatusInitQueue(LinkQueue&Q)/构造空队列Q.front=Q.rear=(QueuePrt)malloc(sizeof(QNode);if(!Q.front)exit(ERROR);Q.front-next=NULL;returnOK;StatusDestroyQueue(LinkQueue&Q)销毁队列Qwhile(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;returnOK;StatusEnQueue(LinkQueue&Q,QElemTypee)插入元素a为Q的新的队尾元

9、素QNode*p;p=(QueuePrt)malloc(sizeof(QNode);if(!p)exit(ERROR);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;StatusDeQueue(LinkQueue&Q,QElemType&e)删除Q的队头元素，用e返回其值QNode*p;if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;StatusQu

10、eueEmpty(LinkQueueQ)/判断对是否为空if(Q.front=Q.rear)returnERROR;returnOK;voidMenu(LinkQueue&Q)/输出选择界面intselect=1;QElemTypee;while(select)coutendl;cout请选择以下功能：endl;cout1,入队endl;cout2,出队endl;cout3,判断队空endl;cout0,退出程序endl;coutselect;switch(select)case0:break;8a输入入队数据e;if(EnQueue(Q,e)cout入队成功endl;break;if(DeQ

11、ueue(Q,e)coute出队endl;break;if(QueueEmpty(Q)cout此队不为空endl;elsecout此队为空endl;break;QNodeh#ifndefQNODE_H#defineQNODE_H#include#includeusingnamespacestd;constintOK=1;constintERROR=0;typedefintQElemType;typedefintStatus;typedefstructQNodeQElemTypedata;structQNode*next;QNode,*QueuePrt;typedefstructQueuePrt

12、front;QueuePrtrear;LinkQueue;StatusInitQueue(LinkQueue&Q);构造空队列StatusDestroyQueue(LinkQueue&Q);销毁队列UQStatusEnQueue(LinkQueue&Q,QElemType);/插入元素a为Q的新的队尾元素StatusDeQueue(LinkQueue&Q,QElemType&e);删除Q的队头元素，用e返回其值StatusQueueEmpty(LinkQueueQ);/判断对是否为空voidMenu(LinkQueue&Q);/输出选择界面#endif运行结果：B顺序存储：A代码部分：main

13、,cpp:#includeSqQueue.hintmain()SqQueueQ;if(InitQueue(Q)cout创建队成功endl;Menu(Q);DestroyQueue(Q);return0;SqQueue,cpp:#includeSqQueue.hStatusInitQueue(SqQueue&Q)/创建空队列Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType);if(!Q.base)exit(ERROR);Q.front=Q.rear=0;returnOK;StatusEnQueue(SqQueue&Q,QElemTypee)插入

14、元素e为Q的新队尾元素if(Q.rear+1)%MAXSIZE)=Q.front)returnERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;StatusDeQueue(SqQueue&Q,QElemType&e)删除Q的对头元素，用e返回其值。if(Q.front=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;returnOK;StatusSqQueueEmpty(SqQueueQ)判断Q是否为空if(Q.front=Q.rear)returnERR

15、OR;returnOK;StatusDestroyQueue(SqQueue&Q)/销毁栈Q.front=Q.rear=0;free(Q.base);returnOK;voidMenu(SqQueue&Q)/输出选择菜单intselect=1;QElemTypee;while(select)coutendl;cout请选择一下功能:endl;cout1,入队endl;cout2,出队endl;cout3,判断是否为空endl;cout0,退出程序endl;coutselect;switch(select)case0:break;coute;if(EnQueue(Q,e)cout入队成功endl

16、;elsecout队满endl;break;if(DeQueue(Q,e)coute出队endl;elsecout队空endl;break;if(SqQueueEmpty(Q)cout队未空endl;elsecout队空endl;break;SqQueue.h#ifndefSQQUEUE_H#defineSQQUEUE_H#include#includeusingnamespacestd;constintMAXSIZE=100;constintMORE=100;constintOK=1;constintERROR=0;typedefintQElemType;typedefintStatus;t

17、ypedefstructQElemType*base;intfront;intrear;SqQueue;StatusInitQueue(SqQueue&Q);创建空队列StatusEnQueue(SqQueue&Q,QElemType);/插入元素e为Q的新队尾元素StatusDeQueue(SqQueue&Q,QElemType&e);/删除Q的对头元素，用e返回其值。StatusSqQueueEmpty(SqQueueQ);/判断Q是否为空StatusDestroyQueue(SqQueue&Q);/销毁栈voidMenu(SqQueue&Q);/输出选择菜单#endif运行结果:创建队成

18、功3,0.队.认断空为百序曰鑫创建队成功3,0.队.认断空为百序曰鑫情选择一下功能;1.入队2,3.0,2,3.0,退出否为空(3)编程实现稀疏矩阵的十字链表存储表示及基本操作的实现(建立、输出等。代码部分：/CrossList.h#include#include#defineOK1;#defineERROR1;typedefintElemType;typedefintStatus;typedefstructOLNodeinti,j;ElemTypee;structOLNode*right,*down;OLNode,*OLink;typedefstructOLink*rhead,*chead;

19、intmu,nu,tu;CrossList;StatusCreateSMatrix_OL(CrossList&M);/CrossList.cpp#includeCrossList.hStatusCreateSMatrix_OL(CrossList&M)intm,n,t,i,j,e,k;OLNode*p,*q;/if(M)free(M);printf(mu,nu,tu:);scanf(%d%d%d,&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;M.rhead=(OLink*)malloc(m+1)*sizeof(OLink);if(!M.rhead)returnERROR;if(!(M.chead=(OLink*)malloc(n+1)*sizeof(OLink)returnERROR;for(k=1;k=M.mu;k+)M.rheadk=NULL;for(k=