《数据结构知识点总结》由会员分享，可在线阅读，更多相关《数据结构知识点总结（72页珍藏版）》请在金锄头文库上搜索。
1、第一章 概述一、概念： 1学科：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系和操作等等.2概念：由某一数据对象及该对象中所有数据成员之间的关系组成.具体来说, 数据结构包含三个方面的内容, 即数据的逻辑结构, 数据的存储结构和对数据所 施加的运算.3这三个方面的关系为：1) 数据的逻辑结构独立于计算机,是数据本身所固有的.2) 存储结构也称为物理结构,是逻辑结构在计算机存储器中的映像,必须 依赖于计算机.3) 运算是指所施加的一组操作总称.运算的定义直接依赖于逻辑结构,但 运算的实现必依赖于存贮结构.4数据( data) :信息的载体,指能够输入到计算机中,
2、并被计算机识别和处理 的符号的集合.例如：数字、字母、汉字、图形、图像、声音都称为数据. 5数据元素( data elemen)t ：数据元素是组成数据的根本单位. 数据元素是一个数据整体中相对独立的单位. 但它还可以分割成假设干个具有不同属性的项字段,故不是组成数据的最小单位.6 逻辑结构：从解决问题的需要出发,为实现必要的功能所建立的数据结构, 它属于用户的视图,是面向对象的.7.物理结构：指数据该如何在计算机中存放,是数据逻辑结构的物理存储方式, 是属于具体实现的视图,是面向计算机的.8 逻辑结构与存储结构二者关系：物理结构是逻辑结构的存储映象.任何一个算法的设计取决于选定的数据逻辑结构
3、,而算法的实现依赖于采用的存储结构.9从逻辑结构划分数据结构：线性结构和非线性结构树、图10. 线性结构：1元素之间为一对一的线性关系2第一个元素无直接前驱3最后一个元素无直接后继4其余元素都有一个直接前驱和直接后继.11. 非线性结构1元素之间为一对多或多对多的非线性关系2每个元素有多个直接前驱或多个直接后继12 顺序存储：数据元素存储方法：所有元素存放在一片连续的存贮单元中. 数据元素之间关系表示：逻辑上有相邻关系的元素存放到计算机内存仍然相邻, 即存储位置表达了数据元素之间的关系.#01且L01aL弘弘a3a3a 1 ast066 MAXSIZE-lMAXSIZE-lL. dataL-d
4、ata(a)413链式存贮数据元素存储方法：元素可以存放在不连续的存贮单元中.数据元素之间关系表示：逻辑上相邻的元素存放到计算机内存后不一定是相邻 的,因此元素之间的关系通过地址确定.bcateatmat14.算法：一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序 列.特性：输入有0个或多个输入输出有一个或多个输出处理结果 确定性每步定义都是确切、无歧义的 有穷性算法应在执行有穷步后结束 可行性每一条运算应可通过已经实现的根本运算执行有限次来实现 算法的含义与程序十分相似,但二者是有区别的.一个程序不一定满足有穷性死 循环,另外,程序中的指令必须是机器可执行的, 而算法中的指令那么
5、无此限制. 一个算法假设用计算机语言来书写,那么它就可以是一个程序.15算法的分析与度量：1算法的性能标准： 正确性：正确执行的功能和性能要求. 可使用性：算法能够很方便的使用. 可读性：便于理解、测试和修改算法. 效率：计算机资源的消耗,包括存储和运行时间. 健壮性：检错、报错及纠错的功能.2算法的事前估计：空间复杂度和时间复杂度3算法的后期测试：在算法中的某些部位插装时间函数time ,测定算法完成某一功能所花费的时间.16时间复杂度：一个算法执行所消耗的时间,从理论上是不能算出来的,必须 上机运行测试才能知道. 但我们不可能也没有必要对每个算法都上机测试, 只需 知道哪个算法花费的时间多
6、, 哪个算法花费的时间少就可以了. 并且一个算法花 费的时间与算法中语句的执行次数成正比例, 哪个算法中语句执行次数多, 它花 费时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记作T(n)=0(f(n):表示算法中根本运算次数 T(n)是问题规模n的某个函数f(n)1)求以下算法段的语句频度 for(i=1; i=n; i+)for(j =1; j =i ; j+) x=x+1;n(n 1)时间频度T(n)=1+2+3+n=2T (n)与n2数量级相同,因此它的时间复杂度为O(n2).2)例分析以下算法段的时间频度及时间复杂度for (i=1;i=n ;i+ )for (j=1;j
7、=i;j+)for ( k=1;k0时称为非 空表.通常将非空的线性表记为(a1, a2,an),其中的数据元素ai (K i n)是一 个抽象的符号, 其具体含义在不同情况下是不同的, 即它的数据类型可以根据具 体情况而定.2. 线性表中数据元素的关系： 元素之间为一对一的线性关系.有且仅有一个开始结点 (表头结点 )a1 ,它没有直接前驱,只有一个直接后继 ; 有且仅有一个终端结点(表尾结点)an,它没有直接后继,只有一个直接前驱； 其它结点都有一个直接前驱和直接后继；3. 线性表的顺序存储结构 ,也称为顺序表. 在内存中开辟一片连续存储空间, 但该连续存储空间的大小要大于或等于顺序表 的
8、长度.然后让线性表中第一个元素存放在连续存储空间第一个位置, 第二个元素紧跟着第一个之后,其余依此类推.4假设线性表中元素为(al, a2,.,an)设第一个元素al的内存地址为L0C(a1),每个元素在计算机内占 那么第i个元素ai的地址为L0C(ai)=L0C(a1)+(i-1) x d骨口. 序号内容骨口. 序号内容001a11a12a22a23a33a3i-1ai-1i-1ai-1iaiixi+1ai+1i+1ainannan-1anmaxsize-1maxsize-1d个存储单元(其中 1 i n).5.插入元素void ListI nsert_sq(Sqlist &L,i nt i
9、, i nt e) int *p,*q;if(iL.le ngth +1) return;q=&L.elemi-1;插入位置for(p=&L.elemL.length -1;p=q;-p ) *(p+1)=*p;*q=e;+L .len gth ; return;#插入前插入后序号内容序号内容001ai1a12a?2a23a33a3i-1a-1i-1ai-1iaiai+1i+1a+1i+1ai+2nn-1an11maxsize-1maxsize-16删除元素 void ListDel_sq(Sqlist &L,int i, int &e)if(iL.length) return; e=L.el
10、emi-1;for(int j=i;jla21 4 (b)带头結点的单链表环带头结点和帝头結点的单储表头指针W150|11(：qi eK. jfH.1201304O150160rc180a；180roNULL11035140130dara 域 next 域巧 I -I_7矶| V_仙 | 斗川 | T15单狂表比逻辑表示删除结点的指针修改10单链表上的插入运算p_uTi-B(b-rn可 建立新的数据结点. 找到插入位置前的结点 改变指针指向.插入结点时的指针修改11 单链表上的删除运算找到删除结点前一个结点(这 就要求有两个指针)改变指针指向释放结点空间删除结点的拒针修改12栈(stack)是
11、限制线性表中元素的插入和删除只能在线性表的同一端进行的一#出栈进栈栈顶栈底(queue).允许种特殊线性表.允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom).13第1个进栈的元素在栈底 最后一个进栈的元素在栈顶 第1个出栈的元素为栈顶元素 最后一个出栈的元素为栈底元素栈是一种后进先出(Last In First Out)的线性表,简 称为LIFO表.根据栈的定义可知,最先放入栈中元素在栈底,最后 放入的元素在栈顶,而删除元素刚好相反,最后放入 的元素最先删除,最先放入的元素最后删除.13仅允许在一端进行插入,另一端进行删除的线性表,称为队列 插入的一端称为队尾rear,允许删除的一端称为队头frort.队列是一种先进先出First In First Out的特殊线性表,或称FIFO表. 假设队列中没有任何元素,那么称为空队列,否那么称为非空队列.出队引 幻v入队-1I队头队尾14 表尾称作队尾,表头称为队头； al为
