数据结构导论-自学考试-概念整理.doc

第 一 章 概论 第 二 章 线 性 表 第 三 章 栈 和 队 列 第 四 章 串 第 五 章 多 维 数 组 第 六 章 树 第 七 章 图 第 八 章 排序 第 九 章 查找第 一 章 概 论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括： 1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的质量： 1正确性；算法应能正确地事先预定的功能。 2易读性；算法应易于阅读和理解，以便于调试和扩充。 3健壮性；当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。 4高效率；即达到所需的时间和空间性能。 11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。 时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2)、线性阶O(n)、线性对数阶O(nlog2)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。 13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。 12.算法的特征：有穷性；确定性；可行性；输入；输出。 13. 决定算法运行时间的因素：（1）问题的规模；（2）编译时间；（3）指令执行速度；（4）重复执行指令的速度。 第 二 章 线 性 表 1.线性表：是由n(n0)个数据元素组成的有穷序列。 2.线性表的基本运算有： 1）Initiate(L),加工型运算，作用是构造空表，即表的初始化； 2）Length(L),引用型运算，其结果是表的结点个数，即表长； 3）Get (L,i), 引用型运算，若1iLength(L)，其结果是表中的第i个结点；否则，为一特殊值。 4）Locate (L,x) ，引用型运算，查找L中值为x的结点并返回结点在L中的位置，若有多个x则返回首个；否则返回特殊值表示查找失败。 5）Insert (L,x,i)，加工型运算，在表的第i个位置插入值为x的新结点，要求1iLength(L)+1； 6）Delete (L,i)，加工型运算，删除表的第i个位置的结点，要求1iLength(L)； 3.顺序表：是线性表的顺序存储结构，即按顺序存储方式构造的线性表的存储结构。 4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1in （其中Loc(a1)是顺序表的第一个结点，C每个变量占用的内存单元）。 5.顺序表上的基本运算 （1）插入 Void insert_sqlist(sqlist L,datatype x,int i) /*将X插入到顺序表L的第i-1个位置*/ if(L.last=maxsize) error(“overflow”); /*溢出*/ if(iL.last+1) error (“position error”); /*非法位置*/ for(j=L.last;j=i;j-) L.dataj=L.dataj-1; /*结点依次后移*/ L.datai-1=x; /*置入X*/ L.last=L.last+1 /*修改表长*/ 在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。（2）删除 Void delete_sqlist(sqlist L,int i); /*删除顺序表L中的第i个位置上的结点*/ if (iL.last) error (“position error”)； /*非法位置*/ for(j=i+1;j=L.last;j+) L.dataj-2=L.dataj-1; /*依次前移，注意第一个L.dataj-2存放ai*/ L.last=L.last-1 /*修改表长*/ 在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O(n)。 （3）定位 Void locate_sqlist(sqlist L,datatype X) /*在顺序表中从前往后查找第一个值等于X的结点。若找到则传回该节点的序号；否则传回0*/ i=1; /*i指示顺序表L中结点序号*/ while (iL.last)&(L.datai-1!=x) /*注意：a1在L.datai-1中*/ i+； /*从前往后找*/ if (iL.last) return (i) else return (0) 6. .单链表：只有一个链域的链表称单链表。（单链表表示法的基本思想是用指针表示结点间的逻辑关系） 单链表的一个结点包含两个部分，结点形式如下：数据域 指针域（链域） （1） 建立单链表。时间复杂度为O(n)。 在单链表中加头结点的作用：操作统一；无论链表是否为空，链表的指针不变。 （2） 定位（按值查找） Int locate_lklist(lklist head,datatype x) /*求表head 中第一个值等于X的结点的序号。不存在这种结点时结果为0*/ P=head;j=0; /*置初值*/ While(p-next!=NULL)&(p-data!=x) p=p-next;j+; If p-data=x return(j); Else return(0); (3)删除 时间复杂度为O(n) Void delete_lklist(lklist head;int i) /*删除表head的第i个结点*/ p=find_lklist(head,i-1); /*先找待删结点的直接前驱*/q=p-next; /*q指向待删结点*/ p-next=q-next; /*摘除待删结点*/ free(q); /*释放已摘除结点q*/ Else error(“不存在第i个结点”) /*否则给出相关信息*/ （3） 插入 时间复杂度为O(n) Void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ P=find_lklist (head,i-1); /*先找第i-1个结点*/ if(p=NULL) /*若第i-1个结点不存在*/ error(“不存在第i个位置”) /*退出并给出出错信息*/ else S=malloc(size); s-data=x; /*否则生成新结点*/ S-next=p-next; /*结点*p的链域值传给结点*s的链域*/ p-next=s; /*修改*p的链域*/ 7.循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。 主要优点：从表中任一结点出发都能通过后移做而扫描整个循环链表。 8.空循环链表仅由一个自成循环的头结点表示。 prior data next ，形成的链表中有两条不同方向的链称为双链表。 10.双链表的特点是找结点的前驱和后继都很容易。 11.顺序表和链表的比较 1） 基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。 2） 基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。 第 三 章 栈 和 队 列 1. 栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。 2. 栈的基本运算有： （1） 初始化 Initstack(s),加工型运算，构造一个空栈。 （2） 进栈 Push(S,X)，加工型运算，将元素X插入栈S中，是X成为栈S的栈顶元素。 （3） 退栈 Pop(s),加工型运算， 当栈不为空时，将栈顶元素赋给X，并从栈中删除当前栈顶。 （4） 读栈顶 Top(s),引用型运算，若栈S不空，由X返回栈顶元素；当栈S为空时，结果为一个特殊标志。 （5） 判栈空 Empty(s), 引用型运算，若栈S为空栈，则结果为1，否则结果为0. 3. 顺序栈：栈的顺序存储结构称顺序栈。 4. .当栈满时，做进栈运算必定产生空间溢出，称“上溢”。 当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。 5. 在顺序栈上的基本运算： 1） 置空栈。 Void initstack(seqstack *s) s-top=-1; 2)判栈空。 int stackempty(seqstack *s) return s-top=-1; 3)判栈满。 int stackfull(seqstack *s) return s-top=stacksize-1; 4)进栈。 Void push(seqstack *s,datatype x) if(stackfull(s) error(“stack overflow”); s-data+s-top=x; 5)退栈。 Datatype pop(seqstack *s) if(stackempty(s) error(“stack underflow”); return S-datas-top-; 6)取栈顶元素。 Dtatatype stacktop(seqstack *s) if(stackempty(s) error(“stack underflow”); return S-datas-top; 6. 链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。 7.链栈上的基本运算： 1） 建栈。 Void initstack(linkstack *s) s-top=NULL; 2)判栈空。 Int stackempty (linkstack *s) return s-top=NULL; 3) 进栈。 Void push(linkstack *s,datatype x) stacknode *p=(stacknode *)malloc(sizeof(stacknode); p-data=x; p-next=s-top; s-top=p; 4) 退栈。 Datatype pop(linksatck *s) datatype x; stacknode *p=s-top; if(stackempty(s) error(“stack underflow”); x=p-data; s-top=p-next; free(p); return x; 5) 取栈顶元素。 Datatype stacktop(linkstack *s) if(stackempty(s) error(“stack is empty”); return s-top-data; 8. 队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。 9. 队列的基本运算： 1）初始化 InitQueue(Q),加工型运算，设置一个空队列Q。 2）入队列 EnQueue(Q,X),加工型运算，将X插入到队列Q的队尾。 3）出队 OutQueue(Q,X)，加工型运算，若队列Q不为空，则将队头元素赋给X，并删除队头结点，而该结点的后继成为新的队头结点。 4）判队列空 EmptyQueue(Q),引用型运算，若队列Q为空，则返回的值为1，否则为0。 5）读队头 GetHead(Q,x),引用型运算，Q不空时由参数X返回队头结点的值，否则给一特殊标志。 10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。 11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。 12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize 13.循环队列的边界条件处理：由于无法用front=rear来判断队列的“空”和“满”。 解决的方法有： 1） 另设一个布尔变量以区别队列的空和满； 2） 少用一个元素，在入队前测试rear在循环意义下加1是否等于front； 3） 使用一个记数器记录元素总数 14. 链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。 15. .链队列的基本运算： 1）入队。 Void enqueue(linkqueue *q,datatype x) queuenode *p=(queuenode *)malloc(sizeof(queuenode); p-data=x; p-next=NULL; if(queueempty(q) q-front=q-rear=p; else q-rear-next=p; q-rear=p; 2）出队。 Datatype dequeue(linkqueue *q) datatype x; queuenode *p; if(queueempty(q) error(“queue is underflow”); p=q-front; x=p-data; q-front=p-next; if(q-rear=p) q-rear=NULL; free(p); return x; 第 四 章 串 1. 串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度； 2. 空串：长度为零的串称空串； 空白串：由一个或多个空格组成的串称空白串； 子串：串中任意个连续字符组成的子序列称该串的子串； 主串：包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置； 3. 空串是任意串的子串； 任意串是自身的子串； 串常量在程序中只能引用但不能改变其值； 串变量取值可以改变； 4. 串的基本运算 （1） 赋值 ASSIGN(S,T),加工型运算，将串T的值传给串变量S。 （2） 判等 EQUAL(S,T),引用型运算，若S和T 的值相等则返回值为1，否则返回值为0. （3） 求长 LENGTH(S),引用型运算，求串的长度。 （4） 联接 CONCAT(S,T),引用型运算，运算结果为由S和T联接在一起形成的新串。 （5） 求子串SUBSTR(S,i,j),引用型运算，其结果是串S中从第i个字符开始的，由连续j个字符组成的子串。 （6） 插入 INSERT(S1,i,S2),加工型运算，作用是将串S2整个插入到串S1的第i个字符之后从而产生的一个新串。 （7） 删除 DELETE(S,I,j),加工新运算，作用是从串S中删去从第i个字符开始的长度为j的子串。 （8） 定位INDEX(S,T)，引用型运算，若在串S中存在一个于T相等的子串，则本运算的结果为S中第一个这样的子串中的第一个字符在S中的位置；否则，结果为0. （9） 替换 REPLACE(S,T,R)，加工型运算，结果是在串S中处处同时以串R置换串T的所有出现所得的新串。 5. 串的存储结构： （1） 串的顺序存储 （2） 串的链接存储 第 五 章 多 维 数 组 1. 多维数组：一般用顺序存储的方式表示数组。 2. 数组的逻辑结构是线性结构的推广。 3. 数组的基本运算是： （1） 读：给定一组下标，读取相应的数据元素； （2） 写：给定一组下标，修改相应的数据元素。 4. 矩阵的压缩存储：值相同的多个元素只分配一个存储空间，零元素不分配空间。 （1） 特殊矩阵：值相同的元素或零元素在矩阵中分布有一定的规律的矩阵。 1） 对称矩阵：在一个n阶的方阵A中，元素满足Aij=Aji 1=i,j1,则X的双亲的编号为i/2. 2).若2in,则结点X无左孩子（且无右孩子）；否则，X的左孩子的编号为2i。 3）.若2i+1n,则结点X无右孩子；否则，X的右孩子编号为2i+1。 19.二叉树中某一结点的左子树深度减去右子树的深度，称为该结点的平衡因子。 20.二叉树的存储结构 （1）链式存储结构： 二叉链表结点的结构为：l lchild | data | rchild ； 二叉链表由根指针唯一确定。 （2）顺序存储结构： 把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个一维数组b0n中，b1n存放结点，b0存放结点总数。 各个结点编号间的关系： 1） i=1是根结点；i1则双亲结点是i/2取整； 2） 左孩子是2i, 右孩子是2i+1；（要小于n） 3） i（n/2取整）的结点是叶子； 4） 奇数没有右兄弟，左兄弟是i-1； 5） 偶数没有左兄弟，右兄弟是i+1； 21.二叉树的遍历：就是按某种次序系统的“访问”二叉树上的所有结点，是每个结点恰好被“访问”一次。 22. 二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。23.树的存储结构： （1）孩子链表表示法是树的一种链式存储结构。 1）孩子链表表示法的思想是：树上的一个结点的内容以及指向该结点所有的孩子的指针存储在一起以便于运算的实现。 2）一个孩子链表是一个带头结点的单链表，单链表的头结点含有两个域：数据域和指针域。（以图1为例） 数据域指针域 孩子域 指针域（2）孩子兄弟链表表示法： （3）.双亲表示法： 24.森林通常定义为树的集合。 25. 树、森林与二叉树的转换 （1）树与二叉树的转换： 1）所有兄弟间连线； 2）保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空 （2）森林与二叉树的转换： 1）将所有树转换成二叉树； 2）将所有树根连线。 26. 树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树。 27.从树中一个结点到另一个结点之间的分支，构成这两个节点之间的路径；路径上的分支的数目称为路径的长度。 28.结点上赋一个有实际意义的实数，称此实数为根结点的权。 29.从根结点到根结点之间的路径长度于根结点上权的积称为结点的带权路径长度。 30.树中所有叶子结点的带权路径长度之和记做树的带权路径长度。 31.n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树称为哈夫曼树（HuFFman），又叫最优二叉树。 32.对字符集进行编码时，字符集中任一个编码都不是其他字符的编码的前缀，称为前缀码。 第 七 章 图 1. 图：图G由两个集合V和E组成，记作G=(V,E)，其中V是顶点的有穷非空集合，E是边的集合，而边是V中顶点的偶对。 2. 若定点的偶对是有序的，则称此图为有向图，有序偶对用括起来；若顶点偶对是无序的，则称此图为无向图，无序偶对用（）括起来。 3. 端点和邻接点：图中若存在有一条边（Vi,Vj），则称Vi,Vj为此边的两个端点，并称他们为邻接点。 4. 顶点的度，入度，出度：无向图中顶点的度定义为无向图中以该顶点为一个端点的边的数目；有向图顶点的出度是以该顶点为起始点的边的数目；入度是以该顶点为终点的边的数目。 5. 顶点n与边数e的关系：无向图的边数e介于0n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0n(n-1)之间，有n(n-1)条边的称有向完全图； 6. 子图：设G,H是图，若V(H)包含于V(G)，E(H)包含于E(G)，则称H是G的子图，G是H的母图；如果H是G的子图且V(H)= V(G)，则称H为G的支撑子图。 7. 可及和连通分量：从顶点Vi到顶点Vj若存在路径，则称Vi和Vj可及；在无向图的顶点集中任意两个顶点都可及，则称此无向图为连通图；极大连通子图称连通分量。 8. 在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量。 9. 权和网：为边赋一个具有某种意义的数值，成这个数值为该边的权；带权的图称为网。 10. 一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图。 11. 图的存储结构：（P109） （1） 邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。 无向图是对称矩阵；有向图行是出度，列是入度。 （2） 邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstarc,并顺序存储在一个向量中；vertex保存顶点信息，firstarc保存邻接表头指针。 12. 邻接矩阵表示法与邻接表表示法的比较： 1） 邻接矩阵是唯一的，邻接表不唯一； 2） 存储稀疏图用邻接表，存储稠密图用邻接矩阵； 3） 求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便； 4） 判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)； 5） 求边数e，邻接矩阵耗时为O(n2)，与e无关，邻接表的耗时为O(e+n)； 13.图的遍历： （1）.图的深度优先搜索：假定图中某个顶点Vi为出发点，首先访问出发点，然后任选一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索，直到图中所有结点都被访问过。 （2）.图的广度优先搜索：从图中某个顶点Vi出发，在访问了Vi之后依次访问Vi的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。 14.生成树中各边的权值和称为该树的树值。 15.权值最小的生成树称为图的最小生成树。 16.求最小生成树的方法：（书P118） （1）.普里姆（PRIM）算法： （2）克鲁斯卡尔（kruskal）算法： 17.在有向图中，顶点表示活动，有向边表示活动之间的先后关系，称这种关系为A.O.V网。 18.拓扑序列：A.O.V网中的所有顶点排成一个顺序序列，使每个活动的所有前驱活动都排在该活动的前面。 19.构造A.O.V网拓扑序列的过程称为拓扑排序。 第 八 章 排 序 1. 文件：由一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字； 2. 排序是将文件按关键字的递增（减）顺序排列； 3. 排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序； 4. 在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内排序，反之称外排序； 5. 内排序的方法主要有：插入排序，交换排序，选择排序，归并排序等四类。 6. 常用的插入排序有：直接插入排序，折半插入排序，表插入排序和希尔排序。 7. 直接插入排序：依次将每个记录插入到一个有序的子序列中去。 算法中引入监视哨R0的作用是： 1） 保存Ri的副本； 2） 简化边界条件，防止循环下标越界。 关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2； 算法的最好时间是O(n)；最坏时间是O(n2)；平均时间是O(n2)；是一种就地的稳定的排序； 8. 交换排序：将键值较大的记录向序列尾部移动，键值较小的记录向序列的前部移动。 （1）.冒泡排序：实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。 关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2； 算法的最好时间是O(n)；最坏时间是O(n2)；平均时间是O(n2)；是一种就地的稳定的排序； （2）.快速排序： 实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。 关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2； 算法的最好时间是O(nlog2n)；最坏时间是O(n2)；平均时间是O(nlog2n)；辅助空间为O(log2n)；是一种不稳定排序； 9.选择排序： （1）直接选择排序 实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。 关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)； 算法的最好时间是O(n2)；最坏时间是O(n2)；平均时间是O(n2)；是一种就地的不稳定的排序； （2） 堆排序 实现过程：把序列按层次填入完全二叉树，调整位