C语言高级程序设计(下)ppt课件

1、例4.1 例4.1 编写一个函数，找出字符串str1与str2的一切最长公共子串。例4.1 首先，断定两个串能否有长为j的子串的方法是：对串1从左至右的的每一个子串，都与串2的从左至右的每一个子串进展比较。思索“bsdefg与“asdefsdefsrt的公共子串例4.1 本例是计算最长的公共子串，这里的方法是从能够的最长的子串的长度开场思索，即从j=min(strlen(str1),strlen(str2)开场，看能否有这个长度的公共子串，假设有，那么一定是最长的，否那么再对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-) /* *从最有能够的长子串开场从最有能够的长子串开场* */ / 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 采用顺序构造存储串。试编写一个实现串通配符匹配的函数pindex()，其中的通配符只需？，它可以和任何一字符匹配胜利，例如：pindex(“?re,there are)前往的结果是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 试编写一个函数int like(char str,char pattern)，该函数实现字符串匹配功能，str为被匹配的字符串，pattern是匹配方式，匹配方式有以下几种情况：1_下划线和?：表示通配1位恣意字符；2*和%：表示通配0个、1个或多个恣意字符；3本义符：- ? * % 表示准确匹配，而不是通配；其它字符为准确匹配；通配符可以多次出现。例4.3 提示：1_下划线和?：不用比较，方式串与待比串分别向前移一位；2*和%：通配0个

