顺序表实现(下)(C语言)

几道相关例题,帮助大家更好理解顺序表.

前言

• 一、顺序表
• 二、创建顺序表并初始化
• 三.删除非递减顺序表L中的重复元素
• 四.在非递减顺序表中删除[s,t]之间的元素
• 五.设计算法逆置顺序表L,并将序列L循环左移
• 六.顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素
• 七.给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B?
• 八.给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)
• 九.测试
• 总结

---

前言

几道相关例题,帮助大家更好理解顺序表.

---

一、顺序表

typedef int Elemtype;
//顺序表的动态分配
typedef struct Sqlist {
	Elemtype* qlist;
	int length;
	int maxsize;
};
//定义打印顺序表函数
void print(Sqlist L) {
	for (int i = 0; i < L.length; i++) {//顺序遍历顺序表
		printf("%d ", L.qlist[i]);
	}

	printf("\n顺序表长度为:%d\n", L.length);
	printf("总大小为:%d\n", L.maxsize);
}

二、创建顺序表并初始化

//例1:定义创建顺序表并初始化函数
void InitSqlist(Sqlist& L) {//初始化空间为20,长度为15,{ 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 }
	L.maxsize = Max;
	L.length = 15;
	int arr[15] = { 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 };
	L.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (L.maxsize));
	for (int i = 0; i < L.length; i++) {
		L.qlist[i] = arr[i];
	}
}

?三.删除非递减顺序表L中的重复元素

//例6:删除非递减顺序表L中的重复元素
void deletesame(Sqlist &L) {
	int curlenth = 0;
	for (int i = 0; i < L.length; i++) {//每次区元素与新表最后一个元素进行比较如果不相等加入新表
		if (curlenth == 0 || L.qlist[i] != L.qlist[curlenth - 1]) {
			L.qlist[curlenth++] = L.qlist[i];
		}
	}
	L.length = curlenth;
}

四.在非递减顺序表中删除[s,t]之间的元素

//例7:在非递减顺序表中删除[s,t]之间的元素
void deletest2(Sqlist& L, int s, int t) {
	int curlength = 0;
	int i = 0;
	for (; i < L.length; i++) {//从前往后找第一个大于或等于s的元素的位置
		if (L.qlist[i] >= s) {
			break;
		}
	}
	curlength = i;
	i = L.length - 1;
	for (; i >= 0; i--) {//从后往前找第一个小于或等于t的元素的位置
		if (L.qlist[i] <= t) {
			break;
		}
	}
	i= i + 1;//指向下一个元素才是要复制的元素
	for (;  i< L.length; i++) {//复制元素
		L.qlist[curlength++] = L.qlist[i];
	}
	L.length = curlength;
}

?五.设计算法逆置顺序表L,并将序列L循环左移

//例8:设计算法逆置顺序表L,并将序列L循环左移
//定义逆置函数
void reverse1(Sqlist& L) {
	int low = 0;
	int high = L.length - 1;
	while (low < high) {//设置low和high指针对表中元素进行两两交换
		Elemtype tmp = L.qlist[low];
		L.qlist[low] = L.qlist[high];
		L.qlist[high] = tmp;
		low++;
		high--;
	}
}
void reverse2(Sqlist& L,int low ,int high) {
	while (low < high) {
		Elemtype tmp = L.qlist[low];
		L.qlist[low] = L.qlist[high];
		L.qlist[high] = tmp;
		low++;
		high--;
	}
}
void ROL(Sqlist &L, int r) {
	reverse2(L, 0, L.length - 1);//整体逆置
	reverse2(L, 0, r-1);//前r个元素逆置
	reverse2(L, r, L.length - 1);//后面元素逆置
}

?reverse1是直接将顺序表全部逆置,reverse2是给定起始和终止逆置.

顺序表的循环左移r位,就是先整体逆置,前r个元素逆置,后面元素逆置.

六.顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素

(1)将两表合并,两表中元素都储存在C中

(2)表A有m+n个存储空间,将A,B两表合并所有元素都存储到A中

