数据结构期末复习资料

《数据结构期末复习资料》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1章绪论是一门研究非数伉计算的程序设计问题屮计算机的操作对象以及它们之间的关系和操作等的学科。数据结构(DataStructure)：相互之间存在一种或多种特定关系的数据元素的集合。2、数据结构的形式定义：二元组Data_StrUCture=(D，S)其中，D是数据元素的有限集，S是D上关系的有限集。3、数据元素之间关系的映像：1、顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。2、非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于数据(逻辑)结构，其实现取决于物理结构。4、算法的定义：对特定问题求解步

2、骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。特性：有穷性、确定性、可行性、输入、输出5、算法的评价——衡量算法优劣的标准正确性(correctness):满足具体问题的需求可读性(readability):易读、易理解健壮性(mbustnes咏当输入数据非法时，算法能够做出反应或进行处理时间复杂性与空间复杂性:执行吋间短、存储空间小第2章线性表1、线性表是一种最简单的线性结构。线性结构是一个数据元素的有序(次序)关系特点：存在唯•一的一个“第一个”的数据元素；存在唯一的一个“最后一个”的数据元素；除第•一个数据元素外，均有唯一的前驱：除最后一个

3、数据元素外，均有唯一的后继2、线性表类型的实现——顺序映像定义：用一组地址连续的存储单元依次存放线性表中的数据元素。■以“存储位置相邻”表示有序对<心-1,乂〉，则有：LOC{ai}=LOC{ai-}+I其屮I是一个数裾元素所占存储量LOC(ai)=LOC(aL)+(/-l)X/■特点：丨、实现逻辑上相邻一物理地址相邻2、实现随机存取3、若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：1n++ltn~2若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为:4、线性表类型的实现——链式映像线性链表特点：用一组地

4、址任意的存储单元存放线性表中的数据元素。5、在单链表屮第i个结点之前进行插入的基本操作为：找到线性表屮第i-1个结点，然后修改其指向后继的指针。s=(LinkList)malloc(sizeof(LNode));//生成新错点s-〉data=e;s->next=p-〉next;p->next=s;//插入在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。q=p->next;p->next=q->next;e=q-〉data;free(cj);5、循环链表：最后一个结点的指针域的指针又指回第一个结点的链表。和单链表的差别仅在于:判别

5、链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。6、双向链表的操作特点：I、“查询”和单链表相同；2、“插入’’和“删除”时需要同时修改两个方向上的指针‘‘插入”：s-〉next=p-〉next;p->next=s;s->next->prior=s;s->prior=p;(s是插入的结点)删除：p-〉next=p-〉next-〉next;p-〉next-〉prior=p;(要删除的是p的下一个结点)第3章栈和队列1、栈、队列的特点：□从数据元素间的逻辑关系看◊是线性表□从操作方式与种类看◊不同于线性表：栈与队列是操作受限的线性表2、桟的基本概

6、念栈---是限制仅在线性表的一端进行插入和删除运算的线性表。栈顶(TOP)--允许插入和删除的一端。栈底(bottom)--不允许插入和删险的一端。空栈--表中没有元素。栈--又称为后进先出的线性表3、栈中元素的特性：1、具有线性关系2、后进先出4、栈的进栈出栈规则：a)按序进栈：有n个元素1，2，...,n，它们按1，2,…,n的次序进栈(i进栈时，1〜(i-1)应该已经进栈);b)栈顶山栈：栈底最后山栈；c)时进时出：元素未完全进栈时，即可出栈。5、栈的表示与实现顺序栈即栈的顺序存储结构：一组地址连续的存储单元依次存放向栈底到栈顶的数椐元素。1、附设一个栈底指针b

7、ase,总是指向栈底。2、附设一个栈顶指针top。空栈吋，top=base；非空栈吋，总是指向栈顶元素+1的位置。□插入一个栈顶元素，指针top增1;□删除一个栈顶元素，指针top减1;□非空栈屮的栈顶指针始终在栈顶元素的下一个位置上链栈：注意：链栈中指针的方向指向前驱结点!6、队列■队列：只允许在表的一端进行插入，而在表的另一端进行删除的线性表。□队尾(rear)允许插入的一端□队头(front)——允许删除的一端■队列特点：先进先出(FIFO)7、队列类型的实现■链队列——队列的链式表示和实现■顺序队列——队列的顺序表示和实现用一组连续的存储单元