数据结构是一门研究计算机的操作对象以及操作对象之间的关.ppt

4.所有拓扑排序序列。 5.根据迪杰斯特拉(Dijkstra)算法，求出给定有向图(如图所示)从顶点v1到其他各顶点长度递增的最短路径，并分别写出执行算法过程中各个数组的变化状态。 数据结构 是一门研究计算机的操作对象 以及操作对象之间的关系 和对操作对象实施的典型操作 的学科 第一部分 概述 研究数据结构从三个方面进行： （1）逻辑结构 （2）存储结构 （3）操作（运算）： 对数据进行的处理， 定义在数据的逻辑结构上 具体实现于数据的存储结构 描述数据逻辑结构 描述数据物理结构 ADT由三元组构成：（D，S，P） D 数据对象 S 关系 P 操作集 关系的表示方法 顺序映象 非顺序映象 顺序存储结构 链式存储结构 四种基本的数据结构及其特点 算法的特征及评价方法 集合 线性表 树 图 数据元素 数据项 数据对象 时间复杂度 空间复杂度 第二部分 表、栈、队列 线性表的逻辑结构 线性表的物理结构 顺序表 单向链表 循环链表 双向链表 静态链表 有序性 均匀性 位序 操作及算法的分析（顺序表、单链表） 插入 删除 查找 建表 合并 集合运算 顺序表与线性链表的对比 1.静态结构与动态结构(大小) 2.数据关系的表示方法 3.操作(插入/删除、查找) 带头结点与不带头结点的对比 1.空表与非空表一致性 2.不同位置插入、删除操作的一致性 栈和队列 栈和队列的特点：操作受限制 栈和队列的操作（建立、入/出） 栈/队列的空、满条件 顺序 链 栈和队列的物理结构 栈和队列的应用 特征串的判断 进制转换 括号匹配 逆波兰表达式求值 ∥–––––线性表的动态分配顺序存储结构––––– #define LIST_INIT_SIZE 100 ∥线性表存储空间的初始分配 #define LISTINCREMENT 10 ∥线性表存储空间的分配增量 typedef struct { ElemType *elem; ∥存储空间基址 int length; ∥当前长度 int listsize; ∥当前分配的存储容量 }SqList; ∥ –––––栈的顺序存储表示 ––––– #define STACK_INIT_SIZE 100 ∥存储空间初始分配 #define STACKINCREMENT 10 ∥存储空间分配增量 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; ∥–––––循环队列──队列的顺序存储结构––––– #define MAXQSIZE 100 ∥最大队列长度 typedef struct {QElemType *base; ∥初始化的动态分配存储空间 int front; ∥头指针,若队列不空,指向队列头元素 int rear; ∥尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; //线性链表存储结构 typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; LinkList L; ∥–––––队列的链式存储结构––––– typedef struct QNode {QElemType data; Struct QNode *next; }QNode, *QueuePtr; //链栈存储结构 typedef struct SNode { SElemType data; struct SNode *next; }SNode, *StackLink; StackLink S; typedef struct { QueuePtr front; ∥队头指针 QueuePtr rear; ∥队尾指针 }LinkQueue 第三部分 串、数组 什么是串 空串 串长 串的物理结构 StrAssign (T , chats) 初始