自学专业考试数据结构重点总结分析02331(2014整理).doc
《自学专业考试数据结构重点总结分析02331(2014整理).doc》由会员分享,可在线阅读,更多相关《自学专业考试数据结构重点总结分析02331(2014整理).doc(21页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、.自考数据结构重点(自考数据结构重点(20142014 整理)整理)第一章第一章 概论概论 1.瑞士计算机科学家沃思提出:算法+数据结构=程序。算法是对数据运算的描述,而数据结构包括逻辑结构和存储 结构。由此可见,程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法,而好的算法在很大 程度上取决于描述实际问题的数据结构。 2.2.数据数据是信息的载体。数据元素数据元素是数据的基本单位。一个数据元素可以由若干个数据项数据项组成,数据项数据项是具有独立含 义的最小标识单位。数据对象数据对象是具有相同性质的数据元素的集合。 3.3.数据结构数据结构指的是数据元素之间的相互关系,即数据的
2、组织形式。 数据结构一般包括以下三方面内容:数据的逻辑结构、数据的存储结构、数据的运算数据结构一般包括以下三方面内容:数据的逻辑结构、数据的存储结构、数据的运算 数据的逻辑结构是从逻辑关系上描述数据,与数据元素的存储结构无关,是独立于计算机的。 数据的逻辑结构分类数据的逻辑结构分类: : 线性结构和非线性结构 数据元素及其关系在计算机内的存储方式,称为数据的存储结构(物理结构)数据的存储结构(物理结构) 。 数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。 数据的运算数据的运算。最常用的检索、插入、删除、更新、排序等。 4. .数据的四种基本存储方法数据的四种基本存储方法: :
3、 顺序存储、链接存储、索引存储、散列存储 (1)顺序存储:通常借助程序设计语言的数组数组描述。 (2)链接存储:通常借助于程序语言的指针来描述。 (3)索引存储:索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 (4)散列存储:该方法的基本思想是:根据元素的关键字直接计算出该元素的存储地址。 5.算法必须满足 5 个准则:输入输入,0 个或多个数据作为输入;输出输出,产生一个或多个输出;有穷性有穷性,算法执行有限 步后结束;确定性确定性,每一条指令的含义都明确;可行性可行性,算法是可行的。 算法与程序的区别:程序必须依赖于计算机程序语言,而一个算法可用自然语言、计算
4、机程序语言、数学语言或 约定的符号语言来描述。目前常用的描述算法语言有两类:类 Pascal 和类 C。 6.评价算法的优劣:算法的“正确性“是首先要考虑的。此外,主要考虑如下三点: 执行算法所耗费的时间,即时间复杂性; 执行算法所耗费的存储空间,主要是辅助空间,即空间复杂性; 算法应易于理解、易于编程,易于调试等,即可读性和可操作性。 以上几点最主要的是时间复杂性,时间复杂度常用渐进时间复杂度表示。 7.算法求解问题的输入量输入量称为问题的规模,用一个正整数 n 表示。 8.常见的时间复杂度按数量级递增排列依次为:常数阶 0(1)、对数阶 0(log2n)、线性阶 0(n)、线性对数阶 0(
5、nlog2n)、平方阶 0(n2)立方阶 0(n3)、k 次方阶 0(nk)、指数阶 0(2n)和阶乘阶 0(n!)。 9.一个算法的空间复杂度 S(n)定义为该算法所耗费的存储空间,它是问题规模 n 的函数,它包括存储算法本身所占 的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。第二章第二章 线性表线性表 1.数据的运算是定义在逻辑结构上的,而运算的具体实现是在存储结构上进行的。 2.只要确定了线性表存储的起始位置,线性表中任意一个元素都可随机存取,所以顺序表是一种随机存取结构。 3.常见的线性表的基本运算: (1)置空表 InitList(L) 构造一个空
6、的线性表 L。 (2)求表长 ListLength(L)求线性表 L 中的结点个数,即求表长。 (3)GetNode(L,i) 取线性表 L 中的第 i 个元素。 (4)LocateNode(L,x)在 L 中查找第一个值为 x 的元素,并返回该元素在 L 中的位置。若 L 中没有元素的值为 x ,则返回 0 值。 (5)InsertList(L,i,x)在线性表 L 的第 i 个元素之前插入一个值为 x 的新元素,表 L 的长度加 1。 (6)DeleteList(L,i)删除线性表 L 的第 i 个元素,删除后表 L 的长度减 1。 4.顺序存储方法:把线性表的数据元素按逻辑次序依次存放在
7、一组地址连续的存储单元里的方法。 顺序表(Sequential List):用顺序存储方法存储的线性表称为顺序表。顺序表顺序表是一种随机存取结构随机存取结构, ,顺序表的.特点是逻辑上相邻的结点其物理位置亦相邻。 5.顺序表上实现的基本运算:顺序表上实现的基本运算: (1 1)插入:)插入:该算法的平均时间复杂度是 O(n),即在顺序表上进行插入运算,平均要移动一半结点(n/2) 。 (2 2)删除)删除:顺序表上做删除运算,平均要移动表中约一半的结点(n-1)/2,平均时间复杂度也是 O(n)。 6.采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定,因此单链表可以用头指
8、针的名 字来命名。生成结点变量的标准函数生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode); /函数 malloc 分配 一个类型为 ListNode 的结点变量的空间,并将其首地址放入指针变量 p 中释放结点变量空间的标准函数释放结点变量空间的标准函数 free(p); /释放 p 所指的结点变量空间 结点分量的访问结点分量的访问 方法二:p-data 和 p-next 指针变量指针变量 p p 和结点变量和结点变量*p*p 的关系的关系: : 指针变量 p 的值结点地址, 结点变量*p 的值结点内容 7.建立单链表建立单链表: : (1)
9、头插法建表:算法: p=(ListNode *)malloc(sizeof(ListNode);/生成新结点p-data=ch; /将读入的数据放入新结点的数据域中p-next=head;head=p;(2) 尾插法建表:算法: p=(ListNode *)malloc(sizeof(ListNode); /生成新结点p-data=ch; /将读入的数据放入新结点的数据域中if (head=NULL)head=p;/新结点插入空表elserear-next=p;/将新结点插到*r 之后rear=p;/尾指针指向新表尾(3) 尾插法建带头结点的单链表: 头结点及作用:头结点及作用:头结点是在链表
10、的开始结点之前附加一个结点。它具有两个优点:由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上 操作一致,无须进行特殊处理;无论链表是否为空,其头指针都是指向头结点的非空指针(空表中头结点的指针域空) ,因此空表和非空表 的处理也就统一了。 头结点数据域的阴影表示该部分不存储信息。在有的应 用中可用于存放表长等附加信息。具体算法:r=head; / 尾指针初值也指向头结点while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/生成新结点s-data=ch; /将读入的数据放入新结点的数
11、据域中.r-next=s;r=s;r-next=NULL;/终端结点的指针域置空,或空表的头结点指针域置空 以上三个算法的时间复杂度均为以上三个算法的时间复杂度均为 O(n)O(n)。 8.单链表上的查找:(带头结点) (1)按结点序号查找:序号为 0 的是头结点。 算法:p=head;j=0;/从头结点开始扫描while(p-nextj+;if(i=j)return p;/找到了第 i 个结点else return NULL;/当 i0 时,找不到第 i 个结点时间复杂度:在等概率假设下,平均时间复杂度为:为时间复杂度:在等概率假设下,平均时间复杂度为:为 n/2=O(n)n/2=O(n)
12、(2)按结点值查找: 具体算法:ListNode *p=head-next;/从开始结点比较。表非空,p 初始值指向开始结点while(p/扫描下一结点return p;/若 p=NULL,则查找失败,否则 p 指向值为 key 的结点 时间复杂度为:时间复杂度为:O(n)O(n) 9.插入运算:插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上,即插入到 ai-1与 ai之间。s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s; 算法的时间主要耗费在查找结点上,故时间复杂度亦为 O(n)。
13、10.删除运算删除运算r=p-next;/使 r 指向被删除的结点 aip-next=r-next;/将 ai从链上摘下free(r);/释放结点 ai的空间给存储池 算法的时间复杂度也是 O(n) 。 p 指向被删除的前一个结点。链表上实现的插入和删除运算,无须移动结点,仅需修改指针。 11.单循环链表在单链表中,将终端结点的指针域 NULL 改为指向表头结点或开始结点即可。判断空链表的条件是head=head-next; 12.仅设尾指针的单循环链表仅设尾指针的单循环链表: : 用尾指针 rear 表示的单循环链表对开始结点 a1和终端结点 an查找时间都是 O(1)。 而表的操作常常是在
14、表的首尾位置上进行,因此,实用中多采用尾指针表示单循环链表。判断空链表的条件为.rear=rear-next;13.13.循环链表:循环链表:循环链表的特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活。 若在尾指针表示的单循环链表上实现,则只需修改指针,无须遍历,其执行时间是 O(1)。具体算法: LinkList Connect(LinkList A,LinkList B) /假设 A,B 为非空循环链表的尾指针 LinkList p=A-next;/保存 A 表的头结点位置A-next=B-next-next;/B 表的开始结点链接到 A 表尾free(B-nex
15、t);/释放 B 表的头结点B-next=p;/return B;/返回新循环链表的尾指针 循环链表中没有 NULL 指针。涉及遍历操作时,其终止条件就不再是像非循环链表那样判别 p 或 p-next 是否 为空,而是判别它们是否等于某一指定指针,如头指针或尾指针等。 在单链表中,从一已知结点出发,只能访问到该结点及其后续结点,无法找到该结点之前的其它结点。而在单 循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现。 14.双向链表双向链表: : 双(向)链表中有两条方向不同的链,即每个结点中除 next 域存放后继结点地址外,还增加一个指 向其直接前趋
16、的指针域 prior。 双链表由头指针 head 惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来,为双(向)循环链表。15.双向链表的前插和删除本结点操作双向链表的前插和删除本结点操作 双链表的前插操作void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中,将值为 x 的新结点插入*p 之前,设pNULL.DListNode *s=malloc(sizeof(DListNode);/s-data=x;/s-prior=p-prior;/s-next=p;/p-prior-next=s;/p-prior=s;/
17、双链表上删除结点*p 自身的操作void DDeleteNode(DListNode *p)/在带头结点的双链表中,删除结点*p,设*p 为非终端结点p-prior-next=p-next;/p-next-prior=p-prior;/free(p);/ 与单链表上的插入和删除操作不同的是,在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的 时间复杂度均为 O(1)。 16.顺序表和链表比较 时间性能:a、线性表:经常性的查找; b、链式存储结构:经常插入删除操作; 空间性能:a、对数据量大小事先能够知道的用线性表; b、数据量变化较大的用链式存储结构。 存储密度越大,存储空间的
18、利用率越高。显然,顺序表的存储密度是 1,链表的存储密度肯定小于 1。第三章 栈和队列 1.栈称为后进先出后进先出(Last In First Out)的线性表,简称为 LIFOLIFO 表表。栈是运算受限的线性表,顺序栈也是用数组表示的。进栈操作:进栈时,需要将 S-top 加 1, S-top=StackSize-1 表示栈满 “上溢上溢“现象-当栈满时,再做进栈运算产生空间溢出的现象。 退栈操作:退栈时,需将 S-top 减 1, S-topfront=Q-rear=0; 判队空判队空: : return Q-rear=Q-front; 判队满判队满: : return (Q-rear+
19、1)%QueueSize=Q-front; 入队入队 Q-dataQ-rear=x; /新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; 出队出队 temp=Q-dataQ-front;Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加 1return temp; 取队头元素取队头元素 return Q-dataQ-front; 6.队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。为了简化处理,在队头结点之前附加一个头结点,并设队头指针指向此结点。链队列的基本运算链队列的基本运算: :(带头结点)(带头结点) (1
20、) 构造空队:Q-rear=Q-front;Q-rear-next=NULL; (2) 判队空:return Q-rear=Q-front; (3) 入队:QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申请新结点p-data=x; p-next=NULL;Q-rear-next=p; /*p 链到原队尾结点后Q-rear=p; /队尾指针指向新的尾 (4) 出队:当队列长度大于 1 时,只需修改头结点指针,尾指针不变s=Q-front-next; Q-front-next=s-next; x=s-data; free(s); retur
21、n x; 当队列长度等于 1 时,不仅要修改头结点指针,还要修改尾指针s=Q-front-next; Q-front-next=NULL; Q-rear=Q-front; x=s-data; free(s); return x; (5) 取队头元素:return Q-front-next-data; 因为有头结点,所以用了 next 和链栈类似,无须考虑判队满的运算及上溢。 在出队算法中,一般只需修改队头指针。但当原队中只有一个结点时,该结点既是队头也是队尾,故删去此结点 时亦需修改尾指针,且删去此结点后队列变空。 7.用计算机来处理计算算术表达式问题,首先要解决的问题是如何将人们习惯书写的中
22、缀表达式转换成后缀表达式。.第四章 多维数组和广义表 1.数组的顺序存储方式数组的顺序存储方式: :一般采用顺序存储方法表示数组。 (1)行优先顺序 a11,a12,a1n,a21,a22,a2n,,am1,am2,,amn (2)列优先顺序 a11,a21,am1,a12,a22,am2,,a1n,a2n,,amnPascal 和 C 语言是按行优先顺序存储的,而 Fortran 语言是按列优先顺序存储的。 2.为了节省存储空间,可以对矩阵中有许多值相同或值为零的元素的矩阵,采用压缩存储。 特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。 (1)对称矩
23、阵 在一个 n 阶方阵 A 中,若元素满足下述性质: aij=aji 0i,jn-1 称为 n 阶对称矩阵,它的元素是关于主对角线对称的,所以只需要存储矩阵上三角或下三角元素即可,让两个 对称的元素共享一个存储空间。 矩阵元素 aij和数组元素 sa【k】之间的关系是k=i(i+1)/2+j ij 0k,有 向边又称为弧,起点称为弧尾,终点称为弧头。无向图的顶点对用圆括号表示(vi,vj)。 在无向图中,称 vi和 vj相邻接,在有向图中称顶点 vi邻接到 vj,顶点 vj邻接于 vi 在无向图中,n 的取值范围是 0-n(n-1)/2,将具有 n(n-1)/2 条边的无向图称为无向完全图。
24、在有向图中,n 的取值范围是 0-n(n-1),将具有 n(n-1)条边的有向图称为有向完全图。 无向图中,顶点的度定义为以该顶点为一个端点的边的数目,有向图的度等于出度和入度之和。 在无向图中,任意两顶点都有路径,则称两顶点连通。若图 G 中的任意两个顶点都连通,称 G 为连通图。无向图 的极大连通子图称为连通分量,显然,任何连通图的连通分量只有一个,即其自身,而非连通的无向图有多个连通而非连通的无向图有多个连通 分量分量。 在有向图中,图 G 中任意两顶点连通,称为强连通图,极大连通子图称为强连通分量。 若在一个图的每条边上标上某种数值,该数值称为该边的权。边上带权的图称为带权图,带权的连
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自学 专业 考试 数据结构 重点 总结 分析 02331 2014 整理
限制150内