《数据结构复习内容讲解》由会员分享，可在线阅读，更多相关《数据结构复习内容讲解（33页珍藏版）》请在金锄头文库上搜索。
1、数据结构细补班材料1、时间复杂度的计算和一些基本概念什么是数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D, S）D：元素有限集 还分成数值类型和非数值类型S：关系有限集数据(data)所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。数据元素(data element)是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Data item)构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。逻辑结构数据元素之间的逻辑关系。即从逻辑关系上描述数据，它
2、与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：集合结构： 仅同属一个集合线性结构: 一对一（1:1) 线性树 结 构: 一对多（1:n) 非线性图结构: 多对多 (m:n) 非线性物理结构物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序存储结构链式存储结构索引存储结构散列存储结构数据的运算数据的运算是在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序抽象数据类型抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的操
3、作。算法算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。算法有5个基本特性：有穷性、确定性、可行性、输入和输出算法评价有4个指标：运行时间、占用空间、正确性和简单性评价指标中的运行时间，就是用时间复杂度来衡量的。时间复杂度表现形式：O(f(n)渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n n0 ，有 f(n) Cg(n)，则f(n) = O(g(n) l 3n+2=O(n) /* 3n+24n for n2 */l 3n+3=O(n) /* 3n+34n for n3 */l 100n+6=O(n) /* 100n+6101n for n10
4、 */l 10n2+4n+2=O(n2) /* 10n2+4n+211n2 for n5 */l 6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n4 */常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。1、设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn请判断下列关系是
5、否成立：（1） f(n)=O(g(n)（2） g(n)=O(f(n)（3） h(n)=O(n1.5)（4） h(n)=O(nlgn) (1)成立。题中由于两个函数的最高次项都是n3,因此当n时，两个函数的比值是 一个常数，所以这个关系式是成立的。 （2）成立。与上同理。 （3）成立。与上同理。 （4）不成立。由于当n时n1.5比nlgn递增的快，所以h(n)与nlgn的比值不是常数，故不成立。2、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0while(i1while (x=(y+1)*(y+1)y+;解答：T(n)=n1/2 ，T(n)=O(n1/
6、2)，最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(3) x=91; y=100;while(y0)if(x100)x=x-10;y-;else x+;解答： T(n)=O(1)， 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。2、线性结构逻辑结构：1.描述: 线性表是由n (n=0)个数据元素(结点)a1,a2,.,ai,.,an组成的有限序列。其中，数据元素的个数n定义为表长。当n=0时称为空表，非空的线性表(n0)记为： (a1,a2,.,a
7、i,.,an)注意: 1.数据元素ai是一个抽象的符号 2. ai可取各种数据类型 3. 一般情况下,同一线性表中的元素具有相同的数据类型 4. i是元素的序号 (1=i=n) 2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继线性表的运算：线性表的常见基本运算包括：置空表SETNULL(L)建表CREATLIST(L)求表长LENGTH(L)取结点GET(L,i)定位LOCATE(L,x)插入INSERT(L,x,i)删除DELETE(L,i)顺序存储的线性结构（顺序表）顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。顺序表：
8、采用顺序存储方法存储的线性表称顺序表。由n个数据元素a1、a2、.an组成的有限序列，称为顺序表存储地址的计算：由于顺序表采用的是顺序存储方法，因此表中的任一结点的存储地址可按下式计算： LOC(ai)=LOC(a1)+(i-1)*c 1=i=n这里：LOC(a1)为结点a1的存储起址，c为每个结点所占存储单元数。 顺序表是一种随机存取结构在c语言中，顺序表用一维数组描述： typedef int datetype; #define maxsize 1024; typedef struct datatype datamaxsize; int last; sequenlist; 顺序表上的基本运
9、算（实现）SETNULL（L）： (*l).last = -1LENGTH(L): (*l).last+1GET(L,i): (*l).datai-11. LOCATE(L,x)算法思想:将x和线性表中的每一个数据元素比较,若相等,返回比较结点的序号,比较至表尾,没有等于x的节点,则返回0.int LOCATE(sequenlist *l,datatype x) int i=0; while(i=(*l).last) if(x=(*l).datai) return(i+1); i +; return(0);最好情况下: T(n)=1最坏情况下: T(n)=n2.插入INSERT(L,x,i)所
10、做工作: 判断是否可插入,从表空间上考虑 判断插入位置是否合法 结点后移 将x插入第i个位置 终端结点下标加13. 删除DELETE(L,i)所作工作: 判断删除位置是否合法:(i(*L).last+1) 结点前移for(j=i;jdata=ch; if(head=NULL) head=s else r-next=s; r=s; ch=getchar( ); if (r!=NULL) r-next=NULL; return head;优点：链表中结点次序和输入次序相同缺点：空表和非空表处理不同 开始结点和其余结点的处理不同解决办法：引入头结点，统一空表和非空表、开始结点和其余结点的处理，简化算法的实现while (ch!=$) s=malloc(sizeof(linklist)
