数据结构导论

Size: px

Start display at page:

Download "数据结构导论"

芯楷詹
7 years ago
Views:

1 微软中国数据结构导论 [ 键入文档副标题 ] 微软用户 2009 [ 键入公司地址 ]

2 目录第一章概论第二章线性表第三章栈和队列第四章串第五章多维数组第六章树第七章图第八章排序第九章查找

3 1. 数据 : 信息的载体, 能被计算机识别存储和加工处理第一章概论 2. 数据元素 : 数据的基本单位, 可由若干个数据项组成, 数据项是具有独立含义的最小标识单位 3. 数据结构 : 数据之间的相互关系, 即数据的组织形式它包括 : 1) 数据的逻辑结构, 从逻辑关系上描述数据, 与数据存储无关, 独立于计算机 ; 2) 数据的存储结构, 是逻辑结构用计算机语言的实现, 依赖于计算机语言 3) 数据的运算, 定义在逻辑结构上, 每种逻辑结构都有一个运算集合常用的运算 : 检索 / 插入 / 删除 / 更新 / 排序 4. 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型数据的存储结构是逻辑结构用计算机语言的实现 5. 数据类型 : 一个值的集合及在值上定义的一组操作的总称分为 : 原子类型和结构类型 6. 抽象数据类型 : 抽象数据的组织和与之相关的操作优点 : 将数据和操作封装在一起实现了信息隐藏 7. 抽象数据类型 ADT: 是在概念层上描述问题 ; 类 : 是在实现层上描述问题 ; 在应用层上操作对象 ( 类的实例 ) 解决问题 8. 数据的逻辑结构, 简称为数据结构, 有 : (1) 线性结构, 若结构是非空集则仅有一个开始和终端结点, 并且所有结点最多只有一个直接前趋和后继 (2) 非线性结构, 一个结点可能有多个直接前趋和后继 9. 数据的存储结构有 : 1) 顺序存储, 把逻辑相邻的结点存储在物理上相邻的存储单元内 2) 链接存储, 结点间的逻辑关系由附加指针字段表示 3) 索引存储, 存储结点信息的同时, 建立附加索引表, 有稠密索引和稀疏索引 4) 散列存储, 按结点的关键字直接计算出存储地址 10. 评价算法的质量 : 1 正确性 ; 算法应能正确地事先预定的功能 2 易读性 ; 算法应易于阅读和理解, 以便于调试和扩充 3 健壮性 ; 当环境发生变化时, 算法能适当地做出反应或进行处理, 不会产生不需要的运行结果 4 高效率 ; 即达到所需的时间和空间性能 11. 算法的时间复杂度 T(n): 是该算法的时间耗费, 是求解问题规模 n 的函数记为 O(n) 时间复杂度按数量级递增排列依次为 : 常数阶 O(1) 对数阶 O(log2ⁿ) 线性阶 O(n) 线性对数阶 O(nlog2ⁿ) 平方阶 O(n^2) 立方阶 O(n^3) k 次方阶 O(n^k) 指数阶 O(2^n)

4 13. 算法的空间复杂度 S(n): 是该算法的空间耗费, 是求解问题规模 n 的函数 12. 算法的特征 : 有穷性 ; 确定性 ; 可行性 ; 输入 ; 输出 13. 决定算法运行时间的因素 :(1) 问题的规模 ;(2) 编译时间 ;(3) 指令执行速度 ;(4) 重复执行指令的速度 1. 线性表 : 是由 n(n 0) 个数据元素组成的有穷序列第二章线性表 2. 线性表的基本运算有 : 1)Initiate(L), 加工型运算, 作用是构造空表, 即表的初始化 ; 2)Length(L), 引用型运算, 其结果是表的结点个数, 即表长 ; 3)Get (L,i), 引用型运算, 若 1 i Length(L), 其结果是表中的第 i 个结点 ; 否则, 为一特殊值 4)Locate (L,x), 引用型运算, 查找 L 中值为 x 的结点并返回结点在 L 中的位置, 若有多个 x 则返回首个 ; 否则返回特殊值表示查找失败 5)Insert (L,x,i), 加工型运算, 在表的第 i 个位置插入值为 x 的新结点, 要求 1 i Length(L)+1; 6)Delete (L,i), 加工型运算, 删除表的第 i 个位置的结点, 要求 1 i Length(L); 3. 顺序表 : 是线性表的顺序存储结构, 即按顺序存储方式构造的线性表的存储结构 4. 顺序表结点的存储地址计算公式 :Loc(ai)=Loc(a1)+(i-1)*C;1 i n ( 其中 Loc(a1) 是顺序表的第一个结点,C 每个变量占用的内存单元 ) 5. 顺序表上的基本运算 (1) 插入 Void insert_sqlist(sqlist L,datatype x,int i) /* 将 X 插入到顺序表 L 的第 i-1 个位置 */ if(l.last==maxsize) error( overflow ); /* 溢出 */ if((i<1) (i>l.last+1)) error ( position error ); /* 非法位置 */ for(j=l.last;j=i;j--) L.data[j]=L.data[j-1]; /* 结点依次后移 */ L.data[i-1]=x; /* 置入 X*/ L.last=L.last+1 /* 修改表长 */ 在顺序表上插入要移动表的 n/2 结点, 算法的平均时间复杂度为 O(n)

