(4)线性表的新结点插入顺序存储线性表的插入:, e7 {, F1 a, L0 O/ G
设线性表结点的类型为整型,插入之前有n个结点,把值为x的新结点插在线性表的第i(0≤i≤n)个位置上。完成插入主要有以下几个步骤:; q- o2 _/ S% _9 Y; g9 q8 o
检查插入要求的有关参数的合理性;, O- w/ D9 O( t9 k' s2 V1 H
把原来第n-1个结点至第i个结点依次往后移一个数组元素位置;
. a. A& |# x( @/ T把新结点放在第i个位置上;# e# S! E3 C! J7 z7 [
修正线性表的结点个数。
: K1 T* J7 O. D& `, d9 ~(5)栈
9 t$ }5 ?7 }9 D) t- f5 m! T3 E堆栈的工作原理是采用后进先出(LIFO)技术,栈顶由中央处理器中的堆栈指示器(SP)指出。在执行PUSH操作中SP减量,而在POP操作中SP增量。( S8 H' O% o* S3 w6 e p* K
下面从数据结构的角度,进一步说明堆栈的基本概念与操作。需要说明的是,其工作原理与前面所介绍的是一致的,不同的是脱离了硬件背景,例如,栈顶指针不是中央处理器的某个寄存器的内容,而是一个抽象的数据结构。来源:www..com- f- R N# o: Q/ S
栈是一种特殊的线性表,这种线性表只能在固定的一端进行插入和删除操作。允许插入和删除的一端称为栈顶,另一端称为栈底。一个新元素只能从栈顶一端进入,删除时,只能删除栈顶的元素,即刚刚被插入的元素。由于元素是按后进先出的次序入栈和出栈的,所以栈又称后进先出表(Last In First Out),简称LIFO表。栈的基本操作有:
; p: A: R4 |2 \( b①create(s) 建立一个空栈s。1 I# C% X% k, ^5 B' v1 L
②empty(s) 测试栈是否为空栈。, |3 r! h% x9 ^ g3 V6 t A
③full(s) 测试栈是否满。
2 o# e6 @" ]# N# X, h+ D& Q- v④push(x,s) 将元素x插入栈s的栈顶。* K% a5 ]- F2 k1 G' \# d
⑤top(s) 取栈顶元素。2 ^8 s+ S' Q- O
⑥pop(s) 删除栈顶元素。* b6 q. d2 s( W0 k
由于栈是一种特殊的线性表,栈的各种操 |