4-1.cpp

一些数据结构的源码

#include <stdio.h>
#include<malloc.h>
#define list_init_size 100
typedef struct
{
	int * elem;
	int length;
}sstable;

void Initlist_seq(sstable &l)
{
	int n;
	l.elem=(int*) malloc(list_init_size*sizeof(int));
	if(!l.elem) printf("存储分配失败！");
	l.length=0;
	printf("请输入你要输入数据的个数！\n");
	scanf("%d",&n);
	printf("请输入数据:\n");
	l.length=n;
	for(int i=1;i<=n;i++)
	
		scanf("%d",&l.elem[i]);
}

void sort_seq(sstable &l)
 { 
	int i,j,t;
    for(i=1;i<=l.length;i++)
     for(j=i+1;j<=l.length;j++)
	  if(l.elem[j]<l.elem[i])
	  {
		  t=l.elem[i];
		  l.elem[i]=l.elem[j];
		  l.elem[j]=t;
	  }
  printf("排序后线性表各元素为：\n");
  for(i=1;i<=l.length;i++)
   {printf("%d",l.elem[i]);
    printf(" ");
   } 
  printf("\n");
}

void search_seq(sstable s,int e)
{
	int i=s.length;
    int j=1;
	while(i)
	{
		if(s.elem[i]==e&&i!=0)
		{
			printf("是第""%d""个数！",i);
			printf("\n");
			break;
		}
    	else if(s.elem[i]!=e&&i==1)
			printf("查无此数！\n");
		i--;
		j++;
	}
	printf("查找次数为：""%d",j);
	printf("\n");
}

void search_bin(sstable s,int e)
{
	int low,high,mid;
	low=1;high=s.length;
	int j=1;
	while(1)
	{
		if(low<=high)
		{	
			mid=(low+high)/2;
		    if(s.elem[mid]==e)
			{
				printf("是第""%d""个数！",mid);
				printf("\n");
			    break;
			}
			else if(s.elem[mid]>e) high=mid-1;
		    else low=mid+1;
		}
		if(low>high)
		{
			printf("查无此数！\n");
			break;
		}
		j++;
	}
    printf("查找次数为：""%d",j);
	printf("\n");
}
void main()
{
	sstable s;
	int e;
	Initlist_seq(s);
	sort_seq(s);
	int a;
	while(1)
	{
		printf("请输入要执行的操作：1为顺序查找，2为折半查找，0为退出\n");
		scanf("%d",&a);
		if(a==1)
		{
			printf("请输入要查找的数：\n");
	        scanf("%d",&e);
	        printf("顺序查找此数的结果为：\n");	
			search_seq(s,e);
		}
		else if(a==2)
		{
			printf("请输入要查找的数：\n");
	        scanf("%d",&e);
	        printf("折半查找此数的结果为：\n");
	        search_bin(s,e);
		}
		else if(a==0)break;
	}
}