试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容

数据结构复习笔记作者: 网络转载发布日期: 无数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具 有独立含义的最小标识单位。如整数这个集合中，10 这个数就可称是一个数据元素.又比如 在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段 就是一个数据项。数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和 对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每 个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据 结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的 是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前 趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一 个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机 语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在 一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言 的层次上讨论存储结构。)第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除 记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除 这些算术运算了，在数据结构中，这些运算常常涉及算法问题。弄清了以上三个问题，就可以弄清数据结构这个概念。通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和 非线性结构 (这两个很容易理解)数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。 首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时 间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算 法时间复杂度的数量级。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算 法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度, 其中的f(n)一般是算法中频度最大的语句频度。此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但 是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。常见的时间复杂度，按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)、线性 阶0(n)、线性对数阶O(nlog2n)、平方阶0(2)、立方阶0(3)、k次方阶0(k)、指数阶 O(2An)o时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结 构、非线性结构。数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、 记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容: 数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一 个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性 表就是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前 趋和直接后继。1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成 的表。这个表就是一个数据结构。每个记录（有姓名，学号，成绩等字段）就是一个结点，对 于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记录），其 他的结点则各有一个也只有一个直接前趋和直接后继 （它的前面和后面均有且只有一个记 录）。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢 ? 用高级语言如何表示各结点之间 的关系呢? 是用一片连续的内存单元来存放这些记录 （如用数组表示）还是随机存放各结点 数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个 问题的。（所以各位赶快学C语言吧）。最后，我们有了这个表（数据结构），肯定要用它，那么就是要对这张表中的记录进行查 询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算 问题了。1.3 常用的存储表示方法有哪几种? 常用的存储表示方法有四种: 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的 逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是 由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。1.4 设三个函数 f,g,h 分别为f(n)=1003+2+1000 , g(n)=253+50002 ,h(n)=1.5+5000nlgn请判断下列关系是否成立：(1) f(n)=O(g(n)(2) g(n)=O(f(n)(3) h(n)=O(nA1.5)(4) h(n)=O(nlgn) (1)成立。这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n),这里的O是数学符号，它的 严格定义是若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的 常数C和n0，使得当n三nO时都满足0WT(n)WC f(n)。用容易理解的话说就是这两个函数 当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算 了吧。第(1)题中两个函数的最高次项都是3，因此当n8时，两个函数的比值是一个常数, 所以这个关系式是成立的。 (2)成立。 (3)成立。 (4)不成立。1.5设有两个算法在同一机器上运行，其执行时间分别为100nA2和2An，要使前者快于后者， n 至少要多大? 15最简单最笨的办法就是拿自然数去代呗。假定n取为10,则前者的值是10000,后者的 值是1024,小于前者，那我们就加个5，用15代入得前者为22500，后者为32768，已经比 前者大但相差不多，那我们再减个1，用14代入得，前者为19600,后者为16384，又比前者 小了，所以结果得出来就是n至少要是15.1.6设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。1.6设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0while(i k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 这个函数是按线性阶递增的(2) i=0; k=0;dok=k+10*i; i+;while(i T(n)=nT(n)=O(n) 这也是线性阶递增的(3) i=1; j=0;while(i+j1while (x=(y+1)*(y+1)y+; T(n)=n1/2 T(n)=O(n1/2)最坏的情况是y=0,那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(5) x=91; y=100;while(y0)if(x100)x=x-10;y-;else x+; T(n)=O(1)这个程序看起来有点吓人，总共循环运行了 1000次，但是我们看到n没有？没。这段程 序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。1.7 算法的时间复杂度仅与问题的规模相关吗？ No,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相 关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复 杂度时，一般就是以最坏情况下的时间复杂度为准的。1.8按增长率由小至大的顺序排列下列各函数：2人100, (2/3)An，(3/2)An， nAn , , n!，2An， lgn ,nAlgn, nA(3/2)分析如下:2A100是常数阶；(2/3)An和(3/2)An是指数阶,其中前者是随n的增大而减小 的；n是指数方阶；Vn是方根阶,n!就是n(n-1)(n-2).就相当于n次方阶；2人口是指 数阶，lgn是对数阶,nAlgn是对数方阶,(3/2)是3/2次方阶。根据以上分析按增长率由小至 大的顺序可排列如下： (2/3)An 2A100 lgn V n nA(3/2) nAlgn (3/2)An 2An n! next-next 和 rear, 查找时间都是 O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。(答案及点评)2.5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道 头指针，能否将结点*卩从相应的链表中删去?若可以，其时间复杂度各为多少？2.5 答：我们分别讨论三种链表的情况。1. 单链表。当我们知道指针 p 指向某结点时，能够根据该指针找到其直接后继，但是由于 不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直 接后继，从而可以删除该结点。其时间复杂度为0(1)。3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又 因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结 点。其时间复杂度应为0(n)。(答案及点评) 2.6 下述算法的功能是什么?LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,*P;if(L&L-next) Q=L;L=L-next;P=L; while (P-next) P=P-next;P-next=Q; Q-next=NULL;return L;/ Demo 第三章：栈和队列(包括习题与答案及要点)转摘 www.E本章介绍的是栈和队列的逻辑结构定义及在两种存储结构 (顺序存储结构和链式存储结构 ) 上如何实现栈和队列的基本运算。本章的重点是掌握栈和队列在两种存储结构上实现的基本 运算，难点是循环队列中对边界条件的处理。1.栈的逻辑结构、存储结构及其相关算法(综合应用): 栈的逻辑结构和我们先前学过的线性表相同，如果它是非空的，则有且只有一个开始结点， 有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后 继)，但是栈的运算规则与线性表相比有更多的限制，栈(Stack )是仅限制在表的一端进行插入 和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为 空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out). 栈的基本运算有六种：构造空栈：InitStack(S)、判栈空: StackEmpty(S)、判栈满： StackFull(S)、进栈：Push(S,x)、可形象地理解为压入，这时栈中会多一个元素退栈： Pop(S) 、 可形象地理解为弹出，弹出后栈中就无此元素了。取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。我们要了解的是，在顺序栈中有上溢和下溢的概念。顺序栈好比一个盒子，我们在里头 放了一叠书，当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明小)，那么 当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算，哼哼)，这时就是 上溢,上溢也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我 们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是下溢。 下溢本身可以 表示栈为空栈,因此可以用它来作为控制转移的条件。链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环 (结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加 了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头 指针就可以了。以上两种存储结构的栈的基本操作算法是不同的，我们主要要学会进栈和退栈的基本算法以 解决简单的应用问题。2.队列的逻辑结构、存储结构及其相关算法(综合应用)。队列(Queue,念Q音)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制, 插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除 的一端称为队尾(rear)，允许插入的一端称为队头(Front)，队列的操作原则是先进先出的， 所以队列又称作FIFO表(First In First Out)队列的基本运算也有六种：置空队 ： InitQueue(Q)判队空： QueueEmpty(Q)判队满： QueueFull(Q)入队 ： EnQueue(Q,x)出队 ： DeQueue(Q)取队头元素：QueueFront（Q）,不同与出队，队头元素仍然保留队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。 对于顺序队列，我们要理解假上溢的现象。我们现实中的队列比如人群排队买票，队伍中的人是可以一边进去从另一头出来的，除非地 方不够，总不会有溢出的现象，相似地，当队列中元素完全充满这个向量空间时，再入队 自然就会上溢，如果队列中已没有元素，那么再要出队也会下溢。那么假上溢就是怎么回事呢?因为在这里，我们的队列是存储在一个向量空间里，在这一段连续的存储空间中，由一个队 列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也 就是说，队列是由两个指针中间的元素构成的。在队列中，入队和出队并不是象现实中，元 素一个个地向前移动，走完了就没有了,而是指针在移动，当出队操作时，头指针向前（即向 量空间的尾部）增加一个位置，入队时，尾指针向前增加一个位置，在某种情况下，比如说 进一个出一个，两个指针就不停地向前移动，直到队列所在向量空间的尾部，这时再入队的 话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列也是空的，却 产生了上溢现象，这就是假上溢。为了克服这种现象造成的空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来， 形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界（尾部）时， 再加1的操作（入队或出队）就使指针指向向量的下界，也就是从头开始。这时的队列就称循 环队列。通常我们应用的大都是循环队列。由于循环的原因，光看头尾指针重叠在一起我们并不能判 断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。方法至少 有三种，一种是另设一个布尔变量来判断（就是请别人看着，是空还是满由他说了算），第二 种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就 算队已满，不许入队。第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时 知道队列的长度了，只要队列中的元素个数等于向量空间的长度，就是队满。 以上是顺序队列，我们要掌握相应算法以解决简单应用问题。队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾 进行插入（入队）的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针 唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只 有一个结点时，出队后要同进修改头尾指针并使队列变空。3.栈和队列的应用（领会） 教材中举了几个例子，对于我们初学者来说，看上去比较繁，我们只要掌握一点，那就是 对于什么情况下用栈和队列作为解决问题的数据结构。判断的要点就是：如果这个问题满足后进先出（LIFO）的原则，就可以使用栈来处理。如果这 个问题满足先进先出（FIFO）的原则，就可以使用队列来处理。比如简单的说，有一个数组序列，我们输入时按顺序输入，但是输出时需要逆序输出，那么 它就可以利用栈来处理，把这个数组存入一个栈中就可以容易地按逆序输出结果了。 第三章 线性表习题及答案 一、基础知识题(答案及点评) 3.1 设将整数 1，2，3，4 依次进栈，但只要出栈时栈非空，则可将出栈操作 按任何次序夹入其中，请回答下述问题：(1) 若入、出栈次序为 Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ), 则出栈的数 字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)？(2) 能否得到出栈序列 1423 和 1432?并说明为什么不能得到或者如何得到。(3) 请分析 1， 2 ， 3 ， 4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。(答案及点评) 3.2 链栈中为何不设置头结点？ 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于 要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。(答案及点评) 3.3 循环队列的优点是什么？ 如何判别它的空和满？3.3 答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量 空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是 通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。 每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数 器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。(答案及点评) 3.4 设长度为 n 的链队用单循环链表表示，若设头指针，则入队出队操作的时 间为何？ 若只设尾指针呢？3.4答：当只设头指针时，出队的时间为1,而入队的时间需要n因为每次入队均需从头指 针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。 因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整 个队列。第四章：串(包括习题与答案及要点)转摘 www.E本章介绍了串的逻辑结构，存储结构及串上的基本运算，由于在高级语言中已经提供了较全 善的串处理功能，因此本章的重点是掌握在串上实现的模式匹配算法。同时这也是本章的难 点。但是从全书来讲，这属于较简单的一章内容。1.串及其运算（领会）（这些内容比较容易理解，不用死记） 串就是字符串，是一种特殊的线性表，它的每个结点仅由一个字符组成。 空串：是指长度为零的串，也就是串中不包含任何字符（结点）。 空白串：指串中包含一个或多个空格字符的串。不同与空串，它的结点就是一个空格字符。1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表 这个表就是一个数据结构。每个记录就是一个结点，对于整个表来说，只有一个开始结点和 一个终端结点，其他的结点则各有一个也只有一个直接前趋和直接后继。这几个关系就确定 了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到里呢 ? 用高级语言如何表示各结点之间的关系呢 ? 是用一片连续的内存单元来存放这些记录还是随机存放各结点数据再用指针进行链接呢 ? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的 。最后，我们有了这个表，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除 等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。