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->data>qa->data){
ra->next=qa;
qa=qa->next;
}
else{
ra->next=pa;
pa=pa->next;
}
}
if(pa->next!=NULL)
二叉树中序遍历非递归算法
ra->next=pa;
if(qa->next!=NULL)
ra->next==qa;
returnR;
}2.单连表的建立，把'a'--'z'26个字母插入到连表中，还要打印！
node*p=NULL;node*head=(node*)malloc(sizeof(node));head->next=NULL;p=head;intlongth='a'-'z';inti;while(i<=longth){node*temp;temp=(node*)malloc(sizeof(node));temp->data=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。
提示：程序运行后首先要求用户指定初始报数上限。然后读取各人的密码。设n<30******算法思想：利用循环链表*******
******问题的规模是n个人，每次杀掉第m
******个人,n和m由用户输入,程序输出最后
******一个活着的人的编号*************/
#include<iostream>
usingnamespacestd;
/*****约瑟夫问题的节点*******/
typedefstructnode
{
intnumber;
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(i<=n)
{
yuesefu_node*q=newyuesefu_node;//新增一个约瑟夫节点
q->number=i;
if(i==n)
{
q->next=head;
}
else
{
q->next=NULL;
}
p->next=q;
p=q;
i++;
}
returnhead;
}
voidout_chink(yuesefu_node*head)
{
yuesefu_node*p=head;
while(p->next!=head)
{
cout<<p->number<<"";
p=p->next;
}
cout<<p->number<<endl;
}
voidkill_out(yuesefu_node*head,intn,intm)
{
if(n<m)
{
cout<<"************************"<<endl;
cout<<"最后活着的人的编号为:";
out_chink(head);
return;
}
yuesefu_node*p=head;
intcount=1;
while(count<m-1)
{
p=p->next;
count++;
}
yuesefu_node*p_pre=p;//记住要删除节点的前一个指针
p=p->next;
cout<<"本次杀掉的人的编号为："<<p->number<<endl;
p_pre->next=p->next;
delete(p);
head=p_pre->next;//指定刚被杀的人的下一个人为下一轮的第一个
cout<<"本轮后活着的人的编号为:";
out_chink(head);
kill_out(head,n-1,m);
}
voidmain()
{
intn,m;
cout<<"pleaseinputn和m:"<<endl;
cin>>n>>m;
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)
{cout<<p->data<<"";
preorder(p->lchild);
preorder(p->rchild);}
}2．非递归遍历利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：
从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。
算法如下：
voidpreorder1(bitree*root)
{bitree*p,*s[100];
inttop=0;//top为栈顶指针
p=root;
while((p!=NULL)||(top>0))
{while(p!=NULL)
{cout<<p->data<<"";
s[++top]=p;p=p->lchild;}
p=s[top--];p=p->rchild;
}
}
中根遍历所谓中根遍历，就是根在中间，先左子树，然后根结点，最后右子树。1．递归遍历
中根遍历二叉树的递归遍历算法描述为：
若二叉树为空，则算法结束；
否则
⑴中根遍历左子树;
⑵输出根结点;
⑶中根遍历右子树。
算法如下:
voidinorder(biteee*root)
{bitree*p;
p=root;
if(p!=NULL)
{inorder(p->lchild);
cout<<p->data<<"";
inorder(p->rchild);
}
}2．非递归遍历同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：
从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。
算法如下:
voidinorder1(bitree*root)
{bitree*p,*s[100];//s为一个栈
inttop=0;
p=root;
while((p!=NULL)||(top>0))
{while(p!=NULL)
{s[++top]=p;p=p->lchild;}
p=s[top--];
cout<<p->data<<"";
p=p->rchild;
}
}
后根遍历所谓后根遍历，就是根在最后，即先左子树，然后右子树，最后根结点。1．递归遍历
后根遍历二叉树的递归遍历算法描述为：
若二叉树为空，则算法结束;
否则
（1）后根遍历左子树:
（2）后根遍历历子树;
（3）访问根结点。
算法如下:
voidpostorder(bitree*root)
{bitree*p;
p=root;
if(p!=NULL)
{postorder(p->lchild);
postorder(p->rchild);
cout<<p->data<<"";
}
}
2．非递归遍历利用栈来实现二叉树的后序遍历要比前序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树,所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，
第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。
算法如下：
voidpostorder1(bitree*root)
{bitree*p,*s1[100];
ints2[100],top=0,b;p=root;
//s1栈存放结点,s2栈存放进栈标志
do{while(p!=NULL)
{s1[top]=p;s2[top++]=0;
//第一次进栈标志为0
p=p->lchild;}
if(top>0)
{b=s2[--top];p=s1[top];
if(b==0)
{s1[top]=p;s2[top++]=1;
//第二次进栈标志为1
p=p->rchild;}
else{cout<<p->data;p=NULL;}}
}while(top>0);}
另外，在编译原理中，有用二叉树来表示一个算术表达式的情形。在一棵二叉树中，若用操作数代表树叶，运算符代表非叶子结点，则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历，则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图6-12。图6-12所对应的前缀表达式：-*abc。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。