(3)对表A进行简单插入排序

//例9:顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素
//(1)将两表合并,两表中元素都储存在C中
//创建La和Lb
void creatLaLb(Sqlist& La, Sqlist& Lb) {
	La.maxsize = 11;
	La.length = 6;
	int arr1[6] = { 0,2,4,7,8,9 };
	La.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));
	for (int i = 0; i < La.length; i++) {
		La.qlist[i] = arr1[i];
	}
	Lb.maxsize = 11;
	Lb.length = 5;
	int arr2[5] = { 10,6,5,3,1 };
	Lb.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));
	for (int i = 0; i < Lb.length; i++) {
		Lb.qlist[i] = arr2[i];
	}
}
//归并排序思想
void mergesort1(Sqlist& La, Sqlist& Lb, Sqlist& Lc) {
	int length = La.length + Lb.length;
	Lc.qlist = (Elemtype*)malloc(sizeof(Elemtype) * length);
	assert(Lc.qlist);
	Lc.maxsize = length;
	int curlength = 0;
	int i = 0;
	int j = Lb.length-1;
	while (i < La.length && j >=0) {
		if (La.qlist[i] > Lb.qlist[j]) {
			Lc.qlist[curlength] = Lb.qlist[j];
			curlength++;
			j--;
		}
		else {
			Lc.qlist[curlength] = La.qlist[i];
			curlength++;
			i++;
		}
	}
	while (i < La.length) {
		Lc.qlist[curlength++] = Lb.qlist[i];
		i++;
	}
	while (j >=0) {
		Lc.qlist[curlength++] = Lb.qlist[j];
		j--;
	}
	Lc.length = curlength;
}
//(2)表A有m+n个存储空间,将A,B两表合并所有元素都存储到A中
void mergesort2(Sqlist& La, Sqlist& Lb) {
	int curlength = 0;
	int i = La.length-1;//A表后
	int j = 0;//B表头
	while (i >= 0 && j < Lb.length) {//将A表与B表元素进行比较将大的存入A表后
		if (La.qlist[i] > Lb.qlist[j]) {
			La.qlist[La.maxsize - curlength - 1] = La.qlist[i];
			curlength++;
			i--;
		}
		else {
			La.qlist[La.maxsize - curlength - 1] = Lb.qlist[j];
			curlength++;
			j++;
		}
	}
	while (i >= 0) {//将A表剩余元素直接复制到A表中
		La.qlist[La.maxsize - curlength - 1] = La.qlist[i];
		curlength++;
		i--;
	}
	while (j < Lb.length) {//将B表剩余元素直接复制到A表中
		La.qlist[La.maxsize - curlength - 1] = Lb.qlist[j];
		curlength++;
		j++;
	}
	La.length = La.length + Lb.length;
}
//(3)对表A进行简单插入排序
void selectsort(Sqlist& L) {
	int i = 0;
	int j = 0;
	while (i < L.length) {//每次选取一个元素
		Elemtype e = L.qlist[i];
		j = i - 1;
		while (j >= 0 && e < L.qlist[j]) {//寻找插入位置
			L.qlist[j + 1] = L.qlist[j];
			j--;
		}
		L.qlist[j + 1] = e;
		i++;
	}
}

七.给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B?

//例10:给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B
//创建两个升序La表和Lb表
void creatLaLb2(Sqlist& La, Sqlist& Lb) {
	La.maxsize = 20;
	La.length = 11;
	int arr1[11] = { 1,1,2,2,3,3,4,4,5,5,6 };
	La.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));
	for (int i = 0; i < La.length; i++) {
		La.qlist[i] = arr1[i];
	}
	Lb.maxsize = 20;
	Lb.length = 11;
	int arr2[11] = { 1,1,2,2,4,4,5,5,6,6,7 };
	Lb.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));
	for (int i = 0; i < Lb.length; i++) {
		Lb.qlist[i] = arr2[i];
	}
}
//求解A交B
void intersect(Sqlist &La,Sqlist &Lb) {
	int curlength = 0;
	int i = 0;
	int j = 0;
	while (i < La.length && j < Lb.length) {//A表和B表元素进行两两比较如果相等加入新表
		if (La.qlist[i] == Lb.qlist[j]) {
			La.qlist[curlength] = La.qlist[i];
			i++;
			j++;
			curlength++;
		}
		else if(La.qlist[i] > Lb.qlist[j]) {//B表当前元素小于表A当前元素B表下表加一
			j++;
		}
		else {//A表当前元素小于表B当前元素A表下表加一
			i++;
		}
	}
	La.length = curlength;//元素个数改变
}

