面试题目总结

1.编程题：
    两个字符串a和b，a和b中都含有汉字，判断两字符串是否匹配。匹配的条件是：b中的汉字出现的次数不少于在a中出现的次数，b中的字符在a中都有出现。并分析时间和空间的复杂度。
2.算法题：
    已知一个序列seq=[a,b,....,z,aa,ab,...,zz,aaa,aab,....],求任意一个字符串s=[a-z]+在seq中出现的位置。
1.编程题:
    有一组N个固定的集合（N为万量级），在每个集合中有0-ID个编号为id的集合，每个集合中有1-M个temp数组（M为1-100）。现在输入temp输出集合的id，条件是这一组temp包含集合id中所有的temp数组，如果没有输出-1.
例如输入：
temp1空格temp2
temp1空格temp3
temp2空格temp3 temp4
注：a.temp中有汉字出现
    b.可以用代码或者伪代码实现
    c.分析该算法的时间和空间复杂度
2.算法题：
    已知一个文件中有N条无序的条目，T1,T2,...,TN，现在可以找到一个整数M使得T1 <T2 <... <TM和TM+1 <TM+2 <.... <TN.
（1）写出一个算法，使得T1' <T2' <... <TN'，其中读写文件的时间复杂度为O(n),内存不限。
（2）写出一个算法，使得T1' <T2' <... <TN'，其中读写文件的时间复杂度为O(n),空间复杂度为O(1)。

一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数

如果n为偶数，则将它除以2
如果n为奇数，则将它加1或者减1
问对于一个给定的n，怎样才能用最少的步骤将它变到1
例如
n=61
n-- 60
n/2 30
n/2 15
n++ 16
n/2 8
n/2 4
n/2 2
n/2 1
编程用c/c++

题目：用C++设计一个不能被继承的类
参考答案：
在Java 中定义了关键字final ，被final 修饰的类不能被继承。但在C++ 中没有final 这个关键字，要实现这个要求还是需要花费一些精力。
首先想到的是在C++ 中，子类的构造函数会自动调用父类的构造函数。同样，子类的析构函数也会自动调用父类的析构函数。要想一个类不能被继承，我们只要把它的构造函数和析构函 数都定义为私有函数。那么当一个类试图从它那继承的时候，必然会由于试图调用构造函数、析构函数而导致编译错误。
可是这个类的构造函数和析构函数都是私有函数了，我们怎样才能得到该类的实例呢？这难不倒我们，我们可以通过定义静态来创建和释放类的实例。基于这个思路，我们可以写出如下的代码：
///////////////////////////////////////////////////////////////////////
// Define a class which can't be derived from
///////////////////////////////////////////////////////////////////////
class FinalClass1
{
public :
      static FinalClass1* GetInstance()
      {
            return new FinalClass1;
      }

      static void DeleteInstance( FinalClass1* pInstance)
      {
            delete pInstance;
            pInstance = 0;
      }

private :
      FinalClass1() {}
      ~FinalClass1() {}
};
这个类是不能被继承，但在总觉得它和一般的类有些不一样，使用起来也有点不方便。比如，我们只能得到位于堆上的实例，而得不到位于栈上实例。
能不能实现一个和一般类除了不能被继承之外其他用法都一样的类呢？办法总是有的，不过需要一些技巧。请看如下代码：
///////////////////////////////////////////////////////////////////////
// Define a class which can't be derived from
///////////////////////////////////////////////////////////////////////
template <typename T> class MakeFinal
{
      friend T;

private :
      MakeFinal() {}
      ~MakeFinal() {}
};

class FinalClass2 : virtual public MakeFinal<FinalClass2>
{
public :
      FinalClass2() {}
      ~FinalClass2() {}
};
这个类使用起来和一般的类没有区别，可以在栈上、也可以在堆上创建实例。尽管类 MakeFinal <FinalClass2> 的构造函数和析构函数都是私有的，但由于类 FinalClass2 是它的友元函数，因此在 FinalClass2 中调用 MakeFinal <FinalClass2> 的构造函数和析构函数都不会造成编译错误。
但当我们试图从 FinalClass2 继承一个类并创建它的实例时，却不同通过编译。
class Try : public FinalClass2
{
public :
      Try() {}
      ~Try() {}
};

