面试——数据结构二

排序及查找方法
 
#include <malloc.h>
#include<stdio.h>
#define N 11
/*用监视哨查找*/
int search(int array[],int n,int k)
{int i;
 i=n-1;
array[0]=k;
while(array[i]!=k) i--;
return(i);
}
/*折半查找法*/
int halfsearch(int array[],int n,int k)
{int i,j,mid;
 i=1;j=n;
while(i<=j)
{mid=(i+j)/2;
 if(k==array[mid]) return(mid);
else if(k<array[mid]) j=mid-1;
      else i=mid+1;
}
return(0);
}

/*冒泡排序法*/
void mpsort(int array[])
{int i,j,a;
a=0;
 for(i=1;i<N;i++)
  for(j=i+1;j<N;j++)
   if(array[i]>array[j])
     {a=array[i];
     array[i]=array[j];
     array[j]=a;}
}
/*直接插入排序*/
void insertsort(int array[])
{int i,j;
 for(i=2;i<N;i++)
 {array[0]=array[i];
j=i-1;
while(array[0]<array[j])
 {array[j+1]=array[j--];
 array[j+1]=array[0];
}
}
}
/*建立*/
void creat(int array[])
{int i;
 printf("enter the array:\n");
 for(i=1;i<N;i++)
 scanf("%d",&array[i]);
}

/*显示*/
void print(int array[])
  {int i;
   printf("The numbers after sort is:\n");
   for(i=1;i<N;i++)
   printf("%d ",array[i]);
   printf("\n");
  }

main()
{int a[11],i,x,chang;
 /*printf("enter the array\n");
 for(i=1;i<11;i++)
 scanf("%d",&a[i]);*/

aga:
 printf("\nchang:1: use watching method finding\n      2:use half method finding\n      3: use directness intsert method sort\n      4:use bubble up method sort\n      5:exit\n");
 scanf("%d",&chang);
 switch (chang)
 {case 1:
       {creat(a);
 printf("Please int the search number:\n");
 scanf("%d",&x);
 printf("The number station is:%d\n",search(a,N,x));
 goto aga;
 }
  case 2:
     { creat(a);
       insertsort(a);
       print(a);
       printf("Please int the search number:\n");
       scanf("%d",&x);
       printf("The number station is:%d\n",halfsearch(a,N,x));
       goto aga;
      }
   case 3:
     {creat(a);
      insertsort(a);
      print(a);
      goto aga;
     }

   case 4:
     {creat(a);
      mpsort(a);
      print(a);
      goto aga;
     }

   case 5:{ printf("exit!\n");break;}
   default:{printf("Error!\n"); goto aga;}
}
}
 

 

二、线性链表的存储实现

struct LNODE{

ElemType data;

struct LNODE *next;

};

typedef struct LNODE LNode;

typedef struct LNODE * LinkList;

1初始化操作

Status Init_L(LinkList L){

if (L=(LinkList *)malloc(sizeof(LNode)))

{L->next=NULL;return 1;}

else return 0;

}

2插入操作

Status ListInsert_L(LinkList &L,int i,ElemType e){

p=L,j=0;

while(p&&j<i-1){p=p->next;++j;}

if(!p||j>i-1) return ERROR;

s=(LinkList)malloc(sizeof(LNode));

s->data=e;s->next=p->next;

p->next=s;

return OK;

}//ListInsert_L

 

3删除操作

Status ListDelete_L(LinkList &L,int i,ElemType &e){

p=L,j=0;

while(p&&j<i-1){p=p->next;++j;}

if(!p->next||j>i-1) return ERROR;

q=p->next;p->next=q->next;

e=q->data;free(q);

return OK;

}//ListDelete_L

 

4取某序号元素的操作

Status GetElem_L(LinkList &L,int i,ElemType &e){

p=L->next,j=1;

while(p&&j<i){p=p->next;++j;}

if(!p||j>i) return ERROR;

e=p->data;

return OK;

}//GetElem_L

