数据结构总复习幻灯片

《数据结构总复习幻灯片》由会员分享，可在线阅读，更多相关《数据结构总复习幻灯片（147页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构,西南民院计算机系,TEL 13618097826 Emailliu-li-,题型 1 选择题 2 填空题 3 解答题 4 算法题,第一章 绪论,第一章 绪 论,计算机的发展 硬件 CPU、内、外存储器等 软件：系统软件、应用软件 应用 科学计算 数据处理 过程控制等 处理数据的能力和种类：数值 字符、字符串 具有多个属性对象 图形 图像 声音,数据结构的研究对象： 非数值数据之间的结构关系，如何表示， 如何存储，如何处理的问题。 本课程讨论的问题： 应用中常用的几种数据结构，以及如何存储, 如何处理它们。,第一章 绪 论,1 数据：客观对象的符号表示。 例如：课程名，地名，书名

2、都是数据 2 数据结构：带有结构和操作的数据元素集合 结构：数据元素之间的关系； 操作：对数据的加工处理 ；,第一章 绪 论,第一章 绪 论,第一章 绪 论,6 数据的存储结构： 数据结构在计算机内存中的表示。 7 顺序存储结构 用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系； 8 链式存储结构 用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。 数据结构基本操作的实现：基本操作在计算机上的实现（方法）,9 数据结构的表示 1 图示表示 2 二元组表示,图示表示：由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的结构

3、关系；,第一章 绪 论,二元组表示 用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。,D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, , ,第一章 绪 论,第一章 绪 论,10 算法的概念 算法是求解问题的操作序列（或操作步骤） 11 时间复杂度T（n） 以求解问题的基本操作（原操作）的执行次数作为算法的时间度量 空间复杂度 用执行算法所需的辅助空间的大小作为算法所需空间的度量,第一章 练习题,1 数据结构：带有结构和操作的数据元素集合。 2 常用的数据结构 数据结构的表示 4 数据的逻辑结构 ：数据之间的结构关系，是具体关

4、系的抽象。 数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理； 数据的存储结构：数据结构在计算机内存中的表示 数据结构基本操作的实现：基本操作在计算机上的实现（方法） 顺序存储结构 链式存储结构 10 算法的概念 算法是求解问题的操作序列（或操作步骤）。 11 时间复杂度T（n） 以求解问题的基本操作（原操作）的执行次数作为算法时间的度量,第二章 线性表,常用的数据结构 1） 集合 2） 线性结构 3） 树结构 4） 图结构 5） 其它复杂结构,第二章 线性表,对每种数据结构，主要讨论如下两方面的问题 1 数据的逻辑结构，数据结构的基本操作； 2 数据的存储结构，数据结构基本操作的实

5、现,第二章 线性表,线性数据结构： 除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。,2.1 线性表的概念 一 线性表的逻辑结构 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。,2.1 线性表的概念,线性表的基本操作 1 初始化操作 InitList(&L) 2 销毁操作DetroyList(&L) 3 置空操作ClearList(&L) 4 判空操作ListEmpty(L) 5 求表长操作 ListLength(L) 6 取元素操作：GetElem(L,i,&e) 7 查找操作 LocateElem(L

6、,e,compare() 8 插入操作 ListInsert(&L,i,e ) 9 删除操作 ListDelete(&L,i,&e ) 10 遍历操作 ListTraverse(&L,visit() ),2.1 线性表的概念,2.2 线性表的顺序存储和实现,一 线性表的顺序存储结构顺序表 1 顺序表用一组连续的内存单元依次存放线性表的数据元素。,2 顺序表的类型定义 typedef struct ElemType *elem; /线性表存储空间基址 int length; /当前线性表长度 int listsize; /当前分配的存储空间大小 SqList;,顺序表图示,设 A =（a1,a2

7、 , a3 , . an ）是一线性表，L是SqList 类型的结构变量，用于存放 A,2.2 线性表的顺序存储和实现,顺序表保存了哪些信息?,2.2 线性表的顺序存储和实现,顺序表保存了哪些信息？ *线性表中的数据元素； *线性表中数据元素的顺序关系； *表中元素个数（简化算法） *当前分配的存储空间 顺序表如何保存这些信息？ 3 顺序表存储特点 元素存储在一组连续的内存单元中； 通过元素存储顺序元素之的逻辑顺序；,二 顺序表的基本操作算法 1 初始化算法 InitList_Sq( SqList &L) 2 插入操作算法 ListInsert_Sq(SqList &L,int i,ElemT

8、ype e) 3 删除操作算法 ListDelete_Sq(SqList &L,inti,ElemType &e),2.2 线性表的顺序存储和实现,2.2 线性表的顺序存储和实现,5 顺序表主要操作特点 1）可随机存取顺序表的元素 (用L.elemi-1或L.elem+(i-1)可直接定位元素的存储地址) 2）插入删除操作通过移动元素实现,23 线性表的链式存储结构和实现,线性表的链式存储结构 用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。,2.3.1 线性链表 一 线性链表的概念 1 线性链表,用一组任意的存储单元存储线性表中的数据

9、元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。,23 线性表的链式存储结构和实现,typedef struct Lnode ElemType data; Struct Lnode *next; LNode, *LinkList;,data next,2 线性链表的结点类型定义 及指向结点的指针类型定义,2. 3. 1 线性链表,2. 3. 1 线性链表,3 线性链表存储特点 1）用一组任意的存储单元存储线性表中的数据元素； 2） 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；,二 线性链表基本操作算法 1 初始化操作算法 InitList_L (Link

10、List &L) 2 插入操作算法 ListInsert_L(LinkList &L,inti,ElemType e) 3 删除操作算法 ListInsert_L(LinkList &L,inti,ElemType &e),2. 3. 1 线性链表,2. 3. 1 线性链表,5 线性链表操作主要特点 1）不能随机存取元素； 2）插入、删除操作通过修改结点的指针实现；,循环链表 循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点,2.3.2 循环链表,双向链表,双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,2.3.3 双向链表,线性表的

11、其他操作的实现 1) 通过调用基本操作算法 2) 直接实现,线性表的其他操作的实现,第二章 练习题,；,线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。 顺序表存储特点： 1）元素存储在一组连续的内存单元中 2）通过元素的存储顺序反映线性表中数据元素之的逻辑顺序； 顺序表操作特点： 1）可随机存取顺序表的元素； 2）顺序表的插入删除操作要通过移动元素实现,第二章 练习题, 线性链表存储特点 1）用任意一组的存储单元存储线性表中的数据元素； 2） 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系； 线性链表操作特点 1）