5 (2) 删除 Void delete_sqlist(sqlist L,int i); /* 删除顺序表 L 中的第 i 个位置上的结点 */ if ((i<1) (i>l.last)) error ( position error ); /* 非法位置 */ for(j=i+1;j=l.last;j++) L.data[j-2]=L.data[j-1]; /* 依次前移, 注意第一个 L.data[j-2] 存放 a i */ L.last=L.last-1 /* 修改表长 */ 在顺序表上删除要移动表的 (n+1)/2 结点, 算法的平均时间复杂度为 O(n) (3) 定位 Void locate_sqlist(sqlist L,datatype X) /* 在顺序表中从前往后查找第一个值等于 X 的结点若找到则传回该节点的序号 ; 否则传回 0*/ i=1; /*i 指示顺序表 L 中结点序号 */ while ((i L.last)&&(L.data[i-1]!=x)) /* 注意 :a1 在 L.data[i-1] 中 */ if (i L.last) else i++; /* 从前往后找 */ return (i) return (0) 6.. 单链表 : 只有一个链域的链表称单链表 ( 单链表表示法的基本思想是用指针表示结点间的逻辑关系 ) 单链表的一个结点包含两个部分, 结点形式如下 : 数据域指针域 ( 链域 ) (1) 建立单链表时间复杂度为 O(n) 在单链表中加头结点的作用 : 操作统一 ; 无论链表是否为空, 链表的指针不变 (2) 定位 ( 按值查找 ) Int locate_lklist(lklist head,datatype x) /* 求表 head 中第一个值等于 X 的结点的序号不存在这种结点时结果为 0*/ P=head;j=0; /* 置初值 */ While((p->next!=NULL)&&(p->data!=x)) p=p->next;j++; If p->data==x Else (3) 删除时间复杂度为 O(n) return(j); return(0); Void delete_lklist(lklist head;int i) /* 删除表 head 的第 i 个结点 */ p=find_lklist(head,i-1); /* 先找待删结点的直接前驱 */

