C語言高級(jí)程序設(shè)計(jì)(下)ppt課件

1、例4.1 例4.1 編寫一個(gè)函數(shù)，找出字符串str1與str2的一切最長公共子串。例4.1 首先，斷定兩個(gè)串能否有長為j的子串的方法是：對(duì)串1從左至右的的每一個(gè)子串，都與串2的從左至右的每一個(gè)子串進(jìn)展比較。思索“bsdefg與“asdefsdefsrt的公共子串例4.1 本例是計(jì)算最長的公共子串，這里的方法是從能夠的最長的子串的長度開場(chǎng)思索，即從j=min(strlen(str1),strlen(str2)開場(chǎng)，看能否有這個(gè)長度的公共子串，假設(shè)有，那么一定是最長的，否那么再對(duì)j-1嘗試，直至j減至0為止。int substr(char int substr(char * *str1,char

2、str1,char * *str2,int str2,int * *len)len)char char * *s1,s1,* *s2; /s2; /* *分別表示長、短串分別表示長、短串* */ / int len1,len2, k,j,i,l,count=0; int len1,len2, k,j,i,l,count=0; len1=strlen(str1); len2=strlen(str2);len1=strlen(str1); len2=strlen(str2);s1=len1len2?str1:str2; s2=len1len2?str2:str1;s1=len1len2?str1:

3、str2; s2=len1len2?str2:str1;len2=len1len2?len2:len1;len2=len1len2?len2:len1;for (j=len2;j0;j-) /for (j=len2;j0;j-) /* *從最有能夠的長子串開場(chǎng)從最有能夠的長子串開場(chǎng)* */ / for (k=0;k+j=len2;k+)for (k=0;k+j=len2;k+) for (i=0;s1i+j-1!=0;i+)for (i=0;s1i+j-1!=0;i+)for (l=0;lj&s1i+l=s2k+l;l+);for (l=0;lj&s1i+l=s2k+l;l+);if (l=j

4、)if (l=j)for (l=0;lj;l+)for (l=0;l0) break;if (count0) break; * *len=(count0)?j:0;len=(count0)?j:0; return count; return count; 例4.2 例4.2 采用順序構(gòu)造存儲(chǔ)串。試編寫一個(gè)實(shí)現(xiàn)串通配符匹配的函數(shù)pindex()，其中的通配符只需？，它可以和任何一字符匹配勝利，例如：pindex(“?re,there are)前往的結(jié)果是2。int pindex(char *substr,char *str)int i,j,k;for (i=0;stri;i+)for (j=i,

5、k=0; strj=substrk|substrk=?; j+,k+)if (!substrk+1)return i;return -1;例4.3 例4.3 試編寫一個(gè)函數(shù)int like(char str,char pattern)，該函數(shù)實(shí)現(xiàn)字符串匹配功能，str為被匹配的字符串，pattern是匹配方式，匹配方式有以下幾種情況：1_下劃線和?：表示通配1位恣意字符；2*和%：表示通配0個(gè)、1個(gè)或多個(gè)恣意字符；3本義符：- ? * % 表示準(zhǔn)確匹配，而不是通配；其它字符為準(zhǔn)確匹配；通配符可以多次出現(xiàn)。例4.3 提示：1_下劃線和?：不用比較，方式串與待比串分別向前移一位；2*和%：通配0個(gè)

6、、1個(gè)或多個(gè)恣意字符，此時(shí)方式串前移一位，而待比串移至與方式串一樣符號(hào)的位置。但有能夠所移到的位置并不是真正匹配的位置，因此要保管“*、“%后面字符的位置，假設(shè)方式串有這種通配符，也可以恢復(fù)方式串到保管的“*、“%位置，繼續(xù)與待比串匹配；3本義符：- ? * % 表示準(zhǔn)確匹配，此時(shí)設(shè)標(biāo)志，并將方式串前移一位； for (j=0,k=0;)for (;strj=patternk|!accurateFlag &(patternk=?|patternk=_| patternk=*|patternk=%|patternk=);)if (strj=patternk)j+; k+; accurateFla

7、g=0;else if (patternk=) /*本義符處置*/ k+;/*方式串前移*/ accurateFlag=1;/*設(shè)標(biāo)志，以使循環(huán)條件成立*/ elseif (patternk=?|patternk=_) /*?、_的處置*/ j+; k+; else /* *，%的處置*/ posK=k+;/*保管*，%的位置*/ while (patternk!=strj & strj!=0) j+; if (patternk!=strj | strj=0) break;if (!patternk & !strj) return 1; /*勝利終了*/else if(!patternk) b

8、reak; /*方式串終了但待比串未終了，不一定終止*/else if(!strj) return 0; /*待比串終了但方式串不終了，不匹配*/if(posK=-1) break;/*假設(shè)無回溯時(shí)機(jī)，那么不匹配*/k=posK; j+;posK=-1;/*回溯至*或%位置，與待比串當(dāng)前字符繼續(xù)比較*/例4.4例4.4 編寫一個(gè)函數(shù)，求串str中出現(xiàn)的第一個(gè)最長反復(fù)子串的下標(biāo)和長度。void firstL(char *str,int *index,int *length)int len,i,j,l; *index=0; *length=0;l=strlen(str);for(i=0;il;i+

9、)for(j=i+1;j*length) /*找到了一個(gè)更長的匹配*/ *index=i; *length=len; 例4.5例4.5 編寫一個(gè)函數(shù)，將串s1中的第i個(gè)字符到第j個(gè)字符之間的字符交換成串s2。char *stuff(char *s1,int i,int j,char *s2) int len1,len2,len;char *p,*h;len1=strlen(s1);len2=strlen(s2);if (i=1 & i=1 & j=len1) len=len1-(j-i+1)+len2; /*新串長度*/h=(char *)malloc(sizeof(char)*len+1);

10、s1i-1=0;strcpy(h,s1);p=h+i-1;strcpy(p,s2);p=p+len2;strcpy(p,s1+j);return h;else return NULL;例4.6例4.6 編寫一個(gè)函數(shù)，將字符串s1中的一切str1串，用串str2交換，將結(jié)果放在串s2中。void replace(char *s1,char *s2,char *str1,char *str2)char *t0,*t1,*t2; /*t0-s1指針,t1-str1指針,t2-str2指針*/while (*s1)for (t0=s1,t1=str1; *t1!=0 & *t0=*t1 ; t0+,t

11、1+); if (*t1!=0) /*str1匹配不上，逐個(gè)復(fù)制到s2中*/*s2+=*s1+;else for (t2=str2;*t2!=0;) *s2+=*t2+;s1=t0;*s2=0;例4.7例4.7 試編寫程序，統(tǒng)計(jì)英文文章中，各單詞出現(xiàn)的次數(shù)。設(shè)英文文章已裝入字符緩沖區(qū)buf中。例4.7我們給出的方法是將讀到的每一個(gè)單詞逐一計(jì)數(shù)。單詞存取的方法中是用hash算法，即用hash函數(shù)計(jì)算出單詞假設(shè)有大寫字母在此都按小寫計(jì)算在hash表中的位置。處理hash沖突的方法是順序查找可用位置。hash函數(shù)的設(shè)計(jì)hashcode(word)=例4.7#define LEN 1000int le

12、n=LEN;typedef struct tagchar * word;int count;NODE;例4.7NODE hashMapLEN;/* 參與hash表中* 參數(shù) word 單詞串*/void init()memset(hashMap,0,LEN*sizeof(NODE);例4.7/* hash計(jì)算定義，即hash函數(shù)*/int hashcode(char * str)int sum=0;int i;char *p,c;for(i=0,p=str;*p;i+,p+)c=isupper(*p)?*p+a-A:*p; sum+=c*c*(i+1);for(i=sum%len;ilen &

13、 hashMapi.word !=NULL;i+)if(stricmp(hashMapi.word ,str)=0) break; if(i=len) for(i=0;isum%len & hashMapi.word !=NULL;i+)if(stricmp(hashMapi.word ,str)=0) break;if(i=sum%len) i=-1;return i;例4.7/* 參與hash表中*/int addToMap(char *word)int i,j;i=hashcode(word);if(i=-1) return 0;if(hashMapi.word =NULL) char

14、*p=(char *)malloc(strlen(word)+1);for(j=0;(size_t)jstrlen(word);j+)if(isupper(*(word+j) *(word+j)+=32; /*將大寫變?yōu)樾懽帜?/strcpy(p,word);hashMapi.word =p;hashMapi.count =1;elsehashMapi.count +;return 1;例4.7/* 打印hash表內(nèi)容*/void print()int i;for(i=0;i=0) fread(&t,LEN,1,fp); printf(%s%d%d%s%fn,,t.age,t.s

15、ex,t.dep,t.wage); fs=fseek(fp,-(long)(LEN*2),1);fclose(fp);return 0; 例5.3某商場(chǎng)經(jīng)過顧客投票，從n=40位優(yōu)秀效力員中，評(píng)選十位效力明星： 1效力員按1，2，順序延續(xù)編號(hào)，每個(gè)編號(hào)用兩個(gè)字符表示，即01，02，； 2所收到的選票按以下格式存于文件source中，一行字符串對(duì)應(yīng)一張選票，其中姓名10個(gè)字符，地址30個(gè)字符，10個(gè)效力員編號(hào)20個(gè)字符。 3對(duì)應(yīng)名次的效力員編號(hào)可以有空缺，但必需用00表示。 4假設(shè)編號(hào)超出規(guī)定范圍，或編號(hào)出現(xiàn)反復(fù)，作廢票處置。 5 按選票中所列最正確效力員明星順序給所列效力員按以下規(guī)范評(píng)分： 一

16、 二 三 四 五 六 七 八 九 十 15 12 9 7 6 5 4 3 2 1 6按各位效力員得分?jǐn)?shù)由高到低順序，列出前十名效力員明星排行表： 名次 效力員編號(hào) 合計(jì)得分 提示： 選票的數(shù)據(jù)文件中的數(shù)據(jù)是構(gòu)造數(shù)據(jù)，因此我們可以定義描畫構(gòu)造，用于讀寫文件。對(duì)于一條記錄的處置是先提取10位所選出的效力員的編號(hào)，然后驗(yàn)證其有效性，假設(shè)有效，那么計(jì)分。全部計(jì)分終了時(shí)，排序并打印。 記錄構(gòu)造定義 ：typedef struct char name10;char address30;char no102; REC; 數(shù)據(jù)定義： long int scoreN+1,orderN+1; scorei-總得分

17、,order-效力員編號(hào) 例5.4有n個(gè)班級(jí)參與ns個(gè)工程的競(jìng)賽。從文件t.in中讀入n=30個(gè)班級(jí)、ns=10個(gè)工程的得分，計(jì)算出各班的總分，并按總分降序的次序?qū)⒚總€(gè)班級(jí)總分及各工程的得分輸出到文件t.out。 提示： 得分文件的格式是非構(gòu)造的，用空格分隔，因此用格式輸入函數(shù)操作。 此標(biāo)題對(duì)文件數(shù)據(jù)的主要處置是排序。為了提高效率，設(shè)計(jì)total,order兩個(gè)數(shù)組，分別代表第i個(gè)班的總分和班級(jí)號(hào)，排序時(shí)只對(duì)這兩個(gè)數(shù)組進(jìn)展操作，以便提高效率。 數(shù)據(jù)定義： int scoreNNS; /* scorei為第i個(gè)班的得分*/int totalN,orderN; /*totali為第i個(gè)班的總分，o

18、rderi為班級(jí)號(hào);例5.5對(duì)于一個(gè)ASCII文件，TAB鍵是一個(gè)空格控制鍵，當(dāng)在一個(gè)字符前插入一個(gè)TAB鍵后，在屏幕上編輯窗口內(nèi)該字符將向后挪動(dòng)18個(gè)字符位置，直至定位在8*k+1列上。例如：假設(shè)字符在第8列，插入一個(gè)TAB鍵后，該字符將定位在第9列上；假設(shè)字符在第9列，插入一個(gè)TAB鍵后，該字符將定位在第17列上。 試編寫一個(gè)函數(shù)，對(duì)于一個(gè)含有TAB符的ASCII文件A.TXT，生成一個(gè)目的文件B.TXT，以適當(dāng)數(shù)量的空格符交換TAB符。其中TAB符的ASCII碼為9。 提示： 本例就是將文本內(nèi)容讀到內(nèi)存中，掃描t交換為假設(shè)干空格，其空格數(shù)要經(jīng)過計(jì)數(shù)計(jì)算，可以不斷累計(jì)，遇n時(shí)復(fù)位為1。這里

19、的文件格式是文本的，我們可以按塊進(jìn)展讀取。我們這里用的是按字符讀取方式，其效率不如前者。 ch=fgetc(fpin);while (ch!=EOF) if (ch=n | ch=r) /*遇回車換行，那么遇回車換行，那么i復(fù)位復(fù)位*/i=1;fputc(ch,fpout); else if (ch!=t)i+;fputc(ch,fpout); else /*遇遇t時(shí)，計(jì)算當(dāng)前光標(biāo)位置時(shí)，計(jì)算當(dāng)前光標(biāo)位置*/k=i%80;k=i=1?8:(8-k%8+1)%8; /*計(jì)算出需求插入的空格數(shù)計(jì)算出需求插入的空格數(shù)k*/i+=k;for (j=0;jk;j+)fputc( ,fpout); ch=

20、fgetc(fpin); 例5.6思索多項(xiàng)式H(x)=xN1xN2xNm，試編寫兩個(gè)函數(shù)： 1 void store(char *filename)，該函數(shù)從鍵盤讀入多個(gè)多項(xiàng)式，并將多項(xiàng)式存儲(chǔ)在由參數(shù)指定的文件中。多項(xiàng)式的輸入方式F(x)=x*3+x*2-x，一個(gè)多項(xiàng)式在文件中占一行，其存儲(chǔ)方式為Fxxx+xx-x，其中F為多項(xiàng)式的函數(shù)名，xxx表示x的立方。 2 void restore(char *filename)，該函數(shù)從參數(shù)filename指定的文件讀出一切的多項(xiàng)式，并以 F(x)=x*3+x*2-x方式進(jìn)展輸出。 提示： 本例是以字符串方式讀寫文件。二個(gè)函數(shù)都要對(duì)字符串進(jìn)展分析。本

21、質(zhì)上是形如F(x)=x*3+x*2-x的格式與形如Fxxx+xx-x格式的字符串之間的相互轉(zhuǎn)換。 例5.7編寫程序，讀下面定義的數(shù)據(jù)庫文件中的全部數(shù)據(jù)，并按字段對(duì)齊的方式列表顯示數(shù)據(jù)。數(shù)據(jù)文件的格式是：1頭部分： 數(shù)據(jù)文件標(biāo)識(shí)：4個(gè)字節(jié) 記錄的字節(jié)大小：4個(gè)字節(jié) 記錄字段數(shù)：2字節(jié)2方式描畫部分 對(duì)于記錄的每個(gè)字段有下面描畫：字段名長：2字節(jié)字段名：如上定義的長度字段字節(jié)數(shù)：2字節(jié)3數(shù)據(jù)部分 反復(fù)下面內(nèi)容，直至文件終了。 刪除標(biāo)志：1字節(jié) 按方式定義部分給出的各字段的數(shù)據(jù)其中記錄的內(nèi)容為： 數(shù)據(jù)按下例格式打印： Name location specialties size rate owner

22、Buonarotti & Company Smallville Air Conditioning, 10 $40.00 Smallville Painting Swanders & Flaughn Smallville Painting, 7 $55.00 Smallville Air Conditioning Moore Power Tool Ya Whoville Air Conditioning 7 $65.00 Whoville 字段描述 字段名 長度 姓名 name 32 地址 location 64 專業(yè) Specialties 64 人數(shù) Size 6 時(shí)薪 Rate 8 擁有者

23、 Owner 8留意: 文件中的數(shù)據(jù)存儲(chǔ)時(shí)，按高位數(shù)據(jù)在高端，而我們的機(jī)器數(shù)據(jù)按高位數(shù)據(jù)在低端存儲(chǔ)。 提示： 根據(jù)文件格式的規(guī)定，先定義文件頭構(gòu)造、字段信息構(gòu)造和記錄構(gòu)造。再分別編寫代碼，將文件中的頭、字段信息和記錄數(shù)據(jù)讀到上面定義的構(gòu)造的實(shí)例中。在讀數(shù)值時(shí)，要將所讀到的值的內(nèi)容反轉(zhuǎn)，如在文件中有二個(gè)字節(jié)為0 x00 和0 x06，那么要將這兩個(gè)字節(jié)反轉(zhuǎn)為0 x06和0 x00。 定義記錄構(gòu)造 : typedef struct recchar flag;char name32;char location64;char specialties64;char size6;char rate8;ch

24、ar owner8; REC; 定義字段描畫構(gòu)造 : typedef struct fieldchar * name;short len; FIELD; 定義頭描畫構(gòu)造 : typedef struct long cookies;long len;short fieldNum; HEADER; 例6.1 例6.1寫一個(gè)程序，要求輸入學(xué)生選修課程的學(xué)習(xí)情況每個(gè)學(xué)生可選多門課程，一門課程可有多個(gè)學(xué)生選修，包括：學(xué)號(hào)、學(xué)生姓名、課程稱號(hào)、成果、所在系別、授課教師姓名；完成以下輸出：將每門課程的成果由高到低排序輸出；計(jì)算出每個(gè)學(xué)生一切選修課程的平均成果，并由高到低排序輸出。例6.1 首先要定義學(xué)生鏈表

25、和課程鏈表的結(jié)點(diǎn)的構(gòu)造，然后編寫創(chuàng)建其結(jié)點(diǎn)實(shí)例的方法和向鏈表中插入的方法。對(duì)于每一個(gè)學(xué)生，建立相應(yīng)學(xué)生信息的結(jié)點(diǎn)；然后計(jì)算學(xué)生平均成果，并按照平均成果將上述結(jié)點(diǎn)插入到學(xué)生鏈表中。 例6.1 數(shù)據(jù)構(gòu)造設(shè)計(jì)： headnum namedepavecourse nextstudentcour teacherscore next例6.1 課程鏈表中結(jié)點(diǎn)的定義 : typedef struct course char cour30; int score; char teacher10; struct course *next; COURSE; 例6.1 學(xué)生鏈表中結(jié)點(diǎn)的定義 : typedef stru

26、ct student int num; char name10; char dep20; float ave; COURSE *link; struct student *next; STUDENT;建立學(xué)生鏈表的代碼片段建立學(xué)生鏈表的代碼片段 : : for(i=0;in;i+) for(i=0;iave=(h=NULL|stu-ave=(* *h)-ave)h)-ave)stu-next=stu-next=* *h; h; * *h=stu;h=stu; else elseq=q=* *h; p=q-next;h; p=q-next;while (p!=NULL & stu-aveave)

