《数据结构与算法分析》课程实验报告三 串
·
目 录
一、实验目的及要求
1.实验目的
1）掌握串的概念、抽象数据类型和特点，掌握串的顺序存储结构和链式存储结构的存储思想及其程序实现，掌握串对应存储结构的基本操作。
2）掌握串的创建、定位、判空、求串长、求子串等算法实现。
2.实验要求
1）熟悉串的顺序存储结构和链式储存结构。
2）上机过程中要遵守实验室的各项规章制度,爱护实验设备，保持环境卫生。
3）本课程的实验过程中，不得进行游戏、上网等操作。
二、实验环境（工具、配置等）
1.硬件要求：笔记本电脑一台。
2.软件要求：Windows11操作系统，编译环境Dev-Cpp。
3.数据结构与算法分析，使用C++语言。
三、实验内容（实验方案、实验步骤、设计思路）
1.实验方案
结合课本中算法知识以及老师上课所讲知识进行灵活运用，编写代码实现串的相关功能并进行测试和相应的修改和完善。
2.实验步骤
1）认真分析课本上串相关功能的算法实现，将书上的伪代码翻译成C++语言的源代码进行测试。
2）认真学习老师上课所讲知识，将知识运用到实践中，对自己的代码进行修改与完善。
3）成功通过代码对串的相关功能进行实现。
4）完成串的实验报告并进行提交。
3.设计思路
1）定义串的基本结构类型。
2）通过函数实现对串的初始化、串的创建、串的赋值、串的判等、求串的长度、求字串的位置、串的插入、串的删除、串的替换、串的无参输出、串的有参输出、串的销毁的基本功能以及使用串实现串的联接和求子串。
3）对串实现顺序存储（顺序串）和堆存储（堆串）并进行串的相关操作。
4）对相关功能的实现进行必要的注释，供自己和老师参考和理解。
5）通过主函数调用各函数进行功能的实现。
四、实验结果与分析
1.使用Dev-Cpp编写顺序存储串，并编译运行进行相关功能的实现，如图4-1：
图4-1 顺序存储串输出结果
2.使用Dev-Cpp编写堆存储串，并编译运行进行相关功能的实现，如图4-2：
图4-2 堆存储串输出结果
1、实验分析
1）编译错误：“error C2057: expected constant expression”
解决方法：定义数组时数组长度为变量，将常量改为变量即可。
2）编译错误：“error C2078: too many initializers”
解决方法：数组初始化时初始值的个数大于数组长度，将数组长度扩大即可。
3）编译错误：”error C2086: 'xxx' : redefinition“
解决方法：变量名、数组名重名，将变量名或数组名中的一个进行修改即可。
4）编译错误：“error C2100: illegal indirection”
解决方法：对非指针变量使用“*”运算，将其变量修改为指针即可。
5）出现的问题：内存分配未成功。
解决方法：使用内存之前先检查指针是否为空（NULL）
6）出现的问题：内存虽然分配成功，但是还没有初始化就进行了使用。
解决方法：在创建后数组之后，要进行赋初值，即使是零也不能省略。
7）出现的问题：未释放空间，造成内存泄露。
解决方法：动态开辟的内存要让申请和释放进行配对。
2、心得体会
1）定义指针之后必须赋值，然后才可以引用。
2）指针赋初值时a.在定义指针的同时进行初始化赋值b.在定义之后单独使用赋值语句。
3）任何类型的指针都可以赋值给void类型的指针变量。
4）用new申请内存之后，因立即检查指针值是否为NULL，防止使用指针值为NULL的内存。
5）避免数字或指针的下标越界，特别要当心发生“多1”或者“少1”操作。
6）动态内存的申请与释放必须配对，防止内存泄漏。
7）用delete释放内存之后，立即将指针设置为NULL，防止“野指针”。
五、附源程序
1.顺序串的实现代码（串的初始化、创建、赋值、判等、插入、删除、替换、销毁、无参输出、有参输出、求长度、求字串位置、串的联接、求子串）
#include <iostream>
#define MAXSIZE 100
using namespace std;
struct SqString {
char ch[MAXSIZE];//字符数组
int length;//串的实际长度
};
//顺序串类
class SString {
public:
//串的初始化
SString() { //无参的构造函数
cout << "顺序串初始化成功！" << endl;
}
//顺序串的创建
void Setstring(char a[]) {
int i;
for (i = 0; a[i] != '\0'; i++) {
S.ch[i] = a[i];
}
S.length = i;
}
//顺序串的赋值
void Givestring(SString s) {
//顺序串的赋值
for (int i = 0; i < s.Location()->length; i++) {
S.ch[i] = s.Location()->ch[i];
}
//顺序串的长度赋值
S.length = s.Location()->length;
}
//判断顺序串是否相等
bool Equalstring(SString s) {
//两者长度不等
if (S.length != s.Location()->length) {
return false;
} else {
for (int i = 0; i < S.length; i++) {
//顺序串的内容不一样
if (S.ch[i] != s.Location()->ch[i]) {
return false;
}
}
return true;
}
}
//求顺序串的长度
int Lengthstring() {
return S.length;
}
//顺序串的联接
SqString Connectstring(SString s) {
SqString str;
str.length = S.length + s.Location()->length;
//给S赋值
for (int i = 0; i < S.length; i++) {
str.ch[i] = S.ch[i];
}
//给s赋值
for (int i = S.length; i < S.length + s.Location()->length; i++) {
str.ch[i] = s.Location()->ch[i - S.length];
}
return str;
}
//求顺序串的子串
SqString Sonstring(int i, int x) {
//返回顺序串中从i开始连续的x个字符
SqString str;
str.length = 0;
if (i <= 0 || i > S.length || x <= 0 || i + x - 1 > S.length) {
return str;
} else {
for (int j = i - 1; j < i + x - 1; j++) {
str.ch[j - (i - 1)] = S.ch[j];
}
str.length = x;
return str;
}
}
//求子串的位置
void Indexstring(char a[], int size) {
int i, j;
for (i = 0; i < S.length; i++) {//从主串开始遍历
for (j = 0; j < size; j++) {//从子串开始遍历
if (S.ch[i] != a[j]) {
if (i + 1 == S.length) {
cout << "该串中没有此字串！" << endl;
}
break;
} else {
i++;
continue;
}
}
if ( j == size) {
cout << "子串在主串的第" << i - size + 1 << "个位置" << endl;
break;
}
}
}
//顺序串的插入
SqString Insertstring(SString s, int x) {
//将串s插入到x处
SqString str;
str.length = 0;
if (x <= 0 || x > S.length + 1) {
return str;
} else {
//插入串S的前i-1个字符
for (int i = 0; i < x - 1; i++) {
str.ch[i] = S.ch[i];
}
//插入串s
for (int i = 0; i < s.Location()->length; i++) {
str.ch[i + x - 1] = s.Location()->ch[i];
}
//插入剩下的S串
for (int i = x - 1; i < S.length; i++) {
str.ch[(x - 1) + s.Location()->length + (i - (x - 1))] = S.ch[i];
}
str.length = S.length + s.Location()->length;
return str;
}
}
//顺序串的删除
SqString Deletestring(int i, int x) {
//删除从位置i开始连续的x个字符
SqString str;
str.length = 0;
if (i <= 0 || i > S.length || x <= 0 || i + x - 1 > S.length) {
return str;
} else {
//赋值S的前i-1个字符
for (int j = 0; j < i - 1; j++) {
str.ch[j] = S.ch[j];
}
//赋值剩下的字符
for (int j = i - 1 + x; j < S.length; j++) {
str.ch[j - x] = S.ch[j];
}
str.length = S.length - x;
return str;
}
}
//顺序串的替换
SqString Replacestring(int i, int x, SString s) {
SqString str;
str.length = 0;
if (i <= 0 || i > S.length || x < 0 || i + x - 1 > S.length) {
return str;
} else {
//赋值S的前i-1个字符
for (int j = 0; j < i - 1; j++) {
str.ch[j] = S.ch[j];
}
//插入s串
for (int j = 0; j < s.Location()->length; j++) {
str.ch[i - 1 + j] = s.Location()->ch[j];
}
//赋值剩下的串
for (int j = i - 1 + x; j < S.length; j++) {
str.ch[(i - 1) + s.Location()->length + (j - (i - 1 + x))] = S.ch[j];
}
str.length = S.length - x + s.Location()->length;
return str;
}
}
//顺序串的输出（无参）
void Printstring() {
if (S.length == 0) {
cout << "该串为空，没有元素可以输出！" << endl;
} else {
for (int i = 0; i < S.length; i++) {
cout << S.ch[i];
}
cout << endl;
}
}
//顺序串的输出(有参）
void Printstring(SqString s) {
if (s.length == 0) {
cout << "该串为空，没有元素可以输出！" << endl;
} else {
for (int i = 0; i < s.length; i++) {
cout << s.ch[i];
}
cout << endl;
}
}
//顺序串的销毁
~SString() {}
private:
SqString S;
SqString *Location() { //返回串的首地址
return &S;
}
};
int main() {
SString S1, S2;
int size, i;
char a[MAXSIZE];
cout << endl;
cout << "进行顺序串的相关操作！" << endl;
//顺序串S1的生成
cout << "顺序串S1的建立！" << endl;
cout << "请输入串S1的长度为：";
cin >> size;
for (i = 0; i < size; i++) {
cout << "请输入串S1的第" << i + 1 << "个元素为：";
cin >> a[i];
}
a[i] = '\0';
S1.Setstring(a);
cout << endl;
//顺序串S1的输出
cout << "顺序串S1为：";
S1.Printstring();
cout << endl;
//顺序串S1的长度
cout << "顺序串S1的长度为：" << S1.Lengthstring() << endl;
cout << endl;
//顺序串S2的生成
cout << "顺序串S2的建立！" << endl;
cout << "请输入串S2的长度为：";
cin >> size;
for (i = 0; i < size; i++) {
cout << "请输入串S2的第" << i + 1 << "个元素为：";
cin >> a[i];
}
a[i] = '\0';
S2.Setstring(a);
cout << endl;
//顺序串S2的输出
cout << "顺序串S2为：";
S2.Printstring();
cout << endl;
//顺序串S2的长度
cout << "顺序串S2的长度为：" << S2.Lengthstring() << endl;
cout << endl;
//获取顺序串的字串
int location, x;
cout << "请输入字串的开始位置为：";
cin >> location;
cout << "请输入需要获取的长度为：";
cin >> x;
cout << "你所获取的字串为：";
S1.Printstring(S1.Sonstring(location, x));
cout << endl;
//顺序串的插入
cout << "请输入需要将S2插入到S1的位置为：";
cin >> location;
cout << "插入后的顺序串为：";
S1.Printstring(S1.Insertstring(S2, location));
cout << endl;
//顺序串的联接
cout << "S1和S2联接后的结果为：";
S1.Printstring(S1.Connectstring(S2));
cout << endl;
//判断顺序串是否相等
if (S1.Equalstring(S2)) {
cout << "顺序串S1和S2相等！" << endl;
} else {
cout << "顺序串S1和S2不相等！" << endl;
}
cout << endl;
//子串的生成
char b[MAXSIZE];
cout << "子串的建立！" << endl;
cout << "请输入子串的长度为：";
cin >> size;
for (i = 0; i < size; i++) {
cout << "请输入子串的第" << i + 1 << "个元素为：";
cin >> b[i];
}
//判断子串的位置
S1.Indexstring(b, size);
cout << endl;
//顺序串的删除
cout << "请输入需要删除S1的位置为：";
cin >> location;
cout << "请输入需要删除S1的长度为：";
cin >> x;
cout << "删除后的结果为：";
S1.Printstring(S1.Deletestring(location, x));
cout << endl;
//顺序串的替换
cout << "请输入需要替换的位置为：";
cin >> location;
cout << "S1替换后的结果为：";
S1.Printstring(S1.Replacestring(location, S2.Lengthstring(), S2));
cout << endl;
//顺序串的销毁
S1.~SString();
cout << "顺序串S1已成功销毁！" << endl;
S2.~SString();
cout << "顺序串S2已成功销毁！" << endl;
return 0;
}2. 堆串的实现代码（串的初始化、创建、赋值、判等、插入、删除、替换、销毁、输出、求长度、求字串位置、串的联接、求子串）
#include <iostream>
#define MAXSIZE 100
using namespace std;
struct HString {
char *ch;
int length;//串的当前长度
};
//串的初始化
void Initstring(HString &S) {
S.ch = new char[MAXSIZE];
S.length = 0;
}
//串的创建
void Createstring(HString &S) {
int size, x;
cout << "请输入串的长度为：";
cin >> S.length;
for (int i = 0; i < S.length; i++) {
cout << "请输入串的第" << i + 1 << "个元素为：";
cin >> S.ch[i];
}
}
//求串的长度
int Lengthstring(HString &S) {
return S.length;
}
//求两串的长度差
int Distancestring(HString &S1, HString &S2) {
int Length;
Length = S1.length - S2.length;
if (Length < 0) {
return -Length;
} else {
return Length;
}
}
//串的联接
void Connectstring(HString &S, HString &S1, HString &S2) {
for (int i = 0; i < S1.length; i++) {
S.ch[i] = S1.ch[i];
}
S.length = S1.length + S2.length;
for (int i = S1.length; i < S.length; i++) {
S.ch[i] = S2.ch[i - S1.length];
}
}
//串的打印
void Printstring(HString &S) {
if (S.length == 0) {
cout << "此串为空串，没有元素可以输出！" << endl;
} else {
for (int i = 0; i < S.length; i++) {
cout << S.ch[i];
}
}
cout << endl;
}
//串的判等
bool Equalstring(HString &S1, HString &S2) {
if (S1.length != S2.length)
return false;
else {
for (int i = 0; i < S1.length; i++) {
if (S1.ch[i] != S2.ch[i])
return false;
}
return true;
}
}
//串的定位
void Indexstring(HString &S) {
int size, i, j;
cout << "请输入子串的长度为：";
cin >> size;
char a[size];
for (i = 0; i < size; i++) {
cout << "请输入子串的第" << i + 1 << "个元素为：";
cin >> a[i];
}
for (i = 0; i < S.length; i++) {//从主串开始遍历
for (j = 0; j < size; j++) {//从子串开始遍历
if (S.ch[i] != a[j]) {
if (i + 1 == S.length) {
cout << "该串中没有此字串！" << endl;
}
break;
} else {
i++;
continue;
}
}
if ( j == size) {
cout << "子串在主串的第" << i - size + 1 << "个位置" << endl;
break;
}
}
}
//获取串的子串
void Sonstring(HString &S, HString &s) {
int size, x;
cout << "请输入需要获取的子串位置为：";
cin >> x;
cout << "请输入需要获取的子串长度为：";
cin >> size;
if (x <= 0 || x > S.length || size < 0 || size > S.length - x + 1)
cout << "该区域无效，请重新输入！" << endl;
for (int i = 0; i < size; i++) {
s.ch[i] = S.ch[x + i - 1];
s.length = size;
}
}
//串的销毁
void Deletestring(HString &S) {
delete S.ch;
}
int main() {
HString S1, S2, S3, S4;
//串的初始化
Initstring(S1);
if (S1.ch) {
cout << "串S1初始化成功！" << endl;
} else {
cout << "串S1初始化失败！" << endl;
}
Initstring(S2);
if (S2.ch) {
cout << "串S2初始化成功！" << endl;
} else {
cout << "串S2初始化失败！" << endl;
}
Initstring(S3);
if (S3.ch) {
cout << "串S3初始化成功！" << endl;
} else {
cout << "串S3初始化失败！" << endl;
}
Initstring(S4);
if (S4.ch) {
cout << "串S4初始化成功！" << endl;
} else {
cout << "串S4初始化失败！" << endl;
}
cout << endl;
cout << "对串S1进行操作！" << endl;
//串S1的创建
Createstring(S1);
cout << endl;
//串S1的打印
cout << "串S1为：";
Printstring(S1);
cout << endl;
//串的长度
cout << "串S1的长度为：" << Lengthstring(S1) << endl;
cout << endl;
cout << "对串S2进行操作！" << endl;
//串S2的创建
Createstring(S2);
cout << endl;
//串S2的打印
cout << "串S2为：";
Printstring(S2);
cout << endl;
//串的长度
cout << "串S2的长度为：" << Lengthstring(S2) << endl;
cout << endl;
//两个串的长度差
cout << "串S1和串S2的长度差为：" << Distancestring(S1, S2) << endl;
cout << endl;
//两个串的联接
Connectstring(S3, S1, S2);
cout << "串S1和串S2联接后为：";
Printstring(S3);
cout << endl;
//获取子串
Sonstring(S1, S4);
cout << "你所获取的字串为：";
Printstring(S4);
cout << endl;
//串的判等
if (Equalstring(S1, S2))
cout << "S1和S2相等！" << endl;
else
cout << "S1和S2不相等！" << endl;
cout << endl;
//串的定位
Indexstring(S1);
cout << endl;
//串的销毁
Deletestring(S1);
cout << "串S1已成功销毁！" << endl;
Deletestring(S2);
cout << "串S2已成功销毁！" << endl;
Deletestring(S3);
cout << "串S3已成功销毁！" << endl;
Deletestring(S4);
cout << "串S4已成功销毁！" << endl;
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
28
0- 0
已为社区贡献9条内容
所有评论(0)