返回
C语言算法大全（经典）

C语言算法大全（经典）

ID：35876370

大小：927.25 KB

页数：252页

时间：2019-04-22

上传者：green wind
C语言算法大全（经典）_第1页
C语言算法大全（经典）_第2页
C语言算法大全（经典）_第3页
C语言算法大全（经典）_第4页
C语言算法大全（经典）_第5页
资源描述：

《C语言算法大全（经典）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

C语言经典算法目录一、单元加61.erre62.erre263.数组完全单元74.栈单元加8二、底层编程91.asm92.C标志符命名源程序213.ping234.winsock2275.检测鼠标296.检出错误307.时间陷阱31三、汉诺塔331.非递归332.汉诺塔343.汉诺塔2354.换位递归365.诺汉塔画图版376.四塔1387.四塔240四、逆阵411.简单逆阵412.逆矩阵423.逆阵45五、经典程序47251 1.编程汉字问题472.编随机数483.递堆法494.汉字字模505.简单数据库546.冒泡法改进557.穷举搜索法578.扫描码589.傻瓜递归5910.神经元模型5911.试题6312.挽救软盘6413.小白鼠钻迷宫6514.小字库DIY6815.小字库DIY-69六、求进制711.16进制10进制712.二进制数723.二进制数272七、数据结构73一、单链表731.ww732.单链表743.单链表1764.单链表2775.单链表倒序786.单链表的处理全集797.建立链表1888.节点899.链表（递归）93251 10.链表十五人排序9611.冒泡排序9812.质因子99二、排列类数据结构1011大整数1012.递归车厢1033.队列1054.二叉排序树1075.二叉树实例1106.各种排序法1157.哈夫曼算法1248.哈慢树1339.建树和遍历13510.迷宫13711.迷宫问题13912.逆波兰计算器14213.排序法14414.数据结构115215.数据结构215315.数据结构315416.双链表正排序15517.推箱子15718.无向图15819.线索化二叉树16120.线性顺序存储结构16321.栈操作166八、数学问题169一、凉东问题1691.321692.re169251 3.数组递归退出1704.数组递归退出2171二、苹果纠纷1721.ff1722.苹果分法172三、数学算法1731.符号图形1732.绘制圆1763.余弦曲线1764.余弦直线177四、桃子猴问题1781.乘方函数桃子猴1782.递归桃猴1783.猴子和桃1794.桃子猴180五、小明买书1801.小明买书1802.小明买书C++181六、圆周率1831.狐狸圆周率1832.圆周率183七、运算类数学问题1841.阿姆斯特朗数1842.百鸡百钱1843.大加数1854.大小倍约1885.大整数1886.灯塔问题1907.递推1928.叠代整除193251 9.多位阶乘19410.多位阶乘219611.黑白19712.简单计算器19713.阶乘递归19914.逻辑移动19915.平方根20016．十五人排序20117.四分砝码20218.完数20319.小孩分糖果204九、数组2051.矩阵转换2052.螺旋数组12063.螺旋数组22074.数字移动2085.数组操作2106.桶排序2107.杨辉三角形212十、问题算法212一、骑士遍历2121.骑士遍历12122.骑士遍历22153.骑士遍历回逆223二、万年历2241．万年历2242.万年历的算法229三、其它问题算法2341.N皇后问题回溯算法2342.动态计算网络最长最短路线236251 3.货郎担分枝限界图形演示2394.货郎担限界算法2485.矩阵乘法动态规划256十一、小写数字转为大写数字2591．小写数字转换成大写数字12592．小写数字转换成大写数字22613.小写数字转换成大写数字3265十二、效验算法2661.Crctable266十三、硬币情况2681.for循环的2682.硬币分法268十四、字符2691.单词倒转2692.出字符2703.回文2704.字符编辑2715.字符编辑技术(插入和删除)2726.字符串查找272十五、数据算法2741.单链表2742.单循环链表2783.定长串2824.二叉树2865.二分查找12886.二分查找22907.链串2928.链队列2959.链栈29810.顺序队列299251 11.顺序栈30212.图305251 七、数据结构251 一、单链表1.ww/*我不知道我这样做合适不合适，好象自己在帮助别人干坏事我不可能给你说得很细，学习到的东西是自己的，难道对自己也可以作弊吗？好好努力吧*/#include#include#includestructf//数据结构{doubledata;structf*next;};main(){intn;scanf("%d",&n);fun(n);}fun(n){doubley=0.00,x=1.00;//这里用双精度实数定义可以容纳更大的数据structf*head,*cthis,*a;intnumber,i,j=0;do{a=(structf*)malloc(sizeof(structf));if(head==NULL)head=a;else{cthis=head;cthis=cthis->next;}cthis=a;cthis->data=j;//这里定义存处在各个链表里的数据//你可以用(int)rand()随机数来代替jnumber=cthis->data;for(i=0;i#includestructroommate{charname[20];longnum;intage;charbirthplace[20];structroommate*next;};structroommate*head,*cthis,*cnew;voidnew_record(void){charch;charnumstr[20];do{cnew=(structroommate*)malloc(sizeof(structroommate));if(head==NULL)head=cnew;else{cthis=head;while(cthis->next!=NULL)cthis=cthis->next;cthis->next=cnew;}cthis=cnew;printf(" entername:");gets(cthis->name);printf(" enternumber:");gets(numstr);cthis->num=atol(numstr);printf(" enterage:");gets(numstr);cthis->age=atoi(numstr);printf(" enterbirthplace:");251 gets(cthis->birthplace);cthis->next=NULL;printf(" print'e'toaddrecord:");ch=getchar();getchar();}while(ch=='e');cthis->next=head;}voidlistall(void){inti=0;cthis=head;do{printf(" recordnumber%d ",i);printf("name:%s ",cthis->name);printf("num:%ld ",cthis->num);printf("age:%d ",cthis->age);printf("birthplace:%s ",cthis->birthplace);cthis=cthis->next;}while(cthis!=head);}voidmain(){charch;intflag=1;head=NULL;while(flag){printf(" type'e'toenternewrecord,");printf("type'l'tolistallrecords,");printf("type'i'toinsertarecord:");ch=getchar();getchar();switch(ch){case'e':new_record();break;case'l':listall();break;default:flag=0;}}}3.单链表1#include251 #includestructroommate{charname;longnum;intage;charbirthplace;structroommate*next;};structroommate*head,*cthis,*cnew;voidins_record(void){inti,j=0;charnumstr,b;cthis=head;printf(" Inputanum:");scanf("%d",&i);while(jnext;++j;}if(j>i-1)return;cnew=(structroommate*)malloc(sizeof(structroommate));printf(" pleaseinputtheinformation:");printf(" entername:");scanf("%s",&cnew->name);printf(" enternumber:");scanf("%ld",&cnew->num);printf(" enterage:");scanf("%d",&cnew->age);printf(" enterbirthplace:");scanf("%s",&cnew->birthplace);cnew->next=cthis;}main(){ins_record();}251 4.单链表2#include#includestructnode{intkey;structnode*next;};voidcreat_link(structnode*);main(){structnode*head=NULL;creat_link(head);/*这里可以这么调用吗？*/}voidcreat_link(structnode*head_node){structnode*p,*q,*Temp;intnumber;printf("Pleaseinputdata:[-1isEnd] ");scanf("%d",&number);while(number!=-1){q=(structnode*)malloc(sizeof(structnode));q->key=number;if(head_node==NULL){head_node=q;p=q;}else{p->next=q;p=q;}scanf("%d",&number);}p->next=NULL;Temp=head_node;while(Temp!=NULL){printf("%d ",Temp->key);Temp=Temp->next;}}251 5.单链表倒序#includestructfsb{intdata;intflag;structfsb*next;};main(){structfsb*p,*head,*sta,*end;inti,cishu,j;end=(structfsb*)malloc(sizeof(structfsb));end->data=0;end->flag=0;end->next=NULL;head=p=end;for(i=2;i<=10;i++){end=(structfsb*)malloc(sizeof(structfsb));end->data=i-1;end->flag=0;end->next=NULL;p->next=end;p=end;}p->next=NULL;printf(" 倒序前：");p=head;for(i=1;i<=10;i++){printf("%d",p->data);p=p->next;}/*************************/p=NULL;while(head->next!=NULL){sta=head;head=head->next;sta->next=p;p=sta;251 }head->next=sta;printf(" 倒序后：");p=head;for(i=1;i<=10;i++){printf("%d",p->data);p=p->next;}/*************************/}6.单链表的处理全集/*谁有兴趣一起来丰富这个程序的的功能？？*/#include#include#defineMAX20#defineELEMTPint#definev(*p)structnode{ELEMTPdata;structnode*next;};structnode*p,*q,*s,*head;intj=0,i,k;main(){intx,y,cord;voidoutlin(structnode*h);voidcreate();voidinsert(structnode*h,intx,inty);voiddeletes(structnode*h,intx);structnode*MaxCompare(structnode*h);structnode*MinCompare(structnode*h);intdelIterance(structnode*h);voidbatchInsert(structnode*h,intx);voidbatchDelete(structnode*h,intx,inty);voidCz(structnode*h);voidXg(structnode*h);printf("建立链表，输入-999完成链表: ");create();251 i=j;outlin(head);do{printf(" 主菜单 ");printf("1插入一个元素 ");printf("2删除一个元素 ");printf("3升序排序 ");printf("4降序排序 ");printf("5查找元素 ");printf("6修改元素 ");printf("7删除重复元素 ");printf("8批量加入元素 ");printf("9批量删除元素 ");printf("0结束程序运行 ");printf("----------------------------------------- ");printf("请输入您的选择(1,2,3,4,5,6,7,8,9,0)");scanf("%d",&cord);switch(cord){case1:{printf("请输入插入的位置i:");scanf("%d",&x);printf("请输入插入的数据y:");scanf("%d",&y);insert(head,x,y);i=j;outlin(head);}break;case2:{printf("x=?");scanf("%d",&x);deletes(head,x);i=j;outlin(head);}break;case3:{printf("链表由大到小是");s=MaxCompare(head);j=i;outlin(s);//outlin(head);251 }break;case4:{printf("链表由大到小是");s=MinCompare(head);j=i;outlin(s);}break;case5:{Cz(head);outlin(head);}break;case6:{Xg(head);outlin(head);}break;case7:{k=delIterance(head);i=i-k;j=i;outlin(head);}break;case8:{printf("请输入插入的位置i:");scanf("%d",&x);batchInsert(head,x);i=j;outlin(head);}break;case9:{printf("请输入删除的起始位置i:");scanf("%d",&x);printf("请输入删除的结束位置y:");scanf("%d",&y);batchDelete(head,x,y);i=j;outlin(head);}break;case0:251 {exit(0);}break;}}while(cord<=9&&cord>=0);}voidoutlin(structnode*h){p=h->next;while(p!=NULL){printf("data=%4d",p->data);p=p->next;}printf(" 输出结束 ");}voiddeletes(structnode*h,intx)//删除节点{p=h;while(p->next!=NULL&&p->next->data!=x)p=p->next;if(p->next==NULL)printf("x不存在!");else{q=p->next;p->next=q->next;free(q);--j;}}voidinsert(structnode*h,intx,inty){s=(structnode*)malloc(sizeof(structnode));s->data=y;q=h;p=h->next;while(p!=NULL&&p->data!=x){q=p;p=p->next;}q->next=s;s->next=p;++j;}251 voidcreate()//建立链表{intx;head=(structnode*)malloc(sizeof(structnode));head->next=NULL;p=head;printf("x=?");scanf("%d",&x);while(x!=-999){s=(structnode*)malloc(sizeof(structnode));s->data=x;s->next=NULL;p->next=s;p=s;printf("x=?");++j;scanf("%d",&x);}}/////////////以下函数由七绝玩家编写/////////////structnode*MaxCompare(structnode*h)//由大到小排序{structnode*t;intx;t=h;s=NULL;while(j!=0){x=t->next->data;q=t->next;while(q!=NULL){if(q->data<=x)x=q->data;elsex=x;q=q->next;}p=t;while(p->next!=NULL&&p->next->data!=x)p=p->next;q=p->next;p->next=q->next;t=p;t=h;p=q;p->next=s;251 s=p;j--;}t->next=s;head=t;return(t);}structnode*MinCompare(structnode*h)//由小到大排序{structnode*t;intx;t=h;s=NULL;while(j!=0){x=t->next->data;q=t->next;while(q!=NULL){if(q->data>=x)x=q->data;elsex=x;q=q->next;}p=t;while(p->next!=NULL&&p->next->data!=x)p=p->next;q=p->next;p->next=q->next;t=p;t=h;p=q;p->next=s;s=p;j--;}t->next=s;head=t;return(t);}intdelIterance(structnode*h)//删除重复元素{intx,y=0;--j;s=h->next;while(j>0)251 {x=s->data;p=s;while(p->next!=NULL){if(p->next==NULL){x=x;}elseif(p->next->data==x){q=p->next;p->next=q->next;free(q);--j;++y;}else{p=p->next;}}s=s->next;--j;}returny;}voidbatchInsert(structnode*h,intx)//批量加入{inty=0;q=h;p=h->next;while(p!=NULL&&p->data!=x){q=p;p=p->next;}printf("y=?");scanf("%d",&y);while(y!=-999){s=(structnode*)malloc(sizeof(structnode));s->data=y;q->next=s;s->next=p;251 q=s;printf("y=?");scanf("%d",&y);++j;}}voidbatchDelete(structnode*h,intx,inty)//批量删除{intk=0,w=0;structnode*t;p=h;q=h;while(p->next!=NULL&&p->next->data!=x){++k;p=p->next;}while(q->next!=NULL&&q->next->data!=y){++w;q=q->next;}if(p->next==NULL||q->next==NULL)printf("输入的位置不正确，请重新开始！");elseif(knext;while(p->next!=s){t=p->next;p->next=t->next;free(t);--j;}}elseif(w=k){printf("没有删除元素");}else{s=p->next;while(q->next!=s){251 t=q->next;q->next=t->next;free(t);--j;}}}//////////////七绝玩家编写结束////////////////////////////以下函数由lihk编写////////////voidCz(structnode*h)//查找//{structnode*num;inti;num=head;printf("输入您要查找的号码:");scanf("%d",&i);while(i!=num->data&&num->next!=NULL){num=num->next;}if(i==num->data)printf("号码:%d",num->data);elseprintf("该号码不在链表里.");}voidXg(structnode*h)//修改//{structnode*num;inti;num=head;printf("查找您要修改的号码:");scanf("%d",&i);while(i!=num->data&&num->next!=NULL){num=num->next;}if(i==num->data){printf(":%d ",num->data);printf("输入您要修改的新信息:");printf("号码:");scanf("%d",&num->data);printf(" 修改成功!");}elseprintf("该号码不在链表里!");}//////////////lihk编写结束/////////////////251 7.建立链表1/*链表建立程序*/#include"stdio.h"#include#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum;intscore;structstudent*next;};intn;/*全局变量n*/structstudent*creat(){structstudent*head;structstudent*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);scanf("%ld%d",&p1->num,&p1->score);/*%d和%d之间不应该有逗号*/head=NULL;while(p1->num!=0){n=n+1;if(n==1)head=p1;elsep2->next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf("%ld%d",&p1->num,&p1->score);}p2->next=NULL;return(head);}voidprint(head)structstudent*head;{structstudent*p;p=head;/*在这里付值才可以*/printf("Now,These%drecordsare: ",n);if(head!=NULL)do{printf("%ld%5d ",p->num,p->score);p=p->next;}while(p!=NULL);251 }voidmain(){structstudent*head;printf("inputrecords: ");head=creat();print(head);}8.节点#include#defineTYPEstructstu#defineLENsizeof(structstu)structstu{intnum;intage;structstu*next;};TYPE*creatlink(intn);TYPE*deletelink(TYPE*head,intnum);TYPE*insertlink(TYPE*head,TYPE*pi);voidprintlink(TYPE*head);voiddestroylink(TYPE*head);voidmain(void){TYPE*head=NULL,*pnum=NULL;intn=3,num;/*创建一个含n个节点的链表*/printf("inputnumberofnode:");head=creatlink(n);printlink(head);/*删除链表中值为num的节点*/printf("Inputthedeletednumber:");scanf("%d",&num);head=deletelink(head,num);printlink(head);/*在链表中插入一个节点*/printf("Insertarecord ");pnum=(TYPE*)malloc(LEN);if(pnum==NULL)printf("PointerisNULL--memoryallocfail!");printf("Inputtheinsertednumber:");251 scanf("%d",&pnum->num);printf("Inputtheinsertedage:");scanf("%d",&pnum->age);head=insertlink(head,pnum);printlink(head);/*销毁链表,释放动态分配的内存*/destroylink(head);}/*创建一个含n个节点的链表*/TYPE*creatlink(intn){TYPE*head=NULL,*pf,*pb;inti;for(i=0;inum);printf("inputage:");scanf("%d",&pb->age);if(i==0)pf=head=pb;elsepf->next=pb;pb->next=NULL;pf=pb;}return(head);}/*删除链表中值为num的节点*/TYPE*deletelink(TYPE*head,intnum){TYPE*pf,*pb;if(head==NULL){printf(" emptylist! ");returnNULL;}pb=head;while(pb->num!=num&&pb->next!=NULL){pf=pb;pb=pb->next;251 }if(pb->num==num){if(pb==head)head=pb->next;elsepf->next=pb->next;free(pb);printf("Thenodeisdeleted ");}elseprintf("Thenodenotbeenfound! ");returnhead;}/*在链表中插入一个节点*/TYPE*insertlink(TYPE*head,TYPE*pi){TYPE*pb,*pf;pb=head;if(head==NULL){head=pi;pi->next=NULL;}else{while((pi->num>pb->num)&&(pb->next!=NULL)){pf=pb;pb=pb->next;}if(pi->num<=pb->num){if(head==pb)head=pi;elsepf->next=pi;pi->next=pb;}else{pb->next=pi;pi->next=NULL;}251 }returnhead;}/*打印链表中各节点信息*/voidprintlink(TYPE*head){printf("NumberttAge ");while(head!=NULL){printf("%dtt%d ",head->num,head->age);head=head->next;}}/*销毁链表,释放动态分配的内存*/voiddestroylink(TYPE*head){TYPE*p,*q;p=head;while(p!=NULL){q=p->next;free(p);p=q;}}9.链表（递归）#include#includestructlistNode{intdata;structlistNode*nextPtr;};typedefstructlistNodeLISTNODE;typedefLISTNODE*LISTNODEPTR;LISTNODEPTRlist(LISTNODEPTR,int);//此处不同voidprintlist(LISTNODEPTR);voidfreelist(LISTNODEPTR);//增加main(){251 LISTNODEPTRnewPtr=NULL;inti,a;for(i=0;i<3;i++){printf("pleaseenteranumber ");scanf("%d,",&a);newPtr=list(newPtr,a);//此处注意}printlist(newPtr);freelist(newPtr);//此处return0;}LISTNODEPTRlist(LISTNODEPTRsPtr,inta){if(sPtr!=NULL)sPtr->nextPtr=list(sPtr->nextPtr,a);//递归，向后面的节点上加数据。else{sPtr=(LISTNODEPTR)malloc(sizeof(LISTNODE));//注意，是节点的尺寸,类型转换sPtr->nextPtr=NULL;sPtr->data=a;}returnsPtr;}voidfreelist(LISTNODEPTRsPtr){if(sPtr!=NULL){freelist(sPtr->nextPtr);//递归，先释放后面的节点free(sPtr);//再释放本节点}else//return;//此两行可不要}voidprintlist(LISTNODEPTRcurrentPtr){if(currentPtr==NULL)printf("Thelistisempty ");else{printf("Thislistis: ");while(currentPtr!=NULL){printf("%d-->",currentPtr->data);251 currentPtr=currentPtr->nextPtr;//这里不一样}printf("NULL ");}}你原程序错误如下：------------------------->list1.c>>#include>#include>>structlistNode{>intdata;>structlistNode*nextPtr;>};>>typedefstructlistNodeLISTNODE;>typedefLISTNODE*LISTNODEPTR;>>voidlist(LISTNODEPTR*,int);>voidprintlist(LISTNODEPTR);>>main()>{>LISTNODEPTRnewPtr=NULL;>>>inti,a;>for(i=0;i<3;i++){>printf("pleaseenteranumber ");>scanf("%d,",&a);>list(&newPtr,a);//此处给的是newPtr的地址，注意！>}>>printlist(newPtr);>>free(newPtr);//链表的释放不能这样写，这样，只释放了newPtr指向的一个节点。//可以先找到链表的尾，然后反向释放；或者，利用printlist的顺序释放，//改函数printlist，或在此函数里释放。>>return0;>}251 >>voidlist(LISTNODEPTR*sPtr,inta)>{>LISTNODEPTRnewPtr,currentPtr;>>newPtr=malloc(sizeof(LISTNODEPTR));//此处错，LISTNODEPTR是指针类型，不是结构类型，//malloc返回void指针，应该强制转换类型，此处会告警不报错，但应有良好的//编程风格与习惯。>if(newPtr!=NULL){>newPtr->data=a;>newPtr->nextPtr=NULL;>>currentPtr=*sPtr;>}>if(currentPtr==NULL){//此处条件不确切，因为currentPtr没有初始化，//如newPtr一旦为NULL，此句及以下就有问题。>newPtr->nextPtr=*sPtr;>*sPtr=newPtr;}//在第一个数来的时候，main里的newPtr通过sPtr被修改指向此节点。//在第二个数来的时候，main里的newPtr通过sPtr被修改指向此节点。//在第三个数来的时候，main里的newPtr通过sPtr被修改指向此节点。//最后，main里的newPtr指向第三个数。>}>>>>voidprintlist(LISTNODEPTRcurrentPtr)>{>if(currentPtr==NULL)>printf("Thelistisempty ");>else{>printf("Thislistis: ");>>while(currentPtr!=NULL){>printf("%d-->",currentPtr->data);//main里的newPtr指向第三个数。你先打印了最后一个数。RE第二个问题>currentPtr=currentPtr->nextPtr->data;//此句非法，类型不同，有可能让你只循环一次，如data为0。RE第一个问题>}>printf("NULL ");251 >}>}//对类似程序能运行，但结果似是而非的情况，应该多利用跟踪调试，看变量的变化。10.链表十五人排序/*发个半拉作品在这里，疑问很多，怎么才能判断一个人和其他的人见过面呢？累的我都头疼*/#include#includestructnet{intnember[3];structnet*next;}main(){intg=0,d=0,w=0,b=0,j,k,i=0,a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};//v=0,h[]={1,8,6,5,3,12,2,13,4,9,14,11,15,7,10};structnet*head=NULL,*trail,*body;while(b<7){for(j=0;j<5;j++){body=(structnet*)malloc(sizeof(structnet));for(k=0;k<3;k++){body->nember[k]=a[i%15];i+=1+w;/*if(b>3){body->nember[k]=h[v%15];v+=1+d;}else{body->nember[k]=a[i%15];i+=1+w;}*///(i>315)?(i-=1+w):(i+=1+w);}251 if(head==NULL){head=body;trail=body;}else{trail->next=body;trail=body;}}w+=6;//(b>3)?(d+=6):(w+=6);b++;}trail->next=NULL;while(head!=NULL){printf("");for(k=0;k<3;k++){g++;(g%15)?(printf("%d",head->nember[k])):(printf("%d ",head->nember[k]));}printf("");head=head->next;}}11.冒泡排序#include"stdio.h"#include"stdlib.h"structnode{intvalues;structnode*next;};structnode*create(int[],int);voidsort(structnode**);inttest_data[20000]={5,9,3,4,5,7,8};main()251 {structnode*h,*p;h=create(test_data,20000);for(p=h;p;p=p->next)printf("%2d",p->values);printf(" ");sort(&h);for(p=h;p;p=p->next)printf("%2d",p->values);printf(" ");}structnode*create(inta[],intn){structnode*h,*q;for(h=NULL;n;n--){q=(structnode*)malloc(sizeof(structnode));q->values=a[n-1];q->next=h;h=q;}returnh;}voidsort(structnode**h){structnode*q,*p,*r,*s,*h1;h1=p=(structnode*)malloc(sizeof(structnode));p->next=*h;while(p->next!=NULL){q=p->next;r=p;while(q->next!=NULL){if(q->next->valuesnext->values)r=q;q=q->next;}if(r!=p){s=r->next;r->next=s->next;s->next=p->next;p->next=s;}p=p->next;}*h=h1->next;/*问题：h1在程序中做了啥用？*/free(h1);}251 12.质因子#include#includestructnode{longfactorarray;structnode*next;};structnode*head,*q,*p;voidfactoring(longn){longi;for(i=2;i<=n/2;i++){if(n%i==0){q=(structnode*)malloc(sizeof(structnode));q->factorarray=i;q->next=NULL;if(head==NULL){head=q;p=q;}else{p->next=q;p=q;}}}}voiddeletes(){while(head!=NULL){p=head;head=p->next;free(p);}}voidmain()251 {longnum;head=NULL;printf("Pleaseinputthenumberyouwanttofindfactors:");while(scanf("%ld",&num)){printf("Thefactorsofthenumber%ldis: ",num);factoring(num);p=head;while(p!=0){printf("*%ld",p->factorarray);p=p->next;}printf(" Plearinputthenumberyouwanttofindfactors:");deletes();}}二、排列类数据结构1大整数#include#include#defineHUN10000typedefstructnode{intdata;structnode*next;}NODE;//定义链表结构NODE*insert(u,num)//在u节点之后插入一个新的NODE，其值为NUMNODE*u;intnum;{NODE*v;v=(NODE*)malloc(sizeof(NODE));//分配内存v->data=num;//赋值u->next=v;//在u后面加入一个NODEreturn(v);}NODE*addint(p,q)//完成加法操作返回指向*p+*q结果的指针251 NODE*p,*q;{NODE*pp,*qq,*r,*s,*t;inttotal,number,carry;pp=p->next;qq=q->next;s=(NODE*)malloc(sizeof(NODE));//建立存放和的链表表头s->data=-1;t=s;carry=0;//进位变量while(pp->data!=-1&&qq->data!=-1)//都不是表头{total=pp->data+qq->data+carry;//对应位和上次进位数求和number=total%HUN;//记录可以存入链表的数carry=total/HUN;//多出的为进位数t=insert(t,number);//把可存入的数插入链表pp=pp->next;//取后面的数qq=qq->next;//}r=(pp->data!=-1)?pp:qq;//两数大小不一取尚未处理的指针while(r->data!=-1)//判断另一个是否到头{total=r->data+carry;//与进位数相加number=total%HUN;//记录可存入的数carry=total/HUN;//记录进位数t=insert(t,number);//插入链表r=r->next;}if(carry)//如果还有进位数t=insert(t,1);//最后一次处理t->next=s;//完成链表return(s);//返回求和指针}NODE*inputint(void)//输入超大正整数{NODE*s,*ps,*qs;structnumber//定义临时中间结构{intnum;structnumber*np;}*p,*q;inti,j,k;longsum;charc;p=NULL;//链首为个位，链尾为高位251 while((c=getchar())!=' ')//按字符接受数字if(c>='0'&&c<='9')//若为数字就存入{q=(structnumber*)malloc(sizeof(structnumber));q->num=c-'0';//存入一位整数q->np=p;p=q;}s=(NODE*)malloc(sizeof(NODE));//建立正式链表的表头s->data=-1;//表头ps=s;while(p!=NULL)//临时链表不为空是{sum=0;i=0;k=1;while(i<4&&p!=NULL)//按四位合并临时链表{sum=sum+k*(p->num);i++;p=p->np;k=k*10;}qs=(NODE*)malloc(sizeof(NODE));//正式链表的主体qs->data=sum;ps->next=qs;ps=qs;}ps->next=s;//完成链表return(s);}printint(s)NODE*s;{if(s->next->data!=-1){printint(s->next);if(s->next->next->data==-1)printf("%d",s->next->data);else{inti,k=HUN;for(i=1;i<=4;i++,k/=10)putchar('0'+s->next->data%(k)/(k/10));}}}main(){251 NODE*s1,*s2,*s;NODE*inputint(),*addint(),*insert_after();s1=inputint();s2=inputint();printf("S1=");printint(s1);printf(" ");printf("S2=");printint(s2);printf(" ");s=addint(s1,s2);printf("S1+S2=");printint(s);printf(" ");}2.递归车厢/**********递归题改为非递归题实例车厢********/#include#defineMAX4intstack[MAX],p=-1;struct{intnum;intsign;}train[MAX];voidsub(){intinc;if(p==MAX-1){for(inc=0;inc<=p;inc++)printf("%3d",stack[inc]);printf(" ");}else{for(inc=0;inc#include#defineElemTypeint#defineQ(*qe)structquenode{ElemTypedata;structquenode*next;}*p,*s,*h;structquefr{structquenode*front,*rear;};main(){structquefr*que;intx,cord;voidOutlin(structquefrqq);voidcreat(structquefr*qe);voidinsert(structquefr*p,ElemTypex);ElemTypedeletes(structquefr*qe);do{printf(" ");251 printf("主菜单 ");printf("1建立链表队列 ");printf("2入队一个元素 ");printf("3出队一个元素 ");printf("4结束程序运行 ");printf("------------------------------- ");printf("请输入您的选择(1,2,3,4)");scanf("%d",&cord);switch(cord){case1:{que=(structquefr*)malloc(sizeof(structquefr));creat(que);Outlin(*que);}break;case2:{printf("x=?");scanf("%d",&x);insert(que,x);Outlin(*que);}break;case3:{printf("x=%d ",deletes(que));Outlin(*que);}break;case4:{exit(0);}}}while(cord<=4);}voidOutlin(structquefrqq){p=qq.front->next;/*指向第一个数据元素节点*/while(p!=NULL){printf("data=%d ",p->data);p=p->next;}printf(" outend ");251 }voidinsert(structquefr*qe,intx)/*入队x值的节点*/{s=(structquenode*)malloc(sizeof(structquenode));s->data=x;s->next=NULL;Q.rear->next=s;Q.rear=s;}ElemTypedeletes(structquefr*qe){ElemTypex;if(Q.front==Q.rear){printf("队列为空。 ");x=0;}else{p=Q.front->next;Q.front->next=p->next;if(p->next==NULL)Q.rear=Q.front;x=p->data;free(p);}return(x);}voidcreat(structquefr*qe){inti,n,x;printf("n=");scanf("%d",&n);h=(structquenode*)malloc(sizeof(structquenode));h->next=NULL;Q.front=h;Q.rear=h;for(i=1;i<=n;i++){scanf("%d",&x);insert(qe,x);}}251 4.二叉排序树#include#includestructnodb{intdata;structnodb*lch,*rch;};structnodb*root,*q,*p;voidinsert1(structnodb*s);voidcreat(){structnodb*s;inti,n,k;printf("n=?");scanf("%d",&n);for(i=1;idata=k;s->lch=NULL;s->rch=NULL;insert1(s);}}voidinsert1(structnodb*s){//非递归插入structnodb*p,*q;if(root==NULL)root=s;else{p=root;while(p!=NULL){q=p;//当p向子数节点移动时，q记录p的双亲的位置if(s->datadata)p=p->lch;elsep=p->rch;}if(s->datadata)251 q->lch=s;elseq->rch=s;//当p为空时，q就是可插入的地方}}voidprint(structnodb*t){if(t!=NULL){print(t->lch);printf("%6d",t->data);print(t->rch);}}voidbstsrch(structnodb*t,intk){intflag;p=NULL;q=t;flag=0;while((q!=NULL)&&(flag==0)){if(q->data==k){printf("发现%5d",q->data);flag=1;}elseif(kdata){p=q;q=q->lch;}else{p=q;q=q->rch;}}if(flag==0)printf("没有发现节点");}voidbstins(structnodb*t,intk){structnodb*r;bstsrch(root,k);251 if(q==NULL){r=(structnodb*)malloc(sizeof(structnodb));r->data=k;r->lch=NULL;r->rch=NULL;if(root==NULL)root=r;elseif(kdata)p->lch=r;elsep->rch=r;}}main(){intn;root=0;creat();print(root);printf("请出入关键值n=?");scanf("%d",&n);bstsrch(root,n);printf(" ");bstins(root,n);print(root);}5.二叉树实例#include#include#defineELEMTPintstructnode{ELEMTPdata;structnode*lc,*rc;};structnode*root;intm=0;main(){intcord;251 structnode*creat();voidpreorderz(structnode*t);voidinorder(structnode*t);voidpostorder(structnode*t);voiddeletes(structnode*t,structnode*p,structnode*f);do{printf(" 主菜单 ");printf("1建立二叉树 ");printf("2先序非递归遍历 ");printf("3中序递归遍历 ");printf("4后序递归遍历，求叶节点数 ");printf("5删除节点 ");printf("6结束程序运行 ");printf("--------------------------------------- ");printf("请输入您的选择(1,2,3,4,5,6)");scanf("%d",&cord);switch(cord){case1:{root=creat();//建立二叉树printf("建立二叉树程序以执行完， ");printf("请返回主菜单，用遍历算法验证程序的正确性 ");}break;case2:{preorderz(root);}break;case3:{inorder(root);}break;case4:{postorder(root);}break;case5:{//deletes(root)}case6:{printf("二叉树程序执行完，再见！ ");251 exit(0);}}}while(cord<=6);}structnode*creat(){structnode*t,*q,*s[30];inti,j,x;printf("i,x=");scanf("%d%d",&i,&x);//i是按满二叉树编号，x节点应有的序号，x是节点的数据while((i!=0)&&(x!=0)){q=(structnode*)malloc(sizeof(structnode));q->data=x;q->lc=NULL;q->rc=NULL;s[i]=q;if(i==1)t=q;//t代表树根节点else{j=i/2;//双亲节点的编号if((i%2)==0)s[j]->lc=q;elses[j]->rc=q;}printf("i,x=");scanf("%d%d",&i,&x);}return(t);}/*voidpreorderz(structnode*p)//前序非递归算法{structnode*q,*s[30];//s辅助栈inttop,bools;q=p;top=0;//栈顶指针bools=1;//bools=1为真值继续循环；bools=0为假时栈空，结束循环do{while(q!=NULL){printf("%6d",q->data);//访问节点top++;251 s[top]=q;q=q->lc;}if(top==0)bools=0;else{q=s[top];top--;q=q->rc;}}while(bools);printf(" ");}//////////////////////////结束preorderz*/voidpreorderz(structnode*p)//前序递归遍历{if(p!=NULL){printf("%6d",p->data);inorder(p->lc);inorder(p->rc);}}voidinorder(structnode*p)//中序非递归遍历{structnode*s[30],*q;inttop,bools;q=p;top=0;bools=1;do{while(q!=NULL){top++;s[top]=q;q=q->lc;}if(top==0)bools=0;else{q=s[top];top--;251 printf("%6d",q->data);q=q->rc;}}while(bools);}/*voidinorder(structnode*p){if(p!=NULL){inorder(p->lc);printf("%6d",p->data);inorder(p->rc);}}//////////////////////////结束inorder*/voidpostorder(structnode*p){structnode*s[30],*s2[30],*q;inttop,bools;q=p;top=0;bools=1;do{while(q!=NULL){top++;s[top]=q;s2[top]=1;q=q->lc;}if(top==0)bools=0;else{if(s2[top]==1){s2[top]=2;q=s[top];q=q->rc;}else{q=s[top];s2[top]=0;top--;251 printf("%6d",q->data);q=NULL;}}}while(bools);}voiddeletes(structnode*t,structnode*p,structnode*f){structnode*s,*q;intbools=1;if(p->lc==NULL)s=p->rc;elseif(p->rc==NULL){s=p->rc;while(s->lc!=NULL){q=s;s=s->rc;}if(q==p)q->rc=s->rc;elseq->lc=s->rc;p->data=s->data;free(s);bools=0;}if(bools==1){if(f==NULL)t=s;elseif(f->lc==p)f->lc=s;elsef->rc=s;free(p);}}/*voidpostorder(structnode*p){if(p!=NULL){postorder(p->lc);251 postorder(p->rc);printf("%6d",p->data);if(p->lc==NULL&&p->rc==NULL)m++;//统计叶子节点}}//////////////////////////结束postorder*/6.各种排序法#include#includestructnode{intkey;}r[20];structrnode{intkey;intpoint;};main(){voidprint(structnodea[20],intn);intcreat();voidshell(structnodea[20],intn);inthoare(structnodea[20],intl,inth);voidquick1(structnodea[20],intn);voidquick2(structnodea[20],intl,inth);voidheap(structnodea[20],inti,intm);voidheapsort(structnodea[20],intn);voidmerges(structnodea[20],structnodea2[20],inth1,intmid,inth2);voidmergepass(structnodea[20],structnodea2[20],intl,intn);voidmergesort(structnodea[20],intn);intyx(intm,inti);intradixsort(structrnodea[20],intn);intnum,l,h,c;structrnodes[20];c=1;while(c!=0){printf("主菜单 ");printf("1输入关键字，以-9999表示结束。 ");printf("2希尔排序 ");251 printf("3非递归的快速排序 ");printf("4递归的快速排序 ");printf("5堆排序 ");printf("6归并排序 ");printf("7基数排序 ");printf("输入选择(1--7,0表示结束):");scanf("%d",&c);switch(c){case1:num=creat();print(r,num);break;case2:shell(r,num);print(r,num);break;case3:quick1(r,num);print(r,num);break;case4:l=0;h=num-1;quick2(r,l,h);printf("outputquick2sortresult: ");print(r,num);break;case5:heapsort(r,num);break;case6:mergesort(r,num);print(r,num);break;case7:radixsort(s,num);}}}//mainendvoidprint(structnodea[20],intn){inti;for(i=0;i=1;i--)a[i].key=a[i-1].key;k=n/2;while(k>=1){for(i=k+1;i<=n;i++){a[0].key=a[i].key;j=i-k;while((a[j].key>a[0].key)&&(j>=0)){a[j+k].key=a[j].key;j=j-k;}a[j+k]=a[0];}k=k/2;}for(i=0;i=x.key))j--;if(ia[j+1].key)j++;if(a[j].key0;i--)a[i].key=a[i-1].key;for(i=n/2;i>=1;i--)heap(a,i,n);printf("输出堆排序结果: ");for(v=n;v>=2;v--){printf("%5d",a[1].key);x.key=a[1].key;a[1].key=a[v].key;a[v].key=x.key;heap(a,1,v-1);}printf("%5d",a[1].key);for(i=0;i=2*l){h1=i;mid=h1+l-1;h2=i+2*l-1;251 merges(a,a2,h1,mid,h2);i=i+2*l;}if((n-i)<=l)for(j=i;j<=n;j++)a2[j].key=a[j].key;else{h1=i;mid=h1+l-1;h2=n-1;merges(a,a2,h1,mid,h2);}}//mergepassendvoidmergesort(structnodea[20],intn){intl;structnodea2[20];l=1;while(l#include#include#include#include/*声明两种链表结构----start*/structnode_a{/*链表1-----作用：用来统计文件中字符的个数和种类（通过count）*/chardata;intcount;structnode_a*next;};typedefstructnode_anode,*list;listhead=NULL;structnodeb{/*链表2-----作用：用来建立用相应的编码代替字符的新文件*/chardata;structnodeb*next;};typedefstructnodebnode_b,*list_b;/*jiangbianmaxieruwenjian*/list_bhead_b=NULL;/*声明两种链表结构----end*//*哈夫曼算法种相关的3种结构的声明-----start*/structforest{floatweight;introot;251 };structalphabet{charsymbol;floatprobability;intleaf;char*bianma;};structtree{intlchild;intrchild;intparent;};typedefstructtree*tree_ptr,tree_node;typedefstructforest*forest_ptr,forest_node;typedefstructalphabet*alphabet_ptr,alphabet_node;tree_ptrtree1;forest_ptrforest1;alphabet_ptralphabet1;intlasttree,lastnode;intleast,second;/*哈夫曼算法种相关的3种结构的声明-----end*//**************stackdifinationstart****************/structstacknode{char*bian_ma;structstacknode*next;};typedefstructstacknodestack_node;typedefstack_node*link;linktop=NULL;voidpush(char*item){linkp;if(top!=NULL){p=(link)malloc(sizeof(stack_node));if(p==NULL){printf("Memoryallocationerror!");return;}p->bian_ma=item;p->next=top;top=p;}else{top=(link)malloc(sizeof(stack_node));if(!top){251 printf("Memoryallocationerror!");return;}top->bian_ma=item;top->next=NULL;}}voidpop(void){linkp;p=top;top=top->next;free(p);}voidmakenull(void){while(top!=NULL)pop();}intempty(){if(top==NULL)return1;elsereturn0;}char*tops(void){return(top->bian_ma);}voiddisplay_stack(links){/*显示栈重的内容*/linkptr;ptr=s;while(ptr!=NULL){printf("%s",ptr->bian_ma);ptr=ptr->next;}}/***************************stack__difinationisend************************/voiddisplay(listh){/*显示链表1*/listptr;inti=1;ptr=h->next;while(ptr!=NULL){printf("%d,%c,%d ",i,ptr->data,ptr->count);i++;ptr=ptr->next;251 }}voiddisplay_b(list_bh){/*显示链表2*/list_bptr;inti=1;ptr=h->next;while(ptr!=NULL){printf("%d,%c ",i,ptr->data);i++;ptr=ptr->next;}}voidinsert(charitem){/*用于插入元素以建立链表1*/listtemp,ptr;intflag;ptr=head->next;if(ptr==NULL){head->next=(list)malloc(sizeof(node));head->next->data=item;head->next->count=1;head->next->next=NULL;}else{while(ptr!=NULL){if(ptr->data==item){ptr->count=ptr->count+1;flag=1;}ptr=ptr->next;}ptr=head;if(flag==1)return;else{temp=ptr->next;ptr->next=(list)malloc(sizeof(node));ptr->next->data=item;ptr->next->count=1;ptr->next->next=temp;}}}voidinsert_b(charitem){/*插入元素以建立链表2*/list_bptr_b,temp_b;251 ptr_b=head_b;if(ptr_b->next==NULL){head_b->next=(list_b)malloc(sizeof(node_b));head_b->next->data=item;head_b->next->next=NULL;}else{while(ptr_b->next!=NULL){ptr_b=ptr_b->next;}ptr_b->next=(list_b)malloc(sizeof(node_b));ptr_b->next->data=item;ptr_b->next->next=NULL;}}voidsearch(void){/*搜索文件并将文件中的数据分别存入作用不同的链表中*/FILE*fp;listptr;charch;if((fp=fopen("test.txt","r"))==NULL)printf("Readingerror! ");while(!feof(fp)){ch=getc(fp);if(ferror(fp)){printf("error! ");break;}if(ch==EOF)break;insert(ch);/*插入元素进链表1*/insert_b(ch);/*插入元素进链表2*/}printf(" ");fclose(fp);}voiddisplay_struct(intn){/*显示哈夫曼算法中的3个结构树组*/inti=0;printf(" ======================================= ");printf("FOREST_STRUCT_ARRY: ");for(i=0;i<=n;i++){printf("%f,%d ",forest1[i].weight,forest1[i].root);}getch();printf(" ALPHABET_STRUCT_ARRY: ");251 for(i=0;i<=n;i++){printf("%f,%d,%c ",alphabet1[i].probability,alphabet1[i].leaf,alphabet1[i].symbol);}getch();printf(" TREE_STRUCT_ARRY: ");for(i=0;i<=2*n-1;i++)printf("%d,%d,%d ",tree1[i].lchild,tree1[i].rchild,tree1[i].parent);printf(" ====================================== ");getch();}intinit_struct(void){/*初始化哈夫曼算法中3种结构数组*/listptr;floatcount=.0;inti=1,n=0;ptr=head->next;while(ptr!=NULL){count=ptr->count+count;n++;ptr=ptr->next;}ptr=head->next;forest1=(forest_ptr)malloc(sizeof(forest_node)*n+sizeof(forest_node));alphabet1=(alphabet_ptr)malloc(sizeof(alphabet_node)*n+sizeof(alphabet_node));tree1=(tree_ptr)malloc(sizeof(tree_node)*n*2-sizeof(tree_node));forest1[0].weight=alphabet1[0].probability=0.0;forest1[0].root=alphabet1[0].leaf=0;alphabet1[0].symbol='0';while(ptr!=NULL){forest1[i].weight=alphabet1[i].probability=ptr->count/count;forest1[i].root=alphabet1[i].leaf=i;alphabet1[i].symbol=ptr->data;i++;ptr=ptr->next;}for(i=0;i<=2*n-1;i++){tree1[i].lchild=0;tree1[i].rchild=0;tree1[i].parent=0;}returnn;}voidcreat(void){/*创建正文文件test.txt*/FILE*fp,*out;charch;251 if((fp=fopen("test.txt","r++"))==NULL)printf("Createrror! ");printf("Inputthedata: ");ch=getch();putch(ch);while(ch!='#'){putc(ch,fp);ch=getch();putch(ch);}fclose(fp);}voidcreat_bianma(intnumber){/*根据哈夫曼算法建立文件中各种字符对应的编码*/inti,j,n;intp;char*bm=malloc(sizeof(char)*number);for(n=1;n<=number;n++){j=i=n;makenull();p=tree1[i].parent;while(tree1[p].parent!=0){if(tree1[p].lchild==i)push("0");elsepush("1");i=p;p=tree1[p].parent;}if(tree1[p].lchild==i)push("0");elsepush("1");strcpy(bm,"");/*目的：使创建编码文件中的各编码中间存在间隔*/while(!empty()){strcat(bm,tops());pop();}alphabet1[j].bianma=malloc(sizeof(char)*number);strcpy(alphabet1[j].bianma,bm);printf(" %c:%s",alphabet1[j].symbol,alphabet1[j].bianma);/*打印出相应的编码*/getch();}}voidwrite_new_file(intnumber){/*根据相应的编码重新建立编码文件*/251 FILE*fp;list_bptr;inti;char*ch=malloc(sizeof(char)*number);ptr=head_b->next;if((fp=fopen("bianma.txt","w"))==NULL)printf("Writeinanewfileerror!");else{while(ptr!=NULL){for(i=1;i<=number;i++){if(ptr->data==alphabet1[i].symbol){strcpy(ch,alphabet1[i].bianma);fputs(ch,fp);}}ptr=ptr->next;}}fclose(fp);}voidmain(void){inti,num;charch;voidhuffman(void);voidlightones();head=(list)malloc(sizeof(node));head->next=NULL;head->data='';head->count=0;head_b=(list_b)malloc(sizeof(node_b));head_b->data='';head_b->next=NULL;do{system("cls");creat();search();printf(" lianbiao1: ");display(head);/*显示链表1*/getch();printf(" lianbiao2: ");display_b(head_b);getch();num=init_struct();printf(" ");251 printf("The3init_structofhuffman? ");display_struct(num);/*显示初始化的哈夫曼书的相关3个结构数组*/lastnode=num;lasttree=num;huffman();printf("Nowthe3structthroughhuffmanshuanfa ");display_struct(num);/*显示哈夫曼树中相关的3种结构（经过哈夫曼算法处理）*/printf(" Thebian_mais: ");creat_bianma(num);write_new_file(num);printf(" Doyouwanttore_try(y/n)?");ch=getchar();}while(ch=='y');}/*哈夫曼算法-----defination_start*/voidlightones(void){inti;if(forest1[1].weight<=forest1[2].weight){least=1;second=2;}else{least=2;second=1;}for(i=3;i<=lasttree;i++)if(forest1[i].weight1){lightones();i=least;j=second;newroot=creat_tree(i,j);forest1[i].weight=forest1[i].weight+forest1[j].weight;forest1[i].root=newroot;forest1[j]=forest1[lasttree];lasttree=lasttree-1;}}8.哈慢树#include#include#include#definen6#definem2*n-1typedefstruct{floatweight;intlchild,rchild,parent;}codenode;typedefcodenodehuffmantree[m];typedefstruct{charch;charbits[n+1];}code;typedefcodehuffmancode[n];voidinithf(huffmantreeT)//－哈夫曼树的初始化{inti;for(i=0;i=0){cd[--start]=(T[p].lchild==c)?'0':'1';251 c=p;}strcpy(H[i].bits,&cd[start]);}}voidzip(huffmancodeH,char*ch,char*s)//－编码{intj=0;char*p[n];unsignedinti;for(i=0;i#includetypedefstructnode{intdata;structnode*lchild,*rchild;}*treetp,tree;treetpcreate(treetpt,intc);voidprint1(treetp);voidprint2(treetp);voidprint3(treetp);intnumber=0;voidmain(){treetpt=0,r;r=create(t,0);printf("前序排列：");print1(r);printf(" 中序排列：");print2(r);printf(" 后序排列：");print3(r);}treetpcreate(treetpt,intc){treetpp,di;do{scanf("%d",&c);if(t==0){t=(treetp)malloc(sizeof(tree));t->lchild=t->rchild=0;t->data=c;}else{p=t;while(p!=0){di=p;251 if(c<(p->data))p=p->lchild;elsep=p->rchild;}if(c<(di->data)){treetpNEWdi=(treetp)malloc(sizeof(tree));NEWdi->lchild=NEWdi->rchild=0;NEWdi->data=c;di->lchild=NEWdi;}else{treetpNEWdi=(treetp)malloc(sizeof(tree));NEWdi->lchild=NEWdi->rchild=0;NEWdi->data=c;di->rchild=NEWdi;}}++number;}while(c!=0);printf("叶子的数量：%d",number);returnt;}voidprint1(treetpt){if(t!=0){printf("%d",t->data);print1(t->lchild);print1(t->rchild);}}voidprint2(treetpt){if(t!=0){print2(t->lchild);printf("%d",t->data);print2(t->rchild);}}voidprint3(treetpt)251 {if(t!=0){print3(t->lchild);print3(t->rchild);printf("%d",t->data);}}10.迷宫#include#defineMAX20/*themaxsizeofa[]andstack.serial[]*/#defineOVER0#defineOK1struct{intserial[MAX];inti;}stack;intweight,a[MAX];voidput(intserial){if(stack.i0){p=seek(num+1);if(p==OK){put(num);return(OK);}else{weight+=a[num];p=seek(num+1);if(p==OK)return(OK);251 elsereturn(OVER);}}if(weight==0){put(num);return(OK);}if(weight<0){weight+=a[num];p=seek(num+1);if(p==OK)return(OK);elsereturn(OVER);}}}main(){inttemp=0;stack.i=-1;printf(" Pleaseinputthetotalwieghtyouneed:");scanf("%d",&weight);printf("Pleaseinputtheweightoflittlecase(Input'0'toend):");doscanf("%d",&a[temp]);while(a[temp++]!=0);/*printf("t%d",weight);for(temp=0;a[temp]!=0;temp++)printf("t%d",a[temp]);*/temp=seek(0);if(temp==OK)printf("Complete ");elseprintf("Uncomlete ");for(;stack.i!=-1;stack.i--){temp=stack.serial[stack.i];printf("t%d",a[temp]);}}11.迷宫问题#include#definer64#definem28#definen210intm=m2-2,n=n2-2;typedefstruct{251 intx,y;//行列坐标intpre;}sqtype;sqtypesq[r];structmoved{intx,y;//坐标增量，取值-1，0，1}move[8];intmaze[m2][n2];intPATH(intmaze[][n2])//找迷宫maze的路径{inti,j,k,v,front,rear,x,y;intmark[m2][n2];for(i=0;i#include#include#defineMAXOP100#defineNUMBER'0'intgetop(char[]);voidpush(double);doublepop(void);intgetch(void);voidungetch(int);intgetop(chars[]){inti,c;while((s[0]=c=getch())==''||c=='t');s[1]='';251 if(!isdigit(c)&&c!='.')returnc;i=0;if(isdigit(c))while(isdigit(s[++i]=c=getch()));if(c=='.')while(isdigit(s[++i]=c=getch()));s[i]='';if(c!=EOF)ungetch(c);returnNUMBER;}#defineBUFSIZE100charbuf[BUFSIZE];intbufp=0;intgetch(void){return(bufp>0)?buf[--bufp]:getchar();}voidungetch(intc){if(bufp>=BUFSIZE)printf("ungetch:toomanycharacters ");elsebuf[bufp++]=c;}main(){inttype;doubleop2;chars[MAXOP];while((type=getop(s))!=EOF){switch(type){caseNUMBER:push(atof(s));break;case'+':push(pop()+pop());break;case'*':push(pop()*pop());break;case'-':op2=pop();251 push(pop()-op2);break;case'/':op2=pop();if(op2!=0.0)push(pop()/op2);elseprintf("error:zerodivisor ");break;/*case'/n':printf("t%.8g ",pop());break;*/case0x0a:printf("t%.8g ",pop());break;default:printf("error:unknowncommand%s ",s);break;}}return0;}#defineMAXVAL100intsp=0;doubleval[MAXVAL];voidpush(doublef){if(sp0)returnval[--sp];else{printf("error:stackempty ");return0.0;}}251 13.排序法#include#includestructnode{intkey;}r[20];structrnode{intkey;intpoint;};main(){voidprint(structnodea[20],intn);intcreat();voidshell(structnodea[20],intn);inthoare(structnodea[20],intl,inth);voidquick1(structnodea[20],intn);voidquick2(structnodea[20],intl,inth);voidheap(structnodea[20],inti,intm);voidheapsort(structnodea[20],intn);voidmerges(structnodea[20],structnodea2[20],inth1,intmid,inth2);voidmergepass(structnodea[20],structnodea2[20],intl,intn);voidmergesort(structnodea[20],intn);intyx(intm,inti);intradixsort(structrnodea[20],intn);intnum,l,h,c;structrnodes[20];c=1;while(c!=0){printf("主菜单 ");printf("1输入关键字，以-9999表示结束。 ");printf("2希尔排序 ");printf("3非递归的快速排序 ");printf("4递归的快速排序 ");printf("5堆排序 ");printf("6归并排序 ");printf("7基数排序 ");printf("输入选择(1--7,0表示结束):");scanf("%d",&c);251 switch(c){case1:num=creat();print(r,num);break;case2:shell(r,num);print(r,num);break;case3:quick1(r,num);print(r,num);break;case4:l=0;h=num-1;quick2(r,l,h);printf("outputquick2sortresult: ");print(r,num);break;case5:heapsort(r,num);break;case6:mergesort(r,num);print(r,num);break;case7:radixsort(s,num);}}}//mainendvoidprint(structnodea[20],intn){inti;for(i=0;i=1;i--)a[i].key=a[i-1].key;k=n/2;while(k>=1){for(i=k+1;i<=n;i++)251 {a[0].key=a[i].key;j=i-k;while((a[j].key>a[0].key)&&(j>=0)){a[j+k].key=a[j].key;j=j-k;}a[j+k]=a[0];}k=k/2;}for(i=0;i=x.key))j--;if(ia[j+1].key)j++;if(a[j].key0;i--)a[i].key=a[i-1].key;for(i=n/2;i>=1;i--)heap(a,i,n);printf("输出堆排序结果: ");for(v=n;v>=2;v--){printf("%5d",a[1].key);x.key=a[1].key;a[1].key=a[v].key;a[v].key=x.key;heap(a,1,v-1);}printf("%5d",a[1].key);for(i=0;i=2*l){h1=i;mid=h1+l-1;h2=i+2*l-1;merges(a,a2,h1,mid,h2);i=i+2*l;}if((n-i)<=l)for(j=i;j<=n;j++)a2[j].key=a[j].key;251 else{h1=i;mid=h1+l-1;h2=n-1;merges(a,a2,h1,mid,h2);}}//mergepassendvoidmergesort(structnodea[20],intn){intl;structnodea2[20];l=1;while(lvoidmain(){structchildrec/*定义结构体*/{charinitial;/*姓名首字母*/intage;/*年龄*/intgrade;/*考试成绩*/}boy,girl;boy.initial='R';boy.age=15;boy.grade=75;girl.age=boy.age-1;/*女孩比男孩小一岁*/girl.grade=82;girl.initial='H';printf("girl:%cis%dyearsoldandgotagradeof%d ",girl.initial,girl.age,girl.grade);printf("boy:%cis%dyearsoldandgotagradeof%d ",boy.initial,boy.age,boy.grade);}15.数据结构2#includestructchildrec{charinitial;/*姓名首字母*/intage;/*年龄*/251 intgrade;/*成绩*/};voidmain(){structchildreckids[12]={{'A',16,80},{'B',13,80},{'C',19,84},{'D',19,89},{'E',12,84},{'F',17,82},{'G',16,90},{'H',16,85},{'I',16,96},{'J',17,91},{'K',13,72},{'L',14,69}};structchildrec*point,extra;intindex;for(index=0;index<12;index++){point=kids+index;printf("%cis%dyearsoldandgotagradeof%d ",(*point).initial,kids[index].age,point->grade);}printf(" ");getch();extra=kids[2];/*结构整体赋值*/printf("dataofextrastruct:initial(%c)age(%d)grade(%d) ",extra.initial,extra.age,extra.grade);getch();extra=*point;/*结构整体赋值*/printf("dataofextrastruct:initial(%c)age(%d)grade(%d) ",extra.initial,extra.age,extra.grade);}15.数据结构3#includevoidmain(){structchildrec/*定义结构类型childrec*/251 {charinitial;/*姓名首字母*/intage;/*年龄*/intgrade;/*考试成绩*/};structchildreckids[12]=/*定义childrec结构体数组并初始化*/{{'A',16,80},{'B',13,80},{'C',19,84},{'D',19,89},{'E',12,84},{'F',17,82},{'G',16,90},{'H',16,85},{'I',16,96},{'J',17,91},{'K',13,72},{'L',14,69}};intindex;for(index=0;index<12;index++)printf("%cis%dyearsoldandgotagradeof%d ",kids[index].initial,kids[index].age,kids[index].grade);}16.双链表正排序#include#include#includestructlist{intdata;structlist*next;structlist*pre;};typedefstructlistnode;typedefnode*link;linkfront=NULL,rear,ptr,head=NULL;linkpush(intitem){linknewnode=malloc(sizeof(node));newnode->data=item;if(head==NULL)251 {head=newnode;head->next=NULL;head->pre=NULL;rear=head;}else{rear->next=newnode;newnode->pre=rear;newnode->next=NULL;rear=newnode;}returnhead;}voidmakenull(){front=NULL;rear=NULL;}empty(){if(front==NULL)return1;elsereturn0;}inttops(){if(empty())returnNULL;elsereturnrear->data;}voidpop(){if(empty())printf("stackisempty! ");elserear=rear->pre;}voiddisplay(linkl){linkp;p=l;while(p!=NULL){printf("%d->",p->data);p=p->next;}251 }voidmain(){intn,i;printf("inputyourfirstdata! ");scanf("%d",&n);front=push(n);/*anotherdata*/for(i=0;i<3;i++){printf("input: ");scanf("%d",&n);push(n);}ptr=front;display(ptr);printf(" Pleaseenteranykeytopop");getch();pop();ptr=front;display(ptr);getch();}17.推箱子#include#includetypedefstructele{intvno;/*物品号*/structele*link;/*另一物品的指针*/}ELE;typedefstructhnode{intremainder;/*箱子尚剩空间*/ELE*head;/*箱内物品链首元指针*/structhnode*next;/*箱子链的后继箱子指针*/}HNODE;main(){intn,i,box_count,box_volume,*a;HNODE*box_h,*box_t,*j;ELE*p,*q;printf("输入箱子容积");scanf("%d",&box_volume);251 printf("输入物品种数");scanf("%d",&n);a=(int*)malloc(sizeof(int)*n);/*存储物品体积信息的数组*/printf("请按体积大小顺序输入各物品的体积：");for(i=0;ivno=i;for(j=box_h;j!=NULL;j=j->next)if(j->remainder>=a[i])break;/*找到还可以装物品i的箱子*/if(j==NULL){/*已用箱子都不能装物品i*/j=(HNODE*)malloc(sizeof(HNODE));/*使用一只新的箱子*/j->remainder=box_volume-a[i];j->head=NULL;if(box_h==NULL)box_h=box_t=j;/*box-t有什么用处，能解释一下吗？*/elsebox_t=box_t->next=j;/*此外box-t又有什么用（在程序中），请说详一细*/j->next=NULL;box_count++;}elsej->remainder=a[i];/*将物品i放入箱子j*/for(q=j->head;q!=NULL&&q->link!=NULL;q=q->link);/*从这里起是放入物品号*/if(q==NULL){p->link=j->head;j->head=p;}else{p->link=NULL;q->link=p;}}/*fori*/}251 18.无向图#include#include#defineMaxSize20structArcNode{intadjvex;structArcNode*nextarc;};structVnode{intdata;structArcNode*firstarc;};structVnodeAdjList[MaxSize];intm,n,v,cord;main(){voidcreatgraph(structVnodeA[MaxSize]);voiddfs(structVnodeA[MaxSize]);voidbfs(structVnodeA[MaxSize]);do{printf(" 主菜单");printf(" 1建立无向图的邻接表");printf(" 2按深度遍历图");printf(" 3按广度遍历图");printf(" 4结束程序运行");printf(" -----------------------------------");printf(" 请输入您的选择1,2,3,4");scanf("%d",&cord);switch(cord){case1:creatgraph(AdjList);break;case2:dfs(AdjList);break;case3:bfs(AdjList);251 break;case4:exit(0);}}while(cord<=4);}//mainendvoidcreatgraph(structVnodeA[MaxSize]){inti,j,k;structArcNode*p;printf("inputarcesandvexes");scanf("%d%d",&m,&n);for(k=0;kadjvex=j;p->nextarc=A[i-1].firstarc;A[i-1].firstarc=p;p=(structArcNode*)malloc(sizeof(structArcNode));p->adjvex=i;p->nextarc=A[j-1].firstarc;A[j-1].firstarc=p;}printf(" ");for(k=0;kadjvex);p=p->nextarc;}printf(" ");}}///creatgraphendvoiddfs(structVnodeA[MaxSize]){structArcNode*p,*ar[MaxSize];intx,i,y,top=-1;intvisited[MaxSize];for(i=0;i=0)){if(!p){p=ar[top];top--;}y=p->adjvex;if(visited[y-1]==0){visited[y-1]=1;printf("->%d",y);p=p->nextarc;if(p){top++;ar[top]=p;}p=A[y-1].firstarc;}elsep=p->nextarc;}}voidbfs(structVnodeA[MaxSize]){}19.线索化二叉树#include#includestructnode{intdata;structnode*lh,*rh;intltag,rtag;}*pr,*t,*s[30];structnode*creat()251 {structnode*t,*q;inti,x,j;printf("i,x=");scanf("%d%d",&i,&x);while((i!=0)&&(x!=0)){q=(structnode*)malloc(sizeof(structnode));q->data=x;q->lh=NULL;q->rh=NULL;s[i]=q;if(i==1)t=q;else{j=i/2;if((i%2)==0)s[j]->lh=q;elses[j]->rh=q;}printf("i,x=");scanf("%d%d",&i,&x);}return(t);}/*voidinthread(structnode*p)//递归算法{if(p!=NULL){inthread(p->lh);printf("%6dt",p->data);if(p->lh!=NULL)p->ltag=0;else{p->ltag=1;p->lh=pr;}//建立P节点的左线索，指向前趋节点PRif(pr!=NULL){if(pr->rh!=NULL)pr->rtag=0;251 else{pr->rtag=1;pr->rh=p;}//前趋节点PR建立左线索，指向节点P}pr=p;//pr跟上p,以便p向后移动inthread(p->rh);}}*/voidinthread(structnode*t)//非递归算法{inttop,bools;structnode*p;pr=NULL;p=t;top=0;bools=1;do{while(p!=NULL){top++;s[top]=p;p=p->lh;}if(top==0)bools=0;else{p=s[top];top--;printf("%6d",p->data);if(p->lh!=NULL)p->ltag=0;else{p->ltag=1;p->lh=pr;}//建立P节点的左线索，指向前趋节点PRif(pr!=NULL){if(pr->rh!=NULL)pr->rtag=0;else{pr->rtag=1;pr->rh=p;}//前趋节点PR建立左线索，指向节点P251 }pr=p;//pr跟上p,以便p向后移动p=p->rh;}//ENDelse}while(bools);pr->rh=NULL;}main(){pr=NULL;t=creat();inthread(t);pr->rh=NULL;}20.线性顺序存储结构#include#include#defineMAX20#defineELEMTPint#definev(*p)structsequnce{ELEMTPelem[MAX];intlen;};main(){structsequnce*pz;inti,y,cord;voidoutlin(structsequnces);voidcreate(structsequnce*p);voidinsert(structsequnce*p,inti,intx);voiddeletes(structsequnce*p,inti);do{printf(" 主菜单 ");printf("1建立线性表 ");printf("2插入一个元素 ");printf("3删除一个元素 ");printf("4结束程序运行 ");printf("------------------------------------ ");printf("请输入您的选择(1,2,3,4)");251 scanf("%d",&cord);switch(cord){case1:{pz=(structsequnce*)malloc(sizeof(structsequnce));create(pz);outlin(*pz);}break;case2:{printf("请输入插入的位置i:");scanf("%d",&i);printf("请输入插入的数据y:");scanf("%d",&y);insert(pz,i,y);outlin(*pz);}break;case3:{scanf("%d",&i);deletes(pz,i);outlin(*pz);}break;case4:exit(0);}}while(cord<=4);}voidoutlin(structsequnces){inti;for(i=1;i<=s.len;i++)printf("%2d%6d ",i,s.elem[i]);}voiddeletes(structsequnce*p,inti){intj;if(i<1||i>v.len)printf("i,位置不存在");else{for(j=i;jv.len+1)printf("i位置不存在。");else{for(j=v.len;j>=i;j--)v.elem[j+1]=v.elem[j];v.elem[i]=x;v.len++;}}voidcreate(structsequnce*p){inti;printf("n=");scanf("%d",&(v.len));for(i=1;i<=v.len;i++){printf("data=");scanf("%d",&(v.elem[i]));}}21.栈操作#include#include#defineMAX20#defineElemTypeint#defineS(*p)structSqStack{ElemTypeelem[MAX];inttop;};main(){structSqStack*q;251 inti,y,cord;ElemTypea;voidOutStack(structSqStackS);voidInitStack(structSqStack*p);voidPush(structSqStack*p,ElemTypex);ElemTypePop(structSqStack*p);ElemTypeGetTop(structSqStack*p);do{printf(" ");printf(" 主菜单 ");printf(" 1初始化顺序栈 ");printf(" 2插入一个元素 ");printf(" 3删除栈顶元素 ");printf(" 4取栈顶元素 ");printf(" 5结束程序运行 ");printf(" -------------------------------- ");printf("请输入您的选择(1,2,3,4,5)");scanf("%d",&cord);switch(cord){case1:{q=(structSqStack*)malloc(sizeof(structSqStack));InitStack(q);OutStack(q);}break;case2:{printf("请输入要插入的数据a=");scanf("%d",&a);Push(q,a);OutStack(q);}break;case3:{Pop(q);OutStack(q);}break;case4:{y=GetTop(q);printf(" y=%d ",y);OutStack(q);}break;case5:251 exit(0);}}while(cord<=5);}voidInitStack(structSqStack*p){if(!p)printf("Eorror");S.top=0;}voidPush(structSqStack*p,ElemTypex){if(S.top0;i--)printf("%2d%6d ",i,S.elem[i]);}八、数学问题一、凉东问题1.32#include"stdio.h"main(){intn,s,j,k,p;inta[100],b[100];//最多允许100人printf("请输入人数：");scanf("%d",&n);printf("请输入数字：");scanf("%d",&s);for(k=0;kmain(){intn,s,j,k,p;inta[100];//最多允许100人printf("请输入人数：");scanf("%d",&n);printf("请输入数字：");scanf("%d",&s);for(j=0;j<100;j++)a[j]=0;for(j=0;jvoidf2();inta[13],i,j,b=13;main(){f2();for(j=0;jvoidf2();inta[13],k,j=1,b=13,n=0;main(){for(k=0;kmain(){inta[6],i,j,k=2520/6;251 for(i=0,j=8;i<6;i++,j--){if(i==0)a[i]=k/2*j/(j-1);elsea[i]=k*j/(j-1);}for(i=5,j=4;i>=0;i--,j++){if(i!=0)a[i]=a[i]-a[i-1]/j;printf("NO:%d=%d ",i+1,a[i]);}}2.苹果分法#includemain(){intb[6],k=2520/6,j,m,x,y,p=0;y=x=k-k/2;for(m=0,j=7;m<6;m++,j--){b[m]=(k-x)+y/j;x=y/j;y=k;}for(m=0,y=1;m<6;m++,y++){p=p+b[m];printf("%d原来有:%d ",y,b[m]);}printf("合为:%d ",p);getch();}三、数学算法1.符号图形#include#include#include251 voidjust(int);voidfall(int);voiddiamond(int);main(){inthose,row;charch;//clrscr();printf("ttt1.jut2.fall3.diamond ");printf("请输入选择，和宽度：");scanf("%d%d",&hose,&row);while(row!=0){if(row<17&&row>-17){switch(hose){case1:{printf("Ensample:");just(row);}break;case2:{printf("Ensample:");fall(row);}break;case3:{printf("Ensample:");diamond(row);}break;default:{printf("ErrorEnter!!");getch();exit(1);}}}//endifelse{251 getch();exit(1);}printf("请输入选择，和宽度：");scanf("%d%d",&hose,&row);}}///***********definefunction*********/voidjust(intchoose){inti,s,j;for(i=1;i<=choose;i++){printf(" ttttt");for(j=1;j<=2*i-1;j++){printf("b");}for(s=1;s<=2*i-1;s++){printf("*");/*注意这里面的空格，一定要空一格，不然结果全然不对*/}}printf(" ");}voidfall(intchoose){inti,s,j;for(i=abs(choose);i>=1;i--){printf(" ttttt");for(j=1;j<=2*i-1;j++){printf("b");}for(s=1;s<=2*i-1;s++){printf("*");///**一样的请注意空一格***/}}printf(" ");}voiddiamond(intchoose){251 inti,s,j;inta,b,c;for(i=1;i<=abs(choose);i++){printf(" ttttt");for(j=1;j<=2*i-1;j++){printf("b");}for(s=1;s<=2*i-1;s++){printf("*");}}for(a=abs(choose);a>=1;a--){if(a==abs(choose))printf("rttttt");elseprintf(" ttttt");for(b=1;b<=2*a-1;b++){printf("b");}for(c=1;c<=2*a-1;c++){printf("*");}}printf(" ");}2.绘制圆#include#includemain(){doubley;intx,m;for(y=10;y>=-10;y--){m=2.5*sqrt(100-y*y);251 for(x=1;x<30-m;x++)printf("");printf("*");for(;x<30+m;x++)printf("");printf("* ");}}3.余弦曲线#include#includemain(){doubley;intx,m;for(y=1;y>=-1;y-=0.1){m=acos(y)*10;for(x=1;x#includemain(){doubley;intx,m,n,yy;for(yy=0;yy<20;yy++){y=0.1*yy;251 m=acos(1-y)*10;n=45*(y-1)+31;for(x=0;x<=62;x++)if(x==m&&x==n)printf("+");elseif(x==n)printf("+");elseif(x==m||x==62-m)printf("*");elseprintf("");printf(" ");}}四、桃子猴问题1979年,诺贝尔奖获得者李政道教授到中国科技大学讲学,他给少年班的同学出了这样一道算术题:有5只猴子在海边发现一堆桃子,决定第二天来平分.第二天清晨,第一只猴子最早来到,它左分右分分不开,就朝海里扔了一只,恰好可以分成5份,它拿上自己的一份走了.第2,3,4,5只猴子也遇到同样的问题,采用了同样的方法,都是扔掉一只后,恰好可以分成5份.问这堆桃子至少有多少只.据说没有一个同学能当场做出答案.李教授说用常见的方法计算很繁,问题的关键在于打破常规思维.。1.乘方函数桃子猴#include#includemain(){doublex,d,t;scanf("%lf",&x);d=pow(x,x);t=d-(x-1);printf("%lf ",t);}251 2.递归桃猴#includeintsub(intn){if(n==1){staticinti=0;do{i++;}while(i%5!=0);//printf("*%d*",i);return(i+1);}else{inttemp;do{temp=sub(n-1);}while(temp%4!=0);//printf("*%d*",temp);return(temp/4*5+1);}}main(){inttotal;total=sub(5);printf("%d ",total);}3.猴子和桃#includemain(){intx,x1,x2,x3,x4;/*我用的不知算不算是穷举法，桃子的初值设的是１００*/for(x=0;x<100000;x++)/*在１００－１００００之间查找，还可以设的更大些*/{if((x-1)%5==0)/*满足第一只猴子的条件*/251 {x1=(x-1)-(x-1)/5;if((x1-1)%5==0)/*这里就是满足第二只猴子的条件*/{x2=(x1-1)-(x1-1)/5;if((x2-1)%5==0)/*满足第三只猴子的条件*/{x3=(x2-1)-(x2-1)/5;if((x3-1)%5==0)/*满足第四只猴子的条件*/{x4=(x3-1)-(x3-1)/5;if((x4-1)%5==0)/*满足第五只猴子的条件*/{printf("%d ",x);/*＜－还可以在这里设置满足六，七，八等猴子的条件*/}}}}}}}4.桃子猴#include#includevoidmain(){inttotal=0;intn,b;scanf("%d%d",&n,&b);while(1){inti=++total;intj;for(j=0;jmain(){intd[6],m,i,j,m;longb[63],flag;floatc[6],min,x;printf("请输入背包可装的重量");scanf("%d",&m);printf("请输入六个物体的重量");for(i=0;i<6;i++)/*输入六个浮点数*/scanf("%f",&c[i]);for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++)/*建立六个数的全部组合并处理*/for(d[1]=0;d[1]<2;d[1]++)/*i:差值具有min组合的数量*/for(d[2]=0;d[2]<2;d[2]++)/*min:与10的最小差值*/for(d[3]=0;d[3]<2;d[3]++)/*d[]:组合时是否取该数的标志*/for(d[4]=0;d[4]<2;d[4]++)for(d[5]=0;d[5]<2;d[5]++){for(flag=0,x=0.,j=5;j>=0;j--)/*flag:将六个数的组合用对应的一个十进制位表示*/{x+=c[j]*d[j];flag=flag*10+d[j];}/*x:对应六个数的组合的和*/x=((x-m>0)?x-m:m-x);/*x:组合的和与10的差*/if(min<0){min=x;/*对第一次计算出的差min进行处理*/b[i++]=flag;/*b[]:记录有相同min的flag的数组i:b[]数组的下标*/}elseif(min-x>1.e-6)/*对新的min的处理*/{min=x;b[0]=flag;i=1;}elseif(fabs((double)x-min)<1.e-6)/*相等的min的处理*/251 b[i++]=flag;}for(m=0;m//#include#defineABS(x)(((x)>0)?(x):(-(x)))voidGetInputValue(float*a,constinthowmany){inti=0;for(i=0;i>1;}mmult[i]=a[0]*ba[0]+a[1]*ba[1]+a[2]*ba[2]+a[3]*ba[3]+a[4]*ba[4]+a[5]*ba[5];}251 }voidLookForNearest(float*mmult,constfloatv){intindex=0;inti=0;intba[6];floatmin=ABS(*mmult-v);for(i=0;i<0x40;i++){if(ABS(mmult[i]-10.0)>1;//ba++;}printf("result:thenearestvalueis:%f,%d%d%d%d%d%d",min,ba[0],ba[1],ba[2],ba[3],ba[4],ba[5]);}main(){//仅仅是N=6的情况，更广泛的话，请自行解决。//defineinputaray,ifuextendsthisprog,ushoulddynamicallocatethisfloata[6];//define中间数组如果输入数字是N的话，floatmult[2^N]floatmult64[64];inti=0;GetInputValue(&a[0],6);CalAllPosibility(&a[0],&mult64[0]);LookForNearest(&mult64[0],10.0);}251 六、圆周率1.狐狸圆周率#includevoidmain(){intN,i,j=1,count=0,countTemp=0;//line1cin>>N;for(i=N;i>=-N;i--,j=1,count+=((countTemp-1)*2+1),countTemp=0)//line2{while(countTemp++,(j*(j++)+i*i)<=N*N);//line3}doubleoutput=double(count)/double(N*N);//line4cout.precision(15);cout<longa=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}七、运算类数学问题1.阿姆斯特朗数#includemain(){inti,t,k,a[3];251 printf("TherearefollowingArmstrongnumbersmallerthan1000: ");for(i=152;i<1000;i++){for(t=0,k=1000;k>=10;t++){a[t]=(i%k)/(k/10);/*k/=10下面略去*/k/=10;}if(a[0]*a[0]*a[0]+a[1]*a[1]*a[1]+a[2]*a[2]*a[2]==i)printf("%d",i);}}/*阿姆斯特朗数是一个正整数等于其的各位数的立方和如153=1*1*1+5*5*5+3*3*3*/2.百鸡百钱#includemain(){intx,y,z,j=0;for(x=0;x<=20;x++){y=(100-7*x)/4;z=100-x-y;if(z%3==0&&y>0&&5*x+3*y+z/3==100)printf("%2d:cock=%2dhen=%2dchicken=%2d ",++j,x,y,z);}}3.大加数/*这是一个大正数加法问题TC中应该完全可以运行。*/#include#include#defineHUN10000typedefstructnode{intdata;structnode*next;}NODE;NODE*insert(NODE*u,intnum)/*声明返回指针函数*/251 {NODE*v;/*声明结构指针*/v=(NODE*)malloc(sizeof(NODE));v->data=num;u->next=v;return(v);}NODE*addint(NODE*p,NODE*q){NODE*pp,*qq,*r,*s,*t;inttotal,number,carry;pp=p->next;qq=q->next;s=(NODE*)malloc(sizeof(NODE));s->data=-1;t=s;carry=0;while(pp->data!=-1&&qq->data!=-1){total=pp->data+qq->data+carry;number=total%HUN;carry=total/HUN;t=insert(t,number);pp=pp->next;qq=qq->next;}r=(pp->data!=-1)?pp:qq;while(r->data!=-1){total=r->data+carry;number=total%HUN;carry=total/HUN;t=insert(t,number);r=r->next;}if(carry)t=insert(t,1);t->next=s;return(s);}NODE*inputint(void){NODE*s,*ps,*qs;structnumber251 {intnum;structnumber*np;}*p,*q;inti,j,k;longsum;charc;p=NULL;while((c=getchar())!=' ')if(c>='0'&&c<='9'){q=(structnumber*)malloc(sizeof(structnumber));q->num=c-'0';q->np=p;p=q;}s=(NODE*)malloc(sizeof(NODE));s->data=-1;ps=s;while(p!=NULL){sum=0;i=0;k=1;while(i<4&&p!=NULL){sum=sum+k*(p->num);i++;p=p->np;k=k*10;}qs=(NODE*)malloc(sizeof(NODE));qs->data=sum;ps->next=qs;ps=qs;}ps->next=s;return(s);}printint(NODE*s){if(s->next->data!=-1){printint(s->next);if(s->next->next->data==-1)printf("%d",s->next->data);else{251 inti,k=HUN;for(i=1;i<=4;i++,k/=10)putchar('0'+s->next->data%(k)/(k/10));}}}main(){NODE*s1,*s2,*s;NODE*inputint(),*addint(),*insert_after();s1=inputint();s2=inputint();printf("S1=");printint(s1);printf(" ");printf("S2=");printint(s2);printf(" ");s=addint(s1,s2);printf("S1+S2=");printint(s);printf(" ");}4.大小倍约/*最大公约数，最小公倍数*/#includeinthcf(inta,intb){intr=0;while(b!=0){r=a%b;a=b;b=r;}return(a);}lcd(intu,intv,inth){return(u*v/h);}main(){251 intu,v,h,l;scanf("%d%d",&u,&v);h=hcf(u,v);printf("H.C.F=%d ",h);l=lcd(u,v,h);printf("L.C.D=%d ",l);}5.大整数/*这只是两个大整数的乘法，加法，减法应不成问题，你可参照下面的程序要是除法的话，可以用数值分析里的牛顿逼近法*//************************************Question:**Howtocalculatetwointegerseachonehasfortybit.**Algorithm:**DeclaretwoarrayssupposetobearrayAandBtostorage**thetwointegersjustasaintactersingly.**GetthefirstnumberfromarrayB,thenuseittomultiply**thenumberofarrayAsingly.DeclareanotherarrayCto**storagethevaluewhenmultiplying.**Thinkingaboutthecarryingbits.**Thinking:**CanyouusetheLinear_Listtodothis?**Iftheyaretwofloatingnumbers,sohowtodoit?************************************/#include#include#include#include//Tocalculatetwo40bitsintegersmultiply,change10to40#defineTHE_ARR_A_SIZE10#defineARR_B_SIZETHE_ARR_A_SIZE#defineARR_C_SIZE(THE_ARR_A_SIZE+ARR_B_SIZE)voidmain(void);voidMultiply(short*,short*,short*,short,short);voidCarrying(short*c,short);voidmain(void){shortA[THE_ARR_A_SIZE]={9,9,9,9,9,9,9,9,9,9};//10shortB[ARR_B_SIZE]={9,9,9,9,9,9,9,9,9,9};shortC[ARR_C_SIZE];shorti=0;for(NULL;i=0;i--){temp=C[i];if(C[i]>9){tens_place=temp/10;units_order=temp%10;C[i-1]+=tens_place;C[i]=units_order;}}}6.灯塔问题//灯塔问题#include#include#includeintsz[11][11],cf=1,k,n,a[20],b[20],c[20];voidshuru(void);voidshuchu(void);boolpanduan(void);voidgoujian(void);voidmain(){inti,j,lj=0,d;shuru();for(i=1;i<=n;i++)cf=cf*2;for(i=0;i0;i1--){for(j1=1;j1<=i1;j1++){if(sz[i1+1][j1]==1&&sz[i1+1][j1]==1)sz[i1][j1]=0;if(sz[i1+1][j1]==0&&sz[i1+1][j1+1]==0)sz[i1][j1]=0;if(sz[i1+1][j1]==1&&sz[i1+1][j1+1]==0)sz[i1][j1]=1;if(sz[i1+1][j1]==0&&sz[i1+1][j1+1]==1)sz[i1][j1]=1;}}}boolpanduan(){intpd=1,j1;for(j1=1;j1<=k;j1++)if(sz[a[j1]][b[j1]]!=c[j1])pd=0;if(pd==0)returnfalse;elsereturntrue;}voidshuchu(void){inti2,j2;for(i2=1;i2<=n;i2++){for(j2=1;j2<=n-i2;j2++)cout<<"";for(j2=1;j2<=i2;j2++)cout<>filename;//input.open(filename);input.open("dt.txt");input>>n;251 k=0;do{k++;input>>a[k]>>b[k]>>c[k];}while((a[k]!=0)&&(b[k]!=0));k--;}7.递推#defineNUM10#includeinti[NUM];main(){intsum,n,total,k,flag,count=0;printf("Pleaseenterrequriedterms(<=10):");scanf("%d",&n);printf("theirsum:");scanf("%d",&total);sum=0;k=n;i[n]=1;printf("Therearefollowingpossibleseries: ");while(1){if(sum+i[k]total||k!=1){sum-=i[++k];flag=0;}elseflag=1;if(flag){251 printf("[%d]:",++count);for(flag=1;flag<=n;++flag)printf("%d",i[flag]);printf(" ");}if(++k>n)break;sum-=i[k];i[k]++;}}8.叠代整除#includequyu(longintm){intx=0,y=0,z=0,he=0;if(m%3==0)x=1;if(m%5==0)y=2;if(m%7==0)z=4;he=x+y+z;returnhe;}main(){longintm;scanf("%d",&m);switch(quyu(m)){case0:printf("不能被任何数整除");break;case1:printf("能被3整除");break;case2:printf("能被5整除");break;case3:251 printf("能被3，5整除");break;case4:printf("能被7整除");break;case5:printf("能被3，7整除");break;case6:printf("能被5，7整除");break;case7:printf("能被3，5，7整除");break;}}9.多位阶乘/*计算30000的阶乘！*//*Thisfile"jiech2.c"createdat2001-08-2420:15:22byLeiPeng.*/#include#include#include#include#include#include#defineMAXN0X7000inta[MAXN];intmain(intargc,char*argv[]){intn,m,i,j,c,t;printf("Entern(n>=2):");while(1){scanf("%d",&n);if(n>=2&&n<=3276)break;printf("mustbe2<=n<=3276");}251 a[0]=1;m=1;for(i=2;i<=n;i++){for(c=0,j=0;j=0;i--)putchar(a[i]+0x30);printf(" pressanykeytocontinue. ");getch();return0;}/*3000!得结果超出了电脑能显示得范围，所以最好采用数组来记录每位*/10.多位阶乘2#includemain(){intdata[40];intdigit;inti,j,r,k;intn;for(i=1;i<=40;i++)/*将数组初始值设为0*/data[i]=0;data[0]=1;data[1]=1;digit=1;printf("Enteranumberwhatyouwanttocalculus:");scanf("%d",&n);for(i=1;i<=n;i++){for(j=1;j<=digit;j++)/*每位上等乘上阶数digit决定有几位*/data[j]*=i;251 for(j=1;j<=digit;j++){if(data[j]>10){for(r=1;r<=digit;r++){if(data[digit]>10)digit++;data[r+1]+=data[r]/10;data[r]=data[r]%10;}}}printf("%d!=",i);for(k=digit;k>0;k--)printf("%d",data[k]);printf(" ");}getch();}11.黑白/*有A,B,C,D,E,五人，每人额头上都帖着一张或黑或白的纸。五人对坐，每人都能看见别人的，但看不见自己的。而且黑的撒谎，白的诚实。A说：“我看见有三个人的是白纸，一人是黑纸”。B说：“我看见四个人的都是黑纸”。C说：“我看见有一个人的是白纸，三个人是黑纸”。D说：“我看见四个人的都是白纸”。E什么也没有说。*/#includemain(){inta,b,c,d,e;for(a=0;a<=1;a++)for(b=0;b<=1;b++)for(c=0;c<=1;c++)for(d=0;d<=1;d++)for(e=0;e<=1;e++)if((a&&b+c+d+e==3||!a&&b+c+d+e!=3)&&(b&&a+c+d+e==0||!b&&a+c+d+e!=0)&&(c&&a+b+d+e==1||!c&&a+b+d+e!=1)&&(d&&a+b+c+e==4||!d&&a+b+c+e!=4))251 {printf("Aispastedapieceof%spaperonhisforehead. ",a?"white":"black");printf("Bispastedapieceof%spaperonhisforehead. ",b?"white":"black");printf("Cispastedapieceof%spaperonhisforehead. ",c?"white":"black");printf("Dispastedapieceof%spaperonhisforehead. ",d?"white":"black");printf("Eispastedapieceof%spaperonhisforehead. ",e?"white":"black");}}12.简单计算器#includeintresult=0,valuess=0,k,y=1,l;chara,b[1],d[50],r;intmain(void){while(1){intj=0;printf("%d",result);printf("pleaseinputacharandnumber ");while((a=getchar())!=' '){b[j]=a;}while((r=getchar())!=' '){d[j]=r;j++;}for(k=0;k251 intfactr(intn){intresult,r;if(n==1)return1;result=factr(n-1)*n;returnresult;}main(){inta;a=factr(5);printf("%d",a);}14.逻辑移动#includeintmain(void){intx=32;unsignedinty=23;x<<=1;//与(signedint)x<<=2;相同，因为变量本身是signed//(unsignedint)x<<=2;//x>>=2;//(unsignedint)x>>=2;(signedint)y<<=2;y<<=2;(signedint)y>>=2;y>>=2;printf("%d%d",x,y);returnx+y;}15.平方根#defineEpsilon1.0E-6/*控制解的精度*/#include#includemain(){floatnum,pre,this;251 do{scanf("%f",&num);/*输入要求平方根的数*/}while(num<0);if(num==0)printf("therootis0");else{this=1;do{pre=this;this=(pre+num/pre)/2;}while(fabs(pre-this)>Epsilon);/*用解的精度，控制循环次数，fabs()是求绝对值的函数*/}printf("therootis%f",this);}16．十五人排序/*原题：一寝室有15个人，每天都要三人一行外出散步一次，要在一周（7天）内每个人都跟其他14人各散步一次，问每一天应该怎么安排？？要快点想哟！！！！都等一会15分钟*/#includeintanpai[7][5][3];intbiaozhi[16][16];inti=0,j=0,k=0,a,total=0;voidhuisu(){if(k==1){anpai[i][j][0]=0;j--;if(j==-1){i--;j=4;}biaozhi[anpai[i][j][2]][anpai[i][j][1]]=0;biaozhi[anpai[i][j][2]][anpai[i][j][0]]=0;k=2;a=anpai[i][j][k];anpai[i][j][k]=0;total-=2;}elseif(k==2){biaozhi[anpai[i][j][1]][anpai[i][j][0]]=0;251 a=anpai[i][j][--k];anpai[i][j][k]=0;total--;}}voidmain(){intb,c,t;for(a=1;a<=15&&total<105;a++){t=0;for(b=0;b<=j;b++)for(c=0;c<3;c++)if(anpai[i][b][c]==a){b=9;break;}if(b==10){while(a==15)huisu();continue;}for(b=0;b0&&i<7)printf("");for(k=0;k<3;k++)printf("%-2d",anpai[i][j][k]);}}printf(" ");}17.四分砝码#include#includemain(){intweight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag;printf("Theweightisbrokeupasfollowing4pieces:");for(weight1=1;weight1<=40;weight1++)for(weight2=weight1+1;weight2<=40-weight1;weight2++)for(weight3=weight2+1;weight3<=40-weight1-weight2;weight3++)if((weight4=40-weight1-weight2-weight3)>=weight3){for(flag=1,x=1;x<41&&flag;x++)/*重物在天平左面，d的各种状态-1：砝码在天平左面，1：砝码在右面，0：不用该砝码*/for(flag=0,d1=1;d1>-2;d1--)for(d2=1;d2>-2&&!flag;d2--)for(d3=1;d3>-2&&!flag;d3--)for(d4=1;d4>-2&&!flag;d4--)if(x==weight1*d1+weight2*d2+weight3*d3+weight4*d4)flag=1;if(flag)printf("%d%d%d%d ",weight1,weight2,weight3,weight4);}}18.完数/*编程找出1000之内的"完数".完数指:一个数如果恰好等于它的因子之和.例如6=1+2+328=1+2+4+7+14*/main(){staticintk[10];251 inti,j,n,s;for(j=2;j<=1000;j++){n=-1;s=j;for(i=1;i(ti))当n=2k时，因为一个整数的因子总是成对出现的，所以有如下关系t1*t2k=X，t2*t2k-2=X，。。。(1)又有t1+t2+...+t2k=X(2)t1*t2*...*t2k=X(3)由(1)和(3)t2*...*t2k-2=1又因为(ti+1)>(ti),知k=1,即1*t1*t2=1+t1+t2=X，解这个不定方程，知t1=2,t2=3为唯一解当n=2k-1时，无解*/19.小孩分糖果/*10个小孩分糖果sweer[10]*/#includeintj=0;main(){staticintsweet[10]={10,2,8,22,16,4,10,6,14,20};//初始化数组inti,t[10],l;printf("child ");printf("round12345678910 ");printf("------------------------------------------------ ");251 print(sweet);while(judge(sweet)){for(i=0;i<10;i++)if(sweet[i]%2==0)t[i]=sweet[i]=sweet[i]/2;//为偶数时直接分出一半elset[i]=sweet[i]=(sweet[i]+1)/2;//为奇数是加1后再分出一半for(l=0;l<9;l++)sweet[l+1]=sweet[l+1]+t[l];sweet[0]+=t[9];print(sweet);}}judge(c)intc[];{inti;for(i=0;i<10;i++)if(c[0]!=c[i])return(1);return(0);}print(s)ints[];{intk;printf("%2d",j++);for(k=0;k<10;k++)printf("%4d",s[k]);printf(" ");}九、数组1.矩阵转换voidtrans(int*p,intn){inti,j,temp;int*pi,*pj;251 for(i=0;i<=n-1;i++){for(j=0;j<=i;j++){pi=p+i*n;/*p首地址*/pj=p+j*n;temp=pi[j];pi[j]=pj[i];pj[i]=temp;}}return;}main(){inta[4][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};inti,j;printf("beforetransform: ");for(i=0;i<=3;i++){for(j=0;j<=3;j++)printf("%d",a[i][j]);printf(" ");}trans((int*)a,4);printf("aftertransform: ");for(i=0;i<=3;i++){for(j=0;j<=3;j++)printf("%d",a[i][j]);printf(" ");}return;}2.螺旋数组1#include"stdio.h"#include"iostream.h"intarray[11][11];251 inttemp;intROW;voidgodown(int&m,int&a){for(temp=1;temp<=ROW;temp++)if(array[temp][a]==0)array[temp][a]=m++;a++;}voidgoright(int&m,int&b){for(temp=1;temp<=ROW;temp++)if(array[b][temp]==0)array[b][temp]=m++;b--;}voidgoup(int&m,int&c){for(temp=ROW;temp>0;temp--)if(array[temp][c]==0)array[temp][c]=m++;c--;}voidgoleft(int&m,int&d){for(temp=ROW;temp>0;temp--)if(array[d][temp]==0)array[d][temp]=m++;d++;}voidmain(){inta,b,c,d,max,m;cout<<"请输入缧旋方阵的维数n(不能大于10):";cin>>ROW;cout<#include#include#include#defineh5//height#definew5//widthvoidmain(){inta[h][w];intd=0,direct[4][2]={{0,1},{1,0},{0,-1},{-1,0}};intx=0,y=0,i;intx1,y1;memset(a,0,sizeof(a));for(i=1;i<=h*w;i++){a[y][x]=i;//nextpostionx1=x+direct[d][0];y1=y+direct[d][1];//trynextpostionif(x1<0||x1>=w||y1<0||y1>=h||a[y1][x1]!=0){//changedirectd=(d+1)%4;x1=x+direct[d][0];y1=y+direct[d][1];}251 x=x1;y=y1;}//displayarrayfor(y=0;yinta[]={0,1,2,5,8,7,6,3};intb[9];intc[9];intcount=0;main(){inti,j,k,t;voidprint();printf("Pleaseenteroriginalorderofdigits1~8:");for(i=0;i<8;i++)scanf("%d",&b[a[i]]);printf("Thesortingprocessisasfelow: ");print();//输出初始矩阵for(t=-1,j=0;j<8&&t==-1;j++)//确定1所在的位置if(b[a[j]]==1)t=j;//t记录1的位置for(j=0;j<8;j++)//把1的位置定为环首c[j]=a[(j+t)%8];for(i=2;i<9;i++)//从2开始依次调整数字//i正确的位置是i-1for(j=i-1;j<8;j++)if(b[c[j]]==i&&j!=i-1){b[4]=i;b[c[j]]=0;//空出来的位置为0print();for(k=j;k!=i-1;k--){251 b[c[k]]=b[c[k-1]];b[c[k-1]]=0;print();}b[c[k]]=i;b[4]=0;print();break;}elseif(b[c[j]]==i)break;}voidprint(void){intc;for(c=0;c<9;c++)if(c%3==2)printf("%2d ",b[c]);elseprintf("%2d",b[c]);printf("---%2d--- ",count++);}5.数组操作#includevoidmain(){charstrg[40],*there,one,two;int*pt,list[100],index;strcpy(strg,"Thisisacharacterstring.");one=strg[0];/*one和two是相同的*/two=*strg;printf("第一输出的是%c%c ",one,two);one=strg[8];two=*(strg+8);printf("第二输出的是%c%c ",one,two);there=strg+10;/*strg+10等同于strg[10]*/printf("第三输出的是%c ",strg[10]);printf("第四输出的是%c ",*there);for(index=0;index<100;index++)list[index]=index+100;pt=list+27;printf("第五输出的是%d ",list[27]);printf("第六输出的是%d ",*pt);}251 6.桶排序#includevoidcomp(intk[],intm,intl){inti=10,j=0,z=1,y=1,x,w,b[500][10];for(w=0;w0){z=l/i;i=i*10;++j;//记录最大数的位数}i=10;while(j>0){for(z=0;z<=m;z++){x=(k[z]/y)%i;b[z][x]=k[z];}w=0;for(z=0;z<10;z++)for(x=0;x=0){k[w]=b[x][z];b[x][z]=-1;w++;}}--j;y=y*10;}for(z=0;z=0){a[m]=n;++m;if(n>l)l=n;//记录最大数scanf("%d",&n);}comp(a,m,l);}7.杨辉三角形#includeintc(x,y);main(){inti,j,n=13;printf("N=");while(n>12)scanf("%d",&n);for(i=0;i<=n;i++){for(j=0;j<12-i;j++)printf("");for(j=1;jintf[11][11];intadjm[121][121];longfgf;voidcreatadjm(void);voide(int,int,int,int);voidtravel(int,int);intn,m;intmain(){inti,j,k,l;printf("Inputn:");scanf("%d",&n);m=n*n;creatadjm();for(i=1;i<=m;i++){for(j=1;j<=m;j++)printf("%2d",adjm[i][j]);printf(" ");}getchar();printf("Inputi,j:");scanf("%d%d",&i,&j);l=(i-1)*n+j;while((i>0)||(j>0)){for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=0;k=0;travel(l,k);251 printf("%d ",fgf);fgf=0;for(i=1;i<=n;i++){for(j=1;j<=n;j++)printf("%4d",f[i][j]);printf(" ");}getchar();printf("Inputi,j:");scanf("%d%d",&i,&j);l=(i-1)*n+j;}return0;}voidcreatadjm(){inti,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=0;for(i=1;i<=m;i++)for(j=1;j<=m;j++)adjm[i][j]=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]==0){f[i][j]=1;if((i+2<=n)&&(j+1<=n))e(i,j,i+2,j+1);if((i+2<=n)&&(j-1>=1))e(i,j,i+2,j-1);if((i-2>=1)&&(j+1<=n))e(i,j,i-2,j+1);if((i-2>=1)&&(j-1>=1))e(i,j,i-2,j-1);if((j+2<=n)&&(i+1<=n))e(i,j,i+1,j+2);if((j+2<=n)&&(i-1>=1))e(i,j,i-1,j+2);if((j-2>=1)&&(i+1<=n))e(i,j,i+1,j-2);if((j-2>=1)&&(i-1>=1))e(i,j,i-1,j-2);}return;}voidtravel(intp,intr){inti,j,q;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]>r)f[i][j]=0;r=r+1;251 i=((p-1)/n)+1;j=((p-1)%n)+1;f[i][j]=r;fgf++;//if(r==25)printf("%d ",p);/*printf("i=%d,j=%d,r=%d ",i,j,r);getchar();*/for(q=1;q<=m;q++){i=((q-1)/n)+1;j=((q-1)%n)+1;if((adjm[p][q]==1)&&(f[i][j]==0))travel(q,r);}return;}voide(inti1,intj1,inti2,intj2){adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;return;}2.骑士遍历2求解骑士游历问题显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历，这时记住解的每一步需要记住两件事：1.当前步的行列位置2.当前步已经试探过哪些方向了，以便回溯回来时能够选择一个新的方向进行试探所以使用两个数组，数组board记住棋盘的每个位置是在马的第几步到达的，这反映了问题的解，即第几步到哪个位置。数组direction记住在棋盘的某个位置已经试探过的方向，每个位置有八个方向，可按某种顺序对八个方向编号，然后在每个位置按编号顺序试探方向。在确定数据结构之后，同样需要确定下面几个问题：1.怎样的状态是初始状态。2.怎样选择当前步可能的路线3.怎样表示向前推进一步4.怎样回溯及清除当前步的痕迹显然初始状态是棋盘的每个位置都置为第0步到达（即还没有到达），每个位置都还没有选择任何方向（可赋值MAX_DIR(=8)表示没有选择方向）。选择当前步可能的路线就是在当前位置选择一个方向来游历下一步。在选择的时候同样需要区分是从第0个方向开始考虑还是从上一次的下一个方向开始考虑。为了方便从下一个方向开始考虑，实际上数组direction在某一位置(curr_x,curr_y)的值记住的是从上一位置选择了哪个编号的方向而到达的，这样容易回溯到上一位置，而且容易在回溯到上一位置之后从下个一方向重新试探。251 向前推进一步则要根据所选择的方向推进到下一位置，记住到下一位置所选择的方向，下一位置是第几步到达的，然后增加步数。回溯一步则要标记当前位置没有到达过（将到达的步数置为0），根据上一步到当前位置的所选择的方向（这个方向是记录当前位置所对应的direction数组中）而回溯到上一位置，然后减少步数。下面程序用类KNIGHT来封装数组board、direction、当前位置(curr_x,curr_y)、当前步数(step)，并且使用last_direction来记住上一位置到当前位置所选择的方向。为了方便计算选择一个方向后从当前推进到下一位置，使用数组var_x和var_y来记住每个方向在x方向和y方向的改变值。这个类中提供的方法的含义与类QUEEN类似。为节省篇幅起见，我们将类的界面、实现及演示放在了同一文件。///////////////////////////////////////////////////////////////////////程序二：求解骑士游历问题的程序//文件：KNIGHT.CPP//功能：使用回溯算法求解骑士游历问题#include#includeenumBOOLEAN{TRUE=1,FALSE=0};constintMAX_WIDTH=30;constintMAX_DIR=8;classKNIGHT{public://FUNCTION:设置初始状态KNIGHT(intwidth);//FUNCTION:用比较直观的方式打印问题的解//REQUIRE:必须先调用了成员函数tourist()voidprint();//FUCTION:根据马的起始位置(start_x,start_y)使用回溯算法求骑士游历问题的一个解//REQUIRE:(start_x,start_y)必需在所设置的棋盘宽度范围内BOOLEANtourist(intstart_x,intstart_y);protected://FUNCTION:初始化记录所选方向的数组，将每个值置为MAX_DIRvoidinit_direction();//FUNCTION:初始化记录马在第几步到位每个位置的数组，将每个值置为0voidinit_chessboard();//FUNCTION:设置初始状态，包括初始化方向数组和棋盘数组，并设置马的初始位置voidset_start(intx,inty);//FUNCTION:在当前位置选择一个方向以推进到下一位置//RETURN:如果可选择一个方向推进则返回TRUE，否则返回FALSE//NOTE:将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定virtualBOOLEANselect_direction();//FUNCTION:从当前位置回溯到上一位置251 //NOTE:将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定virtualvoidbackward();//FUNCTION:从当前位置推进到下一位置//NOTE:将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定virtualvoidforward();//FUNCTION:判断马是否能够走向位置(x,y)。//RETURN:如果马已经到过该位置，或该位置超出棋盘范围返回FALSE，否则返回TRUEBOOLEANis_legal(intx,inty);//FUNCTION:判断是否回溯到初始状态//RETURN:如果步数回到第1步则表示回到初始状态而返回TRUE，否则返回FALSEBOOLEANback_to_start();//FUNCTION:判断是否游历完所有位置//RETURN:如果步数等于棋盘格子数则表示游历完所有位置而返回TRUE，否则返回FALSEBOOLEANis_end();//下面两个数组用来记住选择某个方向后，推进到下一位置时x方向和y方向的值的变化intvar_x[MAX_DIR];intvar_y[MAX_DIR];//记录马第几步到达某个位置的棋盘数组intchessboard[MAX_WIDTH][MAX_WIDTH];//记录马在某个位置是在上一位置选择第几个方向到达的intdirection[MAX_WIDTH][MAX_WIDTH];intwidth;//棋盘宽度intcurr_x,curr_y;//马的当前位置intstep;//已经游历的步数intlast_direction;//上一位置到当前位置所选的方向};KNIGHT::KNIGHT(intwidth){this->width=width;init_direction();total_step=0;}voidKNIGHT::print(){intx,y;cout<<"+";for(x=0;x=width)returnFALSE;if(y<0||y>=width)returnFALSE;if(chessboard[x][y]>0)returnFALSE;returnTRUE;}BOOLEANKNIGHT::back_to_start(){if(step==1)returnTRUE;elsereturnFALSE;}BOOLEANKNIGHT::is_end(){if(step>width*width)returnTRUE;elsereturnFALSE;}voidKNIGHT::set_start(intx,inty){curr_x=x;curr_y=y;step=1;chessboard[x][y]=step;step=step+1;direction[x][y]=MAX_DIR;last_direction=MAX_DIR;}BOOLEANKNIGHT::select_direction(){inttry_x,try_y;//last_direction为MAX_DIR表示当前位置是一个新的位置，在新推进到某个位置(curr_x,curr_y)时，//direction[curr_x][curr_y]会记录上一位置到(curr_x,curr_y)时所选择的方向，这时//last_direction置为MAX_DIR用来标记该位置是新推进的位置。if(last_direction==MAX_DIR)last_direction=0;elselast_direction=last_direction+1;while(last_direction,";cout<<"Width:"<#defineMAX10intnRow=5,nCol=4;/*countchessboard*/intd[8][2]={{1,2},{2,1},{2,-1},{1,-2},/*nextstepadded*/{-1,-2},{-2,-1},{-2,1},{-1,2}};intflag[MAX][MAX];intnSolution;voidsearch(int,int);/*searchtheway*/voidmain(){introw,col,i,j;//clrscr();//gotoxy(1,12);/*initthedata*/printf("Inputthechessboardwidthandheight(nRow,nCol):");scanf("%d,%d",&nRow,&nCol);while(nRow>MAX||nRow<1||nCol>MAX||nCol<1){printf("error!inputagain:");scanf("%d,%d",&nRow,&nCol);}251 printf("Inputthestartpoint(row,col):");scanf("%d,%d",&row,&col);while(row>=nRow||row<0||col>=nCol||col<0){printf("error!inputagain:");scanf("%d,%d",&row,&col);}/*initdataend*/for(i=0;i=0&&nextCol=0&&flag[nextRow][nextCol]==0){flag[nextRow][nextCol]=1;//gotoxy(nextRow*3+4,nextCol+2);step++;printf("%d",step);if(step0)printf(" %02d-%02d-%dwas",month,day,year);if(numbnow-daynumb<0)printf(" %02d-%02d-%dwillbe",month,day,year);printf("a%s ",days[weekday]);}/*endMAIN*//*************************************************************GETDAYS-Fromintegervaluesofyear(YYYY),month**(MM)andday(DD)thissubroutinereturnsa**doublefloatnumberwhichrepresentsthe**numberofdayssinceJan1,1980(day1).**ThisroutineistheoppositeofGETDATE.*************************************************************/doublegetdays(year,month,day)intyear,month,day;{inty,m;doublea,b,d,daynumb;doublefloor(),intg();/************************************makecorrectionfornoyear0************************************/if(year<0)y=year+1;elsey=year;/***********************************************************JanandFebaremonths13and14inthiscalculation***********************************************************/251 m=month;if(month<3){m=m+12;y=y-1;}/****************************calculateJuliandays****************************/d=floor(365.25*y)+intg(30.6001*(m+1))+day-723244.0;/************************************************useJuliancalendarifbeforeOct5,1582************************************************/if(d<-145068.0)daynumb=d;/***************************************otherwiseuseGregoriancalendar***************************************/else{a=floor(y/100.0);b=2-a+floor(a/4.0);daynumb=d+b;}return(daynumb);}/*endGETDAYS*//*********************************************************GETDATE-Thisroutinetakesadoublefloatnumber**representingthenumberofdayssinceJan1,**1980(day1)andreturnstheyearmonthand**dayaspointerintegers**ThisroutineistheoppositeofGETDAYS*********************************************************/getdate(numb)doublenumb;{doublea,aa,b,c,d,e,z;doubledate;date=numb;z=intg(date+2444239.0);if(date<-145078.0)a=z;else{aa=floor((z-1867216.25)/36524.25);a=z+1+aa-floor(aa/4.0);251 }b=a+1524.0;c=intg((b-122.1)/365.25);d=intg(365.25*c);e=intg((b-d)/30.6001);day=b-d-intg(30.6001*e);if(e>13.5)month=e-13.0;elsemonth=e-1.0;if(month>2)year=c-4716.0;elseyear=c-4715.0;if(year<1)--year;return;}/*endGETDATE*//*********************************************************WEEKDAYS-Thisroutinetakesadoublefloatnumber**representingthenumberofdayssinceJan1,**1980(day1)andreturnsthedayoftheweek**where1=Sunday,2=Tuesday,etc.*********************************************************/intweekdays(numb)doublenumb;{doubledd;intday;dd=numb;while(dd>28000.0)dd=dd-28000.0;while(dd<0)dd=dd+28000.0;day=dd;day=((day+1)%7)+1;return(day);}/*********************************************************FRACT-Thisroutinetakesadoublefloatnumber**andreturnsthefractionalpartasadouble**floatnumber*********************************************************/doublefract(numb)doublenumb;{intinumb;doublefnumb;while(numb<-32767)numb+=32767;while(numb>32767)numb-=32767;inumb=numb;251 fnumb=inumb;return(numb-fnumb);}/*endFRACT*//*********************************************************FLOOR-Thisroutinetakesadoublefloatnumber**andreturnsthenextsmallestinteger*********************************************************/doublefloor(numb)doublenumb;{doublefract(),intg();doubleout;out=intg(numb);if(numb<0&&fract(numb)!=0)out-=1.0;return(out);}/*endFLOOR*//*********************************************************INTG-Thisroutinetakesadoublefloatnumber**andreturnstheintegerpartasadouble**floatnumber*********************************************************/doubleintg(numb)doublenumb;{doublefract();return(numb-fract(numb));}/*endINTG*/2.万年历的算法摘自:星期、干支、二十八宿计算公式打印本页关闭本窗口1.求星期公式星期=[5+A(实际天数)]mod72.干支计算公式六十甲子干支序号，从1->59->0。六十甲子干支序号=[23+A(实际天数)]mod603.二十八宿计算公式二十八宿序号=[23+A(实际天数)]mod284.实际天数A的计算A=B(基本天数)+C(闰日天数)251 B=(计算年-1)*365+(要计算到年的月日天数)例：1984年2月1日的基本天数B=(1984-1)*365+(31+1)=723827(天)，其中，31是1月为31天，1为2月1日为1天。公元308年8月28日的基本天数B=(308-1)*365+(31+28+31+30+31+30+31+27)=112055+239=112294(天)这里的(要计算到年的月日天数)，用的是公历，月日天数的规则我好象小学就学过了。哈哈……C=(计算年-1)div4-误差修正值+fixValue2fixValue2为0或者1。常值为0，当年数为闰年(公历闰年法)之中的3月1日之后的为1。误差修正值推算：公元元年1月1日至1582年10月14日为0。1582年10月15日至1699年12月31日为10。从1701年1月1日起每增加一个世纪累加1，但能被400除尽的世纪不累加1。此方法推算即可。--有一个问题，1700年这一年的修正值应为多少呢？算法中正好没有讲到，但看来应该是10。例1701年1月1日起误差值为11，而1801年1月1日起误差修正值为12，而1901年1月1日起误差修正值为13，但2001年误差修正值仍为13，因为2000年能被400整除，故不累加。而2101年1月1日起误差修正值为14。5.实例：1998.3.15的星期、干支与二十八宿B=(1998-1)*365+(31+28+15)=728979C=(1998-1)div4-13+0=486A=B+C=728979+486=729465星期序号=(5+729465)mod7=0，即为星期日干支序号=(13+729465)mod60=58，即为辛酉二十八宿序号=(23+729465)mod28=4，即为房===================================================好可怕！还有一些其它公式……但好象有些参数不知道怎么得到：二十四节交节日算法：用已知年的交接时辰加上22个小时35分，超过24要减去24，分数足60进1个小时，即得到8年后的各节交节时辰。如2000年雨水交节时辰为16时22分，则2008年雨水交节时辰为14时52分。因为16时22分+22时35分=38时57分。38-24=14时。谁知道公元元年到公元八年的交节日，这个算法就可以实现了。--好象逆算法可以解决这个问题。谁试试？农历闰月算法：农历中，二十四节气(十二节气和十二中气)的中气落在月末的话，下251 个月就没有中气。农历将这种有节(节气)无气(中气)的月份规定为闰月。平均计算，19年有七个闰月。但二十四个节气的十二节气和十二中气是怎么分的呢？我没有资料，估记应该是一节气一中气这样交叉。:(unitCNYear;interfaceusessysutils;typeTCNDate=Cardinal;functionDecodeGregToCNDate(dtGreg:TDateTime):TCNDate;functionGetGregDateFromCN(cnYear,cnMonth,cnDay:word;bLeap:Boolean=False):TDateTime;functionGregDateToCNStr(dtGreg:TDateTime):String;functionisCNLeap(cnDate:TCNDate):boolean;implementationconstcstDateOrg:Integer=32900;//公历1990-01-27的TDateTime表示对应农历1990-01-01constcstCNYearOrg=1990;constcstCNTable:array[cstCNYearOrg..cstCNYearOrg+60]ofWORD=(//unsigned16-bit24402,3730,3366,13614,2647,35542,858,1749,//199723401,1865,1683,19099,1323,2651,10926,1386,//200532213,2980,2889,23891,2709,1325,17757,2741,//201339850,1490,3493,61098,3402,3221,19102,1366,//20212773,10970,1746,26469,1829,1611,22103,3243,//20291370,13678,2902,48978,2898,2853,60715,2635,//20371195,21179,1453,2922,11690,3474,32421,3365,//20452645,55901,1206,1461,14038);//2050//建表方法：//0101111101010010高四位是闰月位置,后12位表示大小月,大月30天,小月29天,//闰月一般算小月,但是有三个特例2017/06,2036/06,2047/05//对于特例则高四位的闰月位置表示法中的最高为设置为1特殊处理用wLeapNormal变量////2017/0628330->610982036/0627947->607152047/0523133->55901//如果希望用汇编,这里有一条信息:农历不会滞后公历2个月.//将公历转换为农历//返回:12位年份+4位月份+5位日期functionDecodeGregToCNDate(dtGreg:TDateTime):TCNDate;variDayLeave:Integer;wYear,wMonth,wDay:WORD;i,j:integer;251 wBigSmallDist,wLeap,wCount,wLeapShift:WORD;labelOK;beginresult:=0;iDayLeave:=Trunc(dtGreg)-cstDateOrg;DecodeDate(IncMonth(dtGreg,-1),wYear,wMonth,wDay);if(iDayLeave<0)or(iDayLeave>22295)thenExit;//RaiseException.Create('目前只能算1990-01-27以后的');//RaiseException.Create('目前只能算2051-02-11以前的');fori:=Low(cstCNTable)toHigh(cstCNTable)dobeginwBigSmallDist:=cstCNTable[i];wLeap:=wBigSmallDistshr12;ifwLeap>12thenbeginwLeap:=wLeapand7;wLeapShift:=1;endelsewLeapShift:=0;forj:=1to12dobeginwCount:=(wBigSmallDistand1)+29;ifj=wLeapthenwCount:=wCount-wLeapShift;ifiDayLeave0;end;function251 GetGregDateFromCN(cnYear,cnMonth,cnDay:word;bLeap:Boolean=False):TDateTime;vari,j:integer;DayCount:integer;wBigSmallDist,wLeap,wLeapShift:WORD;begin//0101010010101111高四位是闰月位置,后12位表示大小月,大月30天,小月29天,DayCount:=0;if(cnYear<1990)or(cnYear>2050)thenbeginResult:=0;Exit;end;fori:=cstCNYearOrgtocnYear-1dobeginwBigSmallDist:=cstCNTable[i];if(wBIgSmallDistand$F000)<>0thenDayCount:=DayCount+29;DayCount:=DayCount+12*29;forj:=1to12dobeginDayCount:=DayCount+wBigSmallDistand1;wBigSmallDist:=wBigSmallDistshr1;end;end;wBigSmallDist:=cstCNTable[cnYear];wLeap:=wBigSmallDistshr12;ifwLeap>12thenbeginwLeap:=wLeapand7;wLeapShift:=1;//大月在闰月.endelsewLeapShift:=0;forj:=1tocnMonth-1dobeginDayCount:=DayCount+(wBigSmallDistand1)+29;ifj=wLeapthenDayCount:=DayCount+29;wBigSmallDist:=wBigSmallDistshr1;end;ifbLeapand(cnMonth=wLeap)then//是要闰月的吗?DayCount:=DayCount+30-wLeapShift;result:=cstDateOrg+DayCount+cnDay-1;end;//将日期显示成农历字符串.functionGregDateToCNStr(dtGreg:TDateTime):String;consthzNumber:array[0..10]ofstring=('零','一','二','三','四','五','六','七','八','九','十');251 functionConvertYMD(Number:Word;YMD:Word):string;varwTmp:word;beginresult:='';ifYMD=1thenbegin//年份whileNumber>0dobeginresult:=hzNumber[NumberMod10]+result;Number:=NumberDIV10;end;Exit;end;ifNumber<=10thenbegin//可只用1位ifYMD=2then//月份result:=hzNumber[Number]else//天result:='初'+hzNumber[Number];Exit;end;wTmp:=NumberMod10;//个位ifwTmp<>0thenresult:=hzNumber[wTmp];wTmp:=NumberDiv10;//十位result:='十'+result;ifwTmp>1thenresult:=hzNumber[wTmp]+result;end;varcnYear,cnMonth,cnDay:word;cnDate:TCNDate;strLeap:string;begincnDate:=DecodeGregToCNDate(dtGreg);ifcnDate=0thenbeginresult:='输入越界';Exit;end;cnDay:=cnDateand$1F;cnMonth:=(cnDateshr5)and$F;cnYear:=(cnDateshr9)and$FFF;//测试第22位,为1表示闰月ifisCNLeap(cnDate)thenstrLeap:='(闰)'elsestrLeap:='';result:='农历'+ConvertYMD(cnYear,1)+'年'+ConvertYMD(cnMonth,2)+'月'+strLeap+ConvertYMD(cnDay,3);end;251 end.三、其它问题算法1.N皇后问题回溯算法/**File:queen.c*Description:求N皇后问题回溯算法*Created:2001/11/12*Author:JustinHou[mailto:justin_hou@hotmail.com]*/#include#defineDelayTime20000/*显示棋局时间*/#defineTopX10/*棋盘左上角x坐标*/#defineTopY5/*棋盘左上角y坐标*/intN;/*皇后数量*/inta[8],b[15],c[15];/**a[col-1]记录第col列有无皇后,1表示有。*b[row+col-2]记录从左上数第row+col-1条斜率为1的线上有无皇后。*c[row-col+7]记录从右上数第row-col+8条斜率为-1的线上有无皇后。*/intNum=0;introw;voidBackTrack(introw){intcol;/*局部变量*/for(col=1;col<=N;col++){if(a[col-1]+b[row+col-2]+c[row-col+N-1]==0){a[col-1]=1;/*更改数据*/b[row+col-2]=1;c[row-col+N-1]=1;gotoxy(col*2+TopX,row+TopY);/*画皇后*/putch('Q');if(row14){scanf("%d",&N);if(N>14)printf("Twohugenumber,inputagain:");if(N<=0)printf("Can'ssmallerthan1,again:");}clrscr();for(i=1;i<=N;i++)/*画棋盘(Chessboard)*/{for(j=1;j<=N;j++){gotoxy(i*2+TopX,j+TopY);putch('.');}}BackTrack(1);/*开始回溯算法*/gotoxy(12,17);/*显示最后结果*/printf("Thereare%dkindsofsolution. ",Num);getch();}251 2.动态计算网络最长最短路线/**File:longest.c*Desciption:动态规划算法计算网络的最长路线和最短路线*Created:2001/12/2*Author:JustinHou[mailto:justin_hou@hotmail.com]**/#include#defineN7/*顶点数目*/#defineI999/*表示无穷大*/intgraph[N][N]={/*图的邻接矩阵*/{I,4,5,8,I,I,I},{I,I,I,6,6,I,I},{I,I,I,5,I,7,I},{I,I,I,I,8,9,9},{I,I,I,I,I,I,5},{I,I,I,I,I,I,4},{I,I,I,I,I,I,I}};intList[N];/*存放拓扑序列*/intTopologicalOrder();/*拓扑排序函数*/voidmain()/*主函数*/{inti,j,k,l;intee[N],el[N];/*最长最短距离*/intpath_e[N][N],path_l[N][N],n_e[N],n_l[N];/*记录路径数据*//*初始化数据*/for(i=0;iel[j]){/*更新最长路径长度*/el[j]=graph[k][j]+el[k];/*更新最长路线*/for(l=0;l#include#include#include#defineMAX_CITIES15/*城市的数目*/#defineINFINITY9999/*表示无穷大*/#defineIINFINITY/*表示无穷大*/typedefstruct_POINT{/*定义点的结构*/intx;inty;}POINT;typedefstruct_EDGE{/*定义边的结构*/inthead;inttail;}EDGE;typedefstruct_PATH{/*定义路径结构*/EDGEedge[MAX_CITIES];intedgesNumber;}PATH;typedefstruct_MATRIX{/*定义花费矩阵结构*/intdistance[MAX_CITIES][MAX_CITIES];intcitiesNumber;}MATRIX;typedefstruct_NODE{/*定义树结点*/intbound;/*结点的花费下界*/MATRIXmatrix;/*当前花费矩阵*/PATHpath;/*已经选定的边*/}NODE;intminDist=INFINITY;intGraphDriver;intGraphMode;intErrorCode;POINTcity[MAX_CITIES]={{459,333},{345,234},{362,245},{332,183},{323,343},{630,345},{154,263},{213,112},{432,254},{534,223},{334,333},{432,234},{23,442},{600,400},{500,300}};intSimplify(MATRIX*);/*归约矩阵并返回归约常数*/intMatrixSize(MATRIX,PATH);/*计算矩阵阶数*/EDGESelectBestEdge(MATRIX);/*返回最合适的分枝边*/251 MATRIXInitMatrix(void);/*初始化费用矩阵数据*/MATRIXLeftNode(MATRIX,EDGE);/*计算左枝结点费用矩阵*/MATRIXRightNode(MATRIX,EDGE,PATH);/*计算右枝结点费用矩阵*/PATHAddEdge(EDGE,PATH);/*将边添加到路径数组中*/PATHBABA(NODE*);/*分枝回溯函数B-and-BAr.*/PATHMendPath(PATH,MATRIX);/*修补没有完成的路径*/voidShowMatrix(MATRIX);/*文本显示费用矩阵调试用*/voidShowPath(PATH);/*文本显示路径*/voidDrawPath(PATH);/*图形显示路径*/voidmain(){PATHpath;NODEroot;GraphDriver=DETECT;initgraph(&GraphDriver,&GraphMode,"");ErrorCode=graphresult();if(ErrorCode!=grOk){printf("GraphicsSystemError:%s ",grapherrormsg(ErrorCode));exit(1);}/*初始化数据，归约，建立根结点*/root.matrix=InitMatrix();root.bound=Simplify(&(root.matrix));(root.path).edgesNumber=0;/*进入搜索循环，最终返回最佳路线*/path=BABA(&root);/*显示结果*/DrawPath(path);ShowPath(path);printf(" minDist:%d ",minDist);getch();closegraph();}/*初始化数据*/MATRIXInitMatrix(){introw,col,n;doubledx,dy;MATRIXc;n=MAX_CITIES;/*有待完善数据读取方式*/c.citiesNumber=n;for(row=0;rowmatrix,root->path)==2){if(root->boundbound;minPath=MendPath(root->path,root->matrix);free(root);return(minPath);}}/*根据左下界尽量大的原则选分枝边*/setcolor(7);selectedEdge=SelectBestEdge(root->matrix);line(city[selectedEdge.head].x,city[selectedEdge.head].y,city[selectedEdge.tail].x,city[selectedEdge.tail].y);putpixel(city[selectedEdge.head].x,city[selectedEdge.head].y,MAGENTA);putpixel(city[selectedEdge.tail].x,city[selectedEdge.tail].y,MAGENTA);/**建立左右分枝结点*/right=(NODE*)malloc(sizeof(NODE));if(right==NULL){fprintf(stderr,"Errormallocbranch. ");251 exit(-1);}/*使左枝结点站局原根结点位置，节省空间*/left=root;/*初始化左右分枝结点*/right->matrix=RightNode(root->matrix,selectedEdge,root->path);right->bound=root->bound+Simplify(&(right->matrix));right->path=AddEdge(selectedEdge,root->path);left->matrix=LeftNode(left->matrix,selectedEdge);left->bound=left->bound+Simplify(&(left->matrix));/*如果右结点下界小于当前最佳答案，继续分枝搜索*/if(right->boundboundpath).edgesNumber!=0){free(left);}gotoxy(1,1);printf("CurrentminDist:%d",minDist);return(minPath);}/*修补路径*/PATHMendPath(PATHpath,MATRIXc){introw,col;EDGEedge;251 intn=c.citiesNumber;for(row=0;rowcitiesNumber;h=0;/*行归约*/for(row=0;rowdistance[row][col]distance[row][col];}}/*如果本行元素都是无穷，说明本行已经被删除*/if(min_dist==INFINITY)continue;/*本行每元素减去最小元素*/for(col=0;coldistance[row][col]!=INFINITY){c->distance[row][col]-=min_dist;}}/*计算归约常数*/h+=min_dist;}/*列归约*/for(col=0;coldistance[row][col]distance[row][col];}}/*如果本列元素都是无穷，说明本列已经被删除*/if(min_dist==INFINITY)continue;/*本列元素减去最小元素*/for(row=0;rowdistance[row][col]!=INFINITY){c->distance[row][col]-=min_dist;}}/*计算归约常数*/h+=min_dist;}return(h);}/*搜索所有花费为零的边中最合适的，使左枝下界更大*/EDGESelectBestEdge(MATRIXc){introw,col;intn=c.citiesNumber;intmaxD;EDGEbest,edge;/*所用函数声明*/intD(MATRIX,EDGE);maxD=0;for(row=0;row#include#include#defineTRUE(1)#defineFALSE(0)#defineMAX_CITIES(10)#defineINFINITY(999)#defineIINFINITYtypedefintbool;/*定义边结构*/typedefstruct_EDGE{inthead;inttail;}EDGE;/*定义路径结构*/typedefstruct_PATH{EDGEedge[MAX_CITIES];intedgesNumber;}PATH;/*定义花费矩阵结构*/typedefstruct_MATRIX{intdistance[MAX_CITIES][MAX_CITIES];intcitiesNumber;}MATRIX;/*定义树结点*/typedefstruct_NODE{intbound;/*相应于本结点的花费下界*/MATRIXmatrix;/*当前花费矩阵*/PATHpath;/*已经选定的边*/struct_NODE*left;/*左枝*/struct_NODE*right;/*右枝*/}NODE;251 intSimplify(MATRIX*);EDGESelectBestEdge(MATRIX);MATRIXLeftNode(MATRIX,EDGE);MATRIXRightNode(MATRIX,EDGE,PATH);PATHAddEdge(EDGE,PATH);PATHBABA(NODE);PATHMendPath(PATH,MATRIX);intMatrixSize(MATRIX,PATH);voidShowMatrix(MATRIX);voidShowPath(PATH,MATRIX);main(){PATHpath;NODEroot={0,/*花费下界*/{{{I,1,2,7,5},/*花费矩阵*/{1,I,4,4,3},{2,4,I,1,2},{7,4,1,I,3},{5,3,2,3,I}},5},/*城市数目*/{{0},0},/*经历过的路径*/NULL,NULL/*左枝与右枝*/};/*归约，建立根结点*/root.bound+=Simplify(&root.matrix);/*进入搜索循环*/path=BABA(root);ShowPath(path,root.matrix);}/**算法主搜索函数，Branch-And-BoundAlgorithmSearch*root是当前的根结点，已归约，数据完善*/PATHBABA(NODEroot){inti;staticintminDist=INFINITY;staticPATHminPath;EDGEselectedEdge;NODE*left,*right;puts("CurrentRoot: ------------");ShowMatrix(root.matrix);printf("RootBound:%d ",root.bound);251 /*如果当前矩阵大小为2，说明还有两条边没有选，而这两条边必定只能有一种组合，*才能构成整体回路，所以事实上所有路线已经确定。*/if(MatrixSize(root.matrix,root.path)==2){if(root.boundbound=root.bound;/*继承父结点的下界*/left->matrix=LeftNode(root.matrix,selectedEdge);/*删掉分枝边*/left->path=root.path;/*继承父结点的路径，没有增加新边*/left->left=NULL;left->right=NULL;right->bound=root.bound;right->matrix=RightNode(root.matrix,selectedEdge,root.path);/*删除行列和回路边*/right->path=AddEdge(selectedEdge,root.path);/*加入所选边*/right->left=NULL;right->right=NULL;/*归约左右分枝结点*/left->bound+=Simplify(&left->matrix);right->bound+=Simplify(&right->matrix);/*链接到根*/root.left=left;root.right=right;/*显示到监视器*/puts("RightBranch: ------------");ShowMatrix(right->matrix);puts("LeftBranch: -----------");ShowMatrix(left->matrix);/*如果右结点下界小于当前最佳答案，继续分枝搜索*/251 if(right->boundbound);printf("Thisbranchisdead. ");}/*如果右结点下界小于当前最佳答案，继续分枝搜索*/if(left->boundbound);printf("Thisbranchisdead. ");}printf("Thebestanswernowis%d ",minDist);return(minPath);}/*修补路径*/PATHMendPath(PATHpath,MATRIXc){introw,col;EDGEedge;intn=c.citiesNumber;for(row=0;rowcitiesNumber;h=0;/*行归约*/for(row=0;rowdistance[row][col]distance[row][col];}}/*如果本行元素都是无穷，说明本行已经被删除*/if(min_dist==INFINITY)continue;/*本行每元素减去最小元素*/for(col=0;coldistance[row][col]!=INFINITY){c->distance[row][col]-=min_dist;}}/*计算归约常数*/h+=min_dist;}/*列归约*/for(col=0;coldistance[row][col]distance[row][col];}}/*如果本列元素都是无穷，说明本列已经被删除*/if(min_dist==INFINITY)continue;/*本列元素减去最小元素*/for(row=0;rowdistance[row][col]!=INFINITY){c->distance[row][col]-=min_dist;}}/*计算归约常数*/h+=min_dist;}return(h);251 }/*搜索所有花费为零的边中最合适的，使左枝下界更大*/EDGESelectBestEdge(MATRIXc){introw,col;intn=c.citiesNumber;intmaxD;EDGEbest,edge;/*所用函数声明*/intD(MATRIX,EDGE);maxD=0;for(row=0;row#defineN7intmiddle[N][N];voidShow(int,int);voidmain(){inti,j,l,k;unsignedlongm[N+1][N+1],min;intr[N+1]={10,20,50,1,100,4,20,2};/*矩阵维数*//*初始化*/for(i=1;i<=N;i++){m[i][i]=0;}/*每此增量加一*/for(l=1;lm[i][k]+m[k+1][j]+r[i-1]*r[k]*r[j]){251 min=m[i][k]+m[k+1][j]+r[i-1]*r[k]*r[j];middle[i][j]=k;}}m[i][j]=min;}}printf("M=");Show(1,N);printf(" MultiplyCount:%d ",m[1][N]);}voidShow(inti,intj){intk,m;if(i==j){printf("M%d",i);/*如果下一个是矩阵，输出*/}else{m=middle[i][j];/*分割成左右两组*/if(i!=m)printf("(");/*如果下一个显示的不是矩阵*/Show(i,m);/*显示左边的内容*/if(i!=m)printf(")");/*如果上一个显示的不是矩阵*/printf("x");/*打印乘法符号*/if(m+1!=j)printf("(");/*如果下一个显示的不是矩阵*/Show(m+1,j);/*显示右边的内容*/if(m+1!=j)printf(")");/*如果下一个显示的不是矩阵*/}}6.网络最短路径Dijkstra算法/**File:shortest.c*Description:网络中两点最短路径Dijkstra算法*ShortestPathDijkstraAlgorithm*Created:2001/11/25*Author:JustinHou[mailto:justin_hou@hotmail.com]*/#include#definetrue1#definefalse0#defineI9999/*无穷大*/#defineN20/*城市顶点的数目*/intcost[N][N]={251 {0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}};intdist[N];/*存储当前最短路径长度*/intv0='A'-65;/*初始点是A*/voidmain(){intfinal[N],i,v,w,min;/*初始化最短路径长度数据，所有数据都不是最终数据*/for(v=0;v%c:%2dt",v0+65,i+65,dist[i]);}}十一、小写数字转为大写数字1．小写数字转换成大写数字1#include#include#includechar*floattoch(floatm);staticcharchinese[]="零壹贰叁肆伍陆柒捌玖点";staticcharch[80];voidmain(){floatm;char*s;printf("InputNumber:");scanf("%f",&m);s=floattoch(m);printf(" %s ",s);}char*floattoch(floatm){chartmp[30];inti,j,k=0,flag=0,d=0,temp;floatn;i=m;do{j=i%10;251 tmp[k]=chinese[j*2];tmp[k+1]=chinese[j*2+1];k+=2;i/=10;}while(i);tmp[k]=0;//tmp[k]=0;printf("%d ",strlen(tmp));for(i=strlen(tmp)-1;i>=0;i-=2,d+=2){ch[d]=tmp[i-1];ch[d+1]=tmp[i];}i=(m-(int)m)*1000;k=0;temp=i;//待会判断用do{j=i%10;if(j)flag=1;if(flag){tmp[k]=chinese[j*2];tmp[k+1]=chinese[j*2+1];k+=2;}i/=10;}while(i);while(temp<100){//加入零tmp[k]=chinese[0];tmp[k+1]=chinese[1];k+=2;temp*=10;}tmp[k]=0;if(strlen(tmp)){ch[d]=chinese[20];ch[d+1]=chinese[21];d+=2;}for(i=strlen(tmp)-1;i>=0;i-=2,d+=2){ch[d]=tmp[i-1];251 ch[d+1]=tmp[i];}return(ch);}2．小写数字转换成大写数字2/***程序:123.45则输出“壹佰贰拾叁点肆伍”***/#include/*标准输入输出函数*/#include/*字符串函数*/#includevoidConvertN(intn,char*&p,boolIsSequece=true);/*声明函数ConvertN*/boolConvertSegment(intnumber,intn,char*&p,boolIsLastZiero);/*声明函数ConvertSegment*/boolChangeNumber(doubledbNumber,char*lpszvalues);/*声明函数ChangeNumber*/voidmain(){doubledb=-1200008.9876;printf("%lf ",db);charbuf[100];if(ChangeNumber(db,buf))printf("%s ",buf);db=1000000.98;printf("%lf ",db);if(ChangeNumber(db,buf))printf("%s ",buf);db=10000008.0987;printf("%lf ",db);if(ChangeNumber(db,buf))printf("%s ",buf);db=10200408.09007;printf("%lf ",db);if(ChangeNumber(db,buf))printf("%s ",buf);db=10020400.007;printf("%lf ",db);if(ChangeNumber(db,buf))printf("%s ",buf);}voidConvertN(intn,char*&p,boolIsSequece/*=true*/)/*定义函数ConvertN"小数位转换"将数字n(0<=n<=9)转换成中文后存入p,IsSequece控制存放顺序*/{251 if(n<0||n>9){printf("Error:数组超界! ");/*如果超过界限就输出错误*/exit(0);/*跳出函数*/}charnum[]="零壹贰叁肆伍陆柒捌玖";if(IsSequece)/*如果IsSequece为真就顺序存放*/{*p++=num[2*n];/*因为汉字是双字节的所以，在把阿拉伯数字转化时比如0对应的零是双字节，占数组的0和1的位置，其他的以此类推*/*p++=num[2*n+1];}else/*如果IsSequece为非即反序存放*/{*p++=num[2*n+1];*p++=num[2*n];}}boolConvertSegment(intnumber,intn,char*&p,boolIsLastZiero)/*定义函数ConvertSegment"整数位转换"将number转换成中文后反序存入字符指针pnumber为某数整数部分的第n节(由低位到高位从个位开始每4位为一节,n从0开始)*/{charnum1[]="拾佰仟";charnum2[]="点万亿兆";if(number==0){if(n==0){*p++=num2[2*n+1];*p++=num2[2*n];}returnIsLastZiero;}if(IsLastZiero){ConvertN(0,p,false);}*p++=num2[2*n+1];*p++=num2[2*n];boolflag=true;/*前面是否有零*/for(inti=0;number!=0&&i<4;i++){intm;251 m=number%10;if(m==0&&!flag){flag=true;ConvertN(0,p,false);}elseif(m!=0){flag=false;if(i==0){ConvertN(m,p,false);}else{*p++=num1[2*i+1];*p++=num1[2*i];ConvertN(m,p,false);}}number/=10;}if(i>=4)returnfalse;elsereturntrue;}boolChangeNumber(doubledbNumber,char*lpszvalues){/*定义函数ChangeNumber整数部分最多8位，小数部分最多6位*/if(dbNumber<0.0000001&&-dbNumber<0.0000001)//数位太小{strcmp(lpszvalues,"零");returntrue;}if(dbNumber>100000000L||-dbNumber>100000000L)//数位太大returnfalse;/*开始处理*/charbuf1[50],buf2[50],*p1=buf1,*p2=buf2;/*结果的整数部分和小数部分缓冲区*//*p1是整数指针p2是小数指针*/doublec=dbNumber;c=c>0?c:-c;/*取得大实数的整数部分和小数部分并非易事,long的长度直接限制了整数部分的长度,251 除非构造出更大的整数或直接利用实数计算,否则难以办到!此外受实数精度的影响,有时会导致小数部分的畸形!精请高手指点!!!*/unsignedlonga=(unsignedlong)c;/*整数部分*/doubleb=c-a;/*小数部分*//*printf("%lu ",a);printf("%lf ",b);printf("%lf ",c);*//*处理小数部分*/for(inti=0;i<6;i++){b*=10;/*将小数最高位向前进一位取得整数*/intn=int(b);ConvertN(n,p2);/*转换成字符数值*/b-=n;/*减去整数部分的数取得下一位小数,将其成为整数*/}*p2='';/*处理整数部分*/intcount=0;boolflag=false;while(a!=0){intbuf=a%10000;flag=ConvertSegment(buf,count++,p1,flag);a/=10000;}/*是否有负号*/char*p=lpszvalues;if(dbNumber<0){strcpy(p,"负");p+=2;}/*连接整数部分和小数部分*/p1--;while(p1>=buf1)*p++=*p1--;*p='';strcat(lpszvalues,buf2);returntrue;}251 3.小写数字转换成大写数字3#includevoidmain(){doublex,y;char*ch[]={"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"};char*ch1[]={"拾","佰","仟","万","拾","佰","仟","亿"};charnum[256];longi,n,j,m,y1;printf("input:");scanf("%lf",&x);n=(long)x;/*得整数部分*/y=x-n;/*得小数部分*/for(i=0;n!=0;i++){num[i]=(char)(n%10);n/=10;}m=i;num[i]='.';for(y=y*10;(long)((y-(long)y)*10);)/*如果小数位还是有数(非0)循环继续*/y*=10;/*小数转化为整数如0.11111转为11111.00...*/y1=(long)y;for(i=m+1;y1!=0;i++){num[i]=(char)(y1%10);y1=y1/10;}/*取各位上的数字*/for(n=0;;n++){if(num[n]=='.'){for(j=n-1;j>=0;j--)/*判断是否是万位,亿位..如是再判断是否是0如是就不输出零.*/{if(m<=5)if(m==5&&(int)num[j]==0);elseprintf("%s",ch[(int)num[j]]);/*输出大写壹..*/elseif(m%4==0&&(int)num[j]==0);elseprintf("%s",ch[(int)num[j]]);251 if(m>=2){printf("%s",ch1[m-2]);/*输出拾佰仟..如有2位就输出拾*/m=m--;}}printf("点");break;}}for(i=i-1;num[i]!='.';i--)printf("%s",ch[(int)num[i]]);/*输出小数部分*/}十二、效验算法1.Crctable/*CRCTABLE1.0PublicDomainbyCelsoMinnitti,JrFeb-06-94*//*Thisprogramwillgeneratethecrc16_tableandCRC32_table*//*thatareusedbyCMCRC.ASM*/#include#defineCRC32_POLYNOMIAL0xEDB88320#defineCRC16_POLYNOMIAL0xA001voidmain(){unsignedlongcrc32Table[256];unsignedintcrc16Table[256];unsignedintcrc;unsignedlongcrc32;inti,j;printf("CRCTABLE1.0PublicDomainbyCelsoMinnitti,JrFeb-06-94 ");for(i=0;i<256;i++){crc=i;for(j=8;j>0;j--){if(crc&1)crc=(crc>>1)^CRC16_POLYNOMIAL;elsecrc>>=1;}crc16Table[i]=crc;}251 printf(" crc16_tabletlabeltword");for(i=0;i<256;i++){if(!(i%32)&&i)printf(" ;%Xh",i);if(!(i%8))printf(" tdw");if(i%8!=7)printf("0%04Xh,",crc16Table[i]);elseprintf("0%04Xh",crc16Table[i]);}printf(" ");for(i=0;i<256;i++){crc32=i;for(j=8;j>0;j--){if(crc32&1)crc32=(crc32>>1)^CRC32_POLYNOMIAL;elsecrc32>>=1;}crc32Table[i]=crc32;}printf(" crc32_tabletlabeltdword");for(i=0;i<256;i++){if(!(i%16)&&i)printf(" ;%Xh",i);if(!(i%4))printf(" tdd");if(i%4!=3)printf("0%08lXh,",crc32Table[i]);elseprintf("0%08lXh",crc32Table[i]);}}十三、硬币情况1.for循环的#includemain(){inti,j,k,count=1;printf("TherearefollowingsmallexchangeplansforiYuannote: ");for(i=0;i<=100;i++)for(j=0;j<=100-i;j+=2)251 for(k=0;k<=100-i-2*j;k+=5)if(i+j+k==100)printf(count%4?"%d:1*%d+2*%d+5*%d":"%d:1*%d+2*%d+5*%d ",count++,i,j/2,k/5);getch();}2.硬币分法#include"stdio.h"main(){inti,j,k,s,n=0;/*i,j,k分别代表一分硬币、二分硬币和五分硬币*/printf("%5c%5c%5c ",'1','2','5');for(i=1;i<100;i++)for(j=1;j<50;j++)for(k=1;k<20;k++){s=1*i+j*2+k*5;if(s==100){printf("%5d%5d%5d ",i,j,k);++n;}}printf("Thewaysis%d ",n);}十四、字符1.单词倒转/*如何实现这个算法Thisisagooddaytoday->sihTsiadoogyadyadot*/#include"stdafx.h"#include"string.h"#include"malloc.h"char*fun(char*a);251 intmain(intargc,char*argv[]){char*string="Thisisagooddaytoday";char*ll=fun(string);printf("%s",ll);return0;}char*fun(char*a){char*ptt=(char*)malloc(strlen(a));ptt=a;char*ftt=(char*)malloc(strlen(a));*ftt='';charstep[]="";char*token;token=strtok(strdup(a),step);/*strtok()检索字符串s1,该字符串s1是由字符串s2中定义的定界符所分隔*//*strdup()将字符串s复制到最近建立的单元*/while(token!=NULL){strcat(ftt,strrev(token));/*strrev()将字符串s复制到最近建立的单元*/strcat(ftt,"");token=strtok(NULL,step);}*(ftt+strlen(a)-1)='';returnftt;}2.出字符/*由Andy自行修改为支持大小写转换*/#includemain(){inti=0,n=0;charascs[]={"abcdefghijklmnopqrstuvwxyz"};charascb[]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};chara,b[20];while((a=getchar())!=' '){if(a>=97&&a<=122)b[i]=asc[97+25-(int)a];elseif(a>=65&&a<=95)251 b[i]=asc[65+25-(int)a];i++;n++;}for(i=0;i/*字符串一半数总个数*/intcharf(chard[],intk,inti){if(d[k]==d[i-k]&&k==0)return(1);elseif(d[k]==d[i-k])charf(d,k-1,i);/*递归调用*/elsereturn(0);}main(){inti=0,n=0;chara,b[20];while((a=getchar())!=' '){b[i]=a;i++;}if(i%2==0)n=charf(b,(i/2),i-1);elsen=charf(b,(i/2-1),i-1);if(n==0)printf("不是回文");elseprintf("是回文");getch();251 }4.字符编辑这儿有两个函数,能进行在一个字符串中的插入和删除一个字符,有兴趣的可以参考一下.#include#includevoidcinsert(charccode,char*anystring,intspos){intp;p=strlen(anystring);spos=spos<0?0:spos;spos=spos>=p?p:spos;for(;p>=spos;p--)anystring[p+1]=anystring[p];anystring[spos]=ccode;}voidcdelete(char*anystring,intspos){intp;p=strlen(anystring);if(p>0&&spos>=0&&spos<=p){while(spos#include/*插入函数ccode待插入的字符anystring被插入的字符串spos插入到字符串的位置*/voidcinsert(charccode,char*anystring,intspos){intp;p=strlen(anystring);/*字符串的长度*/spos=spos<0?0:spos;/*插入范围*/spos=spos>=p?p:spos;for(;p>=spos;p--)251 anystring[p+1]=anystring[p];/*从数组最后那那个元素开始向上加*/anystring[spos]=ccode;/*插入该字符*/}/*删除函数anystring被删除的字符串spos删除第几个字符*/voidcdelete(char*anystring,intspos){intp;p=strlen(anystring);/*字符串的长度*/if(p>0&&spos>=0&&spos<=p){while(spos#defineMS20chara[MS]="whatisit";charb[MS]="*is*";intsearchStr(chars1[MS],chars2[MS],intp1,intp2);boolchazhao(chara[MS],charb[MS]);voidmain(){inti;cout<>i;}boolchazhao(chara[MS],charb[MS]){inti;i=searchStr(a,b,1,1);if(i!=0){i=i-strlen(b)+1;cout<next;}return(n);}ElemTypeget(structLNode**p,inti){intj=1;structLNode*q=*p;while(jnext;j++;}if(q!=null)return(q->data);elseprintf("位置参数不正确! ");}intlocate(structLNode**p,ElemTypex){intn=0;structLNode*q=*p;while(q!=null&&q->data!=x){q=q->next;n++;}if(q==null)return(-1);elsereturn(n+1);}voidinsert(structLNode**p,ElemTypex,inti){intj=1;structLNode*s,*q;s=(structLNode*)malloc(sizeof(structLNode));s->data=x;q=*p;if(i==1){s->next=q;p=s;}else{while(jnext!=null){q=q->next;j++;}if(j==i-1){251 s->next=q->next;q->next=s;}elseprintf("位置参数不正确! ");}}intdelete(structLNode**p,inti){intj=1;structLNode*q=*p,*t;if(i==1){t=q;*p=q->next;}else{while(jnext!=null){q=q->next;j++;}if(q->next!=null&&j==i-1){t=q->next;q->next=t->next;}elseprintf("位置参数不正确! ");}if(t=null)free(t);}voiddisplay(structLNode**p){structLNode*q;q=*p;printf("单链表显示:");if(q==null)printf("链表为空!");elseif(q->next==null)printf("%c ",q->data);else251 {while(q->next!=null){printf("%c->",q->data);q=q->next;}printf("%c",q->data);}printf(" ");}2.单循环链表#definenull0typedefcharElemType;typedefstructCircular{ElemTypedata;structLNode*next;};setnull(structCircular**p){*p=null;}intlength(structCircular**p){intn=0;structCircular*q=*p;while(q!=null){n++;q=q->next;}return(n);}ElemTypeget(structCircular**p,inti){intj=1;structCircular*q=*p;while(jnext;j++;251 }if(q!=null)return(q->data);elseprintf("positionparameterisincorrect! ");}intlocate(structCircular**p,ElemTypex){intn=0;structCircular*q=*p;while(q!=null&&q->data!=x){q=q->next;n++;}if(q=null)return(-1);elsereturn(n+1);}voidinsert(structCircular**p,ElemTypex,inti){intj=1;structCircular*s,*q;s=(structCircular*)malloc(sizeof(structCircular));s->data=x;q=*p;if(i==1){s->next=q;p=s;}else{while(jnext!=null){q=q->next;j++;}if(j==i-1){s->next=q->next;q->next=s;}251 elseprintf("positionparameterisincorrect! ");}}voiddelete(structCircular**p,inti){intj=1;structCircular*q=*p,*t;if(i==1){t=q;*p=q->next;}else{while(jnext!=null){q=q->next;j++;}if(q->next!=null&&j==i-1){t=q->next;q->next=t->next;}elseprintf("positionparameterisincorrect! ");}if(t=null)free(t);}voiddisplay(structCircular**p){structCircular*q;q=*p;printf("LinkListdisplay:");if(q==null)printf("LinkListisNull!");elseif(q->next==null)printf("%c ",q->data);else{while(q->next!=null){printf("%c->",q->data);q=q->next;251 }printf("%c",q->data);}printf(" ");}main(){structCircular*head,*q;chare;inti,n;chary;intselect,x1,x2,x3,x4,m;head=setnull();printf("请输入数据长度:")；scanf("%d",&n);for(i=1;ilength=nlenth;T->ch=(char*)malloc(nlenth*sizeof(char)+1);if(!T->ch){T->length=0;exit(overflow);}else{strcpy(T->ch,chars);251 return0;}}//strassignintstrlength(structsstring*S){S->length=strlen(S);returnS->ch;}//strlengthintstrcompare(structsstring*S,structsstring*T){ifS>MAXSTRLEN&&T>MAXSTRLENexit(overflow);if(strcmp(S->ch,T->ch)==0)return0;elseif(strcmp(S->ch,T->ch)>0)return1;elsereturn-1;}//strcompareintclearstring(structsstring*S){if(S->ch){free(S->ch);S->ch=NULL;S->length=0;}return0;}//clearstringintconcat(structsstring*T,structsstring*s1,structsstring*s2){if(s1[0]+s2[0]<=MAXSTRLEN){strcpy(T->ch,s1->ch);strcpy(T->ch,s2->ch);T[0]=S1[0]+S2[0];uncat=TRUE;}elseif(s1[0]ch,s1->ch);strcpy(T->ch,s2->ch);T[0]=MAXSTRLEN;uncat=FALSE;}else{T->ch=s1->lengthuncat=FALSE;}251 returnuncat;}//concatintsubstring(structsstring*sub,structsstring*S,intpos,intlen){char*p;inti;if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)return-1;else{sub->ch=(char*)malloc(len*sizeof(char)+1);p=S->ch;for(i=0;i<=pos-1;i++)p++;}strcpy(sub->ch,p);return0;}//substringmain(){charinp;char*T[255];char*S[255];structsstring*s1,*s2,*res;intpos,len;printf("1-------strassing ");printf("2-------strlength ");printf("3-------strcompare ");printf("4-------clearstring ");printf("5-------concat ");printf("6-------substring ");printf("*-------exit!");printf("pleaseinput1--6or* ")while(1){scanf("%c",&inp);switch(inp){case1:{scanf("%s",&S);res->ch=strassign(s1,S);if(res->ch==0)printf("thestringis:%s",s1->ch);elseprintf("error");}case2:{scanf("%s",&S);s1->length=strlen(S);251 strcpy(s1->ch,S);res->ch=strlength(S);printf("thestringis:%d ",s1->length);}case3:{scanf("%s",&S);scanf("%s",&T);s1->length=strlen(S);strcpy(s1->ch,S);s2->length=strlen(T);strcpy(s2->ch,T);res->ch=strcompare(S,T);switch(res){case0:printf("twostringsareequle");case1:printf("thefirststring>thesecondstring");case-1:printf("thefirststringch=clearstring(s1);res->ch=clearstring(s2);printf("thestringisNULL");}case5:{scanf("%s",&S);scanf("%s",&T);strcat(&s1,S,T);if(res==0)printf("thestringis:%s",s1->ch);}case6:{scanf("%s_%d_%d",S,&pos,&len);s2->length=strlen(S);strcpy(s2->ch,S);res->ch=substring(s1,s2,pos,len);if(res==0)printf("thestringis:%s",s1->ch);elseprintf("error");}case*:exit;}}}251 4.二叉树#include#include#includetypedefstructbitnode{chardata;structbitnode*lchild,*rchild;}bitnode,*bitree;voidcreatebitree(t,n)bitnode**t;int*n;{charx;bitnode*q;*n=*n+1;printf(" Input%dDATA:",*n);x=getchar();if(x!=' ')getchar();if(x==' ')return;q=(bitnode*)malloc(sizeof(bitnode));q->data=x;q->lchild=NULL;q->rchild=NULL;*t=q;printf("ThisAddressis:%o,Datais:%c, LeftPointeris:%o,RightPointeris:%o",q,q->data,q->lchild,q->rchild);createbitree(&q->lchild,n);createbitree(&q->rchild,n);return;}voidvisit(e)bitnode*e;{printf("Address:%o,Data:%c,LeftPointer:%o,RightPointer:%o ",e,e->data,e->lchild,e->rchild);}voidpreordertraverse(t)bitnode*t;{251 if(t){visit(t);preordertraverse(t->lchild);preordertraverse(t->rchild);return;}elsereturn;}voidcountleaf(t,c)bitnode*t;int*c;{if(t!=NULL){if(t->lchild==NULL&&t->rchild==NULL){*c=*c+1;}countleaf(t->lchild,c);countleaf(t->rchild,c);}return;}inttreehigh(t)bitnode*t;{intlh,rh,h;if(t==NULL)h=0;else{lh=treehigh(t->lchild);rh=treehigh(t->rchild);h=(lh>rh?lh:rh)+1;}returnh;}main(){bitnode*t;intcount=0;intn=0;printf(" PleaseinputTREEData: ");createbitree(&t,&n);printf(" ThisisTREEStruct: ");preordertraverse(t);251 countleaf(t,&count);printf(" ThisTREEhas%dleaves",count);printf(",HighofTheTREEis:%d ",treehigh(t));}5.二分查找1#include#include#includetypedefstructbitnode{chardata;structbitnode*lchild,*rchild;}bitnode,*bitree;voidcreatep(t)bitnode**t;{charx;bitnode*q;printf(" x=:");x=getchar();if(x!=' ')getchar();q=(bitnode*)malloc(sizeof(bitnode));q->data=x;q->lchild=NULL;q->rchild=NULL;*t=q;if(q->data!='$')printf("%o,%c,%o,%o",q,q->data,q->lchild,q->rchild);return;}voidfind(p,t)bitnode*p,**t;{bitnode*q,*f;if(*t==NULL)*t=p;else{q=*t;f=NULL;while(q!=NULL){if(p->data>q->data){f=q;q=q->rchild;}else{f=q;q=q->lchild;}}251 if(p->data>f->data)f->rchild=p;elsef->lchild=p;}}voidcreatebst(t)char**t;{bitnode*p;while(p->data!='$'){createp(&p);if(p->data=='$')return;find(p,t);}}voidvisit(e)bitnode*e;{printf("%o,%c,%o,%o ",e,e->data,e->lchild,e->rchild);}voidpreordertraverse(t)bitnode*t;{if(t){visit(t);preordertraverse(t->lchild);preordertraverse(t->rchild);return;}elsereturn;}voidsearchbst(t,k)bitnode*t;chark;{if(!t)printf(" cannotfindit ");elseif(k==t->data)printf(" finditis%o%c%o%o ",t,t->data,t->lchild,t->rchild);elseif(kdata)searchbst(t->lchild,k);elsesearchbst(t->rchild,k);}main(){251 bitnode*t=NULL;chark;printf("inputchar;input'$'forend:");createbst(&t);preordertraverse(t);printf(" inputcharforsearchbst:");k=getchar();searchbst(t,k);}6.二分查找2#include"stdio.h"typedefstruct{char*elem;intlength;}sstable;voidcreate(char**t){inti;staticchara[11];*t=a;for(i=1;i<=10;i++){printf("A[%d]is:",i);scanf("%c",&a[i]);if(a[i]!=' ')getchar();}}intsearth(char*t,chark){inti;for(i=10;i>=0&&t[i]!=k;i--);returni;}voidoutput(char*t){inti;for(i=1;i<=10;i++)printf(" A[%d]is%c",i,t[i]);}voidpx(char*t)251 {chars;inti,j;for(i=1;i<=10;i++)for(j=i+1;j<=10;j++){if(t[i]>t[j]){s=t[i];t[i]=t[j];t[j]=s;}}}intsearch_bin(char*t,chark){intlow=1,high=10,mid;while(low<=high){mid=(low+high)/2;if(k==t[mid])returnmid;elseif(k=0)printf("1:usesearchfindisA[%d] ",s);elseprintf("1:cannotfindit ");px(t);output(t);s=search_bin(t,k);if(s==0)printf(" 1:cannotfindit ");elseprintf(" 2:usesearch_binfindisA[%d] ",s);getchar();}251 7.链串#defineNULL0structsstring{char*ch;intlength;}strassign(structsstring*T,char*chars){intnlenth;nlenth=strlen(chars);T->length=nlenth;T->ch=(char*)malloc(nlenth*sizeof(char)+1);if(!T->ch){T->length=0;return;}else{strcpy(T->ch,chars);return;}}intstrlength(structsstring*T){int*S;return(S->length);}intstrcompare(structsstring*S,structsstring*T){if(strcmp(S->ch,T->ch)==0)return0;elseif(strcmp(S->ch,T->ch)>0)return1;elsereturn-1;}intclearstring(structsstring*S){if(S->ch){free(S->ch);S->ch=NULL;S->length=0;}return0;}intconcat(structsstring*T,structsstring*s1,structsstring*s2){if(T->ch)free(T->ch);if(!(T->ch=(char*)malloc((s1->length+s2->length)*sizeof(char))));251 return;T->length=s1->length+s2->length;strcpy(T->ch,s1->ch);strcpy(T->ch,s2->ch);return0;}intsubstring(structsstring*sub,structsstring*S,intpos,intlen){char*p;inti;if(pos<1||pos>S->length||len<0||len>S->length-pos+1)return-1;if(!len){sub->ch=NULL;sub->length=0;}else{sub->ch=(char*)malloc(len*sizeof(char)+1);p=S->ch;for(i=0;i<=pos-1;i++)p++;}strcpy(sub->ch,p);return0;}main(){charinp;char*T,*S,*res;structsstring*s1,*s2;intpos,len;printf("1-------strassing ");printf("2-------strlength ");printf("3-------strcompare ");printf("4-------clearstring ");printf("5-------concat ");printf("6-------substring ");printf("*-------exit");printf("pleaseinput1--6or* ");while(1){scanf("%c",&inp);switch(inp){case1:{scanf("%s",&S);res->ch=strassign(s1,S);251 if(res->ch==0)printf("thestringis%s",s1->ch);elseprintf("error");}case2:{scanf("%s",&S);s1->length=strlen(S);strcpy(s1->ch,S);res->ch=strlength(S);printf("thelengthis%d ",s1->length);}case3:{scanf("%s",&S);scanf("%s",&T);s1->length=strlen(S);strcpy(s1->ch,S);s2->length=strlen(T);strcpy(s2->ch,T);res->ch=strcompare(S,T);switch(res){case0:printf("twostringsareequle");case1:printf("thefirststring>thesecondstring");case-1:printf("thefirststringch=clearstring(s1);res->ch=clearstring(s2);printf("thestringisNULL");}case5:{scanf("%s",&S);scanf("%s",&T);strcat(&s1,S,T);if(res==0)printf("thestringis:%s",s1->ch);}case6:{scanf("%s_%d_%d",S,&pos,&len);s2->length=strlen(S);strcpy(s2->ch,S);res->ch==substring(&s1,&s2,pos,len);if(res==0)printf("thestringis:%s",s1->ch);251 elseprintf("error");}case*:exit;}}}8.链队列#definenull0typedefintstatus;typedefstructqnode{intdata;structqnode*next;}linkqlist;typedefstruct{linkqlist*front;linkqlist*rear;}linkqueue;voidinit(linkqueue*p){p->front=(linkqlist*)malloc(sizeof(linkqlist));p->rear=p->front;(p->front)->next=null;}statusdestory(linkqueue*q){while(q->front){q->rear=q->front->next;free(q->front);q->front=q->rear;}}statusempty(linkqueue*q){intv;if(q->front==q->rear)v=1;elsev=0;returnv;}statusgethead(linkqueue*q){intv;if(q->front==q->rear)v=-1;elsev=(q->front)->next->data;returnv;}statusenqueue(linkqueue*q,inte){q->rear->next=(linkqlist*)malloc(sizeof(linkqlist));q->rear=q->rear->next;251 if(!q->rear)return-1;q->rear->data=e;q->rear->next=null;}statusdequeue(linkqueue*q){linkqlist*p;inte;if(q->front==q->rear)printf("thelinklistisoverflow");elsep=(q->front)->next;(q->front)->next=p->next;e=p->data;if(q->rear==p)q->rear=q->front;free(p);return(e);}voidvisit(linkqueue*p){linkqueue*q;q=p->front->next;printf("displaythelinklist: ");if(p->front==p->rear)printf("thelinklistisempty!");else{while(q){printf("%d->",q->data);q=q->next;}}printf(" ");}main(linkqueue*head){intn,i,y;intselect;inta,x1,x3,x5,e;intdest;printf("createaemptylinkqlist ");init(head);printf("pleaseinputlinkqlistlength: ");scanf("%d",&n);for(i=1;i<=n;i++){printf("pleaseinputlinkqlistvalue ");scanf("%d",&a);enqueue(head,a);}visit(head);printf("select1---destory() ");printf("select2---empty() ");251 printf("select3---gethead() ");printf("select4---enqueue() ");printf("select5---dequeue() ");printf("pleaseselect(1--5):");scanf("%d",&select);switch(select){case1:{destory(head);visit(head);break;}case2:{x1=empty(head);if(x1==1)printf("thelinklistisempty!");printf("thelinklistisfull");break;}case3:{x3=gethead(head);printf("head->front->%d ",x3);break;}case4:{printf("pleaseinsterthevalue:");scanf("%d",&e);enqueue(head,e);visit(head);break;}case5:{x5=dequeue(head);printf("x5",x5);visit(head);break;}}}9.链栈#definenull0typedefstructstacknode{intdata;structstacknode*next;}stacklink;typedefstruct{stacklink*top;intstacksize;}stackk;initlink(stackk*s){s->top=(stacklink*)malloc(sizeof(stacklink));s->top->data=0;s->top->next=null;}intpoplink(stackk*s){stackk*p;intv;if(s->top->next==null)printf("thestackisempty ");else{v=s->top->next->data;251 p=s->top->next;s->top=s->top->next;free(p);returnv;}}intpushlink(stackk*s,intx){stackk*p;p=(stacklink*)malloc(sizeof(stacklink));p->data=x;p->next=s->top->next;s->top->next=p;}intgettop(stackk*s){inte;if(s==null)printf("thestackisempty! ");e=s->top->next->data;returne;}display(stackk*s){stackk*p;p=s->top->next;printf("displaythestacklink: ");if(s->top=null)printf("thestacklinkisempty! ");else{while(p){printf("->%d",p->data);p=p->next;}}}main(stacklink*p){intn,k,i,select,h,x1,x2;printf("createaemptystacklink! ");initlink(p);printf("inputastacklinklength: ");scanf("%d",&n);for(i=1;i<=n;i++){printf("inputastacklinkvalue: ");scanf("%d",&k);pushlink(p,k);}printf("select1:display() ");printf("select2:pushlink() ");printf("select3:poplink() ");printf("select4:gettop() ");251 printf("inputayourselect(1-4): ");scanf("%d",&select);switch(select){case1:{display(p);break;}case2:{printf("inputapushavalue: ");scanf("%d",&h);pushlink(p,h);display(p);break;}case3:{x1=poplink(p);printf("x1->%d ",x1);display(p);break;}case4:{x2=gettop(p);printf("x2->%d",x2);break;}}}10.顺序队列#definemaxsize100typedefstruct{intdata[maxsize];intfront;intrear;}sqqueue;intsqinit(sqqueue*p)/*装入队列*/{p->front=0;p->rear=0;return1;}intenqueue(sqqueue*q,inte)/*入队*/{if((q->rear+1)%maxsize==q->front)return0;elseq->data[q->rear]=e;q->rear=(q->rear+1)%maxsize;return1;}intdequeue(sqqueue*q)/*出队*/{251 inte;if(q->front==q->rear)return0;e=q->data[q->front];q->front=(q->front+1)%maxsize;returne;}intempty(sqqueue*q){intv;if(q->front==q->rear)v=1;elsev=0;returnv;}intgethead(sqqueue*q){inte;if(q->front==q->rear)e=-1;elsee=q->data[q->front];returne;}voiddisplay(sqqueue*q){ints;s=q->front;printf("thesequeueisdisplay: ");if(q->front==q->rear)printf("thesequeueisempty!");else{while(srear){printf("->%d",q->data[s]);s=(s+1)%maxsize;}printf(" ");}}main(sqqueue*head){251 intn,i,m,x,y,select,xq;printf("createaemptysequeue ");sqinit(head);printf("pleaseinputthesequeuelength: ");scanf("%d",&n);for(i=0;irear:%d ",head->rear);printf("head->front:%d ",head->front);display(head);printf("select1****enqueue() ");printf("select2****dequeue() ");printf("select3****empty() ");printf("select4****gethead() ");printf("select5****display() ");printf("pleaseselect(1--5):");scanf("%d",&select);switch(select){case1:{printf("pleaseinputavalue: ");scanf("%d",&x);enqueue(head,x);display(head);break;}case2:{dequeue(head);display(head);break;}case3:{if(empty(head))printf("thesequeueisempty");elseprintf("thesequeueisfull");}case4:251 {y=gethead(head);printf("outputheadvalue:%d ",y);break;}case5:{display(head);break;}}}}11.顺序栈#definem100typedefstruct{intstack[m];inttop;}stackstru;init(stackstru*s)/*装入栈*/{s->top=0;return1;}intpush(stackstru*s,intx)/*入栈操作*/{if(s->top==m)printf("thestackisoverflow! ");else{s->top=s->top+1;s->stack[s->top]=x;}}voiddisplay(stackstru*s)/*显示栈所有数据*/{if(s->top==0)printf("thestackisempty! ");else{251 while(s->top!=0){printf("%d->",s->stack[s->top]);s->top=s->top-1;}}}intpop(stackstru*s)/*出栈操作并返回被删除的那个记录*/{inty;if(s->top==0)printf("thestackisempty! ");else{y=s->stack[s->top];s->top=s->top-1;returny;}}intgettop(stackstru*s)/*得到栈顶数*/{inte;if(s->top==0)return0;elsee=s->stack[s->top];returne;}main(stackstru*p){intn,i,k,h,x1,x2,select;printf("createaemptystack! ");init(p);printf("inputastacklength: ");scanf("%d",&n);for(i=0;i%d ",x1);display(p);break;}case4:{x2=gettop(p);printf("x2->%d",x2);break;}}}12.图#definetrue1#definefalse0#defineok1#defineerror0#defineoverflow-2#definenull0typedefintstatus;251 #include#include#include#definemaxlen10#definelarge999typedefstruct{inta[maxlen],b[maxlen],h[maxlen];/*第K边的起点,终点,权值*/charvexs[maxlen];/*顶点信息集合*/intvexnum,arcnum;/*顶点数和边数*/intkind;/*图的类型*/intarcs[maxlen][maxlen];/*邻接矩阵*/}graph;typedefstructnode/*表结点结构*/{intadjvex;/*存放与头结点相邻接的顶点在数组中的序号*/intinfo;/*权值*/structnode*next;/*指向与头结点相邻接下一个顶点的表结点*/}edgenode;typedefstruct/*头结点结构*/{intid;/*顶点入度*/chardata;/*顶点信息*/edgenode*link;/*指向头结点对应的单链表中的表结点*/}vexnode;typedefstruct/*邻接表结构*/{vexnodeadjs[maxlen];/*邻接表的头结点集合*/intvexnum,arcnum;/*顶点数,边数*/intkind;}adjlist;typedefstructqnode/*队列存储结构*/{intdata;structqnode*next;}linkqlist;typedefstruct{linkqlist*front;/*队头指针*/linkqlist*rear;/*队尾指针*/}linkqueue;typedefstruct/*栈结构*/{intstack[maxlen];inttop;}stackstru;intcnull=-1;251 graphg;adjlistadjl;stackstru*t;/*拓扑序列顶点栈*/stackstru*s;/*零入度顶点栈*/linkqueue*q;graphprintf_adjmatrix(graphg)/*输出邻接矩阵*/{inti,j;printf("邻接矩阵: ");printf("vertext");for(i=0;iadjvex=g.b[i];p->info=g.h[i];p->next=adjl.adjs[g.a[i]-1].link;adjl.adjs[g.a[i]-1].link=p;}251 }if(g.kind==2||g.kind==4){for(i=0;iinfo=g.h[i];p->adjvex=g.b[i];p->next=adjl.adjs[g.a[i]-1].link;adjl.adjs[g.a[i]-1].link=p;p=(edgenode*)malloc(sizeof(edgenode));p->info=g.h[i];p->adjvex=g.a[i];p->next=adjl.adjs[g.b[i]-1].link;adjl.adjs[g.b[i]-1].link=p;}}printf("邻接表为: ");for(i=0;i",i+1,adjl.adjs[i].data);p=adjl.adjs[i].link;while(p!=cnull){printf("[%c,%d]-->",adjl.adjs[(p->adjvex)-1].data,p->info);p=p->next;}printf("^ ");}returnadjl;}voidinitqueue(linkqueue*p){p->front=(linkqlist*)malloc(sizeof(linkqlist));p->rear=p->front;(p->front)->next=null;}statusempty(linkqueue*q){intv;if(q->front==q->rear)v=true;elsev=false;returnv;}statusaddqueue(linkqueue*q,inte)/*入队列*/{q->rear->next=(linkqlist*)malloc(sizeof(linkqlist));q->rear=q->rear->next;if(!q->rear)return-1;q->rear->data=e;251 q->rear->next=null;}statusdelqueue(linkqueue*q)/*出队列*/{linkqlist*p;inte;if(q->front==q->rear)printf("thelinklistisoverflow");elsep=(q->front)->next;(q->front)->next=p->next;e=p->data;if(q->rear==p)q->rear=q->front;free(p);/*释放P所指的内存区*/return(e);}voidDFS(inti,adjlistadjl)/*深度优先搜索*/{edgenode*p;intj;intvisited[maxlen];/*访问标志数组,访问过为1,未访问过为0*/for(j=0;j",adjl.adjs[i-1].data);visited[i-1]=1;p=adjl.adjs[i-1].link;while(p!=cnull){if(visited[(p->adjvex)-1]!=1)DFS((p->adjvex),adjl);p=p->next;}}voidBFS(inti,adjlistadjl)/*广度优先搜索*/{edgenode*p;intj;intvisited[maxlen];for(j=0;j",adjl.adjs[i-1].data);visited[i-1]=1;addqueue(q,i);while(!empty(q)){i=delqueue(q);p=adjl.adjs[i-1].link;while(p!=cnull){if(visited[(p->adjvex)-1]==0){printf("%4c->",adjl.adjs[p->adjvex-1].data);251 visited[(p->adjvex)-1]=1;addqueue(q,p->adjvex);p=p->next;}}}}statusinitstack(stackstru*s)/*构造空栈*/{s->top=0;returnok;}statuspush(stackstru*s,intx)/*入栈*/{if(s->top==maxlen)printf("thestackisoverflow! ");else{s->top=s->top+1;s->stack[s->top]=x;}}statuspop(stackstru*s){inty;if(s->top==0)printf("thestackisempty! ");else{y=s->stack[s->top];s->top=s->top-1;}returny;}statusstackempty(stackstru*s){if(s->top==maxlen)return(true);elsereturn(false);}statustopsort(adjlistadjl)/*拓扑排序*/{inti,k,count;edgenode*p;printf("拓扑排序序列为: ");initstack(s);for(i=0;i",adjl.adjs[i].data);++count;for(p=adjl.adjs[i].link;p;p=p->next)251 {k=p->adjvex;if(!(--adjl.adjs[k-1].id))push(s,k-1);}}if(countnext){k=p->adjvex;if(--adjl.adjs[k-1].id==0)push(s,k-1);if(ve[j]+(p->info)>ve[k-1])ve[k-1]=ve[j]+(p->info);}}if(countnext){k=p->adjvex;dut=(p->info);if(vl[k]-dutnext){k=p->adjvex;dut=p->info;ee=ve[j];el=vl[k-1]-dut;if(ee==el)printf("(%c,%c)->",adjl.adjs[j].data,adjl.adjs[k-1].data);}}voidshortpath_dijkstra(graphg){intcost[maxlen][maxlen];intdist[maxlen];/*某源点到各顶点的最短路径长度*/intpath[maxlen];/*某源点到终点经过的顶点集合的数组*/251 ints[maxlen];/*最短路径的终点集合*/inti,j,n,v0,min,u;/*U存放最短路径的终点*/printf(" 请输入起点的编号:");scanf("%d",&v0);v0--;for(i=0;i0)path[i]=v0;s[i]=0;}s[v0]=1;for(i=0;i(short3[i][k]+short3[k][j])){short3[i][j]=short3[i][k]+short3[k][j];path[i][j]=k;}printf("(%4c->%4c):%d",g.vexs[i-1],g.vexs[j-1],short3[i][j]);}}main(){inta,i,j,k,h;printf(" 请输入图的类型(1:有向图2:无向图3:有向网4:无向网):");scanf("%d",&i);{g.kind=i;adjl.kind=i;}printf("请输入顶点数,边数:");scanf("%d,%d",&i,&j);g.vexnum=i;adjl.vexnum=i;g.arcnum=j;adjl.arcnum=j;for(i=0;ig.vexnum||j<1||j>g.vexnum){printf("编号超出范围,重新输入");gotolabel}if(g.kind==3||g.kind==4){printf("t该边的权值:");scanf("%d",&h);251 g.h[k-1]=h;}elseg.h[k-1]=null;adjl.adjs[i].id++;}loop1:printf(" 1__邻接矩阵 ");printf("2__邻接表 ");printf("3__深度优先搜索 ");printf("4__广度优先搜索 ");printf("5__最小生成树 ");printf("6__拓扑排序 ");printf("7__关键路径 ");printf("8__从某个源点到其余各顶点的最短路径 ");printf("9__每一对顶点之间的最短路径 ");loop:printf("请选择图的实现:t");scanf("%d",&a);switch(a){case1:creategraph(g);break;case2:createlist(g,adjl);break;case3:printf("请输入出发点编号:");scanf("%d",&k);createlist(g,adjl);printf(" 从第%d点出发深度优先搜索遍历序列:",k);DFS(k,adjl);break;case4:printf("请输入出发点编号:");scanf("%d",&k);createlist(g,adjl);printf(" 从第%d点出发广度优先搜索遍历序列:",k);BFS(k,adjl);break;case5:if(g.kind==4){create_4(g);prim(g);}else{printf("t不能构造最小生成树,请重新选择: ");gotoloop;}break;case6:if(g.kind==1||g.kind==3){createlist(g,adjl);topsort(adjl);}else{printf("t不能拓扑排序,请重新选择: ");gotoloop;}break;case7:if(g.kind==3){createlist(g,adjl);criticalpath(adjl);}else{printf("t没有关键路径,请重新选择: ");gotoloop;}251 break;case8:if(g.kind==3){create_3(g);shortpath_dijkstra(g);}else{printf("t没有最短路径,请重新选择: ");gotoloop;}break;case9:if(g.kind==3){create_3(g);shortpath_floyd(g);}else{printf("t没有最短路径,请重新选择: ");gotoloop;}break;default:printf(" t***wrong*** ");}/*switch*/gotoloop1;}/*main()*/251

当前文档最多预览五页，下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页，下载文档查看全文
温馨提示：
1. 部分包含数学公式或PPT动画的文件，查看预览时可能会显示错乱或异常，文件下载后无此问题，请放心下载。
2. 本文档由用户上传，版权归属用户，天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容，确认文档内容符合您的需求后进行下载，若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误，付费完成后未能成功下载的用户请联系客服处理。
最近更新
更多
大家都在看
近期热门

首页

分享

客服

关闭