?八.给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)

//例11:给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)
//算法思想跟上一题一样
void except(Sqlist& La, Sqlist& Lb) {
	int curlength = 0;
	int i = 0;
	int j = 0;
	while (i < La.length && j < Lb.length) {
		if (La.qlist[i] == Lb.qlist[j]) {//相等下标都相加
			i++;
			j++;
		}
		else if (La.qlist[i] > Lb.qlist[j]) {//a>b,B下标增加
			j++;
		}
		else {//a<b说明当前A中元素一定是B中没有的
			La.qlist[curlength] = La.qlist[i];
			curlength++;
			i++;
		}
	}
	while (i < La.length) {//将A表剩余元素复制到新表
		La.qlist[curlength] = La.qlist[i];
		curlength++;
		i++;
	}
	La.length = curlength;//元素个数改变
}

九.测试

全部代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define Max 20

typedef int Elemtype;
//顺序表的动态分配
typedef struct Sqlist {
	Elemtype* qlist;
	int length;
	int maxsize;
};
//定义打印顺序表函数
void print(Sqlist L) {
	for (int i = 0; i < L.length; i++) {//顺序遍历顺序表
		printf("%d ", L.qlist[i]);
	}

	printf("\n顺序表长度为:%d\n", L.length);
	printf("总大小为:%d\n", L.maxsize);
}

