[大数据]王道数据结构代码——顺序表

#include<stdio.h>
#include<stdlib.h>
#define max 100
typedef struct{
	int *data;
	int maxsize,length;
} sql;
bool sqlinsert(sql &s,int i,int data)//线性表插入 ，时间复杂度O（n） 
{
	if(i<1||i>s.length+1)
	return false;
	if(s.length>=s.maxsize)
	return false;
	for(int j=s.length;j>=i;j--)
	s.data[j]=s.data[j+1];
	s.data[i-1]=data;//数组下标从0开始 
	s.length++;
	return true;
}
bool delesql(sql &s,int i,int &data)//线性表删除 ，时间复杂度O（n） 
{
		if(i<1||i>s.length+1)
			return false;
		data=s.data[i-1];
		for(int j=i;j<s.length;j++)
		{
			s.data[j-1]=s.data[j];
		}
		s.length--;
		return true;	
}
int locateElem(sql s,int data)//线性表查找（顺序查找） ，时间复杂度O（n） 
{
	for(int i=0;i<=s.length;i++)
	{
		if(s.data[i]==data)
		return i+1;
		return 0;
	}
 } 
 
int dele_elem(sql &s,int data)//删除顺序表中的最小值，并返回 最小值 
 {
 	if(s.length==0)
 	return -1;
 	
		int min=s.data[0];
		int pos=0;
		for(int i=1;i<=s.length;i++)
		{
			if(s.data[i]<min)
			{
				min=s.data[i];
				pos=i;	
			}
		
		}
		s.data[pos]=s.data[s.length-1];
		s.length--;
		return min;
  } 
  
void revList(sql &s)//线性表逆转，只用扫描线性表长度的一半
//s.length 是实际大小，从1开始。i是下标，从0开始 
{
int temp;
for(int i=0;i<s.length/2;i++)
{
	temp=s.data[i];
	s.data[i]=s.data[s.length-1-i];
	s.data[s.length-1-i]=temp;
	}	
	
}

bool delelemA(sql &s,int x){//删除线性表中值为x的元素 
	int data=0;
	for(int i=0;i<s.length;i++)
	{
		if(s.data[i]!=x)//将线性表s中不为x的元素存入表中，值为x的元素跳过。 
		{
			s.data[data]=s.data[i];
			data++;
		}
	}
	return true;
}

bool delelemB(sql &s,int a,int b){//删除线性表中值在区间（a,b）中的元素 
	if(a>b)
	return false;
	if(s.length==0)
	return false;
	
	int data=0;
	for(int i=0;i<s.length;i++)
	{
		if(s.data[i]<=a||s.data[i]>=b)//将线性表s中不在区间（a,b）的元素存入表中，在区间（a,b）的元素跳过。 
		{
			s.data[data]=s.data[i];
			data++;
		}
	}
	s.length=data;
	return true;
}
bool delelemC(sql &s,int a,int b){//删除线性表中值在区间（a,b）中的元素 （王道操作） 
	if(a>=b)
	return false;
	if(s.length==0)
	return false;
	int i,j;
	for(i=0;i<s.length&&s.data[i]<a;i++)
		if(i>=s.length)
			return false;
	for(j=i;j<s.length&&s.data[j]<b;j++)
	
	for(;j<s.length;i++,j++)
	s.data[i]=s.data[j];
	s.length=i;
}
bool deleListSame(sql &s){//删除有序线性表中重复的元素，只保留一个 
	if(s.length==0)
		return false;
	int i,j; 
	for(i=0,j=1;j<s.length;j++)//for example:1 2 2 3 3 4 4 5
	//i用来存放不同元素，j用来扫描顺序表。 
 	{
		if(s.data[i]!=s.data[j])
			s.data[++i]=s.data[j];
	}
	s.length=++i;
	return true;
	
}

int removeSame1(sql &B) {			//无序表删除重复元素	
	int i, j = 0, k;
 
	for (i = 1; i < B.length; ++i) {
		k = 0;
		while (k <= j && B.data[k] != B.data[i])
			k++;
		if (k > j)                       //表示B.data[i]与B.data[0...j]中元素都不相同
			B.data[++j] = B.data[i];
	}
	B.length = j+1;
 
	return B.length;
}

