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<stdio.h>#include<malloc.h>#define MaxSize 5typedef char ElemT

3、ype;typedef struct qnodeElemType data;struct qnode*next;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

4、) free(p); p=r; r=p->next; free(q);int QueueLength(LiQueue*q)int n=0;QNode*p=q->front;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-

5、>next=NULL; if(q->rear=NULL) q->front=q->rear=s; else q->rear->next=s; q->rear=s; int deQueue(LiQueue*&q,ElemType&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-&

6、gt;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);extern void enQueue(LiQueue *&q,ElemType e);extern int deQueue(LiQueue *&q,ElemType &e);void main()

7、 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&quo

8、t;); else 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(!QueueE

9、mpty(q) deQueue(q,e); printf("%c",e); printf("n"); printf("(9)釋放鏈隊n"); ClearQueue(q);運算輸出結果如下所示：二、4.1實現順序運算程序如下所示：#include "stdafx.h"#include<stdio.h>#define MaxSize 100typedef structchar chMaxSize;int len;SqString;void StrAssign(SqString &str,char c

10、str)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;i<t.len;i+)s.chi=t.chi;s.len=t.len;int StrEqual(SqString s,SqString t)int same=1,i;if(s.len!=t.len)same=0;else for(i=0;i<s.len;i+)if(s.chi!=t.chi)same=0;return same;int StrLengt

11、h(SqString s)return s.len;SqString Concat(SqString s,SqString t)SqString str;int i;str.len=s.len+t.len;for(i=0;i<s.len;i+)str.chi=s.chi;for(i=0;i<t.len;i+)str.chs.len+i=t.chi;return str;SqString SubStr(SqString s,int i,int j)SqString str;int k;str.len=0;if(i<=0|i>s.len|j<0|i+j-1>s.

12、len)printf("參數不正確n");return str;for(k=i-1;k<i+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(i<=0|i>s1.len+1)printf("參數不正確n");return s1;for(j=0;j<i-1;j+)str.chj=s1.chj;for(j=0;j<s2.len;j+)

13、str.chi+j-1=s2.chj;for(j=i-1;j<s1.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(i<=0|i>s.len|i+j>s.len+1)printf("參數不正確n");return str;for(k=0;k<i-1;k+)str.chk=s.chk;for(k=i+j-1;k<s.len;k

14、+)str.chk-j=s.chk;str.len=s.len-j;return str;SqString RepStr(SqString s,int i,int j,SqString t)int k;SqString str;str.len=0;if(i<=0|i>s.len|i+j-1>s.len)printf("參數不正確n");return str;for(k=0;k<i-1;k+)str.chk=s.chk;for(k=0;k<t.len;k+)str.chi+k-1=t.chk;for(k=i+j-1;k<s.len;k+)s

15、tr.cht.len+k-j=s.chk;str.len=s.len-j+t.len;return str;void DispStr(SqString str)int i;if(str.len>0)for(i=0;i<str.len;i+)printf("%c",str.chi);printf("n");void main()SqString s,s1,s2,s3,s4;printf("(1)建立串s和串s1n");StrAssign(s,"abcdefghijklmn");StrAssign(s1,&

16、quot;xyz");printf("(2)輸出串s：");DispStr(s);printf("(3)串s的長度：%dn",StrLength(s);printf("(4)在串s的第9個字符插入串s1而產生s2n");s2=InsStr(s,9,s1);printf("(5)輸出串s2：");DispStr(s2);printf("(6)刪除串s的第2個字符開始的5個字符而產生s2n");s2=DelStr(s,2,3);printf("(7)輸出串s2：");DispStr(s2);printf("(8)將串s的第2個字符開始的5個字符替換成s1而產生s2n");s2=RepStr(s,2,5,s1);printf("(9)輸出串s2：");DispStr(s2);printf("(10)提取串s的第2個字符開始的10個字符而產生串s