5归并两个单链表的算法

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){

//已知单链线性表La和Lb的元素按值非递减排列

//归并后得到新的单链线性表Lc,元素也按值非递减排列

pa=La->next;pb=Lb->next;

Lc=pc=La;

while(pa&&pb){

if(pa->data<=pb->data){

pc->next=pa;pc=pa;pa=pa->next;

}else{pc->next=pb;pc=pb;pb=pb->next;}

}

pc->next=pa?pa:pb;

free(Lb);

}//MergeList_L

 

 

头指针与头结点的区别：

头指针只相当于结点的指针域，头结点即整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放 线性表的长度等附加信息，也可以不存储任何信息。

典型的约瑟夫环问题。原问题比你的问题要复杂一点。我以前写的程序：
1.用数组。

# include "stdio.h"
# define SIZE 100
main()
{
    int m,n,i;
    int array[SIZE];
    printf("约瑟夫环求解,当前设置最大人数为%d.\n",SIZE);
    printf("报数上限:\n");
    scanf("%d",&m);
    printf("总人数为:\n");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    printf("第%d人的密码为:",i+1);
    scanf("%d",&array);
    }
    joseph(array,m,n);
}
int joseph(a,m,n)
int a[],m,n;
{
    int b[SIZE];        /*计录编号数组.*/
    int i;                /*计数器.*/
    int flag=0;
    int code;            /*删取人的号码.*/
    int sum=n;            /*现存人数.*/
    int point=0;        /*当前报数人的位置.*/
    int num=m;
    for(i=0;i<n;i++)    /*计录数组.*/
    {
    b=i+1;
    }
    while(sum!=0)        /*当人数不为零时继续循环.*/
    {
    for(i=1;i<=num;i++)    /*进行报数.*/
    {

        if(point>=sum)    /*当前报数位置超过最后一人时从第一人报起.*/
        {point=1;}
        else point++;

    }
    num=a[point-1];    /*取密码.*/
    code=b[point-1];    /*取号码.*/
    for(i=point;i<=sum;i++) /*删去退出的人.*/
    {
        a[i-1]=a;
        b[i-1]=b;

    }
    sum--;            /*现存总人数.*/
    flag++;            /*退出的人数.*/
    point--;
    printf("已退出%d人,退出的人的编号为%d.\n",flag,code);
    }

}

2.用循环链表

# include "stdio.h"
# include "alloc.h"
# define LEN sizeof(struct player)
    struct player
    {
    int num;    /*编号*/
    int secret;    /*密码*/
    struct player *next;
    };
    int n;    /*总人数*/
main()
{
    int m;
    void create();
    void delete();
    struct player *head;
    head=(struct player *)malloc(LEN);
    printf("请输入第一次的密码:\n");
    scanf("%d",&m);
    create(head);
    delete(head,m);

}
void create(struct player *head)
{
    struct player *p1,*p2,*p;
    p1=p2=head;
    printf("请输入编号,密码,当编号为零时输入结束.\n");
    printf("总人数为:\n");
    scanf("%d",&n);
    do
    {
    p=p2;
    p2=p1;
    printf("编号:");
    scanf("%d",&p2->num);
    printf("密码:");
    scanf("%d",&p2->secret);
    p1=(struct player *)malloc(LEN);
    p2->next=p1;
    }while(p2->num!=0);
    p->next=head;
    free(p1);
}
void delete(struct player *head,int m)
{
    int i;
    struct player *p,*q;
    int sum;
    p=head;
    sum=m;
    while(n!=0)
    {
    for(i=1;i<sum;i++)
    { q=p;
        p=p->next;
    }
    printf("%d,",p->num);
    sum=p->secret;
    q->next=p->next;
    p=p->next;
    n=n-1;
    }
}
题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

