第三章：栈和队列
3.1：栈和队列的定义和特点
3.1.1：栈的定义和特点
3.1.2：队列的定义和特点
3.2：案例引入
3.3：栈的表示和操作的实现
3.3.1：栈的类型定义
3.3.2：顺序栈的表示与实现
3.3.2.1：顺序栈的初始化
//算法3.1：顺序栈的初始化
Status InitStack(Sqstack &S)
{//构造一个空栈S
S.base=new SELemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base; //top初始化为base，空栈
S.stacksize=MAXSIZE; //stacksize置为栈的最大容量 MAXSIZE
return OK;
}
3.3.2.2：顺序栈判断栈是否为空
//顺序栈判断栈是否为空
Status StackEmpty(SqStack S)
{//若栈为空，返回TRUE，否则返回FALSE
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
3.3.2.3：求顺序栈的长度
//求顺序栈的长度
int StackLength(SqStack S)
{
return S.top-S.base;
}
3.3.2.4：清空顺序栈
//清空顺序栈
Status ClearStack(SqStack S)
{
if(S.base) S.top=S.base;
return OK;
}
3.3.2.5：销毁顺序栈
//销毁顺序栈
Status DestroyStack(SqStack &S)
{
if(s.base)
{
delete S.base;
S.stacksize=0;
S.base=S.top=NULL;
}
return OK;
}
3.3.2.6：顺序栈的入栈
//算法3.2 顺序栈的入栈
Status Push(SqStack &S SElemType e)
{//插入元素e为新的栈顶元素
if(S.top-S.base==S.stacksize) return ERROR; //栈满
*S.top++=e; //将元素e压入栈顶，栈顶指针加1 （*S.top=e; S.top++;）
return OK;
}
3.3.2.7：顺序栈的出栈
//顺序栈的出栈
Status Pop(SqStack &S,SElemType &e)
{//删除S的栈顶元素，用e返回其值
if(S.top-S.base==S.stacksize) return ERROR; //栈空
e=*--S.top; //栈顶指针减1，将栈顶元素赋给e
return OK;
}
3.3.3：链栈的表示和实现
3.3.3.1：链栈的初始化
//算法3.5 链栈的初始化
Status InitStack(LinkStack &S)
{//构造一个空栈S，栈顶指针置空
S=NULL;
return OK;
}
3.3.3.2：链栈的入栈
//算法3.6 链栈的入栈
Status Push(LinkStack &S,SElemType e)
{//在栈顶插入元素e
p=new StackNode; //生成新结点
p->data=e; //将新结点数据置为e
p->next=S; //将新结点插入栈顶
S=p; //修改栈顶指针为p
return OK;
}
3.3.3.3：链栈的出栈
//算法3.7 链栈的出栈
Status Pop(LinkStack &S,SElemType &e)
{//删除S的栈顶元素，用e返回其值
if(S==NULL) return ERROR; //栈空
e=S->data; //将栈顶元素赋给e
p=S; //用p临时保存栈顶元素空间，以备释放
S=S->next; //修改栈顶元素
delete p; //释放原栈顶元素空间
return OK;
}
3.3.3.4：取栈顶元素
//算法3.8 取栈顶元素
SElemType GetTop(LinkStack S)
{//返回S的栈顶元素，不修改栈顶指针
if(S!=NULL) //栈非空
return S->data; //返回栈顶元素的值，栈顶指针不变
}
3.4：栈与递归
3.4.1：采用递归算法解决的问题
//算法3.9 遍历输出链表中各个结点的递归算法
void TraverseList(LinkList p)
{
if(p==NULL) return; //递归终止
else
{
count<<p->data<<endl; //输出当前结点的数据域
TraverseList(L->next); //p指向后继结点继续递归
}
}
//简化
void TraverseList(LinkList p)
{
if(p)
{
count<<p->data<<endl;
TraverseList(L->next);
}
}
//算法3.10 Hanoi塔问题得递归算法
void Hanoi(int n,char A,char B,char C)
{//将塔座A上的n个圆盘按规则搬到C上，B座辅助塔
if(n==1) move(A,1,c); //将编号为1的圆盘从A移动到C
else
{
Hanoi(n-1,A,C,B); //将A上编号为1至n-1的圆盘移动到B，C座辅助塔
move(A,n,C); //将编号为n的圆盘从A移动到C
Hanoi(n-1,B,A,c); //将B上编号为1至n-1的圆盘移动到C，A座辅助塔
}
}
3.4.2：递归过程和递归工作栈
3.4.3：递归算法的效率分析
3.4.4：利用栈将递归转换为非递归的方法
3.5：队列的表示和操作实现
3.5.1：队列的类型定义
3.5.2：循环队列------队列的顺序表示与实现
//队列的顺序存储结构
#define MAXQSIZE 100 //队列可能达到的最大长度
typedef struct
{
QElemType *base; //存储空间的基地址
int front; //头指针
int rear; //尾指针
}SqQueue;
3.5.2.1：队列的初始化
//算法3.1 循环队列的初始化
Status InitQueue(SqQueue &Q)
{//构造一个空队列
Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间
if(!Q.base) exit(OVERFLOW); //存储分配失败
Q.front=Q.rear=0; //头指针和尾指针置为0，队列为空
return OK;
}
3.5.2.2：求循环队列的长度
//算法3.12 求循环队列的长度
int QueueLength(SqQueue Q)
{//返回Q的元素个数，即队列的长度
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
3.5.2.3：循环队列的入队
//算法3.13 循环队列的入队
Status EnQueue(SqQueue &Q,QElemType e)
{//插入元素e为Q的新的队尾元素
if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加1后等于头指针，表明队满
return REEOR;
Q.base[Q.rear]=e; //新元素插入队尾
Q.rear=(Q.rear+1)%MASQSIZE; //队尾指针加1
return OK;
}
3.5.2.4：循环队列的出队
//算法3.14 循环队列的出队
Status DeQueue(SqQueue &Q,QElemType &e)
{//删除Q的队头元素，用e返回其值
if(Q.front==Q.rear) return ERROR; //队空
e=Q.base[Q.front]; //保存队头元素
Q.front=(Q.front+1)%MAXQSIZE; //队头指针加1
return OK;
}
3.5.2.5：取循环队列的队头元素
//算法3.15 取循环队列的队头元素
SElemType GetHead(SqQueue Q)
{//返回Q的队头元素
if(Q.front!Q.rear) //队列非空
return Q.base[Q.front]; //返回队头元素的值，队头指针不变
}
3.5.3：链队------队列的链式表示与实现
3.5.3.1：链队的类型定义
//队列的链式存储结构
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
3.5.3.2：链队的初始化
//算法 3.16 链队的初始化
Status InitQueue(LinkQueue &Q)
{//构造一个空队列Q
Q.front=Q.rear=new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点
Q.front->next=NULL; //头指针的指针域置空
return OK;
}
3.5.3.3：销毁链队列（补充）
//销毁链队列
Status DestroyQueue(LinkQueue &Q)
{
while(Q.front)
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
}
3.5.3.4：链队的入队
//算法3.17 链队的入队
Status EnQueue(LinkQueue &Q,QElemType e)
{//插入元素e为Q的新的队尾元素
p=new QNode; //为入队元素分配结点空间，用指针p指向
p->data=e; //将新结点数据域置为e
p->next=NULL;Q.rear->next=p; //将新结点插入到队尾
Q.rear=p; //修改队尾指针
return OK;
}
3.5.3.5：链队的出队
//算法3.18 链队的出队
Status DeQueue(LinkQueue &Q,QElemType &e)
{//删除Q的队头元素，用e返回其值
if(Q.front==Q.rear) return ERROR; //若队列空，则返回ERROE
p=Q.front->next; //p指向队头元素
e=p->data; //e保存队头元素的值
Q.front->next=p->next; //修改头指针的指针域
if(Q.rear==p) Q.rear=Q.front; //最后一个元素被删，队尾指针指向头指针
delete p; //释放原队头元素的空间
return OK;
}
3.5.3.6：取队头元素
//算法3.19 取链队的队头元素
SElemType GetHead(LinkQueue Q)
{//返回Q的队头元素，不修改队头指针
if(Q.front!=Q.rear) //队列非空
return Q.front->next->data; //返回队头元素的值，队头指针不变
}
第四章：串，数组和广义表
4.1：串的定义
4.2：案例引入
4.3：串的类型定义，存储结构及其运算
4.3.1：串的抽象类型定义
4.3.2：串的存储结构
//串的定长顺序存储结构
#define MAXSIZE 255 //串的最大长度
typedef struct
{
char ch[MAXLEN+1]; //存储串的以为数组
int length; //串的当前长度
}SString;
//串的堆式顺序存储结构
typedef struct
{
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串的当前长度
}HString;
//串的堆式顺序存储结构
typedef struct
{
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串的当前长度
}HString;
//串的链式存储结构 //可有用户定义的块的大小
#define CHUNKSIZE
typedef struct Chunk
{
char ch[CHUNKSIZE]:
struct Chunk *next;
}Chunk;
typedef struct
{
Chunk *head,*tail; //串的头和尾指针
int length; //串的当前长度
}LSting;
4.3.3：串的模式匹配算法
4.3.3.1：BF算法
//算法 4.1 BF算法
int Index BF(SString S,SString T,int pos)
{//返回模式T在主串S中第pos个字符开始第一次出现的位置，若不存在，则返回值为1
//其中，T非空，1<=pos<=S.length
i=pos; j=1; //初始化
while(i<S.length && j<=T.length) //两个串均未比较到串尾
{
if(S.ch[i]==T.ch[j]) //继续比较后继字符
{
++i;
++j;
}
else //指针后退重新开始匹配
{
i=i-j+2;
j=1;
}
}
if(j>T.length) return i-T.length; //匹配成功
else return 0; //匹配失败
}
4.3.3.2：KMP算法
//算法4.2 KMP算法
int Index_KMP(SString S,SString T,int pos)
{//利用模式串T的nex函数求T在主串S中的第pos个字符之后的位置
//其中，T非空，1<=pos<=S.length
i=pos;j=1;
while(i<=S.length && j<=T.length) //两个串均未比较到串尾
{
if(j==0||S.ch[i]==T) //继续比较后继字符
{
++i;
++j;
}
else //模式串向右移动
{
j=nex[j];
}
}
if(j>T.length) return i-T.length; //匹配成功
else return 0; //匹配失败
}
//算法4.3计算next函数值
void get_next(SString T,int next[])
{//求模式串T的next函数值并存入数组next
i=1;next[1]=0;j=0;
while(i<T.length)
{
if(j==0||T.ch[i]==T.ch[j])
{
++i;
++j;
next[i]=j;
}
else
{
j=next[j];
}
}
}
//算法4.4 计算next函数的修正值
void get_nextval(SString T,int nextval[j])
{//求模式串T的next函数修正值并存入数组nextval
i=1;nextval[1]=0;j=0;
while(i<T.length)
{
if(j==0||T.ch[i]==T.ch[j])
{
++i;++j;
if(T.ch[i]!=T.ch[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
4.4 ：数组
4.4.1：数组的类型定义
4.4.2：数组的顺序存储
4.4.3：特殊矩阵的压缩存储
4.4.3.1：对称矩阵
4.4.3.2：三角矩阵
4.4.3.3：对角矩阵
4.4.3.4：稀疏矩阵
4.4.3.4.1：顺序存储结构------三元顺序表
4.4.4.3.2：链式存储结构------十字链表
4.5：广义表
4.6：案例分析与实现
