数据结构实验参考

1、数据结构数据结构实验一实验一 顺序表的基本操作顺序表的基本操作实验目的实验目的: 1.熟悉 C 语言上机环境，进一步掌握 C 语言结构特点 2.掌握顺序表的逻辑结构和定义 3. 掌握顺序表的生成、插入、删除和查找等基本运算实验要求：实验要求： 1.完成算法设计和程序设计，并上机调试通过 2.完成实验报告，提供实验数据和结果 3.对插入和删除算法进行时间复杂度的估算实验内容实验内容:实现顺序表的基本操作，使得对于线性表实现顺序表的基本操作，使得对于线性表(6,9,14,23,28,50), 实现以实现以下功能下功能: 1.从键盘依次往顺序表中输入数据 2.在第 3 位插入数值 10,输出顺序表

2、3.删除第 4 位数值,输出整个顺序表. 4.查找表中是否有数据 24，有则返回其位置 5.输出线性表中第 i 个元素的值，位序 i 由用户通过键盘输入请在实验中完成以下函数定义：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) /向顺序表中输入数据void ShowSelect(); /显示用户提示界面运行后，用户界面如下：思考题：思考题：1.函数调用时，实参何时使用取内容运算符*，何时使用取地址运算符& ?2.试编写一个算法，可以删除顺序表中从第 i 个元素起的 k 个元素。在程序中实现算法并完成调用。参考代码参考代码 1 （秦锋格式定义）：/*线形表的顺序存储，用指针做参数传递，顺序表采用数组存储，定义参考秦锋数据结构中定义格式*/#include#in

4、clude #define MAXSIZE 50#define FALSE 0#define TRUE 1/*数据元素类型 ElemType 为 int 型*/typedef int ElemType;/*定义顺序表类型 SeqList 及指向顺序表的指针 PSeqList*/typedef struct ElemType dataMAXSIZE; /*存放线性表的数组*/ 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(输入数据不得超过 50 个！n);printf(输入顺序表中元素个数:n); scanf(%d,&PL-length); for(i=1;ilength;i+) printf(input the %

10、d number:,i); scanf(%d,&PL-datai-1); /*显示选择提示信息函数*/void ShowSelect() printf(n 请选择要执行的操作：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 请输入你想查找的数据:); 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);实验二实验二 链表的基本操作链表的基本操作实验目的实验目的: 1.进一步熟悉 C 语言上机环境，进一步掌握 C 语言结构特点 2. 掌握单链表的逻辑结构和定义 3. 掌握单链表的生成、插入、删除和查找等基本运算实验要求：实验要求： 1.完成算法设计和程序设计，并上机调试通过 2.完成实验报告，提供

14、实验数据和结果 3.对插入和删除算法进行时间复杂度的估算实验内容实验内容: 实现单链表的基本操作，使得对于线性表(6,9,14,23,28,50), 实现以下功能: 1.从键盘依次往顺序表中输入数据 2.在第 3 位插入数值 10,输出顺序表 3.删除第 4 位数值,输出整个顺序表. 4.查找表中是否有数据 24，有则返回其位置 5.输出线性表中第 i 个元素的值，位序 i 由用户通过键盘输入请在实验中完成以下函数定义并调用它们：LinkList Init_LinkList( ) /初始化单链表void Creat_List(LinkList L ,int 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) /实现单链表的逆置void Reverse_LinkList(LinkList

16、 L) 用户界面如图：实验小结及思考：实验小结及思考：1.总结单链表结构特点2.试编写算法，在一个带头结点的单链表中删除最小值结点参考代码参考代码/*单链表结构定义各书差不多，只名称有区别，本程序名称定义按秦峰版 */*本程序为带头结点单链表*/#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;/*初始化单链表，即产生一个带头结点的空表，创建成功则返回空表的头指针*/LinkList Init_List(void) LinkList L; L=(LinkList) malloc(sizeof(LNode); if(L) L-next=NULL; /产生空表，头结点的 next 域为空 return L; /*按逆序产生一个长度为 n 链表，参数为初始化的空链表，及线性表长度 n*/*每个元素依次插入在头结点后*/int Create_List(LinkList L,int n) int i; LinkList s; /*s 变量用于保存新结点地址*/ printf(生成有%d