1. 程序分析：
2.程序源代码：
#define nmax 50
main()
{
int i,k,m,n,num[nmax],*p;
printf("please input the total of numbers:");
scanf("%d",&n);
p=num;
for(i=0;i<n;i++)
　*(p+i)=i+1;
　i=0;
　k=0;
　m=0;
　while(m<n-1)
　{
　if(*(p+i)!=0) k++;
　if(k==3)
　{ *(p+i)=0;
　k=0;
　m++;
　}
i++;
if(i==n) i=0;
}
while(*p==0) p++;
printf("%d is left\n",*p);
}
我写了一个带头结点的单链表逆置程序，程序的执行结果没什么问题，只是要高手指点一下我写的代码有没有哪里不规范的地方？  
   
  /****************************************************************  
  *     文件名：nz.c       （nz就是逆置！）  
  *     文件描述：带头结点的单链表逆置  
  *     创建人：沁园枫  
  *     创建时间：2006年2月2日  
  ****************************************************************/  
  #include   "stdio.h"  
  typedef int ElemType
  typedef   struct   node       /*单链表结点*/  
  {  
    ElemType    data;                       /*数据域*/  
    struct   node   *next;       /*指针域*/  
  }slink;  
   
  void   main()                     /*主函数*/  
  {  
   slink   *creatslink();                 /*声明xjlb（新建链表）函数*/  
   slink   *inverse(slink  *);       /*声明nzlb（逆置链表）函数*/  
   slink   *h,*p;  
    h= creatslink();                       /*调用xjlb（新建链表）函数*/  
    p=h;  
    while(p-> next!=NULL)/*输出新建单链表后的各元素*/  
    {  
      printf("%d",p-> next ->data);  
      p=p-> next;  
    }  
    printf("\n");  
    h= inverse(h);                     /*调用nzlb（逆置链表）函数*/  
    while(h-> next!=NULL)/*输出逆置后的单链表各元素*/  
    {  
      printf("%d",h-> next ->data);  
      h=h-> next;  
    }  
    getch();                         /*调用getch函数，不知道什么意思的自己查查！*/  
  }  
   
slink   * creatslink()                     /*新建链表函数*/  
  {  
    slink   *h,*l,*a;  
    int   i;  
    h=( slink   *)malloc(sizeof(slink));   /*创建头结点*/
    h-> next =NULL;  
    a=h;  
    for(i=0;i<5;i++)  
    {  
      l=( slink   *)malloc(sizeof(slink));  
      l->data=i;  
      a-> next =l;  
      a=a-> next;  
    }  
    a-> next =NULL;  
    return   h;  
  }  
   
slink   * inverse (slink   *h)         /*逆置链表函数*/  
  {  
   slink   *p,*q;  
    p=h-> next;  
    h-> next =NULL;  
    while(p!=NULL)  
    {  
      q=p;  
      p=p-> next;  
      q-> next =h-> next;  
      h-> next =q;  
    }  
    return   h;  
  } 

单链表逆置算法

 

单链表逆置算法

 

struct node
　{
　　int num;
　　struct node *next;
　}
　struct node* reverse(struct node *head)
　//head 链表头结点　{
　　struct node *p,*temp1,*temp2;
　　if(head==NULL____①____) return head; //||head->next==NULL　　p=head->next;head->next=NULL;
　　while(____②____) //p!=NULL或p　　{
　　　temp1=head;
　　　____③____; //head=p;　　　temp2=p;
　　　p=p->next;
　　　____④____; //temp2->next=temp1;或head->next=temp1;　　　}//Match while statenment
　　　return head; //返回逆置后的链表的头结点　}

 

 

struct node
　{
　　int num;
　　struct node *next;
　}
　struct node* reverse(struct node *head)
　//head 链表头结点　{
　　struct node *p,*temp1,*temp2;
　　if(head==NULL||head->next==NULL) return head;            

 

p=head->next;head->next=NULL;
　　while(p!=NULL或p)

 

{
　　　temp1=head;
　　　head=p;　　　temp2=p;
　　　p=p->next;
　　　temp2->next=temp1;或head->next=temp1;　　　}//Match while statenment
　　　return head; //返回逆置后的链表的头结点　}

 

最大子列和 n的阶乘中有多少个0 10进制to2进制单链表逆置判断链表中是否有环文件中有多少行

#ifndef MYLIST_H
#define MYLIST_H

 

#include <string>

 