Try temp;
由于类 FinalClass2 是从类 MakeFinal <FinalClass2> 虚继承过来的，在调用 Try 的构造函数的时候，会直接跳过 FinalClass2 而直接调用 MakeFinal <FinalClass2> 的构造函数。非常遗憾的是， Try 不是 MakeFinal <FinalClass2> 的友元，因此不能调用其私有的构造函数。
基于上面的分析，试图从 FinalClass2 继承的类，一旦实例化，都会导致编译错误，因此是 FinalClass2 不能被继承。这就满足了我们设计要求。


1.实现memcpy(void* dest,const void* src,unsigned int count)
2.合并两个链表Lsit* merge(List *l1,List* l2)，合成的新链表要以data从大到小有序
3.实现字符串转换"I love this game"转换成"game this love I"，char* convert(char* s)
4.实现一个高效率的程序（包括所需程序代码），以尽量短的时间，将用户信息表中150张按照时间hash的表（每张表的数据量为100万，数据字 段包含《最近修改时间戳/username/nickname/出生地/所在地/年龄/性别/自我介绍》），转换成按照username hash的100张表。转换过程方法和过程需要考虑：
a）尽可能短的时间中断用户服务；
b）尽可能少的使用机器内存。

int szNum[5] = { 1, 2, 3, 4, 5 };
     int *ptrA = (int*)(&szNum+1);
     int *ptrB = (int*)((int)szNum + 1);
     std::cout << ptrA[-1] << *ptrB << std::endl;
问打印结果是什么？

一、如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）
   struct node { char val; node* next;}
   bool check(const node* head) {} //return false : 无环；true: 有环
    一种O（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;
   }
二、删除一个单项链表的最中间的元素，要求时间尽可能短（不能使用两次循环）
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矩阵，规定矩阵沿45度线递增(威盛)
/**
* 得到如下样式的二维数组
* zigzag（jpeg编码里取象素数据的排列顺序）
*
*   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; //这个标志位用来判断是从45度角生成还是225度角生成
int count = 0;
for(i=0; i<n; i++) //生成的上半部分的数据
{

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--) //生成的是下半部分的数据
{
// cout<<i<<endl;
if(flag)
{
   for(int r = 0; r<=i-1; r++)
   {
    int r1 = n-i+r;       //代表当前行
    int c1 = 2*n-i-1-r1; //代表当前列
    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;
}
网上还有一个人写了一个比较巧的算法：
/**
* 得到如下样式的二维数组
* zigzag（jpeg编码里取象素数据的排列顺序）
*
*   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;
        }
    }
    /* 数组赋值 */
    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的整数，不能使用流程控制语句(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,当s.p[1]=1时,s.p此时存放的是1了,而不是地址s.i,故在s.p[0]   =   2时出错.
此时相当于s.p=ox00000001;地址ox0000001   =   2;当然就出错了
如果语句s.p[0]   =2   先于s.p[1]=1则程序就不会出错.此时语句相当于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;
}
请改错，溢出已经考虑，不是错误
2.
void   foo(int   *x,   int   *y)
{
    *x   +=   *y;
    *x   +=   *y;
}
void   fun(int   *x,   int   *y)
{  
    *x   +=   2   *   (*y);
}
问两个函数是否等价，能否互换
解答：第一题的函数是交换。但假如考虑x,   y都是指向同一个变量,结果是这个变量的值为0.
第二题的两个函数是有区别的,也考虑x,y是指向同一个变量.这样第一个函数的结果是这个变量的4倍.但第二个函数的结果是变量的3倍.


排序总结
1.选择排序
选择排序的基本思想是：
对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理
是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这
样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
例1:输入序列数据按非减顺序输出.
   程序如下:
program xzpx;
const n=7;
var a:array[1..n] of integer;
    i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
writeln;
for i:=1 to n-1 do
begin
   k:=i;
   for j:=i+1 to n do
    if a[j]<a[k] then k:=j;
   if k<>i then
    begin t:=a[i];a[i]:=a[k];a[k]:=t;end;
end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.

2.插入排序

插入排序的基本思想:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适
当位置p，原来p后的元素一一向右移动一个位置,使得L[1..i]又是排好序的序列。
例2:输入序列数据按非减顺序输出.
程序1:
program crpx;
const n=7;
var a:array[1..n] of integer;
    i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
