中南大学：《数据结构》课程教学资源（试卷习题）习题

第一章绪论 例:计算f=1!+2!+3!+…+n!,用C语言描述 void factorsum (n) int f, w or(i=1:i《=n:i++) for (=l:j(=i; j++) W-W 第二章线性表 Pl6【算法21顺序表的插入】 int Insert(Elemtype ListI, int*num, int i, Elemtype x) {*在顺序表Lis中,·num为表尾元素下标位置,在第i个元素前插入数据元素x,若成功,返回 TRUE,否则返回 FALSE。 f(*num+1) i printf("Error!) 插入位置出错* eturn FALSE, if(num>=MAXNUM-1) return FALSe; j 表已满* for(F*num; j >=i;j--) List[+1FList] 数据元素后移* ListOn /插入x 长度加1· return TRUE; P18【算法22顺序表的删除】 int Delete( Elemtype List, int*num, int i) 在线性表List中,*mum为表尾元素下标位置,删除第i个长度,线性表的长度减1,若成功 则返回TRUE:否则返回 FALSE。* if(i<op*num printi"ror!"), return False,}*删除位置出错!*/ fo(产=计1Jj<=*numj++) List[j-1=List 数据元素前移 (num)- 长度减1。 eturn TRUE, i P19例:将有序线性表La=(2,4,6,79},Lb={1,5,7,8},合并为Lc={1,2,4,5,6,7,78,9}。 void merge( Elemtype La[, Elemtype Lbl, Elemtype **Lc) i int ij, k, int La length, Lb length La length= Length(La) Lb length= Leng th(Lb),/*取表LaLb的长度* 初始化表Lc While(i<=La length&&j<=Lb length i aFget(La, i), b=get(Lb,j; a<b)insert(Lc, ++k, a); ++1; else (insert(Lc, ++k, b): ++; 将La和Lb的元素插入到Lc中考 (<=La length)i aFget(La, i) insert(Lc, ++k, a): i while ( <=lb length)i b=get (La.j), insert(Lc, ++k, b);3j P2I例如:下面定义的结点类型中,数据域包含三个数据项:学号、姓名、成绩 Struct studer i char num[8] 数据域 数据域 数据域 struct student*next/指针域*/

第一章 绪论 例： 计算 f=1！+2！+3！+…+n！，用 C 语言描述。 void factorsum（n） int n； {int i，j； int f，w； f=0； for （i=1；i〈=n；i++） {w=1； for （j=1；j〈=i；j++） w=w*j； f=f+w；} return； } 第二章 线性表 P16【算法 2.1 顺序表的插入】 int Insert(Elemtype List[],int *num,int i,Elemtype x) {/*在顺序表 List[]中，*num 为表尾元素下标位置，在第 i 个元素前插入数据元素 x，若成功，返回 TRUE，否则返回 FALSE。*/ int j; if (i*num+1) {printf(“Error!”); /*插入位置出错*/ return FALSE;} if (*num>=MAXNUM-1) {printf(“overflow!”); return FALSE;} /*表已满*/ for (j=*num;j>=i;j--) List[j+1]=List[j]; /*数据元素后移*/ List[i]=x; /*插入 x*/ (*num)++; /*长度加 1*/ return TRUE;} P18【算法 2.2 顺序表的删除】 int Delete(Elemtype List[],int *num,int i) {/*在线性表 List[]中，*num 为表尾元素下标位置，删除第 i 个长度，线性表的长度减 1，若成功， 则返回 TRUE；否则返回 FALSE。*/ int j; if(i*num) {printf(“Error!”); return FALSE; } /*删除位置出错！*/ for(j=i+1;j<=*num;j++) List[j-1]=List[j]; /*数据元素前移*/ (*num)--; /*长度减 1*/ return TRUE; } P19 例：将有序线性表 La={2,4,6,7,9}，Lb={1,5,7,8}，合并为 Lc={1,2,4,5,6,7,7,8,9}。 void merge(Elemtype La[],Elemtype Lb[],Elemtype **Lc) { int i,j,k; int La_length,Lb_length; i=j=0;k=0; La_length=Length(La);Lb_length=Length(Lb); /*取表 La,Lb 的长度*/ Initiate(Lc); /*初始化表 Lc*/ While (i<=La_length&&j<=Lb_length) { a=get(La,i);b=get(Lb,j); if(a<b) {insert(Lc,++k,a);++i;} else {insert(Lc,++k,b);++j;} } /*将 La 和 Lb 的元素插入到 Lc 中*/ while (i<=La_length) { a=get(La,i);insert(Lc,++k,a);} while (j<=lb_length) { b=get(La,j);insert(Lc,++k,b); } } P21 例如：下面定义的结点类型中，数据域包含三个数据项：学号、姓名、成绩。 Struct student { char num[8]; /*数据域*/ har name[8]; /*数据域*/ int score; /*数据域*/ struct student *next; /*指针域*/}

P21单链表结点结构定义为: Typedef struct sInode struct sInode 'next Inodetype retype P21【算法2.3单链表的初始化】 nt Initiate(sInodetype **h) i if((h=(sInodetype")malloc(sizeof(sInodetype)NULL) return FALSE return TRUE. P22【算法24单链表的后插入】 i s=(slnodetype")malloc(sizeof(sInodety pe) ->datax - >nexts P22【算法2.5单链表的结点插入】 while(q->next!=p)q=q->next retype S->nextp; P23【算法26单链表的前插入】 int insert(sInodetype "h, int 1, Elemtype x) /在链表h中,在第i个数据元素前插入一个数据元素x制 while(p!=NULL&&jnext++;/*寻找第i1个结点*} /*插入位置错误 if(s=(sInodety pe* )malloc(sizeof(slnodetype)=NULL) return FALSE S->dataS; s->nextp-next, -next=s return TRUI P23 面C程序中的功能是,首先建立一个线性链表head={3,5,7,9},其元素值依 次为从键盘输入正整数(以输入一个非正整数为结束);在线性表中值为x的元素前插入 个值为y的数据元素。若值为x的结点不存在,则将y插在表尾 # include“ stdlib. h struct sInode fint data, struct slnode*next /定义结点类型* head=NULL; /置链表空 scanf(“%d”,&d),/输入链表数据元素* ip(struct sInode*)malloc(sizeof(struct sInode); /*F 个新结点 p->data=d if(head=NULL)head=p,/若链表为空,则将头指针指向当前结点p* else q->next=p,链表不为空时,则将新结点链接在最后* qFp,/*将指针q指向链表的最后一个结点 scanf%d”,d)} scanf("%d, %d, &x, &y ) hile(pl=NULL&&(p-> datal=x){q=pp=p->next;}/*查找元素为x的指针*

P21 单链表结点结构定义为： Typedef struct slnode { Elemtype data; struct slnode *next; }slnodetype; slnodetype *p,*q,*s; P21 【算法 2.3 单链表的初始化】 int Initiate(slnodetype * *h) { if((*h=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE; (*h)->next=NULL; return TRUE; } P22 【算法 2.4 单链表的后插入】 { s=(slnodetype*)malloc(sizeof(slnodetype)); s->data=x; s->next=p->next;p->next=s;} P22 【算法 2.5 单链表的结点插入】 {q=head; while(q->next!=p) q=q->next; s=(slnodetype*)malloc(sizeof(slnodetype)); s->data=x; s->next=p; q->next=s;} P23【算法 2.6 单链表的前插入】 int insert(slnodetype *h,int i,Elemtype x) {/*在链表 h 中，在第 i 个数据元素前插入一个数据元素 x */ slnodetype *p,*q,*s; int j=0; p=h; while(p!=NULL&&jnext;j++; /*寻找第 i-1 个结点*/ } if ( j!=i-1) {printf(“Error!”);return FALSE; /*插入位置错误*/} if ((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE; s->data=x; s->next=p->next; q->next=s; return TRUE;} P23 例：下面 C 程序中的功能是，首先建立一个线性链表 head={3，5，7，9}，其元素值依 次为从键盘输入正整数（以输入一个非正整数为结束）；在线性表中值为 x 的元素前插入一 个值为 y 的数据元素。若值为 x 的结点不存在，则将 y 插在表尾。 #include “stdlib.h” #include “stdio.h” struct slnode {int data; struct slnode *next;} /*定义结点类型*/ main() {int x,y,d; struct slnode *head,*p,*q,*s; head=NULL; /*置链表空*/ q=NULL; scanf(“%d”,&d); /*输入链表数据元素*/ while(d>0) {p=(struct slnode*)malloc(sizeof(struct slnode)); /*申请一个新结点*/ p->data=d; p->next=NULL; if(head==NULL) head=p; /*若链表为空，则将头指针指向当前结点 p*/ else q->next=p; /*链表不为空时，则将新结点链接在最后*/ q=p; /*将指针 q 指向链表的最后一个结点*/ scanf(“%d”,&d);} scanf(“%d,%d”,&x,&y); s=(struct slnode*)malloc(sizeof(struct slnode)); s->data=y; q=head;p=q->next; while((p!=NULL)&&(p->data!=x)) {q=p;p=p->next;} /*查找元素为 x 的指针*/ s->next=p;q->next=s; /*插入元素 y*/

P24【算法2.7单链表的删除】 /*在链表h中删除第i个结点* Int, while(p->nextI=NULL&&j nextF=j+1;/寻找第-1个结点p指向其前驱啼 printi"ror!”),*删除位置错误! return FALSE; j nextp>next>next,/删除第i个结点制 es);/*释放被删除结点空间 P25例:假设已有线性链表La,编制算法将该链表逆置 void converse(sInodetype *head) { slnodetype孝p,*q while(p=NULL) head->next=p P27例:将两个循环链表首尾相接。La为第一个循环链表表尾指针,Lb为第二个循环链表 表尾指针。合并后Lb为新链表的尾指针 Void merge(sInodetype *La, slnodetype "Lb) i slnodetype"p; Lb->next La->next, free(p) P29【算法28双向链表的插入】 int insert dul( dInodetype *head, int i, Elemtype x) {/在带头结点的双向链表中第i个位置之前插入元素x* p=head; while(pl=NULL& p=p->ney ++, ifgI=iK prior=p-> pror,/图中步骤①* p> prior->next=s,/图中步骤② s→>next=p,/图中步骤③*/ /*图中步骤 return TRUE; P30【算法29双向链表的删除】 int Delete dl(dInodetype*head, int i) dInodetype’p,*s p=head

} P24【算法 2.7 单链表的删除】 int Delet(slnodetype *h,int i) { /*在链表 h 中删除第 i 个结点*/ slnodetype *p,*s; int j; p=h;j=0; while(p->next!=NULL&&jnext;j=j+1; /*寻找第 i-1 个结点,p 指向其前驱*/} if(j!=i-1) {printf(“Error!”); /*删除位置错误!*/ return FALSE; } s=p->next; p->next=p->next->next; /*删除第 i 个结点*/ free(s); /*释放被删除结点空间*/ return TRUE; } P25 例：假设已有线性链表 La，编制算法将该链表逆置。 void converse(slnodetype *head) {slnodetype *p,*q; p=head->next; head->next=NULL; while(p!=NULL) { q=p->next; p->next=head->next; head->next=p; p=q; } } P27 例：将两个循环链表首尾相接。La 为第一个循环链表表尾指针，Lb 为第二个循环链表 表尾指针。合并后 Lb 为新链表的尾指针。 Void merge(slnodetype *La,slnodetype *Lb) { slnodetype *p; p=La->next; Lb->next= La->next; La->next=p->next; free(p); } P29【算法 2.8 双向链表的插入】 int insert_dul(dlnodetype *head,int i,Elemtype x) {/*在带头结点的双向链表中第 i 个位置之前插入元素 x*/ dlnodetype *p,*s; int j; p=head; j=0; while (p!=NULL&&jnext; j++; } if(j!=i||idata=x; s->prior=p->prior; /*图中步骤①*/ p->prior->next=s; /*图中步骤②*/ s->next=p; /*图中步骤③*/ p->prior=s; /*图中步骤④*/ return TRUE;} P30【算法 2.9 双向链表的删除】 int Delete_dl(dlnodetype *head,int i) { dlnodetype *p,*s; int j; p=head; j=0;

while (pl=nULL&&jnext; +;} iful=ipror>nex=p>next/图中步骤①*/ p>next> prior=p-> prior,/*图中步骤②*/ return TRUE, P32【算法210多项式相加】 struct poly *add poly(struct poly "Ah, struct poly "Bh) istruct poly *qa, *qb, * s, r, Ch qa=Ah> next: qb=Bh->next/qa和qb分别指向两个链表的第一结点 rqa Ch=Ah 件将链表Ah作为相加后的和链表* while(qal=nULL&&qbl=NULL /两链表均非空* i if (qa->exp==qb->exp) 两者指数值相等* fx=qa->coef+qb->coef; i qa->coef=x r->next=qa rqa 相加后系数不为零时 else{s=qa++fes,s=qb++,fees)}陣*相加后系数为零时制 else if(qa->expexp){r->next=qar=qaqa++;}/多项式Ah的指数值小* else (r->next=qb rqb qb++ 3 多项式Bh的指数值小 if(qa=NULL)r->next=qb e r->nextga 链接多项式Ah或Bh中的剩余结点 return(Ch); 第三章栈和队列 P35相应的C语言函数是: oat fact(int n) if(n==|==1)s=1; else s=n’facn-1) P38用C语言定义的顺序存储结构的栈如下 # define maXnum typedef struct i Elemtype stack MAXNUMI P39【算法3.1栈的初始化】 int initStack(sqstack *s) {/*创建一个空栈由指针S指出* if(s=(sqstack*malloc(sizeof(sqstack)F=NULL)return FALSE; return TR P39【算法3.2入栈操作】 int push(sqstack *s, Elemtype x) {将元素x插入到栈s中,作为s的新栈项* fs→>top>= MAXNUM1) return FALSE,/栈满 s->top++; return TRUE. P39【算法3.3出栈操作】 Elemtype pop(sqstack* s) {/*若栈s不为空,则删除栈顶元素

while (p!=NULL&&jnext; j++; } if(j!=i||iprior->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->expexp){ r->next=qa;r=qa;qa++;} /*多项式 Ah 的指数值小*/ else {r->next=qb;r=qb;qb++;} /*多项式 Bh 的指数值小*/ } 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 不为空，则删除栈顶元素*/

if(s->toptopstack[s->top)); P40【算法3.5判栈空操作】 int Empty(sqstack "s) {/栈s为空时,返回为TRUE:非空时,返回为 FALSE if(s->toprighto=MAXNUM P41【算法38共享栈的入栈操作】 x) *把数据元素x压入左栈( status=L)或右栈( status=R')* if(s->leftop+1==s->righttop) return FALSE; 栈满* if(status=L) S->stack[++s->lefttoplx; 左栈进栈制 else if(status=R)s->stack(--s->righttopF=x;右栈进栈*/ else return FALSE; 参数错误 return TRUE. P42【算法3.9共享栈的出栈操作】 Elemtype pop Dup Stack( dupsqstack*s, char status) {/*从左栈( status=L’)或右栈( status=R')退出栈顶元素* if(status==L) i if (s->lefttopstack[s->lefttop--D; 左栈出栈 else if(status==R) i if(s->righttop>MAXNUM-1) return NULL. /右栈为空 else return(s-> stack[s-> righto+]),右栈出栈* else return NULL- /参数错误* P42链栈的C语言定义为

Elemtype x; if(s->topstack[s->top]; s->top--; return x; } P39【算法 3.4 取栈顶元素】 Elemtype getTop(sqstack *s) {/*若栈 s 不为空，则返回栈顶元素*/ if(s->topstack[s->top]); } P40【算法 3.5 判栈空操作】 int Empty(sqstack *s) {/*栈 s 为空时，返回为 TRUE；非空时，返回为 FALSE*/ if(s->toptop= -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->lefttopstack[s->lefttop--]); /*左栈出栈*/ } else if(status= =’R’) { if (s->righttop>MAXNUM-1) return NULL; /*右栈为空*/ else return (s->stack[s->righttop++]); /*右栈出栈*/ } else return NULL; /*参数错误*/ } P42 链栈的 C 语言定义为：

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->toptopstack(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 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->topstack[s->top]; s->top--; return x; } char gettop(sqstack *s) {/*若栈 s 不为空，则返回栈顶元素*/ if(s->topstack[s->top]); } char precede(char x1,char x2) {/*比较运算符 x1 与 x2 的优先*/ char 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 '':{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; ifmjnk)(s2). length=k else (*s2). length=n; /置子串的串长* for(F0 j nextI=NULL P=p>next) lengthl++;/*求主串和串长喇 if(mnext!=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(mllnso)(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(mj||nk) (*s2).length=k; else (*s2).length=n; /*置子串的串长*/ for(j=0;jnext!=NULL;p=p->next) length1++; /*求主串和串长*/ if(mlength1||nnext; /*找到子串和起始位置*/ s2=(slstrtype *)malloc(sizeof(slstrtype)); /*分配子串和第一个结点*/ v=s2;q=v; for(j=0;jnext!=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(mj||nlength=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; }