c语言算法与数据结构

《c语言算法与数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十二章算法与数据结构12.1算法的基本概念该节知识点所占试题比重为12%，属于重点考查对象，基本上每次必考，主要考查算法的定义和对算法复杂度的理解。历次试题分值在0－4分之间波动。12.1.1考点1：　算法的定义算法是对一个问题求解步骤的一种描述，是求解问题的方法，它是指令的有限序列，其中每条指令表示一个或者多个操作。一般来说，一个算法具有以下5个主要特性。有穷性：一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成。确定性：算法中的每一步都有确切的含义。可行性：算法中的操作能够用已经实现的基本运算

2、执行有限次来实现。输入：一个算法有零个或者多个输入，零个输入就是算法本身确定了初始条件。输出：一个算法有一个或者多个输出，以反映出数据加工的结果。12.1.2考点2：算法复杂度算法复杂度包括时间复杂度和空间复杂度，是衡量一个算法好坏的度量。1、时间复杂度：基本操作重复执行的次数的阶数T(n)=o(f(n))2、空间复杂度：是算法所需空间的度量。G（n）=O(f(n))例1：NXN矩阵相乘for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=

3、c[i][j]+a[i][k]*b[k][j];}12.2数据结构的定义该节知识点所占试题比重为12%，属于重点考查对象，基本上每次必考，主要考查数据的逻辑结构和存储结构。历次试题分值在0－4分之间波动。12.2.1考点1：什么是数据结构一、基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据结构（datastructure)—数据元

4、素和数据元素关系的集合数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素1140

5、01346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：12.2.2考点2：数据结构的图形表示根据数据元素之间关系的不同，通常有4种结构：集合、线性结构、树型结构和图状结构。12.3线性表线性表一般和其他知识点结合起来出题。在每次所考的数据结构、栈、队列、链表、查找、排序等试题中，均涉及线性表的概念。12.3.1考点1：线

6、性表一、线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继二、线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素特征：元素个数n—表长度，n=0空表1

7、单元来存储线性表的元素。线性表中第i+1个元素的存储位置loc(ai+1)和第i个元素的存储位置loc（ai）满足以下关系：Loc(ai+1)=loc(ai)+S其中：S—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现12.3.2考点2：线性表的顺序存储结构线性表的第i个元素的存储位置为：Loc(ai)=loc(a1)+(i-1)×s其中，loc(a1)表示第1个数据元素的存储位置，一般被称为线性表的基地址。12.3.3考点3：线性

8、表的插入和删除操作线性表的插入操作是指在线性表的第i个元素与第i＋1个元素之间插入一个新的数据元素a，使长度为n的线性表（a1…，ai,ai+1,…,an）变成长度为n＋1的线性表（a1…，ai,a,ai+1,…,an）算法时间复杂度T(n)在长度为n的线性表中插入一个元素时，所需移动的元