东北大学842考研

/** 本题有各种答案，无论是学姐的还是红皮书都是错误的。 正确思想在于采用拓扑排序，也是本题考点。深度优先搜索等无法解决。 **/ typedef struct VNode { char data; int no; int count; ArcNode *firstarc; }VNode;//重新定义邻接表表头结点 int TopSort(AGraph *G) { int i,j ,n=0; int stack[maxSize],top=-1;//定义并初始化栈 ArcNode *p; for(i=1;i<G->n;++i) { if(G->adjlist[i].count==0) stack[++top]=i; } while(top!=-1) { i=stack[top--]; ++n;//计数器加1 G->adjlist[i].no=n;//将整形序号赋值给结点 p=G->adjlist[i].firstarc; while(p!=NULL) { j=p->adjvex; --(G->adjlist[j].count); if(G->adjlist[j].count==0) stack[++top]=j; p=p->nextarc; } } if(n==G->n) return 1; else return 0; }

/*三.由键盘输入n(n<50)个英文单词，每个单词由空格分隔。试编写一个递归函数，判断这n个单词是否是按字典顺序排列的。*/ #include<stdio.h>#include<string.h>#define MAXSIZE 50 int WordSort(char word[][15], int n) { if (n < 0) return -1; else if (n == 1) return 1; else { if(strcmp(word[n-1], word[n-2])>0 && WordSort(word, n-1))//下标从0开始最后一个为n-1 return 1; else return 0; } } void main() { char word[MAXSIZE][15]; int size, i; printf("输入单词个数,小于50:\n"); scanf("%d", &size); printf("\n输入%d单词,以空格隔开:\n", size); for (i = 0; i < size; i++) scanf("%s", word[i]); switch (WordSort(word, size)) { case -1: printf("\n请输入单词\n");break; case 0: printf("\n输入的单词不是按字典顺序排序!

http://www.ppkao.com/daan/222163/BD304E420A92B02C21C9193192FE26C3 http://ryanlunar.blog.163.com/blog/static/183577092201241294031508 关于外部变量作用域

//优化版 #include <stdio.h>int main() { FILE *fp; int num, numCur, flag = 0; printf("\nInput a integer: "); scanf("%d", &num); //"r+" 以可读写方式打开文件，该文件必须存在。 //"w" 打开只写文件，若文件存在则文件长度清为0，即该文件内容会消失。若文件不存在则建立该文件。 //"a"为追加写、只写 //"a+"为追加写、可读可写 if ((fp = fopen("a.dat", "a+"))!=NULL) { while (!feof(fp)) { fscanf(fp, "%d", &numCur); if (numCur == num)flag = 1; } if (!flag) { fprintf(fp, " %d", num); //因为要将这个数字写到文件中（相当于计算机input），所以用的是fp1 fclose(fp); } } } /*五.试编写一个程序，从键盘上输入一个整数，在整数文件"a.dat"中查找，要求： 1.若文件"a.dat"不存在，则建立一个新文件"a.dat"，将该整数写入文件； 2.若文件中找到了这个整数，则显示数据存在，否则将该数据写入文件。*/ #include <stdio.h>int main() { FILE *fp1, *fp2; int num, numCur, flag = 0; printf("\nInput a integer: "); scanf("%d", &num); //“r+” 以可读写方式打开文件，该文件必须存在。 //“w” 打开只写文件，若文件存在则文件长度清为0，即该文件内容会消失。若文件不存在则建立该文件。 if ((fp1 = fopen("a.

链表的创建、输出等 原文链接 void Delete(LNode *La, LNode *Lb, LNode *Lc) //删除链表A中既存在B又存在C中的元素 { LNode *pa, *pb, *pc, *q; pa = La; pb = Lb->next; pc = Lc->next; while (pb && pc) //思路：在链表B和C中查找相同的元素看看此元素是否在A链表中 { if (pb->data < pc->data) pb = pb->next; else if (pc->data < pb->data) pc = pc->next; else //找到lb和lc中都出现的结点 { while (pa->next) { if (pa->next->data < pb->data) pa = pa->next; else if (pa->next->data > pb->data) { //pa = pa->next;//此处注释，原因，添加此句会有漏解情况 pb = pb->next; pc = pc->next; break; } else //删除la中也包含的该元素 { q = pa->next; pa->next = q->next; free(q); pa = pa->next; pb = pb->next; pc = pc->next; break; } } } } }

//分别求出一个结点的左右孩子结点的高度做差即为平衡因子 int depth(BTNode *bt) { int r,l; if(bt==NULL) return 0; else { l=depth(bt->lchild); r=depth(bt->rchild); return (l>r?l:r)+1; } } int balance(BTNode *T,int n)//n初始传入值为0 { int l,r; if(T!=NULL) { balance(T->lchild,n); balance(T->rchild,n); l=depth(T->lchild); r=depth(T->rchild); if(l+r>0) ++n;//记录非叶子结点个数 printf("%d",l-r);//打印平衡因子 } return n; }