6 if (( p!=null)&&(p->next!=null )) /* 若直接前驱存在且待删结点存在 */ q=p->next; /*q 指向待删结点 */ p->next=q->next; /* 摘除待删结点 */ free(q); /* 释放已摘除结点 q*/ Else error( 不存在第 i 个结点 ) /* 否则给出相关信息 */ (3) 插入时间复杂度为 O(n) Void insert_lklist(lklist head,datatype x,int i) /* 在表 head 的第 i 个位置上插入一个以 x 为值的新结点 */ P=find_lklist (head,i-1); /* 先找第 i-1 个结点 */ if(p==null) /* 若第 i-1 个结点不存在 */ error( 不存在第 i 个位置 ) /* 退出并给出出错信息 */ else S=malloc(size); s->data=x; /* 否则生成新结点 */ S->next=p->next; /* 结点 *p 的链域值传给结点 *s 的链域 */ p->next=s; /* 修改 *p 的链域 */ 7.. 循环链表 : 是一种首尾相连的链表特点是无需增加存储量, 仅对表的链接方式修改使表的处理灵活方便主要优点 : 从表中任一结点出发都能通过后移做而扫描整个循环链表 8. 空循环链表仅由一个自成循环的头结点表示 9. 在结点中增加一个指针域 prior data next, 形成的链表中有两条不同方向的链称为双链表 10. 双链表的特点是找结点的前驱和后继都很容易 11. 顺序表和链表的比较 1) 基于空间的考虑 : 顺序表的存储空间是静态分配的, 链表的存储空间是动态分配的顺序表的存储密度比链表大因此, 在线性表长度变化不大, 易于事先确定时, 宜采用顺序表作为存储结构 2) 基于时间的考虑 : 顺序表是随机存取结构, 若线性表的操作主要是查找, 很少有插入删除操作时, 宜用顺序表结构对频繁进行插入删除操作的线性表宜采用链表若操作主要发生在表的首尾时采用尾指针表示的单循环链表第三章栈和队列 1. 栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表 (LIFO 表 ) 插入删除端称为栈顶, 另一端称栈底表中无元素称空栈 2. 栈的基本运算有 : (1) 初始化 Initstack(s), 加工型运算, 构造一个空栈 (2) 进栈 Push(S,X), 加工型运算, 将元素 X 插入栈 S 中, 是 X 成为栈 S 的栈顶元素 (3) 退栈 Pop(s), 加工型运算, 当栈不为空时, 将栈顶元素赋给 X, 并从栈中删除当前栈顶 (4) 读栈顶 Top(s), 引用型运算, 若栈 S 不空, 由 X 返回栈顶元素 ; 当栈 S 为空时, 结果为一个特殊标志

7 (5) 判栈空 Empty(s), 引用型运算, 若栈 S 为空栈, 则结果为 1, 否则结果为顺序栈 : 栈的顺序存储结构称顺序栈 4.. 当栈满时, 做进栈运算必定产生空间溢出, 称上溢当栈空时, 做退栈运算必定产生空间溢出, 称下溢上溢是一种错误应设法避免, 下溢常用作程序控制转移的条件 5. 在顺序栈上的基本运算 : 1) 置空栈 Void initstack(seqstack *s) s->top=-1; 2) 判栈空 int stackempty(seqstack *s) return s->top==-1; 3) 判栈满 int stackfull(seqstack *s) return s->top==stacksize-1; 4) 进栈 Void push(seqstack *s,datatype x) if(stackfull(s)) error( stack overflow ); s->data[++s->top]=x; 5) 退栈 Datatype pop(seqstack *s) if(stackempty(s)) error( stack underflow ); return S->data[s->top--]; 6) 取栈顶元素 Dtatatype stacktop(seqstack *s) if(stackempty(s)) error( stack underflow ); return S->data[s->top];

8 6. 链栈 : 栈的链式存储结构称链栈栈顶指针是链表的头指针 7. 链栈上的基本运算 : 1) 建栈 Void initstack(linkstack *s) s->top=null; 2) 判栈空 Int stackempty (linkstack *s) return s->top==null; 3) 进栈 Void push(linkstack *s,datatype x) stacknode *p=(stacknode *)malloc(sizeof(stacknode)); p->data=x; p->next=s->top; s->top=p; 4) 退栈 Datatype pop(linksatck *s) datatype x; stacknode *p=s->top; if(stackempty(s)) error( stack underflow ); x=p->data; s->top=p->next; free(p); return x; 5) 取栈顶元素 Datatype stacktop(linkstack *s)