27、while (p!=NULL & stu-aveave)q=p; p=p-next;q=p; p=p-next; stu-next=p; q-next=stu;stu-next=p; q-next=stu; createStudentNodecreateStudentNode函數(shù)：函數(shù)： STUDENT STUDENT * * createStudentNode() createStudentNode() COURSE COURSE * *q;q; STUDENT STUDENT * * p=(STUDENT p=(STUDENT * *)malloc(sizeof(STUDENT);)mal

28、loc(sizeof(STUDENT); printf(num=); printf(num=); scanf(%d,&p-num); scanf(%d,&p-num); printf(name=); printf(name=); scanf(%s,p-name); scanf(%s,p-name); printf(dep=); printf(dep=); scanf(%s,p-dep); scanf(%s,p-dep); p-link=NULL; p-link=NULL; / /* *輸入所學(xué)課程的分?jǐn)?shù)輸入所學(xué)課程的分?jǐn)?shù)* */ / / /* *假設(shè)為假設(shè)為00那么終了那么終了* */ / w

29、hile (q=createCourseNode()!=NULL) while (q=createCourseNode()!=NULL)insertCourseNode(&(p-link),q );insertCourseNode(&(p-link),q ); / /* *計(jì)算課程的平均成果計(jì)算課程的平均成果* */ / p-ave =aver(p-link); p-ave =aver(p-link); return p; return p; 例6.2 例6.2 1編寫一個(gè)函數(shù)，根據(jù)一個(gè)知數(shù)組構(gòu)造一個(gè)線性鏈表； 2編寫一個(gè)函數(shù)，對(duì)線性鏈表排序。提示： 只需定義結(jié)點(diǎn)構(gòu)造及其操作。這里我們給出了結(jié)

30、點(diǎn)的創(chuàng)建、插入、排序和打印函數(shù)。 建立結(jié)點(diǎn)：ELEM *createNode(int n)ELEM *q=(ELEM*)malloc(sizeof(ELEM);q-n=n;q-next=NULL;return q; 在鏈表尾插入結(jié)點(diǎn) ：void insertAtTail(ELEM * h,ELEM * elem)ELEM * p1,*p2;if(*h=NULL)*h=elem; return ;for(p1=*h,p2=p1-next ;p2!=NULL;p1=p2,p2=p2-next); /*移到鏈表尾部*/p1-next=elem;elem-next=NULL;鏈表元素排序鏈表元素排序

31、：void sortList(ELEM void sortList(ELEM * * *h)h)ELEM ELEM * *p,p,* *q,q,* *r, r,* *s, s,* *h1;h1;h1=p=(ELEMh1=p=(ELEM* *)malloc(sizeof(ELEM);)malloc(sizeof(ELEM); p-next= p-next=* *h;h;while(p-next!=NULL)while(p-next!=NULL)q=p-next;q=p-next;r=p;r=p;while(q-next!=NULL)while(q-next!=NULL)if (q-next-n)

32、next-n)if (q-next-n)next-n)r=q;r=q;q=q-next;q=q-next; if(r!=p)if(r!=p)s=r-next;s=r-next;r-next=p-next;r-next=p-next;r=s-next;r=s-next;s-next=p-next-next;s-next=p-next-next;p-next-next=r;p-next-next=r;p-next=s;p-next=s; p=p-next;p=p-next; * *h=h1-next;h=h1-next;free(h1);free(h1); 例6.3 例6.3 編寫一個(gè)程序，可以完

33、成二個(gè)恣意長度的以字符串表示的正整數(shù)的乘法。闡明：輸入的整數(shù)能夠超越系統(tǒng)所能表示的最大整數(shù)及最大實(shí)數(shù)的范圍或精度。 例：輸入：124597860和123 輸出例6.3 提示：可以將乘法的結(jié)果放于鏈表中，因此我們要首先定義鏈表結(jié)點(diǎn)構(gòu)造和它相關(guān)的操作：創(chuàng)建結(jié)點(diǎn)實(shí)例和鏈表顯示操作，然后編寫乘法運(yùn)算程序。對(duì)于乘數(shù)從個(gè)位開場(chǎng)的每一位，逐一與被乘數(shù)相乘。當(dāng)?shù)趇位乘數(shù)bi與被乘數(shù)aj相乘時(shí)，結(jié)果落于第i+j位上。被乘數(shù) aj a2 a1乘數(shù) bi b1當(dāng)前結(jié)果鏈表的位 ri+j ri+j-1第i位乘數(shù)bi與被乘數(shù)的第j位aj相乘時(shí)的結(jié)果 aj*bi進(jìn)位 ci+j ci+j-1例6.

34、3 因此：m=ri+j+aj*bi+ci+j-1 /*本次計(jì)算中，結(jié)果鏈表的第i+j位上的累計(jì)總值*/ri+j=m%10 /*本次計(jì)算中，結(jié)果鏈表的第i+j位的最終值*/ci+j=m/10 /*本次計(jì)算中的進(jìn)位進(jìn)到第i+j+1位上 第i位乘數(shù)與被乘數(shù)的乘法計(jì)算void multi(BIT *head,char *str,char ch,int i)；參數(shù) head：結(jié)果鏈表的頭指針，str：被乘數(shù)串，ch：乘數(shù)第i位上的數(shù)字，i：乘數(shù)位數(shù)定位乘積個(gè)位：ptr=head; while (nnext!=NULL)ptr=ptr-next; elseq=createNode(0);ptr-next=

35、q;ptr=ptr-next; n+; 定位被乘數(shù)個(gè)位： p=str; while(*p!=0) p+;乘法運(yùn)算：q=ptr;while(pstr)p-; mul1=(*p-0)*(ch-0)+a1; /*乘運(yùn)算*/a1=mul1/10;mul1%=10; /*a1為乘積進(jìn)位*/if(ptr=NULL)ptr=createNode(0);q-next=ptr;q=ptr;mul2=ptr-num+mul1+a2; /*與結(jié)果鏈當(dāng)前位累加*/a2=mul2/10; /*a2為累加進(jìn)位*/mul2%=10; /*mul2為本次運(yùn)算結(jié)果鏈當(dāng)前位的最終值*/ptr-num=mul2;q=ptr;ptr

36、=ptr-next;處置最高進(jìn)位： if(a1!=0|a2!=0) if(ptr=NULL) ptr=createNode(0);q-next=ptr; ptr-num=ptr-num+a1+a2; 兩個(gè)數(shù)字串的乘法計(jì)算： 參數(shù) head：結(jié)果鏈表的頭指針的地址，str：被乘數(shù)串，str2：乘數(shù)串void multiply(BIT * head,char * str1,char *str2)char * p;int i;p=str2;/*定位乘數(shù)個(gè)位*/while (*p!=0) p+;/*為str2的每一位分配空間*/*head=createNode(0);i=0; while (pstr2

37、)p-;if (*p!=0) multi(*head,str1,*p,i); /*乘數(shù)的第 i位數(shù)*p乘以被乘數(shù)*/i+;例6.4例6.4有一個(gè)單鏈表L至少有1個(gè)結(jié)點(diǎn)，其頭結(jié)點(diǎn)指針head，編寫一個(gè)函數(shù)將L逆置，即最后一個(gè)結(jié)點(diǎn)變成第一個(gè)結(jié)點(diǎn)，原來倒數(shù)第二個(gè)結(jié)點(diǎn)變成第二個(gè)結(jié)點(diǎn)，以次類推。 例6.4提示： 定義鏈表的結(jié)點(diǎn)構(gòu)造以及創(chuàng)建結(jié)點(diǎn)、插入、打印、逆置等鏈表的相關(guān)操作。鏈表逆置的部分操作： headNULLpqrpp qq rrppqq rrppqqNULL例6.5例6.5 編寫一個(gè)函數(shù)，交換單鏈表中p所指向的結(jié)點(diǎn)和其后續(xù)位置上的結(jié)點(diǎn)。head指向該鏈表的表頭，p指向該鏈表中的某一結(jié)點(diǎn)。 提示：

38、 交換指定結(jié)點(diǎn)的后序兩個(gè)元素，要對(duì)鏈指針進(jìn)展操作。因此要描畫鏈表的指針及相關(guān)操作。其中交換結(jié)點(diǎn)操作: headNULLps例6.6例6.6編程：輸入數(shù)字串方式的人民幣錢數(shù)人民幣小寫，輸出相應(yīng)的人民幣大寫表示。假定輸入的錢數(shù)小于1億元，且角和分用小數(shù)表示，并假定輸入無錯(cuò)誤。人民幣大寫的規(guī)定如下：假設(shè)金額沒有分，那么后面要加上“整字；假設(shè)數(shù)字中間有延續(xù)假設(shè)干個(gè)0，變成大寫時(shí)，最多寫一個(gè)“零字。假定程序的運(yùn)轉(zhuǎn)環(huán)境支持漢字顯示。他甚至可以本人定義所用到的任何漢字的代碼，而不用思索能否和實(shí)踐一致。例如：1000.00 壹千元整 3009.40 叁千零玖元肆角整 5000608.72 五百萬零陸百零捌元柒

39、角貳分例6.6提示：1人民幣從小寫方式轉(zhuǎn)換為大寫方式是有規(guī)律的。首先我們將除小數(shù)位外的各位稱為位元，位元用5個(gè)屬性描畫：index、val、ch1、ch2和ch3，見圖6.4，除了數(shù)字本身的轉(zhuǎn)換外，十進(jìn)制的單位ch1按“、“拾、“佰、“仟循環(huán)，ch2只在能在被4整除的位上有值，其它位上是“或?yàn)镹ULL。 index87654321001ch3億萬ch2“”仟佰拾“”仟佰拾“”角分ch1val475123456.56 整數(shù)部分小數(shù)點(diǎn)小數(shù)部分例6.6對(duì)應(yīng)的數(shù)據(jù)設(shè)計(jì)：static char *str1=零,壹,貳,叁,肆,伍,陸,柒,捌,玖;static char *str2=,拾,佰,仟;stat

40、ic char *str3=,萬,億;static char *str4=角,分;static char *str5=圓,整;例6.6提示：2 val為0的位元上，十進(jìn)制單位ch2取消，然后用圖6.5的形狀轉(zhuǎn)移圖完成：q0為初始形狀，在這個(gè)形狀下，遇0時(shí)刪去ch1，遇非0時(shí)，轉(zhuǎn)q1形狀；在q1形狀下，遇0時(shí)轉(zhuǎn)q0形狀，該ch1保管。 3處置時(shí)，首先將原串拆分為整數(shù)部分和小數(shù)部分；然后分別分析各部分。在分析整數(shù)部分時(shí)，計(jì)算ch1、ch2和ch3的值，同時(shí)得處置零情形；最后打印各位的內(nèi)容。 q0q1圖6.5 人民幣轉(zhuǎn)換圖示0：去掉非0非00：保管例6.6位結(jié)點(diǎn)構(gòu)造定義 ：typedef struc

41、t bitdescint val; /*本位數(shù)字*/int index; /*序號(hào)*/char* ch1; /*本位數(shù)字對(duì)應(yīng)的大寫方式*/char* ch2; /*“、“拾、“佰、“仟*/char* ch3; /*“萬、“億*/struct bitdesc * next; /*鏈表指針*/BITDESC;創(chuàng)建一個(gè)整數(shù)位：BITDESC *createNode(int val,int index)BITDESC * p=(BITDESC *)malloc(sizeof(BITDESC );p-val=val;p-index =index;p-ch1=str1val;p-ch2=val=0?:st

42、r2index%4;p-ch3 =index%4=0?str3index/4:;p-next =NULL;return p;創(chuàng)建小數(shù)位：BITDESC *createFloatNode(int val,int index)BITDESC * p=(BITDESC *)malloc(sizeof(BITDESC );p-val=val;p-index =index;p-ch1=val=0& index=1?:str1val;p-ch2=val=0?:str4index;p-ch3 =;p-next =NULL;return p;在鏈表尾插入結(jié)點(diǎn)： 參數(shù) head：鏈表的頭指針，node：指定的結(jié)

43、點(diǎn)void insertAtTail(BITDESC * head,BITDESC * node)BITDESC * p1,*p2;if(*head=NULL)*head=node;node-next =NULL;return;for(p1=NULL,p2=*head;p2!=NULL;p1=p2,p2=p2-next);p1-next =node;在鏈表頭插入結(jié)點(diǎn)： 參數(shù) head：鏈表的頭指針，node：指定的結(jié)點(diǎn)void insertAtHead(BITDESC * head,BITDESC * node)if(*head=NULL)*head=node;node-next =NULL;

44、return;node-next =*head;*head=node;分析整數(shù)部分構(gòu)成位元實(shí)例的鏈表，并處置零情形： 參數(shù) head 鏈表頭的地址 intStr 整數(shù)部分的數(shù)字串void parseInt(BITDESC *head,char *intStr)int len=strlen(intStr);int i,state;BITDESC * pBitDesc;char *p=intStr+len-1;for(i=0;p-)insertAtTail(head,createNode(*p-0,i+);if(p=intStr) break;/*處置零*/for(i=0,pBitDesc=*he

45、ad;pBitDesc;pBitDesc=pBitDesc-next,i+)if(i%4=0) state=0;switch(state)case 0:if(pBitDesc-val =0) pBitDesc-ch1 =;else state=1;break;case 1:if(pBitDesc-val =0) state=0;break; 分析小數(shù)部分構(gòu)成位元實(shí)例的鏈表： 參數(shù) head 鏈表頭的地址 floatStr 小數(shù)部分的數(shù)字串 endStr 表示字串“整的地址void parseFloat(BITDESC *head,char *floatStr,char * endStr)int

46、 i=0;int len=0;if(floatStr!=NULL) len=strlen(floatStr);while(*(floatStr+len-1)=0) len-;for(i=0;ilen;i+) insertAtTail(head,createFloatNode(*(floatStr+i)-0,i);if(i2)*endStr=str51; 例6.7例6.7 實(shí)現(xiàn)變?cè)獮閤，y，z的兩個(gè)整系數(shù)多項(xiàng)式的相加。例如：多項(xiàng)式3x6-5x5y2+6x6z 提示： 這個(gè)問題本質(zhì)上是合并兩個(gè)已有序的鏈表，即是兩個(gè)鏈表的歸并排序。每個(gè)結(jié)點(diǎn)表示為： c X i Y j Zk 常數(shù) x的次數(shù) y的次數(shù)

47、 z的次數(shù) 例6.7例:第一個(gè)多項(xiàng)式為：X5+4X2Y2+X 第二個(gè)多項(xiàng)式為：7X3+5XYZ+Z6 那么鏈表分別為： c X i Y j Zk 1 5 0 0 c X i Y j Zk 4 2 2 0 c X i Y j Zk 1 1 0 0 c X i Y j Zk 5 1 1 1 c X i Y j Zk 7 3 0 0 c X i Y j Zk 1 0 0 6 例7.1 例7.1 將A、B、C、D、E、F這6個(gè)變量排成以下圖1所示的三角形，這6個(gè)變量分別取1至6上的整數(shù)，且互不一樣。試找出使三角形3條邊上的3個(gè)數(shù)之和相等的一切能夠解，以下圖2所示為其中的一個(gè)解。 A 4 B F 1 5

48、 C D E 6 3 2 圖1 圖2例7.1 提示： 這個(gè)問題的搜索空間是1至6的一切陳列。對(duì)于每種陳列，看能否滿足要求，假設(shè)滿足，就屬于解空間，輸出它。在產(chǎn)生1至6的陳列時(shí)，采用回溯方法。設(shè)a1a6是一個(gè)陳列，生成下一陳列時(shí)，先思索a6的其它能夠值，假設(shè)沒有，那么釋放a6的值，再思索a5的下一個(gè)能夠值每一個(gè)數(shù)的下一能夠值永遠(yuǎn)按一個(gè)規(guī)律變化，在此只能增大。普通地，對(duì)于k，先思索ak的其它能夠值，假設(shè)沒有，那么釋放ak，思索ak-1的下一能夠值，直至k=0為止。例7.1 _ 1至6數(shù)列的生成的部分過程 a6 65645465a5 56464556a4 44556633a3 33333345a2

49、22222222a111111111a6無其它值，退至a5 a5可選6，a6只能選5。 a6無其它值，退至a5，a5無其它值，退至a4, a4選5 a6無其它值，退至a5，a5選6 a6無其它值，退至a5，a5無其它值，退至a4, a4選6 a6無其它值，退至a5，a5選5 a6無其它值，退至a5，a5退至a4,再退至a3， a3選4 a6無其它值，退至a5，a5選6 int main(int argc, char* argv)int useableN+1; /*占用標(biāo)志，占用標(biāo)志，useablei為為1，表示數(shù)字，表示數(shù)字i被占用被占用*/int j,k;int flag=1; /*終了標(biāo)志

50、終了標(biāo)志*/for (j=1;j=N;j+) useablej=0; /*初始化初始化(1-6)這這6個(gè)數(shù)都未選中個(gè)數(shù)都未選中*/k=1; while (flag)for(j=1;k=N;k+,j+) /*添滿添滿6個(gè)數(shù)個(gè)數(shù),即為即為ak,ak+1,.,aN置值置值*/while (j=N & useablej) j+; /*找到下一個(gè)可用的數(shù)找到下一個(gè)可用的數(shù)*/useablej=1; /* j為被占用為被占用*/ak=j;if (satisfy()print();k-;do /*回溯回溯*/ useableak=0; /*釋放當(dāng)前數(shù)釋放當(dāng)前數(shù)*/ k-;if (k1) flag=0; /*

51、回溯至回溯至k-1*/ for (j=ak+1;j=N & useablej;j+); /*找下一個(gè)可用數(shù)找下一個(gè)可用數(shù)*/ if (j=N) break; /*找到找到*/while (flag);if (flag) /*找到的數(shù)添入當(dāng)前位找到的數(shù)添入當(dāng)前位*/ useableak=0; useablej=1; /*修正占用標(biāo)志修正占用標(biāo)志*/ ak=j; k+;return 0; 例7.2 例7.2 將1到9這9個(gè)數(shù)不反復(fù)填入3*3的方格中，要求各行、各列、對(duì)角線上各數(shù)之和相等，求出一切能夠的填法。提示： 這個(gè)問題與上一問題一樣，只是對(duì)于取數(shù)的范圍、解的滿足條件及打印內(nèi)容不同。 2 7 6

52、 2 9 4 9 5 1 7 5 3 4 3 8 6 1 8例7.3 例7.3 輸入一個(gè)MN的迷宮，編寫一個(gè)非遞歸函數(shù)，找到一條從1，1到M,N的途徑。 提示 ：從(1,1)出發(fā)，將一切能夠的走法全部用隊(duì)列記錄下來。隊(duì)列中的記錄信息除點(diǎn)坐標(biāo)外，還要記錄該點(diǎn)的來源。假設(shè)從(x,y)可以直接到達(dá)x1,y1(xk,yk)，且(x,y)是隊(duì)中第n條記錄，那么在隊(duì)尾參與(x1,y1,n)(xk,yk,n)，見以下圖。假設(shè)所參與的記錄有(M,N)點(diǎn)，那么終了；否那么處置隊(duì)頭的下一條記錄。例7.3 例如：一個(gè)44迷宮。1表示妨礙，0表示通路。 0 10 00 0 0 10 10 110 0 01102112

53、221234567891011312233135335146437449OK尋覓迷宮途徑尋覓迷宮途徑:void laby()int i,j,x,y,v,front=1,rear=1,find=0;mgQueue1.x=1; mgQueue1.y=1; mgQueue1.pre=0; /*初始起初始起點(diǎn)為點(diǎn)為mg11*/mg11=-1; /*表示曾經(jīng)表示曾經(jīng)路過這點(diǎn)路過這點(diǎn)*/while (front=rear & !find)x=mgQueuefront.x;y=mgQueuefront.y;for (v=1;v=8;v+) /*依次掃依次掃描每個(gè)方向描每個(gè)方向*/i=x+zxv;j=y+zy

54、v;if (mgij=0) /*路通那路通那么入隊(duì)么入隊(duì)*/rear+;mgQueuerear.x=i;mgQueuerear.y=j;mgQueuerear.pre=front;mgij=-1;if (i=M & j=N)print(rear);find=1;front+;if (!find) printf(Error!n); 例7.4 例7.4 八皇后問題。在一個(gè)88的國際象棋盤上，有八個(gè)皇后，每個(gè)皇后占一格；要求皇后間不會(huì)出現(xiàn)相互“攻擊的景象，即不能有兩個(gè)皇后處在同一行、同一列或同一對(duì)角線上。問共有多少種不同的方法。提示： 可以用一維數(shù)組表示8位皇后在不同列上的行值，即ai表示第i位皇后

55、所在的行。計(jì)算第i位皇后的位置時(shí)，曾經(jīng)將前i-1位皇后都放好了。只需第i位的位置不與前i-1位沖突，就繼續(xù)計(jì)算后面的各位皇后的位置。計(jì)算時(shí)從第0行開場(chǎng)嘗試，假設(shè)不沖突，那么將ai壓棧并計(jì)算i+1的位置；否那么一切位置嘗試后，都沖突，那么回退至i-1位，嘗試i-1位的下一位置。 void solution(int sta ,int m)int l,flag=1;statop=1; /*初始化初始化*/l=1;while (flag)while (l=m) /*到一個(gè)適宜的位置？到一個(gè)適宜的位置？*/if (satisfy(sta,l,top+1) /*找到了找到了*/break;else l+;

56、if (lm)flag=0; 例7.5 例7.5 將1到9這9個(gè)數(shù)不反復(fù)地分成3組，每組3個(gè)數(shù)字組成一個(gè)3位數(shù)，要求這3個(gè)3位數(shù)都是完全平方數(shù)，例如：361=19*19，529=23*23，784=28*28。 提示：只需11至31的平方是三位數(shù)，用三個(gè)這樣的三位數(shù)嘗試能否滿足要求，即能否滿足：1它們是1至9不同的數(shù)，2不含0。這個(gè)問題與7.1問題一樣。 例8.1 例8.1 假設(shè)銀行一年零存整取的月息為0.63%。如今某人手中有一筆錢，他計(jì)劃在今后的五年中每年的年底取出1000元，到第五年時(shí)剛好取完，請(qǐng)算出他存錢時(shí)應(yīng)存入多少。 例8.1 提示：由題意我們有：第五年底為x5：x5=1000第四年

57、底為x4：x5/(1+0.0063)+1000第三年底為x3：x4/(1+0.0063)+1000第二年底為x2：x3/(1+0.0063)+1000由上可歸納出第i年底余額的計(jì)算式：xi=xi+1/(1+0.0063)+1000 例8.1 int main(int argc, char* argv)float x1=1000.0,x0;int i;for (i=0;i5;i+) x0=x1/(1+0.0063*12); /*年初*/x1=x0+1000.0; /*年末*/printf(%.2f,x0);return 0; 例8.2 例8.2 A、B、C、D、E五人捕魚。A第一個(gè)來，將魚分為5

58、份，把多余的一條魚扔掉，拿走了本人的一份；B第二個(gè)來，也將魚分為5份，把多余的一條魚扔掉，拿走了本人的一份；C、D、E依次到來，也按同樣的方法拿魚。問他們合伙至少捕了多少條魚？ 例8.2 提示：設(shè)捕魚x條，那么有： 得到的魚數(shù) 分后剩余的魚數(shù) 原捕魚數(shù) x0 第一個(gè)人 (x0-1)/5 x1=(x0-1)/5*4 第二個(gè)人 (x1-1)/5 x2=(x1-1)/5*4 第三個(gè)人 (x2-1)/5 x3=(x2-1)/5*4 第四個(gè)人 (x3-1)/5 x4=(x3-1)/5*4 第五個(gè)人 (x4-1)/5 x5=(x4-1)/5*4于是得到普通的遞推式： xi=(xi-1-1)/5*4要計(jì)算n

59、，n=x0，滿足按上面方法可以遞推五次?？梢詮?開場(chǎng)嘗試。例8.2 int main(int argc, char* argv)int n,i,x;for (n=6; ; n+)for (x=n,i=1; i5) break; /*正常分配那么退出*/printf(nn=%d,n);return 0; 例8.3 例8.3 一缸金魚分五次出賣。第一次賣出全部的一半加二分之一條；第二次賣出余下的三分之一加三分之一條；第三次賣出余下的四分之一加四分之一條；第四次賣出余下的五分之一加五分之一條；最后賣出余下的11條。問原來魚缸中共有幾條魚？ 例8.3 提示：設(shè)全部魚有x條，根據(jù)題意如下： 賣出 剩余

60、第一次賣 (x+1)/2 x1=x-(x+1)/2 第二次賣 (x1+1)/3 x2=x1-(x1+1)/3 第三次賣 (x2+1)/4 x3=x2-(x2+1)/4 第四次賣 (x3+1)/5 x4=x3-(x3+1)/5最后剩余的魚數(shù)x4應(yīng)為11。 例8.3 int main(int argc, char* argv)int i,j,x;for (i=20;i+)for (j=1,x=i;j4 & x=11)break;printf(%dn,i-1);return 0; 例8.4 例8.4 一對(duì)小兔子一年后長成大兔子；一對(duì)大兔子每半年生一對(duì)小兔子。大兔子的繁衍期為四年，兔子的壽命是六年。假