链队与顺序串的实现

1、 数据结构与算法 实验报告实验名称：链队与顺序串的实现班 级：12软件工程1班姓 名：常志慧学 号：类 型：上机实验地点：鹤琴403日 期：2013-5-6.一、实验目的：1. 理解链队的特征，理解顺序串的特征2. 用c语言设计好链队和顺序串的表示，并实现相关操作3. 调试程序，编译运行并用数据测试程序4. 熟悉c语言编程二、实验环境：1. PC机一台（带有VS 6.0软件）三、实验内容和要求：1、用c语言设计好链队和顺序串的表示，并实现相关操作2、调试程序，编译运行并用数据测试程序3、认识和熟悉链队与顺序串4、通过分析算法实现相关函数，并与实验教材的代码做比较四、实验步骤：（对实验步骤的说明

2、应该能够保证根据该说明即可重复完整的实验内容，得到正确结果。）1、 对链队与顺序串的表示与相关算法做分析1） 设计它们的结构体表示方法2）设计和实现相关运算函数2、在VS6.0环境下编译实现代码1）编辑源程序，达到调试编译运行的目的2）利用数据进行测试验证五、实验结果与分析（含程序、数据记录及分析和实验总结等）：一、3.2实现链队算法程序如下所示 ：#include stdafx.h#include#include#define MaxSize 5typedef char ElemType;typedef struct qnodeElemType data;struct qnode*next;

3、QNode;typedef struct QNode*front; QNode*rear;LiQueue;void InitQueue(LiQueue *&q) q=(LiQueue*)malloc(sizeof(LiQueue); q-front=q-rear=NULL;void ClearQueue(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);int QueueLength(LiQueue*q)int n=0;QNode*p=q-fr

4、ont;while(p!=NULL) n+; p=p-next;return(n);int QueueEmpty(LiQueue *q)if(q-rear=NULL)return 1;elsereturn 0;void enQueue(LiQueue *&q,ElemType e) 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; int deQueue(LiQueue*&q,ElemTy

5、pe&e) QNode *t; if(q-rear=NULL) return 0; 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); return 1;extern void InitQueue(LiQueue *&q);extern void ClearQueue(LiQueue *&q);extern int QueueLength(LiQueue *q);extern int QueueEmpty(LiQueue *q);ext

6、ern void enQueue(LiQueue *&q,ElemType e);extern int deQueue(LiQueue *&q,ElemType &e);void main() ElemType e; LiQueue *q; printf(1)初始化链队qn); InitQueue(q); printf(2)依次进链队元素a,b,cn); enQueue(q,a); enQueue(q,b); enQueue(q,c); printf(3)链队为%sn,(QueueEmpty(q)?空:非空); if(deQueue(q,e)=0) printf(队空,不能出队n); else

7、 printf(4)出队一个元素%cn,e); printf(5)链队q的元素个数%dn,QueueLength(q); printf(6)依次进链队元素d,e,fn); enQueue(q,d); enQueue(q,e); enQueue(q,f); printf(7)链队q的元素个数%dn,QueueLength(q); printf(8)出链队序列:); while(!QueueEmpty(q) deQueue(q,e); printf(%c,e); printf(n); printf(9)释放链队n); ClearQueue(q);运算输出结果如下所示：二、4.1实现顺序运算程序如下

8、所示：#include stdafx.h#include#define MaxSize 100typedef structchar chMaxSize;int len;SqString;void StrAssign(SqString &str,char cstr)int i;for(i=0;cstri!=0;i+)str.chi=cstri;str.len=i;void StrCopy(SqString &s,SqString t)int i;for(i=0;it.len;i+)s.chi=t.chi;s.len=t.len;int StrEqual(SqString s,SqString t

9、)int same=1,i;if(s.len!=t.len)same=0;else for(i=0;is.len;i+)if(s.chi!=t.chi)same=0;return same;int StrLength(SqString s)return s.len;SqString Concat(SqString s,SqString t)SqString str;int i;str.len=s.len+t.len;for(i=0;is.len;i+)str.chi=s.chi;for(i=0;it.len;i+)str.chs.len+i=t.chi;return str;SqString

10、SubStr(SqString s,int i,int j)SqString str;int k;str.len=0;if(is.len|js.len)printf(参数不正确n);return str;for(k=i-1;ki+j-1;k+)str.chk-i+1=s.chk;str.len=j;return str;SqString InsStr(SqString s1,int i,SqString s2)int j;SqString str;str.len=0;if(is1.len+1)printf(参数不正确n);return s1;for(j=0;ji-1;j+)str.chj=s1

11、.chj;for(j=0;js2.len;j+)str.chi+j-1=s2.chj;for(j=i-1;js1.len;j+)str.chs2.len+j=s1.chj;str.len=s1.len+s2.len;return str;SqString DelStr(SqString s,int i,int j)int k;SqString str;str.len=0;if(is.len|i+js.len+1)printf(参数不正确n);return str;for(k=0;ki-1;k+)str.chk=s.chk;for(k=i+j-1;ks.len;k+)str.chk-j=s.chk;str.len=s.len-j;return str;SqString RepStr(SqString s,int i,int j,SqString t)int k;SqS