资源描述：
《C语言版数据结构知识点汇总.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、引言用计算机解决问题一般步骤： 一般来说，用计算机解决一个具体问题时，大致经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整知道的到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。三种经典的数学模型图书书目自动检索系统--线性关系博弈问题--树城市道路问题--图数据结构（datastructure） 简单的解释：相互之间存在一种或多种特定关系的数据元素的集合。数据间的联系有逻辑关系、存储联系
2、，通常的数据结构指的是逻辑结构。前面提到的三种经典的数学模型体现了数据结构的基本结构，数据结构通常有如下四种关系：（1）集合结构（2）线性结构（3）树形结构（4）图状结构☆线性表（一）N个数据元素的有限序列存储结构：顺序存储结构、链式存储结构（1）（2）（3）（4）（5）（6）（7）（8）12131522343843 当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以"腾"出某个合适的位置放置新元素。删除元素呢？☆线性表（二）链式存储插入新元素的时候只需要改变指针所指向的地址。☆二维数组与线性表如果某一线性表，
3、它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用二维数组。二维数组的一个形象比喻--多个纵队形成的方块m*n☆数组地址计算问题题目描述：已知N*(N+1)/2个数据，按行的顺序存入数组b[1],b[2],...中。其中第一个下标表示行，第二个下标表示列。若aij(i>=j,j=1,2,...,,n)存于b[k]中，问：k,i,j之间的关系如何表示？给定k值，写出能决定相应i,j的算法。答案①K=i*(i-1)/2+j②Read(k);Fori:=1tokdoforj:=1toidoifk=(trunc(I*(I-
4、1)/2)+j)thenwriteln(k,'对应的i,j为：',i,',',j)☆栈特殊的线性表操作特点：后进先出（LastInFirstOut）栈顶--表尾栈底--表头空栈☆栈（考题分析）（1998）栈S初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是______D(A){5,4,3,2,1}(B){2,1}(C){2,3}(D){3,4}☆队列先进先出允许插入的一端称为队尾(rear)，
5、允许删除的一端称为队头(front)。☆循环队列头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。☆树根、叶子、子树结点的度：结点拥有的子树数二叉树☆二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第i层至多有2i-1个结点（i>=1）深度为K的二叉树最多有2k-1个结点（K>=1）☆二叉树的遍历先（根）序遍历ABDFGCEH中（根）序遍历BFDGACHE后（根）序遍历FGDBHECA☆例题分析给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。☆图☆
6、图的存储结构邻接矩阵有向图、无向图、带权图的邻接矩阵☆排序冒泡排序选择排序快速排序希尔排序一、插入排序(InsertionSort)1.基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2.排序过程： 【示例】：[初始关键字][49]38659776132749J=2(38)[3849]659776132749J=3(65)[384965]9776132749J=4(97)[38496597]76132749J=5(76)[3849657697]13274
7、9J=6(13)[133849657697]2749J=7(27)[13273849657697]49J=8(49)[1327384949657697]二、选择排序1.基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2.排序过程：【示例】：初始关键字[4938659776132749]第一趟排序后13［38659776492749]第二趟排序后1327［659776493849]第三趟排序后132738[9776496549]第四趟排序后1327384
8、9[49976576]第五趟排序后1327384949[979776]第六趟排序后132738494976[7697]第七趟排序后13273849497676[97]最后排序结果1327384949767697三、冒泡排序(Bubbl
