c语言编程题目大全.docx

c语言编程题目大全1、线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表答案在请化大学严锐敏数据结构第二版第二章例题，数据结构当中，这个叫做：两路归并排序Linklist*unio(Linklist*p,Linklist*q)linklist*R,*pa,*qa,*ra;pa=p;qa=q;R=ra=p;while(pa-next!=NULL&qa-next!=NULL)if(pa-dataqa-data)ra-next=qa;qa=qa-next;elsera-next=pa;pa=pa-next;if(pa-next!=NULL)ra-next=pa;if(qa-next!=NULL)ra-next=qa;returnR;2.单连表的建立，把a-z26个字母插入到连表中，还要打印！node*p=NULL;node*head=(node*)malloc(sizeof(node);head-next=NULL;p=head;intlongth=a-z;inti;while(idata=i+a;temp-next=NULL;p=temp;p-next=p;i+;returnhead;print(head);3、约瑟夫环：约瑟夫环问题的一种描述是：编号为1.2.3.n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数），开始任意选一个整数作为报数上限值，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺时针下一个人开始重新从1开始报数，如此下去直到所有的人全部都出列为止。试设计程序实现。要求：利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号。测试数据：m的值初始为20：密码3，1，7，2，4，8，4。正确的结果：6，1，4，7，2，3，5。提示：程序运行后首先要求用户指定初始报数上限。然后读取各人的密码。设n30*算法思想：利用循环链表*问题的规模是n个人，每次杀掉第m*个人,n和m由用户输入,程序输出最后*一个活着的人的编号*/#includeusingnamespacestd;/*约瑟夫问题的节点*/typedefstructnodeintnumber;node*next;yuesefu_node;/*建立n个人的循环链表*/yuesefu_node*create_chink(intn)yuesefu_node*head;/头指针yuesefu_node*p=newyuesefu_node;/p是第一个约瑟夫节点head=p;p-number=1;p-next=NULL;inti=2;while(inumber=i;if(i=n)q-next=head;elseq-next=NULL;p-next=q;p=q;i+;returnhead;voidout_chink(yuesefu_node*head)yuesefu_node*p=head;while(p-next!=head)coutnumbernext;coutnumberendl;voidkill_out(yuesefu_node*head,intn,intm)if(nm)cout*endl;cout最后活着的人的编号为:;out_chink(head);return;yuesefu_node*p=head;intcount=1;while(countnext;count+;yuesefu_node*p_pre=p;/记住要删除节点的前一个指针p=p-next;cout本次杀掉的人的编号为：numbernext=p-next;delete(p);head=p_pre-next;/指定刚被杀的人的下一个人为下一轮的第一个cout本轮后活着的人的编号为:;out_chink(head);kill_out(head,n-1,m);voidmain()intn,m;coutpleaseinputn和m:nm;yuesefu_node*head=create_chink(n);kill_out(head,n,m);4、二叉树的遍历及实现所谓前根遍历，就是根结点最先遍历，其次左子树，最后右子树。1递归遍历前根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）输出根结点；（2）前根遍历左子树;（3）前根遍历右子树;算法如下:voidpreorder(bitree*root)bitree*p;p=root;if(p!=NULL)coutdatalchild);preorder(p-rchild);2非递归遍历利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。算法如下：voidpreorder1(bitree*root)bitree*p,*s100;inttop=0;/top为栈顶指针p=root;while(p!=NULL)|(top0)while(p!=NULL)coutdatalchild;p=stop-;p=p-rchild;中根遍历所谓中根遍历，就是根在中间，先左子树，然后根结点，最后右子树。1递归遍历中根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束；否则中根遍历左子树;输出根结点;中根遍历右子树。算法如下:voidinorder(biteee*root)bitree*p;p=root;if(p!=NULL)inorder(p-lchild);coutdatarchild);2非递归遍历同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。算法如下:voidinorder1(bitree*root)bitree*p,*s100;/s为一个栈inttop=0;p=root;while(p!=NULL)|(top0)while(p!=NULL)s+top=p;p=p-lchild;p=stop-;coutdatarchild;后根遍历所谓后根遍历，就是根在最后，即先左子树，然后右子树，最后根结点。1递归遍历后根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）后根遍历左子树:（2）后根遍历历子树;（3）访问根结点。算法如下:voidpostorder(bitree*root)bitree*p;p=root;if(p!=NULL)postorder(p-lchild);postorder(p-rchild);coutdatalchild;if(top0)b=s2-top;p=s1top;if(b=0)s1top=p;s2top+=1;/第二次进栈标志为1p=p-rchild;elsecoutdata;p=NULL;while(top0);另外，在编译原理中，有用二叉树来表示一个算术表达式的情形。在一棵二叉树中，若用操作数代表树叶，运算符代表非叶子结点，则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历，则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图6-12。图6-12所对应的前缀表达式：-*abc。图6-12所对应的中缀表达式：a*b-c。图6-12所对应的后缀表达式：ab*c-。二叉树所对应的遍历序列可以通过递归算法得到，也可以通过非递归算法得到。但有时要求直接写出序列，故我们可以用右图表示图6-12的遍历序列。从二叉树的三种递归遍历算法可以知道，三种遍历算法不同之处在于访问根结点和遍历左、右子树的顺序不同，若递归算法中去掉与递归无关的语句-访问根结点，则三个遍历算法完全相同。于是对于二叉树的遍历，可以看成是从根结点出发，往左子树走，若左子树为空，返回，再进入右子树，右子树访问完后，再返回根结点。这样一来每个结点都被访问三次，若将按顺序第一次访问的结