數(shù)據(jù)結(jié)構(gòu)實驗參考

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)實驗一實驗一 順序表的基本操作順序表的基本操作實驗?zāi)康膶嶒災(zāi)康? 1.熟悉 C 語言上機環(huán)境，進一步掌握 C 語言結(jié)構(gòu)特點 2.掌握順序表的邏輯結(jié)構(gòu)和定義 3. 掌握順序表的生成、插入、刪除和查找等基本運算實驗要求：實驗要求： 1.完成算法設(shè)計和程序設(shè)計，并上機調(diào)試通過 2.完成實驗報告，提供實驗數(shù)據(jù)和結(jié)果 3.對插入和刪除算法進行時間復雜度的估算實驗內(nèi)容實驗內(nèi)容:實現(xiàn)順序表的基本操作，使得對于線性表實現(xiàn)順序表的基本操作，使得對于線性表(6,9,14,23,28,50), 實現(xiàn)以實現(xiàn)以下功能下功能: 1.從鍵盤依次往順序表中輸入數(shù)據(jù) 2.在第 3 位插入數(shù)值 10,輸出順序表

2、3.刪除第 4 位數(shù)值,輸出整個順序表. 4.查找表中是否有數(shù)據(jù) 24，有則返回其位置 5.輸出線性表中第 i 個元素的值，位序 i 由用戶通過鍵盤輸入請在實驗中完成以下函數(shù)定義：PSeqList Init_SeqList( ) /初始化順序表int Length_List (SeqList L) /求順序表長void Disp_List(SeqList L) /輸出順序表 int Locate_List(SeqList L,ElemType x) /在順序表中檢索查找 xint Insert_List(PSeqList PL,int i,ElemType x)/向表中第 i 個元素前插入新元

3、素 xint Delete_List(PSeqList PL,int i) /刪除第 i 個元素void Creat_List(PSeqList PL) /向順序表中輸入數(shù)據(jù)void ShowSelect(); /顯示用戶提示界面運行后，用戶界面如下：思考題：思考題：1.函數(shù)調(diào)用時，實參何時使用取內(nèi)容運算符*，何時使用取地址運算符& ?2.試編寫一個算法，可以刪除順序表中從第 i 個元素起的 k 個元素。在程序中實現(xiàn)算法并完成調(diào)用。參考代碼參考代碼 1 （秦鋒格式定義）：/*線形表的順序存儲，用指針做參數(shù)傳遞，順序表采用數(shù)組存儲，定義參考秦鋒數(shù)據(jù)結(jié)構(gòu)中定義格式*/#include#in

4、clude #define MAXSIZE 50#define FALSE 0#define TRUE 1/*數(shù)據(jù)元素類型 ElemType 為 int 型*/typedef int ElemType;/*定義順序表類型 SeqList 及指向順序表的指針 PSeqList*/typedef struct ElemType dataMAXSIZE; /*存放線性表的數(shù)組*/ int length; /* length 是順序表的長度*/ SeqList, *PSeqList;/*初始化順序表*/PSeqList Init_SeqList( ) PSeqList PL; PL=( PSeqLis

