计算机软件技术基础第三版要领.pptx

线性表及其顺序存储结构;;;;;线性表在顺序存储下的插入运算;;; 线性表在顺序存储下的删除运算 例2.6如图a所示为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素。其删除过程如下： 从第2个元素开始直到最后一个元素，将其中的每一个元素均依次往前移动一个位置，此时线性表的长度变成了7，如图b。 如果再要删除线性表中的第6个元素，则采用类似的方法：将第7个元素往前移动一个位置。此时线性表的长度变成了6，如图c。;;;;;;;;;; ;栈及其应用 1.什么是栈 主程序与子程序之间的调用关系 MAIN SUB1 SUB2 SUB3 SUB4 …… …… …… …… …… CALLSUB1 CALLSUB2 CALLSUB3 CALLSUB4 …… A：…… B：…… C：…… D：…… …… …… …… …… …… …… END RETURN RETURN RETURN RETURN;栈(stack)是限定在一端进行插入与删除的线性表。 允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈是按照“先进后出” (FILO—First In Last Out)或“后进先出” (LIFO—Last In First Out)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。 栈具有记忆作用。 用指针top来指示栈顶的位置，用指针bottom指向栈底。 往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。;2.栈的顺序存储及其运算;top＝0表示栈空；top＝m表示栈满。 建立空栈的顺序存储空间 （即初始化栈的顺序存储空间） //ch2_5.cpp templatetypename T void init_stack(T *S,int m,int *top) { s＝new T[m]； *top＝0； return； } 释放栈的顺序存储空间时 delete s；; (1)入栈运算 入栈运算是指在栈顶位置插入一个新元素。设栈顺序存储空间为S(1:m),栈顶指针为top,入栈元素为x,则入栈操作过程为： ①判断top是否指向S(1:m)的最后一个位置，如果是，则说明栈空间已满，不能进行入栈，即“上溢”错误。算法结束。 ②将top加一。 ③将x插入到top指向的位置。 //ch2_6.cpp templatetypename T { if (*top＝＝m) { printf(Stack－overflow\n)；return；} *top＝*top＋1； s[*top－1]＝x； return； };(2) 退栈运算 退栈运算是指取出栈顶元素并赋给一个指定的变量。设栈顺序存储空间为S(1,m),top指向栈顶。则退栈过程为： ①判断top是否为0，如果是，则栈空，不可能退栈，即“下溢”错误。算法结束。 ②将栈顶元素(top所指元素)赋给指定变量。 ③top减一。 //ch2_7.cpp templatetypename T T pop(T *s,int m,int *top) {T y； if (*top＝＝0) { printf(Stack－underflow\n)；return；} *y＝s[*top－1]； *top＝*top－1；return(y)； };(3) 读栈顶元素 读栈顶元素是指将栈顶元素赋给指定变量。设栈顺序存储空间为S(1,m),top指向栈顶。则读栈顶元素过程为： ①判断top是否为0，如果是，则栈空，读不到栈顶元素。结束。 ②将栈顶元素赋给指定的变量。 //ch2_8.cpp templatetypename T T top(T *s,int m,int *top) {T y if (*top＝＝0) { printf(Stack empty \n)；return；} *y＝s[*top－1]； return(y)； }; 3.顺序栈类 将顺序存储结构下的栈的数据和基本操作(初始化，入栈，退栈，读栈顶元素以及顺序输出栈顶指针与栈中的元素)封装成一