串的基本操作演示實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上串的基本操作演示實驗報告 學號： 姓名： 班級：專心-專注-專業(yè)1 實驗環(huán)境問題描述： 如果語言沒有把串作為一個預先定義好的基本類型對待，又需要用該語言寫一個涉及串操作的軟件系統(tǒng)時，用戶必須自己實現(xiàn)串類型。試實現(xiàn)串類型，并寫一個串的基本操作的演示系統(tǒng)。 基本要求： 在教科書4.2.2節(jié)用堆分配存儲表示實現(xiàn)HString串的最小操作子集的基礎上，實現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作（不使用C語言本身提供的串函數(shù)）。參數(shù)合法性檢查必須嚴格。 說明：（在格式中，表示0個、1個或多個空格所組成的串。串標識表示一個內(nèi)部名或一個串文字。前者是一個串的唯一標識，是一種內(nèi)部形式的（而不是

2、字符形式的）標識符。后者是兩端由單引號括起來的僅可打印字符組成的序列。串內(nèi)每兩個連續(xù)的單引號表示一個單引號符。） 利用上述基本操作函數(shù)構造以下系統(tǒng)：它是一個命令解釋程序，循環(huán)往復地處理用戶鍵入的每一條命令，直至終止程序的命令為止。命令定義如下： （1） 賦值。格式：A串標識回車 用串標識所表示的值建立新串，并顯示新串的內(nèi)部名和串值。如：AHi！ （2） 判相等。 格式：E串標識1串標識2回車 若兩串相等，則顯示“EQUAL”，否則顯示“UNEQUAL”。 （3） 聯(lián)接。 格式：C串標識1串標識2回車 將兩串聯(lián)接產(chǎn)生結果串，它的內(nèi)部名和串值都顯示出來。 （4） 求長度 格式：L串標識回車 顯示串

3、的長度。 （5） 求子串 格式：S串標識+數(shù)1+數(shù)2回車 如果參數(shù)合法，則顯示子串的內(nèi)部名和串值。數(shù)不帶正負號。 （6）子串定位。 格式：I串標識1串標識2回車 顯示第二個串在第一個串中首次出現(xiàn)時的位置。 （7）串替換 格式：R串標識1串標識2串標識2回車 將第一個串中出現(xiàn)所有出現(xiàn)的第二個串用第三個串替換，顯示結果串的內(nèi)部名和串值，原串不變。 （0）退出 格式：Q回車 結束程序的運行。 二、實驗內(nèi)容編寫一個程序，實現(xiàn)順序串的各種基本運算，并在此基礎上設計一個主程序。具體如下：編寫棧的基本操作函數(shù)順序串類型定義如下所示：typedef struct nodechar data;struct no

4、de *next;linkstring;（1）串賦值 Assign(s,t)將一個字符串常量賦給串s,即生成一個其值等于t的串s（2）串復制 StrCopy(s,t)將串t賦給串s（3）計算串長度 StrLength(s)返回串s中字符個數(shù)（4）判斷串相等StrEqual(s,t)若兩個串s與t相等則返回1；否則返回0。（5）串連接 Concat(s,t) 返回由兩個串s和t連接在一起形成的新串。（6）求子串 index(s,j)返回找到串t在串s中的位置 （7）插入InsStr (s,i,t)將串t插入到串s的第i(1iStrLength(s)+1)個字符中,即將t的第一個字符作為s的第i個