9 if(stackempty(s)) error( stack is empty ); return s->top->data; 8. 队列是一种运算受限的线性表, 允许删除的一端称队首, 允许插入的一端称队尾队列又称为先进先出线性表,FIFO 表 9. 队列的基本运算 : 1) 初始化 InitQueue(Q), 加工型运算, 设置一个空队列 Q 2) 入队列 EnQueue(Q,X), 加工型运算, 将 X 插入到队列 Q 的队尾 3) 出队 OutQueue(Q,X), 加工型运算, 若队列 Q 不为空, 则将队头元素赋给 X, 并删除队头结点, 而该结点的后继成为新的队头结点 4) 判队列空 EmptyQueue(Q), 引用型运算, 若队列 Q 为空, 则返回的值为 1, 否则为 0 5) 读队头 GetHead(Q,x), 引用型运算,Q 不空时由参数 X 返回队头结点的值, 否则给一特殊标志 10. 顺序队列 : 队列的顺序存储结构称顺序队列设置 front 和 rear 指针表示队头和队尾元素在向量空间的位置 11. 顺序队列中存在假上溢现象, 由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用, 队尾指针超过向量空间的上界而不能入队 12. 为克服假上溢现象, 将向量空间想象为首尾相连的循环向量, 存储在其中的队列称循环队列 i=(i+1)%queuesize 13. 循环队列的边界条件处理 : 由于无法用 front==rear 来判断队列的空和满解决的方法有 : 1) 另设一个布尔变量以区别队列的空和满 ; 2) 少用一个元素, 在入队前测试 rear 在循环意义下加 1 是否等于 front; 3) 使用一个记数器记录元素总数 14. 链队列 : 队列的链式存储结构称链队列, 链队列由一个头指针和一个尾指针唯一确定 15.. 链队列的基本运算 : 1) 入队 Void enqueue(linkqueue *q,datatype x) queuenode *p=(queuenode *)malloc(sizeof(queuenode)); p->data=x; p->next=null; if(queueempty(q)) q-front=q->rear=p; else q->rear->next=p; q->rear=p; 2) 出队 Datatype dequeue(linkqueue *q)

10 datatype x; queuenode *p; if(queueempty(q)) error( queue is underflow ); p=q->front; x=p->data; q->front=p->next; if(q->rear==p) q->rear=null; free(p); return x; 第四章串 1. 串 : 是由零个或多个字符组成的有限序列 ; 包含字符的个数称串的长度 ; 2. 空串 : 长度为零的串称空串 ; 空白串 : 由一个或多个空格组成的串称空白串 ; 子串 : 串中任意个连续字符组成的子序列称该串的子串 ; 主串 : 包含子串的串称主串 ; 子串的首字符在主串中首次出现的位置定义为子串在主串中的位置 ; 3. 空串是任意串的子串 ; 任意串是自身的子串 ; 串常量在程序中只能引用但不能改变其值 ; 串变量取值可以改变 ; 4. 串的基本运算 (1) 赋值 ASSIGN(S,T), 加工型运算, 将串 T 的值传给串变量 S (2) 判等 EQUAL(S,T), 引用型运算, 若 S 和 T 的值相等则返回值为 1, 否则返回值为 0. (3) 求长 LENGTH(S), 引用型运算, 求串的长度 (4) 联接 CONCAT(S,T), 引用型运算, 运算结果为由 S 和 T 联接在一起形成的新串 (5) 求子串 SUBSTR(S,i,j), 引用型运算, 其结果是串 S 中从第 i 个字符开始的, 由连续 j 个字符组成的子串 (6) 插入 INSERT(S 1,i,S 2), 加工型运算, 作用是将串 S 2 整个插入到串 S 1 的第 i 个字符之后从而产生的一个新串 (7) 删除 DELETE(S,I,j), 加工新运算, 作用是从串 S 中删去从第 i 个字符开始的长度为 j 的子串 (8) 定位 INDEX(S,T), 引用型运算, 若在串 S 中存在一个于 T 相等的子串, 则本运算的结果为 S 中第一个这样的子串中的第一个字符在 S 中的位置 ; 否则, 结果为 0. (9) 替换 REPLACE(S,T,R), 加工型运算, 结果是在串 S 中处处同时以串 R 置换串 T 的所有出现所得的新串 5. 串的存储结构 : (1) 串的顺序存储 (2) 串的链接存储第五章多维数组 1. 多维数组 : 一般用顺序存储的方式表示数组 2. 数组的逻辑结构是线性结构的推广

11 3. 数组的基本运算是 : (1) 读 : 给定一组下标, 读取相应的数据元素 ; (2) 写 : 给定一组下标, 修改相应的数据元素 4. 矩阵的压缩存储 : 值相同的多个元素只分配一个存储空间, 零元素不分配空间 (1) 特殊矩阵 : 值相同的元素或零元素在矩阵中分布有一定的规律的矩阵 1) 对称矩阵 :: 在一个 n 阶的方阵 A 中, 元素满足 Aij=Aji 1<=i,j<=n; 称为对称矩阵元素的总数为 :n(n+1)/2; 2) 三角矩阵 : 以主对角线划分, 三角矩阵有上三角和下三角 ; 上三角的主对角线下元素均为常数 c; 下三角的主对角线上元素均为常数 c 元素总数为 :(n(n+1)/2)+1; (2) 稀疏矩阵 : 矩阵中零元素远远多于非零元素, 并且非零元素的分布没有规律的矩阵第六章树 1. 树 : 是 n 个结点的有限集 T,T 为空时称空树, 否则满足 : 1) 有且仅有一个特定的称为根的结点 ; 2) 其余结点可分为 m 个互不相交的子集, 每个子集本身是一棵树, 并称为根的子树 2. 树上任一个结点拥有的子树数称为该结点的度 ; 3. 一棵树的度是指树中结点最大的度数 4. 度为零的结点称叶子或终端结点 ; 度不为零的结点称分支结点或非终端结点 5. 根结点称开始结点, 根结点外的分支结点称内部结点 ; 6. 树中某结点的子树根称该结点的孩子 ; 该结点称为孩子的双亲 ; 7. 结点的层数从根算起, 若根的层数为 1, 则其余结点层数是其双亲结点层数加 1; 一棵树中所有结点层数的最大值称为树的高度或深度 ; 8. 树中的每个结点的子树不能更改其位置, 称为有序树 ; 反之称为无序树 9. 二叉树是结点的有穷集合, 它或者是空集, 或者同时满足下面两个条件 : (1) 有且只有一个称为根的结点 ; (2) 其余结点分为两个互不相交的集合 T1,T2,T1 和 T2 都是二叉树, 并且 T1,T2 有顺序关系 (T1 在 T2 前面 ), 它们分别称为根的左子树和右子树 10. 二叉树的特征 : 1 度不大于 2; 2 分左, 右分支 11. 度为 2 的有序树与二叉树的区别是 : 前者的子树次序是相对的, 而后者是绝对的 12. 二叉树的物种形态 : A. 空二叉树 B. 只含根的二叉树 C 只含左子树的二叉树 D. 只含右子树的二叉树 E. 同时有左右子树的二叉树 13. 二叉树的基本运算 :

12 1). 初始化 2). 求根 3) 求双亲 4) 求左孩子和右孩子 5) 建树 6) 剪枝 14. 二叉树的性质 : 1) 二叉树第 i(i 1) 层上至多有 2 i-1 个结点 2) 深度为 k(k 1) 的二叉树至多有 2 k -1 个结点 3) 对任何二叉树, 若 2 度结点数为 n 2, 则叶子数为 n 0=n 满二叉树是一棵深度为 k 的且有 2 k -1 个结点的二叉树 ; 16. 完全二叉树是在一棵深度为 k(k 1) 的满二叉树上删去第 k 层上最右边的连续 j(0 j 2 k -1) 个结点 17.. 具有 N 个结点的完全二叉树的深度为 log2n 取整加 1;( 二叉树的第四个性质 ) 18. 如果将一棵有 n 个结点的完全二叉树按层编号, 则对任意编号 i(1 i n) 的结点 X 有 : 1). 若 i=1, 则结点 X 是根 ; 若 i>1, 则 X 的双亲的编号为 i/2. 2). 若 2i>n, 则结点 X 无左孩子 ( 且无右孩子 ); 否则,X 的左孩子的编号为 2i 3). 若 2i+1>n, 则结点 X 无右孩子 ; 否则,X 的右孩子编号为 2i 二叉树中某一结点的左子树深度减去右子树的深度, 称为该结点的平衡因子 20. 二叉树的存储结构 (1) 链式存储结构 : 二叉链表结点的结构为 :l lchild data rchild ; 二叉链表由根指针唯一确定 (2) 顺序存储结构 : 把一棵有 n 个结点的完全二叉树, 从树根起自上而下从左到右对所有结点编号, 然后依次存储在一个一维数组 b[0~n] 中,b[1~n] 存放结点,b[0] 存放结点总数各个结点编号间的关系 : 1) i=1 是根结点 ;i>1 则双亲结点是 i/2 取整 ; 2) 左孩子是 2i, 右孩子是 2i+1;( 要小于 n) 3) i>(n/2 取整 ) 的结点是叶子 ; 4) 奇数没有右兄弟, 左兄弟是 i-1; 5) 偶数没有左兄弟, 右兄弟是 i+1; 21. 二叉树的遍历 : 就是按某种次序系统的访问二叉树上的所有结点, 是每个结点恰好被访问一次 22. 二叉树的遍历方式有 : 前序遍历中序遍历后序遍历时间复杂度为 O(n) B A A E C D F 图 1. 先根遍历 :ABCDEF 中根遍历 :CBDAEF 后跟遍历 :CDBFEA 23. 树的存储结构 : (1) 孩子链表表示法是树的一种链式存储结构 1) 孩子链表表示法的思想是 : 树上的一个结点的内容以及指向该结点所有的孩子的指针存储在一起以便于运算的实现 2) 一个孩子链表是一个带头结点的单链表, 单链表的头结点含有两个域 : 数据域和指针域 ( 以图 1 为例 ) 数据域指针域孩子域指针域

13 0 A 1 2 NULL 1 B 3 4 NULL 2 E 5 NULL 3 C 4 D 5 F (2) 孩子兄弟链表表示法: (3). 双亲表示法 : 24. 森林通常定义为树的集合 25. 树森林与二叉树的转换 (1) 树与二叉树的转换 : 1) 所有兄弟间连线 ; 2) 保留与长子的连线, 去除其它连线该二叉树的根结点的右子树必为空 (2) 森林与二叉树的转换 : 1) 将所有树转换成二叉树 ; 2) 将所有树根连线 26. 树和森林的遍历 : 前序遍历一棵树等价于前序遍历对应二叉树 ; 后序遍历等价于中序遍历对应二叉树 27. 从树中一个结点到另一个结点之间的分支, 构成这两个节点之间的路径 ; 路径上的分支的数目称为路径的长度 28. 结点上赋一个有实际意义的实数, 称此实数为根结点的权 29. 从根结点到根结点之间的路径长度于根结点上权的积称为结点的带权路径长度 30. 树中所有叶子结点的带权路径长度之和记做树的带权路径长度 31.n 个带权叶子结点构成的所有二叉树中, 带权路径长度最小的二叉树称为哈夫曼树 (HuFFman), 又叫最优二叉树 32. 对字符集进行编码时, 字符集中任一个编码都不是其他字符的编码的前缀, 称为前缀码第七章图 1. 图 : 图 G 由两个集合 V 和 E 组成, 记作 G=(V,E), 其中 V 是顶点的有穷非空集合,E 是边的集合, 而边是 V 中顶点的偶对 2. 若定点的偶对是有序的, 则称此图为有向图, 有序偶对用 <> 括起来 ; 若顶点偶对是无序的, 则称此图为无向图, 无序偶对用 () 括起来 3. 端点和邻接点 : 图中若存在有一条边 (V i,v j), 则称 V i,v j 为此边的两个端点, 并称他们为邻接点 4. 顶点的度, 入度, 出度 : 无向图中顶点的度定义为无向图中以该顶点为一个端点的边的数目 ; 有向图顶点的出度是以该顶点为起始点的边的数目 ; 入度是以该顶点为终点的边的数目 5. 顶点 n 与边数 e 的关系 : 无向图的边数 e 介于 0~n(n-1)/2 之间, 有 n(n-1)/2 条边的称无向完全图 ; 有向图的边数 e 介于 0~n(n-1) 之间, 有 n(n-1) 条边的称有向完全图 ; 6. 子图 : 设 G,H 是图, 若 V(H) 包含于 V(G),E(H) 包含于 E(G), 则称 H 是 G 的子图,G 是 H 的母图 ; 如果 H 是 G 的子图且 V(H)= V(G), 则称 H 为 G 的支撑子图 7. 可及和连通分量 : 从顶点 V i 到顶点 V j 若存在路径, 则称 V i 和 V j 可及 ; 在无向图的顶点集中任意两个顶点都可及, 则称此无向图为连通图 ;; 极大连通子图称连通分量 8. 在有向图中, 任意顺序两个顶点都有路径连通称强连通图 ; 极大连通子图称强连通分量 9. 权和网 : 为边赋一个具有某种意义的数值, 成这个数值为该边的权 ; 带权的图称为网 10. 一个连通图的生成树, 是含有该连通图的全部顶点的一个极小连通子图

