《2022年数据结构主要知识点广东湛科院》由会员分享，可在线阅读，更多相关《2022年数据结构主要知识点广东湛科院（8页珍藏版）》请在金锄头文库上搜索。
1、学习必备欢迎下载数据结构主要知识点第一部分：1、数据 是客观事物的符号表示，在计算机科学中是指所有能输入到算机中并被计算机所处理的符号的总称。2、数据对象 是性质相同的数据元素的集合。3、数据结构 是相互间存在一种或多种特定关系的数据元素的集合。4、数据结构的四种基本形式是：集合、线性结构、树形结构和图状结构或网状结构。5、数据类型 是一个值的集合和定义在这个值集上的一组操作的总称。6、顺序存储结构的特点是：1）占用一块地址连续的内存单元；2）用存储位置的物理相邻表示数据间的逻辑相邻；3）可以实现随机存取。7、链式存储结构的特点是：1）动态分配存储空间；2）用指针表示数据间的逻辑关系；3）不能
2、实现随机存取。8、算法 是对特定问题求解步骤的一种描述、是指令的有限序列。9、算法满足以下5 个性质 ：1）输入：一个算法可以有0 个或多个输入；2）输出：一个算法要有一个或多个输出；3）有穷性：一个算法必须在执行有穷步骤后结束，每一步骤也必须在有限时间内完成；4）确定性：算法中的每一步骤都有明确的含义，没有二义性；5）可行性：算法中描述的每一个操作，都可以通过已经实现的基本运算，执行有限次后完成。10、算法的四项基本要求是：1）正确性、可读性、健壮性和效率与低存储需量。2）评价算法 时间效率 的指标是时间复杂度。3）时间复杂度是用算法中基本操作的重复执行次数与问题规模之间的函数关系，来描述算
3、法的时间效率。但由于难以求得基本操作的重复执行次数与问题规模之间的精确的解析的函数关系，所以算法时间复杂度通常用问题规模（n）的某类函数的阶来表示。评价算法 空间效率 的指标是空间复杂度。11、五种常见的算法时间复杂度是：常量阶、线性阶、对数阶、多项式阶和指数阶。12、描述以下三个概念的区别：头指针、头结点、第一个元素结点。第一个元素结点是指链表中存储线性表中第一个数据元素的结点。为操作方便， 通常在链表的第一个结点之前附设一个结点，称为头结点， 该结点的数据域不存储线性表的数据元素， 其作用是为了对链表进行操作时，可以对空表、 非空表的情况以及对第一个元素结点进行同一处理。头指针是指向链表中
4、第一个结点（或为头结点或为第一个元素结点）的指针。若链表中附设头结点，则不管线性表是否为空，头指针均不为空，若链表中不设头结点， 则空链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页学习必备欢迎下载13、在顺序表中插入或删除一个元素，需要平均移动表长一半的元素，具体移动元素的个数与表长和该元素在表中的位置有关。在单链表中， 除第一个数据元素结点外，任一结点的存储位置由其直接前驱结点的指针域的值指示。在单链表中 设
5、置头结点的作用是插入和删除第一个数据元素结点时不必进行特殊处理。第二部分：1、已知 L 是无表头结点的单链表，且P结点即不是第一个结点也不是最后一个结点，试写出实现下列操作的语句序列：1)在结点后插入结点S-next = P-next;P-next=S; 2) 在 结 前 后 插 入 结 点Q=p;P=L;while(P-next!=Q)P=P-next; S-next = P-next;P-next=S; 3)在表首插入S结点S-next=L;L-S; 4)在表尾插入S结点P=L;while(P-next!=NULL) P=P-next; S-next = P-next;P-next=S;
6、2、已知 L 是带表头结点的单链表，且P结点即不是第一个结点也不是最后一个结点，试写出实现下列操作的语句序列：1）删除 P 结点直接后继结点Q=p-next;P-next=P-next-next;free(Q); 2）删除 P 结点直接前驱结点Q=p;P=L;while(P-next-next!=Q) P=P-next; Q=p-next; P-next=P-next-next;free(Q); 3）删除 P 结点Q=P;P=L; while(P-next!=Q) P=P-next; P-next=P-next-next;free(Q); 4）删除第一个数据元素结点P=L;Q=P-next;
7、P-next=P-next-next;free(Q); 5）删除最后一个数据元素结点while(P-next-next!=NULL) P=P-next; Q=p-next;P-next=P-next-next;free(Q); 第三部份：1、顺序栈的存储结构定义#define STACK_INIT_SIZE 100 typedef struct / 这里 SElemType 的类型根据具体情况，由程序员自行定义SElemType *base;/栈基址SElemType *top;/ 栈顶指针int stacksize;/当前已经分配的存储单元，以元素为单位 SqStack;/ 顺序栈数据类型2
8、、有关顺序栈的基本操作1）构造一个空栈int InitStack(SqStack &S) S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) return 0;/ 内存分配失败，返回0 S.top=S.base; S.stacksize=STACK_INIT_SIZE;/ return 1; /InitStack 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页学习必备欢迎下载2）元素进栈（不考虑栈满）int Push(SqStack &
9、S,SElemType e) *S.top=e;S.top+; return 1; /Push 3）元素出栈int Pop(SqStack &S,SElemType &e) if(S.top=S.base) return 0;/ 若栈为空，出栈失败，返回0 S.top-;e= *S.top;/ 用引用参数e 保存栈顶元素的值return 1;/ 出栈成功，返回1 /Pop 2、 （ 1）链栈结点类型的定义typedef struct Lnode/* 链栈结点类型*/ ElemType data;/数据域， ElemType 的类型根据具体情况，由程序员自行定义struct LNode *nex
10、t;/ 指针域LNode,*Link; （2）链栈的存储结构定义typedef struct Link head;/ 栈顶指针int len;/ 链栈的当前长度LinkStack;/* 链栈类型 */ （3）有关链栈的基本操作1）创建带头结点的空链栈int InitLinkStack(LinkStack &S)/*创建带头结点的空链栈*/ S.head=(LNode*)malloc(sizeof(LNode); /*创建头结点 */ if(!S.head)return 0;/ 内存分配失败S.head-next=NULL; S.len=0; return 1;/空链栈创建成功 2）创建新结点i
11、nt NewNode(Link &p,ElemType e) p=(LNode*)malloc(sizeof(LNode); /*创建新结点，引用变量p 保存新结点的地址*/ p-data=e;/* 结构变量整体赋值*/ p-next=NULL; return 1; 3）元素进栈int Push(LinkStack &S,ElemType e) int r; Link p; r=NewNode(p,e);/*p指向新结点 */ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页学习必备欢迎下载if(!r)return 0; p-ne
12、xt=S.head-next;/* 新结点插在头结点之后*/ S.head-next=p; S.len+; return 1; 4）元素出栈int Pop(LinkStack &S,ElemType &e) Link p; if(S.len=0)return 0;/ 若栈为空，则出栈失败p=S.head-next;/* 保存栈顶结点的指针*/ e=p-data;/* 用引用参数e，保存栈顶结点数据域的值*/ S.head-next=p-next;/* 修改栈顶指针，S.head-next 就是栈顶指针 */ S.len-; free(p);/ 释放栈顶元素所占用的内存return 1;/出栈成
13、功 3、循环队列的存储结构定义#define MAXQSIZE 100 typedef struct QElemType *base;/ QElemType 的类型根据具体情况，由程序员自行定义int rear;/队尾指针int front;/ 对头指针SqQueue;/ 循环队列数据类型有关循环队列的基本操作1）创建一个空的循环队列int initqueue(SqQueue &Q) Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType); if(!Q.base) return 0;/ 内存分配失败Q.front=Q.rear=0; retur
14、n 1;/ 队列创建成功/initqueue 2）新元素入队列I nt EnQueue(SeQueue &Q,QelemType e) if(Q.rear+1)%MAXQSIZE = Q.front)return 0;/队列满Q.baseQ.rear=e;/ 新元素插在队尾Q.rear = (Q.rear+1)% MAXQSIZE;/队尾指针加1 Return 1;/入队列成功 3）删除队头元素int Delqueue(SqQueue &Q,QElemType &x) if(Q.front=Q.rear) return 0;/队列为空x=Q.baseQ.front;/ 用引用参数x 保存队头元
15、素的值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页学习必备欢迎下载Q.front=(Q.front+1)%MAXQSIZE;/队头指针加1 return 1;/ 删除成功/Delqueue （1）链队列结点类型typedef struct Lnode/* 链队列结点类型*/ ElemType data;/ ElemType 的类型根据具体情况，由程序员自行定义struct LNode *next; LNode,*Link; （2）链队列类型typedef struct Link front,rear;/ 头、尾指针int le
16、n;/ 队列的当前长度LinkQueue;/* 链队列类型 */ 4、有关链队列的基本操作1）创建带头结点的空链队列int InitLinkQueue(LinkQueue &Q)/*创建带头结点的空链队列*/ Q.front=(LNode*)malloc(sizeof(LNode); /*创建头结点 */ if(!Q.front)return 0;/ 头结点创建失败Q.rear=Q.front;/ 头、尾指针都指向头结点Q.front-next=NULL; Q.len=0; return 1; 2）新元素插入到队尾int EnterQueue(LinkQueue &Q,ElemType e)
17、int r; Link p; r=NewNode(p,e);/*p指向新结点 */ if(!r)return 0;/ 创建新结点失败Q.rear-next=p;/* 新结点插在队尾结点之后*/ Q.rear=p;/* 尾指针等于p*/ Q.len+; return 1;/新元素插入成功 3）删除队头元素int DelQueue(LinkQueue &Q,ElemType &e) Link p; if(Q.len=0)return 0;/ 队列为空p=Q.front-next;/* 保存队头结点的指针*/ e=p-data;/* 用引用参数e保存队头结点数据域的值*/ Q.front-next=
18、p-next;/* 修改队头指针，Q.front-next 就是队头指针*/ Q.len-; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页学习必备欢迎下载if(Q.rear=p)Q.rear=Q.front;/*若队列中只有一个结点，队头也是队尾*/ free(p);/* 删除队尾，需要对队尾指针重新赋值*/ return 1; 第四部分：二叉树是每个结点上最多有左右两个分支的有序二叉树。在二叉树的第k 层上至多有2k-1个结点。深度为 k 的二叉树至多有2k - 1 个结点。具有 n 个结点的完全二叉树的深度为（log2n）
19、向下取整后再加1。若一棵深度为k 的二叉树，共有2k - 1 个结点，则此二叉树就是满二叉树，满二叉树的叶子结点都在最底层。设 T1、T2 都是深度为d 的二叉树，其中T1 还是满二叉树。对T1 和 T2 中的所有结点都按从上到下、从左到右的次序从1 起连续编号，若在T1、T2 中每一个编号相同的结点，在二叉树中的位置也相同，则称T2 是完全二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。完全二叉树的叶子结点都在最底层和倒数第二层。二叉树的顺序存储是用一组地址连续的存储单元，存储二叉树的数据元素。此时， 存储单元的顺序号 （下标），与结点在二叉树中的位置一一对应。顺序存储结构只
20、适用于完全二叉树，对非完全二叉树，顺序存储将造成存储空间的浪费。遍历二叉树就是如何按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。三种遍历二叉树的方案分别是：先序遍历二叉树、中序遍历二叉树和后序遍历二叉树。对给定的一棵二叉树能写出三种遍历的序列，对给定的两种 （先序和中序） 遍历序列能画出相应的二叉树。哈夫曼树是一类带权路径长度最短的树。若要设计长度不等的编码，必须使任一字符的编码都不是另一字符编码的前缀，这种编码称为前缀编码。能根据给定的n 个带权叶子结点，画出哈夫曼树。能根据哈夫曼树写出每个叶子结点的哈夫曼编码。能根据给定的数据元素序列，画出其所对应的二叉排序
21、树。图是一种数据结构，图中的数据元素通常用顶点来表示，而数据元素之间的关系用边或弧来表示。在无向图中，所有顶点的度数之和等于，图中边数的2 倍。在有向图中，所有顶点的入度之和等于所有顶点的出度之和的1 倍。一个有 n 个顶点的无向图最多有n(n-1)/2 条边。具有 4 个顶点的无向完全图有6条边。具有 6 个顶点的无向图至少应有5 条边，才能确保是一个连通图。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8 页学习必备欢迎下载在一个具有n 个顶点的无向图中，要连通全部顶点者少需要n-1 条边。对于一个具有n 个顶点图（无向图或有向图
22、），其邻接矩阵是一个nn 的方阵。对于一个具有n 个顶点和e 条边的无向图，其邻接表表头向量的大小是n；邻接表中结点的总个数是2e。对于无向图和有向图能分别求出：1）每个顶点的度（对有向图还要区分入度和出度）；2）给出一条两个指定顶点间的简单路径；3）给出图的邻接矩阵和邻接表。4）给出从某指定顶点出发，采用深度优先搜索算法进行遍历所得到的搜索序列及其生成树。5）给出从某指定顶点出发，采用广度优先搜索算法进行遍历所得到的搜索序列及其生成树。6）提示：画图的邻接矩阵和邻接表时，要先确定一个顶点的序列。对于给定的有向无环图，能写出其两种拓扑有序序列。对于无向带权图，能写出其最小生成树。查找表是由同一
23、类型的数据元素（记录）构成的集合。关键字是数据元素（或记录）中的某个数据项，用它可以标识（识别）一个数据元素（或记录） 。查找是根据给定的关键字的值，在查找表中确定一个其关键字值等于给定值的数据元素（或记录） 。在顺序查找中“监视哨”的作用是： 在查找中无需控制下标是否越界，因而可以减少大约一半的运算量。顺序查找的平均成功查找长度是表长的一半。折半查找的平均查找长度可近似地表示为log2(n)。 但折半查找只能用于按关键字有序的查找表。分块查找的基本思想是把查找表分成若干快，在每一块中数据的存放次序是任意的，但块与块之间必须有序。 另外还要建立一个索引表，把每一块中的最大关键字值和每一块的块基
24、址存入索引表，索引表按关键字值有序。查找时，首先查找索引表，以确定待查数据元素应在哪一块中，然后再到相应的块中进行顺序查找。散列法（又称哈希法）的基本思想是：以记录中关键字的值为自变量，通过确定的函数H（哈希）函数进行计算，求出对应的函数值，把这个函数值最为存储地址，将该纪录存放在这个位置上，查找时仍按这个确定的函数H 进行计算，获得的将是待查关键字所在记录的地址。在理想的情况下，经过一次简单的计算便可得到存储或查找的地址。但由于 H（哈希）函数是一个从关键字集合到地址集合的压缩映像，因而冲突是不可避免的。所谓冲突是指两个或多个不同的关键字值，对应着一个相同的H（哈希）函数值的情况。如上所叙，
25、散列法归结为如下两个方面：对于给定的一组关键字构造一个计算简单且散列均匀的H（哈希）函数；拟定一个较好的解决冲突的方法。散列函数的构造方法有如下几种：1）直接定址法；2）数字分析法；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页学习必备欢迎下载3）平方取中法：4）折叠法；5）除留余数法。处理冲突的主要方法有：1）开放地址法a)线性探查法b)平方探查法c)双散列函数探查法2)链接法a)静态链接法b)动态链接法散列法的平均查找长度是装填因子的函数，不直接依赖于表长。装填因子（ a）= 表中已有的记录数/表的长度。内部排序：指的是在整
26、个排序过程中，待排记录都是存储在计算机的内存储器中的排序过程。外部排序： 指的是待排记录的数据量很大，以至于内存不能一次容纳全部记录，在排序过程中尚需利用外存的排序过程。评价一个排序算法优劣的标准主要有两条：算法的时间复杂度和空间复杂度。在排序过程忠需要进行如下两种基本操作：比较关键字和移动记录。若在排序前后具有相同键值的纪录的相对位置不变，则称此排序方法是稳定的，否则称为是不稳定的。几种排序方法的比较排序方法时间复杂度空间复杂度稳定性直接插入排序O(n2) O(1) 稳定折半插入排序O(n2) O(1) 稳定2-路插入排序O(n) 稳定希尔排序O(nlog2n)- O(n2) O(1) 不稳定简单选择排序O(n2) O(1) 不稳定堆排序O(nlog2n) O(1) 不稳定冒泡排序O(n2) O(1) 稳定快速排序O(nlog2n) O(1) 不稳定2-路归并排序O(nlog2n) O(n) 稳定基数排序O(d(n+r) O(2r) 稳定精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页
