数据结构-顺序串基本操作实验报告

实验日期2010.5.10 教师签字成绩实验报告【实验名称】第四章串的基本操作及应用【实验目的】1、熟悉将算法转换成程序代码的过程。

2、了解串的逻辑结构特性，熟练掌握串顺序存储结构的C 语言描述方法。

3、熟练掌握串的基本操作：求长度、串的连接、插入、删除等，掌握串的存取特性。

【实验原理】1.串可以可以有三种存储方式，分别为顺序存储、堆分配存储、链式存储，串的基本操作在这三种存储方式下操作。

2.串的模式匹配KMP算法在每一趟匹配过程中出现字符不等时，不需回溯指针，而是利用已经得到的部分匹配结果的结果将模式向右滑动尽可能远的一段距离，继续进行比较。

【实验内容】1.串的顺序存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等）#include<stdio.h>#include<iostream.h>#include<malloc.h>#include<string.h>#define SIZE 20struct HString{char ch[SIZE];int length;};void StrInsert(HString &s,int pos,HString t){int i,j;if(pos<1||pos>s.length+1)cout<<"ERROR!";if(t.length){for(i=s.length-1;i>=pos-1;--i)s.ch[i+t.length]=s.ch[i];for(j=0;j<=t.length-1;j++)s.ch[pos-1+j]=t.ch[j];s.length+=t.length;}}void StrDelete(HString &s,int pos,int len){int i;int v=pos-1;if(pos<1||pos>s.length||len<0||len>s.length-pos+1)cout<<"ERROR!";for(i=pos+len-1;i<=s.length-1;i++)s.ch[v++]=s.ch[i];s.length-=len;}void StrAssign(HString &t,char chars[]){int i;char *c;for(i=0,c=chars;*c;++i,++c);if(!i){t.length=0;}else{for(int j=0;j<i;j++)t.ch[j]=chars[j];t.length=i;}}int StrLen(HString &s){return s.length;}int StrCompare(HString &s,HString t){for(int i=0;i<s.length&&i<t.length;i++){if(s.ch[i]!=t.ch[i])return (int)(t.ch[i]-s.ch[i]);}return s.length-t.length;}void Concat(HString &t,HString s1,HString s2){int i=s1.length+s2.length;for(i=0;i<s1.length;i++)t.ch[i]=s1.ch[i];t.length=s1.length+s2.length;for(i=s1.length;i<t.length;i++)t.ch[i]=s2.ch[i-s1.length];}int SubString(HString &sub,HString s,int pos,int len) {if(pos<1||pos>s.length||len<0||len>s.length-pos+1) {cout<<"ERROR!"<<endl;return 0;}if(!len){sub.length=0;}else{int i=len;for(i=0;i<len;i++)sub.ch[i]=s.ch[pos+i-1];sub.length=len;}}void Display(HString &t){for(int i=0;i<=t.length-1;i++)cout<<t.ch[i];cout<<endl;}void main(){int i;char s[20];do{cout<<"选择您要进行的串的基本操作:"<<endl;cout<<"1.插入"<<endl<<"2.删除"<<endl<<"3.串连结"<<endl<<"4.取子串"<<endl<<"5.串比较"<<endl<<"6.求串长"<<endl<<"7.结束"<<endl;cin>>i;switch(i){case 1:{HString s,t;int pos;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<endl;cout<<"请输入要插入的串t:";cin>>t.ch;StrAssign(t,t.ch);cout<<endl;cout<<"请输入你所要插入的位置:";cin>>pos;StrInsert(s,pos,t);cout<<"插入之后串变为:";Display(s);break;}case 2:{HString s;int pos,len;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<"请输入你所要删除串的首位置为:";cin>>pos;cout<<"请输入你需要删除的串的长度:";cin>>len;StrDelete(s,pos,len);cout<<"删除之后串变为:";Display(s);break;}case 3:{HString s1,s2,t;cout<<"请输入串s1:";cin>>s1.ch;StrAssign(s1,s1.ch);cout<<"请输入串s2:";cin>>s2.ch;StrAssign(s2,s2.ch);Concat(t,s1,s2);cout<<"s1与s2合并后的串为:";Display(t);break;}case 4:{HString sub,s;int pos,len;cout<<"请输入主串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<"请输入所取原串的起始位置pos:";cin>>pos;cout<<"请输入子串的长度len:";cin>>len;SubString(sub,s,pos,len);cout<<"取出的子串为:";Display(sub);break;}case 5:{HString s,t;int value;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<"请输入串t:";cin>>t.ch;StrAssign(t,t.ch);value=StrCompare(s,t);if(value>0) cout<<"串s大于串t"<<endl;else if(value==0) cout<<"串s等于串t"<<endl;else cout<<"串s小于串t"<<endl;cout<<endl;break;}case 6:HString s;char *chars;int val;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);val=StrLen(s);cout<<"串的长度为:"<<val<<endl;break;case 7:cout<<"操作结束!"<<endl;break;default:cout<<"输入错误!请重新输入!"<<endl;break;}}while(i!=7);}2.串的堆分配存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等）#include<stdio.h>#include<iostream.h>#include<malloc.h>#include<string.h>struct HString{char *ch;int length;};void StrInsert(HString &s,int pos,HString t){int i,j;if(pos<1||pos>s.length+1)cout<<"ERROR!";if(t.length){s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char));for(i=s.length-1;i>=pos-1;--i)s.ch[i+t.length]=s.ch[i];for(j=0;j<=t.length-1;j++)s.ch[pos-1+j]=t.ch[j];s.length+=t.length;}}void StrDelete(HString &s,int pos,int len){int i;int v=pos-1;if(pos<1||pos>s.length||len<0||len>s.length-pos+1)cout<<"ERROR!";for(i=pos+len-1;i<=s.length-1;i++)s.ch[v++]=s.ch[i];s.length-=len;}void StrAssign(HString &t,char *chars){int i;char *c;for(i=0,c=chars;*c;++i,++c);if(!i){t.ch=NULL;t.length=0;}else{t.ch=(char *)malloc(i*sizeof(char));for(int j=0;j<i;j++)t.ch[j]=chars[j];t.length=i;}}int StrLen(HString &s){return s.length;}int StrCompare(HString &s,HString t){for(int i=0;i<s.length&&i<t.length;i++){if(s.ch[i]!=t.ch[i])return (int)(t.ch[i]-s.ch[i]);}return s.length-t.length;}void Concat(HString &t,HString s1,HString s2){int i=s1.length+s2.length;t.ch=(char *)malloc(i*sizeof(char));for(i=0;i<s1.length;i++)t.ch[i]=s1.ch[i];t.length=s1.length+s2.length;for(i=s1.length;i<t.length;i++)t.ch[i]=s2.ch[i-s1.length];}int SubString(HString &sub,HString s,int pos,int len){if(pos<1||pos>s.length||len<0||len>s.length-pos+1){cout<<"ERROR!"<<endl;return 0;}if(!len){sub.ch=NULL;sub.length=0;}else{int i=len;sub.ch=(char *)malloc(i*sizeof(char));for(i=0;i<len;i++)sub.ch[i]=s.ch[pos+i-1];sub.length=len;}}void Display(HString &t){for(int i=0;i<=t.length-1;i++)cout<<t.ch[i];cout<<endl;}void main(){int i;char s[20];cout<<"选择您要进行的串的基本操作:"<<endl;do{cout<<"1.插入"<<endl<<"2.删除"<<endl<<"3.串连结"<<endl<<"4.取子串"<<endl<<"5.串比较"<<endl<<"6.求串长"<<endl<<"7.结束"<<endl;cin>>i;switch(i){case 1:{HString s,t;char a[20],b[20];char *sa,*sb;int pos;cout<<"请输入串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<endl;cout<<"请输入要插入的串t:";cin>>b;sb=b;StrAssign(t,sb);cout<<endl;cout<<"请输入你所要插入的位置:";cin>>pos;StrInsert(s,pos,t);cout<<"插入之后串变为:";Display(s);break;}case 2:{HString s;char str[20];char *chars;int pos,len;cout<<"请输入串s:";cin>>str;chars=str;StrAssign(s,chars);cout<<"请输入你所要删除串的首位置为:";cin>>pos;cout<<endl;cout<<"请输入你需要删除的串的长度:";cin>>len;cout<<endl;StrDelete(s,pos,len);cout<<"删除之后串变为:";Display(s);break;}case 3:{HString s1,s2,t;char a[20],b[20];char *sa,*sb;cout<<"请输入串s1:";cin>>a;sa=a;StrAssign(s1,sa);cout<<"请输入串s2:";cin>>b;sb=b;StrAssign(s2,sb);Concat(t,s1,s2);cout<<"s1与s2合并后:";Display(t);break;}case 4:{HString sub,s;char a[20];char *sa;int pos,len;cout<<"请输入主串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<"请输入所取原串的起始位置pos:";cin>>pos;cout<<"请输入子串的长度len:";cin>>len;SubString(sub,s,pos,len);cout<<"该子串为:";Display(sub);break;}case 5:{HString s,t;int value;char a[20],b[20];char *sa,*sb;cout<<"请输入串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<"请输入串t:";cin>>b;sb=b;StrAssign(t,sb);value=StrCompare(s,t);if(value>0) cout<<"串s大于串t"<<endl;else if(value==0) cout<<"串s等于串t"<<endl;else cout<<"串s小于串t"<<endl;cout<<endl;break;}case 6:HString s;char str[20];char *chars;int val;cout<<"请输入串s:";cin>>str;chars=str;StrAssign(s,chars);val=StrLen(s);cout<<"串的长度为:"<<val<<endl;break;case 7:cout<<"操作结束!"<<endl;break;default:cout<<"输入错误!请重新输入!"<<endl;break;}}while(i!=7);3.KMP算法的C实现#include<iostream.h>#include<malloc.h>#include<string.h>struct HString{char *ch;int length;};void StrAssign(HString &t,char *chars){int i;char *c;for(i=0,c=chars;*c;++i,++c);if(!i){t.ch=NULL;t.length=0;}else{t.ch=(char *)malloc(i*sizeof(char));for(int j=0;j<i;j++)t.ch[j]=chars[j];t.length=i;}}void get_next(HString s,int next[]){int i,j;i=1;j=0;next[1]=0;while(i<s.length){if(j==0||s.ch[i-1]==s.ch[j-1]){i++;j++;next[i]=j;}else j=next[j];}for(i=1;next[i]!='\0';i++)cout<<next[i]<<" ";}int Index(HString s,HString t,int pos){int i=pos;int j=1;int next[20];get_next(t,next);while(i<=s.length&&j<=t.length){if(s.ch[i-1]==t.ch[j-1]||j==0){ ++i;++j;}else{j=next[j];}}if(j>t.length)return i-t.length;else return 0;}void Display(HString t){for(int i=0;i<t.length;i++)cout<<t.ch[i];cout<<endl;}void main(){ HString s,t;int pos,k;char a[20],b[20];char *sa,*sb;cout<<"请输入主串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<"请输入模式串t:";cin>>b;sb=b;StrAssign(t,sb);cout<<"请输入起始位置pos:";cin>>pos;k=Index(s,t,pos);if(k==0)cout<<"匹配失败!"<<endl<<endl;else{cout<<"从第"<<k<<"个位置开始匹配"<<endl;Display(s);for(int i=1;i<k;i++)cout<<" ";Display(t);}}【小结讨论】1. 此程序关键在于位置查询，由于对C语言函数的陌生导致问题变的繁琐，自己的C语言水平有待提高。

