halo~我是bay_Tong桐小白 本文内容是桐小白个人对所学知识进行的总结和分享,知识点会不定期进行编辑更新和完善,了解最近更新内容可参看更新日志,欢迎各位大神留言、指点
最近更新:
更新内容——计算机统考408考纲要求、考察目标与变动情况(2020.9.19)持续更新中……2021计算机统考408考纲数据结构学科考察目标
掌握数据结构的基本概念、基本原理和基本方法掌握数据结构的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析能够运用数据结构的基本原理和方法进行问题的分析与求解,具备采用C或C++语言设计与实现算法的能力2021计算机统考408数据结构考纲变动情况 2021计算机统考408考纲对栈、队列和数组部分考察要求
考纲中将栈、队列和数组归为一类进行考察,栈和队列的详细总结可见本栏文章《栈和队列总结——基本知识要点汇总》
对于对称矩阵,可以为每一对对称元分配一个存储空间,则可将n^2个元压缩存储到n(n+1)/2个元的空间中。一般的,习惯以行序为主序存储下三角矩阵(包括对角线)中的元
【后续更新】
【问题引入:对于上述矩阵的存储,当用二维数组存储,但矩阵为稀疏矩阵(即矩阵中包含大量0元素)时会造成大量的存储空间浪费。因此引入多重链表进行存储。】
多重链表:链表中的结点可能同时隶属于多个链多重链表中结点的指针域会有多个,但包含多个指针域的链表不一定是多重链表,比如在双向链表中每个结点含有多个指针域但结点不同时隶属于多个链,因此它不是多重链表多链表在树、图中会大量被使用对于上述例子,采用典型的多重链表——十字链表来存储稀疏矩阵 即每个结点通过两个指针域(行指针Right与列指针Down)把同行同列串起来,结点的数据域存储行坐标Row、列坐标Col、数值Value
具体存储结构:
表中的head为行列的头结点,通过next指针相连,通过Right与Down将矩阵行与列进行联系串联最左上角的Term可看作是矩阵的访问入口,其指针域只用一个即可,通过它即可进行矩阵的遍历访问。其中的数据元素表明矩阵有几行几列共几个存储单元表中的head与Term中,通过down指针依次访问形成的一个循环链表,即为矩阵中的某一行的遍历,对应的,通过right指针依次访问形成的一个循环链表,即为矩阵中的某一列的遍历【详细讲解后续持续更新调整】
广义表定义,顾名思义,就是线性表的推广,也有人称其为列表。对于线性表,表中的n个元素都是基本的单元素;对于广义表,这些元素可以是单元素也可以是另一个广义表
多重链表实质就是广义表的一种存储体现 在C语言中可用Union和一个标记Tag来区分广义表中的元素是单元素还是另一个广义表
持续更新中…… 我是桐小白,一个摸爬滚打的计算机小白