数据结构复习重点

第一章*掌握数据、数据元素、数据对象、数据结构的定义，四类基本结构。•数据：指能够被计算机识别、存储和加工处理的信息载体。（数据（Data）:是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。）•数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。（数据项是数据的不可分割的最小单位。•数据对象：性质相同的数据元素的集合，是数据的一个子集。•数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。•四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。*数据结构的逻辑表示与物理存储->逻辑结构与存储结构•“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。•数据结构在计算机中的表示称为物理结构。又称存储结构。有顺序存储结构和链式存储结构•抽象数据类型定义（ADT）：是指一个数学模型以及定义在该模型上的一组操作。*掌握算法的定义及特性，算法设计的要求•算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性。•算法的五个特性：有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。输出：一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。•算法设计的要求1、正确性2、可读性3、健壮性4、效率与低存储量需求•效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。•存储量需求指算法执行过程中所需要的最大存储空间。•两者都与问题的规模有关。*掌握算法的渐近时间复杂度和空间复杂度的意义与作用及计算方法•语句的频度指的是该语句重复执行的次数。•学会计算语句重复执行的次数。•重点掌握算法的5个特性（有穷性，确定性，可行性，输入，输出），算法好坏衡量标准（好的算法要满足正确性，可读性，健壮性，效率与地存储需求），给出一个算法，分析时间复杂度（表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同），语句频度（指的是该语句重复执行的次数）AW-—*第——早•线性表（LinearList）:由n（n弐）个数据元素（结点）a1,a2， ...an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(al,a2,...an)其中ai是属于某一个数据对象的数据元素。•线性表的逻辑特征是：1•线性表中所有元素的性质是相同的，即具有相同数据类型。2•在非空的线性表，有且仅有一个开始结点al,它没有直接前趋，而仅有一个直接后继a2；3.有且仅有一个终端结点an,它没有直接后继，而仅有一个直接前趋an-1；4•其余的内部结点ai(2旨旨1-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。•线性表的运算：基本运算：1•存取：存取或更新表中某个数据元素。2•插入：在表的两个确定的元素之间插入一个新元素。3•删除：删除表中某个数据元素。4•查找：查找表中满足某种条件的数据元素。如找出某个数据项具有给定值的数据元素。复杂运算：5•合并：把两个线性表合并成一个线性表。6•分解：把一个线性表拆分成多个线性表。7•排序：按一个或多个数据项值的递增或递减次序重新排列表中数据元素。•最基本的运算有：查找、插入和删除。•顺序表一把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里这组连续的存储单元称为向量。假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。线性表中第i+1个数据元素的存储位置LOC(ai+1):LOC(ai+1)=L0C(a1)+L*i线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*L通常称LOC(a1)为线性表的开始地址。•顺序存储结构的特点：表中逻辑上相邻的数据元素存储在相邻的存储位置。即以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。要访问第i个数据元素，就可以直接计算出ai的存储位置LOC(ai)因此，是一种随机存取的存储结构。•适合很少进行插入和删除，但要求以最快的速度存取表中元素的情况。•掌握顺序表的存储结构表示和定义。•顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。•顺序表：把用顺序存储结构存放的线性表称为顺序表(C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。#defineListSize100typedefintDataType;typedefstruct{DataTypedata[ListSize];intlength;}Sqlist;这是静态分配存储空间的定义。采用静态分配时的构造空线性表算法defineListSize100typedefintDataType;typedefstruct{DataTypedata[ListSize];intlength;}Sqlist;StatusInitList(Sqlist*L){/*按静态分配空间方式，构造空线性表L*/L->length=O;returnOK;}模拟主程序：main(){SqlistL;InitList(&L);}在C中也可以用动态分配的一维数组，描述如下：defineLIST_INIT_SIZE100defineLISTINCREMENT10typedefintDataType;typedefstruct{DataType*data;intlength;intlistsize;}Sqlist;采用动态分配时的构造空线性表算法defineLIST_INIT_SIZE100defineLISTINCREMENT10typedefintDataType;typedefstruct{DataType*data;intlength;intlistsize;}Sqlist;StatusInitList(Sqlist*L){/*按动态分配空间方式，构造空线性表L*/L->listsize=LIST_INIT_SIZE;/*存储容量*/L->data=(DataType*)malloc(LIST_INIT_SIZE*sizeof(DataType));/*申请空间*/if(L->data==NULL){printf(“OVERFLOW!”)； /*存储空间申请失败*/returnERROR;}L->length=0;returnOK;})*掌握顺序表的插入(向后移动数据)，删除算法(向前移动数据)，查找运算。1、 插入：线性表的插入运算是指在表的第i(l旨旨1+1)个位置上，插入一个新结点X。算法2.4VoidInsertList(Sqlist&L,DataTypex,inti){//在顺序线性表L中第i个位置之前插入新的元素xintj;if(i<1IIi>l.length+1)printf(“Positionerror");returnERROR;if(l.length>=ListSize){printf(“overflow”);exit(overflow);}for(j=l.length-1;j>=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x;l.length++;}备注：L为固定长度的顺序线性表。2、 删除：线性表的删除运算是指将表的第i(1旨旨1)结点删除，使长度为n的线性表:(a1,...ai-1,ai,ai+1...,an)变成长度为n-1的线性表(a1,...ai-1,ai+1,an)算法2.5VoiddeleteList(Sqlist&1,inti){//在顺序线性表L中删除第i个位置的元素xintj;if(i<1IIi>l.length)printf(“Positionerror");returnERROR;for(j=i;jv=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}*线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点•为避免大量结点的移动，我们介绍线性表的另一种存储方式:链式存储结构，简称为链表(LinkedList)。*分单链表，双链表，循环单链表，循环双链表*掌握各种链表的特点，适用范围。*掌握基本运算，如何改变指针完成运算。*如单链表，双链表，循环链表各种链表的结构图，类C的数据结构定义，做各种运算时如何改变指针第三章#栈的定义及基本运算：*栈(Stack)是限制在表的一端进行插入和删除运算的线性表*插入、删除的这一端为栈顶(Top).另一端为栈底(Bottom)。当表中没有元素时称为空栈。*栈的操作特点：栈的操作后进先出，称为后进先出表(LIFO)*栈的主要运算：插入和删除*插入一个新元素(在栈顶))叫进栈(压入)push(&s,e)；删除一个栈顶元素叫退栈(弹出)pop(&s,e)*栈的其他运算：有栈的初始化(设置一个空栈)判定某个栈是否为空栈(判空》读取栈顶元素等*顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。*可用数组来实现顺序栈。*设定一个整型变量top表示栈顶位置，称栈顶指针。*约定：top指向实际栈顶下面一个空位置，即新数据将要插入的位置。顺序栈的类型定义如下：#defineStackSize100;typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}SeqStack;设S是SeqStack类型的变量。则s.top=0表示空栈(栈空条件)，s.top>=StackSize表示栈满(栈满条件)*若用s.top、s.base分别表示栈顶和栈底指针，则栈空，栈满条件：栈空条件：s.top=s.base； 栈满条件：s.top-s.base>=s.stacksize*栈的基本运算如下：进栈：当某一数据x进栈，先判断栈是否已满，否，置s.data[s.top]=x,s.top加1退栈：当栈顶元素退栈时，先判断栈是否已空，否，s.top减1,取y=s.data[s.top]#栈的应用*数制转换(要求掌握)括号匹配的检验(以下四个了解即可)行编辑程序；迷宫求解；表达式求值；栈和递归的实现：要求能够会编写递归程序。#队列*队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。*允许删除的一端称为队头(front). 允许插入的一端称为队尾(rear)。*队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。*主要运算：插入一个新元素，称入队删除一个新元素，称出队*其它运算：判断队列是否为空判断队列是否为已满设置空队列 销毁队列清空队列 求队列长度取队头元素*一个队列需要两个分别指示队头和队尾的指针。设front为头指针，始终指向队头；rear为尾指针，指向队尾；当front=rear为队空。*由于有顺序表和链表，相应就有顺序队列和链队列。*链队列：用链表表示的队列简称为链队列。设有一表头结点,front始终指向表头结点；rear指向含队尾元素的结点；*队空条件：当front=rear为队空。*队满条件：由于存储空间是用时申请的，一般不能满，除非计算机中空间没有了*链队列的类型定义：typedefstructqueuenode{datatypedata;structqueuenode*next;}queuenode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;*入队操作：申请空结点，给新结点赋值（数据域和指针域）；将原尾指针指向新结点，建立连接；移动尾指针到新结点。*出队操作：判断队列是否为空；否，取队首元素，指针后移，释放队首指针。*注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。*顺序队列：实现：用一维数组实现data[M]*设front为队头指针，指向实际队头的前一个位置；rear为队尾指针，指向实际队尾元素所在位置。*初始状态：front=rear=-1*设定front=rear时队列为空；rear=MAXQSIZE-1队列满了，再不能入队，则称“上溢”（假上溢）*出队操作：队头指针增1,判是否为空，否，取此位置的