18、 个元素的线性表:n,n); for(i=n;i0;i-) printf(请输入线性表中第 %d 个元素:n,i); /*逆序输入元素*/ s=(LinkList)malloc(sizeof(LNode); if(!s) printf(创建结点不成功n); return 0; scanf(%d,&s-data); s-next=L-next; L-next=s; return 1;/* 求单链表表长， 返回 L 中数据元素个数 */ 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(链表不存在或参数 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; /* 在带头结点的单链线性表 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) /* 在带头结点的单链线性表 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; /*以下函数为作业中常见练习，不是基本操作,也未在主函数中调用*/*删除单链表中多余的元素值相同的结点*/ 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(表中只有一个结点); 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; /*显示选择提示信息函数*/void ShowSelect() printf(n 请选择要执行的操作：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(请输入线性表中元素个数：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 请输入你想查找的数据:); 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);实验三实验三 线性表的应用线性表的应用 -稀疏多项式计算器稀疏多项式计算器(vc 环境，&符号)#include#include#define Null 0typedef struct LNode /* 项的表示,多项式的项作为 LinkList 的数据元素 */ int coef; /* 系数 */ int expn; /* 指数 */ struct LNode *next; LNode,*LinkList;typedef

28、 LinkList polynomial; /* 用带有表头结点的有序链表表示多项式*/void CreatePolyn(polynomial &L) /*按尾插法产生一个 n 项多项式*/int i,n; polynomial p,s;L=(polynomial)malloc(sizeof(LNode); L-next=Null;p=L;printf(请输入该多项式的总项数：n);scanf(%d,&n); for(i=1;icoef, &s-expn);p-next=s;p=s;p-next=Null; int ListLength(polynomial L) /*

29、 返回 L 中数据元素个数 */ int i=0; polynomial p=L-next; while(p) i+; p=p-next; return i; int LocateElem(polynomial L,int e)/* 返回 L 中 e 的数据元素的位序,若不存在,则返回值为0 */ int i=0; polynomial p=L-next; while(p) i+; if(p-expn=e) /* 找到这样的数据元素 */ 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); /按先系数，后指数的顺序显示一个多项式 printf(-); p=p-next; printf(n); /求一元多项式的导数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) / 按系数递增有序的多项式，执行相加操作，使之仍按系数递增有序，利用原表结构 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) /若两个多项式的项指数相同，则看其系数，若系数和为0，则两项结点空间都释放 r=pa; pa=pa-next; free(r); r=pb; pb=pb-next; free(pb); else /若系数和不为零，则将两项的系数相加 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 的结果:);Addpolyn(L,P);DispPolyn(L);第三章 栈和队列实验一实验一 栈及其应用栈及其应用实验目的：实验目的： 1.深入了解栈的特性 2.熟练掌握两种存储结构和基本运算的实现算法 3.了解栈空和栈满的判断条件 实验内容实验内容: 顺序栈实现将十进制整数转换为 r（2、8、16）进制数实验要求：实验

34、要求： 由用户通过键盘输入十进制整数 n 和要转换成的进制 r。参考代码参考代码 1：/*顺序栈结构利用数组实现-参数由指针传递*/*按秦峰版定义，不使用引用类型*/#include#include#include#define MAXSIZE 50typedef char ElemType;/*定义栈结构*/typedef struct ElemType dataMAXSIZE; int top;SeqStack,*PSeqStack;/*初始化栈，构造一个空栈，如果成功，则返回栈的地址*/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、*出栈操作，栈不空时，出栈一个元素，用参数*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; /*十进制转换成 r 进制（2,8,16）*/void Conversion(int num,int r) PSeqStack s; ElemType x; if(!r) printf(基数不能为 0); return; s=Init_SeqStack(); if(!s) printf(初始化栈空间失败); return; while(num) if(num%r9) Push_SeqStack(s,num%r+A-10); /*余数大于 9，则进

38、栈 ABCDEF*/ else Push_SeqStack(s,num%r+0); /*余数小于 10，则进栈数字字符*/ num=num/r; while(!Empty_SeqStack(s) Pop_SeqStack(s,&x); printf(%c,x); int main() int r, num;printf(请输入要转换的数据); scanf(%d,&num);printf(请输入要转换成几进制：);scanf(%d,&r);Conversion(num,r);getch(); /非程序一部分，Dev-C+环境要求 参考代码参考代码 2：/*利用顺序栈-清华

39、版定义-实现十进制转换为 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 带头结点的链栈实现十进制数转换为八进制数*/#define Null 0 struct stacknodeint data; str

43、uct stacknode *next; push(struct stacknode *s,int x) /*使一个值为 x 的数进栈*/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); /*头指针指向头结点*/ s-next=Null; scanf(%d,&N); while(N) push(s,N%8); /*余数进栈*/ N=N/8; while(s-ne

45、xt!=Null) data=gettop(s);printf(%dt,data); pop(s); 实验二：实验二： 队列及其应用队列及其应用实验目的：实验目的： 1.深入了解队列的特性 2.巩固对两种存储结构的掌握 实验内容实验内容: 利用循环队列输出 15 位菲波那契数实验要求：实验要求：1.掌握循环队列的类型定义2.掌握循环队列的出队、入队、初始化等基本操作3.掌握循环队列队列空、队列满的判断条件参考代码：参考代码：/*利用数组实现存储-秦峰版定义*/#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、验一： 串及其应用串及其应用实验目的：实验目的：1.深入了解串的特性 2.掌握串的定长表示方法实验内容实验内容: 利用串的定长存储表示实现串替换操作 StrRep， 如将“abcdefcdfg”中“cd”替换成“x”。结果为“abxefxfg”, 实验要求：实验要求：1.掌握串的基本概念，使用定长存储，利用0作为字符串结束标识。2.实现串的基本操作（插入，删除、模式匹配、求串长、输入、输出）等操作3.不得使用 C 中已有的字符串操作函数。4.使用到的函数定义如下： int Strlength(char *s) /求串长 void StrInput(char *s) /输入字符串：通过键盘输入字

48、符串，将字符串存放在 s 中 void StrDisp(char *s) /输出字符串：将字符数组 s 中的字符串输出 /串定位,返回从第 pos 个字符起，t 在 s 中首次出现的位置 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 中出现的所有与串 t 相等的不重叠子串，s 串值改变int StrRep(char *s,char *t,char *r) 参考代码参考代码 1：/实现串的基本操作中的串替换，如将“abcdefcdfg”中“cd”替换成“x” 。结果为“abxefxfg”,不得使用已有的字符串操作函数/本题采用定长顺序存储表示法 2，即用0表示字符串结束 #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;/输出字符串：将字符数组 s 中的字符串输出void StrDisp(char *s) int i=0; while(si!=0) printf(%c,si); i+; /串定位,返回从第 pos 个字符起，t 在 s 中首次出现的位置 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 中出现的所有与串 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 中出现位置 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 替换结果为：); StrDisp(source); getch();参考代码参考代码 2：/*堆存储，堆存储，KMP 算法算法 VC6.0 环境运行环境运行*/#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、设为空串*/ 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/*显示串内容*/void disp(HString S)int i;if(S.length=0) printf(字符串不存在);else for(i=0;iS.length;i+) /逐个字符输出，不能用 printf(%s),因为 StrAssign 函数中赋值完成后，没有给 S.ch 加字符串结束符； printf(%c,S.chi); / 如想使用%s，则赋值完成后，给最后一个字符后添加一个0.同学们可用自己试验/*模式匹配，返回值为子串 T 在主串 S 中第 pos 个字符之后的位置，若不存在，则返回值为 0. BF