栈，队列，数组

绪论

通常称，栈和队列是限定插入和删除只能在表的端点进行的线性表。

栈和队列是两种常用的数据结构。

栈的类型定义

ADT Stack {
	数据对象：
		D = {ai | ai属于ElemSet, i = 1,2,…,n}
	数据关系：
		R1 = {<ai-1, ai> | ai-1,ai属于D, i = 1,2,…,n}
		约定an端为栈顶，a1端为栈底
	基本操作：
		InitStack (&S)
		DestoryStack (&S)
		StackLength (S)
		StackEmpty (S)			//判断是否为空
		GetTop (S, &e)
		ClearStack (&S)
		Push (&S, e)
		Pop (&S, &e)
		StackTravers (&S, visit( ))
}

Push (&S, e)：
	初始条件：
		栈S已存在
	操作结果：
		插入元素e为新的栈顶元素
Pop (&S, &e)：
	初始条件：栈S已存在且非空
	操作结果：删除S的栈顶元素，并用e返回其值

栈的应用举例

这些问题的具体实现代码请见博客内其他文章

1.例一、数制转换

算法基于原理：N = (N div d) * d + N mod d;

例如：(1348)10 = (2504)8

具体伪代码：

void conversion () {
	InitStack(S);
	scanf(“%d”, &N);
	while(N) {
		Push(S, N % d);
		N = N / d;
	}
	while(!StackEmpty(S)) {
		Pop(S, e);
		printf(“%d”, e);
	}
}

2.括号匹配的检验

检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述

例如：考虑这个括号序列

[ ( [ ] [ ] ) ]

分析可能出现的不匹配情况：

*到来的右括号非是所期待的

*到来的是“不速之客”

*直到结束，也没有到来所“期待”的括号

算法设计思想：

1.凡出现左括号，则进栈

2.凡出现右括号，则检查栈是否为空。若栈空，则表明右括号多余；否则和栈顶元素比较。若相匹配，则左括号出栈；否则表明不匹配

3.表达式检验结束时，若栈为空，则表明表达式之中匹配正确；否则表明左括号多余。

伪代码实现：