//例1:定义创建顺序表并初始化函数
void InitSqlist(Sqlist& L) {//初始化空间为20,长度为15,{ 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 }
	L.maxsize = Max;
	L.length = 15;
	int arr[15] = { 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 };
	L.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (L.maxsize));
	for (int i = 0; i < L.length; i++) {
		L.qlist[i] = arr[i];
	}
}
//例6:删除非递减顺序表L中的重复元素
void deletesame(Sqlist &L) {
	int curlenth = 0;
	for (int i = 0; i < L.length; i++) {//每次区元素与新表最后一个元素进行比较如果不相等加入新表
		if (curlenth == 0 || L.qlist[i] != L.qlist[curlenth - 1]) {
			L.qlist[curlenth++] = L.qlist[i];
		}
	}
	L.length = curlenth;
}
//例7:在非递减顺序表中删除[s,t]之间的元素
void deletest2(Sqlist& L, int s, int t) {
	int curlength = 0;
	int i = 0;
	for (; i < L.length; i++) {//从前往后找第一个大于或等于s的元素的位置
		if (L.qlist[i] >= s) {
			break;
		}
	}
	curlength = i;
	i = L.length - 1;
	for (; i >= 0; i--) {//从后往前找第一个小于或等于t的元素的位置
		if (L.qlist[i] <= t) {
			break;
		}
	}
	i= i + 1;//指向下一个元素才是要复制的元素
	for (;  i< L.length; i++) {//复制元素
		L.qlist[curlength++] = L.qlist[i];
	}
	L.length = curlength;
}
//例8:设计算法逆置顺序表L,并将序列L循环左移
//定义逆置函数
void reverse1(Sqlist& L) {
	int low = 0;
	int high = L.length - 1;
	while (low < high) {//设置low和high指针对表中元素进行两两交换
		Elemtype tmp = L.qlist[low];
		L.qlist[low] = L.qlist[high];
		L.qlist[high] = tmp;
		low++;
		high--;
	}
}
void reverse2(Sqlist& L,int low ,int high) {
	while (low < high) {
		Elemtype tmp = L.qlist[low];
		L.qlist[low] = L.qlist[high];
		L.qlist[high] = tmp;
		low++;
		high--;
	}
}
void ROL(Sqlist &L, int r) {
	reverse2(L, 0, L.length - 1);//整体逆置
	reverse2(L, 0, r-1);//前r个元素逆置
	reverse2(L, r, L.length - 1);//后面元素逆置
}
//例9:顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素
//(1)将两表合并,两表中元素都储存在C中
//创建La和Lb
void creatLaLb(Sqlist& La, Sqlist& Lb) {
	La.maxsize = 11;
	La.length = 6;
	int arr1[6] = { 0,2,4,7,8,9 };
	La.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));
	for (int i = 0; i < La.length; i++) {
		La.qlist[i] = arr1[i];
	}
	Lb.maxsize = 11;
	Lb.length = 5;
	int arr2[5] = { 10,6,5,3,1 };
	Lb.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));
	for (int i = 0; i < Lb.length; i++) {
		Lb.qlist[i] = arr2[i];
	}
}
//归并排序思想
void mergesort1(Sqlist& La, Sqlist& Lb, Sqlist& Lc) {
	int length = La.length + Lb.length;
	Lc.qlist = (Elemtype*)malloc(sizeof(Elemtype) * length);
	assert(Lc.qlist);
	Lc.maxsize = length;
	int curlength = 0;
	int i = 0;
	int j = Lb.length-1;
	while (i < La.length && j >=0) {
		if (La.qlist[i] > Lb.qlist[j]) {
			Lc.qlist[curlength] = Lb.qlist[j];
			curlength++;
			j--;
		}
		else {
			Lc.qlist[curlength] = La.qlist[i];
			curlength++;
			i++;
		}
	}
	while (i < La.length) {
		Lc.qlist[curlength++] = Lb.qlist[i];
		i++;
	}
	while (j >=0) {
		Lc.qlist[curlength++] = Lb.qlist[j];
		j--;
	}
	Lc.length = curlength;
}
//(2)表A有m+n个存储空间,将A,B两表合并所有元素都存储到A中
void mergesort2(Sqlist& La, Sqlist& Lb) {
	int curlength = 0;
	int i = La.length-1;//A表后
	int j = 0;//B表头
	while (i >= 0 && j < Lb.length) {//将A表与B表元素进行比较将大的存入A表后
		if (La.qlist[i] > Lb.qlist[j]) {
			La.qlist[La.maxsize - curlength - 1] = La.qlist[i];
			curlength++;
			i--;
		}
		else {
			La.qlist[La.maxsize - curlength - 1] = Lb.qlist[j];
			curlength++;
			j++;
		}
	}
	while (i >= 0) {//将A表剩余元素直接复制到A表中
		La.qlist[La.maxsize - curlength - 1] = La.qlist[i];
		curlength++;
		i--;
	}
	while (j < Lb.length) {//将B表剩余元素直接复制到A表中
		La.qlist[La.maxsize - curlength - 1] = Lb.qlist[j];
		curlength++;
		j++;
	}
	La.length = La.length + Lb.length;
}
//(3)对表A进行简单插入排序
void selectsort(Sqlist& L) {
	int i = 0;
	int j = 0;
	while (i < L.length) {//每次选取一个元素
		Elemtype e = L.qlist[i];
		j = i - 1;
		while (j >= 0 && e < L.qlist[j]) {//寻找插入位置
			L.qlist[j + 1] = L.qlist[j];
			j--;
		}
		L.qlist[j + 1] = e;
		i++;
	}
}
//例10:给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B
//创建两个升序La表和Lb表
void creatLaLb2(Sqlist& La, Sqlist& Lb) {
	La.maxsize = 20;
	La.length = 11;
	int arr1[11] = { 1,1,2,2,3,3,4,4,5,5,6 };
	La.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));
	for (int i = 0; i < La.length; i++) {
		La.qlist[i] = arr1[i];
	}
	Lb.maxsize = 20;
	Lb.length = 11;
	int arr2[11] = { 1,1,2,2,4,4,5,5,6,6,7 };
	Lb.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));
	for (int i = 0; i < Lb.length; i++) {
		Lb.qlist[i] = arr2[i];
	}
}
//求解A交B
void intersect(Sqlist &La,Sqlist &Lb) {
	int curlength = 0;
	int i = 0;
	int j = 0;
	while (i < La.length && j < Lb.length) {//A表和B表元素进行两两比较如果相等加入新表
		if (La.qlist[i] == Lb.qlist[j]) {
			La.qlist[curlength] = La.qlist[i];
			i++;
			j++;
			curlength++;
		}
		else if(La.qlist[i] > Lb.qlist[j]) {//B表当前元素小于表A当前元素B表下表加一
			j++;
		}
		else {//A表当前元素小于表B当前元素A表下表加一
			i++;
		}
	}
	La.length = curlength;//元素个数改变
}
//例11:给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)
//算法思想跟上一题一样
void except(Sqlist& La, Sqlist& Lb) {
	int curlength = 0;
	int i = 0;
	int j = 0;
	while (i < La.length && j < Lb.length) {
		if (La.qlist[i] == Lb.qlist[j]) {//相等下标都相加
			i++;
			j++;
		}
		else if (La.qlist[i] > Lb.qlist[j]) {//a>b,B下标增加
			j++;
		}
		else {//a<b说明当前A中元素一定是B中没有的
			La.qlist[curlength] = La.qlist[i];
			curlength++;
			i++;
		}
	}
	while (i < La.length) {//将A表剩余元素复制到新表
		La.qlist[curlength] = La.qlist[i];
		curlength++;
		i++;
	}
	La.length = curlength;//元素个数改变
}
int main() {
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对InitSqlist进行测试!\n");
	Sqlist L;
	InitSqlist(L);
	print(L);//打印顺序表以及信息
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对deletesame进行测试!\n");
	deletesame(L);
	print(L);
	InitSqlist(L);
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对deletest2进行测试!\n");
	deletest2(L, 4, 7);
	print(L);
	InitSqlist(L);
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对reverse2进行测试!\n");
	reverse1(L);
	print(L);
	InitSqlist(L);
	reverse2(L, 0, L.length - 1);
	print(L);
	InitSqlist(L);
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对ROL进行测试!\n");
	print(L);
	ROL(L,3);
	print(L);
	InitSqlist(L);
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对例8进行测试!\n");
	Sqlist La,Lb,Lc;
	printf("创建La和Lb顺序表\n");
	creatLaLb(La, Lb);
	print(La);
	print(Lb);
	printf("归并La和Lb顺序表\n");
	mergesort1(La, Lb, Lc);
	print(Lc);
	printf("归并La和Lb顺序表用原空间\n");
	mergesort2(La, Lb);
	print(La);
	print(Lb);
	creatLaLb(La, Lb);//初始化一下
	Sqlist LA;
	LA.maxsize = Max;
	LA.length = 12;
	int arr[12] = { 3,6,2,1,7,8,4,5,9,10,12,11 };
	LA.qlist = (Elemtype*)malloc(sizeof(Elemtype) * (LA.maxsize));
	for (int i = 0; i < L.length; i++) {
		LA.qlist[i] = arr[i];
	}
	print(LA);
	printf("对表A进行简单选择插入排序!\n");
	selectsort(LA);
	print(LA);
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对例10进行测试!\n");
	creatLaLb2(La, Lb);
	print(La);
	print(Lb);
	intersect(La, Lb);
	print(La);
	printf("+++++++++++++++++++++++++++++++++++++++\n");
	printf("对例11进行测试!\n");
	creatLaLb2(La, Lb);
	print(La);
	print(Lb);
	except(La, Lb);
	print(La);
	return 0;

}

?输出结果:

---

总结

写了几个经典的顺序表的题目,有些函数作用是创建表的,可以省略,主要是解决问题的思路和方法,输出结果比较常所以我分成了两张图片,大家自行比对,或者直接复制代码上机运行,有问题的地方可以私信我.