算法设计（第2章基本的 数据结构）.pptVIP

第2章 基本数据结构 2.1 链表 2.2 堆栈和队列 2.3 树 2.4 图 2.1 链表 数组：元素顺序存储 2.1 链表 数组：元素顺序存储 存储效率高、存取速度快 不便于元素的增加和删除 a1 a2 a0 a3 a4 … 2.1 链表 数组：元素顺序存储 存储效率高、存取速度快 不便于元素的增加和删除 链表：元素链式存储 存储利用率不高 便于元素的增加和删除 a1 a2 a0 a3 a4 … a1 a0 a2 a4 a3 … 2.1.1 普通链表 链表节点类型定义 链表类型定义 type LinkedNode begin value: int; next: LinkedNode; end type LinkedList begin head, current: LinkedNode; count, r: int; IsEmpty(): bool; Move(i: int); Get(i: int): int; Set(i, v: int); end 2.1.1 普通链表 追加操作 a1 a0 head current current.next ? new LinkedNode(value=v, next=null); 2.1.1 普通链表 追加操作 a1 a0 head current current.next ? new LinkedNode(value=v, next=null); 2.1.1 普通链表 追加操作 插入操作 a1 a0 a2 head current 2.1.1 普通链表 追加操作 插入操作 a1 a0 a2 head current let p = current.next; current.next ? new LinkedNode(value=v, next=p); 2.1.1 普通链表 追加操作 插入操作 删除操作 a1 a0 a2 head current 2.1.1 普通链表 追加操作 插入操作 删除操作 a1 a0 a2 head current current.next ? current.next.next; 2.1.2 泛型链表 泛型链表节点类型定义 泛型链表类型定义 type LinkedNodeT begin value: T; next: LinkedNodeT; end type LinkedListT begin head, current: LinkedNodeT; count, r: int; IsEmpty(): bool; Move(i: int); Get(i: int): int; Set(i: int; v: T); Add(v: T); Insert(i: int; v: T); Remove(i: int); end 2.1.3 双向链表 泛型链表节点类型定义 泛型链表类型定义 type BiLinkedNodeT inherits LinkedNodeT begin prev: LinkedNodeT; end type BiLinkedListT inherits LinkedListT begin Move(i: int) begin … end end 2.2 堆栈和队列 堆栈：先进后出 a4 a3 a2 a1 a0 2.2 堆栈和队列 堆栈：先进后出 a4 a3 a2 a1 a0 type StackT begin size, count: int; elements: T[]; Pop(): T; Peek(): T; Push(item: T); end 2.2 堆栈和队列 堆栈：先进后出 队列：先进先出 a4 a3 a2 a1 a0 2.2 堆栈和队列 堆栈：先进后出 队列：先进先出 a4 a3 a2 a1 a0 type QueueT begin size, count: int; elements: T[]; Dequeue(): T; Peek(): T; Enqueue(item: T); end 2.2 堆栈和队列 堆栈：先进后出 队列：先进先出 优先级队列: 顺序入队，高优先级先出队 3 5 4 8 2 type PriQueueT begin size, count: int; elements: T[]; Dequeue(): T; Peek(): T; Enqueue(item: T); end 2.3 树 普通树 根节点 子节点 叶节点