return FALSE;} s=p;
p->prior->next=p->next; /*图中步骤①*/ p->next->prior=p->prior; /*图中步骤②*/ free(s);
return TRUE;}
P32【算法2.10 多项式相加】
struct poly *add_poly(struct poly *Ah,struct poly *Bh) {struct poly *qa,*qb,*s,*r,*Ch;
qa=Ah->next;qb=Bh->next; /*qa和qb分别指向两个链表的第一结点*/ r=qa;Ch=Ah; /*将链表Ah作为相加后的和链表*/ while(qa!=NULL&&qb!=NULL) /*两链表均非空*/ { if (qa->exp==qb->exp) /*两者指数值相等*/ {x=qa->coef+qb->coef; if(x!=0)
{ qa->coef=x;r->next=qa;r=qa; s=qb++;free(s);qa++;
} /*相加后系数不为零时*/
else {s=qa++;free(s);s=qb++;free(s);} /*相加后系数为零时*/ }
else if(qa->exp
if(qa==NULL) r->next=qb;
else r->next=qa; /*链接多项式Ah或Bh中的剩余结点*/ return (Ch); }
第三章 栈和队列
P35相应的C语言函数是： float fact(int n) {float s;
if (n= =0||n= =1) s=1; else s=n*fact(n-1); return (s); }
P38用C语言定义的顺序存储结构的栈如下： # define MAXNUM <最大元素数> typedef struct {
Elemtype stack[MAXNUM]; int top; } sqstack;
P39【算法3.1 栈的初始化】 int initStack(sqstack *s)
{/*创建一个空栈由指针S指出*/
if ((s=(sqstack*)malloc(sizeof(sqstack)))= =NULL) return FALSE; s->top= -1; return TRUE; }
P39【算法3.2 入栈操作】 int push(sqstack *s, Elemtype x)
{/*将元素x插入到栈s中，作为s的新栈顶*/ if(s->top>=MAXNUM-1) return FALSE; /*栈满*/ s->top++;
s->stack[s->top]=x; return TRUE; }
P39【算法3.3 出栈操作】 Elemtype pop(sqstack *s)
{/*若栈s不为空，则删除栈顶元素*/ Elemtype x;
if(s->top<0) return NULL; /*栈空*/ x=s->stack[s->top]; s->top--; return x; }
P39【算法3.4 取栈顶元素】 Elemtype getTop(sqstack *s)
{/*若栈s不为空，则返回栈顶元素*/ if(s->top<0) return NULL; /*栈空*/ return (s->stack[s->top]); }
P40【算法3.5 判栈空操作】 int Empty(sqstack *s)
{/*栈s为空时，返回为TRUE；非空时，返回为FALSE*/ if(s->top<0) return TRUE; return FALSE; }
P40【算法3.6 栈置空操作】 void setEmpty(sqstack *s)
{/*将栈s的栈顶指针top，置为-1*/
s->top= -1; }
P40 C语言定义的这种两栈共享邻接空间的结构如下： Typedef struct {
Elemtype stack[MAXNUM];
int lefttop; /*左栈栈顶位置指示器*/ int righttop; /*右栈栈顶位置指示器*/ } dupsqstack;
P41【算法3.7 共享栈的初始化】 int initDupStack(dupsqstack *s)
{/*创建两个共享邻接空间的空栈由指针S指出*/
if (s=(dupsqstack*)malloc(sizeof(dupsqstack)))= =NULL) return FALSE; s->lefttop= -1;
s->righttop=MAXNUM; return TRUE; }
P41【算法3.8 共享栈的入栈操作】
int pushDupStack(dupsqstack *s,char status,Elemtype x)
{*把数据元素x压入左栈（status='L'）或右栈（status='R'）*/ if(s->lefttop+1= =s->righttop) return FALSE; /*栈满*/ if(status='L') s->stack[++s->lefttop]=x; /*左栈进栈*/ else if(status='R') s->stack[--s->righttop]=x; /*右栈进栈*/ else return FALSE; /*参数错误*/ return TRUE; }
P42【算法3.9 共享栈的出栈操作】
Elemtype popDupStack(dupsqstack *s,char status)
{/*从左栈（status='L'）或右栈（status='R'）退出栈顶元素*/ if(status= ='L') { if (s->lefttop<0)
return NULL; /*左栈为空*/
else return (s->stack[s->lefttop--]); /*左栈出栈*/ }
else if(status= ='R')
{ if (s->righttop>MAXNUM-1) return NULL; /*右栈为空*/
else return (s->stack[s->righttop++]); /*右栈出栈*/ }
else return NULL; /*参数错误*/
}
P42链栈的C语言定义为： typedef struct Stacknode {
Elemtype data;
Struct Stacknode *next; }slStacktype;
P43【算法3.10 单个链栈的入栈操作】 int pushLstack(slStacktype *top,Elemtype x) {/*将元素x压入链栈top中*/ slStacktype *p;
if((p=(slStacktype *)malloc(sizeof(slStacktype)))= =NULL) return FALSE; /*申请一个结点*/
p->data=x; p->next=top; top=p; return TRUE; }
P43【算法3.11 单个链栈的出栈操作】 Elemtype popLstack(slStacktype *top) {/*从链栈top中删除栈顶元素*/ slStacktype *p; Elemtype x;
if (top= =NULL) return NULL; /*空栈*/ p=top; top=top->next; x=p->data;free(p);return x; }
P44【算法3.12 多个链栈的入栈操作】
int pushDupLs(slStacktype *top[M],int i,Elemtype x) {/*将元素x压入链栈top[i]中*/ slStacktype *p;
if((p=(slStacktype *)malloc(sizeof(slStacktype)))= =NULL) return FALSE; /*申请一个结点*/
p->data=x; p->next=top[i]; top[i]=p; return TRUE; }
P44【算法3.13 多个链栈的出栈操作】 Elemtype popDupLs(slStacktype *top[M],int i) {/*从链栈top[i]中删除栈顶元素*/ slStacktype *p; Elemtype x;
if (top[i]= =NULL) return NULL; /*空栈*/ p=top[i]; top[i]=top[i]->next;
x=p->data;free(p);return x; }
P47【算法3.14 中缀表达式变为后缀表达式】 # define MAXNUM 40 # define FALSE 0 # define TRUE 1 #include \#include \#include \typedef struct {
char stack[MAXNUM]; int top; } sqstack;
int initStack(sqstack *s) {/*初始化栈*/ s->top=-1; return TRUE; }
int push(sqstack *s,char x)
{/*将元素x插入到栈s中，作为s的新栈顶*/ if(s->top>=MAXNUM-1) return FALSE; /*栈满*/ s->top++;
s->stack[s->top]=x; return TRUE; }
char pop(sqstack *s)
{/*若栈s不为空，则删除栈顶元素*/ char x;
if(s->top<0) return NULL; /*栈空*/ x=s->stack[s->top]; s->top--; return x; }
char gettop(sqstack *s)
{/*若栈s不为空，则返回栈顶元素*/ if(s->top<0) return NULL; /*栈空*/ return (s->stack[s->top]); }
char precede(char x1,char x2)
{/*比较运算符x1与x2的优先*/ char result='<'; char sting[2]; sting[0]=x2; sting[1]='\\0';