14 11. 图的存储结构 :(P109) (1) 邻接矩阵表示法 : 邻接矩阵是表示顶点间相邻关系的矩阵 n 个顶点就是 n 阶方阵无向图是对称矩阵 ; 有向图行是出度, 列是入度 (2) 邻接表表示法 : 对图中所有顶点, 把与该顶点相邻接的顶点组成一个单链表, 称为邻接表,adjvex next, 如要保存顶点信息加入 data; 对所有顶点设立头结点,vertex firstarc, 并顺序存储在一个向量中 ; vertex 保存顶点信息,firstarc 保存邻接表头指针 12. 邻接矩阵表示法与邻接表表示法的比较 : 1) 邻接矩阵是唯一的, 邻接表不唯一 ; 2) 存储稀疏图用邻接表, 存储稠密图用邻接矩阵 ; 3) 求无向图顶点的度都容易, 求有向图顶点的度邻接矩阵较方便 ; 4) 判断是否是图中的边, 邻接矩阵容易, 邻接表最坏时间为 O(n); 5) 求边数 e, 邻接矩阵耗时为 O(n^2), 与 e 无关, 邻接表的耗时为 O(e+n); 13. 图的遍历 : (1). 图的深度优先搜索 : 假定图中某个顶点 V i 为出发点, 首先访问出发点, 然后任选一个 V i 的未访问过的邻接点 V j, 以 V j 为新的出发点继续进行深度优先搜索, 直到图中所有结点都被访问过 (2). 图的广度优先搜索 : 从图中某个顶点 V i 出发, 在访问了 V i 之后依次访问 V i 的所有邻接点, 然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点, 重复这一过程, 直至所有顶点都被访问到 14. 生成树中各边的权值和称为该树的树值 15. 权值最小的生成树称为图的最小生成树 16. 求最小生成树的方法 :( 书 P118) (1). 普里姆 (PRIM) 算法 : (2) 克鲁斯卡尔 (kruskal) 算法 : 17. 在有向图中, 顶点表示活动, 有向边表示活动之间的先后关系, 称这种关系为 A.O.V 网 18. 拓扑序列 :A.O.V 网中的所有顶点排成一个顺序序列, 使每个活动的所有前驱活动都排在该活动的前面 19. 构造 A.O.V 网拓扑序列的过程称为拓扑排序第八章排序 1. 文件 : 由一组记录组成, 记录有若干数据项组成, 唯一标识记录的数据项称关键字 ; 2. 排序是将文件按关键字的递增 ( 减 ) 顺序排列 ; 3. 排序文件中有相同的关键字时, 若排序后相对次序保持不变的称稳定排序, 否则称不稳定排序 ; 4. 在排序过程中, 文件放在内存中处理不涉及数据的内外存交换的称内排序, 反之称外排序 ; 5. 内排序的方法主要有 : 插入排序, 交换排序, 选择排序, 归并排序等四类 6. 常用的插入排序有 : 直接插入排序, 折半插入排序, 表插入排序和希尔排序 7. 直接插入排序 : 依次将每个记录插入到一个有序的子序列中去算法中引入监视哨 R[0] 的作用是 : 1) 保存 R[i] 的副本 ; 2) 简化边界条件, 防止循环下标越界关键字比较次数最大为 (n+2)(n-1)/2; 记录移动次数最大为 (n+4)(n-1)/2; 算法的最好时间是 O(n); 最坏时间是 O(n^2); 平均时间是 O(n^2); 是一种就地的稳定的排序 ; 8. 交换排序 : 将键值较大的记录向序列尾部移动, 键值较小的记录向序列的前部移动 (1). 冒泡排序 :