5、t) malloc (sizeof(SeqList); if(PL!=NULL) PL-length=0; else printf(out of space!n);return (PL);/* 清空順序表 */ SeqList Clear_List (SeqList L) L.length=0; return L; /* 求順序表長度 */ int Length_List (SeqList L) return(L.length); /*遍歷輸出順序表*/void Disp_List(SeqList L) int i; if(L.length=0) printf(順序表為空n);elseprin

6、tf(順序表中元素為：n); for(i=0;iL.length;i+) printf(%dt,L.datai); printf(n); /*檢索查找，在線性表中查找元素 x，并返回其位置，若查找不成功，則返回 0*/int Locate_List(SeqList L,ElemType x) int i=0; while(i=L.length) return 0; else return(i+1);/*向順序表第 i 個元素前插入元素 x，插入成功返回 1，不成功返回 0*/int Insert_List(PSeqList PL,int i,ElemType x) int j; if(!PL)

7、printf(順序表不存在！);return 0; if(iPL-length+1) printf(插入位置不正確!n); return 0; for(j=PL-length-1;j=i-1;j-) PL-dataj+1=PL-dataj; PL-datai-1=x; PL-length+; return 1;/*在線性表中插入元素 x，使得線性表仍然有序*/int insert(PSeqList PL,ElemType x) int i,j; i=PL-length-1;while(xdatai) i-; for(j=PL-length-1;ji;j-) PL-dataj+1=PL-data

8、j; PL-datai+1=x; PL-length+; return 1;/*刪除線性表中第 i 個元素,成功刪除元素，返回 1，否則返回 0*/int Delete_List(PSeqList PL,int i) int j; if(!PL)printf(順序表不存在！);return 0; if(iPL-length) printf(刪除位置不正確!n); return 0; for(j=i;jlength-1;j+) PL-dataj-1=PL-dataj;PL-length-;return 1;/* 刪除線性表中從第 i 個元素起 k 個元素*/int delk(PSeqList L

9、,int i,int k) int j; if(iL-length) printf(error!); return 0; else for(j=i+k-1;jlength;j+) L-dataj-k=L-dataj; L-length=L-length-k; return 1; /*向順序表中順序輸入元素*/ void Creat_List(PSeqList PL)int i;printf(輸入數(shù)據(jù)不得超過 50 個！n);printf(輸入順序表中元素個數(shù):n); scanf(%d,&PL-length); for(i=1;ilength;i+) printf(input the %

10、d number:,i); scanf(%d,&PL-datai-1); /*顯示選擇提示信息函數(shù)*/void ShowSelect() printf(n 請選擇要執(zhí)行的操作：n); printf(-n); printf( 1-初始化n); printf( 2-為順序表輸入元素n); printf( 3-求順序表長度n);printf( 4-遍歷輸出順序表n); printf( 5-在順序表中檢索查找n); printf( 6-向順序表中插入元素n);printf( 7-從順序表中刪除元素n); printf( 0- 退出n); printf(-n); printf(please in

11、put number 07 nn);int main(void)PSeqList PL=NULL;int i,x,flag; int len; /*表示順序表長*/ int select; /*select 變量表示用戶的選擇項*/ShowSelect();scanf(%d,&select);while(select!=0)switch(select)case 1: PL=Init_SeqList( ); break; case 2: Creat_List(PL);break; case 3: len=Length_List(*PL); printf(順序表長為%dn,len);bre

12、ak; case 4: Disp_List(*PL);break; case 5: printf(n 請輸入你想查找的數(shù)據(jù):); scanf(%d,&x); flag= Locate_List(*PL, x); if(flag) printf(該元素在順序表中的位置是：%dn,flag) ; else printf(該元素在順序表中不存在); break; case 6: printf(請輸入要插入的元素的值和位置，用空格分隔：n); scanf(%d %d,&x,&i); flag=Insert_List(PL,i,x); if(flag) printf(插入操作成功

13、); break; case 7: printf(請輸入要刪除的元素的位置：n); scanf(%d,&i); flag= Delete_List(PL,i); if(flag) printf(刪除操作成功); break;ShowSelect();scanf(%d,&select);實驗二實驗二 鏈表的基本操作鏈表的基本操作實驗?zāi)康膶嶒災(zāi)康? 1.進一步熟悉 C 語言上機環(huán)境，進一步掌握 C 語言結(jié)構(gòu)特點 2. 掌握單鏈表的邏輯結(jié)構(gòu)和定義 3. 掌握單鏈表的生成、插入、刪除和查找等基本運算實驗要求：實驗要求： 1.完成算法設(shè)計和程序設(shè)計，并上機調(diào)試通過 2.完成實驗報告，提供

14、實驗數(shù)據(jù)和結(jié)果 3.對插入和刪除算法進行時間復雜度的估算實驗內(nèi)容實驗內(nèi)容: 實現(xiàn)單鏈表的基本操作，使得對于線性表(6,9,14,23,28,50), 實現(xiàn)以下功能: 1.從鍵盤依次往順序表中輸入數(shù)據(jù) 2.在第 3 位插入數(shù)值 10,輸出順序表 3.刪除第 4 位數(shù)值,輸出整個順序表. 4.查找表中是否有數(shù)據(jù) 24，有則返回其位置 5.輸出線性表中第 i 個元素的值，位序 i 由用戶通過鍵盤輸入請在實驗中完成以下函數(shù)定義并調(diào)用它們：LinkList Init_LinkList( ) /初始化單鏈表void Creat_List(LinkList L ,int n) / 按逆序產(chǎn)生一個鏈表長度為

