数据结构 : 线性表 Data Structure 2016 年 3 月 15 日星期二 1
线性表 栈和队列 线性表 字典 ADT 栈 队列 2016 年 3 月 15 日星期二 2
线性表 定义 : 线性表 L 是 n 个数据元素 a 0,a 1, a n-1 的有限序列, 记作 L=(a 0,a 1, a n-1 ) 其中元素个数 n(n 0) 定义为表 L 的长度 当 n=0 时,L 为空表, 记作 ( ) 特性 : 在表中, 除第一个元素 a 0 外, 其他每一个元素 a i 有一个且仅有 一个直接前驱 a i-1 除最后一个元素 a n-1 外, 其他每一个元素 a i 有一个且仅有一个直接后继 a i+1 a 0 为第一个元素, 又称为表 头元素 ; a n-1 为最后一个元素, 又称为表尾元素 2016 年 3 月 15 日星期二 3
线性表的抽象数据类型 (ADT) template <typename E> class List { public: List() { virtual ~List() { virtual void clear()=0; virtual void insert(const E& item)=0; virtual void append(const E& item)=0; virtual E remove()=0; virtual void movetostart()=0; virtual void movetoend()=0; virtual void prev()=0; virtual void next()=0; virtual int length() const=0; virtual int currpos() const=0; virtual void movetopos(int pos)=0; virtual bool getvalue(elem&) const=0; virtual const E& getvalue() const=0; 2016 年 3 月 15 日星期二 4
顺序表的实现 采用连续的存储单元依次存储线性表中各元素 我们称这种存储方式为顺序存储方式, 按这种存储方式所得到的线性表叫顺序表 顺序表具有这样的一个特点 : 逻辑上相邻的元素在物理上一定相邻 2016 年 3 月 15 日星期二 5
顺序表类的定义 template <typename E> class AList :public List<E> { private: int maxsize; int listsize; int curr; E* listarray; public: 2016 年 3 月 15 日星期二 6
顺序表类成员函数的实现 顺序表结点插入操作 void insert(const E& it) { Assert (listsize<maxsize, List capacity exceeded ) ;// 边界检查 for (int i=listsize;i>curr;i--) // 移位 listarray[i]=listarray[i-1]; listarray[curr]=it; listsize++; 2016 年 3 月 15 日星期二 7
顺序表的插入图示 k 0 k 1 k 0 k 1 k 0 k 1 position k 2 k 3 k 4 position k 2 k 3 position k 2 x k 3 k 5 k 6 k 4 k 5 k 4 k 5 k 6 k 6 8 2016 年 3 月 15 日星期二 8
顺序表结点删除操作 E remove() { Assert ((curr>=0) &&(curr<listsize), No element );// 边界检查 E it=listarray[curr]; for (int i=curr;i<listsize-1;i++) // 移位 listarray[i]=listarray[i+1]; listsize--; return it; 2016 年 3 月 15 日星期二 9
顺序表的删除图示 k 0 k 0 k 1 k 1 position k 2 position k 2 k 3 k 4 k 4 k 5 k 5 k 6 k 6 10 2016 年 3 月 15 日星期二 10
链表 特点 : 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻 的元素 每个数据元素 ai, 除存储本身信息外, 还需存储其直 接后继的信息 结点 数据域 : 元素本身信息 指针域 : 指示直接后继的存储位置 结点数据域指针域 2016 年 3 月 15 日星期二 11
链表 template <typename E> class Link { public: E element; // value for this node Link *next; // Pointer to next node in list Link(const E& elemval, Link* nextval=null) { element=elemval; next=nextval; Link(link* nextval=null) { next=nextval; 2016 年 3 月 15 日星期二 12
单链表类 template <typename E> class LList :public List<E> { private: Link<E>* head; Link<E>* tail; Link<E>* curr; int cnt; void init(){ curr=tail=head=new Link<E>; cnt=0; void removeall(){ while (head!=null) { curr=head; head=head->next; delete curr; 2016 年 3 月 15 日星期二 13
单链表类 public: LLlist(int size=defaultlistsize){init(); ~LList(){removeall(); void clear(){removeall();init(); bool insert(const E& it); bool append(const E& it); E remove(); void movetostart() {curr=head; void movetoend() {curr=tail; void prev(); void next(); int length() const {return cnt; int currpos() const; void movetopos(int pos); const E& getvalue() const; 2016 年 3 月 15 日星期二 14
单链表的结点插入 void insert(const E& it) { curr->next=new link<e>(it, curr->next); if (tail == curr) tail =curr->next; cnt++; 创建新的结点并且赋给新值 new link<e>(it, curr->next); 当前结点元素前驱的 next 域要指向新插入的结点 curr->next=new link<e>(it, curr->next); 2016 年 3 月 15 日星期二 15
单链表的插入 head tail 20 23 12 15 在 23 和 12 之间插入 10 head tail 10 20 23 12 15 1. 创建新结点 2. 新结点指向右边的结点 3. 左边结点指向新结点 16 2016 年 3 月 15 日星期二 16
单链表结点的删除 E remove() { Assert(curr->next!=NULL, No element ); E it =curr->next->element; link<e>* ltemp =curr->next; if (tail == ltemp) tail =curr; curr->next =curr->next->next; delete ltemp; cnt--; return it; 2016 年 3 月 15 日星期二 17
单链表删除示意 head p. x. 用 p 指向元素 x 的结点, 可以吗? x. p 18 2016 年 3 月 15 日星期二 18
删除值为 x 的结点 q p p q = p next; p next = q next; free(q); x 19 2016 年 3 月 15 日星期二 19
循环链表 循环链表是表中最后一个结点的指针指向头结点, 使链表构成环状 特点 : 从表中任一结点出发均可找到表中其他结点, 提高查找效率 操作与单链表基本一致, 循环条件不同 单链表 p:p->link=null 循环链表 p:p->link=h h 空表 h 2016 年 3 月 15 日星期二 20
双链表 双向链表是指在前驱和后继方向都能遍历的线性链 表 双向链表每个结点结构 : prev ( 左链指针 ) element ( 数据 ) nextt ( 右链指针 ) 前驱方向 后继方向 双向链表通常采用带表头结点的循环链表形式 2016 年 3 月 15 日星期二 21
双链表 非空表 空表 结点指针的指向 p == p llink rlink == p rlink llink 2016 年 3 月 15 日星期二 22
双链表结点 template <typename E> class link { private: static Link<E> *freelist; public: E element; Link* next; Link* prev; Link(const E& it, Link* prevp, Link* nextp) { element=it; prev=prevp; next=nextp; Link(Link* prevp=null,link* nextp=null) { prev=prevp;next=nextp; void* operator new(size_t); void operator delete(void*); 2016 年 3 月 15 日星期二 23
双链表插入示意 p p next k i-1 k i k i+1 q q prev = p; x q next = p next; p next prev = q; p next = q; 24 2016 年 3 月 15 日星期二 24
双链表的插入 void insert(const E& it) { curr->next=curr->next->prev =new Link<E>(it,curr,curr->next); cnt++; 2016 年 3 月 15 日星期二 25
双链表删除示意 p prev p p next k i-1 k i k i+1 prev next p prev next = p next p next prev = p prev 26 2016 年 3 月 15 日星期二 26
双链表的删除 E remove() { if (curr->next==tail) return NULL; E it =curr->next->element; link<e>* ltemp =curr->next; curr->next->next->prev=curr; curr->next= curr->next->next; delete ltemp; cnt--; return it; 2016 年 3 月 15 日星期二 27
线性表实现方法的比较 顺序表 插入 删除运算时间代价 O(n) 预先申请固定长度的数组 如果整个数组元素很满, 则没有结构性存储开销链表 插入 删除运算时间代价 O(1) 但找第 i 个元素删除运算时间 代价 O(n) 存储利用指针, 动态地按照需要为表中新的元素分配存储 空间 每个元素都有结构性存储开销 2016 年 3 月 15 日星期二 28
顺序表和链表存储密度的临界值 n 表示线性表中当前元素的数目, P 表示指针的存储单元大小小 ( 通常为 4 个字节 ) E 表示数据元素的存储单元大小 D 表示可以在数组中存储的线性表元素的最大数目 空间需求 顺序表的空间需求为 DE 链表的空间需求为 n(p+e) n 的临界值, 即 n>de/(p+e) n 越大, 顺序表的空间效率就更高 如果 P=E, 则临界值为 n=d/2 2016 年 3 月 15 日星期二 29
根据应用选择顺序表和链表 顺序表 结点总数目大概可以估计 线性表中结点比较稳定 ( 插入删除操作少 ) n>de/(p+e) 链表 结点数目无法预知 线性表中结点动态变化 ( 插入删除多 ) n<de/(p+e) 2016 年 3 月 15 日星期二 30
栈 (stack) 只允许在一端插入和删除的线性表 允许插入和删除的一端称为栈顶 (top), 另一端称为栈底 (bottom) 特点后进先出 (LIFO) 主要操作 入栈 (push) 出栈(pop) 取栈顶元素 (topvalue) 判栈空 (isempty) 2016 年 3 月 15 日星期二 31
顺序栈 template <typename E> class AStack :public Stack<E> { private: int maxsize; int top; E *listarray; public: AStack(int size =DefaultListSize) { maxsize =size; top =0; listarray =new E [size]; ~AStack() {delete [] listarray; void clear() {top = 0; int length() const {return top; 2016 年 3 月 15 日星期二 32
进栈 出栈算法 void push(const E& it) { Assert (top!=maxsize, Stack is full ); listarray[top++] =it; E pop() { Assert (top!=0, Stack is empty ); return listarray[--top]; Const E& topvalue() const {Assert (top!=0, Stack is empty ); return listarray[top-1]; 2016 年 3 月 15 日星期二 33
进栈示例 2016 年 3 月 15 日星期二 34
出栈示例 2016 年 3 月 15 日星期二 35
链式栈 template < typename E > class LStack :public Stack<E> { private: link<e> * top; int size; public: LStack(int sz =DefaultListSize){top = NULL; size=0; ~LStack() { clear(); void clear(){ while (top!=null) {Link<E>*temp=top;top=top->next; delete temp; size=0; 2016 年 3 月 15 日星期二 36
进栈 出栈算法 void push(const E& it) {top =new Link<E>(it, top);size++; E pop(){ Assert (top!=null, Stack is empty ); E it=top->element; Link<E>* ltemp=top->next; delete top; top=ltemp; size--;return it; Const E& topvalue() const { Assert (top!=null, Stack is empty ); return top->element; int length() const {return size; 2016 年 3 月 15 日星期二 37
过程的嵌套调用 r 主程序 r s 子过程 1 s r t 子过程 2 t s r 子过程 3 r s r 2016 年 3 月 15 日星期二 38
递归过程及其实现 例递归的执行情况分析 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i<=w;++i) printf( %3d,,w); printf( /n ); 运行结果 : 1, 2,2, 3,3,3, 2016 年 3 月 15 日星期二 39
递归调用执行情况如下 : (1) 主程序 w=3; print(w) w 3 print(2); (2) 输出 :3, 3, 3 w 2 print(1) ; (3) 输出 :2, 2 w 1 print(0); (4) 输出 :1 w 0 返回 结束 top (1)w=3 (1 ) 3 top (2)w=2 (2) 2 (1)w=3 (1) 3 top (3)w=1 (3) 1 (2)w=2 (2) 2 (1)w=3 (1) 3 top top (4)w=0 (4) 0 (3)w=1 (3) 1 (2)w=2 (2) 2 (1)w=3 (1) 3 2016 年 3 月 15 日星期二 40
Tower of Hanoi 问题 问题描述 : 有 A,B,C 三个塔座,A 上套有 n 个直径不同的圆盘, 按直径从小到大叠放, 形如宝塔, 编号 1,2,3 n 要求将 n 个圆盘从 A 移到 C, 叠放顺序不变, 移动过程中遵循下列原则 : 每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻, 每个塔座上不能将大盘压到小盘上 2016 年 3 月 15 日星期二 41
Tower of Hanoi 问题 解决方法 : n=1 时, 直接把圆盘从 A 移到 C n>1 时, 先把上面 n-1 个圆盘从 A 移到 B, 然后将 n 号盘从 A 移到 C, 再将 n-1 个盘从 B 移到 C 即把求解 n 个圆盘的 Hanoi 问题转化为求解 n-1 个圆盘的 Hanoi 问题, 依次类推, 直至转化成只有一个圆盘的 Hanoi 问题 2016 年 3 月 15 日星期二 42
Tower of Hanoi 算法 enum TOHop {DOMOVE,DOTOH; class TOHobj{ public: TOHop op; int num; Pole start,goal,tmp; TOHobj(int n,pole s,pole g,pole t) { op=dotoh;num=n; start=s;goal=g;tmp=t; TOPobj(Pole s,pole g) {op=domove;start=s;goal=g; 2016 年 3 月 15 日星期二 43
Tower of Hanoi 算法 void TOH(int n,pole start,pole goal,pole temp) { if (n==0) return; else { TOH(n-1,start,temp,goal); move(start,goal); TOH(n-1,temp,goal,start); 2016 年 3 月 15 日星期二 44
Tower of Hanoi 算法 void TOH(int n,pole start,pole goal,pole tmp,stack<tohobj*>& S) { S.push(new TOHobj(n,start,goal,goal,tmp)); TOHobj* t; while (S.length()>0) { t=s.pop(); if (t->op==domove) move(t->start,t->goal); else if (t->num>0) { int num=t->num;pole tmp=t->tmp;pole goal=t->goal; Pole start=t->start; S.push(new TOHobj(num-1,tmp,goal,start)); S.push(new TOHobj(start,goal)); S.push(new TOHobj(num-1,start,tmp,goal)); delete t; 2016 年 3 月 15 日星期二 45
递归函数示例 2016 年 3 月 15 日星期二 46
数学公式 2016 年 3 月 15 日星期二 47
函数调用及返回的步骤 调用 保存调用信息 ( 参数, 返回地址 ) 分配数据区 ( 局部变量 ) 控制转移给被调函数的入口 返回 保存返回信息 释放数据区 控制转移到上级函数 ( 主调用函数 ) 2016 年 3 月 15 日星期二 48
队列 ( Queue ) 只允许在一端插入, 在另一端删除的线性表 允许插入一端称为队尾 (rear), 另一端称为队首 (front) 特点先进先出 (FIFO) 主要操作 入队 (enqueue) 出队(dequeue) 取队首元素 (frontvalue) 2016 年 3 月 15 日星期二 49
顺序队列 ( Queue ) 顺序队列 顺序循环队列 2016 年 3 月 15 日星期二 50
实现 : 用一维数组实现 sq[m] front=-1 rear=-1 队空 5 4 3 rear 2 J3 rear 1 J2 rear 0 J1 front J1,J1,J3 入队 5 5 4 4 3 3 rear 2 J3 2 front J2 1 front 1 0 front J1 0 front J1,J2,J3 出队 rear front J6 J5 J4 5 4 3 2 1 0 J4,J5,J6 入队 设两个指针 front,rear, 约定 : rear 指示队尾元素 ; front 指示队头元素前一位置初值 front=rear=-1 空队列条件 :front==rear 入队列 :sq[++rear]=x; 出队列 :x=sq[++front]; 2016 年 3 月 15 日星期二 51
存在问题 rear 设数组维数为 M, 则 : 当 front=-1,rear=m-1 时, 再有元素入队发生溢出 真溢出 当 front -1,rear=M-1 时, 再有元素入队发生溢出 假溢出 解决方案 队首固定, 每次出队剩余元素向下移动 浪费时间 循环队列 基本思想 : 把队列设想成环形, 让 sq[0] 接在 sq[m-1] 之后, 若 rear+1==m, 则令 rear=0; front M-1 0 1 实现 : 利用 模 运算 入队 : rear=(rear+1)%m; sq[rear]=x; 出队 : front=(front+1)%m; x=sq[front]; 队满 队空判定条件 2016 年 3 月 15 日星期二 52
队空 :front==rear 队满 :front==rear 4 5 0 front rear J5 rear 3 2 1 J4 4 5 0 J6 3 2 1 front J5 初始状态 J4 J9 4 3 5 2 0 1 J6 J7 解决方案 : 1. 另外设一个标志以区别队空 队满 2. 少用一个元素空间 : 队空 :front==rear 队满 :(rear+1)%m==front front rear J8 2016 年 3 月 15 日星期二 53
顺序队列类的实现 template <typename E> class Aqueue:public Queue<E> { private: int maxsize; int front; int rear; E *listarray; public: AQueue(int size =DefaultListSize) { maxsize = size+1; front =1; rear = 0; listarray = new E [maxsize]; ~AQueue() { delete [] listarray; void clear() {front =1; rear = 0; 2016 年 3 月 15 日星期二 54
顺序队列类的实现 void enqueue(const E& it) { Assert (((rear+2)%maxsize)!=front, Queue is full ); rear=(rear+1)%maxsize; listarray[rear]=it; E dequeue(){ Assert (length()!=0, Queue is empty ); E it=listarray[front]; front=(front+1)%maxsize; return it; 2016 年 3 月 15 日星期二 55
顺序队列类的实现 const E& frontvalue() const { Assert (length()!=0, Queue is empty ); return listarray[front]; virtual int length() const { return ((rear+maxsize)-front+1)%maxsize; ; 2016 年 3 月 15 日星期二 56
链式队列 front 头结点 队头... 队尾 ^ 设队首 队尾指针 front 和 rear, front 指向头结点,rear 指向队尾 rear 2016 年 3 月 15 日星期二 57
链式队列类的实现 template <typename E> class LQueue:public Queue<E> { private: Link<E> *front; Link<E> *rear; int size; public: LQueue(int sz=defaultlistsize) { front = rear = new Link<E>(), size=0; ~LQueue() { clear(); delete front; 2016 年 3 月 15 日星期二 58
链式队列类的实现 void clear() { while (front ->next!= NULL) { rear = front;front = front->next;delete rear; rear = front;size=0; void enqueue(const E& it) { rear->next=new Link<E>(it, NULL); rear = rear->next; size++; 2016 年 3 月 15 日星期二 59
链式队列类的实现 E dequeue() { Assert (size!=0, Queue is empty ); E it=front->next->element; Link<E> *ltemp=front->next; front ->next= ltemp->next; if (rear == ltemp) rear = front; delete ltemp; size--; return it; 2016 年 3 月 15 日星期二 60
链式队列类的实现 const E& frontvalue() const { Assert (size!=0, Queue is empty ); return front->next->element; virtual int length() const {return size; ; 2016 年 3 月 15 日星期二 61
Thank you!!! 2016 年 3 月 15 日星期二 62