🔑【数据结构】之串、数组、矩阵和广义表

串、数组、矩阵、与广义表

串数据类型的定义

串的定义

• 串是由零个或多个字符组成的有限序列
• 字符的个数称为串的长度
• 零个元素的串叫空串
• \0 为编译器识别字符串结束的标记
• 注意空串和空格串的区别

char str[]=“abcdef”;//元素为a-f、\0，str数组长度为7，串str长度为6

串的存储结构

一般采用动态分配存储表示

tpyedef struct
{
    char *ch;//指向动态指针分配存储区首地址的字符指针
    int length;// 串长度（不是字符长度）
}

数组

• 一维数组
• 二维数组
  • 行优先
  • 列优先

矩阵的压缩存储

矩阵

• 注意区分题目有的第一个元素是a00有的是a11
• 矩阵转置
• 矩阵相加
• 矩阵相乘
• 压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间
• 压缩存储的目标：节约存储空间
• 压缩的方法：零元不存储；多个值相同的只存一个
• 压缩存储的对象：特殊矩阵、稀疏矩阵

特殊矩阵和稀疏矩阵

• 定义：相同的元素或者零元素在矩阵中存在一定规律的矩阵称为特殊矩阵，反之称为稀疏矩阵
• （国外）：矩阵中大多数元素都为0的矩阵称为稀疏矩阵
• 特殊矩阵：
  • 对称矩阵：$a_{ij}=a_{ji}$，主对角线元素对等，相同元素只需保存一份，所需空间为$$\frac{(1+n)n}{2}$$
  • 三角阵：上三角：矩阵下三角部分（不包括对角线）元素全为c（c可为0）；下三角（与上相反），所需空间为$$\frac{(1+n)n}{2}+1（需要存储c）$$
  • 对角矩阵：除了主对角线以及上下两条带状区域的元素外，其余都为c（可为0）（补充）

• 稀疏矩阵：常用的顺序存储方式有三元组表示法和伪地址表示法
• 注意：稀疏矩阵压缩存储后失去随机存取特性

广义表

• 长度：表中最上层元素的个数
• 深度：括号的最大层数
• 表头（Head）和表尾（Tail）：当广义表非空时，第一个元素为表头，其余元素伪表尾