自学《数据结构》期末考试复习资料小抄版（呕心沥血整理）

《自学《数据结构》期末考试复习资料小抄版（呕心沥血整理）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、自考数据结构重点(2014整理)第一章概论1•瑞士计算机科学家沃思^{11：算法+数据结构二程序。算法是对数据运算的描述,而数据结构包括逻辑结构和存储结构。山此叮见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很人程度上取决丁•描述实际问题的数据结构。2•数据是信息的载体。数据元素是数据的基木单位。一个数据元索可以山若干个数据项纽成，数据项是具冇独立含义的最小标识单位。数据对象是具仃相同性质的数据元索的集合。3.数据结构指的是数据元索之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内

2、容：数据的逻辑结构.数据的存储结构.数据的运算①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。数据的逻辑结构分类：线性结构和非线件结构②诊据元索及我关系在计算机内的存储方式.称为数据的存储结构(物理结构)。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。③数据的运算。最常用的检索、插入、删除、更新、排序等。4•数据的四种基本存储方法：顺序存储、链接存储、索引存储、散列存储(1)顺序存储：通常借助程序设计语言的数组描述。(2)链接存储：通常借助丁•程序语言的指针来描述。(3)索引存

3、储：索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的纽合。(4)散列存储：该方法的基木思想是:根据元素的关键字虚接计算出该元素的存储地址。5•算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束;确定性，每-•条指令的含义都明确；可行性，算法是可行的。算法与程序的区别：程丿芋必须依赖尸计算机程序语言，而一个算法对用自然语言、计算机程序语言.数学语言或约定的符号语言來描述。H前常用的描述算法语言有两类：类Pascal和类C。6•评价算法的优劣：算法的〃正确性

4、〃是首先耍考虑的。此外，主耍考虑如下三点：①执行算法所耗费的时间，即时间复杂性；②'执行算法所耗费的存储空间，主耍是辅助空间，即空间复杂性；③算法应易于理解.易于编程，易于调试等,即可读性和可操作性。以上几点最主要的是时间复杂性,时间复朵度常川渐进时间复朵度表示。7.算法求解问题的输入量称为问题的规模,用一个正鉴数n表示。&常见的时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(log2n).线性阶0(n).线性对数阶0(nlog2n)、平方阶0(“立方阶0亦)、…、k次方阶0(nk).指数阶0⑵)和阶乘阶0(n!)o9

5、•一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数，它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。第二章线性表1.数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。2•只要确定了线性表存储的起始位置，线性表中任意一个元索都可随机存取，所以顺序表是一种随机存取结构。3•常见的线性表的基本运算：(1)置空表TnitList(L)构造一个空的线性表L。(2)求表长ListLength(L)求线性表L中的结点个数，即求表长。(3)G

6、etNode(L,i)取线性表L中的第i个元素。(4)LocateNode(L,x)在L中查找第一个值为X的元素，并返回该元素在L中的位置。若L中没有元秦的值为x,则返回0值。(5)TnsertList(L,i,x)在线性表L的第i个元索Z前插入一个值为x的新元素，表L的长度加1。(6)DeleteList(L,i)删除线性表L的第i个元素，删除后表L的长度减1。4•顺序存储方法：把线性表的数据元索按逻辑次序依次存放奋一组地址连续的存储单元里的方法。顺序表(Sequentici1List)：用顺序存储方法存储的线性衣称为顺序农。顺

7、序表是-种随机存取结构，顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。5•顺序表上实现的基本运算：(1)插入：该算法的平均时间复杂度是0(n),即在顺序表上进行插入运算，平均要移动一半结点(n/2)o(2)删除：顺序表上做删除运算，平均要移动表中约一半的结点(n-1)/2,平均时间复杂度也是0(n)。6.采用链式存储结构可以避免频繁移动人量元素。一个单链表可山头指针唯一确定，因此单链表可以用头指针的名字來命名。①生成结点变量的标准函数p=(ListNode*)mal1oc(sizeof(ListNode))；〃函数mtilloc

8、分配-个类型为ListNode的结点变量的空间，并将其首地址放入指针变量P中②释放结点变量空间的标准函数free(p)；//释放p所指的结点变量空间③结点分量的访问方法二：p~>data和p->next④指针变量P和结点变量*戸的关系：指针变量P的