2023年数据结构实验报告链串.pdf

《2023年数据结构实验报告链串.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告链串.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、宁波工程学院电信学院计算机教研室实验报告课程名称：数据结构 姓 名:_ 学 号:实验项目：链串的基本算法 班 级：计 科 102指导教师:B 期：20 2 3/1 0/1 3实验位置：电子楼二楼机房一 实验目的1）熟悉串的定义和串的基本操作。2）掌握链串的基本运算。3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有V i s ual C+6.0的计算机。三、实验内容编写一个程序，实现链串的各种基本运算，并在此基础上设计一个主程序。具体如下：编写栈的基本操作函数链串类型定义如下所示:typede f s t r uct s no d e ch a r data；st r

2、 u c t s n o de*ne x t；l i s t r ing;(1)串赋值 A ssign(s,t)将一个字符串常量赋给串S，即生成一个其值等于t的串S(2)串复制 S trC o py(s,t)将串t赋给串s(3 )计算串长度S trL en gth(s)返回串s 中字符个数(4)判断串相等 S trE qual(s,t)若两个串s与 t相等则返回1;否则返回0。(5)串连接 C o n c at(s,t)返回由两个串s 和 t连接在一起形成的新串。(6)求子串 S ub S tr(s,i ,j)返回串s 中从第i(l W iW S trL ength(s)个字符开始的、由连续

3、J个字符组成的子串。插入 I nsS tr(s,i ,t)将 串 t插入到串s 的 第 i (1 W iW S trL ength(s)+1 )个字符中，即将t的第一个字符作为s 的第i个字符，并返回产生的新串(8)串删除 D e I S tr(s,i,j)从 串 S中删去从第i(iw i W S trL ength(s)个字符开始的长度为j 的子串，并返回产生的新串。(9)串替换 R e pS tr(s,sl,s 2 )在串s 中，将所有出现的子串si均替换成s2。(1 0)输出串 D ispS tr(s)输出串s 的所有元素值(1 1)判 断 串 是 否 为 空 I sE mpty(s)编

4、写主函数调用上述函数实现下列操作：(1)建立串 s“ab c defg h i j k I mn,串 si xyz,串 t=h i jk”(2)复制串t到 tl,并输出tl 的长度(3)在 串 s 的第9个字符位置插入串s 1 而产生串s 2,并输出s2(4)删除s第 2个字符开始的5 个字符而产生串s3,并输出S 3(5)将 串 s 第 2个字符开始的3个字符替换成串si而产生串s4,并输出s4(6)提取串s 的第8个字符开始的4个字符而产生串S 5,并输出S 5(7)将 串 s 1 和串t连接起来而产生串s6,并输出s 6(8)比较串si和 s 5是否相等，输出结果程序清单：#in c 1

5、 ude#i n c Iudet yp e d e f struct s n odeoc h ar data;st r u c t snode*n e x t；li s t r i n g;/字符串赋值void s t r a ssig n(1 istring*&s,char c s t r)eint i；li s t ring*p;s=(l i s t ring*)mal 1 o c(siz e of(1 is t rin g);o r=s;for(i=0；cstr L i!八 0=i+)o p=(l i st r i ng*)m a 1 loc(s i ze o f(lis t r ing

6、)；p-data=cstri;r-n ext=p；r=P；0)ar-next=N U LL；)字符串复制v o i d s t r c opy(l i stri n g*&s,1 i str i n g *t)i str i ng*p=t-ne x t,*q,*r;s=(li s tring*)m a 1 1 oc(s ize o f(lis t r i n g);r=s;wh i le(p!=N ULL)o q=(listri n g*)mall o c(sizeof(1 i stri n g);o q-d a ta=pdata;。r-nex t=q;oo r=q;op=p-next;)r-

7、ne x t=N U LL;)/字符串长度i n t s tri e ng t h(l i str i ng*s)int i=0;listr i n g*p=s-nex t;owh i le(p!=NU L L)ooi+；p=p-next;。ret u rn i;/判断字符串是否相等int s t requ a l(li s t ri n g*s,1 i s t rin g*t)1 i s tr i n g*p=s-ne x t,*q=t-n e xt;whil e(p!=NULL&q!=NULL&p-data=qd a ta)p=p-next;叫=Q -n e x t;0)df(p=NU L

8、 L&q=NULL)o ret u m 1 ；e Ise。r etum 0;)字符串连接1 i string*co n cat(listring*s,lis t r i ng*t)lis t ri n g*s t r,*p=s-ne x t,*q,*r;s t r=(1 i s tr i ng*)ma 1 1 o c(si z e of(list r i n g)；r=str;owhile(p!=NULL)q=(listr i ng*)mallo c(si z eof(list r i n g);eqd a t a=p-dat a；r-ne x t=q;p=p-n ext;叩二t ne x t

9、；owhile(p!=NUL L)o q=(listring*)m a 1 1 o c(s izeof(1 ist r in g)；q-data=p-dat a;o r-next=q;oo r=q;p=p-n e xt;r next=NULL;o r etum s tr;)字符串的子串listr i ng*substr(l i st r in g*s,int i,int j)oint k;1 i str i ng*str,*p=s-ne x t,*q,*r；str=(list r ing*)m a ll oc(s i zeo f(1 ist r ing)；s t r-nex t=NULL;r=

10、str;oif(istrlength(s)|I j s tri e ngth(s)return str;ofor(k=0;kp=p-nex t；o f o r(k=l;k d a ta=p-d ata；o r-next=q;r=q；p=p-n ext；。r-ne x t=NU L L;return s t r；)字符串插入listring*inss t r(1 i string*s,int i,listr i n g*t)int k;listr i n g*str,*p=s-n e xt,*pl=t-next,qr;s t r=(lis t r i ng*)m a 1 1 o c(si z e

11、of(1 i s trin g);ostr-next=NULL;r=s t r;if(ist r 1 e n g th(s)+l)o”e t urn s t r;f o r(k=l;k data=p-d a ta;o r-n e x t=q；o r=q;p=p-n e x t;0)w h il e(p 1 !=NULL)。0 q=(1 is t r in g*)mal l o c(s iz e o f(l i s trin g);o q d a t a=p l-d a ta;o r-next=q;r 二q；pl=pl-next；)whil e(p!=NULL)o o q=(1 i string

12、*)mal 1 o c(siz e o f(1 i s tri n g);sq-d a t a=p-d a t a;。一 n e x t=q;o r=q；p=p-n e xt;)r-n ext=N U L L;r etu r n str;字符串删除lis t ring*d elstr(1 i s t r i ng*s,in t i,int j)oint k;lis t r i ng*s t r,*p=s-n e x ts tr=(li s tring*)ma 1 loc(s i z e o f(listr i ng)；s t r -next=NULL;”=str;i f(i st r leng

13、 t h(s)|j s tr 1 e n g t h(s)o retu r n st r;f or(k=0;k d a t a=p d a ta;r-n e x t=q;p=p-n e xt;)for(k=0;k next;whi 1 e(p!=N ULL)q=(listr i ng*)mallo c(size o f(listring)；q-d a t a =p d a ta;。可 next=q;”=q；p=p-n e x t;0rn e xt=NULL;r e t ur n str;)/字符串替换1 i stri n g*r eps t r(listr i ng*s,int i,int j

14、,li s tr i n g*t)i n t k；1 i string*str,*p=s n e xt,*p l=t-ne x t,*q,*r;str=(listring*)mall o c(s i z e o f(l istring)；st r-n e x t=NULL;r=str;if(istrlengt h(s)|jst r 1 ength(s)are t u r n str；ef o r(k=0；kdata=p-d a t a；rnext=q;0r=q；p=p-next;0)for(k=0;k next;w h ile (p 1!=NUL L)q=(listr i ng*)ma 1 l

15、oc(sizeof(1 i stri n g);q-d a t a=pl-d ata;。汴 n ext=q;r=q；p 1=pl-next；)while(p!=NULL)。q=(listring*)mallo c(siz e o f(1 istrin g);q-d a ta=p-d a t a；oor-n e x t=q；o r=q；p=p-n e x t；)r-next=N U LL;retur n str；字符串输出void d i s pstr(listring*s)o 1 i string*p=s-ne x t;while(p!=NULL)叩ri n t f(*%c”,p-data);

16、0p=p-n e x t;叩rintf(n);)判断字符串是否为空void emps t r(lis t ring*s)o i f(s-ne x t=NULL)。pr i ntf(字符串是空的！”)；e l s e。print f(字符串不为空!)v oid initstr(1 is t r i ng*&s)s=(lis t ri n g*)ma 1 loc(s i z e of(l i str i ng)；s-n e x t =NU L L;)主函数i n t main(v o id)1 i s tri n g*s s 3,*s4,*s 5,*s 6；i nt 1;st r a s sign

17、(s,abcdefg h ij k Im n);s t r as s i g n(s 1,M xyz);stra s sign(t,hijk );strc o py(tl,t);p rintf(输出 tl 的长度:%dn ，str 1 ength(t l);s 2=i n s s t r (s,9,s 1 )；printf(输出 s2:n)；disp s tr(s2);s 3=dels t r(s,2,5);pr i ntf(输出 s3:n H)；d i spst r(s3);s4=repst r(s,2,3,si)；p r in t f(输出 s 4:n);odisps t r(s4);s

18、5=subst r(s,8,4)；p r i n tf(输出 s5:n )；dispstr(s5);s 6=con c at(si,t);printf(输出 s6:nn);di s ps t r(s6);1 =s t r e qual(sl,s5);o i f(1=1)printf(M si 与 s5 相等!”)；0 e 1 s ep r i囚4%1与S5不相等!”）；o r e turn 0;运营结果:I D:选串Debug拣串.exe”救出s 2：abcdefghxyzijklnn输出s3：aghijklnn输出s4：axyzef ghijklnn输出s5：h ijk输出s6：xyzhij

19、ks i与s5不相等?Press any key to continue四 实验心得与小结这次上机的内容是实现链串的基本算法，跟前面学的链表的基本算法是差不多的，所以这次实验还是比较简朴的，但也曾出现过一点点小问题，直接把字符串赋值给指针 s=a b c d e f g h i j k l mn ;s 1=xy z ；t=h i j k ;结果出现如下错误：error C2440:*=:cannot conuert from char 15 to struct snodeerror C2440:=：cannot conuert from char 4 to struct snodeerror

20、C244G:=:cannot conuert from char 5 to struct snode-通过调用函数 v oid s t r as s ign(list r i ng*&s,c h ar c s t r )将其订正为 s tr a s sign(s,ab c d efghijk 1 m n );s trassign(sl,Mxyz*);st r as s ig n(tjh ijk)后没有错误;编译、组建都没有错误的情况下,s 2 是在串s 的第 9 个 字 符 位 置 插 入 串 s i 而 产 生 的，本 应 出 现 的 结 果 为abcdefghxyzijklnn可 运 营

21、时 却 出 现 如 下 的 结 果abcdef q h iiii.ik ln n查找了因素之后才发现在插入S 1 数据时,都把S的第九个字母的数据赋值给了 s2,*pl=sl-next；q-d a ta =p-d a ta;把错误改为q-d a ta=p l-d a ta；后运营对的。虽然链串的基本算法的操作还是比较简朴，但也会犯一些毛病，必须通过上机编译调试才干发现,上机之后才干把自认为对的代码重新纠正过来,从而有所进步。通过这次的上机实验，我熟悉了串的定义和串的基本操作，掌握了链串的基本运算，加深对串数据结构的理解并逐步培养解决实际问题的编程能力。五、指导教师评议成绩评估:3 指导教师署名:。