实验报告实验名称：串实验目的：（1）、熟悉C语言的上机环境，进一步掌握C语言的结构特点；（2）、掌握串的定义及C语言实现；（3）、掌握串的模式匹配及C语言实现；（4）、掌握串的各种基本操作；实验步骤：（1）、建立链串类型（2）、实现匹配过程中需考虑的链表的特征。

实验内容：4.一个字符串中的任意一个子序列，若子序列中各字符值均相同，则成为字符平台。

写一算法，输入任意以字符串S，输出S中长度最大的所有字符平台的起始位置及所含字符。

注意，最大字符平台有可能不止一个。

实验数据记录：（源代码及执行过程）#include<stdio.h>#include<stdlib.h>#define Maxsize 20#define n 100typedef struct Node{int element[Maxsize];int front;int rear;}Queue;int EnterQueue(Queue *Q,int x){if((Q->rear+1)%Maxsize == Q->front){printf("队列已满!\n");return 0;}Q->element[Q->rear] = x;Q->rear = (Q->rear+1)%Maxsize;return 1;}int DeleQueue(Queue *Q,int *x){if(Q->front == Q->rear){printf("队列为空!\n");return 0;}*x = Q->element[Q->front];Q->front = (Q->front+1)%Maxsize;return 1;}int Donull(Queue *Q){while(Q->front != Q->rear){Q->element[Q->front] = 0;Q->front = (Q->front+1)%Maxsize;}Q->front = Q->rear = 0;if(Q->front == Q->rear){return 1;}else{return 0;}}int main(void){char str[n];int i=0,j=1,k=1,ch,p=1,flag=1;Queue *Q;Q = (Queue *)malloc(sizeof(Queue));Q->front = Q->rear = 0;printf("请输入字符串：");gets(str);while('\0' != *(str+i)){ while(*(str+i+1) == *(str+i)){if(flag){p = i;flag = 0;}i++;j++;}if(flag){p = i;}if(j >= k){if(j > k){Donull(Q);k = j;}if(EnterQueue(Q ,j) == 0)break;if(EnterQueue(Q,p+1) == 0)break;if(EnterQueue(Q,*(str+i)) == 0)break;}j=1;i++;flag = 1;} while(Q->front < Q->rear){DeleQueue(Q,&j);DeleQueue(Q,&k);DeleQueue(Q,&ch);printf("%-10d",k);for(i = 0; i < j; i++){printf("%c",ch);}printf("\n");}printf("\n");system("pause");}。

