第 七 讲 单链表、循环链表、双向链表 10 23

1、循 环 链 表、双向链表时 间：2013 10 - 231 劝 学 语玩 物 丧 志，玩 人 丧 德。 尚书 读 书须用意，一字值千金。 弟 子 规 2只要有了积极主动的态度， 没有什么目标是不能达到的。 李 开 复3第 七 次 上 课 内 容1、 循环链表 P 392、双向链表 P 433、线性表的应用 P554本节课学习目标 1、循环表的定义 2、双向表的定义 3、线性表的应用5数据的逻辑结构可归结为以下四类线性结构树形结构图状结构集合结构6第 2 章 线 性 表7循环链表 (Circular List)8循环链表是单链表的变形唯一一个区别： 循环链表最后一个结点的next指针不为 0 (

2、NULL)，而是指向了表的前端。增加一个标记： 为简化操作，在循环链表中往往加入表头结点。循 环 表 特 点： 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。9循 环 链 表 示 例10/ 简单循环链表类template class SimpleCircLinkList protected:/ 循环链表实现的数据成员:Node *head;/ 头结点指针/ 辅助函数Node *GetElemPtr(int position) const;/ 返回指向第position个结点的指针void Init();/ 初始化线性表11public:/ 抽象数据类型方法声明及重

3、载编译系统默认方法声明:SimpleCircLinkList();/ 无参数的构造函数virtual SimpleCircLinkList();/ 析构函数int Length() const;/ 求线性表长度bool Empty() const;/ 判断线性表是否为空void Clear();/ 将线性表清空void Traverse(void (*Visit)(const ElemType &) const;/ 遍历线性表StatusCode GetElem(int position, ElemType &e) const;/ 求指定位置的元素StatusCode SetElem(int

4、position, const ElemType &e);/ 设置指定位置的元素值12StatusCode Delete(int position, ElemType &e);/ 删除元素StatusCode Insert(int position, const ElemType &e);/ 插入元素SimpleCircLinkList(const SimpleCircLinkList ©); / 复制构造函数SimpleCircLinkList &operator =(const SimpleCircLinkList ©);/ 赋值语句重载;13用循环链表求解约瑟夫问题约瑟夫

5、问题的提法 n 个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数, 报到第m 个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。例如 n = 8 m = 314/ 文件路径名:s2_5alg.h void Josephus(int n, int m)/ 操作结果:n个人围成一个圆圈，首先第1个人从1开始一/ 个人一个人顺时针报数,报到第m个人，令其出列。/然后再从下一个人开始，从1顺时针报数报到第m/个人，再令其出列，如此下去, 直到圆圈中只/剩一个人为止。此人即为优胜者 SimpleCircLin

6、kList la;/ 定义空循环链表int position = 0;/ 报数到的人在链表中序号int out, winer;for (int k = 1; k = n; k+) la.Insert(k, k);/ 建立数据域为1,2,.,n的循环链表15cout 出列者:; for (int i = 1; i n; i+)/ 循环n-1次，让n-1个个出列for (int j = 1; j la.Length()position = 1;la.Delete(position-, out);/ 报数到m的人出列cout out ;la.GetElem(1, winer);/ 剩下的一个人为优胜

7、者cout endl 优胜者: winer endl;16双向链表 (Doubly Linked List)双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。双向链表每个结点结构： 前驱方向 后继方向双向链表通常采用带表头结点的循环链表形式。17双向循环链表示例18双向链表的实现一、数据结点类模板 template struct DbNode ElemType data; DbNode *back; DbNode *next; DbNode (); DbNode(); DbNode (DbNode *linkback, DbNode *linknext) 19双向链表类模板Templat

8、eClass DbLinkListProtected: DbNode *head; DbNode *GetElemPtr(int pos);Public: DbLinkList(); DbLinkList(); int Length() const; Bool Empty()const;20 Bool Empty() const; Void Clear(); bool GetElem(int pos,ElemType &e); bool SetElem(int pos ,ElemType e); bool Delete(int pos ,ElemType &e); bool Insert(in

9、t pos ,ElemType &e); ;21在链表结构中保存当前位置和元素个数 前面讲解了三种线性表的三种链式存储结构，这三种结构实现比较一致，处理简单，特别适合于初学者，但许多应用程序是按顺序处理线性表的中数据元素的，也就是处理完一个数据元素后再处理下一个数据元素，也可能要几次引用同一个数据元素，比如在访问下一个数据元素之前做GetElem和SetElem操作，对于这类应用程序，前面的链表实现效率低下，这时最好在链表结构中保存当前位置和元素个数。 22Mutable修饰符mutable 可以用来指出，即使结构或者类变量为const，其某个成员也可以被修改 。 例 如： Class A c

10、onst int data; bool Set(int da) const data =da; 23/ 线性链表类template class LinkList protected:/ 链表实现的数据成员:Node *head;/ 头结点指针mutable int curPosition;/ 当前位置的序号mutable Node * curPtr;/ 指向当前位置的指针int count;/ 元素个数24/ 辅助函数Node *GetElemPtr(int position) const;/ 返回指向第position个结点的指针void Init();/ 初始化线性表public:/ 抽象

11、数据类型方法声明及重载编译系统默认方法声明:LinkList();/ 无参数的构造函数virtual LinkList();/ 析构函数int Length() const;/ 求线性表长度bool Empty() const;/ 判断线性表是否为空void Clear();/ 将线性表清空void Traverse(void (*Visit)( const ElemType &) const;/ 遍历线性表25StatusCode GetElem(int position, ElemType &e) const;/ 求指定位置的元素StatusCode SetElem(int positio

12、n, const ElemType &e);/ 设置指定位置的元素值StatusCode Delete(int position, ElemType &e);/ 删除元素StatusCode Insert(int position, const ElemType &e); / 插入元素LinkList(const LinkList ©); / 复制构造函数LinkList &operator =(const LinkList ©); / 赋值语句重载;26重写 GetElemPtr函数Node *LinkList:GetElemPtr(int pos) const if(cur

13、Pos pos) curPose =0; curPtr = head; For( ; curPosnext; return curPtr;27在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn)多项的链表表示一元多项式但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？28 一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n可以下列线性表表示：（p1, e1）, (p2, e2), , (pm,em) ）29 P

14、999(x) = 7x3 - 2x12 - 8x999例 如:可用线性表 ( (7, 3), (-2, 12), (-8, 999) )表示30/ 多项式类class Polynomialprotected:/ 多项式实现的数据成员:LinkList polyList;/ 多项式组成的线性表public:/ 抽象数据类型方法声明:Polynomial();/ 无参构造函数Polynomial();/ 析构函数int Length() const;/ 求多项式的项数31bool IsZero() const;/ 判断多项式是否为0void SetZero();/ 将多项式置为0void Display();/ 显示多项式void InsItem( const PolyItem &item);/ 插入一项Polynomial operator +(const Polynomial &p) const; / 加法运算符重载Polynomial operator -(const Polynomial &p) const; / 减法运算符重载Polynomial operator *(const Polynomial &p) const; / 乘法运算符重载Polynomial(const Polynomial ©);/ 复制构造函