《数据结构全部(2013年5月)打印有答案版本》由会员分享，可在线阅读，更多相关《数据结构全部(2013年5月)打印有答案版本（38页珍藏版）》请在金锄头文库上搜索。
1、数据结构适用班级：软件设计师主讲：张 红网址：E-Mail:分值说明：早上考 8-12分, 下午考 15-30分比特培训中心贵州贵阳课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心()1第一节序论1.1 什么是数据?所有能输入到计算机中并能够被计算机程序处理的符号的总称.它是计算机程序加工的原料.1.2 什么是数据元素?数据的基本单位,在计算机程序中通常作为一个整体来进行考虑和处理.如数组中一个存储单元里面的数或者链表中一个结点.1.3什么是数据结构?是数据元素相互之间存在的一种或多种特定关系的集合.主要研究数据逻辑结构和存储结构及其运算的实现，数据结构的种类:集合：结构中的数据元素之
2、间除了“同属于一个集合”的关系外，别无其它关系。 线性结构：结构中的数据元素之间存在一个对一个的关系树形结构：结构中的数据元素之间存在一个对多个的关系图：状结构或网状结构 结构中的数据元素之间存在多对多的关系1.4 数据的逻辑结构结构定义中的“关系” 描述的是数据元素之间的逻辑关系,又称为逻辑结构.比如平常教学中所画的内存图,数组等为数据的逻辑结构.1.5 数据的物理结构数据结构在计算机中的实际表示形式称为数据的物理结构,又称为物理存储.1.6 算法和算法分析1.6.1 什么是算法？对待定问题求解步骤的一定描述，它是指令的有限序列，其中每一条指令表示一个或多个步骤。为解决某问题的算法与为该问题
3、编写的程序含义是相同的。1.6.2算法的五个特性？有穷性：算法必须在执行有穷步之后结束。确定性：算法中每一条指令必须有确切的含义，读者在理解时不会产生二义性，并且在相同条件下，相同的输入只能得到相同的输出。可行性：算法能把问题真正的解决。 输入：一个算法有零个或多个输入输出：一个算法有一个或多个输出例（2002 年）算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有_(11)_特性。 (11) A. 正确性 B. 确定性 C. 能行性 D. 健壮性1.6.3 算法设计的要求正确性：算法应当满足具体问题的需求可读性
4、：算法应该能让人读懂，能被计算机运行。健壮性：算法应该具有容错处理能力，不容易被击垮。高效率与低存储量要求：效率指程序的执行时间（越短越好） ，算法要占用计算机一定的存储量（越小越好） 。1.6.4算法效率的度量时间复杂度从运行时间上度量，使用大 O记法假如一个程序的实际执行时间为 T（n）= 2n 3+n2+5，则 T（n）=O（n 3）.常见的时间复杂度有：空间复杂度一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。1.固定空间 2.可变空间第二节.线性表线性表是由相同数据类型的结点组成的有限序列。如数组、链表（单链表、双链表、循环单链表，循环双链表） 、栈、队列,双端队列等。数组
5、：int a5=1,2,3,4,5;a0 a1 a2 a3 a41 2 3 4 5单链表课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心()2单循环链表双向循环链表使用头结点的好处:不管链表是否为空，头结点都不为空，这使得对链表的各种操作(查找和修改)得到统一.2.1线性表的存储 (1)顺序存储 用地址连续的数据结构如数组来存储线性表。优点：能随机存取线性表中的任何结点。缺点：数组的大小通常是固定的，不利于任意增加或减少线性表的个数；插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。(2)链接存储用链表存储线性表(链表)，最简单的是单向链表。优点：表的每个结点的实际存储位置是
6、任意的，这给线性表的插入和删除带来方便，只要改变链表有关结点的后继指针就能完成插入或删除的操作，不需移动任何表元。缺点：每个结点增加了一个后继指针成分，要化费更多的存储空间；不方便随机访问线性表的任一结点。2.2 线性表的主要基本运算2.2.1查找运算在线性表查找具有给定键值的结点。算法有顺序查找、分块查找、 二分查找、 散列查找等，其中 二分查找要求线性表是一个有序序列。 注意：在链式存储的情况下，只能用顺序查找算法。2.2.2 插入运算在线性表的第 i(0inI)个结点的前面或后面插入一个新结点。分顺序存储和链式存储两种情况：顺序存储的情况下检查插入要求的有关参数的合理性把原来的第 n-1
7、个结点至第 i个结点依次往后移动一个数组元素位置修改线性表的结点个数 在具有 n个结点的线性表中插入新结点，其时间主要花费在移动结点的循环上，若插入任一位置的概率相等，则在顺序存储性表中插入一个新结点，平均移动次数为 n 2。链式存储的情况下 在链接存储线性表中插入一个键值为 x的新结点，分以下 4种情况：1. 在某指针 p所指结点之后插入；2. 插在首结点之前，使待插入结点成为新的首结点；3. 接在线性表的末尾；4. 在有序链表中插入，使新的线性表仍然有序。2.2.3删除运算删除线性表的第 i(Oin 一 1)个结点。也是分为顺序存储和链接储存两种情况。 （1）顺序存储在有 n个结点的线性表
8、中，删除第 i(Oin1)个结点。删除时应将第 i+1个表元至第 n1个结点依次向前移一个数组元素位置，共移动 n-i-1个结点。完成删除主要有以下几个步骤：检查删除要求的有关参数的合理性； 把原来第 i+1个表元至第 n-1个结点依次向前移一个数组元素位置； 修改线性表元素的个数。课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心()3在具有 n个结点的线性表中删除新结点，其时间主要花费在移动结点的循环上，若删除任一位置的概率相等，则在顺序存储性表中删除一个结点，平均移动次数为（ n 1） 2。（2）链接存储在链表上删除指定值的结点，需考虑几种情况：一是当链表为空链表，不执行删除操作；
9、如果要删除的结点恰为链表的首结点，应将其他情况，先要在链表中查找要删除的结点，从链表首结点开始顺序查找。若找到，执行删除操作，结点个数减 1，若直至链表末尾未找到指定值的结点，则不实行删除操作。2.3 栈 栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端称为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以 栈具有后进先出的特征。两种形式存储栈：（1）顺序存储用顺序存储线性表来表示栈（用数组实现） ，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量 top指出栈顶结点在数组中的下标。（2）链接存储栈栈也可以用
10、链表来实现，用链表实现的栈称为链接栈，简称链栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针 top,top为空的链表为空栈。栈的应用: 数制转换、括号匹配的检验、行编辑程序、迷宫求解、表达式求值2005年下半年：若 push、pop 分别表示入栈、出栈操作，初始栈为空且元素 1、2、3 依次进栈，则经过操作序列push、push、pop、pop、push、pop 之后，得到的出栈序列为_(29)_。(29)A.321 B.213 C.231 D.123可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符“(”就将其入栈，遇到“)”就执行出栈
11、操作。对算术表达式“(a+b*(a+b)/c)+(a+b)”,检查时，_(33)_；对算术表达式“(a+b/(a+b)-c/a)/b”,检查时，_(34)_。这两种情况都表明所检查的算术表达式括号不匹配。(33)A.栈为空却要进行出栈操作 B.栈已满却要进行入栈操作C.表达式处理已结束，栈中仍留下有字符“(” D.表达式处理已结束，栈中仍留下有字符“)”(34)A.栈为空却要进行出栈操作 B.栈已满却要进行入栈操作C.表达式处理已结束，栈中仍留下有字符“(” D.表达式处理已结束，栈中仍留下有字符“)”逆波兰式：是一种算术表达式的另一种表示，也称为后缀表示，定义为把运算符放在两个运算对象的后面
12、。中缀算术表达式转换成对应的后缀算术表达式：把每个运算符都移到运算对象的后面，然后去掉括号即可。例题：表达式采用逆波兰式表示时可以不用括号，而且可以用基于_1_的求值过程进行计算，与逆波兰式 ab+cd+*对应的中缀表达式为：_2_课程：数据结构 主讲：张 红 版权所有：贵大比特培训中心()41A.栈 B.队列 C.符号表 D.散列表 2Aa+b+c*d B.(a+b)*c+d C.(a+b)*(c+d) D.a+b*c+d（2005 年上半年）表达式 a*(b+c)-d的后缀表达形式为_.(39) A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd2.3 队列队列
13、也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运算的一端称为队尾。称队列的结点插入为进队，结点删除为出队。因最先进入队列的结点将最先出队，所以 队列具有先进先出的特征。同栈一样，队列也有两种存储方式：（1）顺序存储可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量 head(称为队头指针)，为了指明当前执行进队运算的队尾位置，也需要一个指针变量 tail(称为尾指针)。若用有 N个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况
14、。一种可行的解决办法是当发生这样的情况时，把队列中的结点移到数组的前端，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。循环队列就是将实现队列的数组 a的第一个元素 a0与最后一个元素 an-1连接起来。队空的初态为 head=tail=O。在循环队列中，当 tail赶上 head时，队列满。反之，当head赶上 tail时，队列变为空。这样队空和队满的条件都同为 head=tail，这会给程序判别队空或队满带来不便。因此，可采用当队列只剩下一个空闲结点的空间时，就认为队列已满，用这种简单办法来区别队空和队满。即队空的判别条件是 head=tail，队满的判别条件是 head=(tai
15、l+1) mod n。循环链表的操作算法如下：#define MAXSIZE 100typedef structint *base;int front;int rear;SqQueue;int InitQueue(SqQueue &Q)Q.base = (int *)malloc(MAXSIZE*sizeof(int);if(!Q.base)exit(); /Q.base=nullQ.front = Q.rear = 0;return 1;int QueueLength(SqQueue &Q)return (Q.rear-Q.front+ MAXSIZE)mod MAXSIZE;int EnQueue(SqQueue &Q, int e)if(Q.rear+1)mod
