wen 数据结构实验（三）
数据结构实验（三）
串、数组和广义表
-
串的封装及基本操作
-
“String.hpp”
// Test4-1：串的封装及基本操作 #include <iostream> #include "../SeqList/SeqList.hpp" using namespace std; struct String :SeqList<char> { String(int c = 100) :SeqList(c) //按指定长度构造串 { } String(const char* chars) //以""结尾的串构造串，方便将C语言的字符串转换为当前封装的String { while (*chars) { append(*chars); chars++; } } String* subString(int pos, int len)//取子串 { String* result = new String(len); memcpy(result->items, items + pos, sizeof(char) * len); length = len; return result; } String& concat(String& T) //连接字符串 { int len = length + T.length; if (capacity < len) //长度不够则扩容 resize(len); memcpy(items + length, T.items, sizeof(char) * T.length);//连接第二部分 length = len; return *this; //返回自身，方便调用者连续使用 } int compare(String& T) //比较两个串是否相等，返回正数、零、负数分别表示大于、等于、小于 { int n = length, m = T.length; int i = 0, j = 0; while (i < n && j < m) { if (items[i] != T.items[i]) //存在一个字符不等则不等 return items[i] - T.items[i];//以第一个不相等的字符计算大小 i++; j++; } return n - m; //全部字符都没有不等，则两个串相等 } bool operator==(String& T) { return compare(T) == 0; } void operator=(const String& T) //深拷贝函数，不重写会导致字符串的数组赋值出现浅拷贝 { length = T.length; resize(length); memcpy(items, T.items, sizeof(char) * T.length); } void split(SeqList<String>& subs, char splitter) { //TODO:依据spliter字符，将字符串的内容分割开，依次存储到subs中 } void replace(String A, String B) { //TODO:查找当前字符串中所以的A，替换成B } void remove(int pos, int len) { //TODO：删除从pos开始的len个字符 } void insert(String& A, int pos) { //TODO：将A插入到pos位置上 if (length + A.length > capacity) //如果长度不够扩容 { resize(length + A.length); } for (int i = length - 1; i >= pos; i--) { items[i + A.length] = items[i]; } for (int i = 0; i < A.length; i++) { items[pos + i] = A.items[i]; } length += A.length; } int index(String& T, int pos = 0) { //TODO：返回T出现的第一个位置，找不到则返回-1 } friend ostream& operator << (ostream& os, String& st); }; ostream& operator<< (ostream& os, String& st) { //标准输出流方式接口 for (int i = 0; i < st.length; i++) os << st.items[i]; return os; } -
“String.cpp”
#include <iostream> #include "./String.hpp" using namespace std; int main() //字符串测试函数 { String A("hello "); //测试显示构造函数 String B = "world!"; //测试类型转换构造函数 A.concat(B).output(); //测试A串连接B串并打印A串 printf("A - B = %d ", A.compare(B)); //测试A串和B串比较 String S("Such a day!"); String T("happy "); S.output(); T.output(); cout << "插入字符串"Such a happy day!"：" << endl; S.insert(T, 7); S.output(); //printf("子串搜索结果是：%d ", S.index(T));//测试求子串位置 return 0; } -
运行截图：
-
-
串的快速匹配——KMP Matching算法
-
“KMP Matching.cpp”
// Test4-2：串的快速匹配——KMP Matching算法 #include <iostream> #include "string.h" #include "time.h" using namespace std; // 暴力匹配算法 int Index(const char* S, const char* T, int pos = 0) { //从pos位置开始查找T，返回T最早出现的位置，如果不存在T，返回-1 int n = strlen(S), m = strlen(T); int i = pos, j = 0; while (i < n && j < m) { if (S[i] == T[j]) //若匹配则一并移动两个指针 { ++i; ++j; } else //若失配则退回重新开始 { i = i - j + 1; j = 0; } } if (j == m) return i - m; return -1; } // KMP Matching算法 void get_next(const char* T, int* next) { //next表构造函数 int i = 0; next[i] = -1; int j = -1; int m = strlen(T); while (i < m) { if (j == -1 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else j = next[j]; } } int Index_KMP(const char* S, const char* T, int pos) { //TODO：实现KMP匹配算法 int m = strlen(S), n = strlen(T); int* next = new int[n]; get_next(T, next); int i = pos, j = 0; while (i < m && j < n) { if (j < 0 || S[i] == T[j]) { ++i; ++j; } else { j = next[j]; } } if (j == n) return i - n; return -1; } int main() {//字符串匹配性能测试函数 char S[] = "00000000000000000000000000,0000000000001"; char T[] = "0000000000001"; int Next[20]; //Next[j]表示T[j]前的最长前后缀相等的长度 get_next(T, Next); int pos; int repeats = 10000000; time_t tBegin0, tEnd0, tBegin1, tEnd1; time(&tBegin0); //记录当前时间tBegin0 for (int i = 0; i < repeats; i++) pos = Index(S, T, 0); //暴力匹配算法测试 time(&tEnd0); //记录当前时间tEnd0 float cost0 = tEnd0 - tBegin0; //计算暴力匹配耗时 time(&tBegin1); //记录当前时间tBegin1 for (int i = 0; i < repeats; i++) pos = Index_KMP(S, T, 0); //KMP匹配算法测试 time(&tEnd1); //记录当前时间tEnd1 float cost1 = tEnd1 - tBegin1; //计算KMP算法匹配耗时 printf("子串暴力匹配算法结果是：%d，耗时%.2fs ", pos, cost0); printf("子串KMP匹配算法结果是： %d，耗时%.2fs ", pos, cost1); return 0; } -
运行截图：
-
-
稀疏矩阵的封装及其快速转置
-
“SparseMatrix.hpp”
//Test5-1：稀疏矩阵的封装及其快速转置 #pragma once #include <iostream> #include <iomanip> #include <memory> using namespace std; #include "../SeqList/SeqList.hpp" //利用顺序表实现三元组的元素存储 template <typename ElemType> struct Triplet { int row, col; //行列下标 ElemType e; //数据 Triplet() {} //必须提供默认构造函数，以便创建三元组数组 Triplet(int r, int c, ElemType v) { row = r; col = c; e = v; } void output() { // 标准化输出 cout << "*Triplet*" << endl; cout.setf(ios::right); cout << setw(5) << "row"; cout << setw(5) << "col"; cout << setw(5) << "ele"; cout << endl; cout << setw(5) << row; cout << setw(5) << col; cout << setw(5) << e; cout << endl; } }; template <typename ElemType> struct SparseMatrix :SeqList<Triplet<ElemType>> { int rows, cols; //行列大小 SparseMatrix(int r, int c, int n = 10) :SeqList<Triplet<ElemType>>(n) { rows = r; cols = c; } int getIndex(int r, int c) //将稠密矩阵的下标转为稀疏矩阵的下标，以便访问 { //此函数当输入索引三元组中的数据为零时，会返回其上一个下标的加一值 //TODO：将下面的顺序查找改为二分查找 //找不到的时候，返回恰好比rc大的存储元素的下标 int i = 0; for (i = 0; i < this->length; i++) { Triplet<ElemType>& t = this->items[i]; //取引用，减少对象的拷贝 if (t.row > r || t.row == r && t.col >= c) break; } return i; } void get(int r, int c) //获取元素 { int index = getIndex(r, c); if (index < this->length && this->items[index].row == r && this->items[index].col == c) return this->items[index].output(); else cout << "Not Find in Triplet!" << endl; //不存在就返回默认值 } void set(int r, int c, ElemType v) //修改元素 { int index = getIndex(r, c); if (index < this->length && this->items[index].row == r && this->items[index].col == c) this->items[index] = v; //TODO：写零时，做删除处理 else //当前的稀疏矩阵中，没有存储r行c列的元素，则插入元素 this->insertAt(index, Triplet<ElemType>(r, c, v)); } void output() { int k = 0; cout.setf(ios::right); cout << "Sparse Matrix: " << endl; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { ElemType v = ElemType(); //设置为默认值 if (k < this->length && i == this->items[k].row && j == this->items[k].col) { v = this->items[k].e; //如果存在元素，就改为元素值 k++; } cout << setw(4) << v; } cout << endl; } cout << endl; } void transposeMatrix() //实现三元组矩阵的快速转置 { //转置矩阵的快速实现方法 //创建并初始化列频数数组 int* arra = new int[cols]; //利用memset(指针或数组, 初始化值修改每一个字节（0-255）, 指针或数组的长度)方法初始化数组每个字节的值 memset(arra, 0, sizeof(int) * cols); /* //速度较慢，效率不如memset高 for (int i = 0; i < cols; i++) { arra[i] = 0; } */ for (int i = 0; i < this->length; i++) { int j = this->items[i].col; arra[j]++; } //创建并初始化累计列频数数组 int* copt = new int[cols]; copt[0] = 0; for (int i = 1; i < cols; i++) { copt[i] = copt[i - 1] + arra[i - 1]; } //创建转置矩阵 Triplet<ElemType>* data = new Triplet<ElemType>[10]; memcpy(data, this->items, this->length * sizeof(Triplet<ElemType>)); //内存拷贝函数将items复制到data //对转置矩阵的三元组重新进行排列 for (int i = 0; i < this->length; i++) { //提取当前三元组的列数 int col = this->items[i].col; //根据列频数和累计列频数，找到当前元素需要存放的位置 int location = copt[col]; //为转置矩阵赋值 //调用三元组的有参构造函数 data[location] = Triplet<ElemType>(this->items[i].col, this->items[i].row, this->items[i].e); /* //一次对三元组的数据成员赋值 data[location].row = this->items[i].col; data[location].col = this->items[i].row; data[location].e = this->items[i].e; */ //存放完成后，cpot数组对应的位置要+1，以便下次该列存储下一个三元组 copt[col]++; } //转置矩阵的输出 int k = 0; cout.setf(ios::right); cout << "Transpose Matrix: " << endl; for (int i = 0; i < cols; i++) { for (int j = 0; j < rows; j++) { ElemType v = ElemType(); if (k < this->length && i == data[k].row && j == data[k].col ) { v = data[k].e; //如果存在元素，就改为元素值 k++; } cout << setw(4) << v; } cout << endl; } cout << endl; } }; -
“SparseMatrix.cpp”
#include <iostream> #include "./SparseMatrix.hpp" using namespace std; int main() //测试稀疏矩阵及其运算 { //新建一个稀疏矩阵 SparseMatrix<int> m(6, 7); m.append(Triplet<int>(0, 1, 12)); m.append(Triplet<int>(0, 2, 9)); m.append(Triplet<int>(2, 0, -3)); m.append(Triplet<int>(2, 4, 14)); m.append(Triplet<int>(3, 2, 24)); m.append(Triplet<int>(4, 1, 18)); m.append(Triplet<int>(5, 0, 15)); m.append(Triplet<int>(5, 3, -7)); m.output(); //测试稀疏矩阵的输出 m.get(0, 2); //测试稀疏矩阵的查找 m.get(0, 3); m.transposeMatrix(); //测试稀疏矩阵的快速转置方法的实现 } -
运行截图：
-
