数据结构重点 整理.doc

《数据结构重点 整理.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构重点整理第一章绪论1、例题：（可参照课本第3页理解）多叉路口交通灯的管理问题：有连线的节点用不同的颜色标记,表示不能同时通行.要求使用的颜色数尽可能少,以减少等待时间.图论中的四色问题.2、数据结构定义：是相互之间存在一种或多种特定关系的数据元素的集合。数据之间不是相互独立的，他们之间有某种特定的关系，这种数据元素之间的关系，称为“结构”，结构=实体+关系.3、四种基本逻辑结构1.集合：元素仅属于同一个集体，没有其他关系。2.线性结构：存在一对一关系，序列相邻，次序关系3.树型结构：存在一对多关系，层次关系。

2、4.图状结构（网状结构）：存在多对多关系，任意性4、两种存储结构：顺序存储、链接存储顺序存储结构——借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。链式存储结构——借助指示元素存储地址的指针表示数据元素之间的逻辑关系。5、.算法定义：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。6、算法的重要特性(1)有穷性：能执行结束(2)确定性：对于相同的输入执行相同的路径(3)0至多个输入(4)1至多个输出(5)有效性(可行性)（用于描述算法的操作都是足够基本的）7、例题：设计一个

3、考试日程安排表，使在尽可能短的时间内安排完考试，要求同一个学生选修的几门课程不能安排在同一个时间内。数据元素的集合。解决该问题，首先选择一个合适的数据结构。用无向图表示，图中的顶点表示课程，不能同时考试的课程之间连上一条边。则该问题就抽象成对该无向图进行“着色”操作，即用尽可能少的颜色去给图中每个顶点着色，使得任意两个相邻的顶点着不同的颜色。同一种颜色表示一个考试时间。Ø答案：1：A,C2:B,D3:E4:F8、时间复杂度定义：一般情况下，算法中基本操作重复执行的时间是问题规模n的某个函数f(n)，算法的时间量度记作

4、T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。9、空间复杂度（1）存储算法本身所占用的空间（2）算法的输入/输出数据占用的空间（3）算法在运行过程中临时占用的辅助空间第二章线性表1、每个结点包含数据域和指针域。数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。2、（1）在P所指向的结点之后插入新的结点（建议看书上29页图2.8）（2）单链表删除时指针发生的变

5、化（课本第29页图2.9）！！！注：课本第29页除程序以外的内容要好好看懂！并要能看懂p--->next=s等的语句描述。第三章栈和队列1、栈：是限定只在表尾进行插入或删除操作的线性表。又称为后进先出的线性表。设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。2、括号匹配的检验：检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。（P49要看懂！）3.行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现

6、有误时可以及时更正。（P49要看懂！）4、队列（Queue）:先进先出(FirstInFirstOut)(缩写为FIFO）的线性表。仅在队尾进行插入和队头进行删除操作的线性表5：判断列队是“空”还是“满”（列头用front表示，列尾rear）当Q.rear>Q.front时:Q.rear–Q.front=队列中元素个数当Q.rear

7、（P80）（了解内容）第五章数组和广义表1、假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元,a-ij.之间存在着一一对应关系：（P95）下三角，含对角线上三角，不含对角线..2、对角矩阵概念（P96）：所有的非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其他的元皆为零。3、稀疏矩阵，称δ为矩阵的稀疏因子。通常认为时称为稀疏矩阵。4、会判断广义表的表头和表尾分别是什么（P108例子及结论要看懂）5、m元多项式的表示

8、P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 P(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15 P=z((A,2),(B,1),(15,0)) (P111)该三元项可用下列的广义表表示：P=z((A,2),(B,1),(15,0))6