[工学]数据结构 02堆栈与递归队列.ppt

1.3 堆栈链式表示和实现 堆栈的链式表示：用一组任意的存储单元存储线性表的数据元素（与线性表的链接存储结构相同，此时表头指针为栈顶指针） 无栈满问题，空间可扩充 插入和删除仅在栈顶处执行 链式栈的栈顶在链头 堆栈结点的定义： int datatype; struct s_node { datatype data; s_node *next; }; 入栈操作的实现 ① 建立新节点 ② 向新节点中添入内容 ③ 使新节点指向栈顶 ④ 栈顶指针指向新节点 出栈操作的实现 ① 判断栈是否为空 ② 用一个指针p存储栈顶指针，并将值赋给一变量 ③ 栈顶指针指向它的下一个节点 ④释放指针p 1.5 堆栈和递归的实现 递归的定义：若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 在以下三种情况下，常常用到递归方法： 定义是递归的 数据结构是递归的 问题的解法是递归的 1.5.1 定义是递归的 例如，阶乘函数 求解阶乘函数的递归算法 long Factorial ( long n ) { if ( n == 0 ) return 1; else return n*Factorial (n-1); } 求解阶乘 n! 的过程 1.5.2 数据结构是递归的 例如，单链表结构 例如，树结构 1.5.3 问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题 1.5.4 汉诺塔问题的解决 #include stdio.h #include conio.h int counter; /*计数器变量*/ void Hanoi(char From,char To,char Auxiliary,int N)//A -C，B辅助 { if(N==1) //递归结束条件 { counter++; printf(Step %d:,counter); printf(Move disk 1 from peg-%c to peg-%c.\n,From,To); } else { //递归执行体 Hanoi(From,Auxiliary,To,N-1);//A-B, C辅助 counter++; printf(Step %d:,counter); printf(Move disk %d from peg-%c to peg-%c.\n,N,From,To); Hanoi(Auxiliary,To,From,N-1); //B-C,A辅助 } } 1.6 队列的类型定义 只允许在一端删除，在另一端插入的线性表。 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特点： 先进先出（FIFO） First In First Out 队列的基本操作 初始化（构造一个空队列）(initQueue) 清空队列(setNull) 判断队列是否为空(isEmpty) 队列的长度(queueLength) 获取队头元素(getHead) 元素入队(addQueue) 元素出队(deleteQueue) 遍历队列各元素(traverse) 1.7 队列的顺序表示和实现 队列的顺序表示：用一个数组来顺序存储队列中的所有元素，用两个整型变量存储队头元素和队尾元素 队列的顺序定义为： int datatype; //假定队列元素的类型为整型 #define maxsize 1024 //假定队列的最大长度为1024 struct Queue { datatype queue[maxsize]; int front; int rear; }; 队列的顺序存储结构 1.存储方式:同一般线性表的顺序存储结构完全相同.但是由于在两端操作,设两个指示器,(rear和front)分别指示队列的尾和首. 特别约定头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一位置! 空队列:rear=front=0 入队:rear=rear+1 出队:front=front+1 队列空:front=rear E D C B A E J I H G F Q.rear Q.front ABCDE相继入队列 Q.Rear Q.front (a)空队列 0 1 2 3 Q.rear Q.rear Q.front Q.front ABCD相继被删除 FGHIJ相继入队列 E被删除 特点:简单,方便,但易产生假溢出 可以看出:当入队一个元素时,可能会出现假溢出现象即: