青海大学软件技术工程实验七、八、九、十综合实验.doc

软件基础基础实验报告
系别：机械工程学院 班级：11材料科学与工程
学号：++++++++ 姓名：+++++++++
实验环境：Turbo c++3.0（vc6.0）
实验七、八、九、十综合实验
实验名称：实验七 线性表的查找算法
实验目的：
（1） 掌握线性表的顺序查找算法
（2） 掌握有序表的折半查找算法
实验内容：
1、 在顺序存储的长度为n的线性表中顺序查找元素x在表中的下标。备注：需要用到的算法是：serch( )
2、 在头指针为head的线性链表中顺序查找元素x的存储序号。
备注：需要用到的算法是：lserch( )
3、 在顺序存储的长度为n的线性表中对分查找元素x在表中的下标。
备注：需要用到的算法是：bserch()
实验名称：实验八 线性表的交换类排序算法
实验目的：
（1） 掌握冒泡排序算法
（2） 掌握快速排序算法★
实验内容：
1、 对无序序列P（1：n）进行冒泡排序。
备注：需要用到的算法是：bubsort( )
2、 对无序序列P（m：n）进行快速排序。
备注：需要用到的算法是：qkserch( )
实验名称：实验九 线性表的插入类排序算法
实验目的：
（1） 掌握简单插入排序算法
（2） 掌握希尔排序算法★
实验内容：
1、 对无序序列P（1：n）进行插入排序。
备注：需要用到的算法是：insort( )
2、 对无序序列P（1：n）进行希尔排序。
备注：需要用到的算法是：shlsort( )
实验名称：实验十 线性表的选择类排序算法
实验目的：
（1） 掌握简单选择排序算法
（2） 了解堆排序算法★
实验内容：
1、 对无序序列P（1：n）进行简单选择排序。
备注：需要用到的算法是：selsort( )

程序代码：(请写上详细的程序注释！)
//菜单函数、
#include"stdlib.h"
#include"stdio.h"
#include"string.h"

void menu()
{
system("cls");system("color 49");
printf("------线性表综合实验------\n");
printf("------请选择要进行的操作------\n");//先加入菜单项
printf("\n****** 1 建表******");
printf("\n****** 2 插入******");
printf("\n****** 3 删除******");
printf("\n****** 4 排序******");
printf("\n****** 5 查找******");
printf("\n****** 6 输出******");
printf("\n****** 7 退出******\n");
}
void input(int *v,int *n)/*输入函数*/
{
int i;
printf("请输入数据：\n");
for (i=0;i<*n;i++)
scanf ("%d",v+i);//利用指针!
}
void output(int *v,int *n)/*输出函数*/
{
int i;
printf("线性表中的元素是：\n");
for (i=0;i<*n;i++)
printf("%d",*(v+i));
}
int *initsl(int m,int *n) /*建表*/
{
int *v;
v=(int *)malloc(m*sizeof(int));
*n=0;
return v;
}
void insl(int *v,int m,int *n,int i,int b)/*插入函数*/
{
int j;
if(*n==m)
{
printf("list overflow!");
return;
}
if(i>*n-1)i=*n;
if(i<1)i=1;
for(j=*n;j>=i;j--)
v[j]=v[j-1];
v[i-1]=b;
*n=*n+1;
return;
}
void delsl(int *v,int m,int *n,int i) /*删除函数*/
{
int j;
if(*n==0)
{
printf("the list is empty!");
return;
}
if(i<1||i>*n)
{
printf("the node is not !");
return;
}
for(j=i;j<=*n;j++)
v[j-1]=v[j];
*n=*n-1;
return;
}
void bubsort(int v[],int n)//冒泡排序
{
int m,k,j,i;int d;k=0;m=n-1;
while (k<m) /*子表未空*/
{
j=m-1;m=0;
for(i=k;i>=j;i++) /*从前往后扫描*/
if (v[i]>v[i+1]) /*发现逆序进行交换*/
{
d=v[i];v[i]=v[i+1];v[i+1]=d;m=i;
}
j=k+1;k=0;
for (i=m;i>=j;i--) /*从后往前扫描*/
if (v[i-1] >v[i]) /*发现逆序进行交换*/
{
d=v[i];v[i]=v[i-1];v[i-1]=d;k=i;
}
}
return;
}
int split(int p[],int m,int n)//分割算法
{
/*返回分界线位置*/
int i,j,k,u,t;
i=m; j=n; k=(i+j)/2;
if ((p[i]>=p[j])&&(p[j]>=p[k]))
u=j; /*选取一个元素*/
else if ((p[i]>=p[k])&&(p[k]>=p[j])) u=k;
else u=i;
t=p[u]; p[u]=p[i];
while (i!=j)
{ while ((i<j)&&(p[j]>=t)) j=j-1;
if (i<j)
{ p[i]=p[j]; i=i+1;}
while ((i<j)&&(p[i]<=t)) i=i+1;
if (i<j);
{ p[j]=p[i]; j=j-1;}
}
p[i]=t;
return(i);

}
void qksort1(int p[],int m,int n)//快速排序
{
int i;if (n>m) /*子表不空*/
{
i=split(p,m,n); /*分割*/
qksort1(p,m,i-1);/*对前子表进行快速排序*/
qksort1(p,i+1,n);/*对后子表进行快速排序*/
}
return;
}
void insort(int p[],int n)//简单插入排序
{
int j,k;int t;
for (j=1;j<n;j++)
{
t=p[j]; k=j-1;
while ((k>=0)&&(p[k]>t))
{
p[k+1]=p[k];k=k-1;
}
p[k+1]=t;
}
return;
}
void shlsort(int p[],int n)//希尔排序
{
int h,j,i;int t;
h=n/2;
while (h>0)
{
for (j=h;j<=n-1;j++)
{
t=p[j];i=j-h;
while ((i>=0)&&(p[i]>t))
{
p[i+h]=p[i]; i=i-h;
}
p[i+h]=t;
}
h=h/2;
}
return;
}

