文档介绍：该【数据结构与算法设计知识点 】是由【莫比乌斯】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【数据结构与算法设计知识点 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构与算法设计知识点
试题类型:
本课程为考试科目(闭卷笔试),试题类型包括:概念填空题(10%),是非判断题(10%),单项选择题(40%),算法填空题(10%),算法应用题(20%),算法设计题(10%)。
第一章绪论
重点内容及要求:
了解与数据结构相关的概念(集合、数据、数据元素、数据项、关键字、元素之间的关系等)。
数据:所有能被输入到计算机中,且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。
数据元素:是数据(集合)中的一个“个体”,数据结构中的基本单位,在计算机程序中通常作为一个整体来考虑和处理。
数据项:是数据结构中讨论的最小单位,数据元素可以是一个或多个数据项的组合
关键码:也叫关键字(Key),是数据元素中能起标识作用的数据项。
其中能起到唯一标识作用的关键码称为主关键码(简称主码);否则称为次关键码。通常,一个数据元素只有一个主码,但可以有多个次码。
关系:指一个数据集合中数据元素之间的某种相关性。
数据结构:带“结构”的数据元素的集合。这里的结构指元素之间存在的关系。
数据类型:是一个值的集合和定义在此集合上的一组操作的总称。
掌握数据结构的基本概念、数据的逻辑结构(四种)和物理结构(数据元素的表示与关系的表示、两类存储结构:顺序存储结构和链式存储结构)。
数据结构包括逻辑结构和物理结构两个层次。
数据的逻辑结构:是对数据元素之间存在的逻辑关系的一种抽象的描述,可以用一个数据元素的集合和定义在此集合上的若干关系来表示
逻辑结构有四种:线性结构、树形结构、图状结构、集合结构
数据的物理结构:是其逻辑结构在计算机中的表示或实现,因此又称其为存储结构。
存储结构:顺序存储结构和链式存储结构
顺序存储结构:利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系;
链式存储结构:除数据元素本身外,采用附加的“指针”表示数据元素之间的逻辑关系。
了解算法分析的基本方法,掌握算法时间复杂度相关的概念。
算法:是为了解决某类问题而规定的一个有限长的操作序列
或处理问题的策略
一个算法必须满足以下五个重要特性:
设计算法时,通常还应考虑满足以下目标:
,,
如何估算算法的时间复杂度?
算法=控制结构+原操作
(固有数据类型的操作)
算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间与原操作执行次数之和成正比
算法的空间复杂度定义为:
S(n)=O(g(n))
表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。
算法的存储量包括:
第二章线性表
重点内容及要求:
掌握线性表的顺序存储结构,了解顺序表的存储特点(数据元素在内存中依次顺序存储),优点:可随机存取访问;缺点:结点的插入/删除操作不方便。
线性表:是一种最简单的数据结构,也是构造其它各类复杂数据结构的基础。一个数据元素的有序(次序)集。它有顺序和链式两种存储表示方法。
线性表必有:
“第一元素”
“最后元素”
,均有唯一的后继;
,均有唯一的前驱
定义如下:
typedefintElemType;
typedefstruct{
ElemType*elem;//存储数据元素的一维数组;
intlength;//线性表当前长度;
intlistsize;//当前分配数组容量;
}SqList;
VoidInitSqList(SqListA,intmaxsize)//初始化线性表
{
=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!)
{
exit(0);
}
=0;
=LIST_INIT_SIZE;
return;
}
了解线性表的链式存储结构,重点掌握带头结点的单链表的基本操作(结点的插入与删除运算),了解单向循环链表和双向链表存储表示方法。
单链表:用一组地址任意的存储单元存放线性表中的数据元素。
以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点
(表示数据元素或数据元素的映象)
单链表是一种顺序存取的结构,求以此为存储表示的线性表长度,可设置一个计数器
3、了解有序线性表的特点(顺序有序表、有序链表)。
有序线性表:线性表中的数据元素相互之间可以比较,并且数据元素在线性表中
依值非递减或非递增有序排列,即ai≥ai-1或ai≤ai-1(i=2,3,…,n),则称该线性表为有序表(OrderedList)
4、学会对线性表设计相关的算法进行相应的处理。
第三章排序
重点内容及要求:
1、掌握对顺序表数据记录进行排序的基本思路和常规操作(比较、移动),了解排序算法的稳定性问题。
2、掌握简单选择排序、直接插入排序、冒泡排序算法,了解各种排序算法的特点及时间复杂度。
排序:将一组“无序”的记录序列按某一关键字调整为“有序”的记录序列。
若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;反之则为外部排序。
选择排序:从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度
基本代码如下
for(i=0;i<n-1;i++)/*外循环控制趟数,n个数选n-1趟*/
{
k=i;/*假设当前趟的第一个数为最值,记在k中*/
for(j=i+1;j<n;j++)/*从下一个数到最后一个数之间找最值*/
if(a[k]<a[j])/*若其后有比最值更大的*/
k=j;/*则将其下标记在k中*/
if(k!=i)/*若k不为最初的i值,说明在其后找到比其更大的数*/
{
t=a[k];a[k]=a[i];a[i]=t;}/*则交换最值和当前序列的第一个数*/
}
插入排序:插入排序是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
。
代码如下:voidInsertSort(SqList&L)//对顺序表L作插入排序
{
for(i=2;i<=;++i)
if([i].key<[i-1].key)
{
[0]=[i];//复制为哨兵
for(j=i-1;[0].key<[j].key;--j)
[j+1]=[j];//记录后移
[j+1]=[0];//插入到正确位置
}
}
冒泡排序:泡排序是一种最直观的排序方法,在排序过程中,将相邻的记录的关键字进行比较,若前面记录的关键字大于后面记录的关键字,则将它们交换,否则不交换。或者反过来,使较大关键字的记录后移,像水中的气泡一样,较小的记录向前冒出,较大的记录
像石头沉入后部。故称此方法为冒泡排序法
代码如下:
voidBubbleSort(SqList&L)
{RcdTypeW;
i=;
while(i>1){//i>1表明上一趟曾进行过记录的交换
lastExchangeIndex=1;
for(j=1;j<i;j++){
if([j+1].key<[j].key){
W=[j];[j]=[j+1];[j+1]=W;//互换记录
lastExchangeIndex=j;
}
}
i=lastExchangeIndex;//一趟排序中无序序列中最后一个记录的位置
}
}
了解什么是堆?
堆是满足下列性质的数列{r1,r2,…,rn}:
(小顶堆)(大顶堆)
第四章栈和队列
重点内容及要求:
1、掌握栈和队列的结构特点及基本操作(入栈、出栈/入队、出队)。
栈(后进先出),队列(先进先出)
构造空栈:
voidInitStack_Sq(SqStack&S)
{//构造一个空栈S
=newSElemType[maxsize];
=-1;
=maxsize;
=incresize;
}
栈:(入栈)
voidPush_Sq(SqStack&S,SElemTypee){
if(==-1)
incrementStacksize(S);
//如果顺序栈的空间已满,应为栈扩容
[++]=e;
//在栈顶插入数据元素
}
栈:(入栈)
boolPop_Sq(SqStack&S,SElemType&e){
//若栈不空,则删除S的栈顶元素,
//用e返回其值,并返回TRUE;
//否则返回FALSE。
if(==-1)returnFALSE;
e=[--];
returnTRUE;
}
2、对于顺序栈,熟悉栈空和栈满的条件;对于链栈,掌握其栈空的条件。
#include<iostream>
usingnamespacestd;
#defineINITSIZE100
#defineRESIZE20
typedefstruct{
int*base;
int*top;
intstacksize;
}Sqstack;
intInitstack(SqstackS){
=(int*)malloc(INITSIZE*sizeof(int));
if(!)returnfalse;
=;
=INITSIZE;
returntrue;
}
intClearstack(Sqstack&S){
free();
=(int*)malloc(INITSIZE*sizeof(int));
=;
returntrue;
}
intStackempty(SqstackS){
if(==)returntrue;
elsereturnfalse;
}
intPush(Sqstack&S,inte){
if(->=){
=(int*)realloc(,(RESIZE+INITSIZE)*sizeof(int));
if(!)returnfalse;
=+;
+=RESIZE;
}
*++=e;
returntrue;
}
intPop(Sqstack&S,int&e){
if(==)returnfalse;
e=*--;
returntrue;
}
intmain()
{
SqstackS;
intt,e;
Initstack(S);
cin>>t;//需要输入元素的个数
while(t--)
{
cin>>e;
Push(S,e);
}//进栈
while(!=)
{
Pop(S,e);
cout<<e<<"";
}//出栈
}
链栈栈空的判断判断链栈是否为空很简单,还记得结构体定义时的那个count吗?如果那个count为0,就说明链栈为空。
StatusClearStack(LinkStack*S)
{
LinkStackPtrp,q;
p=S->top;
while(p)
{q=p;
p=p->next;
free(q);
}
S->count=0;
returnOK;
}
3、掌握栈的典型应用——背包问题求解的基本方法。
背包问题
假设有n件体积分别为w1,w2,…,
即wi1+wi2+…+wik=T,则背包问题有解;
否则无解.
以W(1,8,4,3,5,2),T=10为例
(1,4,3,2),(1,4,5),(8,2)和(3,5,2)是其解。
算法如下
voidknapsack(intw[],intT,intn){
//T在算法中是剩余的容积,初值为背包的体积
InitStack(S);k=0;
do{while(T>0&&k<n){
if(T-w[k]>=0){//第k件物品可以进栈
Push(S,k);T─=w[k];
}
k++;
}
if(T==0)StackTraverse(S);//输出一个解
Pop(S,k);T+=w[k];//退出栈顶物品
k++;
}while(!StackEmpty(S)||k<n);
}
4、对于带头结点的链队列,掌握队列为空的条件,熟悉入队、出队的基本操作方法。
voidInitQueue(LiQueue*&q)
{q=(LiQueue*)malloc(sizeof(LiQueue));
q->front=q->rear-NULL;