前言： 本系列是笔者暑假自学数据结构的笔记整理而来，共126页，3w+字。现在正式开学上课，补充老师所讲内容，并且仔细勘误，根据老师的教学进度分章节发布在上。 教材使用的是王红梅等所著的数据结构——从概念到C++实现（第三版）。 暑假自学时期主要参考的网课： 青岛大学-王卓 武汉大学-李春葆

目录

串定义与概念基本运算串的模式匹配 数组定义与概念稀疏矩阵基本运算 十字链表广义表

串

定义与概念

基本运算

/* StrAssign(&s, cstr):将字符串常量cstr赋值给串s，即生成其值等于cstr的串s StrCopy(&s, t):串复制，将串t赋值给串s StrEqual(s, t):判断串是否相等，若相等返回真，若不等返回假 StrLength(s):求串长，返回串s中的字符个数 Concat(s, t):串连接，返回由串s和串t连接在一起的新串 SubStr(s, i, j):求子串，返回串s中从第i个字符开始的连续的j个字符组成的子串 InsStr(s1, i, s2):插入，将串s2插入到串s1的第i个字符中，返回新串 DelStr(s, i, j):删除，从串s中删去从第i个字符开始的长度为j的子串，并返回产生的新串 RepStr(s, i, j, t):替换，在串s中，将第i个字符开始的连续的j个字符构成的子串用串t替换，并返回新串 DispStr(s):串输出，输出串s的所有值 */

类似的，串可分为两类—顺序串和链串。而串的顺序存储又有两种方法：1.每个单元(例如4字节)只存一个字符，称为非紧缩格式，其存储密度小。2.每个单元存放多个字符，称为紧缩格式，其存储密度大。我们一般讨论前者。

//对于非紧缩格式的字符串，类型定义如下 #define MAXSIZE 100 typedef struct { char data[MAXSIZE]; int length;//字符串长度 }SqString;

顺序串中实现串的基本运算与顺序表的基本运算类似，详细算法见教材。 Eg： 实现Strcmp(s1, s2):

int Strcmo(SqString s, SqString t) { int i, len; len = s.length <= t.length?s.length:t.length; for (i = 0; i < len; i++) { return (s.data[i]>t.data[i]) && (s.data[i] != t.data[i])?1:-1; } if (s.length == t.length) { return 0; } else { return s.length > t.length?1:-1; } }

链串的组织形式与一般的链表类似。 链串中的一个节点可以存储多个字符。通常将链串中每个节点所存储的字符个数称为节 点大小，链串不一定只能采用单链表，要依据情况而定。如果需要从某个节点出发前后查找，可以采用双链表，如果需要快速查找尾结点，可以采用循环双链表。 我们一般只考虑节点大小为1的链串，定义如下：

typedef struct snode { char data; struct snode *next; }LiString;

同样的，链串中实现串的基本运算与单链表的基本运算类似，详细算法见教材。

串的模式匹配

这部分内容请参看我的另一篇文章： 【数据结构】串模式匹配及KMP算法详解——看不懂来砍我

一些习题 1.str=”Software”，其子串个数？ 解：如果原串没有重复元素，那么子串共n(n+1)/2+1

数组

定义与概念

优先存储压缩 一个习题： 若将n阶上三角矩阵A按列优先顺序存储压缩存放在一维数组B[1…n(n+1)/2]中，A中第一个非零元素a11 存放于B数组的b1中，则应存放到bk中的非零元素aij的下标i、j与k的对应关系是？ 解：1~j-1列的元素个数是：j(j-1)/2，第j列aij之前的元素个数：i-1，故k= j(j-1)/2+ i-1 +1 = j(j-1)/2+i。

稀疏矩阵

一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小，即s<<t时，称该矩阵为稀疏矩阵。 稀疏矩阵的压缩存储办法是只存储非零元素，稀疏矩阵中的每一个非零元素需由一个三元组 唯一确定，稀疏矩阵中的左右非零元素构成三元组线性表。

基本运算

#define MAXSIZE 100 #define ElemType int typedef struct { int r;//行号 int c;//列号 ElemType d;//元素值 }TupNode;//三元组定义 typedef struct { int rows;//行数值 int cols;//列数值 int nums;//非零元素个数 TupNode data[MAXSIZE]; }TsMatrix;//三元组顺序表定义 void CreateMat(TsMatrix &t, ElemType A[M][N]) { int i, j; t.rows = M; t.cols = N; t.nums = 0; for (i = 0; i < M; i++) { for (j = 0; j < N; j++) { if (A[i][j] != 0) { t.data[t.nums].r = i; t.data[t.nums].c = j; t.data[t.nums].d = A[i][j]; t.nums++; } } } } //在下标为i，j的位置赋值为x bool Value(TsMatrix &t, ElemType x, int i, int j) { int k = 0, k1; if (i >= t.rows || j >= t.cols) { return false;//ij违法返回false } while (k < t.nums && i > t.data[k].r)//查找行 { k++; } while (k < t.nums && i == t.data[k].r && j > t.data[k].c)//查找列 { k++; } if (t.data[k].r == i && t.data[k].c == j)//找到了 { t.data[k].d = x; } else//不存在就插入一个元素 { for (k1 = t.nums - 1; k1 >= k; k1--) { t.data[k1 + 1].r = t.data[k1].r; t.data[k1 + 1].c = t.data[k1].c; t.data[k1 + 1].d = t.data[k1].d; } t.data[k].r = i; t.data[k].c = j; t.data[k].d = x; t.nums++; } return true; } //将指定的元素值赋给变量 bool Assign(TsMatrix t, ElemType &x, int i, int j) { int k = 0; if (i >= t.rows || j >= t.cols) { return false; } while (k < t.nums && i > t.data[k].r)//查找行 { k++; } while (k < t.nums && i == t.data[k].r && j > t.data[k].c)//查找列 { k++; } if (t.data[k].r == i && t.data[k].c == j)//找到了 { x = t.data[k].d; } else//没找到，就置x为0 { x = 0; } return true; } //输出三元组 void DispMat(TsMatrix t) { if (t.nums <= 0) { return; } cout << "\t" << t.rows << "\t" << t.cols << "\t" << t.nums; cout << "-------------------------------------------"; for (int i = 0; i < t.nums; i++) { cout << "\t" << t.data[i].r << "\t" << t.data[i].c << "\t" << t.data[i].d; } } //矩阵转置，一种非高效算法 //m行n列，t个非0元素，时间复杂度为O(nt) void TranTat(TsMatrix t, TsMatrix &tb) { int p, q = 0, v;//q为tb.data的下标 tb.rows = t.cols; tb.cols = t.rows; tb.nums = t.nums; if (t.nums != 0)//当存在非零元素时执行转置 { for (v = 0; v < t.cols; v++)//tb.data[q]中记录以列序排列 { for (p = 0; p < t.nums; p++)//p为t.data的下标 { if (t.data[p].c == v) { tb.data[q].r = t.data[p].c; tb.data[q].c = t.data[p].r; tb.data[q].d = t.data[p].d; q++; } } } } }

十字链表

特殊矩阵压缩存储后仍具有随机存取特性，但一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去随机存取特性。

广义表

以上 如果此篇博客对您有帮助欢迎点赞与转发 有疑问请留言或私信 2020/10/3