数据结构顺序串基本操作实验报告实验目的：1.掌握顺序串的定义和基本操作；2.掌握顺序串的插入、删除、查找等基本操作。

实验内容：实现顺序串的基本操作，包括串的初始化、插入、删除、查找、输出等操作，并通过实例测试验证操作的正确性。

实验原理：顺序串是一种以连续的存储空间来存储字符序列的数据结构。

在顺序串中，字符串的字符元素依次存储在一组连续的存储单元中，可以通过下标来访问和修改元素。

顺序串的基本操作包括初始化、插入、删除、查找等。

1.串的初始化：初始化一个空串，即将串的长度设置为0。

2.串的插入：在指定位置插入一个字符或字符串。

首先需要判断插入位置的合法性，即位置不能超过当前串的长度，并将插入位置后的元素后移一位，然后将要插入的元素放入指定位置。

3.串的删除：删除指定位置的字符或字符串。

首先需要判断删除位置的合法性，即位置不能超过当前串的长度，然后将删除位置后的元素前移一位。

4.串的查找：在串中查找指定字符或子串第一次出现的位置。

遍历串中的每个元素，检查是否与要查找的字符或子串相等，若相等则返回其位置。

5.串的输出：将串中的元素打印出来。

实验步骤：1.定义顺序串的数据结构。

使用数组来存储字符序列，并定义一个变量用于记录串的长度。

2.初始化一个空串。

将串的长度设置为0。

3.实现插入操作。

根据插入位置的合法性，判断是否需要进行插入操作。

如果插入位置超过了当前串的长度，则将元素插入到串末尾；否则，将插入位置后的元素后移一位，并将要插入的元素放入指定位置。

4.实现删除操作。

根据删除位置的合法性，判断是否需要进行删除操作。

如果删除位置超过了当前串的长度，则无需删除；否则，将删除位置后的元素前移一位。

5.实现查找操作。

遍历串中的每个元素，检查是否与要查找的字符或子串相等，若相等则返回其位置。

6.实现输出操作。

遍历串中的每个元素，将其打印出来。

7.构造测试实例，并进行验证。

实验结果：以插入、删除、查找等操作为例，构造测试实例进行验证：假设有一个空串，插入字符'A'到位置0：结果为"A"；在串的末尾插入字符'B'：结果为"AB"；在位置1插入字符'C'：结果为"ACB"；删除位置3的字符：结果为"AC"；查找字符'C'的位置：结果为1实验总结：本次实验主要是对顺序串的基本操作进行了实现和验证。

