天天看点
返回

线性表的顺序表示和实现-----两个集合的并集（无序，有序），线性表的就地逆置，两个线性表的比较大小，插入元素(O(1))， A 表中 删去既在 B 表中出现又在 C 表中出现的元素，

线性表的顺序表示和实现

线性表的顺序表示和实现-----两个集合的并集（无序，有序），线性表的就地逆置，两个线性表的比较大小，插入元素(O(1))， A 表中 删去既在 B 表中出现又在 C 表中出现的元素，

①集合A=AUB，无序的；

②A,B两个顺序表递增有序，执行C=AUB,算法时间复杂度要求为 O(n+m)(A,B这两个顺序表只允许遍历一次)；

③//实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,...,an)逆置为(an,...,a1)；

④//设A=(a1,...,an)和B=(b1,...,bn)均为顺序表。试写一个比较 A，B 大小的算法,依次比较 A,B 元素的值,如果一样则继续比较,如果不一样则比较完成。；

⑤//设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以 保持该表的有序性；

⑥已知 A，B 和 C 为三个递增有序的顺序表，现要求对 A 表作如下操作：

删去那些既在 B 表中出现又在 C 表中出现的元素。

试对顺序表编写实现上述操作的算法，并分析你的算法的 时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 

头文件

#pragma once//防止头文件被重复引用
//动态不定长顺序表

#define INIT_SIZE 10//顺序表的初始化大小

typedef struct SqList
{
	int *elem;//指向动态内存创建的内存，用于存储数据
	int length;//存放有效数据个数
	int listsize;//存放顺序表的总大小
}Sqlist,* PSqList;//PSqList为结构体类型指针

//初始化线性表
void InitSqlist(PSqList ps);

//在ps的pos位置处插入数据val
bool Insert(PSqList ps,int pos,int val);

//在ps中查找第一个key值,找到返回下标,失败返回-1
int Search(PSqList ps,int key);

//删除ps中的第一个key值
bool DeleteVal(PSqList ps,int key);

//删除ps中pos位置的值
bool DeletePosVal(PSqList ps,int pos);

//获取ps中pos位置的值
int GetElel(PSqList ps,int pos);

//将ps中pos位置的值设为newpos
bool SetElem(PSqList ps,int pos,int newval);

//获取有效数据个数
int GetLentgh(PSqList ps);

//判断ps是否为空
bool IsEmpty(PSqList ps);

//输出ps
void Show(PSqList ps);

//清空ps
void Clear(PSqList ps);

//销毁ps
void Destory(PSqList ps);

函数说明以及实现与顺序线性表的实现：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"SeqList.h"//引用本项目头文件

//初始化线性表
void InitSqlist(PSqList ps)
{
	assert(ps != NULL);
	if(ps == NULL)
	{
		printf("Init Error\n");
		return;
	}
	//-> 自带 *
	ps->elem = (int*)malloc(sizeof(int)*INIT_SIZE);//存放整型元素
	ps->length = 0;//初始化长度为0
	ps->listsize = INIT_SIZE;
}


//扩容，将总容量扩大为原来的2倍
static void Inc(PSqList ps)
{
	assert(ps != NULL);
	if(ps == NULL)
	{
		return;
	}
	ps->elem = (int*)realloc(ps->elem,sizeof(int)*INIT_SIZE*2);//realloc会把原来数据copy过来
	ps->listsize *= 2;
}

//判断ps是否已满,内部函数,不对外
static bool IsFull(PSqList ps)
{
	assert(ps != NULL);
	if(ps == NULL)
	{
		return false;
	}
	return ps->length == ps->listsize;//已满
}

//在ps的pos位置处插入数据val
//插入的数据必须在顺序表的最左边,且连续
bool Insert(PSqList ps,int pos,int val)//O(n)
{
	assert(ps != NULL);
	assert(ps != NULL);
	if(ps == NULL  || pos < 0 || pos > ps->length)
	{
		return false;
	}
	if(IsFull(ps))
	{
		Inc(ps);//如果满了，就扩容
	}
	for(int i = ps->length - 1;i >= pos;i--)
	{
		ps->elem[i+1] = ps->elem[i];
	}
	ps->elem[pos] = val;
	ps->length++;

	return true;
}