writeln;
for i:=2 to n do
begin
   k:=a[i];j:=i-1;
   while (k<a[j]) and (j>0) do
    begin a[j+1]:=a[j];j:=j-1 end;
   a[j+1]:=k;
end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.
3.冒泡排序
冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个
记录是反序的,则进行交换,直到无反序的记录为止。
例:输入序列数据按非减顺序输出。
程序1:
program mppx;
const n=7;
var a:array[1..n] of integer;
    i,j,k,t:integer;
begin
     write('Enter date:');
     for i:= 1 to n do read(a[i]);
     for i:=1 to n -1 do
      for j:=n downto i+1 do
       if a[j-1]<a[j] then
        begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t end;
     write('output data:');
     for i:= 1 to n do write(a[i]:6);
     writeln;
end.
程序2：
program mppx;
const n=7;
var a:array[1..n] of integer;
    i,j,k,t:integer;
    bool:boolean;
begin
     write('Enter date:');
     for i:= 1 to n do read(a[i]);
     i:=1;bool:=true;
     while (i<n) and bool do
      begin
      bool:=false;
      for j:=n downto i+1 do
       if a[j-1]<a[j] then
        begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=true end;
      i:=i+1;
      end;
     write('output data:');
     for i:= 1 to n do write(a[i]:6);
     writeln;
end.
　
程序3：
program mppx;
const n=7;
var a:array[1..n] of integer;
    i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
writeln;
k:=n;
while k>0 do
begin
   j:=k-1;k:=0;
   for i:=1 to j do
    if a[i]>a[i+1] then
     begin t:=a[i];a[i]:=a[i+1];a[i+1]:=t;k:=i;end;
end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.　
返回
4.2快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或
左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.
例:输入一组数据小到大排序.
程序1:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
   while (b[j]>=x) and (j>i) do j:=j-1;
   if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
   while (b[i]<=x) and (i<j) do i:=i+1;
   if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
　
程序2:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
   while (b[j]>=x) and (j>i) do j:=j-1;
   if j>i then begin b[i]:=b[j];i:=i+1;end;
   while (b[i]<=x) and (i<j) do i:=i+1;
   if i<j then begin b[j]:=b[i];j:=j-1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
返回
4.3希尔排序　
基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。
序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当
h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用：d1=n div 2 ,di=di-1
div 2 ；i=2,3,4.....其中n为待排序序列的长度。
程序1:(子序列是插入排序)
program xepx;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i,j,t,d:integer;
bool:boolean;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
d:=n;
while d>1 do
begin
d:=d div 2;
for j:=d+1 to n do
    begin
    t:=a[j];i:=j-d;
    while (i>0) and (a[i]>t) do
       begin a[i+d]:=a[i];i:=i-d;end;
    a[i+d]:=t;
    end;
end;
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
程序2:(子序列是冒泡排序)
program xepx;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i,temp,d:integer;
bool:boolean;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
d:=n
while d>1 do
begin
d:=d div 2;
repeat
   bool:=true;
   for i:=1 to n-d do
     if a[i]>a[i+d] then
     begin temp:=a[i];a[i]:=a[i+d];a[i+d]:=temp; bool:=false end;
until bool;
end;
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
返回
4.4 堆排序与二叉树排序
1.堆排序
堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有
       Ri<=R2i 和Ri<=R2i+1(或>=)
堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。
堆排序的思想是：
1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）
2）当未排序完时
输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。
程序如下：
program duipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procedure sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a[i];
while j<=m do
begin
   if (j<m) and (a[j]>a[j+1]) then j:=j+1;
   if t>a[j] then
      begin a[i]:=a[j];i:=j;j:=2*i; end
             else exit;
a[i]:=t;
end;
end;
begin
for i:=1 to n do read(a[i]);
for i:=(n div 2) downto 1 do
sift(a,i,n);
for i:=n downto 2 do
begin
write(a[1]:4);
a[1]:=a[i];
sift(a,1,i-1);
end;
writeln(a[1]:4);
end.
2.二叉树排序
排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左
（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如
下：
program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
     nod=record
     w:integer;
     right,left:point ;
     end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
   begin
    new(p);
    with p^ do begin w:=d;right:=nil;left:=nil end;
    if k then begin root:=p; k:=false end;
   end
