09地科数据结构总复习指导1

《09地科数据结构总复习指导1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构复习备考指南下面列出的只作为复习車点，并非是考试题，可能是考试相关知识点的罗列；总则：认真复习每一次实验报告当中的内容，认真复习作业当中的内容；认真复习上课讲解的重要内容与课件；认真复习所上章节当中每个知识的基本概念；第一章***1:数据结构的概念，数据的逻辑结构和物理结构的联系与区别数据结构就是研究数据的逻辑结构和物理结构以及它们Z间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型的一门学科。简单地说，数据结构是指相互有关联的数据元索的集合，即数据的组织形式。*和数据项、数据类型、数据元素、数据变量2、数据的逻辑结构

2、和存储结构1、数据的逻辑结构数据的逻辑结构是指数据Z间的相互关系。一般包括：线性结构和非线性结构。1）线性结构：其特点是：结构中有H仅有一个始结点和一个终结点，始结占只有一个灰继结点，终结点只有一个询趋结点，每个内结点有且仅有一个前趋结点和一个后继结点。线性结构最一般的情形是线性表。如卜图：0000线性表2）非线性结构其特点是：结构屮的结点可能有多个前趋结点和多个后继结点。通常有集合，树和网三种类型。如下图。最亜要的非线形结构是“树”，树中有且仅有一个没有前趋结点的结点，称Z为根结点;其他结点都仅有一个前趋结点，但允许有多个后继结点。从根结点到任一非根结点，都有且仅有一条

3、路径。集合树网2、数据的存储结构数据的最基本的存储结构一般有以下四种：***顺序存储方法，链接存储方法，索引存储方法，散列存储方法。3算法的五个特性参看教材。4算法中基木操作重复执行的次数依据算法中最大语句频度来估算，它是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n)),表示随问题规模n的增大，算法执行时间的增长度和f(n)的增长度相同。常用时间复杂度有如下关系：0⑴W0(log2n)WO(n)W0(nlog2n)WO(r?)WO(r?)W…W0(『)W0(2j粋*参考练习分析以下程序段的时间复杂度。for(i=0;i

4、j

5、1)在非空的线性表，有且仅有一个开始结点细，它没有直接询趋，而仅有一个直接后继a2；2)有且仅有一个终端结点尙，它没有直接后继，而仅有一个直接前趋an.1；其余的内部结点珈2勻即・1)都有口仅有一个直接前趋盼]和一个直接后继讪。线性表是一种典型的线性结构。*和2、顺序表的结构类型定义/*顺序表的定义：*/#clefineListSize100/*表空间大小可根据实际需耍而定，这里假设为100*/typedefintDataType;/^DataTypenJ'以是任何相应的数据类型如int,float或char*/typedefstruct{DataTypedata[Lis

6、tSize];/*向量data用于存放表结点*/intlength;/*当前的表长度*/}SeqList;***3/*顺序表的建立：*/voidCreateList(SeqList*L,intn){inti;for(i=0;idata[i]);L~>length=n;}/*顺序表的打印:*/voidPrintUst(SeqListL,intn){inti;for(i=0;i

7、ListL,DataTypex){inti=0;whi1e(i