串-数据结构实验报告串数据结构实验报告一、实验目的本次实验的主要目的是深入理解和掌握串这种数据结构的基本概念、存储方式以及相关的操作算法。

通过实际编程实现串的基本操作，提高对数据结构的理解和编程能力，培养解决实际问题的思维和方法。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理（一）串的定义串是由零个或多个字符组成的有限序列。

在本次实验中，我们主要关注的是字符串。

（二）串的存储方式1、顺序存储定长顺序存储：使用固定长度的数组来存储字符串，长度不足时用特定字符填充。

堆分配存储：根据字符串的实际长度动态分配存储空间。

2、链式存储每个节点存储一个字符，并通过指针链接起来。

（三）串的基本操作1、串的创建和初始化2、串的赋值3、串的连接4、串的比较5、求子串6、串的插入和删除四、实验内容及步骤（一）顺序存储方式下串的实现1、定义一个结构体来表示顺序存储的字符串，包含字符数组和字符串的实际长度。

｀｀｀cppstruct SeqString ｛char str;int length;｝；｀｀｀2、实现串的创建和初始化函数｀｀｀cppSeqString createSeqString(const char initStr) ｛int len ＝ strlen(initStr)；SeqString s;sstr ＝ new charlen ＋ 1;strcpy(sstr, initStr)；slength ＝ len;return s;｝｀｀｀3、串的赋值函数｀｀｀cppvoid assignSeqString(SeqString& s, const char newStr) ｛delete sstr;int len ＝ strlen(newStr)；sstr ＝ new charlen ＋ 1;strcpy(sstr, newStr)；slength ＝ len;｝｀｀｀4、串的连接函数｀｀｀cppSeqString concatSeqString(const SeqString& s1, const SeqString& s2) ｛SeqString result;resultlength ＝ s1length ＋ s2length;resultstr ＝ new charresultlength ＋ 1;strcpy(resultstr, s1str)；strcat(resultstr, s2str)；return result;｝｀｀｀5、串的比较函数｀｀｀cppint compareSeqString(const SeqString& s1, const SeqString& s2) ｛return strcmp(s1str, s2str)；｝｀｀｀6、求子串函数｀｀｀cppSeqString subSeqString(const SeqString& s, int start, int len) ｛SeqString sub;sublength ＝ len;substr ＝ new charlen ＋ 1;strncpy(substr, sstr ＋ start, len)；substrlen ＝＇＼0'；return sub;｝｀｀｀7、串的插入函数｀｀｀cppvoid insertSeqString(SeqString& s, int pos, const SeqString& insertStr) ｛int newLength ＝ slength ＋ insertStrlength;char newStr ＝ new charnewLength ＋ 1;strncpy(newStr, sstr, pos)；strcpy(newStr ＋ pos, insertStrstr)；strcpy(newStr ＋ pos ＋ insertStrlength, sstr ＋ pos)；delete sstr;sstr ＝ newStr;slength ＝ newLength;｝｀｀｀8、串的删除函数｀｀｀cppvoid deleteSeqString(SeqString& s, int start, int len) ｛int newLength ＝ slength len;char newStr ＝ new charnewLength ＋ 1;strncpy(newStr, sstr, start)；strcpy(newStr ＋ start, sstr ＋ start ＋ len)；delete sstr;sstr ＝ newStr;slength ＝ newLength;｝｀｀｀（二）链式存储方式下串的实现1、定义一个节点结构体｀｀｀cppstruct LinkNode ｛char data;LinkNode next;LinkNode(char c) ： data(c)， next(NULL) ｛｝｝；｀｀｀2、定义一个链式存储的字符串类｀｀｀cppclass LinkString ｛private:LinkNode head;int length;public:LinkString(const char initStr)；～LinkString(）；void assign(const char newStr)；LinkString concat(const LinkString& other)；int compare(const LinkString& other)；LinkString subString(int start, int len)；void insert(int pos, const LinkString& insertStr)；void deleteSub(int start, int len)；｝；｀｀｀3、实现各个函数｀｀｀cppLinkString:：LinkString(const char initStr) ｛length ＝ strlen(initStr)；head ＝ NULL;LinkNode p ＝ NULL;for （int i ＝ 0; i ＜ length; i+＋）｛LinkNode newNode ＝ new LinkNode(initStri)；if （head ＝＝ NULL) ｛head ＝ newNode;p ＝ head;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝｝｝LinkString:：～LinkString(）｛LinkNode p ＝ head;while （p) ｛LinkNode temp ＝ p;p ＝ p>next;delete temp;｝｝void LinkString:：assign(const char newStr) ｛／／先释放原有的链表LinkNode p ＝ head;while （p) ｛LinkNode temp ＝ p;p ＝ p>next;delete temp;｝length ＝ strlen(newStr)；head ＝ NULL;p ＝ NULL;for （int i ＝ 0; i ＜ length; i+＋）｛LinkNode newNode ＝ new LinkNode(newStri)；if （head ＝＝ NULL) ｛head ＝ newNode;p ＝ head;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝｝｝LinkString LinkString:：concat(const LinkString& other) ｛LinkString result;LinkNode p1 ＝ head;LinkNode p2 ＝ otherhead;LinkNode p ＝ NULL;while （p1) ｛LinkNode newNode ＝ new LinkNode(p1-＞data)；if （resulthead ＝＝ NULL) ｛resulthead ＝ newNode;p ＝ resulthead;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝p1 ＝ p1-＞next;｝while （p2) ｛LinkNode newNode ＝ new LinkNode(p2-＞data)；if （resulthead ＝＝ NULL) ｛resulthead ＝ newNode;p ＝ resulthead;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝p2 ＝ p2-＞next;｝resultlength ＝ length ＋ otherlength;return result;｝int LinkString:：compare(const LinkString& other) ｛LinkNode p1 ＝ head;LinkNode p2 ＝ otherhead;while （p1 ＆＆ p2 ＆＆ p1-＞data ＝＝ p2-＞data) ｛p1 ＝ p1-＞next;p2 ＝ p2-＞next;｝if （p1 ＝＝ NULL ＆＆ p2 ＝＝ NULL) ｛return 0;｝ else if （p1 ＝＝ NULL) ｛return －1;｝ else if （p2 ＝＝ NULL) ｛return 1;｝ else ｛return p1-＞data p2-＞data;｝｝LinkString LinkString:：subString(int start, int len) ｛LinkString sub;LinkNode p ＝ head;for （int i ＝ 0; i ＜ start; i+＋）｛p ＝ p>next;｝for （int i ＝ 0; i ＜ len; i+＋）｛LinkNode newNode ＝ new LinkNode(p>data)；if （subhead ＝＝ NULL) ｛subhead ＝ newNode;｝ else ｛LinkNode temp ＝ subhead;while （temp>next) ｛temp ＝ temp>next;｝temp>next ＝ newNode;｝p ＝ p>next;｝sublength ＝ len;return sub;｝void LinkString:：insert(int pos, const LinkString& insertStr) ｛LinkNode p ＝ head;for （int i ＝ 0; i ＜ pos 1; i+＋）｛p ＝ p>next;｝LinkNode insertHead ＝ insertStrhead;while （insertHead) ｛LinkNode newNode ＝ new LinkNode(insertHead>data)；newNode>next ＝ p>next;p>next ＝ newNode;p ＝ p>next;insertHead ＝ insertHead>next;｝length ＋＝ insertStrlength;｝void LinkString:：deleteSub(int start, int len) ｛LinkNode p ＝ head;for （int i ＝ 0; i ＜ start 1; i+＋）｛p ＝ p>next;｝LinkNode temp ＝ p>next;for （int i ＝ 0; i ＜ len; i+＋）｛LinkNode delNode ＝ temp;temp ＝ temp>next;delete delNode;｝p>next ＝ temp;length ＝ len;｝｀｀｀（三）测试用例1、顺序存储方式的测试｀｀｀cppint main(）｛SeqString s1 ＝ createSeqString(＂Hello"）；SeqString s2 ＝ createSeqString(＂World"）；SeqString s3 ＝ concatSeqString(s1, s2)；std:：cout ＜＜＂连接后的字符串: ＂＜＜ s3str ＜＜ std:：endl; int cmpResult ＝ compareSeqString(s1, s2)；if （cmpResult ＜ 0) ｛std:：cout ＜＜＂s1 小于 s2" ＜＜ std:：endl;｝ else if （cmpResult ＝＝ 0) ｛std:：cout ＜＜＂s1 等于 s2" ＜＜ std:：endl;｝ else ｛std:：cout ＜＜＂s1 大于 s2" ＜＜ std:：endl;｝SeqString sub ＝ subSeqString(s1, 1, 3)；std:：cout ＜＜＂子串: ＂＜＜ substr ＜＜ std:：endl; insertSeqString(s1, 2, s2)；std:：cout ＜＜＂插入后的字符串: ＂＜＜ s1str ＜＜ std:：endl; deleteSeqString(s1, 3, 2)；std:：cout ＜＜＂删除后的字符串: ＂＜＜ s1str ＜＜ std:：endl; return 0;｝｀｀｀2、链式存储方式的测试｀｀｀cppint main(）｛LinkString ls1(＂Hello"）；LinkString ls2(＂World"）；LinkString ls3 ＝ ls1concat(ls2)；std:：cout ＜＜＂连接后的字符串: ＂；LinkNode p ＝ ls3head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;int cmpResult ＝ ls1compare(ls2)；if （cmpResult ＜ 0) ｛std:：cout ＜＜＂ls1 小于 ls2" ＜＜ std:：endl;｝ else if （cmpResult ＝＝ 0) ｛std:：cout ＜＜＂ls1 等于 ls2" ＜＜ std:：endl;｝ else ｛std:：cout ＜＜＂ls1 大于 ls2" ＜＜ std:：endl;｝LinkString sub ＝ ls1subString(1, 3)；std:：cout ＜＜＂子串: ＂；p ＝ subhead;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;ls1insert(2, ls2)；std:：cout ＜＜＂插入后的字符串: ＂；p ＝ ls1head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;ls1deleteSub(3, 2)；std:：cout ＜＜＂删除后的字符串: ＂；p ＝ ls1head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;return 0;｝｀｀｀五、实验结果及分析（一）顺序存储方式1、连接操作成功实现，输出了正确连接后的字符串。

