考研复习顺序表(数组)

Mercia ·

更新时间:2024-11-10

· 678 次阅读

顺序表复习顺序型线性表结构体InitList(LA)ListEmpty(LA)ListInsert(sqlist LA,int I,int e) 插入元素例题1.已知一个非纯集合，试构造一个纯集合a，使a中只包含b中所有值各不相同的数据元素。（数组去重）2.归并两个“其数据元素按值非递减有序排列的”线性表LA，LB求得线性表LC也具有同样特性 顺序型线性表

顺序型线性表每个元素的存储是连续的，所有元素的地址取决于第一个元素的地址，也就是基地址。

结构体

其实结构体也可以不用写
可以直接写
int num[maxsize];
int length=0;
这样更简单一点

typedef struct{
	int num[maxsize];
	int length;
}sqlist;

InitList(LA)

初始化构造一个顺序表数组初始化很简单

void InitList(sqlist LA)
{
	LA.length=0;
}

ListEmpty(LA)

判空表

bool LIstEmpty(LA)
{
	if(LA.length==0)
	return true;
}

ListInsert(sqlist LA,int I,int e) 插入元素

如果在顺序表插入一个数据，那么位置i，以及i以后的数据都要向后退一个位子。

sqlist ListInsert(sqlist LA,int i,int e)
{
	//如果位置不合法就报错
	if(iLA.length-1){
		printf("wrong");
		return LA;
	}
	//如果新表长度大于最大长度，需要增加分配。这里我就不写代码了，因为我没有在结构体定义最大长度
	//向后退一格
	for(int j=LA.length-1;j>i;j--){
		LA.num[j+1]=LA.num[j];
	}
	//在位置i添加元素
	LA.num[i]=e;
	LA.length++;
	return LA;
}

例题 1.已知一个非纯集合，试构造一个纯集合a，使a中只包含b中所有值各不相同的数据元素。（数组去重）

#include
#define maxsize 100
typedef struct{
	int num[maxsize];
	int length;
}sqlist;
void InitList(sqlist LA)
{
	LA.length=0;
}
sqlist paixu(sqlist LB)
{
	int temp;
	for(int i=0;i<LB.length-1;i++)
	{
		for(int j=i+1;jLB.num[j])
			{
				temp=LB.num[i];
				LB.num[i]=LB.num[j];
				LB.num[j]=temp;
			}
		}
	}
	return LB;
}
int main()
{
	sqlist LA,LB;
	InitList(LA);
	LB.num[0]=6;
	LB.num[1]=4;
	LB.num[2]=4;
	LB.num[3]=8;
	LB.num[4]=1;
	LB.length=5;
	//排序
	LB=paixu(LB);
	LA.num[0]=LB.num[0];
	LA.length=1;
	for(int i=1;iLA.num[i-1]){
			LA.num[LA.length]=LB.num[i];
		}
	}
	return 0;
}

2.归并两个“其数据元素按值非递减有序排列的”线性表LA，LB求得线性表LC也具有同样特性

#include
#define maxsize 100
typedef struct{
	int num[maxsize];
	int length;
}sqlist;
sqlist InitList(sqlist LA)
{
	LA.length=0;
	return LA;
}
sqlist paixu(sqlist LB)
{
	int temp;
	for(int i=0;i<LB.length-1;i++)
	{
		for(int j=i+1;jLB.num[j])
			{
				temp=LB.num[i];
				LB.num[i]=LB.num[j];
				LB.num[j]=temp;
			}
		}
	}
	return LB;
}
sqlist ListInsert(sqlist LA,int i,int e)
{
	//如果位置不合法就报错
	if(iLA.length){
		printf("wrong");
		return LA;
	}
	//如果新表长度大于最大长度，需要增加分配。这里我就不写代码了，因为我没有在结构体定义最大长度
	//向后退一格
	for(int j=LA.length-1;j>=i;j--){
		LA.num[j+1]=LA.num[j];
	}
	//在位置i添加元素
	LA.num[i]=e;
	LA.length++;
	return LA;
}
int main()
{
	sqlist LA,LB;
	InitList(LA);
	LB.num[0]=6;
	LB.num[1]=4;
	LB.num[2]=4;
	LB.num[3]=8;
	LB.num[4]=1;
	LB.length=5;
	LA.num[0]=10;
	LA.num[1]=4;
	LA.num[2]=8;
	LA.num[3]=2;
	LA.num[4]=3;
	LA.length=5;
	//排序
	LB=paixu(LB);
	LA=paixu(LA);
	sqlist LC;
	LC=InitList(LC);
	int i=0,j=0;
	while(i<LA.length&&j<LB.length){
		if(LA.num[i]<=LB.num[j])
		{
			LC=ListInsert(LC,LC.length,LA.num[i]);
			i++;
		}else{
			LC=ListInsert(LC,LC.length,LB.num[j]);
			j++;
		}
	}
	while(i<LA.length)
	{
		LC=ListInsert(LC,LC.length,LA.num[i]);
		i++;
	}
	while(j<LB.length)
	{
		LC=ListInsert(LC,LC.length,LB.num[j]);
		j++;
	}
	return 0;
}