排序及查找方法

排序及查找方法

1>某人在某个市场某个商家买了某台电脑,请用你熟悉的计算机语言表达出里面的关系.

其中有商家类，买家类，商品类。还要有买方法，卖方法。

2>一个完整的单例模式

3>曹操南下攻打刘备，刘备派关羽守锦州，关羽派张飞去守城门。刘备又派诸葛亮去向孙权求援。孙权派兵攻打曹操！

请画出UML图

2006年12月中兴在我们学校的笔试,最后的大题</P>

(其实这些大公司的笔试不难,也不就是如此,只要学一下数据结构就可以搞定!)

排序及查找方法

#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

finding\n 3: use directness intsert method sort\n

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); 2:use half method 4:use bubble up

排序及查找方法

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. 假设执行语句S的时间为O(1)，则执行下列程序短的时间为（） for(i=1;i<=n;i++)

for(j=I;j<=n;j++)

S;

A. O(n) B. O(n2) C. O(n*i) D. O(n+1)

2. 二位数组A[10…20，5…10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的地址是（）

A. 1208 B. 1212 C. 1368 D. 1364

3. 设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能得出栈序列是（） A. 1，2，3，4，5，6 B. 2，1，3，4，5，6 C. 3，4，2，1，5，6 D. 4，3，2，1，5，6 4. 设有98个已排序列元素，采用二分法查 似乎不难，可我还没找到。

头几天参加了中兴的笔试，做的不好，勉强是个合格，就这么黄了。

依稀记得几道题，公共题50分，C++和JAVA二选一50分。 其实一直就在用C，一看没有C心里还霍霍的，我当然选的C++ …… 此处隐藏：6244字，全部文档内容请下载后查看。喜欢就下载吧 ……