bool addlist(sql a,sql b,sql &c){//两个有序表a,b 合并成一个新的有序表 c
	//本算法非常典型，需要牢固掌握
	 
	if(a.length=b.length>=c.maxsize)
	return false;
	int i,j,k;
	//i负责a表，j负责b表，k负责c表。 
	while(i<a.length&&j<b.length)
	{
		//谁小谁的值给新表，然后下标后移 
		if(a.data[i]>b.data[j])
		{
			c.data[k]=b.data[j];
			k++;
			j++;
		}
		else
		{
			c.data[k]=a.data[i];
			k++;
			i++;
		}
		
	}
	while(i<a.length)
	{
		c.data[k]=a.data[i];
			k++;
			i++;
		
	}
	while(j<b.length)
	{
			c.data[k]=b.data[j];
			k++;
			j++;
	}
	return true;
}


void exchangearr(sql &a,int left,int right){//交换数组中前n个元素和后m个元素
//left是前n个元素，right是后m个元素 
	if(left>=right||right>=a.maxsize)
		return ;
	int temp;
	int mid=(left+right)/2;
	for(int i=0;i<mid;i++)
	{
		a.data[i]=temp;
		a.data[i]=a.data[a.length-1-i];
		a.data[a.length-1-i]=temp;
	}
} 
void exchange(sql &s,int left,int right)
{
	exchangearr(s,0,right-1);
	exchangearr(s,right,left+right-1);
}

void exchange2_1(sql &s,int a){//有序递增线性表，查找a的值 
	int i,j,flag=-1;
	for(i=0;i<s.length;i++){
		if(s.data[i]==a)//找到a则与后面的元素交换 ，时间复杂度为O(n) 
		{
			int temp=s.data[i+1];
			s.data[i+1]=s.data[i];
			s.data[i]=temp;
			return;
		}
		if(s.data[i]<a&&s.data[i+1]>a){//如果找不到a，将a插入到 线性表中，使之有序 
			flag=i;
			break; 
		}
		if(s.data[s.length-1]<a){
			s.data[s.length]=a;
			s.length++;
			return;
		} 		
	}

	if(flag!=-1)
	{
		for(j=s.length;j>flag;j--){
			s.data[j]=s.data[j-1];
		}
		s.data[j+1]=a;
		s.length++;
	}
	
} 




void exchange2_2(sql &s,int a){//有序递增线性表，查找a的值 

int low=0,high=s.length-1,mid;//使用折半查找的方法,时间复杂度为O(log2n)
while(low<high) 
{
	mid=(low+high)/2;
	if(s.data[mid]==a)
		break;
	else if(s.data[mid]<a)
		low=mid+1;
	else
		high=mid-1;
}
if(s.data[mid]==a&&mid!=s.length-1)//找到元素，与后面的元素进行交换 
{
		int temp=s.data[mid];
		s.data[mid]=s.data[mid+1];
		s.data[mid+1]=temp;
}
if(low>high)
{
	for(int i=s.length-1;i>high;i--)
	{
		s.data[i+1]=s.data[i];
		s.data[i+1]=a;
		s.length++;
	}
 } 
}



void revergeList1(sql &s,int a,int b){//逆转线性表
 
	int i,temp;
	for(int i=0;i<(b-a)/2;i++)//从两头往中间逆转 时间复杂度为(n) 
	{
		s.data[a+i]=temp;
		s.data[a+i]=s.data[b-i];
		s.data[b-i]=temp;
	 } 
	
}
void converse(sql &s,int a,int b){//revergeList操作函数 如： abcdefgh 逆转前3位 
	revergeList1(s,0,a-1);									//cbadefgh 
	revergeList1(s,a,b-1);									//cbahgfed
	revergeList1(s,0,b-1);									//defghabc
} 

void revergeList2(sql &s,int a,int b){//逆转线性表

sql *aa;//开辟一个新结构体 
aa.length=a;//结构体大小为a，用来储存前s结构体中的a个数 
for(int i=0;i<a;i++){ 
	aa.data[i]=s.data[i];
}
for(int j=0;j<s.length-a;j++){//将后b个数向前移a位 
	s.data[j]=s.data[j+a];	
}
for(int k=0;k<a;k++){//将后b个数向前移a位 
	s.data[b+k]=aa.data[k];	
}

}

int main()
{
	int a=10;
	printf("%d\n",max);
	
	return 0; 
}