《数据结构知识点总结》由会员分享，可在线阅读，更多相关《数据结构知识点总结（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构知识点总结 1 / 35 第一章概论 数据就就是指能够被计算机识别、存储与加工处理得信息得载体。数据元素就是数据得基本单位，可以由若干个数据项组成。数据项就是具有独立含义得最小标识单位。 数据结构得定义： 逻辑结构：从逻辑结构上描述数据，独立于计算机。线性结构：一对一关系。 线性结构：多对多关系。 存储结构：就是逻辑结构用计算机语言得实现。顺序存储结构：如数组。 链式存储结构：如链表。 索引存储结构：稠密索引：每个结点都有索引项。 稀疏 xx：每组结点都有 xx 项。 散列存储结构：如散列表。 数据运算。 对数据得操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 常用得有：检索、
2、插入、删除、更新、排序。 数据类型：就是一个值得集合以及在这些值上定义得一组操作得总称。 结构类型：由用户借助于描述机制定义，就是导出类型。 抽象数据类型 ADT：就是抽象数据得组织与与之得操作。相当于在概念层上描述问题。 优点就是将数据与操作封装在一起实现了信息隐藏。 2 / 35 程序设计得实质就是对实际问题选择一种好得数据结构，设计一个好得算法。算法取决于数据结构。 算法就是一个良定义得计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法得好坏得因素：算法就是正确得； 执行算法得时间； 执行算法得存储空间（主要就是辅助存储空间）； 算法易于理解、编码、调试。 时间复杂度：就是某
3、个算法得时间耗费，它就是该算法所求解问题规模n 得函数。 渐近时间复杂度：就是指当问题规模趋向无穷大时，该算法时间复杂度得数量级。 评价一个算法得时间性能时，主要标准就就是算法得渐近时间复杂度。 算法中语句得频度不仅与问题规模有关，还与输入实例中各元素得取值相关。 时间复杂度按数量级递增排列依次为：常数阶 O（1）、对数阶 O （log2n）、线性阶 O（n）、线性对数阶 O（nlog2n）、平方阶 O（n2）、 立方阶 O（n3）、k 次方阶 O（nk）、指数阶 O（2n）。 空间复杂度：就是某个算法得空间耗费，它就是该算法所求解问题规模n 得函数。 算法得时间复杂度与空间复杂度合称算法复杂
4、度。 第二章线性表 线性表就是由 n0 个数据元素组成得有限序列。 3 / 35 n=0 就是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。 线性表上定义得基本运算： 构造空表：Initlist（L） 求表长：Listlength（L） 取结点：GetNode（L，i） 查找：LocateNode（L，x） 插入：InsertList（L，x，i） 删除：Delete（L，i） 顺序表就是按线性表得逻辑结构次序依次存放在一组地址连续得存储单元中。在存储单元中得各元素得物理位置与 逻辑结构中各结点相邻关系就是一致得。地址计算：LOCa（i）=LOCa（1）+（i-1）*d；（首地址为
5、 1）在顺序表中实现得基本运算： 每个结点值得同时，还存储了其后继结点得地址信息（即指针或 链）。这两部分信息组成链表中得结点结构。 一个单链表由头指针得名字来命名。 单链表运算： 建立单链表头插法：s-next=head；head=s；生成得顺序与输入顺序相反。平均时间复杂度均为 O（n）。 尾插法：head=rear=null；if（head=null）head=s；else r-next=s；r=s；平均时间复杂度均为 O（n）加头结点得算法：对开始结点得操作无需特殊处理，统一了空表与非空表。 查找按序号：与查找位置有关，平均时间复杂度均为 O（n）。按值：与输入实例有关，平均时间复杂度
6、均为 O（n）。 4 / 35 插入运算：p=GetNode（L，i-1）；s-next=p-next；p-next=s；平均时间复杂度均为 O（n）删除运算：p=GetNode（L，i-1）；r=p-next；p-next=r-next；free（r）；平均时间复杂度均为 O（n）单循环链表就是一种首尾相接得单链表，终端结点得指针域指向开始结点或头结点。链表终止条件就是以指针等于头指针或尾指针。 采用单循环链表在实用中多采用尾指针表示单循环链表。优点就是查找头指针与尾指针得时间都就是 O（1），不用 遍历整个链表。 双链表就就是双向链表，就就是在单链表得每个结点里再增加一个指向其直接前趋得指
7、针域 prior，形成两条不同方 向得链。由头指针 head 惟一确定。 双链表也可以头尾相链接构成双（向）循环链表。 双链表上得插入与删除时间复杂度均为 O （1）。 顺序表与链表得比较：基于空间： 顺序表得存储空间就是静态分配，存储密度为 1；适于线性表事先确定其大小时采用。 链表得存储空间就是动态分配，存储密度1；适于线性表长度变化大时采用。 基于时间： 顺序表就是随机存储结构，当线性表得操作主要就是查找时，宜采用。 以插入与删除操作为主得线性表宜采用链表做存储结构。 若插入与删除主要发生在表得首尾两端，则宜采用尾指针表示得单循环链表。 第三章栈与队列 5 / 35 栈（Stack）就是
8、仅限制在表得一端进行插入与删除运算得线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈得修改就是按后进先出得原则进行得，我们又称栈为 LIFO 表（Last In First Out）。通常栈有 顺序栈与链栈两种存储结构。 栈得基本运算有六种：构造空栈：InitStack（S） 判栈空：StackEmpty（S） 判栈满：StackFull（S） 进栈：Push（S，x） 退栈：Pop（S） 取栈顶元素：StackTop（S） 在顺序栈中有“上溢”与“下溢”得现象。“上溢”就是栈顶指针指出栈得外面就是出错状态。 “下溢”可以表示栈为空栈，因此用来作为控制转移得条件。顺序栈
9、中得基本操作有六种：构造空栈判栈空判栈满进栈退栈取栈顶元素链栈则没有上溢得限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表得头指针就可以了。 链栈中得基本操作有五种：构造空栈判栈空进栈退栈取栈顶元素 队列（Queue）就是一种运算受限得线性表，插入在表得一端进行，而删除在表得另一端进行，允许删除得一端称为队头（front），允许插入得一端称为队尾（rear），队列得操作原则就是先进先出得，又称作FIFO 表（First In First Out）、队列也有顺序存储与链式存储两种存储结构。入队：EnQueue（Q，x） 出队：DeQueue（Q） 取队头元素：QueueFront
10、（Q） 6 / 35 顺序队列得“假上溢”现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列就是空得却产生了“上 溢”现象。 为了克服“假上溢”现象引入循环向量得概念，就是把向量空间形成一个头尾相接得环形，这时队列称循环队列。 判定循环队列就是空还就是满，方法有三种： 一种就是另设一个 xx 变量来判断； 第二种就是少用一个元素空间，入队时先测试（rear+1）%m = front）？满：空； 第三种就就是用一个计数器记录队列中得元素得总数。 队列得链式存储结构称为链队列，一个链队列就就是一个操作受限得单链表。为了便于在表尾进行插入（入队）得操作，在表尾增加一个尾指针，一个链队列就由一个头指针与一个尾指针唯一地确定。链队列不存在队满与上溢得问题。在链队列得出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。 第四章串 串就是零个或多个字符组成得有限序列。 空串：就是指长度为零得串，也就就是串中不包含任何字符（结点）。 空白串：指串中包含一个或多个空格字符得串。 在一个串中任意个连续字符组成得子序列称为该串得子串，包
