指针与引用 概念 指针从本质上讲就是存放变量地址 的一个变量，在逻辑上是独立的，它可以被改变，包括其所指向的地址的改变和其指向的地址中所存放的数据的改变。 引用是一个别名，它在逻辑上不是独立的，它 的存在具有依附性，所以引用必须在一开始就被初始化，而且其引用的对象在其整个生命周期中是不能被改变的（自始至终只能依附于同一个变量）。

指针与引用 参数传递 指针传递参数本质上是值传递的方式，它所传递 的是一个地址值。值传递过程中，被调函数的形式参数作为被调函数的局部变量处理，即在栈中开辟了内存空间以存放由主调函数放进来的实参的值，从而成为了实 参的一个副本。值传递的特点是被调函数对形式参数的任何操作都是作为局部变量进行，不会影响主调函数的实参变量的值。（这里是在说实参指针本身的地址值不会变） 在引用传递过程中，被调函数的形式参数虽然 也作为局部变量在栈中开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何操作都被处理成间接寻址，即通过栈中存放 的地址访问主调函数中的实参变量。正因为如此，被调函数对形参做的任何操作都影响了主调函数中的实参变量。 引用传递和指针传递是不同的，虽然它们都是在 被调函数栈空间上的一个局部变量，但是任何对于引用参数的处理都会通过一个间接寻址的方式操作到主调函数中的相关变量。而对于指针传递的参数，如果改变被调函数中的指针地址，它将影响不到主调函数的相关变量。如果想通过指针参数传递来改变主调函数中的相关变量，那就得使用指向指针的指针，或者指针引用。

指针与引用 编译的角度 程序在编译时分别将指针和引用添加到符号表上，符号表上记录的是变量名及变量所对应地址。指针变量在符号表上对应 的地址值为指针变量的地址值，而引用在符号表上对应的地址值为引用对象的地址值。符号表生成后就不会再改，因此指针可以改变其指向的对象（指针变量中的值 可以改），而引用对象则不能修改。

