Struct stacknode "next: P43【算法3.10单个链栈的入栈操作】 int pushLstack(slStacktype*top, Elemtype x) {/*将元素x压入链栈top中 if(p=( slStacktype* malloc( sizeof( slStacktype)== NULL) return FALSE,/申请一个结 p->data=x; p->next=top; top=p; return TRU P43【算法3.11单个链栈的出栈操作】 {*从链栈top中删除栈顶元素* s Istacktype "p: if(top==NULL)return NULL, 空栈啊 p-top top=top->next, xeD->data free(p)' retum x, P44【算法3.12多个链栈的入栈操作】 int pushDupLs(sIS* top[M], int i, Elemtype x) {/将元素x压入链栈top[可中 f(p=( slStacktype*) malloc(sizeof( slStacktype)== NULL) return FALSE;/申请一个结点 p->datax; p->next=top]; top[F=p; return TRUE, P44【算法3.13多个链栈的出栈操作】 Elemtype pop DupLs(slstacktype * top[M], int i) {/*从链栈top中删除栈顶元素* sls backtype"p Elemtype if(top[==NULL)return NULL, 空栈* p-top] topl]=top[->next, P47【算法3.14中缀表达式变为后缀表达式】 define MAXNUM 40 define False f define TRUE I #include "stdlib. h' #include"string. h char stack[MAXNUMI top,) sqstack int initstack(sqstack*s) {/初始化栈 return TRUE {/*将元素x插入到栈s中,作为s的新栈项* ifs>top>= MAXNUM-l) return FALSE/栈满 S->stack[s->topIX; return TRUE. har pop(sqstack"s) {/*若栈s不为空,则删除栈顶元素*
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 "stdio.h" #include "stdlib.h" #include "string.h" 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, 栈空* return x. char gettop(sqstack *s) {/若栈s不为空,则返回栈顶元素 if(s->top<o)return NULL 栈空* return(s->stack(s->top); char precede( char xl, char x2) {/比较运算符x1与x2的优先* har sting 2] sting[1=wo if((xI=+xI=.)&&(strstr("+-)# sting)=NULL)II ((xI==*xI==/&&strstr(+-* 1)#", sting)l=NULL川 result> else if(xI=(&&x2=)1=#&&x2==#) result==; else if(xl==)&&x2==CI==#&&x2==)) isqstack"optr: optr(sqstack")malloc(sizeof(sqstack), if(cl=+&&cl=-&&cl=°&&c=&&cl=(&&c!=)y&&c!=#) fcase<: push(optr, c); c=s[++i], break case > y=pop(optr) break; ) i P51用C语言定义的顺序存储结构的队列如下: # define maXnum<最大元素数> typedef struct Elemtype queue[MAXNUMI t front,/队头指示器*/ int rear,/*队尾指示器 P51【算法3.15顺序队列的初始化】 {*创建一个空队列由指针q指出 if(((sqqueue*)malloc(sizeof(sqqueue)))==NULL)return FALSE; q→>rear=1 P52【算法3.16顺序队列的入队列操作】
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'; if (((x1=='+'||x1=='-')&&(strstr("+-)#",sting)!=NULL))|| ((x1=='*'||x1=='/')&&strstr("+-*/)#",sting)!=NULL)|| (x1==')'&&strstr("+-*/)#",sting)!=NULL)) {result='>';} else if(x1=='('&&x2==')'||x1=='#'&&x2=='#') {result='=';} else if (x1==')'&&x2=='('||x1=='#'&&x2==')') {result=' ';} return result; } main() {sqstack *optr; char s[80],c,y; int i=0; optr=(sqstack *)malloc(sizeof(sqstack)); gets(s); initStack(optr); push(optr,'#'); c=s[i]; while(c!='#'||gettop(optr)!='#') {if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='('&&c!=')'&&c!='#') {printf("%c",c);c=s[++i]; if(c=='\0') break; } else switch (precede(gettop(optr),c)) {case '<':{push(optr,c);c=s[++i];break;} case '=':{pop(optr);c=s[++i];break; } case '>':{y=pop(optr); printf("%c",y); break;}} } printf("%c",'#'); } P51 用 C 语言定义的顺序存储结构的队列如下： # define MAXNUM <最大元素数> typedef struct { Elemtype queue[MAXNUM]; int front; /*队头指示器*/ int rear; /*队尾指示器*/ } sqqueue; P51【算法 3.15 顺序队列的初始化】 int initQueue(sqqueue *q) {/*创建一个空队列由指针 q 指出*/ if ((q=(sqqueue*)malloc(sizeof(sqqueue)))= =NULL) return FALSE; q->front= -1; q->rear=-1; return TRUE; } P52【算法 3.16 顺序队列的入队列操作】 int append(sqqueue *q,Elemtype x)
{/*将元素ⅹ插入到队列q中,作为q的新队尾 ifq>rear>= MAXNUM-) return False,队列满* q->queue(q->rear]=x; eturn TRUE, P52【算法3.17顺序队列的出队列操作】 Elemtype delete( sqqueue *q) {*若队列q不为空,则返回队头元素* if(q->rear=q->front)return NULL; 队列空* return x. P52【算法3.18顺序队列的取头元素操作】 {/*若队列q不为空,则返回队头元素* if(q->rear==q->front)return NULL, 队列空* return(q->queue(s->front+ID) P52【算法3.19顺序队列的非空判断操作】 {/队列q为空时,返回TRUE;否则返回 FALSE* if(q->rear=q-front)return TRUE; return FALSE, P53【算法3.20顺序队列的求长度操作】 int length(sqqueue "q) {/返回队列q的元素个数* P54用C语言定义循环队列结构如下 typedef struct f Elemtype queue[ MAXNUM nt front:/队头指示器*/ Int rear,/队尾指示器* ints;/队列标志位 queue, P54【算法3.21循环队列的初始化】 int initQueue(queue*q) {*创建一个空队列由指针q指出 if ((q=queue*)malloc(sizeof queue))) =NULL)return FALSE; q->front= MAXNUM; q->rearMAXNUM q>=0 置队列空* P55【算法322循环队列的入队列操作 int append(queue*q, Elemtype x) {/将元素x插入到队列q中,作为q的新队尾 if(( g->s==1)&&(q->front=q->rear))return FALSe; 队列满* if(q->rear=MAXNUM)q->rear=0 置队列非 P55【算法3.23循环队列的出队列操作】 Elemtype delete( queue *q) {/若队列q不为空,则返回队头元素* if(q->s==0)retrun NULL, 队列为空
{/*将元素 x 插入到队列 q 中，作为 q 的新队尾*/ if(q->rear>=MAXNUM-1) return FALSE; /*队列满*/ q->rear++; q->queue[q->rear]=x; return TRUE; } P52【算法 3.17 顺序队列的出队列操作】 Elemtype delete(sqqueue *q) {/*若队列 q 不为空，则返回队头元素*/ Elemtype x; if(q->rear= =q->front) return NULL; /*队列空*/ x=q->queue[++q->front]; return x; } P52【算法 3.18 顺序队列的取头元素操作】 Elemtype getHead(sqqueue *q) {/*若队列 q 不为空，则返回队头元素*/ if(q->rear= =q->front) return NULL; /*队列空*/ return (q->queue[s->front+1]); } P52【算法 3.19 顺序队列的非空判断操作】 int Empty(sqqueue *q) {/*队列 q 为空时，返回 TRUE；否则返回 FALSE*/ if (q->rear= =q->front) return TRUE; return FALSE; } P53【算法 3.20 顺序队列的求长度操作】 int length(sqqueue *q) {/*返回队列 q 的元素个数*/ return(q->rear-q->front); } P54 用 C 语言定义循环队列结构如下： typedef struct {Elemtype queue[MAXNUM]; int front; /*队头指示器*/ int rear; /*队尾指示器*/ int s; /*队列标志位*/ }qqueue; P54【算法 3.21 循环队列的初始化】 int initQueue(qqueue *q) {/*创建一个空队列由指针 q 指出*/ if ((q=(qqueue*)malloc(sizeof(qqueue)))= =NULL) return FALSE; q->front= MAXNUM; q->rear=MAXNUM; q->s=0; /*置队列空*/ return TRUE; } P55【算法 3.22 循环队列的入队列操作】 int append(qqueue *q,Elemtype x) {/*将元素 x 插入到队列 q 中，作为 q 的新队尾*/ if (( q->s= =1)&&(q->front= =q->rear)) return FALSE; /*队列满*/ q->rear++; if (q->rear= =MAXNUM) q->rear=0; q->queue[q->rear]=x; q->s=1; /*置队列非空*/ return TRUE; } P55【算法 3.23 循环队列的出队列操作】 Elemtype delete(qqueue *q) {/*若队列 q 不为空，则返回队头元素*/ Elemtype x; if (q->s= =0) retrun NULL; /*队列为空*/ q->front++;
if(q->front==MAXNUM)q->front=0; xeq->queue[q->front if (q->front==q->rear)q->s=0; /置队列空* return P56用C语言定义链队列结构如下: typedef struct Qnode f Elemtype data struct Qnode *next Qnodetype,伸定义队列的结点啊 typedef struct Qnodetype·font;/头指针* Qnodetype*rear,/尾指针* P56【算法3.24链队列的初始化】 nt in {*创建一个空链队列q* ((q-front=(Qnodety pe")malloc(sizeof( Qnodetype)))==NULL)return FALSE; q->rear=q->front q->front->nextNULL return TRUE; }P56【算法3.25链队列的入队列操作】 int Lappend (Queue*q, Elemtype x) {/*将元素x插入到链队列q中,作为q的新队尾* Qnodetype *p: if(p=(Qnodetype*)malloc(sizeof( Qnodetype)))==NULL) return FALSE; p->next=NULL /置新结点的指针为空 将链队列中最后一个结点的指针指向新结点考 将队尾指向新结点 return TRUE. P57【算法3.26链队列的出队列操作】 Elemtype Delete(Queue * q) {γ*若链队列q不为空,则删除队头元素,返回其元素值 Qnodetype *p; if( q->front->next =NULL)return NULL, 空队列 P=q->front->next 取队头考 *删除队头结点* eep) return x. 第四章串 P62用字符数组存放字符串时,其结构用C语言定义如下 # define MAXNUm<允许的最大的字符数> typedef struct i char str[MAXNUM] int length;,/串长度*/ stringtype,/串类型定义 P62用链表存放字符串时,其结构用C语言定义如下: typedef struct node char str: struct node·next; i slstrtype P63用块链存放字符串时,其结构用C语言定义如下: typedef struct node char str[4]: struct node·next i slstrtype P63用堆存放字符串时,其结构用C语言定义如下
if (q->front= =MAXNUM) q->front=0; x=q->queue[q->front]; if (q->front = =q->rear) q->s=0; /*置队列空*/ return x; } P56 用 C 语言定义链队列结构如下： typedef struct Qnode {Elemtype data; struct Qnode *next; }Qnodetype; /*定义队列的结点*/ typedef struct { Qnodetype *front;/*头指针*/ Qnodetype *rear; /*尾指针*/ }Lqueue; P56【算法 3.24 链队列的初始化】 int initLqueue(Lqueue *q) {/*创建一个空链队列 q*/ if ((q->front=(Qnodetype*)malloc(sizeof(Qnodetype)))= =NULL) return FALSE; q->rear=q->front; q->front->next=NULL; return TRUE; }P56【算法 3.25 链队列的入队列操作】 int Lappend(Lqueue *q,Elemtype x) {/*将元素 x 插入到链队列 q 中，作为 q 的新队尾*/ Qnodetype *p; if ((p=(Qnodetype*)malloc(sizeof(Qnodetype)))= =NULL) return FALSE; p->data=x; p->next=NULL; /*置新结点的指针为空*/ q->rear->next=p; /*将链队列中最后一个结点的指针指向新结点*/ q->rear=p; /*将队尾指向新结点*/ return TRUE; } P57【算法 3.26 链队列的出队列操作】 Elemtype Ldelete(Lqueue *q) {/*若链队列 q 不为空，则删除队头元素，返回其元素值*/ Elemtype x; Qnodetype *p; if(q->front->next= =NULL) return NULL; /*空队列*/ P=q->front->next; /*取队头*/ q->front->next=p->next; /*删除队头结点*/ x=p->data; free(p); return x; } 第四章 串 P62 用字符数组存放字符串时，其结构用 C 语言定义如下： #define MAXNUM <允许的最大的字符数> typedef struct { char str[MAXNUM]; int length; /*串长度*/ } stringtype; /* 串类型定义*/ P62 用链表存放字符串时，其结构用 C 语言定义如下： typedef struct node{ char str; struct node *next; } slstrtype; P63 用块链存放字符串时，其结构用 C 语言定义如下： typedef struct node{ char str[4]; struct node *next; } slstrtype; P63 用堆存放字符串时，其结构用 C 语言定义如下：
typedef struct! char *str: It length; i HSstrtype P65C语言中用字符数组存储字符串时,结构定义如下 #define maXnum 80 int length;/串长度 P65【算法41在静态存储方式中求子串】 int substr(stringtype sl, stringtype *s2, int m, int n fint j, k;=sllength; ifm<=Om>jn<0){(*s2)str[oj=0(*s2) length=0 return FALSE;}/*参数错误* k=strlen(&sl str[m-1D; 求子串的长度 if(n>k)(s2). length=k else (*s2). length=n; /置子串的串长* for(F0 j<=(s2). length: j++, m++)(s2 ).strDFslstr[m-1]; (s2)st=; /置结束标记 eturn TRUE, P66假设链表中每个结点仅存放一个字符,则单链表定义如下 typeset struct node har str: struct node·next i slstrtype, P66【算法42在链式存储方式中求子串】 It substr(slstrtype sl, slstrtype*s2, int m, int n) islstrtype"p, q, *V: for( eight=0;p> nextI=NULL P=p>next) lengthl++;/*求主串和串长喇 if(m<=omlengthl n<)(s2=NULL return FALSE, 陣参数错误* p=sl.next, (=0m++)p= 找到子串和起始位置* s2=(slstrtype *)mall of(slstrtype)) 陣分配子串和第一个结点考 for(0;jn&&p->next!=NULL ++ 陣建立子串 q=(slstrtype * )malloc(sizeof(slstrtype)) q->str\0: q->next=NULL, 置子串和尾结点* return TRUE. P67堆存储结构用C语言定义为: typeset struct( char *str: length; 1 HSstrtype P67【算法43共享法求子串】 substr(HSstrtypesl, HSstrtype"s2, int m, int n) f int j, k; if(m<=Om>llnso)(s2->length=0 return FALSE, 参数错误* k=strlen(sl str+m); /主串第m个位置开始之后的串长制 if(n>k)s2->length=k; else s2->length=n 置子串的串长考 s2->strs. str+I 置子串的串首地址 return TRUE
typedef struct{ char *str; int length; } HSstrtype; P65 C 语言中用字符数组存储字符串时，结构定义如下： #define MAXNUM 80 typedef struct { char str[MAXNUM]; int length; /*串长度*/ } stringtype; /* 串类型定义*/ P65【算法 4.1 在静态存储方式中求子串】 int substr(stringtype s1,stringtype * s2,int m,int n) {int j,k;j=s1.length; if(m<=0||m>j||n<0) {(*s2).str[0]='\0';(*s2).length=0;return FALSE; } /*参数错误*/ k=strlen(&s1.str[m-1]) ; /*求子串的长度*/ if (n>k) (*s2).length=k; else (*s2).length=n; /*置子串的串长*/ for(j=0;j<=(*s2).length;j++,m++) (*s2).str[j]=s1.str[m-1]; (*s2).str[j]=’\0’; /*置结束标记*/ return TRUE; } P66 假设链表中每个结点仅存放一个字符，则单链表定义如下 typedet struct node{ char str; struct node *next; } slstrtype; P66【算法 4.2 在链式存储方式中求子串】 int substr(slstrtype s1,slstrtype *s2,int m,int n) {slstrtype *p,*q,*v; int length1,j; p=&s1; for(lenght1=0;p->next!=NULL;p=p->next) length1++; /*求主串和串长*/ if(m<=0||m>length1||n<0) {s2=NULL;return FALSE;} /*参数错误*/ p=s1.next; for(j=0;j<m;j++) p=p->next; /*找到子串和起始位置*/ s2=(slstrtype *)malloc(sizeof(slstrtype)); /*分配子串和第一个结点*/ v=s2;q=v; for(j=0;j<n&&p->next!=NULL;j++) /*建立子串*/ { q->str=p->str; p=p->next; q=(slstrtype *)malloc(sizeof(slstrtype)); v->next=q; v=q; } q->str=’\0’;q->next=NULL; /*置子串和尾结点*/ return TRUE; } P67 堆存储结构用 C 语言定义为： typedet struct{ char *str; int length; } HSstrtype; P67【算法 4.3 共享法求子串】 int substr(HSstrtype s1,HSstrtype *s2,int m,int n) { int j,k; j=s1.length; if(m<=0||m>j||n<0) {s2->length=0;return FALSE;} /*参数错误*/ k=strlen(s1.str+m); /*主串第 m 个位置开始之后的串长*/ if (n>k) s2->length=k; else s2->length=n; /*置子串的串长*/ s2->str=s1.str+m; /*置子串的串首地址 return TRUE; }