1
2
§ 3.1 栈
? (一 )基本概念
? 栈 是一种限定仅在表的一端进行插入与删除的线性表
? 允许进行插入与删除的这一端称为 栈顶,而另一端称为 栈底
? 不含元素的空表称为 空栈
? 插入与删除分别称 进栈 与 出栈 。
? 栈也称作 先进后出 （ First In Last Out）的线性表，简称 FILO表
§ 3.1.1 栈的逻辑结构
a1 a2 a3 a4 … an
栈
底
栈
顶
进栈
出栈
图 -栈示意图
3
? (一 )基本概念
? 栈应用的例子
– 火车扳道站
– 进入单车道死胡同的汽车
– 记录中断返回地址（断点）的结构
§ 3.1.1 栈的逻辑结构
4
§ 3.1.1 栈的逻辑结构
? (一 )基本概念
? 可能的出栈次序
? 设 n=3，按 1,2,3的次序进栈，则可能的出栈
次序为
1 2 3,1 3 2,2 1 3,2 3 1,3 2 1
不可能的次序是：
3 1 2
? 对任意元素 k，若它后面有小于它的元素，则
这些小于它的元素必须以, 逆序, 出现
5
§ 3.1.1 栈的逻辑结构
? (二 ) 基本操作
? Init(s)：初始化栈 s。 设定一个空栈, 栈的所有其它操作仅在此
操作执行 （ 或隐含执行 ） 之后才能进行 。
? Empty(s)：判定函数 。 若栈 s为空, 返回, 真,, 否则返回
,假, 。
? Push(s,x)：入栈函数 。 将元素 x放到栈顶上, 栈溢出时应返回特
殊标志 。
? Pop(S)：出栈函数 。 栈 s不空时, 将栈顶元素摘除, 并返回该元
素 。 否则触发异常 。
? GetTop(s)：读栈顶元素函数 。 与 Pop(s)类似, 但不摘取栈顶元
素 。
? Clear(s)：清除操作 。 使栈 s重新变为一个空栈 。 这里, s是个已
存在的栈 。
? Len(s)：求长度函数 。 返回栈 s中元素个数 。
6
§ 3.1.1 栈的逻辑结构
? (三 ) 基本操作使用示例
? 编写一个带编辑功能的从终端上接收字符的程序
? 若依次输入：
Cg#HIna##NA
则相当于输入 CHINA
? 若依次输入
chi@CHINA
? 则相当于输入 CHINA
“#”代表退格 ；
,@”表示作废
7
… …
Init(s);
ch = getch(); //读入一个字符
while (ch!=EOF) //当未读入结束符时, 一直循环
{
switch(ch)
{
case '#',
Pop(s); break;
case '@',
Clear(s); break;
default:
Push(s,ch);
}
ch = getch();
}
8
§ 3.1.1 栈的逻辑结构
? (四 )栈抽象类
template <class TElem>
class TStack0
{
protected:
long len;
public:
long GetLen (void) {return len; };
char IsEmpty ( ) {return (len<=0)? 1:0; };
virtual TElem& Push (TElem &elem) =0;
virtual TElem& Pop (void) =0;
virtual TElem& GetTop (void) =0;
9
§ 3.1.1 栈的逻辑结构
? (四 )栈抽象类
virtual TElem& RollDown ( ) =0;
virtual TElem& RollUp ( ) =0;
virtual void Clear ( ) =0;
}
10
§ 3.1.2 栈的顺序存贮结构
? (一 ) 存贮方法
? 栈是一种特殊的线性表, 本节先介绍顺序存贮方式
? 用一维数组模拟连续的存贮空间
? 用一个量指示插入 /删除端的位置，一般称该量为 栈顶
指针
a1 a2 a3 a4 … … an元素空间：
栈顶指示器：
图 - 栈顺序存储结构
假设栈底在地址小的一端
11
§ 3.1.2 栈的顺序存贮结构
? (二 ) 顺序栈类
template <class TElem>
class TStackSqu, public TStack0<TElem>
{
protected:
TElem *room;
TElem elemBuff;
long size;
long CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2);
long ResizeRoom (long newSize);
12
§ 3.1.2 栈的顺序存贮结构
? (二 ) 顺序栈类
public:
TStackSqu ();
TStackSqu (long mSize);
~TStackSqu ();
virtual TElem& Push (TElem &elem);
virtual TElem& Pop (void);
virtual TElem& GetTop (void);
virtual TElem& RollDown ( );
virtual TElem& RollUp ( );
virtual void Clear ( );
virtual void Print ( );
}
13
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TStackSqu<TElem>::TStackSqu ( )
{
room=NULL;
size=0;
len=0;
}
14
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TStackSqu<TElem>::TStackSqu (long mSize)
{
len=0;
room=new TElem[mSize];
if (room==NULL) throw TExcepComm(4);
size=mSize;
}
15
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TStackSqu<TElem>::~TStackSqu ( )
{
if (room!=NULL) delete[] room;
}
16
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::Push (TElem &elem)
{
if (len>=size-1)
{
long ret=ResizeRoom(size+10);
if (ret<0) throw TExcepComm(3);
}
room[len]=elem;
len++;
return room[len-1];
}
17
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::Pop (void)
{
if (len<=0) throw TExcepComm(3);
len--;
return room[len];
}
18
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::GetTop (void)
{
return room[len-1];
}
template <class TElem>
void TStackSqu<TElem>::Clear ( )
{
len=0;
}
19
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::RollUp ( )
{
unsigned x;
x=room[0];
for (long i=1; i<len; i++)
room[i-1]=room[i];
room[len-1]=x;
return room[len-1];
}
20
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::RollDown ( )
{
unsigned x;
x=room[len-1];
for (int i=len-2; i>=0; i--)
room[i+1]=room[i];
room[0]=x;
return room[len-1];
}
21
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
longTStackSqu< TElem>::
CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2)
{
long i,k;
k=n2;
if (k>n1) k=n1;
for (i=0; i<k; i++)
objRoom[i] = srcRoom[i];
return k;
}
22
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
longTStackSqu< TElem>::ResizeRoom (long newSize)
{
long i,k;
TElem *pE;
pE= new TElem[newSize];
if (pE==NULL) throw TExcepComm(2);
len = CopyRoom (pE,newSize,room,len);
if (room!=NULL) delete room;
room = pE;
size=newSize;
return len;
}
23
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
void TStackSqu<TElem>::Print ( )
{
cout << '\n';
for (long i=0; i<len; i++)
cout<<' '<<room[i] ;
}
24
§ 3.1.3 栈的链式存贮结构
? (一 ) 存储方法
? 栈采用链式存贮结构主要目的是避免存贮区的
预申请问题
图 - 链式栈基本形式
an-1 a1 ^top
len
an
栈头
TStackLink
链结点, 栈顶
TLinkNode
25
§ 3.1.3 栈的链式存贮结构
? (二 ) 面向对象描述
? 栈采用链式存贮结构主要目的是避免存贮区的
预申请问题
template <class TElem>
struct TLinkNode
{
TElem info;
TLinkNode *next; //Note,not necessay for
<TElem> to follow TLinkNode here
};
26
§ 3.1.3 栈的链式存贮结构
? (二 ) 面向对象描述
类 TStackLink定义如下：
template <class TElem>
class TStackLink, public TStack0<TElem>
{
protected:
TLinkNode<TElem> *top;
TElem elemBuff;
public:
TStackLink();
~TStackLink();
virtual TElem& Push (TElem &elem);
virtual TElem& Pop (void);
virtual TElem& GetTop (void);
27
§ 3.1.3 栈的链式存贮结构
? (二 ) 面向对象描述
virtual TElem& RollDown ( );
virtual TElem& RollUp ( );
virtual void Clear ( );
//New functions
virtual TLinkNode<TElem>* PushNode (TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem>* PopNode (void);
virtual const TLinkNode<TElem>* GetTopNode (void);
virtual void Print ( );
}
28
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
1,初始化
template <class TElem>
TStackLink<TElem>::TStackLink ( )
{
top = NULL;
len=0;
}
template <class TElem>
TStackLink<TElem>::~TStackLink ( )
{
Clear ( );
}
29
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
2,进栈 Push(TElem&elem)
template <class TElem>
TElem& TStackLink<TElem>::Push (TElem &elem)
{
TLinkNode<TElem> *pNode;
pNode = new TLinkNode<TElem>;
if (pNode==NULL) throw TExcepComm(4);
pNode->info = elem ; //TElem must support "="
PushNode(pNode);
return pNode->info;
}
30
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
3,出栈 Pop()
template <class TElem>
TElem& TStackLink<TElem>::Pop (void)
{
TLinkNode<TElem> *pNode;
pNode = PopNode();
elemBuff =pNode->info; //TElem must support "="
delete pNode;
return elemBuff;
}
31
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
4,读栈 GetTop()
template <class TElem>
TElem& TStackLink<TElem>::GetTop (void)
{
return top->info;
}
32
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
5,结点进栈 PushNode(TLinkNode<TElem> *pNode)
template <class TElem>
TLinkNode<TElem>*
TStackLink<TElem>::PushNode(TLinkNode<TElem> *pNode)
{
pNode->next = top;
top = pNode;
len++;
return pNode;
}
33
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
6,结点出栈 PopNode(void) template <class TElem>
template <class TElem>
TLinkNode<TElem> *TStackLink<TElem>::PopNode (void)
{
TLinkNode<TElem> *pNode;
if (top==NULL) throw TExcepComm(5);
elemBuff = top->info; //TElemmust support "="
pNode = top;
top = top->next;
len--;
return pNode;
}
34
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
7,读栈顶结点 GetTopNode(void) template <class TElem>
template <class TElem>
const TLinkNode<TElem>* TStackLink<TElem>::GetTopNode (void)
{
return top;
}
35
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
template <class TElem>
void TStackLink<TElem>::Clear ( )
{
TLinkNode<TElem> *p,*q;
p=top;
while (p!=NULL)
{
q=p;
p=p->next;
delete q;
}
top = NULL;
len=0;
}
36
§ 3.2 队列
? (一 ) 基本概念
? 队列 (Queue)是一种限定仅分别在表的两端进行插入与删
除的线性表 。
? 允许插入的一端称 队尾, 允许删除的一端称 队头 。
? 插入与删除分别称为 入队 与 出队 。
§ 3.2.1 队列的逻辑结构
出队 ← ○ ○ ○ …… ← ○ ○ 进队
队尾队头
图 -队列示意图
37
? (一 ) 基本概念
? 队是一种先进先出 FIFO（ First In First Out）的结构，
元素出队的次序与进队次序相同。
? 应用
? 顾客服务部门的工作方式往往是排队方式
§ 3.2.1 队列的逻辑结构
38
? (二 ) 基本操作
? Init(Q),初始化操作, 设置一个空队列 。
? Empty(Q),判空函数, 若 Q为空, 则返回, 真,, 否则返回, 假, 。
? Enter(Q,x),入队函数, 将元素 x加到队 Q中 。
? Exit(Q),出队操作, 将队头元素摘除并返回之 。
? GetHead(Q),访问队头元素 （ 返回队头元素 ）, 但不摘除 。
? Clear(Q),将队列 Q清空 。
? Len(Q),返回队 Q中元素个数 。
§ 3.2.1 队列的逻辑结构
39
? (一 )非循环队列
? 1,存储方法
? 连续存贮结构, 用一维数组作队元素存贮空间
? 另设两个指示器, 分别指示队头与队尾 （ 分别称对头与队尾指针 ）
§ 3.2.2 队列的连续存贮结构
a1 a2 a3 …… an
图 - 连结存贮结构的队列
room:
front rear 初始状态：front=rear=0
40
? (一 )非循环队列
? 2,进队
? 进队是将元素添加到队尾, 故需访问队尾指针 rear,将元
素 x进队 Q的操作为：
if (队满 ) 触发异常；
Q->rear++;
Q->room[rear] = x;
§ 3.2.2 队列的连续存贮结构
41
? (一 )非循环队列
? 3,出队
? 出队是将当前队中头元素摘取并返回其：
if (队空 ) 触发异常；
Q->front++;
return Q->room[Q->front];
§ 3.2.2 队列的连续存贮结构
42
? (一 )非循环队列
? 4,队空 /满问题
? 队列变空时有下列关系成立
Q->front = = Q->rear
? 显然初始状态也满足此式
? rear超过 room的空间大小,这种情况我们称为, 队满,
?, 假满, 问题的解决方法
a)发生假满时, 移动队中元素, 在尾部让出空位 。 但这种方法
效率差,
b)循环队列法 。
§ 3.2.2 队列的连续存贮结构
43
? (二 )循环队列
? 1,基本思想
? 循环队列, 就是指将队列的存贮区域视作循环结构
? 假定：
队头指示器 front：指向队中第 1个元素的前一个位置 。
队尾指示器 rear：指向队尾元素所在位置 。
? 队空与队满的条件分别为：
队空,rear = = front
队满,(rear+1) MOD N = = front
§ 3.2.2 队列的连续存贮结构
44
? (二 )循环队列
? 2,实现
? 首先定义一个抽象类 TQueue0,该类将是各种存储结构的队列的基
础, 规定了通用操作接口 。
template <class TElem>
class TQueue0
{
protected:
longlen;
§ 3.2.2 队列的连续存贮结构
45
? (二 )循环队列
public:
long GetLen (void) {return len; };
char IsEmpty ( ) {return (len<=0)? 1:0; };
virtual TElem& Qpush (TElem &elem) = 0;
virtual TElem& Qpop (void) = 0;
virtual TElem& GetHead (void) = 0;
virtual TElem& RollDown ( ) = 0;
virtual TElem& RollUp ( ) = 0;
virtual void Clear ( ) = 0;
}
§ 3.2.2 队列的连续存贮结构
46
? (二 )循环队列
? 顺序队的具体的存储用类 TQueueSqu描述
template <class TElem>
class TQueueSqu, public TQueue0<TElem>
{
protected:
TElem *room;
TElem elemBuff;
long front,rear,size;
long CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2);
long ResizeRoom (long newSize);
§ 3.2.2 队列的连续存贮结构
47
public:
TQueueSqu ( );
TQueueSqu (long mSize);
~TQueueSqu ( );
virtual TElem& Qpush (TElem &elem);
virtual TElem& Qpop (void);
virtual TElem& GetHead (void);
virtual TElem& RollDown ( );
virtual TElem& RollUp ( );
virtual void Clear ( );
virtual void Print ( );
}
48
? 各主要操作的实现
template <class TElem>
TQueueSqu<TElem>::TQueueSqu ( )
{
room=NULL;
front=0;
rear=0;
size=0;
len=0;
}
49
template <class TElem>
TQueueSqu<TElem>::TQueueSqu (long mSize)
{
len=0;
front=0;
rear=0;
room = new TElem[mSize];
if (room==NULL) throw TExcepComm(4);
size=mSize;
}
50
template <class TElem>
TQueueSqu<TElem>::~TQueueSqu()
{
if (room!=NULL) delete[] room;
}
51
template <class TElem>
TElem& TQueueSqu<TElem>::Qpush (TElem &elem)
{
if (len>=size-1)
{
long ret = ResizeRoom (size +10);
if (ret<0) throw TExcepComm(3);
}
rear++;
if (rear>=size) rear=0;
room[rear]=elem; //TElem must support "="
len++;
return room[rear];
}
52
template <class TElem>
TElem& TQueueSqu<TElem>::Qpop (void)
{
if (len<=0) throw TExcepComm(3);
len--;
front++;
if (front>=size) front=0;
return room[front];
}
53
template <class TElem>
TElem& TQueueSqu<TElem>::GetHead (void)
{
return room [(front+1) % size];
}
template <class TElem>
void TQueueSqu<TElem>::Clear ( )
{
len = 0;
front = rear = 0;
}
54
template <class TElem>
TElem& TQueueSqu<TElem>::RollUp ( )
{ //TElem must support "="
TElem x;
long k,j;
k =front + 1;
if (k>=size) k=0;
x = room[k];
while (k!=rear)
{
j = k;
k++;
if (k>=size) k=0;
room[j] = room[k];
}
room[rear] = x;
return room[(front+1)%size];
}
55
template <class TElem>
TElem& TQueueSqu<TElem>::RollDown ( )
{ //TElem must support "="
TElem x;
long k,j,f0;
f0 = front+1;
if (f0>=size) f0=0;
k =rear ;
x = room[k];
56
while (k!=front)
{
j = k;
k--;
if (k<=0) k=size-1;
room[j] = room[k];
}
room[f0] = x;
return room[f0];
}
57
template <class TElem>
long TQueueSqu< TElem>::CopyRoom (TElem *objRoom,long n1,TElem
*srcRoom,long n2)
{
long i,k;
k=n2;
if (k>n1) k=n1;
for (i=0; i<k; i++)
objRoom[i] = srcRoom[i];
return k;
}
58
template <class TElem>
longTQueueSqu< TElem>::ResizeRoom (long newSize)
{
long i,k;
TElem *pE;
pE= new TElem[newSize];
if (pE==NULL) throw TExcepComm(2);
len = CopyRoom (pE,newSize,room,len);
if (room!=NULL) delete room;
room = pE;
size=newSize;
return len;
}
59
template <class TElem>
void TQueueSqu<TElem>::Print ( )
{
int i;
cout<<'\n';
if (rear == front) return;
i=front+1;
if (i>=size) i = 0;
while (i!=rear)
{
cout<<' '<<room[i];
i++;
if (i>=size) i=0;
}
cout<<' '<<room[i];
}
60
? (一 )存储方法
? 链式队列的元素采用线性链表存储
? 该链表的描述结点应至少含两个指针：队头元素指针与队尾
元素指针，分别令其指向队中首元素与尾元素对应的结点
§ 3.2.3 队列的链式存贮结构
a2 an ^front
rear
len
a1
图 - 链式队列基本形式
队结点
TStackLink
链结点, 队头
TLinkNode 队尾结点
61
? (二 )面向对象描述
? 设立一个类 TQueueLink，其从 TQueue0派生而来
template <class TElem>
struct TLinkNode
{
TElem info;
TLinkNode *next; //Note,not necessay for <TElem> to follow
TLinkNode here
}
§ 3.2.3 队列的链式存贮结构
62
? (二 )面向对象描述
? 设立一个类 TQueueLink，其从 TQueue0派生而来
template <class TElem>
class TQueueLink, public TQueue0<TElem>
{
protected:
TLinkNode<TElem> *front,*rear;
TElem elemBuff;
public:
TQueueLink ( );
~TQueueLink ( );
§ 3.2.3 队列的链式存贮结构
63
? (二 )面向对象描述
virtual TElem& QPush(TElem &elem);
virtual TElem& QPop(void);
virtual TElem& GetHead(void);
virtual TElem& RollDown();
virtual TElem& RollUp();
virtual void Clear();
§ 3.2.3 队列的链式存贮结构
64
? (二 )面向对象描述
//New functions
virtual TLinkNode<TElem>*
QPushNode (TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem>* QPopNode (void);
virtual const TLinkNode<TElem>*
GetHeadNode(void);
virtual void Print ();
}
§ 3.2.3 队列的链式存贮结构
65
? (三 )基本操作实现
template <class TElem>
TQueueLink<TElem>::TQueueLink ( )
{
front = NULL;
rear = NULL;
len = 0;
}
§ 3.2.3 队列的链式存贮结构
66
? (三 )基本操作实现
template <class TElem>
TQueueLink<TElem>::~TQueueLink ( )
{
Clear ( );
}
§ 3.2.3 队列的链式存贮结构
67
? (三 )基本操作实现
template <class TElem>
TElem& TQueueLink<TElem>::Qpush (TElem &elem)
{
TLinkNode<TElem> *pNode;
pNode = new TLinkNode<TElem>;
if (pNode == NULL) throw TExcepComm(4);
pNode->info = elem ; //TElem must support "="
QPushNode(pNode);
return pNode->info;
}
§ 3.2.3 队列的链式存贮结构
68
? (三 )基本操作实现
template <class TElem>
TElem& TQueueLink<TElem>::Qpop (void)
{
TLinkNode<TElem> *pNode;
pNode = QPopNode();
elemBuff =pNode->info; //TElem must support "="
delete pNode;
return elemBuff;
}
§ 3.2.3 队列的链式存贮结构
69
? (三 )基本操作实现
template <class TElem>
TElem& TQueueLink<TElem>::GetHead (void)
{
if (front==NULL) throw TExcepComm(2);
return front->info;
}
§ 3.2.3 队列的链式存贮结构
70
? (三 )基本操作实现
template <class TElem>
TLinkNode<TElem>* TQueueLink<TElem>::
QPushNode (TLinkNode<TElem> *pNode)
{
pNode->next = NULL;
if (rear!=NULL) rear->next = pNode;
else front = pNode;
rear = pNode;
len++;
return pNode;
}
§ 3.2.3 队列的链式存贮结构
71
? (三 )基本操作实现
template <class TElem>
TLinkNode<TElem> *TQueueLink<TElem>::QPopNode (void)
{
TLinkNode<TElem> *pNode;
if (front==NULL) throw TExcepComm(5);
elemBuff = front->info; //TElem must support "="
pNode = front;
front = front->next;
if (front==NULL) rear=NULL;
len--;
return pNode;
}
§ 3.2.3 队列的链式存贮结构
72
? (三 )基本操作实现
template <class TElem>
const TLinkNode<TElem>* TQueueLink<TElem>:,GetHeadNode (void)
{
return front;
}
§ 3.2.3 队列的链式存贮结构
73
? (三 )基本操作实现
template <class TElem>
void TQueueLink<TElem>::Clear ( )
{
TLinkNode<TElem> *p,*q;
p=front;
while (p!=NULL)
{
q=p;
p=p->next;
delete q;
}
front = NULL;
rear = NULL;
len=0;
}
§ 3.2.3 队列的链式存贮结构
74
? 文字（符号）序列称为 字符串,简称 串
? 人名、产品名、事物名称、车牌号、文献、
源程序
? 串被认为是一种特殊线性表 ── 元素为文字符号的线
性表
§ 3.3 串
75
? (一 ) 基本概念
? 串 是由零个或多个字符构成的有限序列, 一般记为
s = "a1a2… an" (n≥ 0)
? s代表 串的名称
? 用双引号括起来的部分（不含该双引号本身）为 串值
（即字符序列）
? 串值中字符个数（即 n）称为 串长
? 长度为 0的串称为 空串
§ 3.3.1 串的逻辑结构
76
? (一 ) 基本概念
? 串中任意个连续字符构成的部分称为该串的 子串
? 包含子串的串相对该子串称为 主串
? 串中某字符在串中出现的序号为该字符在串中的 字符
位置
? 子串中第 1个字符在串中的序号称为该子串在该串中
的 位置
§ 3.3.1 串的逻辑结构
77
? (一 ) 基本概念
? 串的例子
s1="ab123" /*长度为 5的串 */
s2="100" /*长度为 3的串 */
s3=" " /*含两个空格字符的串, 长度为 2*/
s4="" /*空串, 长度为 0*/
? 长度为 n的串中子串总数 （ 包括空串与自身 ） 为
1+ = 1+
§ 3.3.1 串的逻辑结构
?
?
??n
i
in
1
)1(
2
)1( ?nn
78
? (二 )串的比较运算的定义
? 如何定义单个字符间的大小关系？
? 字符间的大小关系就定义为它们的代码之间的大小关
系, 如 ASCII码
? 例如, 字符 A与 B的 ASCII码分别为 65与 66（ 十进制 ）,
则说 'A'<'B'
? 汉字的编码也有几种, 如大陆用的国标码 (GB2312)，
台湾地区用的 Big5等
§ 3.3.1 串的逻辑结构
79
? (二 )串的比较运算的定义
? 下面考虑串之间的大小关系 。 设 X与 Y是两个串：
X="x1x2… xm"
Y="y1y2… yn"
? 则它们之间的大小关系定义如下：
① 当 m=n且 x1=y1,…,xm=yn,则称 X=Y.
② 当下列条件之一成立时, 称 X<Y.
i) m<n,且 xi=yi,i=1,2,…,m
ii)存在某一个 k<=MIN(m,n),使得 xi=yi,i=1,2,…, k-1,xk<yk.
③ 不属于情况①与②时，称 X>Y,
§ 3.3.1 串的逻辑结构
也称字典序
80
? (二 )串的比较运算的定义
? 几个例子
"abac"与 "abac"：相等 (=)
"we"与 "web"：前者小于后者 (情况 i)
"mouth"与 "move"：前者小于后者 （ 情况 ii）
§ 3.3.1 串的逻辑结构
81
? (三 )串的基本操作
? StrChar ( long idx),返回 s中序号为 idx的字符
? StrCopy ( maxNum),将 s的值复制一份
? StrCompare ( s1,mode),串比较函数,比较 s与 s1之间的大小关系
? StrLen ( ),长度函数
? StrConcat ( s1,maxNum),连接函数
? StrCharAt ( ch,mode,sn),字符位置函数
? StrStr ( s1,mode,sn),子串位置函数
? StrSearch ( s1,mode,sn1,sn2),搜索子串函数
? StrSub ( sn,num),求子串函数
? StrReplace ( s1,s2,mode,sn,num),子串替换函数
§ 3.3.1 串的逻辑结构
82
? (三 )串的基本操作
? StrInsert ( s1,sn),插入函数
? StrDelete ( sn,num),删除函数
? StrDelete ( sel),删除函数
? StrTrimL( ),删除 s中打头空格, 返回 s
? StrTrimR ( ),删除 s中尾随空格, 返回 s
? StrTrimLR ( ),删除 s中打头和尾随空格, 返回 s
? StrTrimAll ( ),删除 s中所有空格, 返回 s
? ToUpper ( ),转化为大写
? ToLower ( ),转化为小写
? ToInteger ( ),转化为整数
§ 3.3.1 串的逻辑结构
83
? (一 )连续存贮结构
? 类似于线性表的顺序结构
? 串值存贮在一块连续的存贮区中, 这块连续的存贮区
一般为动态区
? 每个串设立一个描述结点, 记录串值存贮区首址与串
长度
§ 3.3.2 串的存贮结构
84
? (二 )链式存贮结构
? 两种具体方案：
? 非压缩形式, 一个链表结点只存贮一个字符
? 压缩形式, 一个链结点存贮多个字符
§ 3.3.2 串的存贮结构
85
? (三 )串的基本操作实现
? 类定义
class TStr
{
unsigned char *room;
longsize; //串空间尺寸
longlen; //串当前长
public:
TStr (mSize=30);
TStr (TStr& s);
… …
}
§ 3.3.2 串的存贮结构
86
? (三 )串的基本操作实现
? 串模式匹配
? 给定两个串 T与 P：
T = "t0t1… tn-1"
P = "p0p1… pm-1"
? 其中 0＜ m≤n （ 通常 m<=n）
? 将在 T中寻找最先出现的一个与 P相同的子串的过程称
为 串模式匹配
? 称 T为 目标串, P称为 模式串
§ 3.3.2 串的存贮结构
87
? (三 )串的基本操作实现
? 1,简单串模式匹配算法
首先, 将模式串 P视为从目标串 T中第 1个字符起与 T对
齐, 从头起依次比较对应字符, 若全部对应相等, 则表
明已找到匹配, 终止, 否则, 将 P视为从 T中第 2个字符起
与 T对齐, 再从头比较对应字符, 过程与前类似, 如此进
行, 直至某次找到了匹配 （ 成功 ）, 或某次 T中无足够的
剩余字符与 P对齐 （ 不能匹配, 失败 ） 。
§ 3.3.2 串的存贮结构
88
? (三 )串的基本操作实现
? 1,简单串模式匹配算法 (续 )
实现时, 设三个指示器 i,j,ii,它们的含意是：
i──指向目标串 T中当前参加比较的字符 。 起始时, 指向 T的首字
符, 此后, 每比较一次, 后移一步, 一趟匹配失败时, 回溯到该趟
比较起点的下一位置 。
j──指向模式 T中当前参加比较的字符 。 起始时, 指向 T的首字符,
每比较一次, 后移一步, 一趟匹配失败时, 回溯到 T的首字符处 。
ii── 记录每趟比较的在目标串 T中的起点, 每趟比较后, 后移
一步 。
§ 3.3.2 串的存贮结构
89
? (三 )串的基本操作实现
? 1,简单串模式匹配算法 (续 )
longTStr::StrStr (TStr& s)
{
long i,j,ii;
i = j = ii = 0;
if (len < s.len) return -1;
§ 3.3.2 串的存贮结构
90
? (三 )串的基本操作实现
? 1,简单串模式匹配算法 (续 )
do
{
if (room[i] == s.room[j] )
{ i++; j++; }
else
{
ii++;
i = ii;
j=0;
if (len – ii < s.len) return -1;
}
} while (j<s.len);
return ii;
}
§ 3.3.2 串的存贮结构
时间复杂度 O(m·n )
91
? (三 )串的基本操作实现
? 2,无回溯的匹配算法 (KMP算法 )
? 在匹配过程中, 一旦发现 pj与 ti不等, 应能确定出从 p中的
那个字符起与 ti（ 或 ti+1） 对齐继续往下比较, 我们记这个
字符为 pk,显然 k<j,且对不同的 i,k也不同 。
? 这个 k值仅仅依赖于模式串 P的前 i个字符的构成, 而与目标
串 T无关
? 用一个函数 next表示 j与的这种对应关系, 它的含意是, 当
在匹配过程中一旦发现一对不等的字符 （ 设为 pj与 ti）,
则若 next(j)=k(k≥ 0),则下次的比较应从 p中的 pk起与 T中
的 ti对齐往下进行；若 next(j)<0,则 p中任何字符不必再
与 ti比较, 下次比较从 p的首字符起与 ti+1对齐往下进行 。
? next(j)的取值, 应首先保证使匹配过程无遗漏 （ 即不放过
任何可能的匹配 ）, 其次应使 p串向后滑动尽可能大的距离
（ 即 next(j)之值应尽可能小 ） 。
§ 3.3.2 串的存贮结构
92
? (三 )串的基本操作实现
? KMP算法的基本部分
int StrStr(TStr T,TStr P)
{
int i,j;
int *next;
if (P.len > T.len) return -1;
next = BuildNext(p); //为 P串构造失败函数对应的数组 next;
i = j =0; //假定串中首字符的下标为 0
§ 3.3.2 串的存贮结构
93
? (三 )串的基本操作实现
? KMP算法的基本部分
do
{
if (T.room[i] == P.room[j]
{ i++; j++; }
else
{
if (next[j] > 0) j = next[j]-1;
else {j = 0; i++; }
if (T.len – i < p.len – j ) return -1;
} while (j < P.len);
return i-P.len;
}
§ 3.3.2 串的存贮结构
2
§ 3.1 栈
? (一 )基本概念
? 栈 是一种限定仅在表的一端进行插入与删除的线性表
? 允许进行插入与删除的这一端称为 栈顶,而另一端称为 栈底
? 不含元素的空表称为 空栈
? 插入与删除分别称 进栈 与 出栈 。
? 栈也称作 先进后出 （ First In Last Out）的线性表，简称 FILO表
§ 3.1.1 栈的逻辑结构
a1 a2 a3 a4 … an
栈
底
栈
顶
进栈
出栈
图 -栈示意图
3
? (一 )基本概念
? 栈应用的例子
– 火车扳道站
– 进入单车道死胡同的汽车
– 记录中断返回地址（断点）的结构
§ 3.1.1 栈的逻辑结构
4
§ 3.1.1 栈的逻辑结构
? (一 )基本概念
? 可能的出栈次序
? 设 n=3，按 1,2,3的次序进栈，则可能的出栈
次序为
1 2 3,1 3 2,2 1 3,2 3 1,3 2 1
不可能的次序是：
3 1 2
? 对任意元素 k，若它后面有小于它的元素，则
这些小于它的元素必须以, 逆序, 出现
5
§ 3.1.1 栈的逻辑结构
? (二 ) 基本操作
? Init(s)：初始化栈 s。 设定一个空栈, 栈的所有其它操作仅在此
操作执行 （ 或隐含执行 ） 之后才能进行 。
? Empty(s)：判定函数 。 若栈 s为空, 返回, 真,, 否则返回
,假, 。
? Push(s,x)：入栈函数 。 将元素 x放到栈顶上, 栈溢出时应返回特
殊标志 。
? Pop(S)：出栈函数 。 栈 s不空时, 将栈顶元素摘除, 并返回该元
素 。 否则触发异常 。
? GetTop(s)：读栈顶元素函数 。 与 Pop(s)类似, 但不摘取栈顶元
素 。
? Clear(s)：清除操作 。 使栈 s重新变为一个空栈 。 这里, s是个已
存在的栈 。
? Len(s)：求长度函数 。 返回栈 s中元素个数 。
6
§ 3.1.1 栈的逻辑结构
? (三 ) 基本操作使用示例
? 编写一个带编辑功能的从终端上接收字符的程序
? 若依次输入：
Cg#HIna##NA
则相当于输入 CHINA
? 若依次输入
chi@CHINA
? 则相当于输入 CHINA
“#”代表退格 ；
,@”表示作废
7
… …
Init(s);
ch = getch(); //读入一个字符
while (ch!=EOF) //当未读入结束符时, 一直循环
{
switch(ch)
{
case '#',
Pop(s); break;
case '@',
Clear(s); break;
default:
Push(s,ch);
}
ch = getch();
}
8
§ 3.1.1 栈的逻辑结构
? (四 )栈抽象类
template <class TElem>
class TStack0
{
protected:
long len;
public:
long GetLen (void) {return len; };
char IsEmpty ( ) {return (len<=0)? 1:0; };
virtual TElem& Push (TElem &elem) =0;
virtual TElem& Pop (void) =0;
virtual TElem& GetTop (void) =0;
9
§ 3.1.1 栈的逻辑结构
? (四 )栈抽象类
virtual TElem& RollDown ( ) =0;
virtual TElem& RollUp ( ) =0;
virtual void Clear ( ) =0;
}
10
§ 3.1.2 栈的顺序存贮结构
? (一 ) 存贮方法
? 栈是一种特殊的线性表, 本节先介绍顺序存贮方式
? 用一维数组模拟连续的存贮空间
? 用一个量指示插入 /删除端的位置，一般称该量为 栈顶
指针
a1 a2 a3 a4 … … an元素空间：
栈顶指示器：
图 - 栈顺序存储结构
假设栈底在地址小的一端
11
§ 3.1.2 栈的顺序存贮结构
? (二 ) 顺序栈类
template <class TElem>
class TStackSqu, public TStack0<TElem>
{
protected:
TElem *room;
TElem elemBuff;
long size;
long CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2);
long ResizeRoom (long newSize);
12
§ 3.1.2 栈的顺序存贮结构
? (二 ) 顺序栈类
public:
TStackSqu ();
TStackSqu (long mSize);
~TStackSqu ();
virtual TElem& Push (TElem &elem);
virtual TElem& Pop (void);
virtual TElem& GetTop (void);
virtual TElem& RollDown ( );
virtual TElem& RollUp ( );
virtual void Clear ( );
virtual void Print ( );
}
13
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TStackSqu<TElem>::TStackSqu ( )
{
room=NULL;
size=0;
len=0;
}
14
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TStackSqu<TElem>::TStackSqu (long mSize)
{
len=0;
room=new TElem[mSize];
if (room==NULL) throw TExcepComm(4);
size=mSize;
}
15
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TStackSqu<TElem>::~TStackSqu ( )
{
if (room!=NULL) delete[] room;
}
16
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::Push (TElem &elem)
{
if (len>=size-1)
{
long ret=ResizeRoom(size+10);
if (ret<0) throw TExcepComm(3);
}
room[len]=elem;
len++;
return room[len-1];
}
17
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::Pop (void)
{
if (len<=0) throw TExcepComm(3);
len--;
return room[len];
}
18
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::GetTop (void)
{
return room[len-1];
}
template <class TElem>
void TStackSqu<TElem>::Clear ( )
{
len=0;
}
19
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::RollUp ( )
{
unsigned x;
x=room[0];
for (long i=1; i<len; i++)
room[i-1]=room[i];
room[len-1]=x;
return room[len-1];
}
20
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
TElem& TStackSqu<TElem>::RollDown ( )
{
unsigned x;
x=room[len-1];
for (int i=len-2; i>=0; i--)
room[i+1]=room[i];
room[0]=x;
return room[len-1];
}
21
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
longTStackSqu< TElem>::
CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2)
{
long i,k;
k=n2;
if (k>n1) k=n1;
for (i=0; i<k; i++)
objRoom[i] = srcRoom[i];
return k;
}
22
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
longTStackSqu< TElem>::ResizeRoom (long newSize)
{
long i,k;
TElem *pE;
pE= new TElem[newSize];
if (pE==NULL) throw TExcepComm(2);
len = CopyRoom (pE,newSize,room,len);
if (room!=NULL) delete room;
room = pE;
size=newSize;
return len;
}
23
§ 3.1.2 栈的顺序存贮结构
? (三 ) 基本操作的实现
template <class TElem>
void TStackSqu<TElem>::Print ( )
{
cout << '\n';
for (long i=0; i<len; i++)
cout<<' '<<room[i] ;
}
24
§ 3.1.3 栈的链式存贮结构
? (一 ) 存储方法
? 栈采用链式存贮结构主要目的是避免存贮区的
预申请问题
图 - 链式栈基本形式
an-1 a1 ^top
len
an
栈头
TStackLink
链结点, 栈顶
TLinkNode
25
§ 3.1.3 栈的链式存贮结构
? (二 ) 面向对象描述
? 栈采用链式存贮结构主要目的是避免存贮区的
预申请问题
template <class TElem>
struct TLinkNode
{
TElem info;
TLinkNode *next; //Note,not necessay for
<TElem> to follow TLinkNode here
};
26
§ 3.1.3 栈的链式存贮结构
? (二 ) 面向对象描述
类 TStackLink定义如下：
template <class TElem>
class TStackLink, public TStack0<TElem>
{
protected:
TLinkNode<TElem> *top;
TElem elemBuff;
public:
TStackLink();
~TStackLink();
virtual TElem& Push (TElem &elem);
virtual TElem& Pop (void);
virtual TElem& GetTop (void);
27
§ 3.1.3 栈的链式存贮结构
? (二 ) 面向对象描述
virtual TElem& RollDown ( );
virtual TElem& RollUp ( );
virtual void Clear ( );
//New functions
virtual TLinkNode<TElem>* PushNode (TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem>* PopNode (void);
virtual const TLinkNode<TElem>* GetTopNode (void);
virtual void Print ( );
}
28
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
1,初始化
template <class TElem>
TStackLink<TElem>::TStackLink ( )
{
top = NULL;
len=0;
}
template <class TElem>
TStackLink<TElem>::~TStackLink ( )
{
Clear ( );
}
29
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
2,进栈 Push(TElem&elem)
template <class TElem>
TElem& TStackLink<TElem>::Push (TElem &elem)
{
TLinkNode<TElem> *pNode;
pNode = new TLinkNode<TElem>;
if (pNode==NULL) throw TExcepComm(4);
pNode->info = elem ; //TElem must support "="
PushNode(pNode);
return pNode->info;
}
30
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
3,出栈 Pop()
template <class TElem>
TElem& TStackLink<TElem>::Pop (void)
{
TLinkNode<TElem> *pNode;
pNode = PopNode();
elemBuff =pNode->info; //TElem must support "="
delete pNode;
return elemBuff;
}
31
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
4,读栈 GetTop()
template <class TElem>
TElem& TStackLink<TElem>::GetTop (void)
{
return top->info;
}
32
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
5,结点进栈 PushNode(TLinkNode<TElem> *pNode)
template <class TElem>
TLinkNode<TElem>*
TStackLink<TElem>::PushNode(TLinkNode<TElem> *pNode)
{
pNode->next = top;
top = pNode;
len++;
return pNode;
}
33
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
6,结点出栈 PopNode(void) template <class TElem>
template <class TElem>
TLinkNode<TElem> *TStackLink<TElem>::PopNode (void)
{
TLinkNode<TElem> *pNode;
if (top==NULL) throw TExcepComm(5);
elemBuff = top->info; //TElemmust support "="
pNode = top;
top = top->next;
len--;
return pNode;
}
34
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
7,读栈顶结点 GetTopNode(void) template <class TElem>
template <class TElem>
const TLinkNode<TElem>* TStackLink<TElem>::GetTopNode (void)
{
return top;
}
35
§ 3.1.3 栈的链式存贮结构
? (三 ) 基本操作实现
template <class TElem>
void TStackLink<TElem>::Clear ( )
{
TLinkNode<TElem> *p,*q;
p=top;
while (p!=NULL)
{
q=p;
p=p->next;
delete q;
}
top = NULL;
len=0;
}
36
§ 3.2 队列
? (一 ) 基本概念
? 队列 (Queue)是一种限定仅分别在表的两端进行插入与删
除的线性表 。
? 允许插入的一端称 队尾, 允许删除的一端称 队头 。
? 插入与删除分别称为 入队 与 出队 。
§ 3.2.1 队列的逻辑结构
出队 ← ○ ○ ○ …… ← ○ ○ 进队
队尾队头
图 -队列示意图
37
? (一 ) 基本概念
? 队是一种先进先出 FIFO（ First In First Out）的结构，
元素出队的次序与进队次序相同。
? 应用
? 顾客服务部门的工作方式往往是排队方式
§ 3.2.1 队列的逻辑结构
38
? (二 ) 基本操作
? Init(Q),初始化操作, 设置一个空队列 。
? Empty(Q),判空函数, 若 Q为空, 则返回, 真,, 否则返回, 假, 。
? Enter(Q,x),入队函数, 将元素 x加到队 Q中 。
? Exit(Q),出队操作, 将队头元素摘除并返回之 。
? GetHead(Q),访问队头元素 （ 返回队头元素 ）, 但不摘除 。
? Clear(Q),将队列 Q清空 。
? Len(Q),返回队 Q中元素个数 。
§ 3.2.1 队列的逻辑结构
39
? (一 )非循环队列
? 1,存储方法
? 连续存贮结构, 用一维数组作队元素存贮空间
? 另设两个指示器, 分别指示队头与队尾 （ 分别称对头与队尾指针 ）
§ 3.2.2 队列的连续存贮结构
a1 a2 a3 …… an
图 - 连结存贮结构的队列
room:
front rear 初始状态：front=rear=0
40
? (一 )非循环队列
? 2,进队
? 进队是将元素添加到队尾, 故需访问队尾指针 rear,将元
素 x进队 Q的操作为：
if (队满 ) 触发异常；
Q->rear++;
Q->room[rear] = x;
§ 3.2.2 队列的连续存贮结构
41
? (一 )非循环队列
? 3,出队
? 出队是将当前队中头元素摘取并返回其：
if (队空 ) 触发异常；
Q->front++;
return Q->room[Q->front];
§ 3.2.2 队列的连续存贮结构
42
? (一 )非循环队列
? 4,队空 /满问题
? 队列变空时有下列关系成立
Q->front = = Q->rear
? 显然初始状态也满足此式
? rear超过 room的空间大小,这种情况我们称为, 队满,
?, 假满, 问题的解决方法
a)发生假满时, 移动队中元素, 在尾部让出空位 。 但这种方法
效率差,
b)循环队列法 。
§ 3.2.2 队列的连续存贮结构
43
? (二 )循环队列
? 1,基本思想
? 循环队列, 就是指将队列的存贮区域视作循环结构
? 假定：
队头指示器 front：指向队中第 1个元素的前一个位置 。
队尾指示器 rear：指向队尾元素所在位置 。
? 队空与队满的条件分别为：
队空,rear = = front
队满,(rear+1) MOD N = = front
§ 3.2.2 队列的连续存贮结构
44
? (二 )循环队列
? 2,实现
? 首先定义一个抽象类 TQueue0,该类将是各种存储结构的队列的基
础, 规定了通用操作接口 。
template <class TElem>
class TQueue0
{
protected:
longlen;
§ 3.2.2 队列的连续存贮结构
45
? (二 )循环队列
public:
long GetLen (void) {return len; };
char IsEmpty ( ) {return (len<=0)? 1:0; };
virtual TElem& Qpush (TElem &elem) = 0;
virtual TElem& Qpop (void) = 0;
virtual TElem& GetHead (void) = 0;
virtual TElem& RollDown ( ) = 0;
virtual TElem& RollUp ( ) = 0;
virtual void Clear ( ) = 0;
}
§ 3.2.2 队列的连续存贮结构
46
? (二 )循环队列
? 顺序队的具体的存储用类 TQueueSqu描述
template <class TElem>
class TQueueSqu, public TQueue0<TElem>
{
protected:
TElem *room;
TElem elemBuff;
long front,rear,size;
long CopyRoom (TElem *objRoom,long n1,TElem *srcRoom,long n2);
long ResizeRoom (long newSize);
§ 3.2.2 队列的连续存贮结构
47
public:
TQueueSqu ( );
TQueueSqu (long mSize);
~TQueueSqu ( );
virtual TElem& Qpush (TElem &elem);
virtual TElem& Qpop (void);
virtual TElem& GetHead (void);
virtual TElem& RollDown ( );
virtual TElem& RollUp ( );
virtual void Clear ( );
virtual void Print ( );
}
48
? 各主要操作的实现
template <class TElem>
TQueueSqu<TElem>::TQueueSqu ( )
{
room=NULL;
front=0;
rear=0;
size=0;
len=0;
}
49
template <class TElem>
TQueueSqu<TElem>::TQueueSqu (long mSize)
{
len=0;
front=0;
rear=0;
room = new TElem[mSize];
if (room==NULL) throw TExcepComm(4);
size=mSize;
}
50
template <class TElem>
TQueueSqu<TElem>::~TQueueSqu()
{
if (room!=NULL) delete[] room;
}
51
template <class TElem>
TElem& TQueueSqu<TElem>::Qpush (TElem &elem)
{
if (len>=size-1)
{
long ret = ResizeRoom (size +10);
if (ret<0) throw TExcepComm(3);
}
rear++;
if (rear>=size) rear=0;
room[rear]=elem; //TElem must support "="
len++;
return room[rear];
}
52
template <class TElem>
TElem& TQueueSqu<TElem>::Qpop (void)
{
if (len<=0) throw TExcepComm(3);
len--;
front++;
if (front>=size) front=0;
return room[front];
}
53
template <class TElem>
TElem& TQueueSqu<TElem>::GetHead (void)
{
return room [(front+1) % size];
}
template <class TElem>
void TQueueSqu<TElem>::Clear ( )
{
len = 0;
front = rear = 0;
}
54
template <class TElem>
TElem& TQueueSqu<TElem>::RollUp ( )
{ //TElem must support "="
TElem x;
long k,j;
k =front + 1;
if (k>=size) k=0;
x = room[k];
while (k!=rear)
{
j = k;
k++;
if (k>=size) k=0;
room[j] = room[k];
}
room[rear] = x;
return room[(front+1)%size];
}
55
template <class TElem>
TElem& TQueueSqu<TElem>::RollDown ( )
{ //TElem must support "="
TElem x;
long k,j,f0;
f0 = front+1;
if (f0>=size) f0=0;
k =rear ;
x = room[k];
56
while (k!=front)
{
j = k;
k--;
if (k<=0) k=size-1;
room[j] = room[k];
}
room[f0] = x;
return room[f0];
}
57
template <class TElem>
long TQueueSqu< TElem>::CopyRoom (TElem *objRoom,long n1,TElem
*srcRoom,long n2)
{
long i,k;
k=n2;
if (k>n1) k=n1;
for (i=0; i<k; i++)
objRoom[i] = srcRoom[i];
return k;
}
58
template <class TElem>
longTQueueSqu< TElem>::ResizeRoom (long newSize)
{
long i,k;
TElem *pE;
pE= new TElem[newSize];
if (pE==NULL) throw TExcepComm(2);
len = CopyRoom (pE,newSize,room,len);
if (room!=NULL) delete room;
room = pE;
size=newSize;
return len;
}
59
template <class TElem>
void TQueueSqu<TElem>::Print ( )
{
int i;
cout<<'\n';
if (rear == front) return;
i=front+1;
if (i>=size) i = 0;
while (i!=rear)
{
cout<<' '<<room[i];
i++;
if (i>=size) i=0;
}
cout<<' '<<room[i];
}
60
? (一 )存储方法
? 链式队列的元素采用线性链表存储
? 该链表的描述结点应至少含两个指针：队头元素指针与队尾
元素指针，分别令其指向队中首元素与尾元素对应的结点
§ 3.2.3 队列的链式存贮结构
a2 an ^front
rear
len
a1
图 - 链式队列基本形式
队结点
TStackLink
链结点, 队头
TLinkNode 队尾结点
61
? (二 )面向对象描述
? 设立一个类 TQueueLink，其从 TQueue0派生而来
template <class TElem>
struct TLinkNode
{
TElem info;
TLinkNode *next; //Note,not necessay for <TElem> to follow
TLinkNode here
}
§ 3.2.3 队列的链式存贮结构
62
? (二 )面向对象描述
? 设立一个类 TQueueLink，其从 TQueue0派生而来
template <class TElem>
class TQueueLink, public TQueue0<TElem>
{
protected:
TLinkNode<TElem> *front,*rear;
TElem elemBuff;
public:
TQueueLink ( );
~TQueueLink ( );
§ 3.2.3 队列的链式存贮结构
63
? (二 )面向对象描述
virtual TElem& QPush(TElem &elem);
virtual TElem& QPop(void);
virtual TElem& GetHead(void);
virtual TElem& RollDown();
virtual TElem& RollUp();
virtual void Clear();
§ 3.2.3 队列的链式存贮结构
64
? (二 )面向对象描述
//New functions
virtual TLinkNode<TElem>*
QPushNode (TLinkNode<TElem> *pNode);
virtual TLinkNode<TElem>* QPopNode (void);
virtual const TLinkNode<TElem>*
GetHeadNode(void);
virtual void Print ();
}
§ 3.2.3 队列的链式存贮结构
65
? (三 )基本操作实现
template <class TElem>
TQueueLink<TElem>::TQueueLink ( )
{
front = NULL;
rear = NULL;
len = 0;
}
§ 3.2.3 队列的链式存贮结构
66
? (三 )基本操作实现
template <class TElem>
TQueueLink<TElem>::~TQueueLink ( )
{
Clear ( );
}
§ 3.2.3 队列的链式存贮结构
67
? (三 )基本操作实现
template <class TElem>
TElem& TQueueLink<TElem>::Qpush (TElem &elem)
{
TLinkNode<TElem> *pNode;
pNode = new TLinkNode<TElem>;
if (pNode == NULL) throw TExcepComm(4);
pNode->info = elem ; //TElem must support "="
QPushNode(pNode);
return pNode->info;
}
§ 3.2.3 队列的链式存贮结构
68
? (三 )基本操作实现
template <class TElem>
TElem& TQueueLink<TElem>::Qpop (void)
{
TLinkNode<TElem> *pNode;
pNode = QPopNode();
elemBuff =pNode->info; //TElem must support "="
delete pNode;
return elemBuff;
}
§ 3.2.3 队列的链式存贮结构
69
? (三 )基本操作实现
template <class TElem>
TElem& TQueueLink<TElem>::GetHead (void)
{
if (front==NULL) throw TExcepComm(2);
return front->info;
}
§ 3.2.3 队列的链式存贮结构
70
? (三 )基本操作实现
template <class TElem>
TLinkNode<TElem>* TQueueLink<TElem>::
QPushNode (TLinkNode<TElem> *pNode)
{
pNode->next = NULL;
if (rear!=NULL) rear->next = pNode;
else front = pNode;
rear = pNode;
len++;
return pNode;
}
§ 3.2.3 队列的链式存贮结构
71
? (三 )基本操作实现
template <class TElem>
TLinkNode<TElem> *TQueueLink<TElem>::QPopNode (void)
{
TLinkNode<TElem> *pNode;
if (front==NULL) throw TExcepComm(5);
elemBuff = front->info; //TElem must support "="
pNode = front;
front = front->next;
if (front==NULL) rear=NULL;
len--;
return pNode;
}
§ 3.2.3 队列的链式存贮结构
72
? (三 )基本操作实现
template <class TElem>
const TLinkNode<TElem>* TQueueLink<TElem>:,GetHeadNode (void)
{
return front;
}
§ 3.2.3 队列的链式存贮结构
73
? (三 )基本操作实现
template <class TElem>
void TQueueLink<TElem>::Clear ( )
{
TLinkNode<TElem> *p,*q;
p=front;
while (p!=NULL)
{
q=p;
p=p->next;
delete q;
}
front = NULL;
rear = NULL;
len=0;
}
§ 3.2.3 队列的链式存贮结构
74
? 文字（符号）序列称为 字符串,简称 串
? 人名、产品名、事物名称、车牌号、文献、
源程序
? 串被认为是一种特殊线性表 ── 元素为文字符号的线
性表
§ 3.3 串
75
? (一 ) 基本概念
? 串 是由零个或多个字符构成的有限序列, 一般记为
s = "a1a2… an" (n≥ 0)
? s代表 串的名称
? 用双引号括起来的部分（不含该双引号本身）为 串值
（即字符序列）
? 串值中字符个数（即 n）称为 串长
? 长度为 0的串称为 空串
§ 3.3.1 串的逻辑结构
76
? (一 ) 基本概念
? 串中任意个连续字符构成的部分称为该串的 子串
? 包含子串的串相对该子串称为 主串
? 串中某字符在串中出现的序号为该字符在串中的 字符
位置
? 子串中第 1个字符在串中的序号称为该子串在该串中
的 位置
§ 3.3.1 串的逻辑结构
77
? (一 ) 基本概念
? 串的例子
s1="ab123" /*长度为 5的串 */
s2="100" /*长度为 3的串 */
s3=" " /*含两个空格字符的串, 长度为 2*/
s4="" /*空串, 长度为 0*/
? 长度为 n的串中子串总数 （ 包括空串与自身 ） 为
1+ = 1+
§ 3.3.1 串的逻辑结构
?
?
??n
i
in
1
)1(
2
)1( ?nn
78
? (二 )串的比较运算的定义
? 如何定义单个字符间的大小关系？
? 字符间的大小关系就定义为它们的代码之间的大小关
系, 如 ASCII码
? 例如, 字符 A与 B的 ASCII码分别为 65与 66（ 十进制 ）,
则说 'A'<'B'
? 汉字的编码也有几种, 如大陆用的国标码 (GB2312)，
台湾地区用的 Big5等
§ 3.3.1 串的逻辑结构
79
? (二 )串的比较运算的定义
? 下面考虑串之间的大小关系 。 设 X与 Y是两个串：
X="x1x2… xm"
Y="y1y2… yn"
? 则它们之间的大小关系定义如下：
① 当 m=n且 x1=y1,…,xm=yn,则称 X=Y.
② 当下列条件之一成立时, 称 X<Y.
i) m<n,且 xi=yi,i=1,2,…,m
ii)存在某一个 k<=MIN(m,n),使得 xi=yi,i=1,2,…, k-1,xk<yk.
③ 不属于情况①与②时，称 X>Y,
§ 3.3.1 串的逻辑结构
也称字典序
80
? (二 )串的比较运算的定义
? 几个例子
"abac"与 "abac"：相等 (=)
"we"与 "web"：前者小于后者 (情况 i)
"mouth"与 "move"：前者小于后者 （ 情况 ii）
§ 3.3.1 串的逻辑结构
81
? (三 )串的基本操作
? StrChar ( long idx),返回 s中序号为 idx的字符
? StrCopy ( maxNum),将 s的值复制一份
? StrCompare ( s1,mode),串比较函数,比较 s与 s1之间的大小关系
? StrLen ( ),长度函数
? StrConcat ( s1,maxNum),连接函数
? StrCharAt ( ch,mode,sn),字符位置函数
? StrStr ( s1,mode,sn),子串位置函数
? StrSearch ( s1,mode,sn1,sn2),搜索子串函数
? StrSub ( sn,num),求子串函数
? StrReplace ( s1,s2,mode,sn,num),子串替换函数
§ 3.3.1 串的逻辑结构
82
? (三 )串的基本操作
? StrInsert ( s1,sn),插入函数
? StrDelete ( sn,num),删除函数
? StrDelete ( sel),删除函数
? StrTrimL( ),删除 s中打头空格, 返回 s
? StrTrimR ( ),删除 s中尾随空格, 返回 s
? StrTrimLR ( ),删除 s中打头和尾随空格, 返回 s
? StrTrimAll ( ),删除 s中所有空格, 返回 s
? ToUpper ( ),转化为大写
? ToLower ( ),转化为小写
? ToInteger ( ),转化为整数
§ 3.3.1 串的逻辑结构
83
? (一 )连续存贮结构
? 类似于线性表的顺序结构
? 串值存贮在一块连续的存贮区中, 这块连续的存贮区
一般为动态区
? 每个串设立一个描述结点, 记录串值存贮区首址与串
长度
§ 3.3.2 串的存贮结构
84
? (二 )链式存贮结构
? 两种具体方案：
? 非压缩形式, 一个链表结点只存贮一个字符
? 压缩形式, 一个链结点存贮多个字符
§ 3.3.2 串的存贮结构
85
? (三 )串的基本操作实现
? 类定义
class TStr
{
unsigned char *room;
longsize; //串空间尺寸
longlen; //串当前长
public:
TStr (mSize=30);
TStr (TStr& s);
… …
}
§ 3.3.2 串的存贮结构
86
? (三 )串的基本操作实现
? 串模式匹配
? 给定两个串 T与 P：
T = "t0t1… tn-1"
P = "p0p1… pm-1"
? 其中 0＜ m≤n （ 通常 m<=n）
? 将在 T中寻找最先出现的一个与 P相同的子串的过程称
为 串模式匹配
? 称 T为 目标串, P称为 模式串
§ 3.3.2 串的存贮结构
87
? (三 )串的基本操作实现
? 1,简单串模式匹配算法
首先, 将模式串 P视为从目标串 T中第 1个字符起与 T对
齐, 从头起依次比较对应字符, 若全部对应相等, 则表
明已找到匹配, 终止, 否则, 将 P视为从 T中第 2个字符起
与 T对齐, 再从头比较对应字符, 过程与前类似, 如此进
行, 直至某次找到了匹配 （ 成功 ）, 或某次 T中无足够的
剩余字符与 P对齐 （ 不能匹配, 失败 ） 。
§ 3.3.2 串的存贮结构
88
? (三 )串的基本操作实现
? 1,简单串模式匹配算法 (续 )
实现时, 设三个指示器 i,j,ii,它们的含意是：
i──指向目标串 T中当前参加比较的字符 。 起始时, 指向 T的首字
符, 此后, 每比较一次, 后移一步, 一趟匹配失败时, 回溯到该趟
比较起点的下一位置 。
j──指向模式 T中当前参加比较的字符 。 起始时, 指向 T的首字符,
每比较一次, 后移一步, 一趟匹配失败时, 回溯到 T的首字符处 。
ii── 记录每趟比较的在目标串 T中的起点, 每趟比较后, 后移
一步 。
§ 3.3.2 串的存贮结构
89
? (三 )串的基本操作实现
? 1,简单串模式匹配算法 (续 )
longTStr::StrStr (TStr& s)
{
long i,j,ii;
i = j = ii = 0;
if (len < s.len) return -1;
§ 3.3.2 串的存贮结构
90
? (三 )串的基本操作实现
? 1,简单串模式匹配算法 (续 )
do
{
if (room[i] == s.room[j] )
{ i++; j++; }
else
{
ii++;
i = ii;
j=0;
if (len – ii < s.len) return -1;
}
} while (j<s.len);
return ii;
}
§ 3.3.2 串的存贮结构
时间复杂度 O(m·n )
91
? (三 )串的基本操作实现
? 2,无回溯的匹配算法 (KMP算法 )
? 在匹配过程中, 一旦发现 pj与 ti不等, 应能确定出从 p中的
那个字符起与 ti（ 或 ti+1） 对齐继续往下比较, 我们记这个
字符为 pk,显然 k<j,且对不同的 i,k也不同 。
? 这个 k值仅仅依赖于模式串 P的前 i个字符的构成, 而与目标
串 T无关
? 用一个函数 next表示 j与的这种对应关系, 它的含意是, 当
在匹配过程中一旦发现一对不等的字符 （ 设为 pj与 ti）,
则若 next(j)=k(k≥ 0),则下次的比较应从 p中的 pk起与 T中
的 ti对齐往下进行；若 next(j)<0,则 p中任何字符不必再
与 ti比较, 下次比较从 p的首字符起与 ti+1对齐往下进行 。
? next(j)的取值, 应首先保证使匹配过程无遗漏 （ 即不放过
任何可能的匹配 ）, 其次应使 p串向后滑动尽可能大的距离
（ 即 next(j)之值应尽可能小 ） 。
§ 3.3.2 串的存贮结构
92
? (三 )串的基本操作实现
? KMP算法的基本部分
int StrStr(TStr T,TStr P)
{
int i,j;
int *next;
if (P.len > T.len) return -1;
next = BuildNext(p); //为 P串构造失败函数对应的数组 next;
i = j =0; //假定串中首字符的下标为 0
§ 3.3.2 串的存贮结构
93
? (三 )串的基本操作实现
? KMP算法的基本部分
do
{
if (T.room[i] == P.room[j]
{ i++; j++; }
else
{
if (next[j] > 0) j = next[j]-1;
else {j = 0; i++; }
if (T.len – i < p.len – j ) return -1;
} while (j < P.len);
return i-P.len;
}
§ 3.3.2 串的存贮结构