5、字符,并返回產(chǎn)生的新串（8）串刪除 DelStr (s,i,j)從串s中刪去從第i(1iStrLength(s)個字符開始的長度為j的子串,并返回產(chǎn)生的新串。（9）串替換 RepStr (s,s1,s2)在串s中,將所有出現(xiàn)的子串s1均替換成s2。（10）輸出串DispStr(s)輸出串s的所有元素值（11） 判斷串是否為空 IsEmpty(s)（12） 輸入串inputchuan(char str100,linkstring *&s)輸入字符串str并將字符串傳遞給指針串s三：程序：#include<stdio.h>#include<iostream.h>#i

6、nclude<stdlib.h>typedef struct nodechar data;struct node *next;linkstring;void assign(linkstring *&s,char t)/將字符串t賦值給指針串s,并返回sint i=0;linkstring *q,*tc;s=(linkstring *)malloc(sizeof(linkstring);s->next=NULL;tc=s;/tc指向s串的最后一個結點while(ti!='0')/實現(xiàn)字符數(shù)組順序賦值到串sq=(linkstring *)malloc(si

7、zeof(linkstring);q->data=ti;tc->next=q;/使得s中與tc同地址的next指向q,使tc與q相連接tc=q;/tc直接指向qi+;tc->next=NULL;void strcopy(linkstring *&s,linkstring *t)/將t串賦值給s串并返回slinkstring *p=t->next,*q,*tc;s=(linkstring *)malloc(sizeof(linkstring);s->next=NULL;tc=s;/tc指向s串的最后一個結點while(p!=NULL)/實現(xiàn)字符數(shù)組順序賦值到

8、串sq=(linkstring *)malloc(sizeof(linkstring);q->data=p->data;tc->next=q;/使得s中與tc同地址的next指向q,使tc與q相連接tc=q;/tc直接指向qp=p->next;tc->next=NULL;int strlength(linkstring *s)/求s的長度int n=0;linkstring *p;p=s->next;while(p!=NULL)n+;p=p->next;return n;void dispstr(linkstring *s)/輸出串slinkstrin

9、g *p=s->next;while(p!=NULL)cout<<p->data;p=p->next;cout<<endl;int strequal(linkstring *s,linkstring *t)/判斷s串和t串是否相等linkstring *p,*q;p=s->next;q=t->next;while(p!=NULL&&q!=NULL)if(p->data!=q->data)return 0;p=p->next;q=q->next;if(p!=NULL|q!=NULL)return 0;e

10、lsereturn 1;linkstring *concat(linkstring *s,linkstring *t)/將t串連接到s串后linkstring *p,*q,*tc,*r;r=(linkstring *)malloc(sizeof(linkstring);r->next=NULL;tc=r;p=s->next;while(p!=NULL)q=(linkstring *)malloc(sizeof(linkstring);q->data=p->data;tc->next=q;tc=q;p=p->next;p=t->next;while(p!

11、=NULL)q=(linkstring *)malloc(sizeof(linkstring);q->data=p->data;tc->next=q;tc=q;p=p->next;tc->next=NULL;return r;int index(linkstring *s,linkstring *t)/找到串t在串s中的位置linkstring *p,*q,*p1;int i=0;p=s->next;while(p!=NULL)q=t->next;/q始終從頭開始與p進行比對if(p->data=q->data) p1=p;while(p1

12、!=NULL&&q!=NULL&&p1->data=q->data)p1=p1->next;q=q->next;if(q=NULL)return i;break;p=p->next;i+;return -1;int instr(linkstring *&s,int i,linkstring *t)/將t插入s串的第i個位置linkstring *q=s->next,*p=s,*r;int k;r=(linkstring *)malloc(sizeof(linkstring);strcopy(r,t);/p=r;/考慮到

13、如果k=1的情況r=r->next;/free(p);for(k=0;k<i;k+)if(q=NULL)return 0;p=q;q=q->next;p->next=r;while(r->next!=NULL)r=r->next;r->next=q;p=p->next;/s->next=p;return 1;int delstr(linkstring *&s,int i,int j)/刪除串s 中從第i個位置開始的j個字符int k;linkstring *p,*q;/q=s;p=s->next;for(k=0;k<i;

14、k+)/先找到第i個結點，讓q指向第i個結點，讓p指向第i+1個結點if(p=NULL)return 0;q=p;p=p->next;for(k=0;k<j;k+)if(p=NULL)return 0;p=p->next;q->next=p;return 1;void repstr(linkstring *&s,linkstring *t,linkstring *r)/將s中出現(xiàn)的t替換成rint i;i=index(s,t);while(i>=0)delstr(s,i,strlength(t);instr(s,i,r);i=index(s,t);void

15、 inputchuan(char str100,linkstring *&s)/輸入字符串str并將字符串傳遞給指針串scin>>str;assign(s,str);void main()linkstring *s,*t,*r;/也可以先定義多個串指針實現(xiàn)書上說的“顯示”“刪除”兩個功能；char str100,str1100,str2100;int i,n;cout<<"輸入要執(zhí)行操作的序號"<<endl;cout<<"1)賦值2)判相等3)連接4)求長度5)求子串6)子串定位7)串替換0)退出"

16、<<endl;cin>>n;while(n!=0)switch(n)case 1:cout<<"輸入要賦值的串："<<endl;inputchuan(str,s);dispstr(s);break;case 2:cout<<"輸入要判定是否相等的兩個串："<<endl;inputchuan(str1,s);inputchuan(str2,t);if(strequal(s,t)=1)cout<<"equal"<<endl;elsecout&l

17、t;<"unequal"<<endl;break;case 3:cout<<"輸入要連接的兩個串："<<endl;inputchuan(str1,s);inputchuan(str2,t);r=concat(s,t);dispstr(r);cout<<endl;break;case 4:cout<<"輸入要求長度的串："<<endl;inputchuan(str,s);cout<<strlength(s)<<endl;break;ca

18、se 5:break;case 6:cout<<"輸入第一個串并輸入要定位的串"<<endl;inputchuan(str1,s);inputchuan(str2,t);n=index(s,t);if(n=-1)cout<<"找不到"<<endl;elsecout<<n+1<<endl;break;case 7:cout<<"將第一個串中所有出現(xiàn)的第二個串用第三個串替代"<<endl;inputchuan(str,s);inputchuan(str1,t);inputchuan(str2,r);repstr(s,t,r);dispstr(s);break;cout<<"輸入1-7繼續(xù)，否則輸入0退出"<<endl;cin>>n;4、 實驗心得與小結1）熟悉串的定義和串的基本操作。2）掌握順序串的基本運算。3）加深對串數(shù)據(jù)結構的理解，逐步培養(yǎng)解決實際問題的編程能力。4）運用到了串的鏈式存儲結構，對鏈表也有了進一步提高。本次課程設計是對我們這一學期來數(shù)據(jù)結構課程學習成果的