struct listnode
{
int value;
listnode *next;

 

listnode ( int num ): value (num), next (NULL)
{
}
};
class Mylist
{
public:

 

Mylist ();
~Mylist ();
void Insert ( int value ) ;
std::string GetEntireList ();

 

void Reverse ();

 

private:
listnode *head;

 

};
#endif

 

//----------------------------------------------------------------

 

#include "Mylist.h"

 

using namespace std;

 

Mylist::Mylist ()
{
head = NULL;
}

 

Mylist::~Mylist()
{
if ( head != NULL )
{
  listnode *temp = head ;
  while ( head != NULL )
  {
   temp = head->next;
   delete head;
   head = temp;
  }
}
}

 

void Mylist::Insert ( int value )
{
if ( head == NULL )
{
  head = new listnode ( 0 );
}

 

listnode *curnode = new listnode ( value );

 

listnode *temp = head;
while (  temp->next != NULL )
{
  temp = temp->next;
}

 

temp->next = curnode;
}

 

string Mylist::GetEntireList ()
{
string str = "";

 

listnode *temp = head->next ;
while ( temp != NULL )
{
  str += temp->value + '0'   ;
  str += ' ' ;
  temp = temp->next;
}

 

return str;
}

 

void Mylist::Reverse ()
{
if ( head == NULL || head->next == NULL )
{
  return;
}

 

listnode *end = head;
while ( end->next != NULL )
{
  end = end->next;
}

listnode *curnode = head->next;

 

while ( curnode != end )
{
  // 将curnode从链表中删除
  head->next = curnode->next;

 

  //将curnode插入到end后面
  curnode->next = end->next;
  end->next = curnode;

 

  curnode = head->next; 
}

 

}
// 判断链表中是否存在着环
bool Mylist::HasaCycle ()
{
listnode *itr1 = NULL;
listnode *itr2 = NULL;

 

// 如果链表为空则返回false
if ( head == NULL || head != NULL && ( head->next == NULL )  )
{
  return false;
}

 

itr1 = head->next;
itr2 = itr1->next;
if ( itr2 == NULL )
{
  return false;
}

 

// 如果head-〉next指向了head ，或者itr1-〉head 指向了itr1，或者itr1-〉next指向了head,有环
if ( itr1 == head || itr2 == itr1 || itr2 == head )
{
  return true;
}

 

// head -> itr1 -> itr2 -> * 
while ( itr1 != NULL && itr2 != NULL && itr2->next != NULL  )
{
  if ( itr1 == itr2 || itr2->next == itr1 )  记号
  {
   return true;
  }
  itr1 = itr1->next;
  itr2 = itr2->next->next;
}

return false;
}

 

}

 

//================================

 

// test。cpp

 

#include <fstream>
#include <iostream>
#include <math.h>
#include <string>
#include <list>

 

#include "Mylist.h"

 

using namespace std;

 

//==================================================
// 获得data。txt文件中有多少行
int  GetTotalLineCount ()
{
ifstream ifs;
ifs.open ( "data.txt", ios::in );

 

int count  = 1 ;

 

//string p;

 

// while ( getline( ifs, p ) ) { ++count; }
char ch;

 

while ( ifs.get( ch ) )
{
  if ( ch == '\n')
  {
   ++count;
  }
}
ifs.close();
return count;
}
//================================================================
//计算正整数num的阶乘中有多少个0
const int FIVE = 5;

 

// 得到不大于 num的5的最大次方，如 num = 5 时返回 1， 26 时返回 2
int LowerNearestPow ( int num )
{
int powoffive = 1;

 

while ( pow ( FIVE, powoffive ) <= num )
{
  ++powoffive;
}

 

return powoffive;
}
// 考虑25，125， 625 等的情况
int GetZerosofXFactorial ( int num )
{
int lowernearestpow = LowerNearestPow ( num );

 

int zerocount = 0;
while (  lowernearestpow > 0 )
{
  zerocount += num / pow ( FIVE,  lowernearestpow ) ;
  --lowernearestpow;
}

return zerocount;
}
//=========================================================================
// 将10进制正整数num转化为2进制数

 