//在ps中查找第一个key值,找到返回下标,失败返回-1
int Search(PSqList ps,int key)
{
	assert(ps != NULL);
	if(ps == NULL)
	{
		return false;
	}
	int flag = -1;
	for(int i=0;i < ps->length;i++)
	{
		if(ps->elem[i] == key)
		{
			flag = i;  //找到了
			break;
		}		
	}
	return flag;
}

//删除ps中的第一个key值
bool DeleteVal(PSqList ps,int key)
{
	assert(ps != NULL);
	if(ps == NULL)
	{
		return false;
	}
	int index = Search(ps,key);

	return DeletePosVal(ps,index);
}

//删除ps中pos位置的值
bool DeletePosVal(PSqList ps,int pos)
{
	assert(ps != NULL);
	if(ps == NULL || pos > ps->length && pos < 0)
	{
		return false;
	}

	for(int i = pos;i + 1 < ps->length;i++)//将后面的数据往前移
	{
		ps->elem[i]=ps->elem[i+1];
	}
	ps->length --;

	return true;
}

//获取ps中pos位置的值
int GetElel(PSqList ps,int pos)
{
	assert(ps != NULL );
	if(ps == NULL && pos > ps->length && pos < 0 )
	{
		return -1;
	}
	return ps->elem[pos];
}

//将ps中pos位置的值设为newpos
bool SetElem(PSqList ps,int pos,int newval)
{
	assert(ps != NULL );
	if(ps == NULL && pos > ps->length && pos < 0 )
	{
		return false;
	}
	ps->elem[pos] = newval;
	return true;
}

//获取有效数据个数
int GetLentgh(PSqList ps)
{
	assert(ps != NULL );
	if(ps == NULL)
	{
		return 0;
	}
	return ps->length;
}

//判断ps是否为空
bool IsEmpty(PSqList ps)
{
	assert(ps != NULL );
	if(ps == NULL)
	{
		return false;
	}
	return ps->length == 0;
}

//输出ps
void Show(PSqList ps)
{
	assert(ps != NULL );
	if(ps == NULL && ps->length < 0)
	{
		return ;
	}
	for(int i = 0;i < ps->length;i++)
	{
		printf("%d ",ps->elem[i]);
	}
	printf("\n");
}

//清除数据
void  Clear(PSqList ps)
{
	assert(ps != NULL );
	if(ps == NULL)
	{
		return ;
	}
	ps->length = 0;
}

//销毁ps,回收内存
void Destory(PSqList ps)
{
	assert(ps != NULL );
	if(ps == NULL)
	{
		return ;
	}
	free(ps->elem);
	ps->elem = NULL;
	ps->length = 0;
	ps->listsize = 0;
}

主函数（所有函数都已经测试过）：

#include<stdio.h>
#include"SeqList.h"


//集合A=AUB，无序的
void Union_unsort(PSqList pA,PSqList pB)
{
	int value_a = 0;
	int Lenght_A = GetLentgh(pA);
	int Lenght_B = GetLentgh(pB);

	for(int i = 0;i < Lenght_B;i++)
	{
		value_a = GetElel(pB,i);
		if(-1 == Search(pA,value_a))
		{
			Insert(pA,Lenght_A,value_a);
		}
	}
	printf("\n");
}

//A,B两个顺序表递增有序，执行C=AUB,算法时间复杂度要求为 O(n+m)(A,B这两个顺序表只允许遍历一次)
void Union_Merge_sort(PSqList pA,PSqList pB,PSqList pC)
{
	
	int value_a = 0,value_b = 0;
	int Lenght_A = GetLentgh(pA);
	int Lenght_B = GetLentgh(pB);
	
	int i = 0,j = 0,k = 0;
	while (i < Lenght_A && j < Lenght_B)
	{
		value_a = GetElel(pA,i);
		value_b = GetElel(pB,j);
		if(value_a < value_b)
		{
			Insert(pC,k,value_a);
			i++;
		}
		else  if(value_a == value_b)
		{
			Insert(pC,k,value_a);
			i++;
			j++;
		}
		else
		{
			Insert(pC,k,value_b);
			j++;
		}
		k++;
	}
	//一个顺序表长度>另一个顺序表长度
	while (i < Lenght_A)
	{
		value_a = GetElel(pA,i);
		Insert(pC,k,value_a);
		i++,k++;
	}
	while (j < Lenght_B)
	{
		value_b = GetElel(pB,j);
		Insert(pC,k,value_b);
		j++,k++;
	}
}

