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

-
. z
数据构造知识点概括
第一章 概 论
数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是或尾指针。
　　采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O〔1〕，不用
遍历整个链表。
　　双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方
向的链。由头指针head惟一确定。
　　双链表也可以头尾相构成双〔向〕循环链表。
　　双链表上的插入和删除时间复杂度均为O 〔1〕。
　　顺序表和链表的比拟：　　·基于空间：
·顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。
·链表的存储空间是动态分配，存储密度＜1；适于线性表长度变化大时采用。
·基于时间：
·顺序表是随机存储构造，当线性表的操作主要是查找时，宜采用。
·以插入和删除操作为主的线性表宜采用链表做存储构造。
·假设插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。
第三章 栈和队列
　　栈〔Stack〕是仅限制在表的一端进展插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进展的，我们又称栈为LIFO表〔Last In First Out〕。通常栈有
顺序栈和链栈两种存储构造。
　　栈的根本运算有六种： ·构造空栈：InitStack〔S〕
·判栈空： StackEmpty〔S〕
·判栈满： StackFull〔S〕
·进栈： Push〔S，*〕
·退栈： Pop〔S〕
·取栈顶元素：StackTop〔S〕
　　在顺序栈中有"上溢〞和"下溢〞的现象。 ·"上溢〞是栈顶指针指出栈的外面是出错状态。
·"下溢〞可以表示栈为空栈，因此用来作为控制转移的条件。
　　顺序栈中的根本操作有六种：·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素
　　链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。
链栈中的根本操作有五种：·构造空栈·判栈空·进栈·退栈·取栈顶元素
队列〔Queue〕是一种运算受限的线性表，插入在表的一端进展，而删除在表的另一端进展，允许删除的一端称
为队头〔front〕，允许插入的一端称为队尾〔rear〕 ，队列的操作原则是先进先出的，又称作FIFO表〔First In
First Out〕 .队列也有顺序存储和链式存储两种存储构造。
队列的根本运算有六种：　　·置空队：InitQueue〔Q〕
·判队空：QueueEmpty〔Q〕
·判队满：QueueFull〔Q〕
·入队：EnQueue〔Q，*〕
·出队：DeQueue〔Q〕
·取队头元素：QueueFront〔Q〕
　　顺序队列的"假上溢〞现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上
溢〞现象。
为了克制"假上溢〞现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种：
·一种是另设一个布尔变量来判断；
·第二种是少用一个元素空间，入队时先测试〔〔rear+1〕%m = front〕？ 满：空；
-
. z
·第三种就是用一个计数器记录队列中的元素的总数。
队列的链式存储构造称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进展插入〔入队〕的
操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢
的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。
第四章 串
　　串是零个或多个字符组成的有限序列。
·空串：是指长度为零的串，也就是串中不包含任何字符〔结点〕。
·空白串：指串中包含一个或多个空格字符的串。
·在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。
·子串在主串中的序号就是指子串在主串中首次出现的位置。
·空串是任意串的子串，任意串是自身的子串。
　　串分为两种： ·串常量在程序中只能引用不能改变；
·串变量的值可以改变。
　　串的根本运算有： ·求串长strlen〔char*s〕
·串复制strcpy〔char*to，char*from〕
·串联接str