《数据结构》实验报告排序实验题目：输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。

实验所使用的数据结构内容及编程思路：1.插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。

一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r［1..i-1］中插入一个记录r［i］后，变成含有i个记录的有序子序列r［1..i］；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r［0］处设置哨兵。

在自i-1起往前搜索的过程中，可以同时后移记录。

整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。

2.快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

假设待排序的序列为{L.r[s]，L.r[s+1],…L.r[t]},首先任意选取一个记录(通常可选第一个记录L.r[s])作为枢轴（或支点）（pivot），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。

由此可以该“枢轴”记录最后所罗的位置i作为界线，将序列{L.r[s]，…，L.r[t]}分割成两个子序列{L.r[i+1],L.[i+2],…,L.r[t]}。

这个过程称为一趟快速排序，或一次划分。

一趟快速排序的具体做法是：附设两个指针low和high，他们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两不直至low=high为止。

数据结构实验三课程数据结构实验名称顺序栈基本操作第页专业班级学号姓名实验日期：年月日评分一、实验目的1．熟悉并能实现栈的定义和基本操作。

2．了解和掌握栈的应用。

二、实验要求1．进行栈的基本操作时要注意栈"后进先出"的特性。

2．编写完整程序完成下面的实验内容并上机运行。

3．整理并上交实验报告。

