数据结构c语言版知识点概括.docx

数据构造学问点概括
第一章 概 论
数据就是指可以被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的根本单位，可以由假设干个数据项组成。数据项是具有独立含义的最小标识单位。
数据构造的定义：
·逻辑构造：从逻辑构造上更大时承受。
　　·基于时间：
　　·依次表是随机存储构造，当线性表的操作主要是查找时，宜承受。
　　·以插入和删除操作为主的线性表宜承受链表做存储构造。
·假设插入和删除主要发生在表的首尾两端，那么宜承受尾指针表示的单循环链表。
第三章 栈和队列
　　栈〔〕是仅限制在表的一端进展插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原那么进展的，我们又称栈为表〔 〕。通常栈有
依次栈和链栈两种存储构造。
　　栈的根本运算有六种： ·构造空栈：〔S〕
　　·判栈空： 〔S〕
　　·判栈满： 〔S〕
　　·进栈： 〔S，x〕
　　·退栈： 〔S〕
　　·取栈顶元素：〔S〕
　　在依次栈中有“上溢〞和“下溢〞的现象。 ·“上溢〞是栈顶指针指出栈的外面是出错状态
。
　　·“下溢〞可以表示栈为空栈，因此用来作为限制转移的条件。
　　依次栈中的根本操作有六种：·构造空栈 ·判栈空 ·判栈满 ·进栈 ·退栈 ·取栈顶元素
　　链栈那么没有上溢的限制，因此进栈不要判栈满。链栈不须要在头部附加头结点，只要有链表的头指针就可以了。
链栈中的根本操作有五种：·构造空栈 ·判栈空 ·进栈 ·退栈 ·取栈顶元素
队列〔〕是一种运算受限的线性表，插入在表的一端进展，而删除在表的另一端进展，允许删除的一端称
为队头〔〕，允许插入的一端称为队尾〔〕 ，队列的操作原那么是先进先出的，又称作表〔
〕 .队列也有依次存储和链式存储两种存储构造。
队列的根本运算有六种：　　·置空队：〔Q〕
　·判队空：〔Q〕
　·判队满：〔Q〕
　·入队：〔Q，x〕
　·出队：〔Q〕
　·取队头元素：〔Q〕
　　依次队列的“假上溢〞现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了“上
溢〞现象。
　为了抑制“假上溢〞现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
断定循环队列是空还是满，方法有三种：
·一种是另设一个布尔变量来推断；
·第二种是少用一个元素空间，入队时先测试〔〔1〕 = 〕？ 满：空；
　　·第三种就是用一个计数器记录队列中的元素的总数。
队列的链式存储构造称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进展插入〔入队〕的
操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢
的问题。在链队列的出队算法中，要留意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。
第四章 串
　　串是零个或多个字符组成的有限序列。
　　·空串：是指长度为零的串，也就是串中不包含任何字符〔结点〕。
　　·空白串：指串中包含一个或多个空格字符的串。
　　·在一个串中随意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。
　　·子串在主串中的序号就是指子串在主串中首次出现的位置。
　　·空串是随意串的子串，随意串是自身的子串。
　　串分为两种： ·串常量在程序中只能引用不能变更；
　　·串变量的值可以变更。
　　串的根本运算有： ·求串长〔*s〕
·串复制〔*，*〕
　·串联接〔*，*〕
　·串比较〔*s1，*s2〕
·字符定位〔*s，〕
　串是特殊的线性表〔结点是字符〕，所以串的存储构造及线性表的存储构造类似。串的依次存储构造简称为依次串。
　依次串又可按存储支配的不同分为：
·静态存储支配：干脆用定长的字符数组来定义。优点是涉及串长的操作速度
快，但不相宜插入、链接操作。
　·动态存储支配：是在定义串时担忧排存储空间，须要运用时按所需串的长度支配存储单元。
　串的链式存储就是用单链表的方式存储串值，串的这种链式存储构造简称为链串。链串及单链表的差异只是它的 结
点数据域为单个字符。
为理解决“存储密度〞低的状况，可以让一个结点存储多个字符，即结点的大小。
　　依次串上子串定位的运算：又称串的“形式匹配〞或“串匹配〞，是在主串中查找出子串出现的位置。在串匹配中，将主串称为目的〔串〕，子串称为形式〔串〕。这是比较简洁理解的，串匹配问题就是找出给定形式串P在给定目的串T中首次出现的有效位移或者是全部有效位移。最坏的状况下时间困难度是O〔〔1〕m〕，假设m及n同阶
的话那么它是O〔