高等學?！獢?shù)據(jù)結構習題答案(編輯修改稿)

　

【文章內(nèi)容簡介】 printf(%d,n%8)。 }}void f(int n) /* 非遞歸算法*/{ InitStack(p)。/*初始化棧*/ do { Push(p,n%8)。 n=n/8。 }while(n)。 while(!Empty(p)) { Pop(p,o)。 printf(%d,o)。 }}7．已知n為大于等于零的整數(shù)，試寫出計算下列遞歸函數(shù)f(n)的遞歸和非遞歸算法。 n+1 當n＝0時 f(n)＝ n*f(n/2) 當n≠0時解：int f(int n)/* 遞歸*/{ if(n==0) return 1。 else return n*f(n/2)。}int f(int n) /* 非遞歸*/{ int stack[MAXLEN][3]。 int top=1,fval。 stack[top][1]=n。/*初值入棧*/ while(n!=0)/*存入所有的n/2*/ { top++。 n/=2。 stack[top][1]=n。 } stack[top][0]=1。 while(top1)/*退棧求值*/ { fval=stack[top][0]。 top。 stack[top][2]=fval。 stack[top][0]=stack[top][1]*stack[top][2]。 } return(stack[top][0])。}8．對于一個具有m個單元的循環(huán)隊列，寫出求隊列中元素個數(shù)的公式。解：(+m)%m9．假設用一個數(shù)組Q[M]來表示隊列，該隊列只設一個隊頭指針front，不設隊尾指針而改設計數(shù)器count用以記錄隊列中元素的個數(shù)。試編寫出相應的置空隊列，入隊列和出隊列的算法。解：typedef struct{ ELEMTP elem[MAXSIZE]。 int front。 /*隊頭*/ int count。 }MySqQueue。void Empty(MySqQueue *Sq)/*置空隊列*/{ Sqfront=0。 Sqcount=0。}int EnQueue(MySqQueue *Sq，ELENTP x)/* 在循環(huán)隊列Sq的尾部插入一個新的元素x */ { if(Sqcount==MAXSIZE) return 1。/*隊列上溢*/ else { Sqcount++。 Sqelem[(Sqfront+Sqcount)%MAXSIZE]=x。 } return 1。}int DelQueue(MySqQueue *Sq，ELEMTP *y)/*刪除循環(huán)隊列Sq的隊頭元素，并存人*y中*/{ if(Sqcount==0) return 1。/*隊列下溢*/ else { Sqfront=(Sqfront+1)%MAXSIZE。 *y=Sqelem[Sqfront]。 Sqcount。 } return 1。}10．假設以帶頭結點的循環(huán)鏈表示列隊，并且只設一個指針指向隊尾元素結點(注意不設頭指針)，試編寫出相應的置空隊列，入隊列和出隊列的算法。解：typedef struct node{ /*結點結構*/ ELEMTP data。 struct node *next。}QNode。typedef struct{ QNone *rear。 /*隊尾指針*/}MyLQueue。void Empty(MyLQueue *Lq)/*置空隊列*/{ if(Lqrear!=NULL)/*循環(huán)隊列為非空*/ { head=Lqrearnext。 while(head!=Lqrear) { p=head。 head=headnext。 free(p)。 } free(head)。 Lqrear=NULL。 } }int EnQueue(MyLQueue *Lq，ELENTP x)/* 在循環(huán)隊列Sq的尾部插入一個新的元素x */ { p=(QNone *)malloc(sizeof(QNone))。 if(p==NULL) return 1。 else { pdata=x。 pnext=NULL 。 if(Lqrear==NULL)/*循環(huán)隊列為空*/ { Lqrear=p。 pnext=p。 } else { head=Lqrearnext。 Lqrearnext=s。 Lqrear=s。 snext=head。 } } return 1。}int DelQueue(MyLQueue *Lq，ELEMTP *y)/*刪除循環(huán)隊列Sq的隊頭元素，并存人*y中*/{ if(Lqrear==NULL)/*隊列下溢*/ return 1。 else { head=Lqrearnext。 if(head==Lqrear)/*只有一個節(jié)點*/ { *y=headdata。 free(head)。 Lqrear=NULL。 } else { *y=headdata。 Lqrearnext=headnext。 free(head)。 } } return 1。}上機實習題1．設計一個算法，檢驗C源程序代碼中的括弧對是否正確配對。要求在某個C源程序文件上對你的算法進行驗正。include typedef struct node{ char data。 struct node *next。}SNode。 SNode * Push(SNode *top , char x){ SNode *p。 p=(SNode *)malloc(sizeof(SNode))。 pdata=x。 pnext=top。 top=p。 return top。}SNode *Pop(SNode *top , char *y, int *flag){ SNode *p。 if(top==NULL) *flag=0。 /*鏈棧已空*/ else { /*出棧*/ p=top。 *y=pdata。 top=pnext。 *flag=1。 } return top。}int main(int argc, char *argv[]){ FILE *fp。 char ch,o。 int flag=1。 SNode *p=NULL。 if(argc!=2) { printf(You forgot to enter the filename\n)。 exit(1)。 } if((fp=fopen(argv[1],r))==NULL) { printf(cannot open file\n)。 exit(1)。 } ch=getc(fp)。 while(ch!=EOF) { if(ch==39。(39。||ch==39。[39。||ch==39。{39。) { printf(Push%c\n,ch)。 p=Push(p,ch)。 } if(ch==39。)39。) { p=Pop(p,amp。o,amp。flag)。 printf():Pop%c,%d\n,o,flag)。 if(flag==0) printf(d lose 39。(39。)。 else switch (o) { case 39。(39。 :break。 case 39。[39。 :printf(lose 39。]39。)。exit(0)。 case 39。{39。 :printf(lose 39。}39。)。exit(0)。 } } if(ch==39。]39。) { p=Pop(p,amp。o,amp。flag)。 printf([:Pop%c,%d\n,o,flag)。 if(flag==0) printf(d lose 39。[39。)。 else switch (o) { case 39。(39。 :printf(lose 39。)39。)。exit(0)。 case 39。[39。 :break。 case 39。{39。 :printf(lose 39。}39。)。exit(0)。 } } if(ch==39。}39。) { p=Pop(p,amp。o,amp。flag)。 printf({:Pop%c,%d\n,o,flag)。 if(flag==0) printf(d lose 39。{39。)。 else switch (o) { case 39。(39。 :printf(lose 39。)39。)。exit(0)。 case 39。[39。 :printf(lose 39。]39。)。exit(0)。 case 39。{39。 :break。 } } ch=getc(fp)。 } p=Pop(p,amp。o,amp。flag)。 if(flag==0) printf(OK)。 while(flag!=0)/*如果棧未空*/ { switch (o) { case 39。(39。 :printf(lose 39。)39。)。break。 case 39。[39。 :printf(lose 39。]39。)。break。 case 39。{39。 :printf(lose 39。}39。)。break。 } p=Pop(p,amp。o,amp。flag)。 } fclose(fp)。 return 0。}2．設計程序，模擬手機的某些短信息功能。功能要求：（1）接受短信息，若超過存儲容量（如最多可存儲20條），自動將最早接受的信息刪除。（2）顯示短信息數(shù)量。（3）逐條顯示短信息（從最新的開始）；（4）刪除其中的任意一條短信息；（5）清除。/*（1）接受短信息，若超過存儲容量（如最多可存儲20條），自動將最早接受的信息刪除。（2）顯示短信息數(shù)量。（3）逐條顯示短信息（從最新的開始）；（4）刪除其中的任意一條短信息；（5）清除。*/include include include define MAXSIZE 20/*存儲容量*/define INFOLEN 100/*信息長度*/typedef struct node{ /*結點結構*/ char Info[INFOLEN]。 struct node *next。 }QNode。typedef struct{ QNode * front。 /*隊頭指針*/ QNode * rear。 /*隊尾指針*/ int count。}MyInfo。MyInfo *Init() /*初始化*/{ MyInfo *p。 QNode *q。 p=(MyInfo *)malloc(sizeof(MyInfo))。 pcount=0。 q=(QNode *)malloc(sizeof(QNode))。 qnext=NULL。 pfront=q。 prear=q。 return p。}int GetNew(MyInfo *Lq)/* 獲得新短信 */ { time_t t。 struct tm *local。 QNode * p。 t=time(NULL)。 local=localtime(amp。t)。/*獲得時間信息，模擬短信內(nèi)容*/ if(Lqcount==MAXSIZE) { Delete(Lq)。 } p=(QNode *)malloc(sizeof(QNode))。 strcpy(pInfo,asctime(local))。 pnext=NULL 。 Lqrearnext=p。 Lqrear=p。 Lqcount++。 return 1。}int Delete(MyInfo *Lq)/*刪除循環(huán)隊列Lq的隊頭元素*/{ QNode * p。 if(Lqfront==Lqrear) ret