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

资源提示 第二章线性表、栈和队列 作业提交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 ELEM> 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<em)*: insert(const 2.3.2双链表 dink Elem tatem, LL: (double linked list) ∥带头结点 单链表的主要不足之处是: anakselem>(item, head): ink字段仅仅指向后继结点,不能 有效地找到前驱 fence>next: 双链表弥补了上述不足之处 righten++i Link<Elem>(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<class Elem> bool NHList<Elem>::insert(const Elem& item) { if (head == NULL) head = curr = tail = new Link<Elem>(item, NULL); else { Link<Elem>* temp = head; if (temp == curr) { head = new Link<Elem>(item, head); curr = head; } else { while(temp->next != curr) temp = temp->next; temp->next = new Link<Elem>(item, curr); curr = temp->next; } } rightcnt++; return true; } template <class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(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 应用场合的选择 „ 不要使用顺序表的场合 „ 经常插入删除时，不宜使用顺序表 „ 线性表的最大长度也是一个重要因素 „ 不要使用链表的场合 „ 当读操作比插入删除操作频率大时， 不应选择链表 „ 当指针的存储开销，和整个结点内容 所占空间相比其比例较大时，应该慎 重选择