数据结构总复习讲解.ppt

数据结构是计算机科学与技术或信息类专业本科生的一门核心课程。 本课程介绍如何对各种数据进行组织，并在计算机中对其进行存储、传递和转换。内容包括：数组、链表、栈和队列、递归、树与森林、图、查找、内部排序、外部排序与文件结构等。 课程强化数据结构基本知识和程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。 先修课：C语言程序设计、计算机数学(离散数学) ;;内容安排 (40授课+16实验); ;1.1 数据结构课程的地位;数据结构的研究内容： 数据结构是一门研究数据逻辑、存储和运算的一般方法的学科。 ;1.2 基本概念;有四种基本数据结构： 集合: 数据元素间除同属于一个集合外,无其它关系 线性结构: 一个对一个，如线性表、栈、队列 树形结构: 一个对多个，如树 图状结构: 多个对多个，如图;用 二元组描述数据结构;1.4 数据的存储（物理）结构;元素n;1536;1.5 数据类型;1.5.1 抽象数据类型的表示;1.5.2 抽象数据类型的表示;1.5.3 例题;;;1.8 时间复杂度; ;线性结构的特点：;第2章 线性表;（a1, a2, … ai-1，ai, ai＋1 ，…, an） ;线性表的抽象数据类型(ADT);InitList(L); DestroyList(L); ClearList(L); ListEmpty(L); ListLength(L); GetElem(L, i, e); LocateElem(L, e, compare()); PriorElem(L, cur_e, pre_e); NextElem(L, cur_e, next_e); ListInsert(L, i, e); ListDelete(L,i, e); ListTraverse(L, visited()); 假设利用两个线性表LA和LB分别表示两个集合A和B（即:线性表中的数据元素即为集合中的成员），现要求一个新的集合A=AUB。; 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。 ;2.1 顺序表的表示;线性表的顺序存储结构示意图;例2-2 非递减线性表La,Lb的合并. Lc=La∪Lb. (算法2.2) P20;2.2 链表的表示;例1 画出26 个英文字母表的链式存储结构。;与链式存储有关的术语：;5、头指针、头结点和首元结点 ;2.3 补充结构数据类型及其C语言表示法;补充：结构类型的C语言表示法;设p为指向链表的第i个元素的指???,则第i个元素的 数据域写为 ，指针域写为 。;应用举例：两个链表的归并（教材P31）;用链表可表示为：;算法分析：;La;2.4 循环链表;循环链表的特点: 表中的最后一个结点的指针域指向头结点, 整个链表形成一个环。 从表的任意结点出发可以找到表中其它结点。;第三章 栈和队列; 3.1 栈 3.1 .1 栈的概念 3.1 .2 栈的顺序存储和实现 3.1 .3 栈的链式存储和实现 ;3.1 栈;说明：设（a1, a2, a3, …, an ） 是一个栈 1）表尾称为栈顶，表头称为栈底 ，即a1为栈底元素，an为栈顶元素，2）在表尾插入元素的 操作称进栈操作，在表头删除元素的操作称为出栈操作;3）元素按a1, a2, a3, …, an 的次序进栈, 第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶, 第一个出栈的元素为栈顶元素；?4）栈的元素具有后进先出的特点,所以栈又称为后进先出表（LIFO表）5）由于进栈、出栈操作总是在栈顶一端进行，通常设置称为栈顶指针的变量指示栈顶的位置。;栈的示意图;二 栈的基本操作 1）?初始化操作InitStack((S) 功能：构造一个空栈S； 2） 销毁栈操作DestroyStack(S) 功能：销毁一个已存在的栈;? 3） 置空栈操作ClearStack(S) 功能：将栈S置为空栈; 4） 取栈顶元素操作GetTop(S, e) 功能：取栈顶元素，并用e 返回; 5）进栈操作Push(S, e)功能：元素e进栈; 6）退栈操作Pop(S, e) 功能：栈顶元素退栈，并用e返回; 7）判空操作StackEmpty(S) 功能：若栈S为空，则返回True，否则返回False;; 栈的顺序存储结构也是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元