void match (char &exp) {
	InitStack(S);
	char c;
	int i = 0, b = 1;
	while(exp[i] != ‘/0’ && b == 1) {
		if(exp[i] == ‘(’)
			Push(S, exp[i]);
		else if(exp[i] == ‘)’) {
			c = Pop(S);
			if( c != ‘(’)
				b = 0;
		}
	i++;
	}
	return (b && StackEmpty(S));
}

3.行编辑程序问题

[分析]在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。

[合理做法]建立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区；并假设“#”为退格符，“@”为退行符。

假设从终端接受了如下字符：

1 2	whli##ilr#e(s#s) outcha@putchar(s=#++);

则实际上的字符为：

1 2	while(*s) putchar(s++);

伪代码实现：

while (ch != EOF && ch != ‘\n’) {
	switch (ch) {
		case ‘#’ : Pop(S,ch);
		     break;
		case ‘@’: ClearStack(S);
		     break;
		//充值S为空栈
		default: Push(S,ch);
			 break;
		}
	ch = getchar(); //从终端接受下一个字符
}
//将从栈底到栈顶传送至调用过程的数据区；
ClearStack(S);	//重置S为空栈
if(ch != EOF) ch = getchar;

4.表达式求值

限于二元运算符的表达式求值

表达式＝操作数+运算符+操作数

操作数＝简单变量 | 表达式

运算符＝标识符 | 无符号整数

表达式的三种标识方法：

设EXP = S1 + OP + S2
则称OP + S1 + S2 为前缀表达式
S1 + OP + S2 为中缀表达式
S1 + S2 + OP 为后缀表达式

例如：EXP ＝ a * b + (c - d / e) * f
前缀式：+ * ab  * - c / def 
中缀式：a * b + c - d / e * f
后缀式：ab *  cde / - f * +

[结论]：1.操作数之间相对次序没变

　　2.运算符的相对次序不同
　　
　　3.中缀式丢失了括号信息，致使运算的次序不确定
　　
　　4.前缀式的运算规则：
　　
　　　　连续出现的两个操作数和在他们之前和紧靠他们的运算符构成一个最小表达式；
　　　　
　　5.后缀式的运算规则：
　　
　　　　运算符在式中出现的顺序恰为表达式的运算顺序。
　　　　
　　　　每个运算符和在他出现之前出现且紧靠他的两个操作数构成最小表达式。

如何从后缀式求值？

　　先找运算符，再找表达式
　　
如何从原表达式求得后缀式？

　　分析原表达式和后缀式的运算符
　　
原表达式：EXP ＝ a b + (c - d / e) f

后缀式：ab cde / - f +

每个运算符的运算次序要由他之后的一个运算符决定，在后缀式中优先数高的运算符领先于优先数低的运算符。

从原表达式求得后缀表达式的规律为：

　　1.设立暂存运算符的栈
　　
　　2.设表达式的结束符为’#’，预设运算符栈的栈底为’#’
　　
　　3.若当前字符为操作数，直接发送给后缀式
　　
　　4.若当前运算符的优先数高于栈顶运算符，则进栈
　　
　　5.否则，将栈顶运算符发送给后缀式，然后该运算符进栈
　　
　　6.’ ( ’对它之前后的运算符起隔离作用，’ ) ’可视为自相应左括号开始的表达式的结束符

5.实现递归

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：

　　1.将所有的实在参数、返回地址等信息传递给被调用函数保存；
　　
　　2.为被调用函数的局部变量分配存储区；
　　
　　3.将控制转移到被调用函数的入口；
　　
　　　　从被调用函数返回到调用函数之前，应该完成下列三项任务：
　　　　
　　　　　　1.保存被调函数的运行结果；
　　　　　　
　　　　　　2.释放被调函数的数据区；
　　　　　　
　　　　　　3.依照被调函数的返回地址将控制转移到调用函数；
　　　　　　
　　　　多个函数嵌套调用的规则是：
　　　　
　　　　　　后调用，先返回(此时内存管理实行“栈式管理”)

栈类型的实现

1.顺序栈：类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针

//栈的顺序存储表示（动态分配）
#define STACK_INIT_SIZE 100
typedef struct {
	SElemType *base;
	SElemType *top;
	int stacksize;
} SqStack;
//注意，非空栈时top始终在顶栈元素的下一个位置

顺序栈的实现：

Status initStack(SqStack &L, int maxsize) {
//构造一个最大空间为maxsize的空顺序栈
	S.base = new SElemType[maxsize];
	if (!S.base) 
		exit(overflow);
	S.top = S.base;
	S.stacksize = maxsize;
	return OK;
}

进栈的实现：

Status push(SqStack &L, SElemType e) {
//若栈不满，则将e推入栈顶
	if (S.top - S.base >= S.stacksize) {
		return(overflow);		//栈满
	}
	*S.top++ = e;
	return OK;
}

top始终指向栈顶元素的下一个位置

出栈的实现：

Status pop(SqStack &L, SElemtype &e) {
//若栈不空，删除栈顶的元素，并返回其值
	if(S.top == S.base)
		return ERROE;
	e = *- -S.top;
	return e;
}

2.栈链形式描述：

typedef struct node {
	SElemType data;
	struct node *next;
}StackNode, *LinkStack;
	
LinkStack top;		//说明top是栈顶指针

因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了方便计算附加一个头指针。

队列的类型定义

ADT Queue {
	数据对象：D = {ai | ai 属于 SElemtype}
	数据关系：R = <ai-1, ai>
			约定其中a1端为队列头，an端为队列尾
	队列的基本操作：
		1.InitQueue (&Q)
		2.DestroyQueue (&Q)
		3.QueueEmpty (Q)
		4.QueueLength (Q)
		5.GetHead (Q, &e)
		6.ClearQueue (&Q)
		7.EnQueue (&Q, e)			//入队
		8.DeQueue (&Q, &e)		//出队
		9.QueueTravers (Q, visit( ))
}ADT Queue

队列类型的实现

1.链队列：链式映象

typedef struct QNode {	//结点类型
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct{		//链队列类型
	QueuePtr front;	//队头指针
	QueuePtr rear;	//队尾指针
}LinkQueue;

InitQueue (&Q)的实现：

	
Status initQueue(&Q) {
	//构造一个空队列Q
	Q.front = Q.rear = new QNode;
	if (!Q.front) 
		return ERROR;
		//分配内存失败
	Q.front  -> next = NULL;
	return OK;
}

EnQueue (&Q, e)的实现：

	
Status enQueue(&Q, e) {
//插入元素e为Q的新队尾元素
	p = new QNode;
	if(!p)
		return ERROR;
	p.data = e;
	p.next = NULL;
	Q.rear.next = p;
	Q.rear = p;
	return OK;
}

DeQueue (&Q, &e) 的实现：

	
Status deQueue(&Q, &e) {
//若队列不空，删除队列的头元素，并用e返回
	if(Q.front == Q.rear) 
		return ERROR;
	p = Q.front.next;
	e = p.data;
	Q.front.next = p.next;
	if(Q.rear == p)
		Q.rear = Q.front;		//针对只剩下一个元素的情况
	delete(p);
	return OK;
}

2.循环队列：顺序映象

【笔者注：此部分建议边画环形图边理解为好】

队列的顺序存储结构中，用一组地址连续存储单元依次存放从队头到对尾的所有元素

附设两个指针front和rear分别指示队头元素的位置和对尾元素的下一个位置

初始化建空列时令front ＝ rear ＝ 0，插入新的对尾元素时尾指针增1，删除队头元素时头指针增1。

注：由于普通的队列的front和rear的同增现象，有可能会出现假上溢情况。

因为在队列的操作中，头尾指针只增加不减小，导致被删除元素的空间永远无法重复利用。尽管队列中实际的元素个数可能远远小于存储空间的规模，但仍然不可以做入队的操作，该现象称为假上溢。

客服假上溢现象的方法是将顺序队列想象成一个首尾相接的圆环，称之为循环队列。

循环队列中是无法通过Q.front = Q.rear 来判断队列“空”还是“满”，解决此问题的方法至少有三种：

　　1.另设一个标志位区别队列中的空与满
　　
　　2.使用一个计数器计录队列中元素的总数(实际上是队列长度)。
　　
　　3.少用一个元素的空间，约定以“队列头指针在队列尾指针的下一个位置(指环状的下一个位置)上”作为队列呈现“满”状态的标志。（在后继算法中我们使用这种方法）.
　　
循环队列类型定义：

#define MAXQSIZE 100
typedef struct {
	QElemType *base;		//动态分配存储空间
	int front;			//头指针，若队列不空；指向队列头元素
	int rear;			//尾指针，若队列不空，指向队列尾元素的下一个位置
	int queuesize;
}

初始化循环队列：

Status initQueue(SqQueue &Q, int maxsize) {
	//构造一个最大存储空间为maxsize的空循环队列Q
	Q.base = new QElemType[maxsize];
	if(!Q.base) 
		return OVERFLOW;
	Q.queuesize = maxsize;
	Q.front = Q.rear = 0;
	return OK;
}

在循环队列中入队的实现：

Status enQueue(SqQueue &Q, ElemTypt e) {
	//插入元素e为Q的新的对尾元素
	if ( (Q.rear + 1) % Q.queuesize == Q.front )
		return OVERFLOW;		//队列满
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % Q.queuesize;
	return OK;
}

在循环队列中出队的实现：

Status deQueue(SqQueue &Q, ElemType &e) {
	//若队列不空，则删除Q的队头元素，用e返回其值
	if(Q.front == Q.rear) 
		return OVERFLOW;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % Q.queuesize;
	return OK;
}

循环队列中需要注意的几点：

　　1.如果Q.front = Q.rear，则可以判断队列已空
　　
　　2.如果（Q.rear + 1）% Q.queuesize = Q.front ，则可以判断队列为满
　　
　　3.无论是对循环队列进行插入或者删除元素时，均可能涉及到尾指针或头指针的调整（非简单的对指针进行+1操作），即：
　　
　　　　Q.rear = (Q.rear + 1) % MAXQSIZE 或
　　　　
　　　　Q.front = (Q.front + 1) % MAXQSIZE
　　　　
　　4.如何理解 (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE 即为循环链表的长度：
　　
　　　　1>当Q.rear > Q.front 时，循环队列长度＝ Q.rear - Q.front
　　　　
　　　　2>当Q.rear < Q.front 时，循环队列长度＝ Q.rear - Q.front + MAXQSIZE
　　　　
　　　　3>综上，循环队列长度＝ (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE
　　　　
3.几种特殊的队列

　　1.双端队列：可以在双端进行插入、删除的线性表
　　
　　2.输入受限的双端队列：线性表的两端都可以输出数据元素，但是只有一端可以进行输入操作
　　
　　3.输出受限的双端队列：线性表的两端都可以输入数据元素，但是只有一端可以进行输出操作

队列与循环链表

【笔者注：这个概念在界内存在广泛争议，如下是笔者所站的立场，读者若有异议请见谅】

队列（包括循环队列），是一个逻辑概念，而链表是一个存储概念。一个队列是否是循环队列，不取决于它将采用何种存储结构，根据实际的需要，循环队列可以采用顺序存储结构，也可以采用链式存储结构，包括采用循环链表作为cc结构。

　　1.一串数据依次通过一个栈，并不能保证出栈的顺序总是倒序，可以产生多种出栈序列。
　　
　　一串数据通过一个栈后的顺序由每个数据之间的入栈出栈次序决定。只有当“所有数据全部入栈后再出栈”才能使数据倒序。事实上，存在一种操作序列——“入栈，出栈，入栈，出栈……”——可以试数据通过栈后次序保持不变
　　
　　2.一串数据通过一个队列，只有一种出队列方式，就是其入队列顺序　　

数组的顺序表示与实现

类型特点：

　　1.只有引用性操作，没有加工型操作
　　
　　2.数组是多维的结构，而存储空间是一个一维的结构
　　
有两种顺序映象的表示：

　　1.以行序为主序（低下标优先）
　　
　　　　二维数组A中任意一个元素aij的存储地址为：LOC(i,j) = LOC(0,0) + (列数 i + j) C //C为元素类型的大小
　　　　
　　2.以列序为主序（高下标优先）　　

特殊矩阵的压缩存储

1.稀疏矩阵

假设m行n列的矩阵含t个非零元素，则称a ＝ t / mn 为稀疏因子。

通常将a < 0.05 的矩阵称为稀疏矩阵。

以常规方法，即以二维数组表示高阶的稀疏矩阵时，会产生的问题：

　　1.零值元素占了很大的空间
　　
　　2.计算中遇到了很多与零值的运算，若遇除法还需判断
　　
解决问题的原则：

　　1.尽可能少存或不存零值元素
　　
　　2.尽可能减少没有实际意义的运算
　　
　　3.操作方便。
　　
即能尽可能快地找到与下标值（i，j）对应元素；能尽可能快地找到同一行或同一列的非零值元。

有两类矩阵：

　　1.特殊矩阵：非零元在矩阵中的分布有一定规则。
　　
　　　　如：对称矩阵，三角矩阵，对角矩阵
　　　　
　　2.随机稀疏矩阵：非零元在矩阵中随机出现
　　
2.对称矩阵的压缩：

aij = aji;

由于对称矩阵的对称性，只用保存上三角或者下三角矩阵的元素就可以了。让每两个对称的元素共享一个存储空间，这样能节约近一半的存储空间。

不失一般性，按行优先顺序存储主对角线（包括对角线）以下的元素，其存储空间的下标为 k ＝ i * (i + 1) / 2 + j （若上三角并且也是按行优先则将i与j互换即可）

因此，aij的地址可用如下方程来计算：

LOC(aij) = LOC(sa[k]) = LOC(sa[0]) + k * C
//不丢失随机存取的特性

对于任意给定一组下标（i，j），均可在sa[k]中找到矩阵元素aij，反之也成立。

3.三角矩阵的压缩：

上三角或者下三角的元素（不包括主对角线）全为常数（一般为0）的矩阵

三角矩阵中的重复元素C可以共享一个存储空间，其余的元素正好有 n(n + 1) / 2 个，因此三角矩阵可以压缩到向量sa[0,…, n(n + 1) / 2 ] 中，其中C存放在向量的最后一个分量中。

上三角aij与sa[k] 的关系为：
	if( i <= j ) 
		k = i(2n - i + 1) / 2 + j - 1;
	else
		k = n(n + 1) / 2;		//存放C
下三角aij与sa[k] 的关系为：
	if( i <= j ) 
		k = i * (i + 1) / 2 + j；
	else
		k = n(n + 1) / 2;		//存放C

4.对角矩阵的压缩：

除了主对角线以及其邻近的若干条对角线上的元素不为0外，其他元素都为0.

对角矩阵可以按行优先顺序或者按对角线的顺序将其压缩存储到一个向量中，并且也能找到每个元素和向量下标的对应关系。

aij与sa[k] 的关系为:

数组sa中的元素sa[k]与三对角带状矩阵中aij存在一一对应的关系。在aij之前有i行，共3i-1个非零元素；在第i行，有j-i+1个非零元素，所以：

k = 2i + j

因此对角矩阵可以压缩到向量sa[0,…, 3n-2 ] 中

5.随机稀疏矩阵的压缩存储方法

三元组顺序表(计数从0开始)

define MAXSIZE 12500
typedef struct {
	int i, j;			//该非零元的行下标与列下标
	ElemType e;		//该非零元的值
}Triple;			//三元组类型

typedef union {
	Triple data[MAXSIZE + 1];
	int mu, nu, tu;	//行数、列数、非零元素的个数
}TSMatrix;			//稀疏矩阵类型

SaberDa的幻想乡

C++/ JS　　|　　呐呐呐　　|　　gli97@gwmail.gwu.edu　　|　　没有什么胜利可言挺住就意味着一切