《数据结构c语言版知识点概括》由会员分享，可在线阅读，更多相关《数据结构c语言版知识点概括（13页珍藏版）》请在金锄头文库上搜索。
1、-数据构造知识点概括第一章 概 论数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的根本单位，可以由假设干个数据项组成。数据项是具有独立含义的最小标识单位。数据构造的定义：逻辑构造：从逻辑构造上描述数据，独立于计算机。线性构造：一对一关系。线性构造：多对多关系。存储构造：是逻辑构造用计算机语言的实现。顺序存储构造：如数组。链式存储构造：如链表。索引存储构造：稠密索引：每个结点都有索引项。稀疏索引：每组结点都有索引项。散列存储构造：如散列表。数据运算。对数据的操作。定义在逻辑构造上，每种逻辑构造都有一个运算集合。常用的有：检索、插入、删除、更新、排序。数据类型：是一个值的集
2、合以及在这些值上定义的一组操作的总称。构造类型：由用户借助于描述机制定义，是导出类型。抽象数据类型ADT：是抽象数据的组织和与之的操作。相当于在概念层上描述问题。优点是将数据和操作封装在一起实现了信息隐藏。程序设计的实质是对实际问题选择一种好的数据构造，设计一个好的算法。算法取决于数据构造。算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：算法是正确的；执行算法的时间；执行算法的存储空间主要是辅助存储空间；算法易于理解、编码、调试。时间复杂度：是*个算法的时间消耗，它是该算法所求解问题规模n的函数。渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间
3、复杂度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。时间复杂度按数量级递增排列依次为：常数阶O1、对数阶Olog2n、线性阶On、线性对数阶Onlog2n、平方阶On2、立方阶On3、k次方阶Onk、指数阶O2n。空间复杂度：是*个算法的空间消耗，它是该算法所求解问题规模n的函数。算法的时间复杂度和空间复杂度合称算法复杂度。第二章 线性表线性表是由n0个数据元素组成的有限序列。n=0是空表；非空表，只能有一个开场结点，有且只能有一个终端结点。线性表上定义的根本运算：构造空表：InitlistL求表长：L
4、istlengthL取结点：GetNodeL，i查找：LocateNodeL，*插入：InsertListL，*，i删除：DeleteL，i顺序表是按线性表的逻辑构造次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑构造中各结点相邻关系是一致的。地址计算：LOCai=LOCa1+i-1*d；首地址为1在顺序表中实现的根本运算：插入：平均移动结点次数为n/2；平均时间复杂度均为On。删除：平均移动结点次数为n-1/2；平均时间复杂度均为On。线性表的链式存储构造中结点的逻辑次序和物理次序不一定一样，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结
5、点的地址信息即指针或链。这两局部信息组成链表中的结点构造。 一个单链表由头指针的名字来命名。单链表运算：建立单链表头插法：s-ne*t=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为On。尾插法：head=rear=null；ifhead=null head=s；else r-ne*t=s；r=s； 平均时间复杂度均为On加头结点的算法：对开场结点的操作无需特殊处理，统一了空表和非空表。查找按序号：与查找位置有关，平均时间复杂度均为On。按值：与输入实例有关，平均时间复杂度均为On。插入运算：p=GetNodeL，i-1；s-ne*t=p-ne*t；p-ne*t=s；平均
6、时间复杂度均为On删除运算：p=GetNodeL，i-1；r=p-ne*t；p-ne*t=r-ne*t；freer；平均时间复杂度均为On单循环链表是一种首尾相接的单链表，终端结点的指针域指向开场结点或头结点。链表终止条件是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O1，不用遍历整个链表。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方向的链。由头指针head惟一确定。双链表也可以头尾相构成双向循环链表。双链表上的插入和删除时间复杂度均为O 1。顺序表和链表的比拟：基于空间
7、：顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。链表的存储空间是动态分配，存储密度1；适于线性表长度变化大时采用。基于时间：顺序表是随机存储构造，当线性表的操作主要是查找时，宜采用。以插入和删除操作为主的线性表宜采用链表做存储构造。假设插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。第三章 栈和队列栈Stack是仅限制在表的一端进展插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进展的，我们又称栈为LIFO表Last In First Out。通常栈有顺序栈和链栈两种存储构造。栈的根本
8、运算有六种： 构造空栈：InitStackS判栈空： StackEmptyS判栈满： StackFullS进栈： PushS，*退栈： PopS取栈顶元素：StackTopS在顺序栈中有上溢和下溢的现象。 上溢是栈顶指针指出栈的外面是出错状态。下溢可以表示栈为空栈，因此用来作为控制转移的条件。顺序栈中的根本操作有六种：构造空栈判栈空判栈满进栈退栈取栈顶元素链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。链栈中的根本操作有五种：构造空栈判栈空进栈退栈取栈顶元素队列Queue是一种运算受限的线性表，插入在表的一端进展，而删除在表的另一端进展，允许删
9、除的一端称为队头front，允许插入的一端称为队尾rear ，队列的操作原则是先进先出的，又称作FIFO表First In First Out .队列也有顺序存储和链式存储两种存储构造。队列的根本运算有六种：置空队：InitQueueQ判队空：QueueEmptyQ判队满：QueueFullQ入队：EnQueueQ，*出队：DeQueueQ取队头元素：QueueFrontQ顺序队列的假上溢现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了上溢现象。为了克制假上溢现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。判定循环队列是空还是满，方
10、法有三种： 一种是另设一个布尔变量来判断；第二种是少用一个元素空间，入队时先测试rear+1%m = front？ 满：空；第三种就是用一个计数器记录队列中的元素的总数。队列的链式存储构造称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进展插入入队的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。第四章 串串是零个或多个字符组成的有限序列。空串：是指长度为零的串，也就是串中不包含任何字符结点。空白串：指串中包含一个或多个空格字符的串。
11、在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。子串在主串中的序号就是指子串在主串中首次出现的位置。空串是任意串的子串，任意串是自身的子串。串分为两种： 串常量在程序中只能引用不能改变；串变量的值可以改变。串的根本运算有： 求串长strlenchar*s串复制strcpychar*to，char*from串联接strcatchar*to，char*from串比拟charcmpchar*s1，char*s2字符定位strchrchar*s，charc串是特殊的线性表结点是字符，所以串的存储构造与线性表的存储构造类似。串的顺序存储构造简称为顺序串。顺序串又可按存储分配的
12、不同分为：静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度快，但不适合插入、操作。动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。串的链式存储就是用单链表的方式存储串值，串的这种链式存储构造简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。为了解决存储密度低的状况，可以让一个结点存储多个字符，即结点的大小。顺序串上子串定位的运算：又称串的模式匹配或串匹配，是在主串中查找出子串出现的位置。在串匹配中，将主串称为目标串，子串称为模式串。这是比拟容易理解的，串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移。
13、最坏的情况下时间复杂度是On-m+1m，假设m与n同阶的话则它是On2。链串上的子串定位运算位移是结点地址而不是整数第五章 多维数组数组一般用顺序存储的方式表示。存储的方式有： 行优先顺序，也就是把数组逐行依次排列。PASCAL、C列优先顺序，就是把数组逐列依次排列。FORTRAN地址的计算方法： 按行优先顺序排列的数组：LOCaij=LOCa11+i-1*n+j-1*d.按列优先顺序排列的数组：LOCaij=LOCa11+j-1*n+i-1*d.矩阵的压缩存储：为多个一样的非零元素分配一个存储空间；对零元素不分配空间。特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。稀疏
14、矩阵的概念：一个矩阵中假设其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。特殊矩阵的类型： 对称矩阵：满足aij=aji。元素总数nn+1/2.I=ma*i，j，J=mini，j，LOCaij=LOCsa0+I*I+1/2+J*d.三角矩阵： 上三角阵：k=i*2n-i+1/2+j-i，LOCaij=LOCsa0+k*d.下三角阵：k=i*i+1/2+j，LOCaij=LOCsa0+k*d.对角矩阵：k=2i+j，LOCaij=LOCsa0+k*d.稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。参加行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。第六章 树树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。根是开
