caozuo.cpp

此乃是数据结构的线性表操作全实现源代码 用现实的

Status InitList(SqList &L)   //构造空的线性表
{
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE*
		sizeof(ElemType));        //申请内存空间
	if( !L.elem )exit(OVERFLOW);  //存储分配失败
	L.length = 0;                 //空表长度为0  
	L.listsize = LIST_INIT_SIZE;  //初始存储容量
	return OK;
}//InitList_Sq


Status ListInsert(SqList &L, int i, ElemType e)
{//在顺序表L中第i个位置之前插入新的元素e
 //i的合法值为1<=i<=ListLength_Sq(L)+1
	ElemType *p,*q;
	if( i < 1  ||  i > L.length + 1) return ERROR; 
	if( L.length >= L.listsize )
	{                      //当前存储空间已满，增加分配
		ElemType *newbase;		
		newbase = ( ElemType *)realloc( L.elem, 
			(L.listsize+LISTINCREMENT )*sizeof(ElemType));
		if(!newbase)exit(OVERFLOW);     //存储分配失败
		L.elem = newbase;               //新基址
		L.listsize += LISTINCREMENT;    //增加存储容量
	}
	q = L.elem + i - 1;                  //q为插入位置
	for( p = L.elem + L.length - 1 ;  p >= q; --p )
		*(p + 1) = *p;                  //插入位置及之后的元素右移
	*q = e;                             //插如e
	++L.length;                         //表长增加一
	return OK;
}


Status ListDelete(SqList &L,int i,ElemType &e)
{//在顺序线性表L中删除第i个元素，并用e返回其值
 //i的合法值为1<=i<=L.length
	ElemType *p, *q;
	if ((i<1) || (i>L.length)) return ERROR;//i值不合法
	p = &(L.elem[i-1]);                  //p为被删除元素的位置
	e = *p;                              //被删除元素的值赋给e
	q = L.elem + L.length - 1;           //表尾元素的位置
	for(p; p < q; ++p)   *(p) = *(p+1);  //被删除元素之后的元素左移
	--L.length;                          //表长减1
	return OK;
}

Status Visit(SqList L)//输出线性表元素
{
	ElemType i;
	printf("线性表为:");
	for (i = 0; i < L.length; i++)
		printf("%4d",L.elem[i]);
	printf("\n");
	return OK;
}

Status Find (SqList L, ElemType e)//查找元素
{
	ElemType i;
	for(i=0;i<L.length;i++)
		if(L.elem[i]==e)break;    //找到元素，跳出循环
	if(i<L.length)
		return i+1;               //元素位置为i+1
	else return ERROR;
}



Status DestroyList(SqList &L)//销毁线性表L
{
	free(L.elem);
	return OK;
}

Status ClearList(SqList &L)	//清空线性表L
{
	L.length = 0;
	return OK;
}

Status  Regular(SqList L)
{
	//元素是否对称
	ElemType i,j;
	ElemType flag = 0;
	if (L.length%2 == 0)  j = L.length/2;    //长度为偶数
	if (L.length%2 == 1)  j = (L.length+1)/2;//长度为奇数
	for (i = 0; i < j; i++)
	{
		if(L.elem[i] != L.elem[L.length-1-i]){
			flag = 1;  break; }             //对称的两数不相等                  //跳出循环
	}
	if (flag == 0)
		printf("顺序表是对称的!!\n");
	if (flag == 1)
		printf("顺序表不对称!!\n");
	return OK;
}

Status Paixu(SqList &L)
{
	//冒泡法进行升序排序
	ElemType i,j,t;
	for(j = 0 ; j < L.length; j++)
	{
		for( i = j+1; i < L.length ; i ++)	
			if( L.elem[j] > L.elem[i] )	
			{
				t=L.elem[j];
				L.elem[j] = L.elem[i];
				L.elem[i] = t;
			}
	}
	return OK;
}