6、、1个或多个恣意字符，此时方式串前移一位，而待比串移至与方式串一样符号的位置。但有能够所移到的位置并不是真正匹配的位置，因此要保管“*、“%后面字符的位置，假设方式串有这种通配符，也可以恢复方式串到保管的“*、“%位置，继续与待比串匹配；3本义符：- ? * % 表示准确匹配，此时设标志，并将方式串前移一位； 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;/*设标志，以使循环条件成立*/ 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;/*假设无回溯时机，那么不匹配*/k=posK; j+;posK=-1;/*回溯至*或%位置，与待比串当前字符继续比较*/例4.4例4.4 编写一个函数，求串str中出现的第一个最长反复子串的下标和长度。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) /*找到了一个更长的匹配*/ *index=i; *length=len; 例4.5例4.5 编写一个函数，将串s1中的第i个字符到第j个字符之间的字符交换成串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 编写一个函数，将字符串s1中的一切str1串，用串str2交换，将结果放在串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匹配不上，逐个复制到s2中*/*s2+=*s1+;else for (t2=str2;*t2!=0;) *s2+=*t2+;s1=t0;*s2=0;例4.7例4.7 试编写程序，统计英文文章中，各单词出现的次数。设英文文章已装入字符缓冲区buf中。例4.7我们给出的方法是将读到的每一个单词逐一计数。单词存取的方法中是用hash算法，即用hash函数计算出单词假设有大写字母在此都按小写计算在hash表中的位置。处理hash冲突的方法是顺序查找可用位置。hash函数的设计hashcode(word)=例4.7#define LEN 1000int le

12、n=LEN;typedef struct tagchar * word;int count;NODE;例4.7NODE hashMapLEN;/* 参与hash表中* 参数 word 单词串*/void init()memset(hashMap,0,LEN*sizeof(NODE);例4.7/* hash计算定义，即hash函数*/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; /*将大写变为小写字母*/strcpy(p,word);hashMapi.word =p;hashMapi.count =1;elsehashMapi.count +;return 1;例4.7/* 打印hash表内容*/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某商场经过顾客投票，从n=40位优秀效力员中，评选十位效力明星： 1效力员按1，2，顺序延续编号，每个编号用两个字符表示，即01，02，； 2所收到的选票按以下格式存于文件source中，一行字符串对应一张选票，其中姓名10个字符，地址30个字符，10个效力员编号20个字符。 3对应名次的效力员编号可以有空缺，但必需用00表示。 4假设编号超出规定范围，或编号出现反复，作废票处置。 5 按选票中所列最正确效力员明星顺序给所列效力员按以下规范评分： 一

16、 二 三 四 五 六 七 八 九 十 15 12 9 7 6 5 4 3 2 1 6按各位效力员得分数由高到低顺序，列出前十名效力员明星排行表： 名次 效力员编号 合计得分 提示： 选票的数据文件中的数据是构造数据，因此我们可以定义描画构造，用于读写文件。对于一条记录的处置是先提取10位所选出的效力员的编号，然后验证其有效性，假设有效，那么计分。全部计分终了时，排序并打印。 记录构造定义 ：typedef struct char name10;char address30;char no102; REC; 数据定义： long int scoreN+1,orderN+1; scorei-总得分

17、,order-效力员编号 例5.4有n个班级参与ns个工程的竞赛。从文件t.in中读入n=30个班级、ns=10个工程的得分，计算出各班的总分，并按总分降序的次序将每个班级总分及各工程的得分输出到文件t.out。 提示： 得分文件的格式是非构造的，用空格分隔，因此用格式输入函数操作。 此标题对文件数据的主要处置是排序。为了提高效率，设计total,order两个数组，分别代表第i个班的总分和班级号，排序时只对这两个数组进展操作，以便提高效率。 数据定义： int scoreNNS; /* scorei为第i个班的得分*/int totalN,orderN; /*totali为第i个班的总分，o

18、rderi为班级号;例5.5对于一个ASCII文件，TAB键是一个空格控制键，当在一个字符前插入一个TAB键后，在屏幕上编辑窗口内该字符将向后挪动18个字符位置，直至定位在8*k+1列上。例如：假设字符在第8列，插入一个TAB键后，该字符将定位在第9列上；假设字符在第9列，插入一个TAB键后，该字符将定位在第17列上。 试编写一个函数，对于一个含有TAB符的ASCII文件A.TXT，生成一个目的文件B.TXT，以适当数量的空格符交换TAB符。其中TAB符的ASCII码为9。 提示： 本例就是将文本内容读到内存中，扫描t交换为假设干空格，其空格数要经过计数计算，可以不断累计，遇n时复位为1。这里

19、的文件格式是文本的，我们可以按块进展读取。我们这里用的是按字符读取方式，其效率不如前者。 ch=fgetc(fpin);while (ch!=EOF) if (ch=n | ch=r) /*遇回车换行，那么遇回车换行，那么i复位复位*/i=1;fputc(ch,fpout); else if (ch!=t)i+;fputc(ch,fpout); else /*遇遇t时，计算当前光标位置时，计算当前光标位置*/k=i%80;k=i=1?8:(8-k%8+1)%8; /*计算出需求插入的空格数计算出需求插入的空格数k*/i+=k;for (j=0;jk;j+)fputc( ,fpout); ch=

20、fgetc(fpin); 例5.6思索多项式H(x)=xN1xN2xNm，试编写两个函数： 1 void store(char *filename)，该函数从键盘读入多个多项式，并将多项式存储在由参数指定的文件中。多项式的输入方式F(x)=x*3+x*2-x，一个多项式在文件中占一行，其存储方式为Fxxx+xx-x，其中F为多项式的函数名，xxx表示x的立方。 2 void restore(char *filename)，该函数从参数filename指定的文件读出一切的多项式，并以 F(x)=x*3+x*2-x方式进展输出。 提示： 本例是以字符串方式读写文件。二个函数都要对字符串进展分析。本

21、质上是形如F(x)=x*3+x*2-x的格式与形如Fxxx+xx-x格式的字符串之间的相互转换。 例5.7编写程序，读下面定义的数据库文件中的全部数据，并按字段对齐的方式列表显示数据。数据文件的格式是：1头部分： 数据文件标识：4个字节 记录的字节大小：4个字节 记录字段数：2字节2方式描画部分 对于记录的每个字段有下面描画：字段名长：2字节字段名：如上定义的长度字段字节数：2字节3数据部分 反复下面内容，直至文件终了。 删除标志：1字节 按方式定义部分给出的各字段的数据其中记录的内容为： 数据按下例格式打印： 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 专业 Specialties 64 人数 Size 6 时薪 Rate 8 拥有者

23、 Owner 8留意: 文件中的数据存储时，按高位数据在高端，而我们的机器数据按高位数据在低端存储。 提示： 根据文件格式的规定，先定义文件头构造、字段信息构造和记录构造。再分别编写代码，将文件中的头、字段信息和记录数据读到上面定义的构造的实例中。在读数值时，要将所读到的值的内容反转，如在文件中有二个字节为0 x00 和0 x06，那么要将这两个字节反转为0 x06和0 x00。 定义记录构造 : typedef struct recchar flag;char name32;char location64;char specialties64;char size6;char rate8;ch

24、ar owner8; REC; 定义字段描画构造 : typedef struct fieldchar * name;short len; FIELD; 定义头描画构造 : typedef struct long cookies;long len;short fieldNum; HEADER; 例6.1 例6.1写一个程序，要求输入学生选修课程的学习情况每个学生可选多门课程，一门课程可有多个学生选修，包括：学号、学生姓名、课程称号、成果、所在系别、授课教师姓名；完成以下输出：将每门课程的成果由高到低排序输出；计算出每个学生一切选修课程的平均成果，并由高到低排序输出。例6.1 首先要定义学生链表

25、和课程链表的结点的构造，然后编写创建其结点实例的方法和向链表中插入的方法。对于每一个学生，建立相应学生信息的结点；然后计算学生平均成果，并按照平均成果将上述结点插入到学生链表中。 例6.1 数据构造设计： headnum namedepavecourse nextstudentcour teacherscore next例6.1 课程链表中结点的定义 : typedef struct course char cour30; int score; char teacher10; struct course *next; COURSE; 例6.1 学生链表中结点的定义 : typedef stru

26、ct student int num; char name10; char dep20; float ave; COURSE *link; struct student *next; STUDENT;建立学生链表的代码片段建立学生链表的代码片段 : : 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函数：函数： 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; / /* *输入所学课程的分数输入所学课程的分数* */ / / /* *假设为假设为00那么终了那么终了* */ / w

29、hile (q=createCourseNode()!=NULL) while (q=createCourseNode()!=NULL)insertCourseNode(&(p-link),q );insertCourseNode(&(p-link),q ); / /* *计算课程的平均成果计算课程的平均成果* */ / p-ave =aver(p-link); p-ave =aver(p-link); return p; return p; 例6.2 例6.2 1编写一个函数，根据一个知数组构造一个线性链表； 2编写一个函数，对线性链表排序。提示： 只需定义结点构造及其操作。这里我们给出了结

30、点的创建、插入、排序和打印函数。 建立结点：ELEM *createNode(int n)ELEM *q=(ELEM*)malloc(sizeof(ELEM);q-n=n;q-next=NULL;return q; 在链表尾插入结点 ：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 编写一个程序，可以完

33、成二个恣意长度的以字符串表示的正整数的乘法。阐明：输入的整数能够超越系统所能表示的最大整数及最大实数的范围或精度。 例：输入：124597860和123 输出例6.3 提示：可以将乘法的结果放于链表中，因此我们要首先定义链表结点构造和它相关的操作：创建结点实例和链表显示操作，然后编写乘法运算程序。对于乘数从个位开场的每一位，逐一与被乘数相乘。当第i位乘数bi与被乘数aj相乘时，结果落于第i+j位上。被乘数 aj a2 a1乘数 bi b1当前结果链表的位 ri+j ri+j-1第i位乘数bi与被乘数的第j位aj相乘时的结果 aj*bi进位 ci+j ci+j-1例6.

34、3 因此：m=ri+j+aj*bi+ci+j-1 /*本次计算中，结果链表的第i+j位上的累计总值*/ri+j=m%10 /*本次计算中，结果链表的第i+j位的最终值*/ci+j=m/10 /*本次计算中的进位进到第i+j+1位上 第i位乘数与被乘数的乘法计算void multi(BIT *head,char *str,char ch,int i)；参数 head：结果链表的头指针，str：被乘数串，ch：乘数第i位上的数字，i：乘数位数定位乘积个位：ptr=head; while (nnext!=NULL)ptr=ptr-next; elseq=createNode(0);ptr-next=

35、q;ptr=ptr-next; n+; 定位被乘数个位： p=str; while(*p!=0) p+;乘法运算：q=ptr;while(pstr)p-; mul1=(*p-0)*(ch-0)+a1; /*乘运算*/a1=mul1/10;mul1%=10; /*a1为乘积进位*/if(ptr=NULL)ptr=createNode(0);q-next=ptr;q=ptr;mul2=ptr-num+mul1+a2; /*与结果链当前位累加*/a2=mul2/10; /*a2为累加进位*/mul2%=10; /*mul2为本次运算结果链当前位的最终值*/ptr-num=mul2;q=ptr;ptr

36、=ptr-next;处置最高进位： if(a1!=0|a2!=0) if(ptr=NULL) ptr=createNode(0);q-next=ptr; ptr-num=ptr-num+a1+a2; 两个数字串的乘法计算： 参数 head：结果链表的头指针的地址，str：被乘数串，str2：乘数串void multiply(BIT * head,char * str1,char *str2)char * p;int i;p=str2;/*定位乘数个位*/while (*p!=0) p+;/*为str2的每一位分配空间*/*head=createNode(0);i=0; while (pstr2

37、)p-;if (*p!=0) multi(*head,str1,*p,i); /*乘数的第 i位数*p乘以被乘数*/i+;例6.4例6.4有一个单链表L至少有1个结点，其头结点指针head，编写一个函数将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，以次类推。 例6.4提示： 定义链表的结点构造以及创建结点、插入、打印、逆置等链表的相关操作。链表逆置的部分操作： headNULLpqrpp qq rrppqq rrppqqNULL例6.5例6.5 编写一个函数，交换单链表中p所指向的结点和其后续位置上的结点。head指向该链表的表头，p指向该链表中的某一结点。 提示：

38、 交换指定结点的后序两个元素，要对链指针进展操作。因此要描画链表的指针及相关操作。其中交换结点操作: headNULLps例6.6例6.6编程：输入数字串方式的人民币钱数人民币小写，输出相应的人民币大写表示。假定输入的钱数小于1亿元，且角和分用小数表示，并假定输入无错误。人民币大写的规定如下：假设金额没有分，那么后面要加上“整字；假设数字中间有延续假设干个0，变成大写时，最多写一个“零字。假定程序的运转环境支持汉字显示。他甚至可以本人定义所用到的任何汉字的代码，而不用思索能否和实践一致。例如：1000.00 壹千元整 3009.40 叁千零玖元肆角整 5000608.72 五百万零陆百零捌元柒

39、角贰分例6.6提示：1人民币从小写方式转换为大写方式是有规律的。首先我们将除小数位外的各位称为位元，位元用5个属性描画：index、val、ch1、ch2和ch3，见图6.4，除了数字本身的转换外，十进制的单位ch1按“、“拾、“佰、“仟循环，ch2只在能在被4整除的位上有值，其它位上是“或为NULL。 index87654321001ch3亿万ch2“”仟佰拾“”仟佰拾“”角分ch1val475123456.56 整数部分小数点小数部分例6.6对应的数据设计：static char *str1=零,壹,贰,叁,肆,伍,陆,柒,捌,玖;static char *str2=,拾,佰,仟;stat

40、ic char *str3=,万,亿;static char *str4=角,分;static char *str5=圆,整;例6.6提示：2 val为0的位元上，十进制单位ch2取消，然后用图6.5的形状转移图完成：q0为初始形状，在这个形状下，遇0时删去ch1，遇非0时，转q1形状；在q1形状下，遇0时转q0形状，该ch1保管。 3处置时，首先将原串拆分为整数部分和小数部分；然后分别分析各部分。在分析整数部分时，计算ch1、ch2和ch3的值，同时得处置零情形；最后打印各位的内容。 q0q1图6.5 人民币转换图示0：去掉非0非00：保管例6.6位结点构造定义 ：typedef struc

41、t bitdescint val; /*本位数字*/int index; /*序号*/char* ch1; /*本位数字对应的大写方式*/char* ch2; /*“、“拾、“佰、“仟*/char* ch3; /*“万、“亿*/struct bitdesc * next; /*链表指针*/BITDESC;创建一个整数位：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;创建小数位：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;在链表尾插入结点： 参数 head：链表的头指针，node：指定的结

43、点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;在链表头插入结点： 参数 head：链表的头指针，node：指定的结点void insertAtHead(BITDESC * head,BITDESC * node)if(*head=NULL)*head=node;node-next =NULL;

44、return;node-next =*head;*head=node;分析整数部分构成位元实例的链表，并处置零情形： 参数 head 链表头的地址 intStr 整数部分的数字串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; 分析小数部分构成位元实例的链表： 参数 head 链表头的地址 floatStr 小数部分的数字串 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 实现变元为x，y，z的两个整系数多项式的相加。例如：多项式3x6-5x5y2+6x6z 提示： 这个问题本质上是合并两个已有序的链表，即是两个链表的归并排序。每个结点表示为： c X i Y j Zk 常数 x的次数 y的次数

47、 z的次数 例6.7例:第一个多项式为：X5+4X2Y2+X 第二个多项式为：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个变量排成以下图1所示的三角形，这6个变量分别取1至6上的整数，且互不一样。试找出使三角形3条边上的3个数之和相等的一切能够解，以下图2所示为其中的一个解。 A 4 B F 1 5

48、 C D E 6 3 2 图1 图2例7.1 提示： 这个问题的搜索空间是1至6的一切陈列。对于每种陈列，看能否满足要求，假设满足，就属于解空间，输出它。在产生1至6的陈列时，采用回溯方法。设a1a6是一个陈列，生成下一陈列时，先思索a6的其它能够值，假设没有，那么释放a6的值，再思索a5的下一个能够值每一个数的下一能够值永远按一个规律变化，在此只能增大。普通地，对于k，先思索ak的其它能够值，假设没有，那么释放ak，思索ak-1的下一能够值，直至k=0为止。例7.1 _ 1至6数列的生成的部分过程 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; /*占用标志，占用标志，useablei为为1，表示数字，表示数字i被占用被占用*/int j,k;int flag=1; /*终了标志

50、终了标志*/for (j=1;j=N;j+) useablej=0; /*初始化初始化(1-6)这这6个数都未选中个数都未选中*/k=1; while (flag)for(j=1;k=N;k+,j+) /*添满添满6个数个数,即为即为ak,ak+1,.,aN置值置值*/while (j=N & useablej) j+; /*找到下一个可用的数找到下一个可用的数*/useablej=1; /* j为被占用为被占用*/ak=j;if (satisfy()print();k-;do /*回溯回溯*/ useableak=0; /*释放当前数释放当前数*/ k-;if (k1) flag=0; /*

51、回溯至回溯至k-1*/ for (j=ak+1;j=N & useablej;j+); /*找下一个可用数找下一个可用数*/ if (j=N) break; /*找到找到*/while (flag);if (flag) /*找到的数添入当前位找到的数添入当前位*/ useableak=0; useablej=1; /*修正占用标志修正占用标志*/ ak=j; k+;return 0; 例7.2 例7.2 将1到9这9个数不反复填入3*3的方格中，要求各行、各列、对角线上各数之和相等，求出一切能够的填法。提示： 这个问题与上一问题一样，只是对于取数的范围、解的满足条件及打印内容不同。 2 7 6

52、 2 9 4 9 5 1 7 5 3 4 3 8 6 1 8例7.3 例7.3 输入一个MN的迷宫，编写一个非递归函数，找到一条从1，1到M,N的途径。 提示 ：从(1,1)出发，将一切能够的走法全部用队列记录下来。队列中的记录信息除点坐标外，还要记录该点的来源。假设从(x,y)可以直接到达x1,y1(xk,yk)，且(x,y)是队中第n条记录，那么在队尾参与(x1,y1,n)(xk,yk,n)，见以下图。假设所参与的记录有(M,N)点，那么终了；否那么处置队头的下一条记录。例7.3 例如：一个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; /*初始起初始起点为点为mg11*/mg11=-1; /*表示曾经表示曾经路过这点路过这点*/while (front=rear & !find)x=mgQueuefront.x;y=mgQueuefront.y;for (v=1;v=8;v+) /*依次扫依次扫描每个方向描每个方向*/i=x+zxv;j=y+zy

54、v;if (mgij=0) /*路通那路通那么入队么入队*/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 八皇后问题。在一个88的国际象棋盘上，有八个皇后，每个皇后占一格；要求皇后间不会出现相互“攻击的景象，即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法。提示： 可以用一维数组表示8位皇后在不同列上的行值，即ai表示第i位皇后

55、所在的行。计算第i位皇后的位置时，曾经将前i-1位皇后都放好了。只需第i位的位置不与前i-1位冲突，就继续计算后面的各位皇后的位置。计算时从第0行开场尝试，假设不冲突，那么将ai压栈并计算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) /*到一个适宜的位置？到一个适宜的位置？*/if (satisfy(sta,l,top+1) /*找到了找到了*/break;else l+;

56、if (lm)flag=0; 例7.5 例7.5 将1到9这9个数不反复地分成3组，每组3个数字组成一个3位数，要求这3个3位数都是完全平方数，例如：361=19*19，529=23*23，784=28*28。 提示：只需11至31的平方是三位数，用三个这样的三位数尝试能否满足要求，即能否满足：1它们是1至9不同的数，2不含0。这个问题与7.1问题一样。 例8.1 例8.1 假设银行一年零存整取的月息为0.63%。如今某人手中有一笔钱，他计划在今后的五年中每年的年底取出1000元，到第五年时刚好取完，请算出他存钱时应存入多少。 例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年底余额的计算式：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第一个来，将鱼分为5

58、份，把多余的一条鱼扔掉，拿走了本人的一份；B第二个来，也将鱼分为5份，把多余的一条鱼扔掉，拿走了本人的一份；C、D、E依次到来，也按同样的方法拿鱼。问他们合伙至少捕了多少条鱼？ 例8.2 提示：设捕鱼x条，那么有： 得到的鱼数 分后剩余的鱼数 原捕鱼数 x0 第一个人 (x0-1)/5 x1=(x0-1)/5*4 第二个人 (x1-1)/5 x2=(x1-1)/5*4 第三个人 (x2-1)/5 x3=(x2-1)/5*4 第四个人 (x3-1)/5 x4=(x3-1)/5*4 第五个人 (x4-1)/5 x5=(x4-1)/5*4于是得到普通的递推式： xi=(xi-1-1)/5*4要计算n

59、，n=x0，满足按上面方法可以递推五次。可以从6开场尝试。例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 提示：设全部鱼有x条，根据题意如下： 卖出 剩余

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最后剩余的鱼数x4应为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 一对小兔子一年后长成大兔子；一对大兔子每半年生一对小兔子。大兔子的繁衍期为四年，兔子的寿命是六年。假