复习提纲-数据结构

《复习提纲-数据结构》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。数据结构的定义：数据之间的相互关系，即数据的组织形式。包含三个方面——1.逻辑结构：数据元素之间的逻辑关系。线性结构：一对一关系。非线性结构：多对多关系。2.存储结构：数据元素及其关系在计算机内存储器的表示。顺序存储结构：如数组。链式存储结构：如链表。索引存储结构：稠密索引：每个结点都有索引项。稀疏索引：每组结点都有索引项。散列存储结构：如散列表。3.数据运算。对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合，常用的有：检索、

2、插入、删除、更新、排序。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。·原子类型：由语言提供。值不能分解。结构类型：由用户借助于描述机制定义，是导出类型。抽象数据类型ADT：是抽象数据的组织和与之的操作。相当于在概念层上描述问题。优点是将数据和操作封装在一起实现了信息隐藏。程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：1、算法是正确的；2、执行算法的时间；3、执行算法的存储空间（主要是辅助存储空间）；4、算法易于理解、编码、调试。时间复杂度

3、：是某个算法的时间消耗，它是该算法所求问题规模n的函数。渐近时间复杂度：是指当问题规模趋于无穷大时，该算法时间复杂度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。时间复杂度按数量级递增排列依次为：常数阶：O(1)对数阶：O(log2n)线性阶：O(n)线性对数阶：O(nlog2n)平方阶：O(n2)立方阶：O(n3)指数阶：O(2n)空间复杂度：是某个算法空间消耗，它是该算法所求解问题规模n的函数。算法的时间复杂时和空间复杂时合称算法复杂度。第二章线性表是由n≥0个数据元素组成的有限序列。n=

4、0是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。　线性表上定义的基本运算：·构造空表：Initlist(L)·求表长：Listlength(L)·取结点：GetNode(L,i)·查找：LocateNode(L,x)·插入：InsertList(L,x,i)·删除：Delete(L,i)顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。地址计算：LOCa(i)=LOCa(1)+(i-1)*d；（首地址为1）顺序表的类型定义：#defineListsize100;/*设置线性表的最大长度为1

5、00*/typedefintDataType;//DataType的类型可根据实际情况而定typedefstruct{DataTypedata[Listsize];//向量data用于存放表结点intLength;/*记录当前表中元素的个数*/}Seqlist；在顺序表中实现的基本运算：1.顺序表的初始化（建立一个空的顺序表）voidInitate(Seqlist*L)//L指向结构体类型变量Seqlist{L－>Length=0;}//L－>Length表示L所指向结构体变量Seqlist的Length成员2.求顺序表的长度intLength(Seqlist*L){returnL－

6、>length;}3、插入：顺序表的插入操作：顺序表的插入操作是指在顺序表的第i(1≤i≤n+1)位置上，插入一个新结点x，使长度为n的线性表变成长度为n+1的线性表。voidInsertList(Seqlist*L,DataTypex，inti){intj;if(i<1

7、

8、i>L→length+1)printf("positionerror");if(L－>length>=ListSize)printf("overflow!");for(j=L－>length-1;j>=i-1;j--)L－>data[j+1]=L－>data[j];L－>data[i-1]=x;L－>le

9、ngth++;}算法分析：最坏的情况：i=1，需要结点移动n次，时间复杂度为O(n)最好的情况：i=n+1，不需要移动结点，时间复杂度为O(1)平均时间复杂度：结点移动次数为：(n+(n-1)+(n-2)+...+1+0)/(n+1)=n/2时间复杂度为O(n)4、删除：线性表的删除运算是指将表的第i(1≤i≤n)个结点删去，使长度为n的线性表变成长度为n-1的线性表voidDeleteList(SeqList*L,inti){intj;if(i<1

10、

11、i