const int TWO = 2 ;

 

string  DecimalToBin ( unsigned int num )
{
if ( num == 0 )
{
  return "0";
}
string binform = "";

 

while ( num > 0 )
{
  binform.insert ( binform.begin(),  num % TWO + '0' );
  num /= TWO ;
}

 

return binform;

 

}
//=========================================================================
// 求一个整数数组的最大子列和
int MaxSubArraySum ( int *array, int size )
{
int sum = 0;

 

while ( size >= 0 )
{

 

  if ( array[size] > 0 )
  {
   sum += array[ size ];
  }

 

  else if ( array[size] < 0  )
  {
   if ( sum == 0 )  
   {
    sum = array[size];
   }
  }// end of else

 

  --size;

 

}// end of while

 

return sum;
}

 

//=========================================================================
void main ()
{
// int count = GetTotalLineCount ();
// cout << count << endl;

 

// while ( 1 )
// {
//  cout << " 请输入一个数，本程序将计算这个数的阶乘中有多少个0：" << endl;
//  int num;
//  cin >> num ;

 

//  cout << GetZerosofXFactorial ( num ) << endl;
// }

 

// while ( 1 )
// {
//  cout << " 请输入一个正整数，本程序将计算这个数的二进制形式：" << endl;

 

//  unsigned int num;
//  cin >> num ;

 

//  cout << DecimalToBin ( num ) << endl;

 

// }
// Mylist intlist;
// for ( int i=0; i<8; ++i )
// {
//  intlist.Insert ( i );
// }
// string str = intlist.GetEntireList ();
// cout << " 在逆置之前链表内容为：" << str << endl;

 

// intlist.Reverse();

 

// str = intlist.GetEntireList ();
// cout << " 在逆置之后链表内容为：" << str << endl;

 

// int sum[] = { -1, -2, 0, -4, -6, -1}; // -1
//{ 1, 2, -1, -4, 6, 1};   // 10
// int size = sizeof( sum ) / sizeof(int) - 1;
// cout << MaxSubArraySum ( sum , size ) << endl;
}

又n个人围成一圈,顺序排号.从第一个人开始报数(从1到m报数),凡报到m的人退出圈子,问最后留下的是原来第几号?链表:
#include<stdio.h>
#include<malloc.h>

typedef struct node{
int info;
struct node *next;
};
node *tbuildhlink(int n)  /*带头节点的尾插法*/
{
    node *head,*s,*p2;
    int i=1;
   
    head=(node *)malloc(sizeof(node));
    p2=head;
    while(i<=n)
    {
        s=(node *)malloc(sizeof(node));
        s->info=i;
        p2->next=s;
        p2=s;
        i++;
    }
    if(p2)  p2->next=head;
    return(head);
}
void Display(struct node* head)
{
    node *p;
    p=head->next;
    if(!p)
    {
        printf("\nthe hlink is empty!");
    }
    else
    {
        printf("\nthe value of the hlink is:\n");
        while(p!=head)
        {
            printf("%d--->",p->info);
            p=p->next;
        }
    }
    printf("^\n");
}
int delete_node(struct node *head,int  n,int m)
{
    int count=1,sum=n;
    struct node *p,*pre;
    pre=head;
    p=pre->next;
    while(sum>1)
    {
        if(p==head)
        {
            p=p->next;
        }           
        if(count<m)
        {
            pre=p;
            p=p->next;   
            count++;
        }
        if(count==m)
        {
            if(p==head)
            {
                p=p->next;
            }
            printf("第%d个人出列.\n",p->info);
            pre->next=p->next;
            free(p);
            p=pre->next;
            count=1;
            sum--;
        }
    }
    return(pre->info);
}
   
int main()
{
    node *head;
    int n,m;
   
    printf("输入n,m:");
    scanf("%d%d",&n,&m);
    head=tbuildhlink(n);
    Display(head);
    printf("最后剩下第%d个.\n",delete_node(head,n,m));
    return(0);