链式 存储结构的表、堆栈和队列
4.1 链式 存储结构
4.2 单链表
4.3 单循环链表
4.4 双向循环链表
4.5 链式堆栈
4.6 链式队列
4.7 链式存储结构的特点
4.8 应用问题的面向对象程序设计方法计算机学院信息教研室
DS
4.1链式 存储结构链式 存储结构：初始时为空链，每当有新的数据元素需要存储时，用户向系统动态申请所需的存储空间插入链中。
申请：
名字指针 =new 类型明（初始化值）
释放,Delete 名字指针计算机学院信息教研室
DS
4.1链式 存储结构特点：任意两个在逻辑上相邻的数据元素在物理上不一定相邻。其逻辑顺序是通过链中的指针来实现的。
为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，
这个信息称为指针 (pointer)或链 (link)。
计算机学院信息教研室
DS
4.1链式 存储结构链式 存储结构数据元素集合的方法是用结点（ Node）构造链。计算机学院信息教研室
DS
data next
其中,data域是数据域，用来存放结点的值。
next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。
4.1链式 存储结构头结点是指头指针所指的不存放数据元素的结点。
其中,带头结点的链式结构在表的存储中更为常见。不带头结点的链式结构在栈和队列的存储中更为常见。
空指针在算法描述中用 NULL来表示，空指针是一个特殊的标识，用来表识链的结束。
计算机学院信息教研室
DS
4.2 单链表（ Single Linked)
链表正是通过每个结点的链域将线性表的 n个结点 按其逻辑次序链接 在一起的。由于上述链表的每一个结点 只有一个链域,故将这种链表称为单链表（ Single Linked)。
例 1、线性表,(bat,cat,eat,fat,hat,jat，
lat,mat)
计算机学院信息教研室
DS
bat cat eat mat ^ …
head
单链表 (Singly Linked List)
特点
每个元素 (表项 )由结点 (Node)构成。
线性结构
结点可以不连续存储
表可扩充计算机学院信息教研室
a0 a1 an ^…head
data next
单链表的存储映像计算机学院信息教研室单链表的类模板计算机学院信息教研室
DS
类模板将类的数据成员和成员函数设计得更完整、更灵活。
类模板更易于复用。
在单链表的类模板定义中，增加了 表头结点 。
由图分析：单链表的基本组成部分是结点，
一个单链表可用该单链表的头指针来表示。（用类的组合来实现）
先设计结点类定义单链表类计算机学院信息教研室
DS
a0 a1 an ^ …head
data next
a0 a1 an ^ …head
4.2.1 结点类的定义和实现数据成员：数据域 data（ 公有,应用问题要使用 ）
指针域 next（ 私有）
private:
ListNode<T> *next; //该指针是结点类的对象成员函数：
初始化构造一个结点对象（头结点）
新建立一个结点,(指向下一个结点的指针 )
计算机学院信息教研室
DS data next
4.2.1 结点类的定义和实现
#include<iostream.h>
#include<stdio.h>
template<class T>class LinList; //前视定义，否则，无法定义友元
template<class T>class ListNode
{
friend class LinList<T>; //定义友元
private:
ListNode<T> *next; //指向下一个结点的指针
public:
…
}
计算机学院信息教研室
DS
ListNode.h
4.2.1 结点类的定义和实现
{
…
public:
T data; //定义公有成员便于访问
ListNode(ListNode<T> *ptrNext = NULL);
//构造函数，用于构造头结点
ListNode(const T& item,ListNode<T>
*ptrNext = NULL); //构造函数，非头结点
~ListNode(){}; //析构函数
}
计算机学院信息教研室
DS
ListNode.h
4.2.1 结点类的定义和实现
template<class T>
ListNode<T>::ListNode(ListNode<T>
*ptrNext):next(ptrNext)
{ }
template<class T>
ListNode<T>::ListNode(const T
&item,ListNode<T> *ptrNext)
{
data = item;
next = ptrNext;
}
计算机学院信息教研室
DS
ListNode.cpp
4.2.2 单链表类的 定义 和实现数据成员 (1)头指针（ 2）元素个数（ 3）当前结点指针成员函数,3组
（ 1）构造函数和析构函数
（ 2）表操作的成员函数（任何对单链表结点的操作都要从头结点开始）
（ 3）遍历函数（为什么要提出？）
计算机学院信息教研室
DS a0 a1 an ^ …head
template<class T>class LinList
{
private:
ListNode<T> *head; //指向头结点的指针
int size; //单链表的元素个数
ListNode<T> *currPtr; //当前结点指针
public:
LinList(void); //构造函数
~LinList(void); //析构函数
…
}
计算机学院信息教研室
DS
4.2.2 单链表类的 定义 和实现
Linlist.h
template<class T>class LinList
{
private:
public:
…
int ListSize(void) const; //返回链表的元素个数
int ListEmpty(void) const;
ListNode<T> *Index(int pos); //定位
void Insert(const T& item,int pos); //插入
T Delete(int pos); //删除
T GetData(int pos); //取元素
void ClearList(void); //清空链表
…
}
计算机学院信息教研室
DS
4.2.2 单链表类的 定义 和实现
Linlist.h
表操作的成员函数
template<class T>class LinList
{
private:
public:
…
ListNode<T> *Reset(int pos=0); //把第
pos个结点设置为当前结点 currPtr
ListNode<T> *Next(void); //currPtr指向下一个结点
int EndOfList(void) const; //currPtr是否指在链表尾
}
计算机学院信息教研室
DS
4.2.2 单链表类的 定义 和实现
Linlist.h
遍历表的函数
template<class T>
LinList<T>::LinList() //构造函数
{
head = new ListNode<T>();
size = 0;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
head ^
template<class T>
LinList<T>::~LinList(void) //析构函数
{
ClearList(); //释放所有非头结点
delete head; //释放头结点
head = NULL;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
a0 a1 an ^…head
head ^
template<class T>
int LinList<T>::ListSize(void) const //返回链表的个数
{
return size;
}
template<class T>
int LinList<T>::ListEmpty(void) const //判断是否为空
{
if(size <= 0)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
template<class T>
ListNode<T> *LinList<T>::Index(int pos) //定位，返回指向第 pos个结点的指针
{
if(pos < -1||pos > size)
{
cout<<"参数 pos越界出错！ "<<endl;exit(1);
}
if(pos = -1) return head; //pos为 -1时，返回头指针 head
ListNode<T> *p = head->next;
int i = 0;
while(p != NULL && i < pos) //寻找第 pos个结点
{
p = p->next;
i++;
}
return p;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现Linlist.cpp
a0 a1 an ^…head
posp
template<class T>
void LinList<T>::Insert(const T& item,int pos) //在 pos个结点之前插入一个 data域为 item的新结点
{
ListNode<T> *p = Index(pos-1);
ListNode<T> *newNode = new ListNode<T>(item,p->next);
p->next = newNode;
size++;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
ai-1 ai an ^…head
x 1
2
p
计算机学院信息教研室
DS
head a
i+1 an ^ ai …ai-1a0 …
qP
template<class T>
T LinList<T>::Delete(int pos) //删除第 pos
个结点，并返回被删除结点的 data
{
if(size == 0)
{
cour<<"链表已空无元素可删 !"<<endl;
exit(1);
}
…,
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
head
ai+1 an ^ ai …ai-1a0 …
qP
{
…
ListNode<T> *q,*p = Index(pos - 1); //p指向第 pos-1个结点
q = p->next; //q指向第 pos个结点
p->next = p->next->next; //第 pos个结点脱链
T data = q->data;
delete q; //释放第 pos个结点
size--;
return data;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和实现
Linlist.cpp
head
ai+1 an ^ ai …ai-1a0 …
qP
template<class T>
T LinList<T>::GetData(int pos) //返回第 pos个结点的 data值
{
ListNode<T> *p = Index(pos);
return p->data;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和实现
Linlist.cpp
template<class T>
void LinList<T>::ClearList(void) //清空表为初始化状态
{
ListNode<T> *p,*p1;
p = head->next; //p指向第一个结点
while(p != NULL) //循环释放结点空间直至初始化状态
{
p1 = p;
p = p->next;
delete p1;
}
size = 0;
}
计算机学院信息教研室
DS
Linlist.cpp
a0 a1 an ^…head
head ^
p
p1
4.2.2 单链表类的定义和实现
template<class T>
ListNode<T> LinList<T>::Reset(int pos) //把第 pos个结点设置为当前结点 currPtr
{
if(head == NULL) return NULL;
if(pos < -1 || pos > size)
{
cout<<"参数 pos越界出错！ "<<endl;
exit(1);
}
if(pos == -1) return head;
…
}
计算机学院信息教研室
DS
Linlist.cpp
4.2.2 单链表类的定义和实现
{
…
if(pos == 0) return head->next;
else 定为指针 currPtr的值
{
currPtr = head->next;
ListNode<T> *prePtr = head;
for(int i = 0; i < pos; i++) 循环定位 currPtr指向结点 pos
{
prePtr = currPtr;
currPtr = currPtr->next;
}
}
return currPtr;
}
计算机学院信息教研室
DS
Linlist.cpp
a0 a1 an ^…head
poscurrPtrprePtr
4.2.2 单链表类的定义和实现
template<class T>
LinList<T>::ListNode<T> *Next(void)
//currPtr指向下一个结点
{
if(currPtr != NULL)
currPtr = currPtr->next;
return currPtr;
}
计算机学院信息教研室
DS
Linlist.cpp
a0 a1 an ^…head
currPtr
4.2.2 单链表类的定义和实现
template<class T>
int LinList<T>::EndOfList(void) const
//currPtr是否指在链表尾
{
if(currPtr == NULL)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
a0 a1 an ^…head
4.2.2 单链表类的定义和实现定位，前插入、删除和取元素成员函数的时间复杂度均为 O(n).
与顺序表相比，链表类增加了一组循环遍历成员函数。可以有效降低对循环遍历操作的时间复杂度。 (为什么？ )
计算机学院信息教研室
DS
a0 a1 an ^…head
#include "LinList.h"
void main(void)
{
LinList<int> myList;
for(int i=0;i<5;i++)
myList.Insert(i+10,i);
cout<<"测试 GetData()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.GetData(i)<<" ";
cout<<"测试遍历成员函数结果如下,"<<endl;
ListNode<int> *p = myList.Reset(); //p指在第一个结点
while(!myList.EndOfList()) //是否到达表尾
{
cout<<myList.Next<<" ";
p = myList.Next(); //p指在第一个结点
}
}
计算机学院信息教研室
DS
单链表类的应用表和顺序表
typedef int DataType; //具体应用时定义的数据类型 Datatype
#include "seqlist.h" //类 Seqlist的定义和实现头文件
void main(void)
{
SeqList myList; //插入 5个整型元素
for(int i=0;i<5;i++)
myList.Insert(i+10,i);
cout<<"测试 GetData()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.GetData(i)<<,” ;
cout<<"测试 Delete()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.Delete(0)<<" ";
}
计算机学院信息教研室
DS
顺序表类的应用单循环链表 (Circular Linked List)
循环链表是单链表的变形。
相同点：两者结点结构相同。
不同点：循环链表最后一个结点的
next指针不为 0 (NULL)，而是指向了表的前端。
特点：只要知道表中某一结点的地址，就可搜寻到所有其他结点。
计算机学院信息教研室
xdc
DS
head
#include<iostream.h>
#include<stdio.h>
template<class T>class CirList; //前视定义，
否则，无法定义友元
template<class T>class ListNode
{
friend class CirList<T>; //定义友元
…
}
计算机学院信息教研室
DS
ListNode.h
单循环链表类的定义
template<class T>class CirList
{
private:
ListNode<T> *head; //指向头结点的指针
int size; //单循环链表的元素个数
ListNode<T> *currPtr; //当前结点个数
public:
CirList(void); //构造函数
~CirList(void); //析构函数
…
}
计算机学院信息教研室
DS
CirList.h
{
private:
…
public:
…
int ListSize(void) const; //返回链表的元素个数
int ListEmpty(void) const;
ListNode<T> *Index(int pos); //定位
void Insert(const T& item,int pos); //插入
T Delete(int pos); //删除
T GetData(int pos); //取元素
void ClearList(void); //清空链表
}
计算机学院信息教研室
DS
{
private:
…
public:
…
ListNode<T> *Reset(int pos=0); //把第 pos个结点设置为当前结点 currPtr
ListNode<T> *Next(void); //currPtr指向下一个结点
int EndOfList(void) const; //currPtr是否指在链表尾
//单循环链表的补充成员函数
int NextEndOfList()const //currPtr->next是否链表尾；
T DeleteAfter(); //删除 currPtr->next所指结点并返回被删除结点的 data
}
计算机学院信息教研室
DS
单循环链表类的 实现
template<class T>
CirList<T>::CirList()//构造函数
{
head = new ListNode<T>();
head->next = head;
size = 0;
}
计算机学院信息教研室
DS
CirList.cpp
head
template<class T>
CirList<T>::ListNode<T> *Next(void)
//currPtr指向下一个结点
{
currPtr = currPtr->next;
return currPtr;
}
计算机学院信息教研室
DS
template<class T>
int CirList<T>::EndOfList(void) const
//currPtr是否指在链表尾
{
if(currPtr == head)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
template<class T>
int CirList<T>::NextEndOfList() const
//currPtr->next是否链表尾
{
if(currPtr->next == head)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
template<class T>
T CirList<T>::DeleteAfter(); //删除 currPtr->next所指结点并返回被删除结点的 data
{
ListNode<T> *p = currPtr->next; //p指向要删除的结点
currPtr->next = p->next; //currPtr->next结点脱链
T data = p->data;
delete p;
size--;
return data;
}
计算机学院信息教研室
DS
8761 2head 3 54
(约瑟夫问题 ) 设有 n个认为成一个圆圈，任意给出一个整整数 m,从第一个人开始计数，数到第 m个人时被从圆圈中删除。问最后剩下的是哪个人。
计算机学院信息教研室
DS
单 循环链表的应用 ----约瑟夫问题单 循环链表的应用 ----约瑟夫问题计算机学院信息教研室
DS
例如 n = 8 m = 3
#include "CirList.h"
template<class T>
void Josephus(CirList<T> &CList,int n,int m) //约瑟夫环函数
{
ListNode<T> *p;
cout<<"删除次序为,"<<endl;
CList.Reset(-1);
for(int i = 0; i<n-1; i++)
{
for(int j=0; j<m-1,j++)
{
p = CList.Next();
if(CList.EndOfList())
p = CList.Next();
}
if(CList.NextEndOfList())
p = CList.Next();
cout<<"删除第 "<<CList.DeleteAfter()<<"人 "<<endl;
}
cout<<"最后剩下的是：第 "<<CList.GetData(0)<<"个人 "<<endl;
}
计算机学院信息教研室
DS
8761 2head 3 54
void main(void)
{
CirList<int>myCirList; //定义 int型的 CirList类对象
int n,m;
cout<<"输入 n:";
cin>>n;
cout<<"输入 m:";
cin>>m;
for(int i=0;i<n;i++)
myCirList.Insert(i+1,i); //形成约瑟夫环
cout<<"人员编号依次为,";
ListNode<int> *p = myCirList.Reset();
while(!myCirList.EndOfList())
{
cout<<p->data<<" ";
p = myCirList.Next();
}
cout<<endl;
Josephus(myCirList,n,m); 调用约瑟夫环的函数
}
计算机学院信息教研室
DS
双向 循环 链表 (Doubly Circular Linked List)
双向链表是指在前驱和后继方向都能遍历的线性链表。
双向链表每个结点结构：
前驱方向 后继方向双向链表通常采用带表头结点的循环链表形式。
计算机学院信息教研室
DS
ll LL ii nn kk
(( 左左 链链 指指 针针 ))
dd aa tt aa
(( 数数 据据 ))
rr LL ii nn kk
(( 右右 链链 指指 针针 ))
双向 循环 链表 (Doubly Circular Linked List)
计算机学院信息教研室
DS
结点指针的指向
p == p→ prior→ next == p→ next→ prior
双向链表 类的实现
template<class T> //构造函数
DCirList<T>::DCirList()
{
head = new DLNode<T>();
head->next = head;
head->prior = head;
size = 0;
}
计算机学院信息教研室
DS
DCirList.cpp
head
计算机学院信息教研室
DS
item
a b
newNode
p
1 3 24
双向链表 类的实现
template<class T>
void DCirList<T>::Insert(const T&item,int pos)
{
DLNode<T> *p = Index(pos);
DLNode<T> *newNode = new DLNode<T>(item,NULL,NULL);
newNode->prior = p->prior; //1
newNode->next = next; //2
p->prior->next = newNode; //3
p->prior = newNode; //4
size++;
}
计算机学院信息教研室
DS
DCirList.cpp
双向链表 类的实现
template<class T>
T DCirList<T>::Delete(int pos)
{
...
DLNode<T> *p = Index(pos);
p->prior->next = p->next;
p->next->prior = p->prior;
T data = p->data;
delete p;
size--;
return data;
}
计算机学院信息教研室
DS
DCirList.cpp
a cb
p
双向链表 类的实现
template<class T>
T DCirList<T>::DeleteAt()
{
DLNode<T> *p = currPtr->prior;
currPtr->prior->next = currPtr->next;
currPtr->next->prior = currPtr->prior;
T data = currPtr->data;
delete currPtr;
currPtr = p;
size--;
return data;
}
计算机学院信息教研室
DS
DCirList.cpp
a cb
p
currPtrp
链式堆栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头不带头结点的链式堆栈插入时可直接把新结点插入到头指针后，删除时可直接删除头指针所指的结点，因此链式堆栈不需要头结点时更方便。
计算机学院信息教研室
DS
an-1 an-2 an-3 a0
结点 类的 定义 和实现
#include<iostream.h>
#include<stdlib.h>
template <class T> class LinStack; //前视定义
template <class T>
class StackNode
{
friend class LinStack<T>; //定义类为友元
private,
StackNode<T> *next; //结点链指针
public:
T data;
StackNode(const T&item,StackNode<T> *ptrNext
= NULL); //构造函数
~StackNode(){};
};
计算机学院信息教研室
DS
StackNode.h
结点 类的定义和 实现
StackNode(const T &item,StackNode<T>*ptrNext)
{
data = item;
next = ptrNext;
}
计算机学院信息教研室
DS
StackNode.cpp
data next
链式堆栈类的 定义 和实现
template <class T>
class LinStack
{
private:
StackNode<T> *top;
int size;
public:
LinStack(void);
~LinStack(void);
int StackSize(void)const;
int StackEmpty(void)const;
void Push (const T& item);
T Pop(void);
T Peek(void);
void ClearStack(void);
}
计算机学院信息教研室
DS
LinStack.h
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::LinStack() //构造函数
{
top = NULL;
size = 0;
}
template<class T>
LinStack<T>::~LinStack() //析够函数
{
ClearStack();
top = NULL;
}
计算机学院信息教研室
DS
LinStack.cpp
an-1 an-2 an-3 a0
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::StackSize(void)const
{
return size;
}
template<class T>
LinStack<T>::StackEmpty(void)const
{
if(size<=0)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
StackNode.cpp
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::Push(const T& item)
{
StackNode<T> *newNode= new StackNode<T>(item,top);
top = newNode;
size++;
}
template<class T>
LinStack<T>::Peek(void) //返回栈顶结点的 data值
{
return top->data;
}
计算机学院信息教研室
DS
StackNode.cpp
an-1 an-2 an-3 a0
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::Pop(void)
{
if(size == 0)
{
cout<<"堆栈已空，无元素可删！ "<<endl;
exit(1);
}
StackNode<T> *p = top->next;
T data = top->data;
delete top;
size--;
top = p;
retrun data;
}
计算机学院信息教研室
DS
StackNode.cpp
an-1 an-2 an-3 a0
p
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::ClearStack(void)
{
StackNode<T> *p,*p1;
p = top;
while(p! = NULL)
{
p1 = p;
p = p->next;
delete p1;
}
size = 0;
}
计算机学院信息教研室
DS
StackNode.cpp
an-1 an-2 an-3 a0
pp1
4.1 链式 存储结构
4.2 单链表
4.3 单循环链表
4.4 双向循环链表
4.5 链式堆栈
4.6 链式队列
4.7 链式存储结构的特点
4.8 应用问题的面向对象程序设计方法计算机学院信息教研室
DS
4.1链式 存储结构链式 存储结构：初始时为空链，每当有新的数据元素需要存储时，用户向系统动态申请所需的存储空间插入链中。
申请：
名字指针 =new 类型明（初始化值）
释放,Delete 名字指针计算机学院信息教研室
DS
4.1链式 存储结构特点：任意两个在逻辑上相邻的数据元素在物理上不一定相邻。其逻辑顺序是通过链中的指针来实现的。
为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，
这个信息称为指针 (pointer)或链 (link)。
计算机学院信息教研室
DS
4.1链式 存储结构链式 存储结构数据元素集合的方法是用结点（ Node）构造链。计算机学院信息教研室
DS
data next
其中,data域是数据域，用来存放结点的值。
next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。
4.1链式 存储结构头结点是指头指针所指的不存放数据元素的结点。
其中,带头结点的链式结构在表的存储中更为常见。不带头结点的链式结构在栈和队列的存储中更为常见。
空指针在算法描述中用 NULL来表示，空指针是一个特殊的标识，用来表识链的结束。
计算机学院信息教研室
DS
4.2 单链表（ Single Linked)
链表正是通过每个结点的链域将线性表的 n个结点 按其逻辑次序链接 在一起的。由于上述链表的每一个结点 只有一个链域,故将这种链表称为单链表（ Single Linked)。
例 1、线性表,(bat,cat,eat,fat,hat,jat，
lat,mat)
计算机学院信息教研室
DS
bat cat eat mat ^ …
head
单链表 (Singly Linked List)
特点
每个元素 (表项 )由结点 (Node)构成。
线性结构
结点可以不连续存储
表可扩充计算机学院信息教研室
a0 a1 an ^…head
data next
单链表的存储映像计算机学院信息教研室单链表的类模板计算机学院信息教研室
DS
类模板将类的数据成员和成员函数设计得更完整、更灵活。
类模板更易于复用。
在单链表的类模板定义中，增加了 表头结点 。
由图分析：单链表的基本组成部分是结点，
一个单链表可用该单链表的头指针来表示。（用类的组合来实现）
先设计结点类定义单链表类计算机学院信息教研室
DS
a0 a1 an ^ …head
data next
a0 a1 an ^ …head
4.2.1 结点类的定义和实现数据成员：数据域 data（ 公有,应用问题要使用 ）
指针域 next（ 私有）
private:
ListNode<T> *next; //该指针是结点类的对象成员函数：
初始化构造一个结点对象（头结点）
新建立一个结点,(指向下一个结点的指针 )
计算机学院信息教研室
DS data next
4.2.1 结点类的定义和实现
#include<iostream.h>
#include<stdio.h>
template<class T>class LinList; //前视定义，否则，无法定义友元
template<class T>class ListNode
{
friend class LinList<T>; //定义友元
private:
ListNode<T> *next; //指向下一个结点的指针
public:
…
}
计算机学院信息教研室
DS
ListNode.h
4.2.1 结点类的定义和实现
{
…
public:
T data; //定义公有成员便于访问
ListNode(ListNode<T> *ptrNext = NULL);
//构造函数，用于构造头结点
ListNode(const T& item,ListNode<T>
*ptrNext = NULL); //构造函数，非头结点
~ListNode(){}; //析构函数
}
计算机学院信息教研室
DS
ListNode.h
4.2.1 结点类的定义和实现
template<class T>
ListNode<T>::ListNode(ListNode<T>
*ptrNext):next(ptrNext)
{ }
template<class T>
ListNode<T>::ListNode(const T
&item,ListNode<T> *ptrNext)
{
data = item;
next = ptrNext;
}
计算机学院信息教研室
DS
ListNode.cpp
4.2.2 单链表类的 定义 和实现数据成员 (1)头指针（ 2）元素个数（ 3）当前结点指针成员函数,3组
（ 1）构造函数和析构函数
（ 2）表操作的成员函数（任何对单链表结点的操作都要从头结点开始）
（ 3）遍历函数（为什么要提出？）
计算机学院信息教研室
DS a0 a1 an ^ …head
template<class T>class LinList
{
private:
ListNode<T> *head; //指向头结点的指针
int size; //单链表的元素个数
ListNode<T> *currPtr; //当前结点指针
public:
LinList(void); //构造函数
~LinList(void); //析构函数
…
}
计算机学院信息教研室
DS
4.2.2 单链表类的 定义 和实现
Linlist.h
template<class T>class LinList
{
private:
public:
…
int ListSize(void) const; //返回链表的元素个数
int ListEmpty(void) const;
ListNode<T> *Index(int pos); //定位
void Insert(const T& item,int pos); //插入
T Delete(int pos); //删除
T GetData(int pos); //取元素
void ClearList(void); //清空链表
…
}
计算机学院信息教研室
DS
4.2.2 单链表类的 定义 和实现
Linlist.h
表操作的成员函数
template<class T>class LinList
{
private:
public:
…
ListNode<T> *Reset(int pos=0); //把第
pos个结点设置为当前结点 currPtr
ListNode<T> *Next(void); //currPtr指向下一个结点
int EndOfList(void) const; //currPtr是否指在链表尾
}
计算机学院信息教研室
DS
4.2.2 单链表类的 定义 和实现
Linlist.h
遍历表的函数
template<class T>
LinList<T>::LinList() //构造函数
{
head = new ListNode<T>();
size = 0;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
head ^
template<class T>
LinList<T>::~LinList(void) //析构函数
{
ClearList(); //释放所有非头结点
delete head; //释放头结点
head = NULL;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
a0 a1 an ^…head
head ^
template<class T>
int LinList<T>::ListSize(void) const //返回链表的个数
{
return size;
}
template<class T>
int LinList<T>::ListEmpty(void) const //判断是否为空
{
if(size <= 0)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
template<class T>
ListNode<T> *LinList<T>::Index(int pos) //定位，返回指向第 pos个结点的指针
{
if(pos < -1||pos > size)
{
cout<<"参数 pos越界出错！ "<<endl;exit(1);
}
if(pos = -1) return head; //pos为 -1时，返回头指针 head
ListNode<T> *p = head->next;
int i = 0;
while(p != NULL && i < pos) //寻找第 pos个结点
{
p = p->next;
i++;
}
return p;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现Linlist.cpp
a0 a1 an ^…head
posp
template<class T>
void LinList<T>::Insert(const T& item,int pos) //在 pos个结点之前插入一个 data域为 item的新结点
{
ListNode<T> *p = Index(pos-1);
ListNode<T> *newNode = new ListNode<T>(item,p->next);
p->next = newNode;
size++;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
ai-1 ai an ^…head
x 1
2
p
计算机学院信息教研室
DS
head a
i+1 an ^ ai …ai-1a0 …
qP
template<class T>
T LinList<T>::Delete(int pos) //删除第 pos
个结点，并返回被删除结点的 data
{
if(size == 0)
{
cour<<"链表已空无元素可删 !"<<endl;
exit(1);
}
…,
计算机学院信息教研室
DS
4.2.2 单链表类的定义和 实现
Linlist.cpp
head
ai+1 an ^ ai …ai-1a0 …
qP
{
…
ListNode<T> *q,*p = Index(pos - 1); //p指向第 pos-1个结点
q = p->next; //q指向第 pos个结点
p->next = p->next->next; //第 pos个结点脱链
T data = q->data;
delete q; //释放第 pos个结点
size--;
return data;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和实现
Linlist.cpp
head
ai+1 an ^ ai …ai-1a0 …
qP
template<class T>
T LinList<T>::GetData(int pos) //返回第 pos个结点的 data值
{
ListNode<T> *p = Index(pos);
return p->data;
}
计算机学院信息教研室
DS
4.2.2 单链表类的定义和实现
Linlist.cpp
template<class T>
void LinList<T>::ClearList(void) //清空表为初始化状态
{
ListNode<T> *p,*p1;
p = head->next; //p指向第一个结点
while(p != NULL) //循环释放结点空间直至初始化状态
{
p1 = p;
p = p->next;
delete p1;
}
size = 0;
}
计算机学院信息教研室
DS
Linlist.cpp
a0 a1 an ^…head
head ^
p
p1
4.2.2 单链表类的定义和实现
template<class T>
ListNode<T> LinList<T>::Reset(int pos) //把第 pos个结点设置为当前结点 currPtr
{
if(head == NULL) return NULL;
if(pos < -1 || pos > size)
{
cout<<"参数 pos越界出错！ "<<endl;
exit(1);
}
if(pos == -1) return head;
…
}
计算机学院信息教研室
DS
Linlist.cpp
4.2.2 单链表类的定义和实现
{
…
if(pos == 0) return head->next;
else 定为指针 currPtr的值
{
currPtr = head->next;
ListNode<T> *prePtr = head;
for(int i = 0; i < pos; i++) 循环定位 currPtr指向结点 pos
{
prePtr = currPtr;
currPtr = currPtr->next;
}
}
return currPtr;
}
计算机学院信息教研室
DS
Linlist.cpp
a0 a1 an ^…head
poscurrPtrprePtr
4.2.2 单链表类的定义和实现
template<class T>
LinList<T>::ListNode<T> *Next(void)
//currPtr指向下一个结点
{
if(currPtr != NULL)
currPtr = currPtr->next;
return currPtr;
}
计算机学院信息教研室
DS
Linlist.cpp
a0 a1 an ^…head
currPtr
4.2.2 单链表类的定义和实现
template<class T>
int LinList<T>::EndOfList(void) const
//currPtr是否指在链表尾
{
if(currPtr == NULL)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
a0 a1 an ^…head
4.2.2 单链表类的定义和实现定位，前插入、删除和取元素成员函数的时间复杂度均为 O(n).
与顺序表相比，链表类增加了一组循环遍历成员函数。可以有效降低对循环遍历操作的时间复杂度。 (为什么？ )
计算机学院信息教研室
DS
a0 a1 an ^…head
#include "LinList.h"
void main(void)
{
LinList<int> myList;
for(int i=0;i<5;i++)
myList.Insert(i+10,i);
cout<<"测试 GetData()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.GetData(i)<<" ";
cout<<"测试遍历成员函数结果如下,"<<endl;
ListNode<int> *p = myList.Reset(); //p指在第一个结点
while(!myList.EndOfList()) //是否到达表尾
{
cout<<myList.Next<<" ";
p = myList.Next(); //p指在第一个结点
}
}
计算机学院信息教研室
DS
单链表类的应用表和顺序表
typedef int DataType; //具体应用时定义的数据类型 Datatype
#include "seqlist.h" //类 Seqlist的定义和实现头文件
void main(void)
{
SeqList myList; //插入 5个整型元素
for(int i=0;i<5;i++)
myList.Insert(i+10,i);
cout<<"测试 GetData()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.GetData(i)<<,” ;
cout<<"测试 Delete()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.Delete(0)<<" ";
}
计算机学院信息教研室
DS
顺序表类的应用单循环链表 (Circular Linked List)
循环链表是单链表的变形。
相同点：两者结点结构相同。
不同点：循环链表最后一个结点的
next指针不为 0 (NULL)，而是指向了表的前端。
特点：只要知道表中某一结点的地址，就可搜寻到所有其他结点。
计算机学院信息教研室
xdc
DS
head
#include<iostream.h>
#include<stdio.h>
template<class T>class CirList; //前视定义，
否则，无法定义友元
template<class T>class ListNode
{
friend class CirList<T>; //定义友元
…
}
计算机学院信息教研室
DS
ListNode.h
单循环链表类的定义
template<class T>class CirList
{
private:
ListNode<T> *head; //指向头结点的指针
int size; //单循环链表的元素个数
ListNode<T> *currPtr; //当前结点个数
public:
CirList(void); //构造函数
~CirList(void); //析构函数
…
}
计算机学院信息教研室
DS
CirList.h
{
private:
…
public:
…
int ListSize(void) const; //返回链表的元素个数
int ListEmpty(void) const;
ListNode<T> *Index(int pos); //定位
void Insert(const T& item,int pos); //插入
T Delete(int pos); //删除
T GetData(int pos); //取元素
void ClearList(void); //清空链表
}
计算机学院信息教研室
DS
{
private:
…
public:
…
ListNode<T> *Reset(int pos=0); //把第 pos个结点设置为当前结点 currPtr
ListNode<T> *Next(void); //currPtr指向下一个结点
int EndOfList(void) const; //currPtr是否指在链表尾
//单循环链表的补充成员函数
int NextEndOfList()const //currPtr->next是否链表尾；
T DeleteAfter(); //删除 currPtr->next所指结点并返回被删除结点的 data
}
计算机学院信息教研室
DS
单循环链表类的 实现
template<class T>
CirList<T>::CirList()//构造函数
{
head = new ListNode<T>();
head->next = head;
size = 0;
}
计算机学院信息教研室
DS
CirList.cpp
head
template<class T>
CirList<T>::ListNode<T> *Next(void)
//currPtr指向下一个结点
{
currPtr = currPtr->next;
return currPtr;
}
计算机学院信息教研室
DS
template<class T>
int CirList<T>::EndOfList(void) const
//currPtr是否指在链表尾
{
if(currPtr == head)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
template<class T>
int CirList<T>::NextEndOfList() const
//currPtr->next是否链表尾
{
if(currPtr->next == head)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
template<class T>
T CirList<T>::DeleteAfter(); //删除 currPtr->next所指结点并返回被删除结点的 data
{
ListNode<T> *p = currPtr->next; //p指向要删除的结点
currPtr->next = p->next; //currPtr->next结点脱链
T data = p->data;
delete p;
size--;
return data;
}
计算机学院信息教研室
DS
8761 2head 3 54
(约瑟夫问题 ) 设有 n个认为成一个圆圈，任意给出一个整整数 m,从第一个人开始计数，数到第 m个人时被从圆圈中删除。问最后剩下的是哪个人。
计算机学院信息教研室
DS
单 循环链表的应用 ----约瑟夫问题单 循环链表的应用 ----约瑟夫问题计算机学院信息教研室
DS
例如 n = 8 m = 3
#include "CirList.h"
template<class T>
void Josephus(CirList<T> &CList,int n,int m) //约瑟夫环函数
{
ListNode<T> *p;
cout<<"删除次序为,"<<endl;
CList.Reset(-1);
for(int i = 0; i<n-1; i++)
{
for(int j=0; j<m-1,j++)
{
p = CList.Next();
if(CList.EndOfList())
p = CList.Next();
}
if(CList.NextEndOfList())
p = CList.Next();
cout<<"删除第 "<<CList.DeleteAfter()<<"人 "<<endl;
}
cout<<"最后剩下的是：第 "<<CList.GetData(0)<<"个人 "<<endl;
}
计算机学院信息教研室
DS
8761 2head 3 54
void main(void)
{
CirList<int>myCirList; //定义 int型的 CirList类对象
int n,m;
cout<<"输入 n:";
cin>>n;
cout<<"输入 m:";
cin>>m;
for(int i=0;i<n;i++)
myCirList.Insert(i+1,i); //形成约瑟夫环
cout<<"人员编号依次为,";
ListNode<int> *p = myCirList.Reset();
while(!myCirList.EndOfList())
{
cout<<p->data<<" ";
p = myCirList.Next();
}
cout<<endl;
Josephus(myCirList,n,m); 调用约瑟夫环的函数
}
计算机学院信息教研室
DS
双向 循环 链表 (Doubly Circular Linked List)
双向链表是指在前驱和后继方向都能遍历的线性链表。
双向链表每个结点结构：
前驱方向 后继方向双向链表通常采用带表头结点的循环链表形式。
计算机学院信息教研室
DS
ll LL ii nn kk
(( 左左 链链 指指 针针 ))
dd aa tt aa
(( 数数 据据 ))
rr LL ii nn kk
(( 右右 链链 指指 针针 ))
双向 循环 链表 (Doubly Circular Linked List)
计算机学院信息教研室
DS
结点指针的指向
p == p→ prior→ next == p→ next→ prior
双向链表 类的实现
template<class T> //构造函数
DCirList<T>::DCirList()
{
head = new DLNode<T>();
head->next = head;
head->prior = head;
size = 0;
}
计算机学院信息教研室
DS
DCirList.cpp
head
计算机学院信息教研室
DS
item
a b
newNode
p
1 3 24
双向链表 类的实现
template<class T>
void DCirList<T>::Insert(const T&item,int pos)
{
DLNode<T> *p = Index(pos);
DLNode<T> *newNode = new DLNode<T>(item,NULL,NULL);
newNode->prior = p->prior; //1
newNode->next = next; //2
p->prior->next = newNode; //3
p->prior = newNode; //4
size++;
}
计算机学院信息教研室
DS
DCirList.cpp
双向链表 类的实现
template<class T>
T DCirList<T>::Delete(int pos)
{
...
DLNode<T> *p = Index(pos);
p->prior->next = p->next;
p->next->prior = p->prior;
T data = p->data;
delete p;
size--;
return data;
}
计算机学院信息教研室
DS
DCirList.cpp
a cb
p
双向链表 类的实现
template<class T>
T DCirList<T>::DeleteAt()
{
DLNode<T> *p = currPtr->prior;
currPtr->prior->next = currPtr->next;
currPtr->next->prior = currPtr->prior;
T data = currPtr->data;
delete currPtr;
currPtr = p;
size--;
return data;
}
计算机学院信息教研室
DS
DCirList.cpp
a cb
p
currPtrp
链式堆栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头不带头结点的链式堆栈插入时可直接把新结点插入到头指针后，删除时可直接删除头指针所指的结点，因此链式堆栈不需要头结点时更方便。
计算机学院信息教研室
DS
an-1 an-2 an-3 a0
结点 类的 定义 和实现
#include<iostream.h>
#include<stdlib.h>
template <class T> class LinStack; //前视定义
template <class T>
class StackNode
{
friend class LinStack<T>; //定义类为友元
private,
StackNode<T> *next; //结点链指针
public:
T data;
StackNode(const T&item,StackNode<T> *ptrNext
= NULL); //构造函数
~StackNode(){};
};
计算机学院信息教研室
DS
StackNode.h
结点 类的定义和 实现
StackNode(const T &item,StackNode<T>*ptrNext)
{
data = item;
next = ptrNext;
}
计算机学院信息教研室
DS
StackNode.cpp
data next
链式堆栈类的 定义 和实现
template <class T>
class LinStack
{
private:
StackNode<T> *top;
int size;
public:
LinStack(void);
~LinStack(void);
int StackSize(void)const;
int StackEmpty(void)const;
void Push (const T& item);
T Pop(void);
T Peek(void);
void ClearStack(void);
}
计算机学院信息教研室
DS
LinStack.h
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::LinStack() //构造函数
{
top = NULL;
size = 0;
}
template<class T>
LinStack<T>::~LinStack() //析够函数
{
ClearStack();
top = NULL;
}
计算机学院信息教研室
DS
LinStack.cpp
an-1 an-2 an-3 a0
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::StackSize(void)const
{
return size;
}
template<class T>
LinStack<T>::StackEmpty(void)const
{
if(size<=0)
return 1;
else
return 0;
}
计算机学院信息教研室
DS
StackNode.cpp
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::Push(const T& item)
{
StackNode<T> *newNode= new StackNode<T>(item,top);
top = newNode;
size++;
}
template<class T>
LinStack<T>::Peek(void) //返回栈顶结点的 data值
{
return top->data;
}
计算机学院信息教研室
DS
StackNode.cpp
an-1 an-2 an-3 a0
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::Pop(void)
{
if(size == 0)
{
cout<<"堆栈已空，无元素可删！ "<<endl;
exit(1);
}
StackNode<T> *p = top->next;
T data = top->data;
delete top;
size--;
top = p;
retrun data;
}
计算机学院信息教研室
DS
StackNode.cpp
an-1 an-2 an-3 a0
p
链式堆栈类的定义和 实现
template<class T>
LinStack<T>::ClearStack(void)
{
StackNode<T> *p,*p1;
p = top;
while(p! = NULL)
{
p1 = p;
p = p->next;
delete p1;
}
size = 0;
}
计算机学院信息教研室
DS
StackNode.cpp
an-1 an-2 an-3 a0
pp1