15、nint Length_List (LinkList L ) /求單鏈表表長void Disp_List(LinkList L) /依次輸出單鏈表中元素 /在單鏈表中檢索查找 x，找不到返回 0，否則返回在線性表中的位序int Locate_List(LinkList L,ElemType x) /向表中第 i 個元素前插入新元素 xint Insert_List(LinkList L,int i,ElemType x) /刪除單鏈表中第 i 個元素int Delete_List(LinkList L,int i) /實現(xiàn)單鏈表的逆置void Reverse_LinkList(LinkList

16、 L) 用戶界面如圖：實驗小結(jié)及思考：實驗小結(jié)及思考：1.總結(jié)單鏈表結(jié)構(gòu)特點2.試編寫算法，在一個帶頭結(jié)點的單鏈表中刪除最小值結(jié)點參考代碼參考代碼/*單鏈表結(jié)構(gòu)定義各書差不多，只名稱有區(qū)別，本程序名稱定義按秦峰版 */*本程序為帶頭結(jié)點單鏈表*/#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define Null 0typedef int ElemType; typedef struct LNode ElemType data; struct LNode *next; LNode ,*LinkL

17、ist;/*初始化單鏈表，即產(chǎn)生一個帶頭結(jié)點的空表，創(chuàng)建成功則返回空表的頭指針*/LinkList Init_List(void) LinkList L; L=(LinkList) malloc(sizeof(LNode); if(L) L-next=NULL; /產(chǎn)生空表，頭結(jié)點的 next 域為空 return L; /*按逆序產(chǎn)生一個長度為 n 鏈表，參數(shù)為初始化的空鏈表，及線性表長度 n*/*每個元素依次插入在頭結(jié)點后*/int Create_List(LinkList L,int n) int i; LinkList s; /*s 變量用于保存新結(jié)點地址*/ printf(生成有%d

18、 個元素的線性表:n,n); for(i=n;i0;i-) printf(請輸入線性表中第 %d 個元素:n,i); /*逆序輸入元素*/ s=(LinkList)malloc(sizeof(LNode); if(!s) printf(創(chuàng)建結(jié)點不成功n); return 0; scanf(%d,&s-data); s-next=L-next; L-next=s; return 1;/* 求單鏈表表長， 返回 L 中數(shù)據(jù)元素個數(shù) */ int Length_List(LinkList L) int i=0; LinkList p=L-next; while(p) i+; p=p-next

19、; return i; /* 當按位置查找元素，第 i 個元素存在時,其值賦給 e 并返回 1,否則返回 0 */ int GetElem_List(LinkList L,int i,ElemType *e) int j=0; LinkList p=L; while(p&jnext; j+; if(!p|ji) printf(鏈表不存在或參數(shù) i 錯); return 0; *e=p-data; /* 取第 i 個元素 */ return 1; /* 按元素查找，查找鏈表中是否存在值為 e 的元素，存在，則返回 L 中第一個 e 元素的位序,若不存在,則返回值為 0 */ int Lo

20、cate_List(LinkList L,ElemType e) int i=0; LinkList p=L; while(p&p-data!=e) p=p-next; i+; if(p) return i; else return 0; /* 在帶頭結(jié)點的單鏈線性表 L 中第 i 個位置之前插入元素 e */int Insert_List(LinkList L,int i,ElemType e) int j=0; LinkList p=L,s; while(p&jnext; j+; if(!p|ji-1) return ERROR; s=(LinkList)malloc(si

21、zeof(struct LNode); s-data=e; s-next=p-next; p-next=s; return OK; int Delete_List(LinkList L,int i,ElemType *e) /* 在帶頭結(jié)點的單鏈線性表 L 中，刪除第 i 個元素,并由 e 返回其值 */ int j=0; LinkList p=L,q; while(p-next&jnext; j+; if(!p-next|ji-1) return 0; q=p-next; p-next=q-next; *e=q-data; free(q); return 1; int Disp_Li

22、st(LinkList L)/*顯示單鏈表*/ LinkList p=L-next; if(p=Null) printf(單鏈表為空表); else printf(輸出單鏈表:n); while(p!=Null) printf(%d,p-data); printf(-); p=p-next; printf(n); return 1; /*以下函數(shù)為作業(yè)中常見練習，不是基本操作,也未在主函數(shù)中調(diào)用*/*刪除單鏈表中多余的元素值相同的結(jié)點*/ void DelRepeat_List(LinkList L) LinkList p,h,pre; h=L-next; if(h=NULL) printf(

23、是一個空表); return; p=L-next-next; if(p=NULL) printf(表中只有一個結(jié)點); return; while(h-next!=NULL) pre=h; p=pre-next; while(p) if(h-data=p-data) pre-next=p-next; free(p); p=pre-next; else pre=p; p=p-next; h=h-next; /*顯示選擇提示信息函數(shù)*/void ShowSelect() printf(n 請選擇要執(zhí)行的操作：n); printf(-n); printf( 1-初始化n); printf( 2-逆序

24、輸入元素n); printf( 3-求單鏈表長度n);printf( 4-遍歷輸出順序表n); printf( 5-在單鏈表中檢索查找n); printf( 6-向單鏈表中插入元素n);printf( 7-從單鏈表中刪除元素n); printf( 0- 退出n); printf(-n); printf(please input number 07 nn);int main(void)LinkList PL=NULL;int i,x,flag; int len; /*表示單鏈表長*/ int select; /*select 變量表示用戶的選擇項*/ShowSelect();scanf(%d,&

25、amp;select);while(select!=0)switch(select)case 1: PL=Init_List(); break; case 2: printf(請輸入線性表中元素個數(shù)：n);scanf(%d,&len);Create_List(PL,len);break; case 3: len=Length_List(PL); printf(單鏈表表長為%dn,len);break; case 4: Disp_List(PL);break; case 5: printf(n 請輸入你想查找的數(shù)據(jù):); scanf(%d,&x); i= Locate_List(

26、PL, x); if(flag) printf(該元素在順序表中的位置是：%dn,i) ; else printf(該元素在順序表中不存在); break; case 6: printf(請輸入要插入的元素的值和位置，用空格分隔：n); scanf(%d %d,&x,&i); flag=Insert_List(PL,i,x); if(flag) printf(插入操作成功); break; case 7: printf(請輸入要刪除的元素的位置：n); scanf(%d,&i); flag= Delete_List(PL,i,&x); if(flag) prin

27、tf(刪除操作成功); break; case 8: DelRepeat_List(PL); ShowSelect();scanf(%d,&select);實驗三實驗三 線性表的應(yīng)用線性表的應(yīng)用 -稀疏多項式計算器稀疏多項式計算器(vc 環(huán)境，&符號)#include#include#define Null 0typedef struct LNode /* 項的表示,多項式的項作為 LinkList 的數(shù)據(jù)元素 */ int coef; /* 系數(shù) */ int expn; /* 指數(shù) */ struct LNode *next; LNode,*LinkList;typedef

28、 LinkList polynomial; /* 用帶有表頭結(jié)點的有序鏈表表示多項式*/void CreatePolyn(polynomial &L) /*按尾插法產(chǎn)生一個 n 項多項式*/int i,n; polynomial p,s;L=(polynomial)malloc(sizeof(LNode); L-next=Null;p=L;printf(請輸入該多項式的總項數(shù)：n);scanf(%d,&n); for(i=1;icoef, &s-expn);p-next=s;p=s;p-next=Null; int ListLength(polynomial L) /*

29、 返回 L 中數(shù)據(jù)元素個數(shù) */ int i=0; polynomial p=L-next; while(p) i+; p=p-next; return i; int LocateElem(polynomial L,int e)/* 返回 L 中 e 的數(shù)據(jù)元素的位序,若不存在,則返回值為0 */ int i=0; polynomial p=L-next; while(p) i+; if(p-expn=e) /* 找到這樣的數(shù)據(jù)元素 */ return i; p=p-next; return 0; void DispPolyn(polynomial L)/*顯示多項式表*/ LinkList

30、p=L-next; if(p=Null) printf(the list is not exit!); elseprintf(多項式共%d 項：, ListLength(L); while(p!=Null) printf(%d,%d,p-coef,p-expn); /按先系數(shù)，后指數(shù)的順序顯示一個多項式 printf(-); p=p-next; printf(n); /求一元多項式的導數(shù)void Polyn(polynomial &La)polynomial p=La-next,q=La; while(p) if(p-expn!=0) p-coef =(p-coef)*(p-expn)

31、; p-expn -; p=p-next ; else q-next =p-next; p=p-next ; void Addpolyn(polynomial &La, polynomial &Lb) / 按系數(shù)遞增有序的多項式，執(zhí)行相加操作，使之仍按系數(shù)遞增有序，利用原表結(jié)構(gòu) LinkList pa=La-next,pb=Lb-next,pc,r; pc=La; La-next =Null;while(pa&pb) if(pa-expnexpn) pc-next=pa; pc=pa; pa=pa-next; else if(pa-expnpb-expn) pc-nex

32、t=pb; pc=pb; pb=pb-next; else if(pa-coef+pb-coef=0) /若兩個多項式的項指數(shù)相同，則看其系數(shù)，若系數(shù)和為0，則兩項結(jié)點空間都釋放 r=pa; pa=pa-next; free(r); r=pb; pb=pb-next; free(pb); else /若系數(shù)和不為零，則將兩項的系數(shù)相加 pc-next=pa; pa-coef=pa-coef+pb-coef ; pc=pa; pa=pa-next;r=pb; pb=pb-next;free(pb); if(pa) pc-next=pa;else pc-next=pb;void main()pol

33、ynomial L=Null,P=Null ;printf(輸入第一個多項式(L)：n );CreatePolyn(L);printf( 輸入第二個多項式(P)：n );CreatePolyn(P);DispPolyn(L);DispPolyn(P);printf( L+P 的結(jié)果:);Addpolyn(L,P);DispPolyn(L);第三章 棧和隊列實驗一實驗一 棧及其應(yīng)用棧及其應(yīng)用實驗?zāi)康模簩嶒災(zāi)康模?1.深入了解棧的特性 2.熟練掌握兩種存儲結(jié)構(gòu)和基本運算的實現(xiàn)算法 3.了解棧空和棧滿的判斷條件 實驗內(nèi)容實驗內(nèi)容: 順序棧實現(xiàn)將十進制整數(shù)轉(zhuǎn)換為 r（2、8、16）進制數(shù)實驗要求：實驗

34、要求： 由用戶通過鍵盤輸入十進制整數(shù) n 和要轉(zhuǎn)換成的進制 r。參考代碼參考代碼 1：/*順序棧結(jié)構(gòu)利用數(shù)組實現(xiàn)-參數(shù)由指針傳遞*/*按秦峰版定義，不使用引用類型*/#include#include#include#define MAXSIZE 50typedef char ElemType;/*定義棧結(jié)構(gòu)*/typedef struct ElemType dataMAXSIZE; int top;SeqStack,*PSeqStack;/*初始化棧，構(gòu)造一個空棧，如果成功，則返回棧的地址*/PSeqStack Init_SeqStack() PSeqStack s; s=(PSeqStack

35、)malloc(sizeof(SeqStack); if(s) s-top=-1; return s;/* 判斷棧是否為空，如果為空，則返回 1，否則返回 0*/int Empty_SeqStack(PSeqStack s)if(s-top=-1) return 1; else return 0;/*入棧操作，棧不滿時，入棧一個元素，成功返回 1，失敗返回 0*/int Push_SeqStack(PSeqStack s,ElemType x)if(s-top=MAXSIZE-1 ) return 0;else s-top=s-top+1; s-datas-top=x; return 1; /

36、*出棧操作，棧不空時，出棧一個元素，用參數(shù)*x 保存，成功返回 1，失敗返回 0*/int Pop_SeqStack(PSeqStack s,ElemType *x)if(Empty_SeqStack(s) return 0;else *x=s-datas-top; s-top=s-top-1; return 1; /*取棧頂元素操作，棧不空時，獲取棧頂元素，成功返回 1，失敗返回 0*/int GetTop_SeqStack(PSeqStack s,ElemType *x) if(Empty_SeqStack(s) return 0;else *x=s-datas-top; return 1

37、;/*銷毀棧*/void Destroy_SeqStack(PSeqStack *s)if(*s) free(*s);*s=NULL;return; /*十進制轉(zhuǎn)換成 r 進制（2,8,16）*/void Conversion(int num,int r) PSeqStack s; ElemType x; if(!r) printf(基數(shù)不能為 0); return; s=Init_SeqStack(); if(!s) printf(初始化?？臻g失敗); return; while(num) if(num%r9) Push_SeqStack(s,num%r+A-10); /*余數(shù)大于 9，則進

38、棧 ABCDEF*/ else Push_SeqStack(s,num%r+0); /*余數(shù)小于 10，則進棧數(shù)字字符*/ num=num/r; while(!Empty_SeqStack(s) Pop_SeqStack(s,&x); printf(%c,x); int main() int r, num;printf(請輸入要轉(zhuǎn)換的數(shù)據(jù)); scanf(%d,&num);printf(請輸入要轉(zhuǎn)換成幾進制：);scanf(%d,&r);Conversion(num,r);getch(); /非程序一部分，Dev-C+環(huán)境要求 參考代碼參考代碼 2：/*利用順序棧-清華

39、版定義-實現(xiàn)十進制轉(zhuǎn)換為 R 進制*/#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0#define Null 0typedef int status;typedef int elemtype;typedef structelemtype *base;elemtype *top; int stacksize; sqstack;status initstack(sqstack *s)s-base=(elemtype *)malloc(STACK_INIT_SIZE*siz

40、eof(elemtype);if(s-base=Null)printf(error); exit(0);s-top=s-base;s-stacksize=STACK_INIT_SIZE;return(OK);status stackempty(sqstack *s)if(s-top=s-base) return OK; else return ERROR;void push(sqstack *s,elemtype e)if(s-top-s-base=s-stacksize ) s-base=(elemtype *)realloc(s-base,(s-stacksize+ STACKINCREM

41、ENT)*sizeof(elemtype); if(!s-base) exit(0);s-top=s-base+s-stacksize;s-stacksize+= STACKINCREMENT; *(s-top)=e;s-top+;void pop(sqstack *s,elemtype *e)if(s-top=s-base) printf(underflow!n); else *e=*(-s-top);status gettop(sqstack *s,elemtype *e)*e=*(s-top-1);void conversion()sqstack s; int N,R,data,pope

42、lem; initstack(&s); printf(“input N and R:n”); scanf(%d,%d,&N,&R); while(N) push(&s,N%R); N=N/R; while(!stackempty(&s) gettop(&s,&data);printf(%dt,data); pop(&s,&popelem); main()conversion();/*利用 l 帶頭結(jié)點的鏈棧實現(xiàn)十進制數(shù)轉(zhuǎn)換為八進制數(shù)*/#define Null 0 struct stacknodeint data; str

43、uct stacknode *next; push(struct stacknode *s,int x) /*使一個值為 x 的數(shù)進棧*/struct stacknode *p;p=(struct stacknode *) malloc(sizeof(struct stacknode);p-data=x;p-next=s-next; s-next=p;int pop(struct stacknode *s) /*出棧操作*/struct stacknode *p; p=s-next; if(s-next=Null) return 0; s-next=p-next; free(p); retur

44、n 1;int gettop(struct stacknode *s) /*取棧頂元素*/ if(s-next=Null) printf(no data exit); return -1; return s-next-data;main()struct stacknode *s; int N,data;s=(struct stacknode *) malloc(sizeof(struct stacknode); /*頭指針指向頭結(jié)點*/ s-next=Null; scanf(%d,&N); while(N) push(s,N%8); /*余數(shù)進棧*/ N=N/8; while(s-ne

45、xt!=Null) data=gettop(s);printf(%dt,data); pop(s); 實驗二：實驗二： 隊列及其應(yīng)用隊列及其應(yīng)用實驗?zāi)康模簩嶒災(zāi)康模?1.深入了解隊列的特性 2.鞏固對兩種存儲結(jié)構(gòu)的掌握 實驗內(nèi)容實驗內(nèi)容: 利用循環(huán)隊列輸出 15 位菲波那契數(shù)實驗要求：實驗要求：1.掌握循環(huán)隊列的類型定義2.掌握循環(huán)隊列的出隊、入隊、初始化等基本操作3.掌握循環(huán)隊列隊列空、隊列滿的判斷條件參考代碼：參考代碼：/*利用數(shù)組實現(xiàn)存儲-秦峰版定義*/#define maxsize 6typedef structint *base; int front; int rear;squeue

46、;main()squeue Q;int i=0,n;Q.base=(int *)malloc(maxsize*sizeof(int);Q.front=0;Q.base0=1;Q.base1=1;Q.rear=2;while(i!=15) Q.baseQ.rear=Q.baseQ.front+Q.base(Q.front+1)%maxsize; Q.rear=(Q.rear+1)%maxsize; n=Q.baseQ.front; if(i%3=0) printf(n); printf(%5d,n); Q.front=(Q.front+1)%maxsize; i+; 第四章第四章 串串實驗一：實

47、驗一： 串及其應(yīng)用串及其應(yīng)用實驗?zāi)康模簩嶒災(zāi)康模?.深入了解串的特性 2.掌握串的定長表示方法實驗內(nèi)容實驗內(nèi)容: 利用串的定長存儲表示實現(xiàn)串替換操作 StrRep， 如將“abcdefcdfg”中“cd”替換成“x”。結(jié)果為“abxefxfg”, 實驗要求：實驗要求：1.掌握串的基本概念，使用定長存儲，利用0作為字符串結(jié)束標識。2.實現(xiàn)串的基本操作（插入，刪除、模式匹配、求串長、輸入、輸出）等操作3.不得使用 C 中已有的字符串操作函數(shù)。4.使用到的函數(shù)定義如下： int Strlength(char *s) /求串長 void StrInput(char *s) /輸入字符串：通過鍵盤輸入字

48、符串，將字符串存放在 s 中 void StrDisp(char *s) /輸出字符串：將字符數(shù)組 s 中的字符串輸出 /串定位,返回從第 pos 個字符起，t 在 s 中首次出現(xiàn)的位置 BF 算法 int StrIndex(char *s, int pos, char *t) /串插入,在 s 的第 i 位處插入串 t ,s 串值改變 ，i 在1,Strlength(s)間 int StrInsert(char *s,int i,char *t) /串刪除，從 s 中第 i 位刪除長為 len 的字符串，i 在1,Strlength(s)間int StrDelete(char *s,int

49、i,int len) /串替換，用 r 替換 s 中出現(xiàn)的所有與串 t 相等的不重疊子串，s 串值改變int StrRep(char *s,char *t,char *r) 參考代碼參考代碼 1：/實現(xiàn)串的基本操作中的串替換，如將“abcdefcdfg”中“cd”替換成“x” 。結(jié)果為“abxefxfg”,不得使用已有的字符串操作函數(shù)/本題采用定長順序存儲表示法 2，即用0表示字符串結(jié)束 #include#define MAXSIZE 80/求串長int Strlength(char *s) int i=0; while(si!=0) i+; return i; /輸入字符串：通過鍵盤輸入字符

50、串，將字符串存放在 s 中void StrInput(char *s)int i=0;char ch; scanf(%c,&ch);while(ch!=n) si=ch; i+; scanf(%c,&ch); si=0;/輸出字符串：將字符數(shù)組 s 中的字符串輸出void StrDisp(char *s) int i=0; while(si!=0) printf(%c,si); i+; /串定位,返回從第 pos 個字符起，t 在 s 中首次出現(xiàn)的位置 BF 算法 int StrIndex(char *s,int pos,char *t) int i=pos-1,j=0; wh

51、ile(iStrlength(s)&jStrlength(t) if(si=tj) i+; j+; else i=i-j+1; j=0; if(j=Strlength(t) return(i-j+1); /返回在串中的位置，不是下標 else return -1; /串插入,在 s 的第 i 位處插入串 t ,s 串值改變 ，i 在1,Strlength(s)間 int StrInsert(char *s,int i,char *t) int j=0; int slen=Strlength(s); int tlen=Strlength(t); if(i=MAXSIZE) printf(

52、存儲空間不夠！); return 0; for(j=slen-1;j=i-1;j-) sj+tlen=sj; for(j=0;jslen) return 0; for(j=i-1+len;jslen;j+) sj-len=sj; sslen-len=0; return 1; /串替換，用 r 替換 s 中出現(xiàn)的所有與串 t 相等的不重疊子串，s 串值改變int StrRep(char *s,char *t,char *r) int slen=Strlength(s); int tlen=Strlength(t); int rlen=Strlength(r); int index=-1; /串

53、t 在 s 中出現(xiàn)位置 index=StrIndex(s,1,t); /從 s 中第一個字符開始查找字符串 t if(index=-1) return 0; do StrDelete(s,index,tlen); StrInsert(s,index,r); index=StrIndex(s, index+rlen,t); while(index!=-1); return 1; int main(void) char source80; char target20; char replace20; printf(n 請輸入源字符串：); StrInput(source); printf(n 請輸

54、入在源字符串中查找的目標字符串：); StrInput(target); printf(n 請輸入替換字符串：); StrInput(replace); StrRep(source,target,replace); printf(n 替換結(jié)果為：); StrDisp(source); getch();參考代碼參考代碼 2：/*堆存儲，堆存儲，KMP 算法算法 VC6.0 環(huán)境運行環(huán)境運行*/#include#include#include#include#define MAXSTRLEN 255 #define NULL 0int next255;typedef struct char *ch

55、; int length;HString;/*串賦值，將字符串常量 chars 賦值給串 T*/int StrAssign(HString &T, char *chars) int n=0,i;char *ch;for (n=0,ch=chars ; *ch!=0; n+,ch+);if(!n) T.ch=NULL; T.length=0; return 1;T.ch=(char *)malloc(n*sizeof(char)+1); if(!T.ch) T.length=0; printf(溢出); exit(0); else for(i=0;in;i+) T.chi=charsi;

56、 T.length=n; return 1; /StrAssign/*求串長，返回值為串 S 的長度*/ int StrLength(HString S) return S.length; /StrLength/*比較串 S 和 T，若相同為 0*/int StrCompare(HString &S,HString &T) int i; for(i=0;iS.length& iT.length;i+) if(S.chi!=T.chi) return S.chi-T.chi; return S.length-T.length; /StrCompare/*置空串，將串 S

57、設(shè)為空串*/ int ClearString(HString &S) if (S.ch) free (S.ch); S.ch=NULL; S.length=0; return 1; / ClearString/*連接串，將 S1 和 S2 連接成一個新串 T*/int Concat(HString &T,HString S1,HString S2) int i; if(T.ch) free(T.ch); if(!(T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char) printf(溢出!); return 0; for(i=

58、0;iS1.length;i+) T.chi=S1.chi; for(i=0;iS2.length;i+) T.chi+S1.length=S2.chi; T.length=S1.length+S2.length; return 1; /Concat/*求子串，子串 Sub 為主串 S 中從第 pos 個字符起長度為 len 的子串*/ int SubString(HString &Sub,HString S,int pos,int len) int i,j; if(posS.length | lenS.length-pos+1) return 0; if(Sub.ch) free(S

59、ub.ch); if(!len) Sub.ch=NULL; Sub.length=0; else Sub.ch=(char*) malloc(len *sizeof(char)+1); for(i=0,j=pos-1;j=pos+len-2;i+,j+) Sub.chi=S.chj; Sub.length=len; return 1; /SubString /*插入串，在字符串 S 中從第 pos 個字符前插入字符串 T*/int strInsert(HString &S,int pos,HString T) int j;if(posS.length+1) printf(插入子串的位置

60、不合法); return 0; S.ch=(char *) realloc(S.ch,(S.length+T.length)*sizeof(char); if(!S.ch) printf(空間分配不成功，插入操作失敗); return 0; for(j=S.length-1;j=pos-1;j-) S.chj+T.length=S.chj;for(j=0;jT.length;j+) S.chj+pos-1=T.chj;S.length+=T.length;return 1;/strInsert/*顯示串內(nèi)容*/void disp(HString S)int i;if(S.length=0) printf(字符串不存在);else for(i=0;iS.length;i+) /逐個字符輸出，不能用 printf(%s),因為 StrAssign 函數(shù)中賦值完成后，沒有給 S.ch 加字符串結(jié)束符； printf(%c,S.chi); / 如想使用%s，則賦值完成后，給最后一個字符后添加一個0.同學們可用自己試驗/*模式匹配，返回值為子串 T 在主串 S 中第 pos 個字符之后的位置，若不存在，則返回值為 0. BF