指针与引用 总结 相同点： 不同点： 都是地址的概念； 指针指向一块内存，它的内容是所指内存 的地址；而引用则是某块内存的别名。 指针是一个实体，而引用仅是个别名； 引用只能在定义时被初始化一次，之后不可 变；指针可变；引用“从一而终”，指针可以“见异思迁”； 引用没有const，指针有const，const的指针不可变；（具体指没有int& const a这种形式，而const int& a是有     的，  前者指引用本身即别名不可以改变，这是当然的，所以不需要这种形式，后者指引用所指的值不可以改变） 引用不能为空，指针可以为空； “sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到的是指针本身的大小； 指针和引用的自增(++)运算意义不一样； 引用是类型安全的，而指针不是 (引用比指针多了类型检查

数 据 结 构 Ch.3 栈和队列 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj

§3.1 栈 定义和运算 入栈 出栈 栈 —— 仅在表的一端插、删的(操作受限)线性表 栈顶 —— 插删的一端 栈底 —— 另一端 插入——进（入）栈、删除——出（退）栈 栈顶 —— 插删的一端 栈底 —— 另一端 结构特征 --“后进先出” 修改原则：退栈者总是最近入栈者 服务原则：后来者先服务 （LIFO表） 例： 入栈 出栈

§3.1 栈 Note:后入栈者先出栈，但不排除后者未进栈，先入栈者先出栈。 基本运算：① 判栈空 ②入栈 ③出栈 ④判栈 满 ⑤读栈顶 ⑥置空栈

§3.1.1 顺序栈 底相对固定 可设在向量的任一端 Top指针为下标类型 (整型量) #define StackSize 100 typedef struct { DataType data[StackSize]; int top; }SeqStack;

§3.1.1 顺序栈 设栈底在向量低端data[0]，则： 入栈 ：top+1 出栈：top-1 栈空：top<0 栈满：top=StackSize-1 上溢：满时入栈 下溢：空时出栈(不一定是错误)

§3.1.1 顺序栈 Note：top指针不是指物理地址，与C的指针变量含义不同。可理解为相对地址，是指示元素的所在位置

§ 3.1.1 顺序栈 实现： 初始化 （置空栈） int StacEmpty(SeqStack &S) { //亦可用非引用 判栈满 void InitStack(SeqStack &S) { //必须引用 S.top=-1; } 判栈空 int StacEmpty(SeqStack &S) { //亦可用非引用 return S.top<0;} 判栈满 int StackFull (SeqStack &S) { return S.top==StackSize-1;}

§ 3.1.1 顺序栈 入栈 void Push(SeqStack &S, DataType x) { 出栈 读栈顶 两个栈共享空间 if(StackFull(S)) Error(“overflow”); S.data[++S.top]=s; // 指针先加1，后x入栈 } 出栈 DataType Pop(SeqStack &S) { if(StackEmpty(S)) Error(“UnderFlow”); //下溢 return S.data[S.top--]; //返回栈顶后指针减1 读栈顶 两个栈共享空间

§ 3.1.2 链栈 只在表头操作，故头指针即为top，无需头结点 定义 typedef struct snode { DataType data; struct snode *next; } StackNode; typedef struct { StackNode *top; } LinkStack; 链栈动态分配结点，无需考虑上溢

§ 3.1.2 链栈 void InitStack(LinkStack &S) { S.top=Null; } int StackEmpty (LinkStack &S) { return S.top==NULL; void Push(LinkStack &S, DataType x) { StackNode *p=(StackNode*) malloc (sizeof(StackNode)); p->data=x; p->next=s.top; s.top=p;

§ 3.1.2 链栈 DataType Pop(LinkStack &S) { DataType x; StackNode *p=S.top; if(StackEmpty(S)) Error (“underflow”); // 下溢 x=p->data; S.top=p->next; free(p); return x; }

§3.2 队列 定义 队列：运算受限的线性表，一端插入(队尾)，另一端删除(队头)。 结构特征： 例子：排队现象 操作： 先进先出，先来先服务，FIFO表 例子：排队现象 操作： 入队(插入)序列： 出队(删除)序列：

§ 3.2 队列 顺序队列 —— 队列的顺序存储结构 空队列：front = rear； 初值为0 入队：插入rear位置，然后加1

§ 3.2 队列 上溢：队满时入队 下溢：队空是出队 (不一定是错误，可能是转移控制条件) 伪上溢：队非满但不能插入 原因：f，r 只增不减 例如：入，出，入，出，…… 尽管任一时刻，队中最多只有1个元素，但无论事先定义多大的空间，均会产生指针越界

§ 3.2 队列 怎样消除伪上溢？ 循环队列： 实用顺序队列多为循 环队列 重复利用已删除的结点空间，将向量视为首尾相接的环。这种用循环向量实现的队列称为循环队列。 f，r在循环定义下的加1动作： 越界时，令其指向下界0 i = (i+1==QueueSize) ? 0:i+1; // i为front或rear 可用模运算简化： i=(i+1)%QueueSize; 循环队列： 实用顺序队列多为循 环队列

§ 3.2 队列 边界问题 队满和队空时，front=rear，如何区分？解决方法： 设一布尔量以示区分 留一个结点不用。约定 入队前，测试尾指针+1 (循环定义下) 是否等于头指针。若相等则为满 使用1个计数器，记录队列长度 （用此法） #define QueueSize 100 typedef struct { int front; int rear; int count; DataType data [QueueSize]; } CirQueue;

§ 3.2 队列 操作实现 置空队 void InitQueue (CirQueue &Q) { Q.front = Q.rear = 0; Q.count = 0; // 队空 } 判队空 int QueueEmpty (CirQueue &Q) { return Q.count == 0; } 判队满 int QueueFull (CirQueue &Q) { return Q.count ==QueueSize; }

§ 3.2 队列 入队 void EnQueue (CirQueue &Q, DataType x) { if (QueueFull (Q) ) Error(“overflow”); //上溢 Q.count++; Q.data [Q.rear] = x; // 插入 Q.rear = (Q.rear+1)%QueueSize; // 尾指针加1 } 出队 DataType DeQueue (CirQueue &Q) { if(QueueEmpty (Q) ) Error (“underflow”); //下溢，不一定是错 temp = Q.data[Q.front]; Q.count--; Q.front= (Q.front+1)%QueueSize; return temp; }

§ 3.2 队列 链队列 仅限于在表头和尾插删的单链表 typedef struct qnode{ 不带头节点： DataType data; struct qnode *next; }QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue; 不带头节点：

§ 3.2 队列 void InitQueue (LinkQueue &Q) { Q.front = Q.rear = NULL; //有头结点是不同 } int QEmpty (LinkQueue &Q) { //无上溢，故不判满队 return Q.front == NULL; // 头尾指针均为空，有头结点时 f = r void EnQueue (LinkQueue &Q, DataType x) { QNode *p = (QNode*) malloc( sizeof(QNode) ); p->data = x; p->next = NULL; // 新结点作为新的队尾 if (Q.Empty(Q) ) // 若有头结点无需判此项 Q.front = Q.rear = p; // 插入空队 else { // 插入非空队尾，有无头结点均要做此项 Q.rear->next = p; // *p链到原尾结点之后。 Q.rear = p; // 指向新尾*p

§ 3.2 队列 DataType DeQueue (LinkQueue &Q) { if ( QEmpty(Q) ) Error (“underflow”); //下溢 p = Q.front; // 指向队头 x = p->data; Q.front = p->next; // 队头摘下 if (Q.rear == p) // 原队中只有一个结点，删去后队变空 Q.rear = NULL; free (p) ; return x; }

§ 3.3 栈和队列的应用 § 3.3.1 栈的应用 数据转换 问题： 一非负十进制整数N 基为B的B进制数 例： 规律： （3.1） 其中 表示B进制数的第 i 位数字 十进制数N可用长度为 位B进制数表示为

§3.3.1 栈的应用 如何确定 ？ 令 ，则（3.1）式为： （3.2） (3.2)式整除B，则余数为 ，商为括号内的和式。故 (3.2)式可表达为： // “/”为整除 算法思想： 模除求余数： 整除求商：N/B，令此为新的N，重复①求 ，反复至某N为0时结束 上述过程依次求出的B进制各位为(从低位至高位): 用栈保存，退栈输出 即为所求。

§ 3.3.1 栈的应用 例如：

§ 3.3.1 栈的应用 实现 typedef int DataType； void MultiBaseOutput (int N, int B) { // N为非负十进制整数， B为基 int i; SeqStack S; //顺序栈S InitStack(S); //置空栈 while (N) { //从右向左产生bi , i=0,1, …, j push(S, N%B); // 将 bi 入栈 N=N/B; } while( !StackEmpty(S)) { // 栈S非空 i = Pop(S); printf(“%d”,i); 时间复杂度 29 29

2.栈与递归 § 3.3.1 栈的应用 递归是一种强有力的数学工具，可使问题的描述和求解变得简洁与清晰 递归：若一函数、过程或数据结构定义的内部又直接或间接使用定义本身，则称它们是递归的，或递归定义的 30 30

§ 3.3.1 栈的应用 递归算法设计（分治法）分解、求解、组合 step1： 将原问题分解为一个或多个规模更小，但与原 问题特性类似的子问题 (递归步骤) // 解子问题 为调用语句 step2：确定一个或多个无须分解，可直接求解的最小子 问题 (终结条件) // 归纳基础 例 1： int F (int n) { //设n为非负整Œ数 if (n==0) return 1; else return n*F(n-1) ; } //递归终结条件 //递归步骤 (n-1)!规模比n!小1 至少有一个直接求解的最小子问题，保证递归终止，否则无限循环 分解为一个子问题，若F(n)是解n!，则F(n-1)可解(n-1)!

§ 3.3.1 栈的应用 例2： 有些问题表面上不是递归定义的，但可通过分析，抽象出递归的定义。 写一个就地生成n个元素 全排列 (n!) 的算法，要求算法终止时保持 原状 解：设 A[0 ..n-1] 基类型为char,“就地 (in place)”不允许使用 A 以外的数组 生成 全排列 n个子问题 分解

§ 3.3.1 栈的应用 递归终结分支 当 n=1 时， 一个元素全排列只有一种，即为本身。实际上无须进一步递归，可直接打印输出A # define N 8 // A[0..7] void permute (char A[], int n) { //外部调用时令 n=7 if(n==0) print (A); // 打印A[0..7] else { Permute(A,n-1); //求A[0..n-1]的全部排列。1st子问题不用交换 for (i=n-1; i>0; i--) { Swap(A[i], A[n]); // 交换 和 内容，说明为引用 Permute(A,n-1); // 求A[0..n-1] 全排列 Swap(A[i],A[n]); //交换 } } }

§ 3.3.1 栈的应用 算法时间分析： 所以实验时，n不能太大 例3：n阶Hanoi塔问题 将X上的圆盘移到Z上，要求按同样次序排列，且满足： 每次只能移动一片 圆盘可插在X，Y，Z任一塔座上 任一时刻不能将大盘压在小盘上

§ 3.3.1 栈的应用 分解 设 n>1 原问题：将n片从X移到Z，Y为辅助塔，可分解为： 将上面n-1 个盘从X移至Y，Z为辅助盘 将 nth 片从X移至 Z 将Y上n-1个盘子移至Z，X为辅助盘 终结条件 n = 1时，直接将编号为1的盘子从 X 移到Z void Hanoi (int n, char x, char y, char z ) { // n个盘子从 X 移至 Z，Y 为辅助 if ( n==1 ) move(X,1,Z); // 将1号盘子从 X 移至 Z, 打印 else { Hanoi (n-1,x,z,y); //源X，辅Z，目Y move (x,n,z); Hanoi (n-1,y,x,z); //源Y，辅X，目Z } //子问题特征属性与原问 //题相同规模小1，参数不//同

§ 3.3.1 栈的应用 递归的内部实现 调用 调用一个函数时，系统将为调用者构造一个活动记录，并将其压入栈的顶，然后将程序控制权转移到被调用函数。若被调用函数有局部变量，则在栈顶也要为其分配空间，形成一个活动结构。 实际上所有的递归或非递归函数都是这样实现的 活动结构： 局部变量 活动记录：参数表的内容为实参 返址为函数调用语句的下一指令的位置

§ 3.3.1 栈的应用 返回 当被调用函数执行完毕时，系统将活动结构退栈，并根据退栈返回地址将程序控制权转移给调用者继续执行 例： F(4)为例 改写： int F (int n) { int temp; if (n==0) return 1; //返回语句引 起退栈 else { //调用F(n-1) 引起入栈 temp = n*F(n-1); return temp; // 退栈 } void main(void) { int n; n = F(4); //调用引起压栈 } Ret L1 Ret L1: 赋值语句的地址 Ret L2: 计算乘法的地址 为简单起见，假设局部变量不入栈 Ret L2

§ 3.3.1 栈的应用 执行返回指令 Ret L2: temp=1*1; //从F(0）返回 0! = 1 是递归终结条件，故执行F(0)引起返回(return 1) 退栈 , 返回到F(1)的Ret L2处，继续执行temp = 1*1； 按着执行return temp又引起 退栈，返回到F(2)的Ret L2处，执行temp = 2*1，… 执行返回指令 Ret L2: temp=1*1; //从F(0）返回

典型的堆栈帧结构如图所示。堆栈中存放的是与每个函数对应的堆栈帧。当函数调用发生时，新的堆栈帧被压入堆栈；当函数返回时，相应的堆栈帧从堆栈中弹出。

函数调用示例 函数： EIP(指令指针)、EBP(基址指针)、ESP指针(堆栈指针) Stack frame 函数： int func(int a, int b){ int retVal = a + b; return retVal; } int main(int argc, char* argv[]) { int result = func(1, 2); printf("Hello World!\n"); return 0; EIP(指令指针)、EBP(基址指针)、ESP指针(堆栈指针) Call DST: SP=SP-2, (SP+1,SP)=IP, IP=IP+D16 RET EXP: IP=(SP+1,SP), SP=SP+2, SP=SP+D16 … 2 1 Ret-add ebp retVal …

§ 3.3.1 栈的应用 递归算法的正确性 初学者很难相信递归程序的正确性 原因：一个函数尚未完成 (即对本函数的正确性还未确 信) 时又调用了自身，故对递归函数正确性缺乏 信心 例：非递归函数或过程 假设Q正确的情况下，证明了P正确， 则一旦证明了被调过程Q是正确的，我们就对P的正确性深信不疑！ 由于P、Q各自独立，独立于P来证明Q的正确性很容易，这大概是对自己写非递归程序较有信心的缘故

§ 3.3.1 栈的应用 若P是递归过程，则不可能独立于P来证明被调过程 (亦自身) 是否正确。因此，我们只能假设过程P内部所有递归的调用是正确的 (不考虑其内部实现细节)，才能由此证明P的正确性。其理论依据是数学归纳法： (1) 证明参数满足递归终结条件时函数或过程正确 (相当于归纳基础)。 假设过程函数内部的所有递归调用语句正确 (相当于归纳假设)，由此证明过程正确或函数是正确的 (相当于归纳步骤) Note: 函数内的递归调用语句的参数应比函数本身的参数更接近递归终结条件参数，这样才能确保递归是可终止的

3.表达式求值 § 3.3.1 栈的应用 算符优先法: 先乘除，后加碱；从左到右计算；先括号内后括号外 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 操作数(operand): 变量、常量，进OPND栈 操作符(operator): 算术、关系、逻辑运算符，进OPTR栈 界限符(delimiter): #，（，） 43 43

算符间的优先关系: θ1 θ2 + - * / ( ) # + > > < < < > > θ1 θ2 + - * / ( ) # + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < = Precede: 判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间 的优先关系的函数. Operate: 进行二元运算aθb的函数.

OperandType EvaluateExpression() {InitStack(OPTR); Push(OPTR, ‘#’); InitStack(OPND); c = getchar(); While(c!=’#’ || GetTop(OPTR)!=’#’){ If(!In(c,OP)){ Push(OPND,c); c = getchar();} // 不是运算符则进栈 else switch(Precede(GetTop(OPTR),c)){ case ‘<’: // 栈顶元素优先权低 Push(OPTR,c); c = getchar(); break; case ‘≒’: // 脱括号并接受下一个字符 Pop(OPTR,x); c = getchar(); break; case ‘>’: // 退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; default: printf(“Expression error!”); return(ERROR); } // switch } // while return GetTop(OPND); } // EvaluateExpression

对算术表达式3*(7-2)求值 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 3 * ( 7 - 2 ) # Push(OPND,’3’) 2 # 3 * ( 7 - 2 ) # Push(OPTR,’*’) 3 # * 3 ( 7 - 2 ) # Push(OPTR,’(’) 4 # * ( 3 7 - 2 ) # Push(OPND,’7’) 5 # * ( 3 7 - 2 ) # Push(OPTR,’-’) 6 # * ( - 3 7 2 ) # Push(OPND,’2’) 7 # * ( - 3 7 2 ) # Operate(‘7’,’-‘,’2’) 8 # * ( 3 5 ) # POP(OPTR) 9 # * 3 5 # Operate(‘3’,’*’,’5’) 10 # 15 # Return(GetTop(OPND))

§3.3.2 队列的应用 例：周末舞会，男、女各排成一队，跳舞时，依次从男、女队的头上各出一人配成舞伴，若两队人数不同，较长的队中未配对者等下一轮舞曲 typedef struct { char name[20]; char sex; // M—男，F—女 } Person; typedef person DataType; //将队列定义中的数据类型改为Person void DancePartners（Person dancer[ ], int num）{ int i; Person P; CirQueue Mdancers, Fdancers; InitQueue(Mdancers); // 男士队列 InitQueue(Fdancers);

§3.3.2 队列的应用 for( i=0; i<num; i++ ) { P = dancer[ i ]; if (P.sex == ‘M’) EnQueue (Mdancers, P); // 入男队 else EnQueue (Fdancers, P); // 入女队 } printf (“The dancing partners are:\n\n”); while (!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers)) { // 男女队列均非空 P=DeQueue(Fdancers); // 女士出队 printf(“%s ”, P.name); // 女士姓名 P=DeQueue(Mdancers); //男士出队 printf(“%s\n”, P.name);

§3.3.2 队列的应用 if (!QueueEmpty(Fdancers)) { //女队非空，输出剩余人数及队头者名字 printf(“\n There are %d women waiting for the next round.\n”, Fdancers.count);// count是队列属性，长度 P=QueueFront(Fdancers); // 取队头 printf (“%s will be the first to get a partner.\n”, P.name); } else{ // 男队类型处理 } 时间复杂度：O(n)