文档介绍：该【数据结构基本知识点】是由【莫比乌斯】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【数据结构基本知识点】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第一章
1、什么是数据结构
①数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
②数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
③4类基本结构:⑴集合;⑵线性(一个前驱,一个后继)结构;⑶树形结构;⑷图状结构或网状结构。
2、数据结构的二元组表示:Data_Structure=(D,S)//D是数据元素的有限集,S是D上关系的有限集。
3、算法的5大特性:⑴有穷性;
4、衡量算法的标准:时间复杂度和空间复杂度
5、数据的逻辑结构分四类
6、数据结构写出逻辑结构,反之。
第二章
0、线性表的基本概念。
1、线性表的顺序存储的基本操作:Insert,EIs=n/=(n-1)/2
2、线性表的顺序存储的特点:连续地址,随机查找。
3、线性表的链式存储的特点:地址不保证连续,顺序查找。
(1)重点1:结构类型P28
TypedefstructLNode{
ElemTypedata;
StructLNode*next;
}LNode,*LinkList;
(2)重点2:基本方法
StatusGetElem_L(LinkListL,inti,ElemType&e);
StatusListInsert_L(LinkList&L,inti,ElemTypee);
StatusListDelete_L(LinkList&L,inti,ElemType&e);
voidCreateList_L(LinkList&L,intn);
voidPrint(LinkListL)
{LinkListp=L->next;(有头结点)
if(!p)printf(“thislinkisempty!\n”);
else{printf(“%d,”,p->data);
while(p->next)
{p=p->next;printf(“%d,”,p->data);}
printf(“\n”);
}
}
voidCountNodes(LinkListL,int&nd)
{nd=0;//
LinkListp=L->next;(有头结点)
if(!p)printf(“thislinkisempty!\n”);
else{nd++;//
while(p->next)
{p=p->next;nd++;}//
}
}
voidCountAve(LinkListL,int&av)
{intn=0,s=0//
av=0;
LinkListp=L->next;(有头结点)
if(!p)printf(“thislinkisempty!\n”);
else{s=s+p->data;n++;//
while(p->next)
{p=p->next;s=s+p->data;n++;}//
av=s/n;
}
returnav;//
}
voidPrintMax(LinkListL,)
{intmax;
LinkListp=L->next;(有头结点)
if(!p)printf(“thislinkisempty!\n”);
else{max=p->data;
while(p->next)
{p=p->next;if(p->data>max)max=p->data;}//
printf(“max=%d\n”,max);
}
}
voidDeletaMaxNode(LinkListL,)
{intmax;
LinkListq,t;//q---记录p的前驱结点指针,t-----保存最大结点的前驱指针。
LinkListp=L->next;(有头结点)
q=L;//
if(!p)printf(“thislinkisempty!\n”);
else{max=p->data;t=q;//
while(p->next)
{q=p;p=p->next;//
if(p->data>max){max=p->data;t=q;}//
}
q=t->next;t->next=q->next;free(q);
}
}
(3)循环链表的特点:首尾特点
(4)链表为空的条件:分有头链表与无头链表。
(5)分清头结点,开始结点、尾结点。
第三章栈和队列
1、栈和队列是端点受限操作的线性表。
2、栈的定义及特点:FILO
3、Push(&s,e)Pop(&s,&e)基本操作过程。
4、判定通过栈操作的序列正确否或可能性。
5、栈空或栈满的条件。
6、队列特性:FIFO
7、循环队列:为空的条件,为满的条件。
8、EnQueue(&Q,e)的操作
9、DeQueue(&Q,&e)的操作
第四章串
1、串的定义与表示
2、空串与空白串的区别
3、串的基本操作
4、什么是模式匹配
5、intIndex(stringS,stringT,intpos);作用P79
6、统计子串的个数
数组与广义表
数组的定义
数组元素存储方式:按行存储或按列存储(不同语言)
数组元素地址的计算(重点会计算)
数组A[a....m][b.....n],行数M=m-a+1,列数N=n-b+1;每个元素L个字节。
按行:loc(Aij)=loc(Aab)+((i-a)*N+(j-b))*L;
按列:loc(Aij)=loc(Aab)+((j-b)*M+(i-a))*L;
广义表的定义。
广义表的表示与存储
广义表的长度与深度
GetHead(T),GetTail(T)的作用。
树与二叉树
树的定义与基本术语
二叉树的定义与特点
二叉树的5种基本形态
二叉树的性质(1)(2)(3)(4)(5)
满二叉树与完全二叉树的异同
完全二叉树的相关计算
n个结点的完全二叉树,h=|log2n|+1,n0=|(n+1)/2|;n2=n0-1;n1=(n+1)%2
二叉树的存储结构:顺序结构(完全二叉树的顺序)与链式结构。
二叉树的三种遍历方式
计算结点数,叶子数
线索二叉树中增加2个标志域LTag,RTag的作用
会画线索树
树与二叉树的相互转换
森林与二叉树的相互转换
树的先根遍历相当于二叉树的先根遍历,后根遍历相当于二叉树中根。
Huffman树的定义
Huffman树的建立、编码形成法则、WPL的计算。
图
图的定义与术语P159
图的表示与存储
完全图的定义
邻接矩阵与邻接链表的形成(重点)
会写图的遍历结果:DFS(栈,碰头回)BFS(队列,齐步走)
(利用邻接矩阵或邻接表,进行遍历操作)
连通分量与连通图
最小生成树的确定(Prim,Kruskal,重点)
会写拓扑排序的序列(队列)
关键路径的确立
最短路径。
单源到其它各点的最短路径。
查找
顺序表查找中,哨兵的谁,有什么效果ASL=(n+1)/2
有序表查找中,最多查找比较的次数=|log2n|+1
索引表查找结合有序分块顺序进行查找。ASL=log2(n/s+1)+s/2
二叉排序树的定义(递归)
创建二叉排序树、如何删除结点。
平衡二叉树的定义、平衡因子,如何确立插入后不平衡,如何调整。
RR/LL/LR/RL
哈希函数,哈希表
H(key1)=H(key2)=c;称为冲突,key1,key2互为同义词。
哈希函数的目标是建立散布均匀的分布。
处理冲突的方法:开放地址法,进行线性探测。
内部排序
1、直接插入法。O(n2),最好有序情况下为O(n)。(会写分步过程)
2、折半插入法。O(n2).
3、希尔排序法。最后一步长度必须为1.。O(n3/2)。(会写分步过程)
4、快速排序法。O(nlogn),最差O(n2)。会画过程,知道如何判定过程多少。
5、冒泡排序法、选择排序法。O(n2)
6、归并排序法。O(nlogn),最差O(n2)
P283
初始关键字[49][38][65][97][76][13][27]
一趟后[3849][6597][1376][27]
二趟后[38496597][132776]
三趟后[13273849657697]
数据结构重点(60分)~,(),图的遍历,最小生成树,邻接表和邻接矩阵,,建散列表(除留取余法),十一,,七,九章