12、不能随机存取元素； 2）插入、删除操作通过修改结点的指针实现；顺序表的插入、删除操作平均要移动表的一半元素,第二章 练习题,顺序表能随机存取元素的原因是：顺序表能通过L.elemi-1或L.elem+(i-1)直接定位元素的存储地址。 线性链表不能随机存取元素的原因是： 需从线性链表的头指针开始，顺着链指针定位元素的存储地址 对于经常要存取元素的应用，线性表应采用顺序存储结构 10 对于经常要插入删除元素的应用，线性表应采用链式存储结构,第三章 栈和队列,栈是限定仅能在表尾进行插入删除操作的线性表。,栈的特点 后进先出,3.1 栈,一.栈的概念 1 栈的定义,3.1 栈,2 栈的基本操作 1）

13、 初始化操作InitStack(&S) 2）销毁栈操作DestroyStack(&S) 3）置空栈操作ClearStack(&S) 4）取栈顶元素操作GetTop(S, &e) 5）进栈操作Push(&S, e) 6）退栈操作Pop(&S, &e） 7）判空操作StackEmpty(S),3.1 栈,二 栈的顺序存储和实现 1 栈的顺序存储结构 1） 用一组连续的内存单元依次存放自栈底到栈顶的数据元素； 2） 栈顶元素的位置由栈顶指针指示；,typedef struct SElemType *base; /栈底指针 SElemType *top /栈顶指针 int stacksize; /当前

14、分配的栈空间大小 /(以sizeof(SElemType)为单位） SqStack;,3.1 栈,2 顺序栈的类型定义,3.1 栈,顺序栈的图示,栈操作算法 1）进栈操作算法：在栈顶插入元素 Push(SqStack &S, SElemType e) 2）出栈操作算法：在栈顶插入元素 Pop(SqStack &S, SElemType &e ) 4 栈操作主要特点 进栈、出栈操作要修改栈顶指针,3.1 栈,3.1 栈,栈的链式存储和实现 栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。 注意：栈顶指针就是带头结点的线性链表的头指针,S,四 栈的应用举例 例2 表达式求值 算符优

15、先算法：掌握利用操作数栈OPND ，运算符栈OPTR，对表达式求值的方法,3.2 栈,第三章 练习题,栈是限定仅能在表尾一端进行插入、删除操作的线性表； 2 表尾称为栈顶，表头称为栈底； 3 栈的具有后进先出的特点； 4 栈顶元素的位置由一个栈顶指针指示； 5 进栈、出栈操作要修改栈顶指针； 6 一个栈的输入序列为a,b,c，则所有可能的出栈序列为： abc,acb,bac,bca,cba,一 队列的概念 队列的定义,队列是限定仅能在表头删除，表尾插入的线性表。,队列的特点 先进先出,34 队列,2 队列的基本操作 1）初始化操作InitQueue( &Q) 2）销毁操作DestroyQueu

16、e( &Q) 3）置空操作ClearQueue(&Q) 4）判空操作QueueEmpty(Q) 5）取队头元素操作GetHead(Q,&e) 6）入队操作EnQueue( &Q, e ) 7）出队操作DeQueue( &Q, &e),34 队列,二 循环队列队列的顺序存储和实现 循环队列队列的顺序存贮结构 （1）在队列的顺序存贮结构中用一组连续存储单元依次存储队列的数据元素 （2）队头、队尾元素的位置分别由队头指针和队尾指针指示； （3）将顺序队列设想为首尾相连的环状空间,34 队列,2 循环队列的类型定义,#define MAXSIZE 100 /最大队列长度 typedef struct QElemType *base; 队空间基址 int front; /队头指针 int