15 实现过程 : 从下到上相邻两个比较, 按小在上原则扫描一次, 确定最小值, 重复 n-1 次关键字比较次数最小为 n-1 最大为 n(n-1)/2; 记录移动次数最小为 0, 最大为 3n(n-1)/2; 算法的最好时间是 O(n); 最坏时间是 O(n^2); 平均时间是 O(n^2); 是一种就地的稳定的排序 ; (2). 快速排序 : 实现过程 : 将第一个值作为基准, 设置 i,j 指针交替从两头与基准比较, 有交换后, 交换 j,i i=j 时确定基准, 并以其为界限将序列分为两段重复以上步骤关键字比较次数最好为 nlog2n+nc(1) 最坏为 n(n-1)/2; 算法的最好时间是 O(nlog2n); 最坏时间是 O(n^2); 平均时间是 O(nlog2n); 辅助空间为 O(log2n); 是一种不稳定排序 ; 9. 选择排序 : (1) 直接选择排序实现过程 : 选择序列中最小的插入第一位, 在剩余的序列中重复上一步, 共重复 n-1 次关键字比较次数为 n(n-1)/2; 记录移动次数最小为 0, 最大为 3(n-1); 算法的最好时间是 O(n^2); 最坏时间是 O(n^2); 平均时间是 O(n^2); 是一种就地的不稳定的排序 ; (2) 堆排序实现过程 : 把序列按层次填入完全二叉树, 调整位置使双亲大于或小于孩子, 建立初始大根或小根堆, 调整树根与最后一个叶子的位置, 排除该叶子重新调整位置算法的最好时间是 O(nlog2n); 最坏时间是 O(nlog2n); 平均时间是 O(nlog2n); 是一种就地的不稳定排序 ; 9. 归并排序 : 要求待排序列部分有序 (1). 部分有序的含义是待排序列由若干个有序的子序列组成 (2). 基本是想 : 将这些有序的子序列进行合并, 从而得到有序的序列 (3). 方法 : 比较各子序列的第一个记录的键值, 最小的一个就是排列后序列的第一个记录的键值取出这些记录, 继续比较各子序列现在的第一个记录的键值, 便可以找出排序后的第二个记录如此继续下去, 最终得到排序结果因此, 归并的基础是合并 10. 二路归并排序 : 实现过程 : 如果序列中有 n 个记录, 可以把它看成 n 个子序列, 每个子序列中只包含一个记录先将每相邻的两个子序列合并, 得到 (n/2) 个较大的有序子序列, 每个子序列包含 2 个记录再将这些子序列两两合并, 得到 ((n/2) /2) 个有序子序列如此反复, 直到最后合并成一个有序序列第九章查找 1. 查找表是一种以集合为逻辑结构, 以查找为核心运算, 同时包括其他运算的数据结构 2. 由任意一些可辨认的对象构成的整体称为集合 3. 集合与其他逻辑结构 ( 线性结构, 树状结构, 图状结构 ) 的根本区别 : 在集合这种逻辑结构中, 任何结点之间都不存在逻辑关系这也是集合这种逻辑结构的基本特点 4.. 查找的同时对表做修改操作 ( 如插入或删除 ) 则相应的表称之为动态查找表, 否则称之为静态查找表 5. 二分查找 ( 又称折半查找 ), 它的算法思想 : 是对一有序表中的元素, 从初始的查找区间开始, 每经过一次与当前查找区间的中点位置上的结点关键字进行比较, 若相等, 则查找成功, 否则, 当前查找区间的缩小一半, 按 k 值大小在某半个区间内重复相同的步骤进行查找, 直到查找成功或失败为止 1) 二分查找在等概率的情况下查找成功的平均查找长度 ASL 为 lg(n+1)-1, 在查找失败时所需比较的关键字个数不超过判定树的深度, 最坏情况下查找成功的比较次数也不超过判定树的深度 lg(n+1) ( 不小于 lg(n+1)

16 的最小整数 ) 2) 二分查找只适用于顺序存储结构而不能用链式存储结构实现因为链表无法进行随机访问, 如果要访问链表的中间结点, 就必须先从头结点开始进行依次访问, 这就要浪费很多时间, 还不如进行顺序查找, 而且, 用链存储结构将无法判定二分的过程是否结束, 因此无法用链表实现二分查找 6. 二叉排序树 (BST) 又称二叉查找树, 其定义是 : 二叉排序树要或者是空树或者满足如下性质的二叉树 : 1) 若它的左子树非空, 则左子树上所有结点的值均小于根结点的值 ; 2) 若它的右子树非空, 则右子树上所有结点的值均大于根结点的值 ; 3) 左右子树本身又是一棵二叉排序树

Microsoft Word - 专升本练习5：图.doc

Microsoft Word - 专升本练习5：图.doc 第五章图一选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e