三、实验内容1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。

2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。

主要功能描述如下：（1）从键盘上输入表达式。

（2）分析该表达式是否合法：•a) 是数字，则判断该数字的合法性。

若合法，则压入数据到堆栈中。

•b) 是规定的运算符，则根据规则进行处理。

在处理过程中，将计算该表达式的值。

•c) 若是其它字符，则返回错误信息。

（3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。

程序中应主要包含下面几个功能函数：•l void initstack()：初始化堆栈•l int Make_str()：语法检查并计算•l int push_operate(int operate)：将操作码压入堆栈•l int push_num(double num)：将操作数压入堆栈•l int procede(int operate)：处理操作码•l int change_opnd(int operate)：将字符型操作码转换成优先级•l int push_opnd(int operate)：将操作码压入堆栈•l int pop_opnd()：将操作码弹出堆栈•l int caculate(int cur_opnd)：简单计算+，-，*，/•l double pop_num()：弹出操作数四、实验步骤（描述实验步骤及中间的结果或现象。

在实验中做了什么事情，怎么做的，发生的现象和中间结果）第一题：#include <iostream>using namespace std;#define STACK_INIT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量#define OVERFLOW -1#define OK 1#define NO -1#define NULL 0typedef int Status;typedef char SElemType;typedef struct{SElemType *base; //在栈构造之前和销毁之后，base的值为NULLSElemType *top; //栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位} SqStack;Status Initstack(SqStack &S)//构造一个空栈S{S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize= STACK_INIT_SIZE;return OK;}//InitStackStatus StackEmpty(SqStack &S){if(S.base==S.top)return OK;elsereturn NO;}Status ClearStack (SqStack &S)//把S置为空{if(S.base=S.top);return OK;}Status DsetroyStack (SqStack &S)//销毁栈S{S.base=NULL;return OK;}Status Push(SqStack &S,SElemType e)//插入元素e为新的栈顶元素{if (S.top-S.base>=S.stacksize){S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base) //存储分配失败exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}//PushStatus Pop(SqStack &S,SElemType &c)//若栈不空，则删除S的栈顶元素，用c返回其值，并返回OK；否则返回ERROR {if(S.top==S.base)return NO;c=*--S.top;return OK;}//PopStatus GetTop(SqStack &S,SElemType &e){if (S.top==S.base)return NO;e=*(S.top-1);return OK;}//GetTopint main(){SqStack S;Initstack(S);cout<<"输入要压到栈中的元素!"<<endl;char c;while((c=getchar())!='\n'){Push(S,c);}GetTop(S,c);cout<<"栈顶元素为："<<c<<endl;//ClearStack (S);//DsetroyStack(S);for(int i=0;S.top!=S.base;i++){Pop(S,c);cout<<"栈中第"<<i+1<<"元素的值:";cout<<c<<endl;}return 0;}第二题：#include<iostream>using namespace std;#define STACK_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define OK 1#define NO 0typedef int Status;typedef char SElemType;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;int main(){char GetTop(SqStack &s);Status Initstack(SqStack &s);Status push_operate(SqStack &s,SElemType e);Status push_num(SqStack &s,int e);Status Stackempty(SqStack &s);Status pop_num(SqStack &s,int &c);Status pushoperate(SElemType operate);Status pushnum(SElemType num);Status caculate(SElemType a,SElemType operate,SElemType b);Status pop_operate(SqStack &s,SElemType &c);Status change(SElemType e);char Precede(SElemType a,SElemType b);char Operatecxz();int m;m=Operatecxz();cout<<m<<endl;return 0;}Status change(SElemType e){int m;m=e-48;return m;}Status Initstack(SqStack &s){s.base=(SElemType *)malloc(STACK_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_SIZE;return OK;}Status Stackempty(SqStack &s){if(s.base==s.top)return OK;elsereturn NO;}Status push_num(SqStack &s,int e){if(s.top-s.base>=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;return OK;}Status push_operate(SqStack &s,SElemType e){if(s.top-s.base>=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;return OK;}Status pop_operate(SqStack &s,SElemType &c){if(s.top==s.base)return NO;c=*--s.top;return OK;}Status pop_num(SqStack &s,int &c){if(s.top==s.base)return NO;c=*--s.top;return OK;}char GetTop(SqStack &s){char c;if(s.top==s.base)return NO;c=*(s.top-1);return c;}Status caculate(int a,SElemType operate,int b){int s;if(operate=='+')s=a+b;if(operate=='-')s=a-b;if(operate=='*')s=a*b;if(operate=='/')s=a/b;return s;}Status In(SElemType c){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')') return OK;if(c>='0'&&c<='9')return NO;return -1;}char Precede(SElemType a,SElemType b){if(a=='+'||a=='-'){if(b=='+'||b=='-'||b==')'||b=='#')return '>';if(b=='*'||b=='/'||b=='(')return '<';}if(a=='*'||a=='/'){if(b=='+'||b=='-'||b==')'||b=='*'||b=='/'||b=='#')return '>';if(b=='(')return '<';}if(a=='('){if(b==')')return '=';if(b=='+'||b=='-'||b=='*'||b=='/')return '<';if(b=='#')return ' ';}if(a==')'){if(b==')')return ' ';if(b=='+'||b=='-'||b=='*'||b=='/'||b=='('||b=='#')return '>';}if(a=='#'){if(b=='#')return '=';if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(')return '<';if(b==')')return ' ';}return ' ';}char Operatecxz(){SqStack Operate,Num;char c,e,x;int num,a,b,flat=1,sz=0;Initstack(Operate);push_operate(Operate,'#');Initstack(Num);c=getchar();while(c!='#'||GetTop(Operate)!='#'){if(In(c)==-1){cout<<"input error!"<<endl;flat=0;break;}if(In(c)!=1){if(sz==0){num=change(c);sz=1;c=getchar();continue;}if(sz==1)num=num*10+change(c);c=getchar();continue;}else{if(sz==1)push_num(Num,num);sz=0;x=GetTop(Operate);switch(Precede(GetTop(Operate),c)){case '<':{push_operate(Operate,c);c=getchar();break;}case '=':{pop_operate(Operate,e);c=getchar();break;}case '>':{pop_num(Num,a);pop_operate(Operate,e);pop_num(Num,b);push_num(Num,caculate(b,e,a));break;}}}}pop_operate(Operate,e);if(e!='#')flat=0;if(flat==1){pop_num(Num,a);return a;}if(flat==0)return 0;}五．实验结果与讨论（描述最终得到的结果，并进行分析说明，可能的误差原因）第一题：1 把主函数中的ClearStack (S);DsetroyStack(S)注释掉的结果：2 不把ClearStack (S)注释掉，把栈清空：3 不把DsetroyStack(S)注释掉，即销毁栈：出现一堆乱码，说明销毁成功。

