数据结构与算法设计知识点
若整个排序过程不需要访问外存便能完成,则称此类排序问题为
内部排序;反之则为外部排序。
选择排序:从记录的无序子序列中“选择”关键字最小或最大的记 录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的
长度
基本代码如下
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;}/*则交换最值和当前序列的第一个数*/ }
线性表必有: 1.集合中必存在唯一的一个“第一元素”
3
2.集合中必存在唯一的一个 “最后元素”
3.除最后元素在外,均有 唯一的后继;
4.除第一元素之外,均有 唯一的前驱
定义如下:
typedef int ElemType;
typedef struct{ ElemType*elem;
//存储数据元素的一维数组;
4、学会对线性表设计相关的算法进行相应的处理。
第三章 排序
重点内容及要求: 1、掌握对顺序表数据记录进行排序的基本思路和常规操作(比较、移动),了解排序算 法的稳定性问题。 2、掌握简单选择排序、直接插入排序、冒泡排序算法,了解各种排序算法的特点及时 间复杂度。
排序:将一组“无序”的记录序列按某一关键字调整为“有序”的记 录序列。
关键码:也叫关键字(Key),是数据元素中能起标识作用的数 据项。
其中能起到唯一标识作用的关键码称为主关键码(简称主码); 否则称为次关键码。通常,一个数据元素只有一个主码,但可以有多 个次码。
关系:指一个数据集合中数据元素之间的某种相关性。 数据结构:带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型:是一个值的集合和定义在此集合上的一组操作的总
int length; int listsize;
//线性表当前长度; //当前分配数组容量;
}SqList; Void InitSqList(SqList A,int maxsize)//初始化线性表
{
A.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点
(表示数据元素 或 数据元素的映象) 单链表是一种顺序存取的结构,求以此为存储表示的线性表长
度,可设置一个计数器
3、了解有序线性表的特点(顺序有序表、有序链表)。
有序线性表:线性表中的数据元素相互之间可以比较,并且数据
4
元素在线性表中依值非递减或非递增有序排列,即 ai≥ai-1 或 ai≤ai-1(i = 2,3,…, n),则称该线性表为有序表(Ordered List)
相邻的记录的关键字进行比较,若前面记录的关键字大于后面记录的
关键字,则将它们交换,否则不交换。或者反过来,使较大关键字的
记录后移,像水中的气泡一样,较小的记录向前冒出,较大的记录
像石头沉入后部。故称此方法为冒泡排序法
代码如下:
void BubbleSort( SqList &L )
{ RcdType W;
}
7
2、对于顺序栈,熟悉栈空和栈满的条件;对于链栈,掌握其栈空的条件。 #include <iostream> using namespace std; #define INITSIZE 100 #define RESIZE 20 typedef struct {
int *base; int *top; int stacksize; }Sqstack; int Initstack(Sqstack S){ S.base=(int *)malloc(INITSIZE*sizeof(int)); if(!S.base) return false; S.top=S.base; S.stacksize=INITSIZE; return true; } int Clearstack(Sqstack &S){ free(S.base); S.base=(int *)malloc(INITSIZE*sizeof(int)); S.top=S.base; return true; } int Stackempty(Sqstack S){ if(S.base==S.top) return true; else return false; } int Push(Sqstack &S,int e){ if(S.top-S.base>=S.stacksize){ S.base=(int *)realloc(S.base,(RESIZE+INITSIZE)*sizeof(int)); if(!S.base) return false; S.top=S.base+S.stacksize; S.stacksize+=RESIZE; } *S.top++=e; return true; } int Pop(Sqstack &S,int &e){ if(S.base==S.top) return false; e=*--S.top; return true; } int main()
if(!A.elem)
{
exit(0);
}
A.length = 0;
A.listsize = LIST_INIT_SIZE;
return ;
}
2、 了解线性表的链式存储结构,重点掌握带头结点的单链表的基本操作(结点 的插入与删除运算),了解单向循环链表和双向链表存储表示方法。
单链表:用一组地址任意的存储单元存放线性表中的数据元素。
g(n) 的增长率相同。 算法的存储量包括: 1. 输入数据所占空间 2. 程序本身所占空间 3. 辅助变量所占空间
第二章 线性表
重点内容及要求: 1、 掌握线性表的顺序存储结构,了解顺序表的存储特点(数据元素在内存中依次
顺序存储),优点:可随机存取访问;缺点:结点的插入/删除操作不方便。
线性表:是一种最简单的数据结构,也是构造其它各类复杂 数据结构的基础。一个数据元素的有序(次序)集。它有顺序和 链式两种存储表示方法。
栈(后进先出),队列(先进先出)
构造空栈:
void InitStack_Sq (SqStack &S) { // 构造一个空栈 S
S.elem = new SElemType[maxsizபைடு நூலகம்]; S.top =-1; S.stacksize = maxsize; S.incrementsize=incresize; }
数据结构与算法设计知识点
试题类型:
本课程为考试科目(闭卷笔试),试题类型包括:概念填空题(10 %),是非判断题(10 %), 单项选择题(40 %),算法填空题(10%),算法应用题(20 %),算法设计题(10 %)。
第一章 绪论
重点内容及要求: 1、 了解与数据结构相关的概念(集合、数据、数据元素、数据项、关键字、元
8
{ Sqstack S; int t,e; Initstack(S); cin>>t; //需要输入元素的个数 while(t--) { cin>>e; Push(S,e); } //进栈 while(S.top!=S.base) { Pop(S,e); cout<<e<<" "; }// 出栈
i = L.length;
while (i >1) {
// i>1 表明上一趟曾进行过记录的交换
lastExchangeIndex = 1;
for (j = 1; j < i; j++){
if (L.r[j+1].key < L.r[j].key) {
W=L.r[j];L.r[j] =L.r[j+1];L.r[j+1] = W; // 互换记录
3、 了解算法分析的基本方法,掌握算法时间复杂度相关的概念。
算法:是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性:1.有穷性 2.确定性 3.可行性 4.有输入 5.有输出 设计算法时,通常还应考虑满足以下目标:
1.正确性,2.可读性, 3.健壮性 4.高效率与低存储量需求
lastExchangeIndex = j;
}
}
i = lastExchangeIndex; // 一趟排序中无序序列中最后一个记录的位置
}
}
3、 了解什么是堆?
堆是满足下列性质的数列{r1, r2, …,rn}:
6
rrii(小顶堆rr2)i2i1
rri(i大顶堆rr2)i2i1
第四章 栈和队列
重点内容及要求: 1、掌握栈和队列的结构特点及基本操作(入栈、出栈/入队、出队)。
1
称。
2、 掌握数据结构的基本概念、数据的逻辑结构(四种)和物理结构(数据元素 的表示与关系的表示、两类存储结构:顺序存储结构和链式存储结构)。
数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构:是对数据元素之间存在的逻辑关系的一种 抽象的描述,可以用一个数据元素的集合和定义在此集合上的若 干关系来表示 逻辑结构有四种:线性结构、树形结构、图状结构、集合结构 数据的物理结构:是其逻辑结构在计算机中的表示或实现, 因此又称其为存储结构。 存储结构:顺序存储结构和链式存储结构 顺序存储结构:利用数据元素在存储器中相对位置之间的某种 特定的关系来表示数据元素之间的逻辑关系; 链式存储结构:除数据元素本身外,采用附加的“指针”表示数 据元素之间的逻辑关系。