数据结构 s->prior-p->pnor; p→>pnor>next=s; s>nextp; p->pnor-s retum (1); 算法29 (2)删除 在双向链表中删除一个结点相应的指针变化情况如图215所示。 t山 图215双向链表的删除 由图示可见,要删除p结点的步骤应为 p->prior->nextp->next; (2 p>next->priorp->prior; 在双向循环链表中剽除一个结点的算法描述见算法210 int DuLinkDelete( DuLinkList *1, int i, elemtype *s) {"在双向循环链表L中删除第i个数据元素 DuLinkList 'p: int j; p=L;j=0; whil(p>1ext!NUUL改&j≤) (p=p->ne t; j++) if( p->next==NULL, return(0); p>pror-next p->next; p->next->pnor-p->prior; s=p->data; free(p) return D) 算法210 2 24限定性线性表及其应用 栈和队列是两种重要的线性结构,是线性表的特殊表现形式。栈和队列与线性表在数据 结构上完全相同,其特殊性在于栈和队列的基本操作是线性表操作的子集,即它们是操作受 限的线性表,又称为限定性线性表
第2章线性表 24.1栈 1.栈的定义 栈(sack)是限定仅在表的一端进行插入或删除操作的线性表。通常把允许插入和删除 操作的一端称为栈顶(top),而另一端称为栈底(botm)。表为空时称为空栈。在栈上的主 要运算是插入和删除。栈的插入操作称为进栈或入栈,栈的删除操作称为退栈或出栈。栈顶 的位置随元素的插入和删除而变化。如图216所示的栈中,a1是栈底 出栈 进栈 元素,an是栈顶元素。栈中元素按a,a2,…,an的顺序进栈,每一次入 栈的元素都在原栈顶元素之上,并成为新的栈顶元素,每一次出栈的栈顶 元素总是当前的栈顶元素。所以出栈的顺序是anam,…,a。可见, 栈的修改是按后进先出的原则进行的。因此,栈又称为“后进先出”(last in first out)的线性表,简称LIFO表。日常生活中一叠盘子的取放是 栈的典型的例子,盘子总是放在最上面,取盘子时总是从最上面的一栈底a 叠开始 图216栈的示意图 2.栈的存储结构与运算 栈是操作受限的线性表,因此栈也有两种存储结构。 (1)顺序栈 顺序栈即栈的顺序存储结构,是指利用一组地址连续的存储单元依次存放从栈底到栈顶 的数据元素。在C语言中用一维数组实现栈的顺序存储,同时附设栈顶指示器top指示栈顶 元素在顺序栈中的位置。于是顺序栈可作如下描述: define maxnum100∥定义顺序栈最大容量为100 typedef struct i elemtype stack[maxnum) p SqStack; 由于C语言中数组下标从0开始,于是约定top指向实际栈顶元素后面的一个空位置, 即新数据元素将插入的位置。如图2.17所示栈的修改状况及栈顶指针的变化情况。 2 2 top 2 p116 010 010 010 (a)栈空 (b)10进栈 c)16进栈 d)16退栈 图2.7顺序栈的进栈与退栈示意图 栈的初始状态下top=0,表示是空栈,栈中无数据元素。当数据元素10进栈时,先置 stack[top}=-10,再将tp加1;退栈时则先将top减1,再取出栈顶元素。由于一维数组限定 了栈的最大容量,当top= maxnum时栈已满,若再有数据元素进栈,栈将溢出,称为“上溢”, 这是一个错误状态。反之,当top=0时栈已空,再作退栈运算,栈将溢出,称为“下溢 这也是一个错误状态,通常被用来作为控制转移的条件
数据结构 栈的基本操作有:初始化栈、进栈、出栈、取栈顶元素和判栈空等 ①初始化栈。算法描述见算法2.1 void InitStack( SqStack s) ∥构造一个空栈s s->top=0; 算法211 ②进栈。算法描述见算法2.12。 int push( SqStack 's, elemtype x) ∥数据元素x插入顺序栈s中成为新的栈顶元素 if(s->top==maxnum f printf ("over flow!"); return(0); s->stack[s->top]x; s->toptt return(); 算法212 ③出栈。算法描述见算法2.13。 int pop( SqStack*s, elemtype p) W∥顺序栈s的栈顶元素退栈,用◆p保存其值 f printf("stack empty! ") return(O); s>top--, "p-s->stack[s->top retum (D) 算法213 ④取栈顶元素。算法描述见算法214。 elemtype GetTop( Sqstacks) {获取顺序栈s的栈顶元素 if (s->top==0)return(0); else retum(s->stack[--s->top]); 算法214
第2章线性表 ⑤判栈空。算法描述见算法215。 int Stack Empty( SqStack 's) {判别顺序栈s是否为空栈 f (s->top==0) return(D) return(0) 算法215 对于进栈时的“上溢”现象应设法避免。在实际应用中,若一个程序使用多个栈,一个 栈发生“上溢”其他栈可能还留有很多空间。为了充分利用各个栈的空间,尽量避免产生“上 溢”,可采用多个栈共享空间的方法,即给多个栈分配一个足够大的数组空间,利用栈的动态 性,使其存储空间互相补充。 为简单起见,下面讨论两个栈共享存储空间的方法。给两个栈分配一个长度为M的数组 空间,将两个栈的栈底分别设在存储空闾約两端,栈顶向存储空间的中间伸展(如图218所 示)。这样两个栈之间可以做到互补余泱,伯得某个栈实际可利用的最大空间大于M2。这时 只有两个栈的栈顶相遇时才可能发生“上益”,显然这比两个各有M2存储空间的栈产生“上 溢”的几率要小。这种两栈共享的数给构可描述如下: #define M 500 typedef stuct t elemtype stack[! p[2 3 DuStack; 图218两栈共享空间示意图 为方便起见,在此约定共享空间只剩一个空间(即tp[J=+op[])时认为栈满,如果此 时再向任一栈中插入元素则发生“上溢”现象。下面介绍这种数据结构中的有关算法。 ①初始化栈。算法描述见算法216 void InitDu Stack( DuStack*s) ∥构造两个共享的空栈结构s s->top[0=0; s->top(I]M-1; 算法216 ②进栈。算法描述见算法217
数据结构 int Du Push( DuStack*s, int i, elemtype x 数据元素x插入第i个栈,i01 if(i!=0&&i!=1) f printf ("error! "); if(s->top[OF=s->topl]) f printf ("over flow!"); return(0) s->top=x s>top[]++; retum(1); 算法217 ③出栈。算法描述见算法2.18。 int DuPop( DuStack*s, int i, elemtype 'p) {∥第个栈的栈顶元素退栈,用中保存其值,i0 if(i=0&&i=1) f printf ("error!"); retun(0); if(i==0) f if(s>top[0]==0 i printf ("stack 0 empty!"); return(0); else &s->top[0h-; Fp=s->stack[s->top[OJ] p[l]==M-1) d printf ("stack 1 empty! ") retum