数据结构\顺序串基本操作实验报告实验报告数据结构\顺序串基本操作一、实验目的本实验旨在通过实践，掌握顺序串的基本操作，包括顺序串的初始化、销毁、插入、删除和查找等。

二、实验内容1\初始化顺序串2\销毁顺序串3\插入元素到顺序串4\删除顺序串中的指定元素5\查找顺序串中的指定元素三、实验步骤1\初始化顺序串顺序串的初始化就是创建一个空顺序串，可以通过创建一个定长数组来实现。

具体步骤如下：（1）定义一个定长数组，例如a[MAX_SIZE]，用于存储顺序串的元素。

（2）定义一个变量len，用于记录顺序串的当前长度，初值为0。

2\销毁顺序串销毁顺序串就是释放顺序串占用的内存空间，具体步骤如下：（1）释放数组a所占用的内存空间。

（2）将len重置为0。

3\插入元素到顺序串插入元素到顺序串就是在指定位置插入一个元素。

具体步骤如下：（1）判断插入位置的合法性，如果位置小于0或大于当前顺序串的长度，即为非法操作。

（2）将len加1，表示顺序串的长度增加了一个。

（3）将插入位置及其之后的元素依次后移一位。

（4）将需要插入的元素存放到插入位置处。

4\删除顺序串中的指定元素删除顺序串中的指定元素就是将顺序串中某个位置的元素删除。

具体步骤如下：（1）判断被删除位置的合法性，如果位置小于0或大于等于当前顺序串的长度，即为非法操作。

（2）将被删除位置之后的元素依次前移一位。

（3）将len减1，表示顺序串的长度减少了一个。

5\查找顺序串中的指定元素查找顺序串中的指定元素就是找出顺序串中第一个与给定元素相等的元素的位置。

具体步骤如下：（1）从顺序串的第一个元素开始逐个与给定元素比较，直到找到相等的元素或搜索到顺序串的末尾。

（2）返回相等元素的位置。

四、实验结果与分析根据实验步骤，我们可以完成顺序串的初始化、销毁、插入、删除和查找等基本操作。

通过这些操作，我们可以对顺序串进行各种元素的插入、删除和查找操作，方便实现顺序串的各种功能。

数据结构实验一顺序表实验报告一、实验目的本次实验的主要目的是通过实现顺序表的基本操作，深入理解线性表的逻辑结构和存储结构，掌握顺序表的插入、删除、查找等操作的实现方法，提高编程能力和问题解决能力。

二、实验环境本次实验使用的编程语言为 C 语言，编程环境为 Visual Studio 2019。

三、实验原理顺序表是一种线性表的存储结构，它使用一组连续的存储单元依次存储线性表中的元素。

在顺序表中，元素的逻辑顺序与物理顺序是一致的。

顺序表的基本操作包括初始化、插入、删除、查找、遍历等。

在实现这些操作时，需要考虑顺序表的存储空间是否已满、插入和删除元素时元素的移动等问题。

