北京大学：《数据结构与算法》课程教学资源（实验班讲义）第二章 线性表、栈和队列

资源提示 第二章线性表、栈和队列 作业提交ftp更改 张铭 idsQZproi@fusion grids,cn http:/db.pku.edu.cn/mzhang/dsl 讲义和作业发布不变 北京大学信息科学与技术学院 数据结构与算法教学小组 ■实习课讲义和作业发布 tp: db. pku. edu. cn/mzhang/DS/shixi L 版权所有,转载或印必究 北大举张铭写 意叔有 大纲 线性结构分类 21线性表( linear list) 端他储 22顺序表一向量( Sequential list vector 访问型 23链表 Linked list 24线性表实现方法的比较 25栈( Stack) 26队列( Queue) 顺序文件 中ac 匙盒大管皇歌张节写 新有,聊邮究 21线性表( linear list) 逻辑定义:由结点集N,以及定义在结点集N class list/线性表类模板lst,棋板参数ELEM 的线性关系r所组成的线性结构 结点:线性表的元囊 istO;∥创建一个空的新性表 唯一的起点:没有前驱,有一个唯一的后继 ∥从计算机存储空间删去薹个性表 唯一的终点:有一个唯一的前驱而没有后继 void clear;∥将该线性表的全部元素清除,成为空表 内部结点:有唯一的前驱,唯一的后继 结点个数:线性表的长度 void insert(int L, ELEM value);∥入画数,在第位插入 线性表的关系r,简称前驱关系 oid remove(intj;∥删除画教,删去第号元 反对称性、传递性 6 ack -EM fetch(int/取,返回第个元素的值 北盒大带皇歌张帖习 北真大物张帖写

1 第二章 线性表、栈和队列 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 back next 资源提示 作业提交ftp更改 „ 实验班作业提交 ftp://ds_honor:ds07honor@fusion.grids.cn „ 实习课作业提交 ftp://ds_proj:ds07proj@fusion.grids.cn 讲义和作业发布不变 „ 实验班讲义和作业发布（包括实习作业） http://db.pku.edu.cn/mzhang/ds/honor/ „ 实习课讲义和作业发布 http://db.pku.edu.cn/mzhang/DS/shixi/ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 back next 大纲 „ 2.1 线性表(linear list) „ 2.2 顺序表—向量(Sequential list— vector ) „ 2.3 链表(Linked list) „ 2.4 线性表实现方法的比较 „ 2.5 栈(Stack) „ 2.6 队列(Queue) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 back next 线性结构分类 线性结构 直接访问型 顺序访问型 目录索引型 向 量 记 录 字 典 散列表 栈 队 列 顺序文件 广义表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 back next 2.1 线性表(linear list) „ 逻辑定义：由结点集N，以及定义在结点集N 上的线性关系r所组成的线性结构 „ 结点：线性表的元素 „ 唯一的起点：没有前驱，有一个唯一的后继 „ 唯一的终点：有一个唯一的前驱而没有后继 „ 内部结点：有唯一的前驱，唯一的后继 „ 结点个数：线性表的长度 „ 线性表的关系r，简称前驱关系 „ 反对称性、传递性 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 back next template class list //线性表类模板list，模板参数ELEM { list(); // 创建一个空的新线性表 ~list(); // 从计算机存储空间删去整个线性表 void clear() ; // 将该线性表的全部元素清除，成为空表 void append(ELEM value) ; // 尾附函数，在表尾加新元素 void insert(int i, ELEM value) ; // 插入函数，在第i号位插入 void remove(int i); // 删除函数，删去第i号元素 ELEM fetch(int i); //读取，返回第i个元素的值 }

顺序表类定义 2.2顺序表一向量 onst int Max length=100;∥假定最大长度为100 用定长的一维数组存储结构 ■主要特性: ∥顺序最大长度 t curr len;∥顺序表当前长度 元素的类型相同 ELEM* nodelist;∥私有变量,存储顺序表实例的向量 元素顺序地存储在连续存储空间 以下列出成员函数〔顺序表的函数集) 中 int curr;∥当前下标,顺序表的公共变量 list(const int size);∥ constructor函数创建新表 ■通过下标读写即可指定位置元素 ∥ destructor函数,将该表实例删去 id clear0;/清除内容,成为空表 新有,食究 北大举张铭写 意叔有 k-1 mske oid setFirst0;∥第一个元素位量赋予当前下标curr nodelist oid nexto ∥urr下移一格,即curr+1 miZ void prev(: 将cu上移一格,即cur-1 bool islnListo;∥若curr位量有值时,返回 (a)在t位置插入元素item oid append( onst EleM&);∥在表尾增添新元素 void insert(const ELEM&);∥在当前下标cur插入 ELEM remove0;/返回curr的位置元章值,并删除 maize bool is Empty 肖线性表为空时,返回true ELEM curr Value0; ∥返回ur位的元素值 ∥返回此表的当前实际长度 中ad (b)删除t位置的元素 匙盒大管皇歌张节写 新有,聊邮究 插入算法执行时间 删除算法时间代价 元素总个数为n,各个位置插入 与插入操作相似,O(m) 的概率相等为p=1/n ■平均移动元素次数为 顺序表存取元素方便,时间代价 为O(1) ∑1/n·(n-1) 但插入、删除操作则付出时间代 价O(m) ■总时间开销估计为O(n) back 真大带酱张储 北大管息歌张帖习

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 back next 2.2 顺序表—向量 „ 采用定长的一维数组存储结构 „ 主要特性: „ 元素的类型相同 „ 元素顺序地存储在连续存储空间 中 „ 通过下标读写即可指定位置元素 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 back next 顺序表类定义 const int Max_length = 100; // 假定最大长度为100 class list { // 顺序表，向量 private : int msize; // 顺序表最大长度 int curr_len; // 顺序表当前长度 ELEM* nodelist; //私有变量，存储顺序表实例的向量 public: //以下列出成员函数（顺序表的函数集) int curr; //当前下标，顺序表的公共变量 list(const int size) ; // constructor函数,创建新表 ~list(); //destructor函数，将该表实例删去 void clear(); //清除内容，成为空表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 back next void setFirst(); // 第一个元素位置赋予当前下标curr void next(); // curr下移一格，即curr+1 void prev(); //将curr上移一格，即curr-1 bool isInList(); // 若curr位置有值时，返回true void append(const ELEM&); //在表尾增添新元素 void insert(const ELEM&); // 在当前下标curr插入 ELEM remove(); //返回curr的位置元素值，并删除 bool isEmpty(); //当线性表为空时，返回true ELEM currValue(); //返回curr位置的元素值。 int length(); // 返回此表的当前实际长度 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 back next nodelist nodelist i 0 1 t k-1 msize i 0 1 t k msize nodelist nodelist i 0 1 t k-2 msize i 0 1 t k-1 msize (a) 在 t 位置插入元素item (b) 删除 t 位置的元素 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 back next 插入算法执行时间 „ 元素总个数为n，各个位置插入 的概率相等为p＝1/n „ 平均移动元素次数为 „ 总时间开销估计为O（n） n-1 i 0 1/ ( - ) 2 n n ni = ∑ • ≈ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 back next 删除算法时间代价 „ 与插入操作相似，O(n) „ 顺序表存取元素方便，时间代价 为O(1) „ 但插入、删除操作则付出时间代 价O(n)

23链表( inked list 令单链表 first指向特殊的头结点 双链表 ■引入头结点有利于特殊情况的处理 ①循环链表 空链表 链表头 i按照c/C++数组下标编号的规则 从0到n-1 链表的第0个结点为frst>link 真太血张写 大血张體 新有食究 单链表的存储结构 单链表结点类型以及变量说明 单链表 struct ListNode f{a{aa-…tamz eleM data 空的单链衰 istNode link data字段 link字段 typedef ListNode listPtr; ListPtr first, las 中ack bacK 真太张铭写 北盒大管血歌张写 新究 单链表插入算法 不带头结点vs带头结点 插入数据内容为 value的新结点,为第个结 istNode* Insert(ELEM value, int i)i 2四212sz p= FindIndex(i-l) 0位121 if (p- NULL )return NULL q· new List 口圆回 q->link- NULL) 不带头结点带头结点 return q: 120231012i Back 真大带酱张储 新有,种究 北大管息歌张帖习

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 back next 2.3 链表(linked list) „ 单链表 „ 双链表 „ 循环链表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 back next „ first指向特殊的头结点 „ 引入头结点有利于特殊情况的处理 „ 空链表 „ 链表头 „ i按照C/C++数组下标编号的规则 „ 从0到n-1 „ 链表的第0个结点为first->link 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 back next 单链表的存储结构 first a0 a1 a2 an-1 last 单链表 空的单链表 first last data字段 link字段 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 back next 单链表结点类型以及变量说明 struct ListNode { ELEM data； ListNode * link; }; typedef ListNode * ListPtr; ListPtr first, last; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 back next 单链表插入算法 // 插入数据内容为value的新结点, 为第i个结点。 ListNode * Insert(ELEM value, int i) { ListNode *p，*q; p = FindIndex(i-1); if (p == NULL ) return NULL; q = new ListNode; // 需要时才new q->link = p->link; q->data = value; p->link = q; if(q->link == NULL ) last=q; return q; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 back next 20 23 10 12 15 15 不带头结点 head curr tail 20 23 12 15 head curr tail 20 23 12 带头结点 head fence tail 20 23 12 15 head fence tail 10 不带头结点 vs 带头结点

∥不带头结点 bool nhl(item, head): ink字段仅仅指向后继结点,不能 有效地找到前驱 fence>next: 双链表弥补了上述不足之处 righten++i Link(tem, curr) return true; ■增加一个指向前驱的指针 return true: 真太血张写 大血张體 新有食究 双链表示意图 双链表及其结点类型的说明 truct DblListNode 双向链表 elem data first- aoa*… DblListNode *rlink: DblListNode *llink: struct Double list DbIListNode *first, *last CK cK 真太张铭写 北盒大管血歌张写 新究 插入过程(注意顺序) 删除过程 在P所指结点后面插入一个新结点 删除p所指的结点 □= q->rlink=p->rlink p->rlink=NULL 如果马上 q>link=p(注意,教材p-> rlink-link) Mlink=NULL 则可以不 p->rlinK=q bac> link->nK=q 真大带酱张储 新有,种究 北大管息歌张帖习

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 back next // 带头结点 // 不带头结点 template bool NHList::insert(const Elem& item) { if (head == NULL) head = curr = tail = new Link(item, NULL); else { Link* temp = head; if (temp == curr) { head = new Link(item, head); curr = head; } else { while(temp->next != curr) temp = temp->next; temp->next = new Link(item, curr); curr = temp->next; } } rightcnt++; return true; } template bool LList::insert(const Elem& item) { fence->next = new Link(item, fence->next); if (tail == fence) tail = fence->next; rightcnt++; return true; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 back next 2.3.2 双链表 (double linked list) „ 单链表的主要不足之处是： „ link字段仅仅指向后继结点，不能 有效地找到前驱 „ 双链表弥补了上述不足之处 „ 增加一个指向前驱的指针 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 back next 双链表示意图 first last a0 a1 an-1 双向链表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 back next 双链表及其结点类型的说明 struct DblListNode { ELEM data; DblListNode *rlink; DblListNode *llink; }; struct DoubleList { DblListNode *first，*last; }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 back next 插入过程（注意顺序） 在p所指结点后面插入一个新结点 p q q->rlink=p->rlink q->llink=p (注意，教材p->rlink->llink) p->rlink=q q->rlink->llink=q new q; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 back next 删除过程 „ 如果马上删除p „ 则可以不赋空 删除p所指的结点 p p->llink->rlink=p->rlink p->rlink->llink=p->llink p->rlink=NULL p->llink=NULL

2.3.3循环链表 (circularly linked list) 几种主要链表比较 单链表或双链表的头尾结点链接 空的单链豪frst 起来 给不少操作带来了方便 ao E ■从循环表中任一结点出发,都能 空的辑环健衰frst 访问到表中其他结点 一画ak: 不增加额外存储花销 循环双向衰 B ao t a1 真太血张写 大血张體 新食 注意指针变量的有效性 注意链表的边界处理 记得使用new 几个特殊点的处理 使用新指针变量,或要生成一个新结 头指针处理 点前先执行new操作 非循环链表尾结点的指针城保持为NUL 循环链表尾结点的指针回指头结点 ■不要引用NULL指针 链表处理 ■使用指针前,先用语句(或whle循 空链表的特殊处理 环条件中的语句)判断它非空 插入或删除结点时指针勾链的顺序 不用引用 Delete了的指针 指针移动的正确性 中ack 真太张铭写 ·找武道历“牌 24线性表实现方法的比较 应用场合的选择 顺序表的主要优点 ■不要使用顺序表的场合 没用使用指针,不用花费附加开销 经常插入删除时,不宜使用顺序表 线性表元素的读访问非常简洁便利 ■线性表的最大长度也是一个重要因素 链表的主要优点 不要使用链表的场合 无需事先了解线性表的长度 当读操作比插入删除操作频率大时 允许线性表的长度有很大变化 不应选择链表 能够适应经常插入删除内部元亲的情况 当指针的存储开销,和整个结点内容 ,应该慎 back 所占空间相比其比例较大时, 真大带酱张储 新有,种究 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 back next 2.3.3 循环链表 (circularly linked list) „ 单链表或双链表的头尾结点链接 起来 „ 给不少操作带来了方便 „ 从循环表中任一结点出发，都能 访问到表中其他结点 „ 不增加额外存储花销 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 back next 几种主要链表比较 first a0 a1 a2 an-1 last 单链表 空的单链表 first last first a0 a1 a2 an-1 last 循环链表 空的循环链表 first last first last a0 a1 an-1 双向链表 循环双向链表 first last a0 a1 an-1 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 back next 注意指针变量的有效性 „ 记得使用new „ 使用新指针变量，或要生成一个新结 点前先执行new操作 „ 不要引用NULL指针 „ 使用指针前，先用if语句（或while循 环条件中的语句）判断它非空 „ 不用引用Delete了的指针 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 back next 注意链表的边界处理 „ 几个特殊点的处理 „ 头指针处理 „ 非循环链表尾结点的指针域保持为NULL „ 循环链表尾结点的指针回指头结点 „ 链表处理 „ 空链表的特殊处理 „ 插入或删除结点时指针勾链的顺序 „ 指针移动的正确性 „ 插入 „ 查找或遍历 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 back next 2.4 线性表实现方法的比较 „ 顺序表的主要优点 „ 没用使用指针，不用花费附加开销 „ 线性表元素的读访问非常简洁便利 „ 链表的主要优点 „ 无需事先了解线性表的长度 „ 允许线性表的长度有很大变化 „ 能够适应经常插入删除内部元素的情况 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 back next 应用场合的选择 „ 不要使用顺序表的场合 „ 经常插入删除时，不宜使用顺序表 „ 线性表的最大长度也是一个重要因素 „ 不要使用链表的场合 „ 当读操作比插入删除操作频率大时， 不应选择链表 „ 当指针的存储开销，和整个结点内容 所占空间相比其比例较大时，应该慎 重选择

栈的抽象数据类型 25栈( stack) plate class Stack 算集为: 栈:限制访问端口的线性 LIF0寝 该实例消亡 Push:元章插入,“压入 Pop:元素删除,弹出 void push( ELEM item);∥item压入栈项 Top:表首被称为栈顶 ELEM Popo;∥返回栈顶内容,并从栈顶弹出 ELEM GetTop0;∥返回栈顶内容,但不弹出 Begrime 4 bool IsEmptyo; ∥若找已空返回 bool SuLlo;∥若梭已满返回真,顺序栈有用 栈顶」 最大长度 int length: ∥当前栈长 真太血张写 大血张體 新有食究 栈的实现 21顺序栈 template 顺序栈 使用向量实现 ○链式栈 ELEM* EImList;∥存放据元章微組 用单链表方式存储,其中指针的方向 ∥校顶在的位置,即下标值 是从栈顶向下链接 MansiZe;∥栈的最大长度 构建栈的实例,向量空间长度为size 栈的应用计算表达式的值 栈与递归 ∥其他运算同视ADT CK back 真太张铭写 魏张写 新究 顺序栈 顺序栈的创建 ∥实例的创建,指定最大长度100。在类的内部实 laxsIzesize ∥开辟向量存储空间 size 5 栈顶 ElmList-new ElEM maxsize 判晰nw命令成功否,否则断言程序异常 sert(ElmList -NULL): ∥表示栈空 back 真大带酱张储 北大管息歌张帖习

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 back next 2.5 栈(stack) 栈：限制访问端口的线性表 LIFO表 „ Push：元素插入 ，‘压入’ „ Pop：元素删除，‘弹出’ „ Top：表首被称为‘栈顶’ 1 2 3 4 栈底 栈顶 栈最大长度 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 back next 栈的抽象数据类型 template class Stack { // 栈的运算集为： Stack(int sz); //创建栈的实例 ~Stack(); //该实例消亡 void Push(ELEM item); // item压入栈顶 ELEM Pop(); // 返回栈顶内容，并从栈顶弹出 ELEM GetTop(); // 返回栈顶内容，但不弹出 void ClearStack(); // 变为空栈MakeEmpty(); bool IsEmpty(); // 若栈已空返回真 bool IsFull(); // 若栈已满返回真，顺序栈有用 int length(); // 当前栈长 }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 back next 栈的实现 „ 顺序栈 „ 使用向量实现 „ 链式栈 „ 用单链表方式存储，其中指针的方向 是从栈顶向下链接 „ 栈的应用--计算表达式的值 „ 栈与递归 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 back next 2.5.1 顺序栈 template class Stack { private: ELEM *ElmList; // 存放数据元素数组 int top; // 栈顶在的位置，即下标值 int maxsize; // 栈的最大长度 //构建栈的实例，向量空间长度为size Public: Stack(int size); // 其他运算同栈ADT … }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 back next 顺序栈 栈顶 5 4 8 7 1 element [0] [1] [2] [3] [4] max_size - 1 size = 5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 back next 顺序栈的创建 //栈实例的创建，指定最大长度100。在类的内部实现 Stack(int size=100) { maxsize=size; //开辟向量存储空间 ElmList=new ELEM[maxsize]; //判断new命令成功否，否则断言程序异常 assert(ElmList!=NULL); top=-1; // 表示栈空 }

压入栈顶 从栈顶弹出 template template void Stack: Push(ELEM item) ELEM Stack: Popo 判非栈满,否则栈溢出,退出运行 判栈非空,否则断言栈空异常退出运行 ssert(sfUll) top++;/栈顶 ElmList topl=item; return ElmListtop-; next back 真太血张写 大血张體 新有食究 从栈顶读取,但不弹出 其他函数 template ∥函数在类定义之内实现,不用“”修饰 ELEM Stack: GetTopo bool IsEmptyo∥返回真,若栈已空 i return top==-1;3 判栈非空,否则断言栈空异常退出 ∥栈满时,返回非零值(真true) assert( IsEmpty o); bool Is Fullo return top==maxsize-1: return ElmList topl a Clearstacko{top=1;}∥变空栈 StackO{ delete EnlIst;}∥栈消亡 CK bacK 真太张铭写 北盒大管血歌张写 新究 sTL中关于堆栈的函数 252链式栈 其中t。p函数表示取栈项元,并将结果返回给用户 (如果栈不空的话 用单链表方式存储 将果返回 指针的方向从栈顶向下链接 有些库函数提供了这样的函数ptop? Nt2|{3-4Z STL为什么这两个操作分开? 使舞函数之间的合度降低 Top栈顶 back 真大带酱张储 新有,种究 北大管息歌张帖习

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 back next 压入栈顶 template void Stack::Push(ELEM item) { //判非栈满，否则栈溢出，退出运行 assert(!IsFull()); top++; //栈顶 ElmList[top]=item; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 back next 从栈顶弹出 template ELEM Stack::Pop() { //判栈非空，否则断言栈空异常退出运行 assert(!IsEmpty()); return ElmList[top--]; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 back next 从栈顶读取，但不弹出 template ELEM Stack::GetTop() { //判栈非空，否则断言栈空异常退出 assert(!IsEmpty()); return ElmList[top]; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 back next 其他函数 „ // 函数在类定义之内实现, 不用“::”修饰 „ bool IsEmpty() // 返回真，若栈已空 { return top == -1;} „ // 栈满时，返回非零值（真true） bool IsFull() {return top==maxsize-1;} „ ClearStack() { top=-1; } // 变空栈 „ ~Stack() {delete []ElmList;} // 栈消亡 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 back next STL中关于堆栈的函数 „ 其中top函数表示取栈顶元素，并将结果返回给用户 „ pop函数表示将栈顶元素弹出（如果栈不空的话） „ pop函数仅仅是一个操作，并不将结果返回。 „ pointer=aStack.pop()？错误！ „ 有些库函数提供了这样的函数ptop？ „ STL为什么这两个操作分开？ „ 主要是概念上显得清晰 „ 保证一个函数只确定地完成一项特定的功能 „ 使得函数之间的耦合度降低 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 back next 2.5.2 链式栈 „ 用单链表方式存储 „ 指针的方向从栈顶向下链接 N 1 2 3 4 Top 栈顶

链式栈的创建 单链表的结点类型 emplate class Stack / Singly- template class Link t Link *top; public /最大栈长链找可以不要 Elem data; / Value for this node int curr len; 当前栈长 Link *next: / Pointer to next node in list public: Link(const Elem& elemval, Link* nextval =NULL Stack( int size=100){//构建找的实例 telement= elemval; next= nextval; y /创建一个空栈,链式栈不用指定最大长度 Link(Link* nextval =NULL)[ next nextval; 1 maxsize size 真太血张写 大血张體 新有食究 压入栈顶 自单链栈弹出 template template void Stack: Push(ELEM item) ELEM Stack: Popo //判栈非空,否则断言栈空 Link *temp assert(lIs Empty) temp new Link ELEM result=top->data;//智存栈顶内容 //若无存储空间则异常,程序退出运行 ssert(temp==NULL; tempt= top; /老栈顶指针 top=top>next;/新栈顶指针 temp->next=top;//老栈项指针 curr_len--i //新栈项指针 ptr;∥/释放空间 curr_ len++i eturn result /返回的是弹出内容 CK bacK 真太张铭写 北盒大管血歌张写 新究 小结 计算机过时技能ToP10 实际应用中,顺序栈比链式栈用 1. Cobol, 2. Nonrelational DBMS 非关系数据库管理系统) 得更广泛些 3.Non- IP networks(非IP网 般来说,栈不允许“读取内部元 )、4.cC:Mail 素”,只能在栈顶操作 5. Cold Fusion 6.C语言设计 7. Power Builder 8 CNE ( Netware认证工程师) 9.Pc网络管理员 next 真大带酱张储 新有,种究 北大管息歌张帖习

8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 back next 单链表的结点类型 // Singly-linked list node template class Link { public: Elem data; // Value for this node Link *next; // Pointer to next node in list Link(const Elem& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; } }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 back next 链式栈的创建 template class Stack { private: Link *top; int maxsize; // 最大栈长, 链栈可以不要 int curr_len; // 当前栈长 public: Stack(int size=100) { //构建栈的实例 //创建一个空栈，链式栈不用指定最大长度 top = NULL; curr_len = 0; maxsize = size; } … }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 back next 压入栈顶 template void Stack::Push(ELEM item) { Link *temp; temp = new Link; //若无存储空间则异常，程序退出运行 assert(!temp==NULL); temp->data = item; temp->next = top; //老栈顶指针 top = temp; //新栈顶指针 curr_len++; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 back next 自单链栈弹出 template ELEM Stack::Pop() { //判栈非空，否则断言栈空异常，程序退出 assert(!IsEmpty()); ELEM result = top->data; //暂存栈顶内容 Link *temptr; temptr = top; //老栈顶指针 top = top->next ; //新栈顶指针 curr_len--; delete temptr; //释放空间 return result; //返回的是弹出内容 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 back next 小结 „ 实际应用中，顺序栈比链式栈用 得更广泛些 „ 一般来说，栈不允许“读取内部元 素”，只能在栈顶操作 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 back next 计算机过时技能TOP10 „ 1.Cobol 、2. Nonrelational DBMS （非关系数据库管理系统） „ 3. Non-IP networks（非IP网 络）、4. CC:Mail „ 5. ColdFusion „ 6. C 语言设计 „ 7. PowerBuilder、8. CNE （NetWare认证工程师） „ 9. PC网络管理员、10. OS/2

抽象数据类型 c数据类型的问题 ■抽象数据类型 1.在同一个程序中,如果栈的 ■实质为“逻辑结构+运算/操作 隐蔽了存储实现细 StackElementType不同 上层算法以一致的形式调用底层数据结构 需要定义不同的栈 例如在STLC++中 2.从顺序栈改为链式栈 Stack push(x) 顺序找,链式找 上层调用语句一定要改变 上层调用语句不需要改变 真太血张写 大血张體 新有食究 253栈的应用-计算表达式的值 计算表达式的值 栈可以应用于递归函数 ■表达式的递归定义 ( recursive function)的实现 ■基本符号集:{0,1,…,9,+,一 ■使用下推表(栈)自动进行复杂 的算术表达式的递归求值 因子《常数李{项>, 后缀表达式 CK ■后缀表达式求值 bacK 真太张铭写 北盒大管血歌张写 新究 语法公式(中缀表达法) 后缀表达式 BNF范式,可以利用Lex,Yacc等自动构造编译器 =1因于 /=|》:=0|1|2|3|4|5|6|7 ∷=|<常数〉 数字〉.<常数 数字》:=0|1|2|3|4|5|6 back 真大带酱张储 新有,种究 北大管息歌张帖习

9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 back next 抽象数据类型 „ 抽象数据类型 „ 实质为“逻辑结构 + 运算/操作” „ 隐蔽了存储实现细节 „ 上层算法以一致的形式调用底层数据结构 „ 例如在STL C++中 „ Stack.push(x) „ 顺序栈，链式栈 „ 上层调用语句不需要改变 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 back next C数据类型的问题 „ 1. 在同一个程序中，如果栈的 StackElementType 不同 „ 需要定义不同的栈； „ 2. 从顺序栈改为链式栈 „ 上层调用语句一定要改变 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 back next 2.5.3 栈的应用--计算表达式的值 „ 栈可以应用于递归函数 (recursive function)的实现 „ 使用下推表（栈）自动进行复杂 的算术表达式的递归求值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 back next 计算表达式的值 „ 表达式的递归定义 „ 基本符号集：{0，1，…，9，+，-， *，/，（，）} „ 语法成分集：{ , , , , } „ 语法公式集 „ 后缀表达式 „ 后缀表达式求值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 back next 语法公式(中缀表达法) BNF范式，可以利用Lex,Yacc等自动构造编译器 „ ∷= + | － | „ ：：= * | / | „ ::= | （ ） „ ∷= | „ ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 back next 后缀表达式 „ ∷= + | － | „ ：：= * | / | „ ::= „ ∷= | | . | „ ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

栈的应用 后缀表达式求值 中缀表达的算术表达式的计算次序 中缀表达式: ∠=【 (1)先执行括号内的计算,后执行括号外 运算符在中间 的计算。在具有多层括号时,按层次反 需要括号改变优先级 复地脱括号,左右括号必须配对 率□ 十、 (2)在无括号或同层括号时,先乘(*) 4*x*(2*x+a)-c 除(/),后作加(+)、减(-)。 后缀表达式 (3)在同一个层次,若有多个乘除(* ■运算符在后面 /)或加减(+,-)的运算,那就按自左 完全不需要括号 至右顺序执行 2x*a+*c一 张帖写 大血张體 新有食究 中缀转后缀表达式值示例 中缀转后缀算法 当输入的是操作数时,直接输出到后缀 4*x*C2*x+a)一C 2x*a+*c (2)当输入的是开括号时,也把它压栈。 (3)当输入的是闭括号时,先 ■运算符可以作为中缀输入的自然分割 输出的后缀表达式,可以采用空格分割 cin按照变量指定的格式输入 CK bacK 真太张铭写 权新有,轨些究 北盒大管血歌张写 新究 后缀表达式求值 (4)当输入的是运算符时 ■循环:依次顺序读用户键入的符号序 算符的 列,组成并判别语法成分的类别 将栈顶元素弹出,放到后缀表达式序列中; 1.当遇到的是一个操作数,则压入栈顶; (b)把输入的运算符压校 2当通到的是一个运算符,就从栈中两次取 (5)最 出栈顶,按照运算符对这两个操作数进行计 算。然后将计算结果压入栈顶 如此继续,直到遇到符号=,这时栈顶 的值就是输入表达式的值。 back 真大带酱张储 新有,种究 北大管息歌张帖习 10

10 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 back next 栈的应用 ——后缀表达式求值 „ 中缀表达式： „ 运算符在中间 „ 需要括号改变优先级 „ 4* x * (2 * x + a) – c „ 后缀表达式 „ 运算符在后面 „ 完全不需要括号 „ 4 x * 2 x * a + * c – - * * + * c 4 x a 2 x 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 back next 中缀表达的算术表达式的计算次序 „ (1)先执行括号内的计算，后执行括号外 的计算。在具有多层括号时，按层次反 复地脱括号，左右括号必须配对。 „ (2)在无括号或同层括号时，先乘(*) 、 除(／)，后作加(+)、减(-)。 „ (3)在同一个层次，若有多个乘除（*、 ／）或加减 (+，-)的运算，那就按自左 至右顺序执行。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 back next 中缀转后缀表达式值示例 „ 4 * x * (2 * x + a) – c „ 4 x * 2 x * a + * c – „ 运算符可以作为中缀输入的自然分割 „ 输出的后缀表达式，可以采用空格分割 „ cin按照变量指定的格式输入 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 back next 中缀转后缀算法 „ （1）当输入的是操作数时，直接输出到后缀 表达式序列。 „ （2）当输入的是开括号时，也把它压栈。 „ （3）当输入的是闭括号时，先判断栈是否为 空，若为空（括号不匹配），应该当错误异常 处理，清栈退出。若非空，则把栈中的元素依 次弹出，直到遇到第一个开括号为止，将弹出 的元素输出到后缀表达式的序列中（弹出的开 括号不放到序列中），若没有遇到开括号，说 明括号也不匹配，做异常处理，清栈退出。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 back next „ （4）当输入的是运算符时 „ （a) 循环，当（栈非空 and 栈顶不是开括 号 and 栈顶运算符的优先级不低于输入的运算符的 优先级）时，反复操作 将栈顶元素弹出，放到后缀表达式序列中； „ （b）把输入的运算符压栈。 „ （5）最后，当中缀表达式的符号序列全部读 入时，若栈内仍有元素，把它们全部依次弹 出，都放到后缀表达式序列尾部。若弹出的元 素遇到开括号时，则说明括号不匹配，做错误 异常处理，清栈退出。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 back next 后缀表达式求值 „ 循环：依次顺序读用户键入的符号序 列，组成并判别语法成分的类别 „ 1.当遇到的是一个操作数，则压入栈顶； „ 2.当遇到的是一个运算符, 就从栈中两次取 出栈顶，按照运算符对这两个操作数进行计 算。然后将计算结果压入栈顶。 „ 如此继续，直到遇到符号＝, 这时栈顶 的值就是输入表达式的值