Status Jiou(SqList &L)
{
	//奇数放前，偶数放后排序
	ElemType i,j;
	ElemType *p;
	ElemType count=0;
	for (i = 0; i < L.length; i++)
	{
		if(count>=L.length-1) break;//判断次数为长度减1
		if(L.elem[i]%2==0)          //为偶数，则放表尾
		{
			j=L.elem[i];            //printf("%d",j);
			for(p = L.elem+i; p < &(L.elem[L.length-1]);p++)  	
				*(p) = *(p+1);
			*p = j;
			count++;   i--;							
		}
		else count ++;
	}
	Visit(L);
	return OK;
}

Status Build(SqList &L)
{
	L.length = 0;                 //清空数据
	int i,n,e;
	printf("输入顺序线性表长度:");//输入数据个数
	scanf("%d",&n);
	printf("输入数据元素:\n");    //输入数据元素
	for(i = 1; i <= n; i++)
	{
		scanf("%d",&e);
		ListInsert(L, i,  e);     //循环插入元素
	}
	Visit(L);
	return OK;
}




Status Handle(SqList &L)
{
	//存在顺序表后的插入，删除，查找的选择函数
	int num,i,e;
	 
	char c='y';
	while (c=='y')//选择操作
	{
		printf("***************************\n");
		printf("1.插入元素:\n");
		printf("2.删除元素:\n");
		printf("3.查找元素:\n");
		printf("4.元素是否对称：\n");
		printf("5.按升序排序\n");
		printf("6.奇数放前，偶数放后排序\n");
		printf("7.清空顺序表并重建:\n");
		printf("****************************\n");
		printf("请选择需要的操作:");
		scanf("%d",&num);
		if(num!=1 && num!=2 && num!=3 && num!=4 
			&& num!=5 && num!=6 && num!=7 )
		{	
			printf("输入错误，请重新输入:\n");
			scanf("%d",&num);
		}
		switch(num)//输入要选择的操作
		{
		case 1:                   //插入元素
			printf("输入插入的位置以及插入元素:\n");
			scanf("%d%d",&i,&e);
			ListInsert(L, i, e);  //插入操作
			Visit(L);             //输出插入后的线性表
			break;
		case 2:                   //删除元素
			printf("输入要删除数据的位置：\n");
			scanf("%d",&i);
			if(ListDelete(L,i,e)==0)
				printf("输入的数值不合法!!!\n");
			else
			{
				printf("删除的元素为%d\n",e);
				Visit(L);        //输出删除操作后的线性表
			}
			break;
		case 3:                  //查找元素
			printf("输入要查找的元素：\n");
			scanf("%d",&e);
			i = Find(L,e);
			if(i)  printf("所查找元素的位置为%d",i);
			else   printf("没查找到元素!!\n");
			break;
		case 4:                  //判断对称
			Regular(L);
			break;
		case 5:                  //排序
			Paixu(L);
			Visit(L);
			break;
		case 6:                  //奇数前，偶数后
			Jiou(L);
			break;
		case 7:                  //清空，重建表
			Build(L);
			break;
		}
		printf("继续操作(y/n): \n");
		scanf("%s",&c);
		if( c != 'y' && c != 'n' )
		{
			printf("请输入y or n 进行选择:\n");
			scanf("%s",&c);
		}
	}
	return OK;
}

Status MergeList(SqList La,SqList Lb, SqList &Lc)
{
	//两个线性表的合并，之前la和lb经过有序排列
	ElemType *pa,*pb,*pc;
	pa = La.elem; pb = Lb.elem;
	Lc.listsize = Lc.length = La.length + Lb.length;
	pc = Lc.elem = (ElemType*)malloc(Lc.listsize*
		sizeof(ElemType));      //为Lc申请地址
	if(!Lc.elem)exit(OVERFLOW); //分配失败
	while (pa<=La.elem+La.length-1 &&
		pb<=Lb.elem+Lb.length-1)
	{//La，Lb元素同时都未遍历完，进行此步操作
		if(*pa <= *pb) *pc++ = *pa++;
		else  *pc++ = *pb++;
	}
	while(pa<=La.elem+La.length-1) 
		*pc++ = *pa++;//La未遍历完，插入剩余元素
	while(pb<=Lb.elem+Lb.length-1)
		*pc++ = *pb++;//Lb未遍历完，插入剩余元素
	Visit(Lc);
	return OK;
}