四、实验内容（一）顺序表的定义｀｀｀cdefine MAXSIZE 100 ／／定义顺序表的最大长度typedef struct ｛int dataMAXSIZE; ／／存储顺序表的元素int length; ／／顺序表的当前长度｝ SeqList;｀｀｀（二）顺序表的初始化｀｀｀cvoid InitList(SeqList L) ｛L>length ＝ 0;｝｀｀｀（三）顺序表的插入操作｀｀｀cint InsertList(SeqList L, int i, int e) ｛if （L>length ＝＝ MAXSIZE) ｛／／顺序表已满return 0;｝if （i ＜ 1 ｜｜ i ＞ L>length ＋ 1) ｛／／插入位置不合法return 0;｝for （int j ＝ L>length; j ＞＝ i; j) ｛／／移动元素L>dataj ＝ L>dataj 1;｝L>datai 1 ＝ e; ／／插入元素L>length+＋；return 1;｝｀｀｀（四）顺序表的删除操作｀｀｀cint DeleteList(SeqList L, int i, int e) ｛if （L>length ＝＝ 0) ｛／／顺序表为空return 0;｝if （i ＜ 1 ｜｜ i ＞ L>length) ｛／／删除位置不合法｝e ＝ L>datai 1; ／／取出被删除的元素for （int j ＝ i; j ＜ L>length; j+＋）｛／／移动元素L>dataj 1 ＝ L>dataj;｝L>length;return 1;｝｀｀｀（五）顺序表的查找操作｀｀｀cint SearchList(SeqList L, int e) ｛for （int i ＝ 0; i ＜ Llength; i+＋）｛if （Ldatai ＝＝ e) ｛return i ＋ 1;｝｝｝｀｀｀（六）顺序表的遍历操作｀｀｀cvoid TraverseList(SeqList L) ｛for （int i ＝ 0; i ＜ Llength; i+＋）｛printf(＂％d ＂， Ldatai)；｝printf(＂＼n"）；｝｀｀｀五、实验步骤1、打开 Visual Studio 2019，创建一个新的 C 语言项目。

（封面）学生实验报告学院：国际经贸学院课程名称：数据结构专业班级：09电子商务姓名：学号：学生实验报告（经管类专业用）一、实验目的及要求：1、目的通过实验，实现顺序栈的各种基本运算。

2、内容及要求编写一个程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成下列功能：（1）初始化栈S。

（2）判断栈S是否非空。

（3）依次进栈元素a，b，c，d，e。

（4）判断栈S是否非空。

（5）输出栈的长度。

（6）输出从栈顶到栈底的元素。

（7）输出出栈序列；（8）判断链栈S是否为空；（9）释放链栈二、仪器用具：三、实验方法与步骤:一、查阅顺序栈等相关资料，熟悉顺序栈基本概念和流程二、“开展”顺序栈实验流程三、整理实验数据和文档，总结实验的过程，编写实验报告四、实验结果与数据处理：1、顺序栈的代码：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType data[MaxSize];int top; //栈顶指针} SqStack;void InitStack(SqStack *&s){s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}void ClearStack(SqStack *&s){free(s);}int StackLength(SqStack *s){return(s->top+1);}int StackEmpty(SqStack *s){return(s->top==-1);}int Push(SqStack *&s,ElemType e) {if (s->top==MaxSize-1)return 0;s->top++;s->data[s->top]=e;return 1;}int Pop(SqStack *&s,ElemType &e) {if (s->top==-1)return 0;e=s->data[s->top];s->top--;return 1;}int GetTop(SqStack *s,ElemType &e) {if (s->top==-1)return 0;e=s->data[s->top];return 1;}void DispStack(SqStack *s){int i;for (i=s->top;i>=0;i--)printf("%c ",s->data[i]);printf("\n");void main() {// 主函数SqStack S=(SqStack *)malloc(sizeof(SqStack)); printf("(1)初始化顺序栈\n");InitStack(S);printf("(2)判断顺序栈是否为空:\n"); StackEmpty(S);printf("(3)依次进栈元素a,b,c,d,e:\n");Push(S,'a');Push(S,'b');Push(S,'c');Push(S,'d');Push(S,'e');printf("(4)判断顺序栈是否为空:\n"); StackEmpty(S);printf("(5)输出栈长度:%d\n",StackLength(S)); printf("(6)输出从栈顶到栈底的元素:\n"); StackTraverse(S);printf("(7)读出栈顶元素:%d\n",GetTop(S,e));printf("(8)删除栈顶元素:%d\n",Pop(S,e));printf("(9)输出从栈顶到栈底的元素:\n");StackTraverse(S);printf("(10)判断顺序栈是否为空\n");StackEmpty(S);printf("(11)释放栈。

一、实验目的和要求1理解串的一般线性表之间的差异。

2重点掌握在顺序串上和链串上实现串的基本运算算法。

3掌握串的简单匹配算法和KMP算法。

4灵活运用串这种数据结构解决一些综合应用问题。

二、实验环境、内容和方法实验内容：1实现顺序串的各种基本运算。

2实现链串的各种基本运算。

3实现顺序串的各种模式匹配运算。

4求一个串中出现的第一个最长重复串。

实验方法：通过上机操作完成各内容。

实验环境：实验用PC机一台，使用操作系统为Windows XP Professional，安装OFFICE 2003、VC++等软件。

三、实验过程描述实验题4.1实现顺序串各种基本运算的算法编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp 完成如下功能：1建立串谁“abcdefghefghefghijklmn”和串s1=”xyz”;2输出串s;3输出串s的长度；4在串s的第9个字符位置插入串s1而产生串s2;5输出串s2;6删除串s第2个字符开始的5个字符替换成串s1而产生串s2；7输出串s2;8将串s第2个字符开始的5个字符替换成串s1而产生串s2;s2;输出串9．10提取串s的第2个字符开始的10个字符而产生串s3;11输出串s3；12将串s1和串s2连接起来而产生串s4;13输出串s4.解：本工程Proj4_1组成结构如图4.1所示。

algo4-1.cpp文件，其中包含如下函数：StrAssign(SqString &str,char cstr[]):由串常量cstr创建串str. StrCopy(SqString &s,SqString t):将串t复制到串s.StrEqual(SqString s,SqString t):判断两个串s和t是否相同。

StrLength(SqString s):求串s的长度。

Concat(SqString s,SqString t):将串t连接到串s之后产生新串。