#include<stdio.h>#define maxSize 100 void Palindrome(LNode *h,int n) { char stack[maxSize],top=-1;//定义栈 char queue[maxSize],front=0,rear=0;//定义队列 char a,b; int i,count=0; LNode *p=h; for(i=0;i<n;i++)//前n个字母分别入栈入队 { stack[++top]=p->data; queue[rear++]=p->data; p=p->next; } for(i=0;i<n;i++) { a=stack[top--];//出栈 b=queue[front++];//出队 if(a!=b) break; else count++; } if(count!=n) printf("非回文\n"); else printf("回文\n"); }

前辈答案 http://blog.csdn.net/zl19890124 #include <stdio.h> #define MAX_NM 10 #define MAX_POSTAGE 1024 #define INF 2147483647 int n, m; int x[MAX_NM], ans[MAX_NM], y[MAX_POSTAGE], maxStamp, r; /* * backtrack(i)表示x[0...i-1]这i张邮票已经完全确定， * 相应于x[0...i-1]的最大连续邮资区间r和每种邮资所需要的 * 最少邮票张数y[0...r]也都确定，现在枚举x[i] * 的每个值，确定x[i] */ void backtrack(int i) { int *backup_y, backup_r; int next, postage, num, tmp; if(i >= n) { if(r > maxStamp) { maxStamp = r; for(tmp = 0; tmp < n; tmp++) ans[tmp] = x[tmp]; } return; } backup_y = (int*)malloc(MAX_POSTAGE * sizeof(int)); for(tmp = 0; tmp < MAX_POSTAGE; tmp++) backup_y[tmp] = y[tmp]; backup_r = r; for(next = x[i - 1] + 1; next <= r + 1; next++) { /* update x[i] */ x[i] = next; /* update y */ for(postage = 0; postage < x[i-1] * m; postage++) { if(y[postage] >= m) continue; for(num = 1; num <= m - y[postage]; num++) if(y[postage] + num < y[postage + num * next] && (postage + num * next < MAX_POSTAGE)) y[postage + num * next] = y[postage] + num; } /* update r */ while(y[r + 1] < INF) r++; backtrack(i + 1); /* restore */ r = backup_r; for(tmp = 0; tmp < MAX_POSTAGE; tmp++) y[tmp] = backup_y[tmp]; } free(backup_y); } int main() { int i; scanf("%d%d", &n, &m); x[0] = 1; r = m; for(i = 0; i <= r; i++) y[i] = i; while(i < MAX_POSTAGE) y[i++] = INF; maxStamp = 0; backtrack(1); printf("max stamp is: %d/n", maxStamp); for(i = 0; i < n; i++) printf("%4d", ans[i]); return 0; }

原文链接 http://blog.csdn.net/jcwKyl/article/details/4137398 #include <stdio.h> #define MAX_NM 10 #define MAX_POSTAGE 1024 #define INF 2147483647 int n, m; int x[MAX_NM], ans[MAX_NM], y[MAX_POSTAGE], maxStamp, r; /* * backtrack(i)表示x[0...i-1]这i张邮票已经完全确定， * 相应于x[0...i-1]的最大连续邮资区间r和每种邮资所需要的 * 最少邮票张数y[0...r]也都确定，现在枚举x[i] * 的每个值，确定x[i] */ void backtrack(int i) { int *backup_y, backup_r; int next, postage, num, tmp; if(i >= n) { if(r > maxStamp) { maxStamp = r; for(tmp = 0; tmp < n; tmp++) ans[tmp] = x[tmp]; } return; } backup_y = (int*)malloc(MAX_POSTAGE * sizeof(int)); for(tmp = 0; tmp < MAX_POSTAGE; tmp++) backup_y[tmp] = y[tmp]; backup_r = r; for(next = x[i - 1] + 1; next <= r + 1; next++) { /* update x[i] */ x[i] = next; /* update y */ for(postage = 0; postage < x[i-1] * m; postage++) { if(y[postage] >= m) continue; for(num = 1; num <= m - y[postage]; num++) if(y[postage] + num < y[postage + num * next] && (postage + num * next < MAX_POSTAGE)) y[postage + num * next] = y[postage] + num; } /* update r */ while(y[r + 1] < INF) r++; backtrack(i + 1); /* restore */ r = backup_r; for(tmp = 0; tmp < MAX_POSTAGE; tmp++) y[tmp] = backup_y[tmp]; } free(backup_y); } int main() { int i; scanf("%d%d", &n, &m); x[0] = 1; r = m; for(i = 0; i <= r; i++) y[i] = i; while(i < MAX_POSTAGE) y[i++] = INF; maxStamp = 0; backtrack(1); printf("max stamp is: %d/n", maxStamp); for(i = 0; i < n; i++) printf("%4d", ans[i]); return 0; }

#include<stdio.h>int main() { int i,temp,reversedNum; for(i=1993; i>0; --i) { temp=i; reversedNum=0; while(temp)//除2取余倒排的逆运算！！！ { reversedNum=reversedNum*2+temp%2; temp/=2; } if(i==reversedNum) { printf("%d",i); break; } } return 0; }