else with p^ do if d>=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
   begin
    if left<>nil then hyt1(left);
    write(w:4);
    if right<>nil then hyt1(right);
   end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a[i],first);
hyt1(root);writeln;
end.
返回
4.5 归并排序
归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并
(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。
1.二路归并
例1:将有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合并一个有序表 L.
program gb;
const m=3;n=7;
type arrl1=array[1..m] of integer;
arrl2=array[1..n] of integer;
arrl=array[1..m+n] of integer;
var a:arrl1;
b:arrl2;
c:arrl;
i,j,k,r:integer;
begin
write('Enter l1(sorted):');
for i:=1 to m do read(a[i]);
write('Enter l2(sorted):');
for i:=1 to n do read(b[i]);
i:=1;j:=1;k:=0;
while (i<=m) and (j<=n) do
begin
k:=k+1;
if a[i]<=b[j] then begin c[k]:=a[i];i:=i+1; end
               else begin c[k]:=b[j];j:=j+1;end;
end;
if i<=m then for r:=i to m do c[m+r]:=a[r];
if j<=n then for r:=j to n do c[n+r]:=b[r];
writeln('Output data:');
for i:=1 to m+n do write(c[i]:5);
writeln;
end.
2.归并排序
program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
    i:integer;
procedure merge(r:arr;l,m,n:integer;var r2:arr);
var i,j,k,p:integer;
begin
i:=l;j:=m+1;k:=l-1;
while (i<=m)and (j<=n) do
begin
   k:=k+1;
   if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end
                 else begin r2[k]:=r[j];j:=j+1 end
end;
if i<=m then
for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;
if j<=n then
for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;
end;
procedure mergesort( var r,r1:arr;s,t:integer);
var k:integer; c:arr;
begin
if s=t then r1[s]:=r[s] else
   begin
    k:=(s+t) div 2;
    mergesort(r,c,s,k);
    mergesort(r,c,k+1,t);
    merge(c,s,k,t,r1)
   end;
end;
begin
write('Enter data:');
for i:= 1 to maxn do
read(a[i]);
mergesort(a,b,1,maxn);
for i:=1 to maxn do
write(b[i]:9);
writeln;
end.
返回
4.6 线形排序
以上我们讨论的算法均是基于比较的排序算法，在排序算法中有基于数字本身的算法：计数、桶、基
数排序。
1.计数排序
基本思想是对于序列中的每一元素x,确定序列中小于x的元素的个数。
例：n个整数序列且每个值在[1,m],排序之。
program jspx;
const m=6;n=8;
var i,j:integer;
    a,b:array[1..n] of integer;
    c:array[1..m] of integer;
begin
writeln('Enter data:');
for i:=1 to n do read(a[i]);
for i:=1 to m do c[i]:=0;
for i:=1 to n do c[a[i]]:=c[a[i]]+1;
for i:=2 to m do c[i]:=c[i]+c[i-1];
for i:=n downto 1 do
begin
b[c[a[i]]]:=a[i];
c[a[i]]:=c[a[i]]-1;
end;
writeln('Sorted data:');
for i:= 1 to n do
write(b[i]:6);
end.
2.桶排序
桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个
桶装入一个值,顺序输出各桶的值,将得到有序的序列。
例：输入n个0到100之间的整数，由小到大排序输出。
program tpx;
const n=7;
var b:array[0..100] of integer;
    k:0..100;
    i:integer;
begin
write('Enter date:(0-100)');
for i:=0 to 100 do b[i]:=0;
for i:= 1 to n do
begin
read(k);
b[k]:=b[k]+1;
end;
writeln('Output data:');
for i:=0 to 100 do
while b[i]>0 do begin write(i:6);b[i]:=b[i]-1 end;
writeln;
end.
3.基数排序
基本思想是对n个元素依次按k,k-1,...1位上的数字进行桶排序。
program jspx;
const n=8;
type link=^node;
    node=record
        data:integer;
        next:link;
     end;
var i,j,l,m,k:integer;
    a:array[1..n] of integer;
    s:string;
    q,head:array[0..9] of link;
    p,p1:link;
begin
writeln('Enter data:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
begin
for j:=0 to 9 do
   begin
    new(head[j]);
    head[j]^.next:=nil;
    q[j]:=head[j]
   end;
for j:=1 to n do
   begin
    str(a[j],s);
    for k:=1 to 5-length(s) do
     s:='0'+ s;
    m:=ord(s[i])-48;
    new(p);
    p^.data:=a[j];
    p^.next:=nil;
    q[m]^.next:=p;
    q[m]:=p;
   end;
l:=0;
for j:=0 to 9 do
begin
   p:=head[j];
   while p^.next<>nil do
    begin
     l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;
    end;
end;
end;
writeln('Sorted data:');
for i:= 1 to n do
write(a[i]:6);
end.
各种排序算法的比较
1.稳定性比较
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的
选择排序、希尔排序、快速排序、堆排序是不稳定的
2.时间复杂性比较
插入排序、冒泡排序、选择排序的时间复杂性为O(n2)
其它非线形排序的时间复杂性为O(nlog2n)
线形排序的时间复杂性为O(n);
3.辅助空间的比较
线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);
4.其它比较
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。
宜用归并排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
最短路径问题
#include <stdio.h>
#include <conio.h>
#include <assert.h>
#include <stdlib.h>
#include <mem.h>

#define tile_num(x,y) ((y)*map_w+(x)) //将 x,y 坐标转换为地图上块的编号
#define tile_x(n) ((n)%map_w) //由块编号得出 x,y 坐标
#define tile_y(n) ((n)/map_w)

#define MAPMAXSIZE 180 //地图面积最大为 180x180，如果没有64K内存限制可以更大
#define MAXINT 32767

//树结构, 比较特殊, 是从叶节点向根节点反向链接，方便从叶节点找到根节点
typedef struct tree_node *TREE;

struct tree_node {
int h; //节点所在的高度，表示从起始点到该节点所有的步数
int tile; //该节点的位置
TREE father; //该节点的上一步
};

//链接结构，用于保存处理过的和没有处理过的结点
typedef struct link_node *LINK;

struct link_node {
TREE node;
int f;
LINK next;
};

LINK sort_queue; // 保存没有处理的行走方法的节点
LINK store_queue; // 保存已经处理过的节点 (搜索完后释放)

unsigned char * map; //地图数据
unsigned int * dis_map; //保存搜索路径时,中间目标地最优解

int map_w,map_h; //地图宽和高
int start_x,start_y,end_x,end_y; //地点,终点坐标

// 初始化队列
void init_queue(void)
{
sort_queue=(LINK)malloc(sizeof(*sort_queue));
sort_queue->node=NULL;
sort_queue->f=-1;
sort_queue->next=(LINK)malloc(sizeof(*sort_queue));
sort_queue->next->node=NULL;
sort_queue->next->f=MAXINT;
sort_queue->next->next=NULL;

store_queue=(LINK)malloc(sizeof(*store_queue));
store_queue->node=NULL;
store_queue->f=-1;
store_queue->next=NULL;
}

// 待处理节点入队列, 依靠对目的地估价距离插入排序
void enter_queue(TREE node,int f)
{
LINK p=sort_queue,father,q;
while(f>p->f) {
father=p;
p=p->next;
assert(p);
}
q=(LINK)malloc(sizeof(*q));
assert(sort_queue);
q->f=f,q->node=node,q->next=p;
father->next=q;
}

// 将离目的地估计最近的方案出队列
TREE get_from_queue(void)
{
LINK bestchoice=sort_queue->next;
LINK next=sort_queue->next->next;
sort_queue->next=next;

bestchoice->next=store_queue->next;

Top

store_queue->next=bestchoice;
return bestchoice->node;
}

// 释放栈顶节点
void pop_stack(void)
{
LINK s=store_queue->next;
assert(s);
store_queue->next=store_queue->next->next;
free(s->node);
free(s);
}

// 释放申请过的所有节点
void freetree(void)
{
int i;
LINK p;
while(store_queue){
p=store_queue;
free(p->node);
store_queue=store_queue->next;
free(p);
}
while (sort_queue) {
p=sort_queue;
free(p->node);
sort_queue=sort_queue->next;
free(p);
}
}

// 估价函数,估价 x,y 到目的地的距离,估计值必须保证比实际值小
int judge(int x,int y)
{
int distance;
distance=abs(end_x-x)+abs(end_y-y);
return distance;
}

// 尝试下一步移动到 x,y 可行否
int trytile(int x,int y,TREE father)
{
TREE p=father;
int h;
if (map[tile_num(x,y)]!=' ') return 1; // 如果 (x,y) 处是障碍,失败
//这一步用来判断(x,y)点是否已经加入队列，多余可以删除，因为dis_map已经
//保存该点是否已经保存
//while (p) {
// if (x==tile_x(p->tile) && y==tile_y(p->tile)) return 1; //如果 (x,y) 曾经经过,失
败
// p=p->father;
//}
h=father->h+1;
if (h>=dis_map[tile_num(x,y)]) return 1; // 如果曾经有更好的方案移动到 (x,y) 失败
dis_map[tile_num(x,y)]=h; // 记录这次到 (x,y) 的距离为历史最佳距离

// 将这步方案记入待处理队列
p=(TREE)malloc(sizeof(*p));
p->father=father;
p->h=father->h+1;
p->tile=tile_num(x,y);
enter_queue(p,p->h+judge(x,y));
return 0;
}

// 路径寻找主函数
int * findpath(void)
{
TREE root;
int i,j;
int * path;
memset(dis_map,0xff,map_h*map_w*sizeof(*dis_map)); //填充dis_map为0XFF，表示各点未
曾经过
init_queue();
root=(TREE)malloc(sizeof(*root));
root->tile=tile_num(start_x,start_y);
root->h=0;
root->father=NULL;
enter_queue(root,judge(start_x,start_y));
for (;;) {
int x,y,child;
TREE p;
root=get_from_queue();
if (root==NULL) {
return NULL;
}
x=tile_x(root->tile);
y=tile_y(root->tile);
gotoxy(x+1,y+1);
putchar('\'');
if (x==end_x && y==end_y) break; // 达到目的地成功返回

child=trytile(x,y-1,root); //尝试向上移动
child&=trytile(x,y+1,root); //尝试向下移动
child&=trytile(x-1,y,root); //尝试向左移动
child&=trytile(x+1,y,root); //尝试向右移动
//child&=trytile(x+1,y-1,root);//尝试向右上移动
//child&=trytile(x+1,y+1,root); //尝试向右下移动
//child&=trytile(x-1,y+1,root); //尝试向左下移动
//child&=trytile(x-1,y-1,root); //尝试向左上移动

if (child!=0)
pop_stack(); // 如果四个方向均不能移动,释放这个死节点
}

// 回溯树，将求出的最佳路径保存在 path[] 中
path=(int*)malloc((root->h+2)*sizeof(int));
assert(path);
for (i=0;root;i++) {
path[i]=root->tile;
root=root->father;
}
path[i]=-1;
freetree();
return path;
}

void printpath(int *path)
{
int i;
if(path==NULL) return ;
for (i=0;path[i]>=0;i++) {
gotoxy(tile_x(path[i])+1,tile_y(path[i])+1);
cprintf(".");
}
}

int readmap(void)
{
FILE *f;
int i,j;
f=fopen("map.dat","r");
assert(f);
fscanf(f,"%d,%d\n",&map_w,&map_h);
map=malloc(map_w*map_h+1);
assert(map);
for(i=0;i<map_h;i++)
fgets(map+tile_num(0,i),map_w+2,f);
fclose(f);
start_x=-1,end_x=-1;
for (i=0;i<map_h;i++)
for (j=0;j<map_w;j++) {
if (map[tile_num(j,i)]=='s') map[tile_num(j,i)]=' ',start_x=j,start_y=i;
if (map[tile_num(j,i)]=='e') map[tile_num(j,i)]=' ',end_x=j,end_y=i;
}
assert(start_x>=0 && end_x>=0);
dis_map=malloc(map_w*map_h*sizeof(*dis_map));
assert(dis_map);
return 0;
}

void showmap(void)
{
int i,j;
clrscr();
for (i=0;i<map_h;i++) {
gotoxy(1,i+1);
for (j=0;j<map_w;j++)
if (map[tile_num(j,i)]!=' ') cprintf("O");
else cprintf(" ");
}
gotoxy(start_x+1,start_y+1);
cprintf("s");
gotoxy(end_x+1,end_y+1);
cprintf("e");
}

int main()
{
int * path;
readmap();
showmap();
getch();
path=findpath();
printpath(path);
if(dis_map) free(dis_map);
if(path) free(path);
if(map) free(map);
getch();
return 0;
}
最小堆队列实现
堆队列实现
#include <iostream>
using namespace std;
enum Result{Overflow,Underflow};
template <class T>
class PrioQueue
{
public:
PrioQueue()
{
  maxSize=20;
  n=0;
  q=new T[maxSize];
}
PrioQueue(T* head,int length)
{
  maxSize=length+1;
  n=length;
  q=new T[length];
  for(int i=0;i<length;i++)
   q[i]=head[i];
        CreateHeap(length);
}
~PrioQueue(){delete q;}
    void Append(const T& x);
void Serve(T& x);
bool IsEmpty() const
{
  return n==0;
}
bool IsFull() const
{
  return n==20;
}
private:
T* q;
void AdjustDown(int r,int j);
void AdjustUp(int j);
void CreateHeap(int n);
// void Print();
int n,maxSize;
};
template <class T>
void PrioQueue<T>::AdjustDown(int r,int j)
{
T temp=q[r];
int m=2*r+1;
while(m<=j)
{
if((q[m]>q[m+1])&&(m<j))
m=m+1;
if(temp>q[m])
q[(m-1)/2]=q[m];
m=2*m+1;
}
q[(m-1)/2]=temp;
}
template <class T>
void PrioQueue<T>::AdjustUp(int j)
{
T temp=q[j];
int m=j;
while((m>0)&&(q[(m-1)/2]>temp))
{
q[m]=q[(m-1)/2];
m=(m-1)/2;
}
q[m]=temp;
}
template <class T>
void PrioQueue<T>::Serve(T& x)
{
if(IsEmpty()) throw Overflow;
x=q[0];
q[0]=q[n-1];
AdjustDown(0,n-1);
n=n-1;
}
template <class T>
void PrioQueue<T>::Append(const T& x)
{
if(IsFull()) throw Underflow;
q[n++]=x;
AdjustUp(n-1);
//Print();
}
template <class T>
void PrioQueue<T>::CreateHeap(int n)
{
for(int i=(n-1)/2;i>-1;i--)
AdjustDown(i,n-1);
}
/*
template <class T>
void PrioQueue<T>::Print()
{
for(int i=0;i<n;i++)
cout<<q[i]>>endl;
}
*/
int main()
{
int x[6]={62,18,30,46,50,70};
int e;
PrioQueue<int> m=PrioQueue<int>(x,6);
try
{
m.Serve(e);
cout<<e;
system("pause");
}
catch(Result err)
{
switch(err)
{   
case Underflow:
cout<<"underflow"<<endl;
break;
case Overflow:
cout<<"overflow"<<endl;   
break;
}
}
}

队列实现：
/*
（1）initQueue（Q）
　 置空队。构造一个空队列Q。
（2）isEmpty（Q）
　 判断队列是否空。若队列Q为空，则返回真值，否则返回假值。

（3）isFull(Q)
   判断队列是否以满, 以满返回true, 没满则返回flase
（4） addQueue（Q，x）
　 若队列Q非满，则将元素x插入Q的队尾。此操作简称 入队 。
（5） DelQueue（Q）
　 若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称 出队 。
（6） queueFront（Q）
　 若队列Q非空，则返回队头元素，但不改变队列Q的状态。
（7） queueDisplay（Q）
　 显示队列中的元素。
*/
#include "iostream.h"
#define maxSize 10  // 存储数据大小, 可以随便设定值
struct Queue
{
int data[maxSize];
int front;  // 队首
int rear;  // 队尾
};
void initQueue( Queue &Q );
bool isEmpty( Queue &Q );
bool isFull( Queue &Q );
bool addQueue( Queue &Q, int x );
bool delQueue( Queue &Q );
int queueFront( Queue &Q );
bool queueDisplay( Queue &Q );
int main( void )
{
int i;
int num;
Queue Q;
initQueue( Q );  // 初始化队列

cout << "输入入队10个数" << endl;
/* 入队 */
for ( i = 0; i < 10; i++ )
{
  cin >> num;
  if ( addQueue( Q, num ) == false )
  {
   cout << "队列以满!" << endl;
  }
}
cout << "队头: " << queueFront( Q ) << endl; // 显示队头
cout << "队列所有元素:" << endl;
if ( queueDisplay( Q ) == false )    // 显示队列所有元素
{
  cout << "队列为空!" << endl;
}

/* 出队 */
for ( i = 0; i < 5; i++ )
{
  if ( delQueue( Q ) == false )
  {
   cout << "队列以空" << endl;
  }
}
cout << endl;
cout << endl;
cout << "================== 出队以后 ===========================" << endl;
cout << "出队后队头: " << queueFront( Q ) << endl; // 显示队头
cout << "出队后队列所有元素:" << endl;
if ( queueDisplay( Q ) == false )     // 显示队列所有元素
{
  cout << "队列为空!" << endl;
}

cout << endl;
cout << "输入入队5个数" << endl;
/* 再入队 */
for ( i = 0; i < 5; i++ )
{
  cin >> num;
  if ( addQueue( Q, num ) == false )
  {
   cout << "队列以满!" << endl;
  }
}
cout << endl;
cout << endl;
cout << "================== 入队以后 ===========================" << endl;
cout << "入队后队头: " << queueFront( Q ) << endl; // 显示队头
cout << "入队后队列所有元素:" << endl;
if ( queueDisplay( Q ) == false )     // 显示队列所有元素
{
  cout << "队列为空!" << endl;
}
return 0;
}
/* 初始化队列 */
void initQueue( Queue &Q )
{
int i;
for ( i = 0; i < maxSize; i++ )
{
  Q.data[i] = 0;  // 初始值都为0
  Q.front = 0;
  Q.rear = 0;
}
}
/* 判断队列是否为空, 为空返回true, 不为空则返回flase */
bool isEmpty( Queue &Q )
{
if ( Q.front != 0 )  // 如果队头不等于0,则表示不为空
{
  return false;
}

return true;
}
/* 判断队列是否以满, 以满返回true, 没满则返回flase */
bool isFull( Queue &Q )
{
if ( Q.data[maxSize - 1] == 0 )  // 如果队尾等于0,则表示队列没满
{
  return false;
}
return true;
}
/* 若队列Q非满,则将元素x插入Q的队尾.此操作简称 入队 */
bool addQueue( Queue &Q, int x )
{
if ( isFull( Q ) == true ) // 检测队列是否以满
{
  return false;
}
int i;
for ( i = 0; i < maxSize; i++ )
{
  if ( Q.data[i] == 0 ) // 当为0时则表示此位置没被复值,即可在此位置入队,且该值变为队尾
  {
   if ( i == 0 ) // 设队头
   {
    Q.front = x;
   }
   Q.data[i] = x;
   Q.rear = x;  // 设队尾,每添加一个值,则该值即为队尾
   return true;
  }
}
}
/* 若队列Q非空,则删去Q的队头元素,并返回该元素. 此操作简称 出队 */
bool delQueue( Queue &Q )
{
if ( isEmpty( Q ) == true ) // 检测队列是否为空
{
  return false;
}
int i;

/* 删除队头元素，并将所有队列元素提前一个位置 */
for ( i = 0; i < maxSize; i++ )
{
  if ( Q.data[i] == 0 || i == maxSize - 1 ) // 判断队列中元素是否以全部提前
  {
   Q.data[i] = 0;
   Q.front = Q.data[0]; // 设队头,每出队一个值,则原来第二个值变成队头
   return true;
  }
  Q.data[i] = Q.data[i+1]; // 将队列元素提前
}
}
/* 若队列Q非空,则返回队头元素,但不改变队列Q的状态. */
int queueFront( Queue &Q )
{
if ( isEmpty( Q ) == true ) // 检测队列是否为空
{
  return false;
}

return Q.front;  // 返回队头元素
}
/* 显示队列中的元素 */
bool queueDisplay( Queue &Q )
{
if ( isEmpty( Q ) == true ) // 检测队列是否为空
{
  return false;
}
int i;
for ( i = 0; i < maxSize; i++ )
{
  if ( Q.data[i] == 0 ) // 判断队列中元素是否以全部显示
  {
   return true;
  }
  cout << "第" << i + 1 << "个: " << Q.data[i] << endl;
}

}