201447 指针与引用 指针与引用 ■◆数传递 ■概念 零指针传 ◆指针从本质上讲就是存放变量地址的一个变县 在逻携上是独立的，它可以披改变，包括基 所指向的地址的改变和其指向的地址中所存放 的数据的改变。 。引用是一个别名，它在逻辑上不是独立的， 它 的存在具有依附性，所以引用必须在一开女 科翼宋能版文的（百瑞宝致精 被初始化：而且其引用的对像在其整个生命 个变量) 指针与引用 指针与引用 ·总结 ◆相同点： ■编译的角度 乡都是地址的振意) 指针指向一峡内存，它的内毫是所指内存的地址；而引用侧是菜块内存的别 ◆程序在编泽时分别将指针和引用添加到符号表 符号表上记录的是变量名及变量所对应地 ◆不同点1 上 。指针变量在符号表上对应的地址值为指针 产指针是一个实体，而引用仅量个别名： 引用只能在定义时被初始化一次，之后不可变：抛针可变：引用“从一而络 变量的地址值，而引用在符号表上对应的地址 ,指针河以“见异息迁”， 值为引用对象的地址值。符号表生成后就不会 引用没有c。 指针有const,cons的指针不可度，（具体指有nt nsta种形式，而const int这a有 指引本身即名不可 再改，因此指针可以改变其指向的对象（指针 以改变，这是当然的，所以不需要这种形式，后者指引用所的值不可以改 海》 变量中的值可以改)，而引用对象则不能修放 引用不能为空，指针可以为空： 28of引用”得到的是所指向的变量对像的大小，而“s2Eof指针”得到 的是指针本鼻的大小： 指针和引用的户增+漫算童义不一样； 引用量类型安全的，而物针不是引用比指针多了类世查 83.1栈 数据结构 ■定义和运算 ◆栈—仅在表的一端插、副的操作受限)线性表 擂入—进（入）找、膝一—出（退）找 Ch.3栈和队列 ◆栈顶—一插副的一端 ◆栈底一另一端 计算机学院 肖明军 结构特征一“后进先出” 修改原则：退烛者总是量近入找者 Email:xiaomj@ustc.edu.cn 服务原则：后来者先服务（山FO瘦） 例a1,a2,·.·,an 入栈 http://staff.ustc.edu.cn/-xiaomj Cn,0n-1,···,a1 出栈
2014/4/7 1 指针与引用 概念 指针从本质上讲就是存放变量地址 的一个变量 ，在逻辑上是独立的，它可以被改变，包括其 所指向的地址的改变和其指向的地址中所存放 的 的变 数据 改 。 引用是一个别名，它在逻辑上不是独立的，它 的存在具有依附性，所以引用必须在一开始就 被初始化，而且其引用的对象在其整个生命周 期中是不能被改变的（自始至终只能依附于同 一个变量）。 指针与引用 参数传递 指针传递参数本质上是值传递的方式，它所传递 的是一个地址值。值 传递过程中，被调函数的形式参数作为被调函数的局部变量处理，即 在栈中开辟了内存空间以存放由主调函数放进来的实参的值，从而成 为了实 参的一个副本。值传递的特点是被调函数对形式参数的任何操 作都是作为局部变量进行，不会影响主调函数的实参变量的值。（这 里是在说实参指针本身的地址值不会变） 在引用传递过程中，被调函数的形式参数虽然 也作为局部变量在栈中 开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的 地址。被调函数对形参的任何操作都被处理成间接寻址，即通过栈中 存放 的地址访问主调函数中的实参变量。正因为如此，被调函数对形 参做的任何操作都影响了主调函数中的实参变量。 引用传递和指针传递是不同的，虽然它们都是在 被调函数栈空间上的 一个局部变量，但是任何对于引用参数的处理都会通过一个间接寻址 的方式操作到主调函数中的相关变量。而对于指针传递的参数，如果 改变被调函数中的指针地址，它将影响不到主调函数的相关变量。如 果想通过指针参数传递来改变主调函数中的相关变量，那就得使用指 向指针的指针，或者指针引用。 指针与引用 编译的角度 程序在编译时分别将指针和引用添加到符号表 上，符号表上记录的是变量名及变量所对应地 址。指针变量在符号表上对应 的地址值为指针 变量的地址值，而引用在符号表上对应的地址 值为引用对象的地址值。符号表生成后就不会 再改，因此指针可以改变其指向的对象（指针 变量中的值 可以改），而引用对象则不能修改 。 指针与引用 总结 相同点： 都是地址的概念； 指针指向一块内存，它的内容是所指内存 的地址；而引用则是某块内存的别 名。 不同点： 指针是一个实体，而引用仅是个别名； 引用只能在定义时被初始化 次 引用只能在定义时被初始化一次，之后不可 变；指针可变；引用“从 而终 一 ”，指针可以“见异思迁”； 引用没有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 栈 定义和运算 栈 —— 仅在表的一端插、删的(操作受限)线性表 插入——进（入）栈、删除——出（退）栈 栈顶 —— 插删的一端 栈底 —— 另一端 6 栈底 另 端 结构特征 --“后进先出” 修改原则：退栈者总是最近入栈者 服务原则：后来者先服务 （LIFO表） 例： 入栈 出栈 n a 2 a 1 a
2014/47 s3.1栈 s3.1.1顺序找 Note:后入栈者先出栈，但不排除后者未进找， 底相对固定 先入栈者先出栈。 。可设在向量的任一端 Top指针为下标类型（整型量） #define StackSize 100 typedef struct{ DataType data[StackSize]; 基本运算：①判栈空②入栈③出栈④判栈 满⑤读找顶⑥置空栈 int top; )SegStack; s3.1.1顺序栈 §3.1.1顺序栈 ■设栈底在向量低端data0],则： 设如指向当省钱须元 ◆入找：top+1 出栈：top-1 ◆栈空：top<0 具县具县 栈满：top=StackSize-1 ◆上溢：满时入栈 ◆下溢：空时出栈（不一定是错误） Note:top指针不是指物理地址，与C的指针变量 含义不同。可理解为相对地址，是指示元素的所 在位置 §3.1.1顺序栈 83.1.1顺序栈 ■实现： 入栈 ◆初始化（置空栈） void Push(SeqStack &S,DataType x){ void InitStack(SeqStack&S)(l必须引用 if(StackFull(S)) Error("overflow"); S.data[++s.top]F5;∥指针先加1，后x入钱 S.top=-1;} ◆判栈空 出栈 int StacEmpty(SeqStack&s)(l亦可用非引用 DataType Pop(SeqStack &S){ return S.top<0;) if(StackEmpty(S》Error("UnderFlow;I下港 ◆判栈满 return S.data[S.top-小：士返回项后指针减1 int StackFull (SeqStack &S)( 。读栈顶 return S.top==StackSize-1;) ■两个找共享空间 2
2014/4/7 2 §3.1 栈 Note:后入栈者先出栈，但不排除后者未进栈， 先入栈者先出栈。 2 1 ,,, n a aa 7 基本运算：① 判栈空 ②入栈 ③出栈 ④判栈 满 ⑤读栈顶 ⑥置空栈 §3.1.1 顺序栈 底相对固定 可设在向量的任一端 Top指针为下标类型 (整型量) #define StackSize 100 8 typedef struct { DataType data[StackSize]; int top; }SeqStack; 设栈底在向量低端data[0]，则： 入栈 ：top+1 出栈：top-1 栈空：top<0 §3.1.1 顺序栈 栈空：top<0 栈满：top=StackSize-1 上溢：满时入栈 下溢：空时出栈(不一定是错误) 9 §3.1.1 顺序栈 10 Note：top指针不是指物理地址，与C的指针变量 含义不同。可理解为相对地址，是指示元素的所 在位置 § 3.1.1 顺序栈 实现： 初始化 （置空栈） void InitStack(SeqStack &S) { //必须引用 S.top=-1; } 判栈空 11 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入栈 } 出栈 12 DataType Pop(SeqStack &S) { if(StackEmpty(S)) Error(“UnderFlow”); //下溢 return S.data[S.top--]; //返回栈顶后指针减1 } 读栈顶 两个栈共享空间
201447 §3.1.2链栈 s3.1.2链栈 ■只在表头操作，故头指针即为op,无需头结点 void InitStack(LinkStack &S){ S.top=Null; 定义 typedef struct snode{ int StackEmpty (LinkStack &S){ DataType data; return S.top==NULL; struct snode'next; }StackNode; void Push(LinkStack &S,DataType x){ typedef struct( StackNode 'p=(StackNode")malloc(sizeof(StackNode)); StackNode 'top; p>data=x; }LinkStack; p>next=s.top; s.top=p; ■链找动态分配结点，无需考虑上溢 s3.1.2链找 §3.2队列 DataType Pop(LinkStack &S){ 1,定义 DataType x; ◆队列：运算受限的线性表，一端插入（队尾），另一端」 StackNode 'p=S.top; 除（队头）。 if(StackEmpty(S》 ◆结构特征： Error"underflow":∥下溢 x=p>data; ,先进先出，先来先服务，FFO表 S.top=p->next; ◆例子：排队现象 free(p); 操作： return x粉 入队播入)序列：a1···an 出队除序列：a1···an 83.2队列 83.2队列 2顺序队列一队列的顺序存储结构 ◆上滋：队满时入队 ◆空队列：front=rear;初值为0 ◆下滋：队空是出队（不一定是错误，可能是转移控 ◆入队：插入rear位置，然后加1 制条件)】 ◆出队：去front)所指元素，然后加1 ◆伪上滋：队非满但不能插入 ,头指针什ot物向实际队头元素 原因：{，「只不城 ,尾指针er指向实际队属元赛的下一个位量 例如：入，出，入，出， AB C 尽管任一时制，队中量多只有1个元凛，但无论事先定义 deet: 地 多大的空间，均会产生指针越界 6123 (eA 3
2014/4/7 3 § 3.1.2 链栈 只在表头操作，故头指针即为top，无需头结点 定义 typedef struct snode { DataType data; t t d* t 13 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; } 14 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; 15 x p S.top=p->next; free(p); return x; } §3.2 队列 1. 定义 队列：运算受限的线性表，一端插入(队尾)，另一端删 除(队头)。 结构特征： 先进先出，先来先服务，FIFO表 16 例子：排队现象 操作： 入队(插入)序列： 出队(删除)序列： § 3.2 队列 2. 顺序队列 —— 队列的顺序存储结构 空队列：front = rear； 初值为0 入队：插入rear位置，然后加1 出队：删去front所指元素，然后加1 头指针 front 指向实际队头元素 17 指向实际队头元素 尾指针 rear 指向实际队尾元素的下一个位置 § 3.2 队列 上溢：队满时入队 下溢：队空是出队 (不一定是错误，可能是转移控 制条件) 伪上溢：队非满但不能插入 原因：f，r 只增不减 18 例如：入，出，入，出，…… 尽管任一时刻，队中最多只有1个元素，但无论事先定义 多大的空间，均会产生指针越界
20147 §3.2队列 s32队列 ◆怎样消除伪上溢？ ◆边界问题 队满和队空时，ront=rear,如何区分？解决方法 ①设一布尔量以示区分 ,r在须环定义下的加1助作 留一个结点不用。约定 越界时，今其指向下界0 入队前，测试尾指针+1（循环定义下）是否等于头指 i=(t1=QueueSize)?0:#1;∥i为frontl或rear 针。若相等测为满 可用模运算前化： ③使用个计数围，记录队列长度（用此法） =(i+1)%QueueSize: #define QueueSize 100 。循环队列： typedef struct{ int front; 实用顺序队列多为循 int rear; int count; 环队列 DataType data [QueueSize]; CirQueue; §3.2队列 §3.2队列 ◆操作实现 入队 置空队 void EnQueue(CirQueue &Q,DataType x){ void InitQueue (CirQueue &Q){ if (QueueFull (Q)) Q.front =Q.rear =0: Error("overflow");//上溢 Q.count++: Q.count=0;∥队空 Q.data[Q.rear]=x;∥入 Q.rear=(Q.rear+1)%QueueSize;∥指针加t 判队空 int QueueEmpty (CirQueue &Q){ 出队 return Q.count==0; DataType DeQueue (CirQueue &Q){ if(QueueEmpty(Q) Erro rhow":/下溢，不一定是蜡 int QueueFull (CirQueue &Q){ temp=Q.data[.fron return Q.count ==QueueSize; Q.count--; Q.front=(Q.front+1)%QueueSize; return temp; 83.2队列 83.2队列 3. 链队列 void InitQueue (LinkQueue &Q){ Q.front=Q.rear=NULL;有头结点是不同 仅限于在表头和尾插侧的单链表 不带头节点 int QEmpty (LinkQueue&Q)(l凭上溢，故不判满队 typedef struct qnode( return o.front=NULL;∥头愿指针均为空，有头轴点时f=r DataType data; struct qnode 'next: void EnQueue (LinkQueue &Q,DataType x){ }QNode; (a空队列 QNode 'p =(QNode")malloc(sizeof(QNode)); p->data=x:p->next=NULL;∥新结点作为新的队见 计(Q.Empy(Q)）∥若有头结点无需判此项 typedef struct Q fron Q.front-=Q.rear=p∥入空队 QNode 'front; se{∥滑入非空队凰，有无头结点均要徽此项 QNode 'rear; Q.rear->next=p;∥“p链到眼具轴点之后， }LinkQueue; Q.rear=p:∥指向新属p
2014/4/7 4 § 3.2 队列 怎样消除伪上溢？ 重复利用已删除的结点空间，将向量视为首尾相接的环。 这种用循环向量实现的队列称为循环队列。 f，r在循环定义下的加1动作： 越界时，令其指向下界0 i = (i+1==QueueSize) ? 0:i+1; // i为front或rear 19 可用模运算简化： i=(i+1)%QueueSize; 循环队列： 实用顺序队列多为循 环队列 § 3.2 队列 边界问题 队满和队空时，front=rear，如何区分？解决方法： ① 设一布尔量以示区分 ② 留一个结点不用。约定 入队前，测试尾指针+1 (循环定义下) 是否等于头指 针。若相等则为满 20 ③ 使用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; // 队空 } 判队空 21 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 } 22 出队 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 队列 3. 链队列 仅限于在表头和尾插删的单链表 typedef struct qnode{ DataType data; struct qnode *next; *Q 不带头节点： 23 }QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue; （a） 空队列 1a n a § 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) { 24 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 } }
201447 §3.2队列 §3.3栈和队列的应用 DataType DeQueue(LinkQueue &Q){ S3.3.1找的应用 if QEmpty(Q)) 1数据转换 Eror('underflow;下港 问题：一非负十进制整数N→基为B的B进制数 p=Q.front;;∥指向队头 例： x=p->data; 280=88+480=34 2810=34 720=1·4+0-42+2-4+0-P=1021 Q.front=p->next∥队头摘下 f(Q.rear=p)∥原队中只有一个结点，去后队变空 规辣：N= 0≤≤B-1 (3.1) Q.rear=NULL; 其中山表示B进制数的第位敷字 free(p); 十进制数N可用长度为oga N门+1位B进制数表示为 return x; b1ogaN1…b2bbo s3.3.1栈的应用 §3.3.1栈的应用 ◆如何确定：？ 例蜘：V=353点6741 令.N则(3.1)式为： N=bB+-1B卡+b1B+玩 =(B1+b-B-”+…+2B+)B+ (3.2) (3.2)式整除B,则余数为bn商为括号内的和式。故(3.2)式 6 可表达为： N=(N/B)·B+N%B∥“为整除 ◆算法思想： 01 0 1 ①障求余数：N%B÷咖 雪整珠求商：WB,令此为新的N,量复①求b,反复至某N为0时的桌 8=1 44 空程 58-7 68-6 上述过程依次求出的B进制各位为（从低位至高位）：，们，·， N8-444 4448-55 55/86 6/80 用转保存，退找输出，而-1，-·，2，，即为所求。 N3553 为44 N55 N-0 s3.3.1栈的应用 s3.3.1栈的应用 实现 typedef int DataTyper 2栈与递归 void MultiBaseOutput (int N,int B){ ∥N为非负十进制整数，B为基 int SeqStack S:序s ◆递归是一种强有力的数学工具，可使问 InitStack(SM置空找 题的描述和求解变得简洁与清晰 R心sN将4Xar while(N{l从右向左产生色，i=0,1, N=N/B: 递归：若一函数、过程或数据结构定义 的内部又直接或间接使用定义本身，则 while(IStackEmpty(S》(∥t钱s非空 称它们是递归的，或递归定义的 i=Pop(S); printf(“%d”,店 时间复杂度O(logN门 5
2014/4/7 5 § 3.2 队列 DataType DeQueue (LinkQueue &Q) { if ( QEmpty(Q) ) Error (“underflow”); //下溢 p = Q.front; // 指向队头 x = p->data; 25 Q.front = p->next; // 队头摘下 if (Q.rear == p) // 原队中只有一个结点，删去后队变空 Q.rear = NULL; free (p) ; return x; } § 3.3 栈和队列的应用 § 3.3.1 栈的应用 1.数据转换 问题： 一非负十进制整数N 基为B的B进制数 例： 26 规律： （3.1） 其中 表示B进制数的第 i 位数字 十进制数N可用长度为 位B进制数表示为 bi §3.3.1 栈的应用 如何确定 ？ 令 ，则（3.1）式为： （3.2） (3.2)式整除B，则余数为 ，商为括号内的和式。故 (3.2)式 可表达为： 27 // “/”为整除 算法思想： ① 模除求余数： ② 整除求商：N/B，令此为新的N，重复①求 ，反复至某N为0时结束 上述过程依次求出的B进制各位为(从低位至高位): 用栈保存，退栈输出 即为所求。 § 3.3.1 栈的应用 例如： 28 § 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 入栈 29 N=N/B; } while( !StackEmpty(S)) { // 栈S非空 i = Pop(S); printf(“%d”,i); } } 时间复杂度 § 3.3.1 栈的应用 2.栈与递归 递归是一种强有力的数学工具，可使问 题的描述和求解变得简洁与清晰 递归：若一函数、过程或数据结构定义 30 递归：若 函数、过程或数据结构定义 的内部又直接或间接使用定义本身，则 称它们是递归的，或递归定义的