算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第2章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第2章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章基本数据结构2.1链表2.2堆栈和队列2.3树2.4图2.1链表数组：元素顺序存储2.1链表数组：元素顺序存储存储效率高、存取速度快不便于元素的增加和删除a1a2a0a3a4…2.1链表数组：元素顺序存储存储效率高、存取速度快不便于元素的增加和删除链表：元素链式存储存储利用率不高便于元素的增加和删除a1a2a0a3a4…a1a0a2a4a3…2.1.1普通链表链表节点类型定义链表类型定义typeLinkedNodebeginvalue:int;next:LinkedNode;endtypeLinkedListbe

2、ginhead,current:LinkedNode;count,r:int;IsEmpty():bool;Move(i:int);Get(i:int):int;Set(i,v:int);end2.1.1普通链表链表节点类型定义链表类型定义typeLinkedNodebeginvalue:int;next:LinkedNode;endtypeLinkedListbeginhead,current:LinkedNode;count,r:int;IsEmpty():bool;Move(i:int);Get(i:int):i

3、nt;Set(i,v:int);Add(v:int);Insert(i,v:int);Remove(i:int);end2.1.1普通链表追加操作…headcurrent2.1.1普通链表追加操作a1a0headcurrentcurrent.nextnewLinkedNode(value=v,next=null);2.1.1普通链表追加操作a1a0headcurrentcurrent.nextnewLinkedNode(value=v,next=null);2.1.1普通链表追加操作插入操作a1a0a2headcu

4、rrent2.1.1普通链表追加操作插入操作a1a0a2headcurrentletp=current.next;current.nextnewLinkedNode(value=v,next=p);2.1.1普通链表追加操作插入操作删除操作a1a0a2headcurrent2.1.1普通链表追加操作插入操作删除操作a1a0a2headcurrentcurrent.nextcurrent.next.next;2.1.2泛型链表泛型链表节点类型定义泛型链表类型定义typeLinkedNodebeginvalue:

5、T;next:LinkedNode;endtypeLinkedListbeginhead,current:LinkedNode;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);end2.1.3双向链表泛型链表节点类型定义泛型链表类型定义typeBiLinkedNodeinheritsLinkedNodebeginprev

6、:LinkedNode;endtypeBiLinkedListinheritsLinkedListbeginMove(i:int)begin…endend2.2堆栈和队列堆栈：先进后出a4a3a2a1a02.2堆栈和队列堆栈：先进后出a4a3a2a1a0typeStackbeginsize,count:int;elements:T[];Pop():T;Peek():T;Push(item:T);end2.2堆栈和队列堆栈：先进后出队列：先进先出a4a3a2a1a02.2堆栈和队列堆栈：先进后出队

7、列：先进先出a4a3a2a1a0typeQueuebeginsize,count:int;elements:T[];Dequeue():T;Peek():T;Enqueue(item:T);end2.2堆栈和队列堆栈：先进后出队列：先进先出优先级队列:顺序入队，高优先级先出队35482typePriQueuebeginsize,count:int;elements:T[];Dequeue():T;Peek():T;Enqueue(item:T);end2.3树普通树根节点子节点叶节点2.3树普通树typeT

8、reeNodebeginvalue:T;children:LinkedList>;end2.3树二叉树typeTreeNodebeginvalue:T;left,right:BTreeNode;end2.3树二叉树满二叉树完全二叉树2.3树堆元素类型可比较任一节点值均不大于其子节点的值2.