某大公司的两道笔试题，大家一块来做一下
1.一群人围成一圈，123的报数，报3者出列，求最后一个人。
2.利用链表实现将两个有序队列A和B合并到有序队列H中，不准增加其他空间。
请提供全一点的程序，谢谢
[解决办法]
第一题：
// kickout.cpp : Defines the entry point for the console application.
//
#include "stdafx.h "
#include "malloc.h "
#include "stdio.h "
int main()
{
int m,n;
int kickouts = 0;
int *p = NULL;
int i ,j;
i=j=0;
printf( "Please input m,n: ");
scanf( "%d,%d ",&m,&n);
while(n <1)
{
printf( "n doen 't less 0 , retry n: ");
scanf( "%d ",&n);
}
p=(int*)malloc(m*sizeof(int));
for(i=0;i <m;i++)
p[i]=1;
i = 0;
while(1)
{
i = i%m;
if(p[i++]) j++;
if(j == n)
{
p[i-1]=0;
j = 0;
kickouts++;
}
if(kickouts == m-1)
break;
}
for(i = 0;i <m;i++)
if(p[i]) printf( "%d\n ",i+1);
return 0;
}
[解决办法]
#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
int data;
struct node *next;
}LNode;
main()
{
LNode* Create(int,int);
LNode* GetNode(LNode *);
int Print(LNode *,int);
LNode *p;
int n,k,m;
do
{
printf ( "输入总人数 ");
scanf ( "%d ",&n);
}
while (n <=0);
do
{
printf ( "输入开始人的序号(1~%d) ",n);
scanf ( "%d ",&k);
}
while (k <=0 || k> n);
do
{
printf ( "输入间隔数字 ");
scanf ( "%d ",&m);
}
while(m <=0);
p=Create(n,k);
Print(p,m);
return 0;
}
LNode* Create(int n,int k)
{
int start=k-1;
LNode *s,*p,*L=0,*t;
if (start==0) start=n;
while (n!=0)
{
s=(LNode *)malloc(sizeof(LNode));
if (L==0) p=s;
if (n==start) t=s;
s-> data=n;
s-> next=L;
L=s;
n--;
}
p-> next=L;
return t;
}
LNode* GetNode(LNode *p)
{
LNode *q;
for (q=p;q-> next!=p;q=q-> next);
q-> next=p-> next;
free (p);
return (q);
}
Print(LNode *p,int m)
{
int i;
printf ( "出队编号:\n ");
while (p-> next!=p)
{
for (i=1;i <=m;i++)
p=p-> next;
printf ( "%d ",p-> data);
p=GetNode(p);
}
printf( "%d\n ",p-> data);
return 0;
}
[解决办法]
1、搜索约瑟夫环
2、升序还是降序？
以升序为例：
while(a != NULL && b!= NULL)
{
if (a-> data < b-> data)
{
h-> data = a-> data;
a = a-> next;
}
else if (a-> data == b-> data)
{
h-> data = a-> data;
a = a-> next;
b = b-> next;
}
else
{
h-> data = b-> data;
b = b-> next
}
h = h-> next;
}
if (a == NULL)
{
while (b != NULL)
{
h-> data = b-> data;
h = h-> next;
b = b-> next;
}
}
else
{
while(a != NULL)
{
h-> data = a-> next;
h = h-> next;
a = a-> next;
}
}
[解决办法]
第一个问题：
#include <iostream> //几个人的围圈问题，数到3的退出圈子
using namespace std;
class Link;
typedef struct node
{
int data;
node *next;
} node,*Sqlist;
int main()
{
Sqlist h=(Sqlist)malloc(sizeof(node)); //用一个无头指针的循环链表实现
cin> > h-> data; //先读入第一个节点
Sqlist q=h,p;
int n,now=1;
cin> > n;
for(int i=1;i <n;i++) //加上第一个节点，一共是n个
{
Sqlist p=(Sqlist)malloc(sizeof(node));
cin> > p-> data;
q-> next=p;
q=p;
}
q-> next=h; //最后一个指向第一个，成为环
p=q=h;
while(q-> next!=q)
{
if(now==3)
{
cout < <p-> data < <endl;
q-> next=p-> next;
free(p);
p=q-> next; //删掉一个点之后，后面的点补上，而不要往下移指针
now=1; //这个补上的点就是第一个点了
continue;
}
q=p;
p=p-> next;
now++;
}
cout < <q-> data < <endl; //还留下的那一个点
return 0;
}
[解决办法]
第二题，我这是一个链表的合并，其实队列也一样，我懒得改了，楼主随便看一下吧
SqList Merge(SqList H,SqList L) //合并，
{
SqList p1,q1,p2,q2;
Seq(H); //先让两个表有序，
Seq(L);
p1=H;
q1=p1-> next;
p2=L;
q2=p2-> next;
int n=H-> size;
while(q1!=NULL && q2!=NULL) //用一个链表的空间做，
{
if(q1-> data < q2-> data) //如果一表小，则一表指针q1后移
{
p1=q1;
q1=q1-> next;
}
else //若一表相等或大于二表，则二表前插，二表指针q2后移，一表不动
{
p1-> next=q2;
q2=q2-> next;
(p1-> next)-> next=q1;
p1=p1-> next;
H-> size++; //长度增加
}
}
if(q1==NULL) //若一表先移至NULL处，说明二表还有一大堆数据
{
p1-> next=q2; //直接将二表连到一表的后面，
q1=q2;
while(q1!=NULL)
{
q1=q1-> next; //将指针移到合并后的表的表尾，为了计算还有多
//少个二表的数据
H-> size++; //同时根据二表的剩余数据个数，增加表长
}
}
return H;
}
[解决办法]
#include <stdio.h>
#include <conio.h>
int main( void )
{
int n, i = 0, m, p;
scanf( "%d%d ", &n, &m); //n总人数，m步长
while( ++i <= n )
{
p = i * m;
while (p > n)
p = p - n + (p - n - 1)/(m - 1);
printf( "%d\n ", p);
}
getch();return 0;
}
[解决办法]
刚看完数据结构阿 第二题好像是书上的例题
linklist mergelinklist(linklist A,linklist B)
{
Node *La,*Lb;
linklist H;
La=A-> next;
Lb=B-> next;
H=La;
H-> next=NULL;
r=h;
while(La!=NULL&&Lb!=NULL)
{
if(La-> data <=Lb-> data)
{
r-> next=La;r=La;La=La-> next;
}
else
{
r-> next=Lb;r=Lb;Lb=Lb-> next;
}
}
if(La)
r-> next=La;
else
r-> next=Lb;
free(B);
return(H);
}
[解决办法]
摆脱不要说简单.
要知道在那个环境下,用手写, 还是比较麻烦的. 我敢说100个人里面90个都写不出很好的,一点没错的代码来,
[解决办法]
哈哈，是吗？看着是很简单嘛，就是你知道怎么做了为什么还问啊。呵呵
[解决办法]
1` 著名的约瑟夫环问题. 单向循环链表轻松搞定.
2` 建立一个循环:
两个指针curA, curB , 分别指向A,B链表头;
比较两指针指向值大小, 小的插入到H, 并移动该指针cur = cur-> next;
直到curA = NULL, curB = NULL.
[解决办法]
第1题：
原题：
用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。（约瑟夫环问题 Josephus）
提示：
由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。
为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。
代码：
/********************************************************************
created: 2006/06/14
filename: C:\Documents and Settings\Administrator\桌面\tmpp\josephus.c
file path: C:\Documents and Settings\Administrator\桌面\tmpp
file base: josephus
file ext: c
author: A.TNG
version: 0.0.1
purpose: 实现 Josephus 环问题
用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，
直至全部输出。写出C程序。（约瑟夫环问题 Josephus）
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
/* 结构体和函数声明 */
typedef struct _node_t
{
int n_num;
struct _node_t *next;
} node_t;
node_t *node_t_create(int n);
node_t *node_t_get(node_t **pn, int m);
/* 功能函数实现 */
/*
* name: node_t_create
* params:
* n [in] 输入要构造的链表的个数
* return:
* 返回构造成功的环形单向链表指针
* notes:
* 构造节点数量为 n 的环形单向链表
*
* author: A.TNG 2006/06/14 17:56
*/
node_t * node_t_create(int n)
{
node_t *p_ret = NULL;
if (0 != n)
{
int n_idx = 1;
node_t *p_node = NULL;
/* 构造 n 个 node_t */
p_node = (node_t *) malloc(n * sizeof(node_t));
if (NULL == p_node)
return NULL;
else
memset(p_node, 0, n * sizeof(node_t));
/* 内存空间申请成功 */
p_ret = p_node;
for (; n_idx < n; n_idx++)
{
p_node-> n_num = n_idx;
p_node-> next = p_node + 1;
p_node = p_node-> next;
}
p_node-> n_num = n;
p_node-> next = p_ret;
}
return p_ret;
}
/*
* name: main
* params:
* none
* return:
* int
* notes:
* main function
*
* author: A.TNG 2006/06/14 18:11
*/
int main()
{
int n, m;
node_t *p_list, *p_iter;
n = 20; m = 6;
/* 构造环形单向链表 */
p_list = node_t_create(n);
/* Josephus 循环取数 */
p_iter = p_list;
m %= n;
while (p_iter != p_iter-> next)
{
int i = 1;
/* 取到第 m-1 个节点 */
for (; i < m - 1; i++)
{
p_iter = p_iter-> next;
}
/* 输出第 m 个节点的值 */
printf( "%d\n ", p_iter-> next-> n_num);
/* 从链表中删除第 m 个节点 */
p_iter-> next = p_iter-> next-> next;
p_iter = p_iter-> next;
}
printf( "%d\n ", p_iter-> n_num);
/* 释放申请的空间 */
free(p_list);
system( "PAUSE ");
}
第2题：
linklist mergelinklist(linklist A,linklist B)
{
Node *La,*Lb;
linklist H;
La=A-> next;
Lb=B-> next;
H=La;
H-> next=NULL;
r=h;
while(La!=NULL&&Lb!=NULL)
{
if(La-> data <=Lb-> data)
{
r-> next=La;r=La;La=La-> next;
}
else
{
r-> next=Lb;r=Lb;Lb=Lb-> next;
}
}
if(La)
r-> next=La;
else
r-> next=Lb;
free(B);
return(H);
}
[解决办法]
第一题用链表理解简单，效率似乎偏低
[解决办法]
这是基础题！LZ要努力呀。
[解决办法]
要真是笔试题目的话就很难做了，
你得考虑安全性，健壮性，风格，效率等问题
朴素的实现是用不到实际中的
[解决办法]
mark
