资源描述：
《数据结构导论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、微软中国数据结构导论[键入文档副标题]微软用户2009[键入公司地址]目录第一章概论第二章线性表第三章栈和队列第四章串第五章多维数组第六章树第七章图第八章排序第九章查找第一章概论1.数据：信息的载体,能被计算机识别、存储和加工处理。2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3.数据结构：数据之间的相互关系，即数据的组织形式。它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数
2、据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。7.抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。8.数据的逻辑结构，简称为数据结构，
3、有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。（2）非线性结构，一个结点可能有多个直接前趋和后继。9.数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2）链接存储，结点间的逻辑关系由附加指针字段表示。3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4）散列存储，按结点的关键字直接计算出存储地址。10.评价算法的质量：○1正确性；算法应能正确地事先预定的功能。○2易读性；算法应易于阅读和理解，以便于调试和扩充。○3健
4、壮性；当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。○4高效率；即达到所需的时间和空间性能。11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2ⁿ)、线性阶O(n)、线性对数阶O(nlog2ⁿ)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。12.算法的特征：有穷性；确定性
5、；可行性；输入；输出。13.决定算法运行时间的因素：（1）问题的规模；（2）编译时间；（3）指令执行速度；（4）重复执行指令的速度。第二章线性表1.线性表：是由n(n≥0)个数据元素组成的有穷序列。2.线性表的基本运算有：1）Initiate(L),加工型运算，作用是构造空表，即表的初始化；2）Length(L),引用型运算，其结果是表的结点个数，即表长；3）Get(L,i),引用型运算，若1≤i≤Length(L)，其结果是表中的第i个结点；否则，为一特殊值。4）Locate(L,x)，引用型运算，查找L中值为x的结点
6、并返回结点在L中的位置，若有多个x则返回首个；否则返回特殊值表示查找失败。5）Insert(L,x,i)，加工型运算，在表的第i个位置插入值为x的新结点，要求1≤i≤Length(L)+1；6）Delete(L,i)，加工型运算，删除表的第i个位置的结点，要求1≤i≤Length(L)；3.顺序表：是线性表的顺序存储结构，即按顺序存储方式构造的线性表的存储结构。4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1≤i≤n（其中Loc(a1)是顺序表的第一个结点，C每个变量占用的内存单元）。
7、5.顺序表上的基本运算（1）插入Voidinsert_sqlist(sqlistL,datatypex,inti)/*将X插入到顺序表L的第i-1个位置*/{if(L.last==maxsize)error(“overflow”);/*溢出*/if((i<1)
8、
9、(i>L.last+1))error(“positionerror”);/*非法位置*/for(j=L.last;j=i;j--)L.data[j]=L.data[j-1];/*结点依次后移*/L.data[i-1]=x;/*置入X*/L.last=L.last
10、+1/*修改表长*/}在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。（2）删除Voiddelete_sqlist(sqlistL,inti);/*删除顺序表L中的第i个位置上的结点*/{if((i<1)
11、
12、(i>L.last))error(“positionerror”)；/*非法位置*/for