/*查找函数*/
int serch(int v[],int n,int x) //线性表在顺序存储结构下的顺序查找

{
int k;
k=0;
while ((k<n)&&(v[k]!=x)) k=k+1;
if (k==n) k=-1;
return(k);
}

int bserch(int v[],int n,int x) //有序线性表在顺序存储结构下的对分查找
{
int i,j,k;
i=1; j=n;
while (i<=j)
{
k=(i+j)/2;
if (v[k-1]==x)
return(k-1);
if (v[k-1]>x)
j=k-1;
else i=k+1;
}
return(-1);
}

//主函数
void main()
{
int *v=NULL,*n=NULL,m,i,b,k,xz,x;
char cc;
n=(int *)malloc(sizeof (int));
menu();
scanf("%d",&xz);
while(1)
{
switch(xz)
{
case 1:
printf("请输入线性表的空间大小：\n");
scanf("%d",&m);
v=initsl(m,n);
printf("请输入线性表的实际长度：\n");
scanf("%d",n);
input(v,n);
break;

//选中菜单项1后发生的事件（调用函数），后面的以此类推````````
case 2:
cc='y';
while(cc=='Y'||cc=='y')
{
if(*n==m){printf("list overfiow!");break;}
printf("\n请输入要插入的位置i和元素b:");
scanf("%d%d",&i,&b);
insl(v,m,n,i,b);
getchar();
printf("是否要继续插入?（y or n）");
cc=getchar();
getchar();
}
break;
case 3:
printf("\n请输入要删除元素的位置:");
scanf("%d",&i);
delsl(v,m,n,i);
break;

case 4:
if(*n==0)
{
printf("List is empty!");
return;
}
printf("冒泡排序，请输入1\n");
printf("快速排序，请输入2\n");
printf("插入排序，请输入3\n");
printf("希尔排序，请输入4\n");
scanf("%d",&i);
while (1)
{

switch (i)
{
case 1:bubsort(v,*n); break;
case 2:qksort1(v,0,*n-1);break;
case 3:insort(v,*n); break;
case 4:shlsort(v,*n); break;

}

}
break;

case 5:

if(*n==0)
{
printf("List is empty!");
return;
}
printf("线性表在顺序存储结构下的顺序查找，请输入1\n");
printf("有序线性表在顺序存储结构下的对分查找，请输入2\n");
scanf("%d",&i);
switch (i)
{
case 1:
{
printf("请输入要查找的元素X=\n");
scanf("%d",&x);
k=serch(v,*n,x);
}
break;
case 2:
{
printf("请输入要查找的元素X=\n");
scanf("%d",&x);
k=bserch(v,*n,x);
}
break;
}
if (k==-1){printf("\n你所需要的数据已找到!");}
else printf("\n你所需要的数据不存在!");
break;

case 6:
output(v,n);
system("pause");
break ;
default:
printf("对不起，你输入的数据有误!\n请重新输入!\n");

break;
}

if(xz==7)
{
printf("\n谢谢使用!");
break ;
}

menu();
scanf("%d",&xz);
}
}