数据结构---特殊矩阵和广义表

🌞欢迎来到机器学习的世界 
🌈博客主页：卿云阁

💌欢迎关注🎉点赞👍收藏⭐️留言📝

🌟本文由卿云阁原创！

🙏作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢！

---

目录

一维数组

 二维数组

普通矩阵的存储 

 对称矩阵的压缩存储

三对角矩阵的压缩存储

稀疏矩阵的压缩存储 

广义表 

---

一维数组

        我们定义int a[0],起始地址LOC，LOC(ai)=LOC+i×k，其中i表示数组的下标，k表示一个数据元素所占的字节数。 比如此时要计算(假设起始地址是400，k=4)。

                                  LOC(a3)=400+3*4=412

---

 二维数组

       二维数组a[i][j]某一个元素地址的计算和一维数组的计算类似关键是判断前面有多少个元素。

---

普通矩阵的存储 

---

 对称矩阵的压缩存储

 

 

         上三角矩阵中，主对角线之上的第i行(0≦i<n)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有 (n-i)(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：aii,aii+1,…aij-1。

---

三对角矩阵的压缩存储

---

稀疏矩阵的压缩存储 

       比如第一行的4在第一行第三列，5这个元素在第一行第六列。此时如果想访问某一个三元组，只能顺序访问失去了随机存储的特性。

//三元组结构体
typedef struct{//所在行数，列数int i,j;//值int e;
}triple;

      定义一个向下域（down[])数组，数组里面存放的是一个一个的指针，我们把这些指针称之为向下域，这里的每一个指针就对应了稀疏矩阵的每一列，定义一个向右域（right[])数组，这里的每一个指针就对应了稀疏矩阵的每一行，每一个非0元素都对应着一个节点，这个节点包括非0元素的行，列，值，另外还有两个指针。第一行的第一个非0元素是4，第一行第三列对应的值是4。

---

广义表 

     广义表是线性表的推广。线性表中的元素仅限于原子项(单个数据元素)，而广义表中的元素既可以是原子项，也可以是子表(另一个线性表)。