09地科数据结构总复习指导1

数据结构复习备考指南下面列出的只作为复习重点，并非是考试题，可能是考试相关知识点的罗列；总则：认真复习每一次实验报告当中的内容，认真复习作业当中的内容；认真复习上课讲解的重要内容与课件；认真复习所上章节当中每个知识的基本概念；第一章***1：数据结构的概念，数据的逻辑结构和物理结构的联系与区别数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型的一门学科。简单地说，数据结构是指相互有关联的数据元素的集合，即数据的组织形式。***数据项、数据类型、数据元素、数据变量2、数据的逻辑结构和存储结构1、数据的逻辑结构数据的逻辑结构是指数据之间的相互关系。一般包括：线性结构和非线性结构。1）线性结构：其特点是：结构中有且仅有一个始结点和一个终结点，始结占只有一个后继结点，终结点只有一个前趋结点，每个内结点有且仅有一个前趋结点和一个后继结点。线性结构最一般的情形是线性表。如下图：线性表2）非线性结构其特点是：结构中的结点可能有多个前趋结点和多个后继结点。通常有集合，树和网三种类型。如下图。最重要的非线形结构是“树”，树中有且仅有一个没有前趋结点的结点，称之为根结点；其他结点都仅有一个前趋结点，但允许有多个后继结点。从根结点到任一非根结点，都有且仅有一条路径。集合树网2、数据的存储结构数据的最基本的存储结构一般有以下四种：***顺序存储方法，链接存储方法，索引存储方法，散列存储方法。3算法的五个特性：有穷性可行性确定性输入输出参看教材。4算法中基本操作重复执行的次数依据算法中最大语句频度来估算，它是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，表示随问题规模n的增大，算法执行时间的增长度和f(n)的增长度相同。常用时间复杂度有如下关系：O(1)≤O(log2n)≤O(n)≤O(nlog2n)≤O(n2)≤O(n3)≤…≤O(nk)≤O(2n)***参考练习分析以下程序段的时间复杂度。for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;解：该程序段的时间复杂度为O(m*n)。如果m=n?A[i][j]=0;改成x++;x=x+1;又为多少？在线性结构、树形结构和图形结构中，元素之间的联系分别对应为-----------------、--------------和-----------一个算法的效率可分为-----------------和---------------下面的程序段中，对x赋值的语句频度为--------for(i=0;in;i++)for(j=0;ji;j++)for(k=0;kj;k++)x=x+m;数据的存储结构可用四种基本的存储方法表示，它们分别是-----------、-----------、-----------、-------------******理解数组与结构的定义与特征；并能够给出数组与结构的应用线性第1部分***１线性表的逻辑特征从以上的定义及例子可以看出，线性表具有以下逻辑特征：1）在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；2）有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。***2、顺序表的结构类型定义/*顺序表的定义：*/#defineListSize100/*表空间大小可根据实际需要而定，这里假设为100*/typedefintDataType;/*DataType可以是任何相应的数据类型如int,float或char*/typedefstruct{DataTypedata[ListSize];/*向量data用于存放表结点*/intlength;/*当前的表长度*/}SeqList;***３/*顺序表的建立：*/voidCreateList(SeqList*L,intn){inti;for(i=0;in;i++)scanf(%d,&L-data[i]);L-length=n;}/*顺序表的打印：*/voidPrintList(SeqListL,intn){inti;for(i=0;in;i++)printf(%d,L.data[i]);printf(\n);}顺序表的查找算法/*顺序表的查找：*/intLocateList(SeqListL,DataTypex){inti=0;while(iL.length&&L.data[i]!=x)++i;if(iL.length)returni+1;/*找到返回该值的位置*/elsereturn0;/*找不到返回0*/}***４/*单链表的定义：*/typedefcharDataType;/*DataType可以是任何相应的数据类型如int,float或char*/typedefstructnode/*结点类型定义*/{DataTypedata;/*结点的数据域*/structnode*next;/*结点的指针域*/}ListNode;typedefListNode*LinkList;*****单链表中指针p指向结点A，若增加或删除结点存在，则需要修改指针的操作如何修改！在C中，链结点变量的动态生成方法：S=(ListNode*)malloc(sizeof(ListNode));/*生成新结点*/它表示，通过函数malloc分配一个类型为ListNode的结点变量的空间，并将其始地址放入指针变量S中。***参考练习１）线性表中哪些元素只有一个直接前驱和一个直接后继----------A首元素B尾元素C中间元素D所有的元素２）在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为---------An-i+1Bn-iCiDi-1３）何时选用顺序表、何时选用链表作为线性表的存储结构为宜？线性表的两种存储结构及其优缺点。①.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。②基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。线性第2部分栈***１栈（Stack）的概念栈（stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的特殊线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出（LIFO，lastinfirstout）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。下图是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。２栈的入栈和出栈操作在顺序存储结构上的实现a1a2an入栈出栈栈顶top栈底bottom图3-1栈的示意图．．．//-----栈的顺序存储表示-----#defineMaxsize50;#defineFalse0;#defineTrue1TypedefintBOOL;//typedefenum{false1=0,true1=1}BOOLTypedefintT;typedefstructstack{intTop,Maxstack;TElemType[Maxsize];}Stack;1)顺序栈的创建voidCreatestack(Stack*s,intmaxsize){s-Top=-1;s-Maxstack=maxsize;}***2）判断栈是否为空BOOLisempty(Stacks){returns.Top0;}***3）判断栈是否为满BOOLisfull(Stacks){returns.Top=s.Maxstack-1;}***4)入栈voidPush(Stack*s,Tx){if(isfull(*s))printf(underflow);elses-Elements[++s-Top]=x;}***5）出栈voidPop(Stack*s){if(isfull(*s))printf(underflow);elses-Top--;}***参考练习1）线性表和栈都是-------结构，可以在线性表的------位置插入和删除元素，对于栈只能在----------位置插入和删除元素（2）一个栈的入栈序列是A、B、C、D、E，则栈的出栈序列是--------------（3）顺序栈是空栈的条件是---------Atop==0Btop==1Ctop==--1Dtop==m(4)栈是限定在---------处进行插入或删除操作的线性表A端点B栈底C栈顶D中间（5）设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后（push每次操作是压入一个元素，pop每次操作弹出一个元素），输出序列是2，3（６）栈是限定在（______）处进行插入或删除操作的线性表A端点B栈底C栈顶D中间线性第2部分队列***１队列的定义队列（Queue）也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一段称为队头（Front），允许插入的一段称为队尾（Rear）。队列的修改是按先进先出的原则进行的。因此，队列又称为先进先出（FirstInFirstOut）的线性表，简称为FIFO表。假若队列Q={a1，a2，…，an}，进队列的顺序为a1，a2，…，an，则队头元素为a1，队尾元素为an。***２队列是一个受限的线性表存在惟一的第一个元素（队头）；存在惟一的最后一个元素（队尾）；除第一个元素之外，每个元素均只有一个直接前驱；除最后一个元素之外，每个元素均只有一个直接后继***３循环队列（CircularQueue）（教材当中）1）基本概念2）循环队列满队与空队的条件判断***参考练习(1)队列是限定在（）处进行插入操作的线性表------------A端点B队头C队尾D中间（2）队列的特点是--------------A先进先出B后进先出C先进后出D不进不出（3）循环队列Sq是空队列的条件是-------------ASq-read==Sq-frontB(Sq-read+1)%maxsize==Sq-frontCSq-read==0DSq-front==0(4)循环队列Sq是满队列的条件是-------------ASq-read==Sq-frontB(Sq-read+1)%maxsize==Sq-frontCSq-read==0DSq-front==0（５）队列是限制插入只能在--------，而删除在表的----------的线性表。线性第3部分数组1、数组的定义数组（Arrays）是由一组类型相同的数据元素构造而成的。它的每个元素由一个值和一组下标确定。一维数组:如果数组元素只含有一个下标，这样的数组称为一维数组。如果把数据元素的下标顺序换成线性表中的序号，则一维数组就是一个一维数组。出队出队a1a2a3aian队头（front）队尾（rear）……二维数组:如果数组的每一个元素都含有两个下标，这样的数组称为二维数组，也称为矩阵（Matrix）。如下图，Amn就是一个m行n列的矩阵，可以用一个二维数组来表示，它的每一个元素由aij及一组下标来确定。数组一旦被定义，