一、如何判斷一個單鏈表是有環(huán)的？（注意不能用標(biāo)志位，最多只能用兩個額外指針）
struct node { char val; node* next;}
bool check(const node* head) {} //return false : 無環(huán)；true: 有環(huán)
一種O（n）的辦法就是（搞兩個指針，一個每次遞增一步，一個每次遞增兩步，如果有環(huán)的話兩者必然重合，反之亦然）：
bool check(const node* head)
{
if(head==NULL)
return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast)
return true;
}
return false;
}
二、刪除一個單項鏈表的最中間的元素，要求時間盡可能短（不能使用兩次循環(huán)）
struct link
{
int data;
struct link *next;
};
void delMiddle(link *head)
{
if(head == NULL)
return;
else if(head->next == NULL)
{
delete head;
return;
}
else
{
link *low = head;
link *fast = head->next;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
if(fast == NULL)
break;
low = low->next;
}
link *temp = low->next;
low->next = low->next->next;
delete temp;
}
}
int main()
{
struct link *head,*l;
struct link *s;
head = (link*)malloc(sizeof(link));
head->data=0;
head->next = NULL;
l = head;
for(int i=1; i<9; i++)
{
s = (link*)malloc(sizeof(link));
s->data = i;
s->next = NULL;
l->next= s;
l = l->next;
}
print(head);
delMiddle(head);
print(head);
return 0;
}
三、輸入n，求一個n*n矩陣，規(guī)定矩陣沿45度線遞增(威盛)
/**
* 得到如下樣式的二維數(shù)組
* zigzag（jpeg編碼里取象素數(shù)據(jù)的排列順序）
*
* 0, 1, 5, 6,14,15,27,28,
* 2, 4, 7,13,16,26,29,42,
* 3, 8,12,17,25,30,41,43,
* 9,11,18,24,31,40,44,53,
* 10,19,23,32,39,45,52,54,
* 20,22,33,38,46,51,55,60,
* 21,34,37,47,50,56,59,61,
* 35,36,48,49,57,58,62,63
*/
void zigzag(int n)
{
int **a =(int**) malloc(n*sizeof(int *)); //分配空間
if(NULL == a)
return ;
int i;
for(i = 0; i < n; i++) {
if((a[i] =(int*) malloc(n * sizeof(int))) == NULL) {
while(--i>=0)
free(a[i]);
free(a);
return;
}
}
bool flag = false; //這個標(biāo)志位用來判斷是從45度角生成還是225度角生成
int count = 0;
for(i=0; i<n; i++) //生成的上半部分的數(shù)據(jù)
{
if(flag)
{
for(int r = 0; r<=i; r++)
{
a[r][i-r] = count;
count++;
}
flag = false;
}
else
{
for(int r = i; r>=0; r--)
{
a[r][i-r] = count;
count++;
}
flag = true;
}
}
for(i=n-1; i>=0; i--) //生成的是下半部分的數(shù)據(jù)
{
// cout<<i<<endl;
if(flag)
{
for(int r = 0; r<=i-1; r++)
{
int r1 = n-i+r; //代表當(dāng)前行
int c1 = 2*n-i-1-r1; //代表當(dāng)前列
a[r1][c1] = count;
count++;
}
flag = false;
}
else
{
for(int r = i-1; r>=0; r--)
{
cout<<"ddd"<<endl;
int r1 = n-i+r;
int c1 = 2*n-i-1-r1;
// cout<<r1<<","<<c1<<endl;
a[r1][c1] = count;
count++;
}
flag = true;
}
}
for(int r = 0; r<n; r++)
{
for(int c=0; c<n; c++)
cout<<a[r][c]<<",";
cout<<endl;
}
}
int main()
{
int n;
cin>>n;
zigzag(n);
return 0;
}
網(wǎng)上還有一個人寫了一個比較巧的算法：
/**
* 得到如下樣式的二維數(shù)組
* zigzag（jpeg編碼里取象素數(shù)據(jù)的排列順序）
*
* 0, 1, 5, 6,14,15,27,28,
* 2, 4, 7,13,16,26,29,42,
* 3, 8,12,17,25,30,41,43,
* 9,11,18,24,31,40,44,53,
* 10,19,23,32,39,45,52,54,
* 20,22,33,38,46,51,55,60,
* 21,34,37,47,50,56,59,61,
* 35,36,48,49,57,58,62,63
*/
#include <stdio.h>
int main()
{
int N;
int s, i, j;
int squa;
scanf("%d", &N);
/* 分配空間 */
int **a = malloc(N * sizeof(int *));
if(a == NULL)
return 0;
for(i = 0; i < N; i++) {
if((a[i] = malloc(N * sizeof(int))) == NULL) {
while(--i>=0)
free(a[i]);
free(a);
return 0;
}
}
/* 數(shù)組賦值 */
squa = N*N;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++) {
s = i + j;
if(s < N)
a[i][j] = s*(s+1)/2 + (((i+j)%2 == 0)? i : j);
else {
s = (N-1-i) + (N-1-j);
a[i][j] = squa - s*(s+1)/2 - (N - (((i+j)%2 == 0)? i : j));
}
}
/* 打印輸出 */
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++)
printf("%-6d", a[i][j]);
printf("\n");
}
return 0;
}
四、打印1到1000的整數(shù)，不能使用流程控制語句(for,while,goto等)也不能使用遞歸
1.
typedef struct _test{
static int a;
_test(){
printf("%d\n",_test::a);
a++;
}
}Test;
int Test::a = 1;
int main()
{
Test tt[1000];
return 0;
}
2.
#include <stdio.h>
#define B P,P,P,P,P,P,P,P,P,P
#define P L,L,L,L,L,L,L,L,L,L
#define L I,I,I,I,I,I,I,I,I,I,N
#define I printf( "%3d ",i++)
#define N printf( "\n ")
int main()
{
int i = 1;
B;
}
或
#define A(x) x;x;x;x;x;x;x;x;x;x;
int main ()
{
int n = 1;
A(A(A(printf ("%d ", n++))));
return 0;
}
五、struct S {
int i;
int * p;
};
void main()
{
S s;
int * p = &s.i;
p[0] = 4;
p[1] = 3;
s.p = p;
s.p[1] = 1;
s.p[0] = 2;
}
問程序會在哪一行死掉。 （microsoft）
解： S s;
int * p = &s.i; //s.i的地址存儲在p里
p[0] = 4; //修改了s.i
p[1] = 3; //修改了s.p
s.p = p; //s.p指向s.i
s.p[1] = 1; //修改s.p本身
s.p[0] = 2; //s.p指向的是0x00000001,嘗試向這里寫,出錯
s.p[0] = 2; 時出錯
因為s.p存的是s.i的地址,s.p[1]為s.p,當(dāng)s.p[1]=1時,s.p此時存放的是1了,而不是地址s.i,故在s.p[0] = 2時出錯.
此時相當(dāng)于s.p=ox00000001;地址ox0000001 = 2;當(dāng)然就出錯了
如果語句s.p[0] =2 先于s.p[1]=1則程序就不會出錯.此時語句相當(dāng)于s.i=2;s.p=1;
六、題目描述：
1. int swap(int *x,int *y)
{
if(x==NULL ¦ ¦ y==NULL)
return -1;
*x += *y;
*y = *x- *y;
*x -= *y;
return 1;
}
請改錯，溢出已經(jīng)考慮，不是錯誤
2.
void foo(int *x, int *y)
{
*x += *y;
*x += *y;
}
void fun(int *x, int *y)
{
*x += 2 * (*y);
}
問兩個函數(shù)是否等價，能否互換
解答：第一題的函數(shù)是交換。但假如考慮x, y都是指向同一個變量,結(jié)果是這個變量的值為0.
第二題的兩個函數(shù)是有區(qū)別的,也考慮x,y是指向同一個變量.這樣第一個函數(shù)的結(jié)果是這個變量的4倍.但第二個函數(shù)的結(jié)果是變量的3倍.