[数据结构与算法]数据结构(基于顺序表基本操作的算法设计)

.cpp

#include"SqList.h"
#include<Stdio.h>
void main()
{
	int i,k;ElemType e;
	SqList L;
	InitList(L);

	InsElem(L,2,1);InsElem(L,3,2);												//插入数据
	InsElem(L,6,3);InsElem(L,4,4);	
	InsElem(L,5,5);InsElem(L,9,6);
	InsElem(L,1,7);InsElem(L,7,8);
	InsElem(L,8,9);InsElem(L,7,10);
	InsElem(L,-6,11);InsElem(L,-8,12);	

	printf("初始线性表为:");DispList(L);

	Swapmaxmin(L);												//最大值和最小值交换位置
	printf("最大值和最小值交换后的线性表为:");DispList(L);


	i=1;k=2;													//删除自第二个元素开始的k个元素
	Deletek(L,i,k);
	printf("删除自第%d个元素开始的%d个元素后的线性表为:",i,k);DispList(L);

	Move(L);													//奇数在前偶数在后进行交换
	printf("奇数在前偶数在后交换后线性表为:");DispList(L);
	

	e=7;														//删除所有为e的元素
	Deletex(L,e);
	printf("删除所有元素为%d后的线性表为:",e);DispList(L);

														
	Deleteminus(L);													//删除所有为负整数的元素
	printf("删除所有为负整数后的线性表为:");DispList(L);

	DestroyList(L);
	printf("-----------------------------------------------------------------------------------------------------\n");

	SqList A;SqList B;SqList C;

	InitList(A);
	InsElem(A,1,1);InsElem(A,2,2);												//向A表插入数据
	InsElem(A,3,3);InsElem(A,4,4);	
	printf("A表元素:");DispList(A);

	InitList(B);
	InsElem(B,3,1);InsElem(B,5,2);												//向B表插入数据
	InsElem(B,7,3);
	printf("B表元素:");DispList(B);

	InitList(C);																//归并后C表数据
	Merge(A,B,C);
	printf("C表元素:");DispList(C);

	DestroyList(A);DestroyList(B);DestroyList(C);								//销毁表A,B,C
	printf("-----------------------------------------------------------------------------------------------------\n");


	InitList(A);
	InsElem(A,1,1);InsElem(A,2,2);												//向A表插入数据
	InsElem(A,3,3);InsElem(A,4,4);	
	printf("A表元素:");DispList(A);

	InitList(B);
	InsElem(B,3,1);InsElem(B,5,2);												//向B表插入数据
	InsElem(B,7,3);
	printf("B表元素:");DispList(B);

	InitList(C);																//C表数据为A,B表中的公共数据
	Commelem(A,B,C);
	printf("C表元素:");DispList(C);

	DestroyList(A);DestroyList(B);DestroyList(C);								//销毁表A,B,C
	printf("-----------------------------------------------------------------------------------------------------\n");


	InitList(A);
	InsElem(A,1,1);InsElem(A,2,2);												//向A表插入数据
	InsElem(A,3,3);InsElem(A,4,4);	
	printf("A表元素:");DispList(A);

	InitList(B);
	InsElem(B,4,1);InsElem(B,5,2);												//向B表插入数据
	InsElem(B,7,3);InsElem(B,9,4);
	printf("B表元素:");DispList(B);
	
	k=4;
	Topk(A,B,k,e);
	printf("第%d小的元素为:%d\n",k,e);

}

SqList.h

#include<stdio.h>
#include<math.h>
#define MaxSize 100    //存放最大空间
#define INF 32767	   //最大元素值
typedef int ElemType;  //int类型
typedef struct
{
	ElemType data[MaxSize]; //存放数据表的元素
	int length;             //顺序表的实际长度
}SqList;                   //顺序表类型   重命名

void InitList(SqList &L)   //初始化
{
	L.length=0;
}

int InsElem(SqList &L,ElemType x,int i)  //在元素i（即物理下标i-1）处插入元素
{
	int j;
	if(i<1||i>L.length+1)
		return 0;
	for(j=L.length;j>i;j--)
		L.data[j]=L.data[j-1];
	L.data[i-1]=x;
	L.length++;
	return 1;
}

void DispList(SqList L)//输出
{
	int i;
	for(i=0;i<L.length;i++)
		printf("%d  ",L.data[i]);
	printf("\n");
}

void swap(ElemType &x,ElemType &y)//交换函数
{
	ElemType tmp=x;
	x=y;
	y=tmp;
}

void Swapmaxmin(SqList &L)//最大值和最小值交换位置
{
	int i,maxi,mini;
	maxi=mini=0;
	for(i=1;i<L.length;i++)
		if(L.data[i]>L.data[maxi])
			maxi=i;
		else if(L.data[i]<L.data[mini])
			mini=i;
		swap(L.data[maxi],L.data[mini]);
}

int Deletek(SqList &L,int i,int k)//删除自第二个元素开始的k个元素
{
	int j;
	if(i<1||k<1||i+k-1>L.length)
		return 0;
	for(j=i+k-1;j<L.length;j++)
		L.data[j-k]=L.data[j];
	L.length-=k;
	return 1;
}


void Move(SqList &L)			//奇数在前偶数在后进行交换
{
	int i=0,j=L.length-1;
	while(i<j)
	{
		while(L.data[i]%2==1) i++;
		while(L.data[j]%2==0) j--;
		if(i<j)
		swap(L.data[i],L.data[j]);
	}
}


void Deletex(SqList &L,ElemType x)//删除所有为e的元素
{
	int i,k=0;
	for(i=0;i<L.length;i++)
	{
		if(L.data[i]!=x)
		{
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
}


void Deleteminus(SqList &L)//删除所有为负整数的元素
{
	int i,k=0;
	for(i=0;i<L.length;i++)
	{
		if(L.data[i]>=0)
		{
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
}

void DestroyList(SqList L)//销毁表
{}


void Merge(SqList A,SqList B,SqList &C)//二路归并算法，将两个递增有序的顺序表A,B归并到递增有序的顺序表C中
{

	int i=0,j=0,k=0;
	while(i<A.length&&j<B.length)
	{
		if(A.data[i]<B.data[j])
		{
			C.data[k]=A.data[i];
			i++;k++;
		}
		else
		{
			C.data[k]=B.data[j];
			j++;k++;
		}
	}
	while(i<A.length)
	{
		C.data[k]=A.data[i];
		i++;k++;
	}
	while(j<B.length)
	{
		C.data[k]=B.data[j];
		j++;k++;
	}
	C.length=k;
}


void Commelem(SqList A,SqList B,SqList &C)//将A,B表中的公共数据复制到C表
{
	int i=0,j=0,k=0;
	while(i<A.length&&j<B.length)
	{
		if(A.data[i]<B.data[j])
			i++;
		else if(A.data[i]>B.data[j])
			j++;
		else
		{
			C.data[k]=A.data[i];
			i++;j++;k++;
		}
	}
	
	C.length=k;
}

int Topk(SqList A,SqList B,int k,ElemType &e)//求第k小的元素
{
	int i=0,j=0;
	if(k<1||k>A.length+B.length)
		return 0;
	while(true)
	{
		k--;
		int x=(i<A.length?A.data[i]:INF);
		int y=(j<B.length?B.data[j]:INF);

		if(x<y)
		{
			if(k==0)
			{
				e=x;
				return 1;
			}
			i++;
		}
		else
		{
			if(k==0)
			{
				e=y;
				return 1;
			}
			j++;
		}
	}
}