链队与顺序串的实现

数据结构与算法实验报告实验名称：链队与顺序串的实现班级：12软件工程1班姓名：常志慧学号：12130326类型：上机实验地点：鹤琴403日期：2013-5-6.一、实验目的：1.理解链队的特征，理解顺序串的特征2.用c语言设计好链队和顺序串的表示，并实现相关操作3.调试程序，编译运行并用数据测试程序4.熟悉c语言编程二、实验环境：1.PC机一台（带有VS6.0软件）三、实验内容和要求：1、用c语言设计好链队和顺序串的表示，并实现相关操作2、调试程序，编译运行并用数据测试程序3、认识和熟悉链队与顺序串4、通过分析算法实现相关函数，并与实验教材的代码做比较四、实验步骤：（对实验步骤的说明应该能够保证根据该说明即可重复完整的实验内容，得到正确结果。）1、对链队与顺序串的表示与相关算法做分析1）设计它们的结构体表示方法2）设计和实现相关运算函数2、在VS6.0环境下编译实现代码1）编辑源程序，达到调试编译运行的目的2）利用数据进行测试验证五、实验结果与分析（含程序、数据记录及分析和实验总结等）：一、3.2实现链队算法程序如下所示：#includestdafx.h#includestdio.h#includemalloc.h#defineMaxSize5typedefcharElemType;typedefstructqnode{ElemTypedata;structqnode*next;}QNode;typedefstruct{QNode*front;QNode*rear;}LiQueue;voidInitQueue(LiQueue*&q){q=(LiQueue*)malloc(sizeof(LiQueue));q-front=q-rear=NULL;}voidClearQueue(LiQueue*&q){QNode*p=q-front,*r;if(p!=NULL){r=p-next;while(r!=NULL){free(p);p=r;r=p-next;}}free(q);}intQueueLength(LiQueue*q){intn=0;QNode*p=q-front;while(p!=NULL){n++;p=p-next;}return(n);}intQueueEmpty(LiQueue*q){if(q-rear==NULL)return1;elsereturn0;}voidenQueue(LiQueue*&q,ElemTypee){QNode*s;s=(QNode*)malloc(sizeof(QNode));s-data=e;s-next=NULL;if(q-rear==NULL)q-front=q-rear=s;else{q-rear-next=s;q-rear=s;}}intdeQueue(LiQueue*&q,ElemType&e){QNode*t;if(q-rear==NULL)return0;if(q-front==q-rear){t=q-front;q-front=q-rear=NULL;}else{t=q-front;q-front=q-front-next;}e=t-data;free(t);return1;}externvoidInitQueue(LiQueue*&q);externvoidClearQueue(LiQueue*&q);externintQueueLength(LiQueue*q);externintQueueEmpty(LiQueue*q);externvoidenQueue(LiQueue*&q,ElemTypee);externintdeQueue(LiQueue*&q,ElemType&e);voidmain(){ElemTypee;LiQueue*q;printf((1)初始化链队q\n);InitQueue(q);printf((2)依次进链队元素a,b,c\n);enQueue(q,'a');enQueue(q,'b');enQueue(q,'c');printf((3)链队为%s\n,(QueueEmpty(q)?空:非空));if(deQueue(q,e)==0)printf(队空,不能出队\n);elseprintf((4)出队一个元素%c\n,e);printf((5)链队q的元素个数%d\n,QueueLength(q));printf((6)依次进链队元素d,e,f\n);enQueue(q,'d');enQueue(q,'e');enQueue(q,'f');printf((7)链队q的元素个数%d\n,QueueLength(q));printf((8)出链队序列:);while(!QueueEmpty(q)){deQueue(q,e);printf(%c,e);}printf(\n);printf((9)释放链队\n);ClearQueue(q);}运算输出结果如下所示：二、4.1实现顺序运算程序如下所示：#includestdafx.h#includestdio.h#defineMaxSize100typedefstruct{charch[MaxSize];intlen;}SqString;voidStrAssign(SqString&str,charcstr[]){inti;for(i=0;cstr[i]!='\0';i++)str.ch[i]=cstr[i];str.len=i;}voidStrCopy(SqString&s,SqStringt){inti;for(i=0;it.len;i++)s.ch[i]=t.ch[i];s.len=t.len;}intStrEqual(SqStrings,SqStringt){intsame=1,i;if(s.len!=t.len)same=0;else{for(i=0;is.len;i++)if(s.ch[i]!=t.ch[i])same=0;}returnsame;}intStrLength(SqStrings){returns.len;}SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;str.len=s.len+t.len;for(i=0;is.len;i++)str.ch[i]=s.ch[i];for(i=0;it.len;i++)str.ch[s.len+i]=t.ch[i];returnstr;}SqStringSubStr(SqStrings,inti,intj){SqStringstr;intk;str.len=0;if(i=0||is.len||j0||i+j-1s.len){printf(参数不正确\n);returnstr;}for(k=i-1;ki+j-1;k++)str.ch[k-i+1]=s.ch[k];str.len=j;returnstr;}SqStringInsStr(SqStrings1,inti,SqStrings2){intj;SqStringstr;str.len=0;if(i=0||is1.len+1){printf(参数不正确\n);returns1;}for(j=0;ji-1;j++)str.ch[j]=s1.ch[j];for(j=0;js2.len;j++)str.ch[i+j-1]=s2.ch[j];for(j=i-1;js1.len;j++)str.ch[s2.len+j]=s1.ch[j];str.len=s1.len+s2.len;returnstr;}SqStringDelStr(SqStrings,inti,intj){intk;SqStringstr;str.len=0;if(i=0||is.len||i+js.len+1){printf(参数不正确\n);returnstr;}for(k=0;ki-1;k++)str.ch[k]=s.ch[k];for(k=i+j-1;ks.len;k++)str.ch[k-j]=s.ch[k];str.len=s.len-j;returnstr;}SqStringRepStr(SqStrings,inti,intj,SqStringt){intk;SqStringstr;str.len=0;if(i=0||is.len||i+j-1s.len){printf(参数不正确\n);returnstr;}for(k=0;ki-1;k++)str.ch[k]=s.ch[k];for(k=0;kt.len;k++)str.ch[i+k-1]=t.ch[k];for(k=i+j-1;ks.len;k++)str.ch[t.len+k-j]=s.ch[k];str.len=s.len-j+t.len;returnstr;}voidDispStr(SqStringstr){inti;if(str.len0){for(i=0;istr.len;i++)printf(%c,str.ch[i]);printf(\n);}}voidmain(){SqStrings,s1,s2,s3,s4;printf((1)建立串s和串s1\n);StrAssign(s,abcdefghijklmn);StrAssign(s1,xyz);printf((2)输出串s：);DispStr(s);printf((3)串s的长度：%d\n,StrLength(s));printf((4)在串s的第9个字符插入串s1而产生s2\n);s2=InsStr(s,9,s1);printf((5)输出串s2：);DispStr(s2);printf((6)删除串s的第2个字符开始的5个字符而产生s2\n);s2=DelStr(s,2,3);printf((7)输出串s2：);DispStr(s2);printf((8)将串s的第2个字符开始的5个字符替换成s1而产生s2\n);s2=RepStr(s,2,5,s1);printf((9)输出串s2：);DispStr(s2);printf((10)提取串s的第2个字符开始的10个字符而产生串s3\n);s3=SubStr(s,2,10);printf((11)输出串s3：);DispStr(s3);printf((12)将串s1和串s2连接起来而产生串s4\n);s4=Concat(s1,s2);printf((13)输出串s4：);DispStr(s4);}运算输出结果如下所示：实验总结：六：思考题：学生用户名密码liweiguostuliweiguostu