【文章內(nèi)容簡介】 用一個棧來存放運(yùn)算符，當(dāng)遇到運(yùn)算符,就把運(yùn)算符入棧，直到某個適當(dāng)?shù)臅r機(jī)，再讓運(yùn)算符出棧。算法分析：　當(dāng)前掃描到的字符按以下幾種情況分別處理：a) 若當(dāng)前的字符是變量，則立即將它輸出。b) 若當(dāng)前的字符是’(‘，則讓’(‘入棧。c) 若當(dāng)前的字符是運(yùn)算符(‘+’,’‘,’*’,’/’,’^’),則將它的（進(jìn)棧前)優(yōu)先級別與棧頂字符的（棧中）優(yōu)先級別相比較。如果當(dāng)前的運(yùn)算符的優(yōu)先級別小于等于棧頂字符的優(yōu)先級別，那么退出棧頂字符并輸出。這樣的過程一直進(jìn)行到當(dāng)前的運(yùn)算符的優(yōu)先級別大于棧頂字符的為止，然后讓當(dāng)前的運(yùn)算符入棧。d) 若當(dāng)前的字符是’)’，則從棧中依次退出運(yùn)算符并輸出，直到’(‘為止，然后退出’(‘，但不輸出’(‘.e) 若當(dāng)前的字符是’\0’,則從棧中依次退出所有的運(yùn)算符并輸出，直到’$’為止，’$”不退棧，也不輸出。下面給出程序：define MAXN 100int icp(char c){ switch(c) { case 39。^39。:return(4)。 //進(jìn)棧前的運(yùn)算符的優(yōu)先級 case 39。*39。: case 39。/39。:return(2)。 case 39。+39。: case 39。39。:return(1)。 }}int isp(char c){ switch(c) { case 39。^39。:return(3)。 //棧中的運(yùn)算符的優(yōu)先級 case 39。*39。: case 39。/39。:return(2)。 case 39。+39。: case 39。39。:return(1)。 case 39。(39。:return(0)。 case 39。$39。:return(1)。//置于棧底，保證后面的運(yùn)算符能進(jìn)棧 }}int ischar(char c){ if((c=39。A39。amp。amp。c=39。Z39。)||(c=39。a39。amp。amp。c=39。z39。)) return(1)。 else return(0)。}int mid_to_pos(char midexpress[],char posexpress[]){char stack[MAXN],c。 int top,i,j。 stack[0]=39。$39。 top=0。 j=0。 i=0。 c=midexpress[0]。 while(c!=39。\039。) { if(ischar(c)) posexpress[j++]=c。 else switch(c) { case 39。+39。: case 39。39。: case 39。*39。: case 39。/39。: case 39。^39。: while(icp(c)=isp(stack[top])) posexpress[j++]=stack[top]。 stack[++top]=c。 break。 case 39。(39。: stack[++top]=c。 break。 case 39。)39。: while(stack[top]!=39。(39。) posexpress[j++]=stack[top]。 top。 break。 default: return(1)。 } c=midexpress[++i]。 } while(top0) posexpress[j++]=stack[top]。 posexpress[j]=39。\039。 return(0)。}測試報告： void main(){char midexpress[MAXN],posexpress[MAXN],c。 int i,result。 i=0。 printf(\ninput the mid_expresstion:(end with 39。!39。)\n)。 scanf(%c,amp。c)。 while(c!=39。!39。) { midexpress[i++]=c。 scanf(%c,amp。c)。 } midexpress[i]=39。\039。 result=mid_to_pos(midexpress,posexpress)。 if(result==1) printf(convertion fails!\n)。 else { printf(the pos_expresstion is:\n)。 printf(%s,posexpress)。 }}輸入：(a+b*c)^d^(e*f/g)h*i!(輸入以’!’結(jié)尾) 輸出：abc*+def*g/^^hi*輸入：a+b*c/d+e^f^g+h!輸出：abc*d/+efg^^+h+輸入：(a+b)*(c/d)+(e^f)^(g+h)!輸出：ab+cd/*ef^gh+^+1．11 編寫一個統(tǒng)計(jì)給定的線性鏈表的結(jié)點(diǎn)個數(shù)的C函數(shù)。存儲結(jié)構(gòu)：連表的結(jié)點(diǎn)采用：struct node{int data。//關(guān)鍵字的類型自定 struct node *link。}。算發(fā)分析：利用鏈表的性質(zhì)（結(jié)點(diǎn)中的指針指向下一個結(jié)點(diǎn)），逐步向表尾移動，以此計(jì)算出結(jié)點(diǎn)數(shù)。下面給出程序：typedef struct node{int data。 struct node *link。 }NODE。int count(NODE *head){NODE *p。int c=0。p=head。while(p!=NULL){p=plink。 c++。}return(c)。}測試報告：void main(){NODE a[10]。 int i=0。 for(。i9。i++) {a[i].data=i。 a[i].link=amp。a[i+1]。} a[i].data=i。 a[i].link=NULL。 printf(the total amount of the linked node is:%d\n,count(amp。a[0]))。}輸入：|0123456789^輸出：the total amount of the linked node is:101．12 編寫一個將給定的線性鏈表逆轉(zhuǎn)的C函數(shù)，只允許改變結(jié)點(diǎn)的指針值，不允許移動結(jié)點(diǎn)值。算法如下：(1) 置P為鏈表首址，R,Q為空；(2) 若P為空返回NULL；算法結(jié)束，轉(zhuǎn)（5），否則轉(zhuǎn)（3）；(3) 若鏈表只有一個結(jié)點(diǎn)，轉(zhuǎn)（5），否則轉(zhuǎn)（4）；(4) R=P,P=PLINK,RLINK=Q,置Q=R,若PLINK為空，轉(zhuǎn)（5），否則轉(zhuǎn)（4）；(5) PLINK=R,返回P,算法結(jié)束。源程序如下：include typedef struct node{ int data。 struct node* link。 }NODE。 NODE* tranfer(head) NODE *head。 { NODE *p,*q,*r。 p=head。 r=q=NULL。 if(head==NULL) return(NULL)。 if(plink!=NULL) {do{ r=p。 p=plink。rlink=q。q=r。}while(plink!=NULL)。 } plink=r。 return(p)。 } NODE* create(n)/*建立初始鏈表*/ int n。 { int i。 NODE *head,*p,*q。 if(n==0) return(NULL)。 head=(NODE*)malloc(sizeof(NODE))。 p=head。 for(i=1。in。i++) { scanf(%d,amp。(pdata))。 q=(NODE*)malloc(sizeof(NODE))。 plink=q。 p=q。 } scanf(%d,amp。(pdata))。 plink=NULL。 return(head)。 } main() { NODE *head,*r,*p。 int n=5。 printf(enter the data:\n)。 head=create(n)。 p=head。 while(p!=NULL) { printf(%d ,pdata)。 p=plink。 } printf(\n)。 head=tranfer(head)。 p=head。 printf(now the list is:\n)。 while(p!=NULL) { printf(%d ,pdata)。 p=plink。 } printf(\n)。 }輸入：1 2 3 4 5輸出：5 4 3 2 1對于給定的線性鏈表,編寫一個把值為a的結(jié)點(diǎn)插在值為b的結(jié)點(diǎn)的前面的c函數(shù)。若值為b的結(jié)點(diǎn)不在線性鏈表中，則把a(bǔ)插在表的最后。[存儲結(jié)構(gòu)] 利用線形表的鏈接存儲：typedef struct node{char data。 struct node *link。}NODE。 定義指針NODE **head,*p,*q,*t。 [解題思路] 指針*head指向鏈表的根結(jié)點(diǎn)，指針p指向值為b的結(jié)點(diǎn)，指針t指向它的前趨結(jié)點(diǎn)，指針q指向插入結(jié)點(diǎn)a。 (1) 如果頭結(jié)點(diǎn)*head為空，或*head的結(jié)點(diǎn)值為b，修改頭指針，結(jié)束算法；(2) 查找值為b的結(jié)點(diǎn)，若找到，把值為a的結(jié)點(diǎn)插到b的前面；(3) 若找不到，把a(bǔ)結(jié)點(diǎn)插在鏈表最后；結(jié)束算法。 [程序] include typedef struct node{char data。 struct node *link。}NODE。 void insert(NODE **head,char a) {NODE *p,*q,*t。 q=(NODE*)malloc(sizeof(NODE))。 qdata=a。 if(*head==NULL||(*head)data==39。b39。) {qlink=*head。 *head=q。 return。} for(p=*head。pdata!=39。b39。amp。amp。p!=NULL。p=plink) t=p。 qlink=p。 tlink=q。 }[測試用例1] 原鏈表：b,c,d,e,g,h插入a結(jié)點(diǎn)后：a,b,c,d,e,f,g,h[測試用例2] 原鏈表：c,d,e,f,g,h 插入a結(jié)點(diǎn)后:c,d,e,f,g,h,a[測試用例3] 原鏈表：c,d,e,b,f