void Swap_Int(int *a,int *b)
{
	int tmp = 0;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

//实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,...,an)逆置为(an,...,a1)。 
void Inversion(PSqList pA)
{
	int tmp = 0;
	int length_A = GetLentgh(pA);
	for(int i = 0,j = length_A - 1;i < length_A / 2;i++,j--)
	{
		Swap_Int(&pA->elem[i],&pA->elem[j]);
	}	
}

int Min_Int(int a,int b)
{
	return a < b ? a : b;
}

//设A=(a1,...,an)和B=(b1,...,bn)均为顺序表。试写一个比较 A，B 大小的算法,依次比较 A,B 元素的值,如果一样则继续比较,如果不一样则比较完成。 
int Compare(PSqList pA,PSqList pB)
{
	int Lenght_A=GetLentgh(pA);
	int Lenght_B=GetLentgh(pB);

	for(int i = 0;i < Min_Int(Lenght_A,Lenght_B);i++)
	{
		if(GetElel(pA,i) != GetElel(pB,i))
		{		
			return GetElel(pA,i) - GetElel(pB,i);//不相等返回较大的顺序表
		}
	}

	return Lenght_A - Lenght_B;//==0表示相等，大于0A大，反之B大
}


//设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 
int  Insert_Merge_SList(PSqList pA,int x)
{
	int i = 0;
	for(i = GetLentgh(pA) - 1;i >= 0;i--)
	{
		if(x >= GetElel(pA,i))
		{
			break;
		}
	}

	return Insert(pA,i + 1,x);
}


/*
已知 A，B 和 C 为三个递增有序的顺序表，现要求对 A 表作如下操作：
删去那些既在 B 表中出现又在 C 表中出现的元素。
试对顺序表编写实现上述操作的算法，并分析你的算法的 时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 
*/
void List_A_sub_BC(PSqList pA,PSqList pB,PSqList pC)//O(n)
{

	int value_a = 0,value_b = 0,value_c = 0;
	int i = 0,j = 0,k = 0;//分别为顺序表ABC的下标

	while (i < GetLentgh(pA) && j < GetLentgh(pB) && k < GetLentgh(pC))
	{
		value_a = GetElel(pA,i);
		value_b = GetElel(pB,j);
		value_c = GetElel(pC,k);

		if( value_a == value_b && value_a == value_c )
		{
			DeletePosVal(pA,i);
		}
		else if(value_b < value_a )
		{
			j++;
		}
		else if(value_c < value_a )
		{
			k++;
		}
		else
		{
			i++;
		}
	}
	printf("\n");
}

int main()
{

	SqList pA,pB,pC;
	
	InitSqlist(&pA);
	InitSqlist(&pB);
	InitSqlist(&pC);
	Insert(&pA,0,1);Insert(&pA,1,2);
	Insert(&pA,2,3);Insert(&pA,3,5);
	Insert(&pA,4,7);Insert(&pA,5,9);
	Insert(&pA,6,10);Insert(&pA,7,11);
	Insert(&pA,8,19);Insert(&pA,9,29);

	Insert(&pB,0,1);Insert(&pB,1,3);
	Insert(&pB,2,4);Insert(&pB,3,6);
	Insert(&pB,4,8);
	
	
	Insert(&pC,0,1);Insert(&pC,1,3);
	Insert(&pC,2,5);Insert(&pC,3,6);
	Insert(&pC,4,8);Insert(&pC,5,9);
	
	printf("A集合:");
	Show(&pA);
	printf("B集合:");
	Show(&pB);


	printf("C集合:");
	Show(&pC);

	
	
	Destory(&pA);
	Destory(&pB);
	Destory(&pC);

	return 0;
}
顺序表 数据结构
上一篇: 两集合的并集（线性表）
下一篇: QT一些函数和需要记忆的一些东西QT一些函数和需要记忆的一些东西

继续阅读