22.07.07---线性表的顺序表示

目录

1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置有最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

2.设计一个高效的算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1).

3.长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

 4.从有序顺序表中删除其值在给定值 s 与 t 之间(要求s < t)的所有元素，如果s 或 t不合理或者顺序表为空则显示出错信息并退出运行。​编辑

5.从顺序表中删除其值在给定值s与t之间(包含s和t，要求s)的所有元素，如果s和t不合理或者顺序表为空则显示出错信息并退出运行。<>

 6.从有序顺序表中删除所有其值重复的元素，是表中所有元素的值均不同。​编辑

 7.将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表。

 8.已知在一维数组A[m+n]中依次存放着两个线性表(a1,a2,a3,...,am)和(b1,b2,b3,...,bn)。试编写一个函数，将数组中两个顺序表的位置呼唤，即将(b1,b2,b3,...,bn)放在(a1,a2,a3,...,am)的前面。

9.线性表{a1,a2,a3,...,an}中元素递增有序且按顺序存储与计算机内。要求设计一算法完成用最少时间在表中查找数值为x的元素，若找到将其与后继元素位置相交换，若找不到将其插入表中并使表中元素仍递增有序。​编辑

 10.设将n(n>1)个整数存放到一堆数组R中，试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0

 11.一个长度为L(L>=1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1={11，13，15，17，19}，则S1的中位数是15，两个序列的中位数是含他们所有元素的升序序列的中位数。例如，若S2={2，4，6，8，20}，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

 12.已知一个整数序列A=(a0,a1,...,a(n-1)),其中0<=ain/2(0<=pk,1<=k<=m)，则称x为a的主元素。例如a=(0,5,5,3,5,7,5,5)，则5为主元素；又如a=(0,5,5,3,5,1,5,7)，则a中没有主元素。假设a中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出a的主元素。若存在主元素，则输出该元素；否则输出-1。<>(0<=i

 13.给定一个含n(n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。

14.定义三元组(a,b,c)(a,b,c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距离。例如S1={-1，0，9}，S2={-25，-10，10，11}，S3={2，9，17，30，41}，则最小距离为2，相应的三元组为{9，10，9}。

1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置有最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = { 2,3,4,6,7,1,8,9 };
	int length = 8;
}SqList;

bool ListDelete(SqList& s, int& elem)
{
	if (s.length == 0)
		return false;

	int min_num = s.a[0];
	int flag = 0;     //记录数组下标

	for (int i = 1; i < s.length; i++)
	{
		if (s.a[i] < min_num)
		{
			min_num = s.a[i];
			flag = i;
		}
	}

	elem = s.a[flag];
	s.a[flag] = s.a[s.length - 1];

	return true;
}

int main()
{
	SqList s;

	printf("原先数组为：n");

	for (int i = 0; i < s.length; i++)
		printf("%3d", s.a[i]);
	printf("n");

	int k = 0;
	if (ListDelete(s, k))
	{
		printf("最小元素为 k = %dn", k);
		printf("修改之后的线性表为：n");

		for (int i = 0; i < s.length; i++)
			printf("%3d", s.a[i]);
		printf("n");
	}
	else
		printf("错误n");

	return 0;
}

---

2.设计一个高效的算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1).

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = { 1,4,6,3,2,8,7 };
	int length = 7;
}SqList;

void Reverse(SqList &L)
{
	for (int i = 0; i <= L.length / 2; i++)
	{
		int temp = L.a[i];
		L.a[i] = L.a[L.length - i - 1];
		L.a[L.length - i - 1] = temp;
	}
}

int main()
{
	SqList L;
	
	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	Reverse(L);
	
	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	return 0;
}

---

3.长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = { 5,2,0,1,3,1,4,1,1,4 };
	int length = 10;
}SqList;

void delete_x(SqList& L, int x)
{
	int k = 0;

	for (int i = 0; i < L.length; i++)
	{
		if (L.a[i] == x)
			k++;
		else
			L.a[i - k] = L.a[i];
	}
	L.length = L.length - k;
}

int main()
{
	SqList L;

	for(int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	delete_x(L, 1);

	for(int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	return 0;
}

---

 4.从有序顺序表中删除其值在给定值 s 与 t 之间(要求s < t)的所有元素，如果s 或 t不合理或者顺序表为空则显示出错信息并退出运行。

 (此图来源于b站的名为"憨憨鱼怪"的博主，仅用于学习，再次感谢~)

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = { 1,2,3,3,4,5,6,7,7,7,8,9 };
	int length = 12;
}SqList;

//open interval 开区间
bool DeleteOpenInterVal(SqList& L, int s, int t)
{
	if (s >= t || L.length == 0)
		return false;
	
	int left = 0;      //记录>左端点s的第一个数据元素的下标值
	bool flag = false; //用来判断是否存在>s的值

	for (int i = 0; i < L.length; i++)
	{
		if (L.a[i] > s)
		{
			left = i;
			flag = true;
			break;
		}
	}

	if (!flag)//不存在>s的数据元素则返回false
		return false;

	int right = 0;//记录>=右端点t的第一个数据元素的下标

	for (int i = left; i < L.length; i++)
	{
		if (L.a[i] >= t)
		{
			right = i;
			break;
		}
	}

	int Lpos = left, Rpos = right;
	//删除(s,t)的所有元素
	for (int i = right; i < L.length; i++)
	{
		L.a[left] = L.a[i];
		left++;
	}
	L.length = L.length - (Rpos - Lpos);

	return true;
}

int main()
{
	SqList L;

	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	if (!DeleteOpenInterVal(L, 3, 7))
		printf("错误n");

	printf("线性表长度为：%dn", L.length);

	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	return 0;
}

---

5.从顺序表中删除其值在给定值s与t之间(包含s和t，要求s

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = { 4,1,2,5,0,0,3 };
	int length = 7;
}SqList;

//closed interval 闭区间
bool DeleteClosedInterval(SqList& L, int s, int t)
{
	if (L.length == 0 || s >= t)
		return false;

	int count = 0;       //记录[s,t]区间内的数据元素的个数
	bool flag = false; //用来判断是否存在>s的数据

	for (int i = 0; i < L.length; i++)
	{
		if (L.a[i] >= s)
		{
			flag = true;
			break;
		}
	}

	if (!flag)
		return false;

	for (int i = 0; i < L.length; i++)
	{
		if (L.a[i] >= s && L.a[i] <= t)
			count++;
		else
			L.a[i - count] = L.a[i];
	}
	L.length = L.length - count;

	return true;
}

int main()
{
	SqList L;

	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	if (!DeleteClosedInterval(L, 3, 5))
		printf("错误n");

	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	return 0;
}

---

 6.从有序顺序表中删除所有其值重复的元素，是表中所有元素的值均不同。

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = { 2,2,3,3,3,5,6,6,7 };
	int length = 9;
}SqList;

void deleteRepeatValue(SqList& L)
{
	int black = 1; //首元素是唯一的，从第二个数据元素开始记录

	for (int red = 1; red < L.length; red++)
	{
		if (L.a[red] != L.a[red - 1])
		{
			L.a[black] = L.a[red];
			black++;
		}
	}

	L.length = black;
}

int main()
{
	SqList L;

	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	deleteRepeatValue(L);

	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");

	return 0;
}*/

---

 7.将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表。

#include 

#define Max 50

typedef struct SqList {
	int data[Max];
	int length;
}SqList;

bool vergeSqList(SqList A, SqList B, SqList& C)
{
	if (C.length < A.length + B.length)
		return false;

	int ptrA = 0, ptrB = 0, ptrC = 0;

	while (ptrA < A.length && ptrB < B.length)
	{
		if (A.data[ptrA] <= B.data[ptrB])
			C.data[ptrC++] = A.data[ptrA++];
		else
			C.data[ptrC++] = B.data[ptrB++];
	}

	while (ptrA < A.length)
	{
		C.data[ptrC++] = A.data[ptrA++];
	}

	while (ptrB < B.length)
	{
		C.data[ptrC++] = B.data[ptrB++];
	}

	C.length = A.length + B.length;

	return true;
}

int main()
{
	SqList A = { {2,3,4,6,7 },5 };

	SqList B = { {3,4,4},3 };

	SqList C;
	C.length = A.length + B.length;

	printf("顺序表A中的数据元素：");
	for (int i = 0; i < A.length; i++)
		printf("%3d", A.data[i]);
	printf("n");

	printf("顺序表B中的数据元素：");
	for (int i = 0; i < B.length; i++)
		printf("%3d", B.data[i]);
	printf("n");

	if (!vergeSqList(A, B, C))
		printf("合并错误n");
	else
	{
		printf("顺序表C中的数据元素：");
		for (int i = 0; i < C.length; i++)
			printf("%3d", C.data[i]);
		printf("n");
	}

	return 0;
}

---

 8.已知在一维数组A[m+n]中依次存放着两个线性表(a1,a2,a3,...,am)和(b1,b2,b3,...,bn)。试编写一个函数，将数组中两个顺序表的位置呼唤，即将(b1,b2,b3,...,bn)放在(a1,a2,a3,...,am)的前面。

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = { 1,2,3,4,5,6,7 };
	int length = 7;
}SqList;

void reverseSqList(SqList& L, int left, int right)
{
	for (int i = left; i <= (left + right) / 2; i++)
	{
		int temp = L.a[i];
		L.a[i] = L.a[right+left - i];
		L.a[left + right - i] = temp;
	}
}

void print(SqList L)
{
	for (int i = 0; i < L.length; i++)
		printf("%3d", L.a[i]);
	printf("n");
}

void change(SqList& L, int m, int n)
{
	
	//1.将顺序表中的所有数据元素逆置
	printf("整个顺序表数据元素逆置：n");
	reverseSqList(L, 0, m + n - 1);
	print(L);

	
	//2.将逆置后的顺序表中的前n个元素逆置
	printf("前%d个数据元素逆置n",n);
	reverseSqList(L, 0, n - 1);
	print(L);

	
	//3.将顺序表中的后m个元素逆置
	printf("结果顺序表为：n");
	reverseSqList(L, n, n + m - 1);
	print(L);
}

int main()
{
	SqList L;

	printf("初始状态：n");
	print(L);
	change(L, 3, 4);//123 4567 -----> 4567 123

	return 0;
}

---

9.线性表{a1,a2,a3,...,an}中元素递增有序且按顺序存储与计算机内。要求设计一算法完成用最少时间在表中查找数值为x的元素，若找到将其与后继元素位置相交换，若找不到将其插入表中并使表中元素仍递增有序。

#include 

#define Max 50

typedef struct SqList {
	int a[Max] = {1,2,4,5,6,7,8,9};
	int length = 8;
}SqList;

void seekNum_x(SqList& L, int x)
{
	int left, right, mid;
	left = 0, right = L.length - 1;

	while (left <= right)
	{
		mid = (left + right) / 2;
		if (L.a[mid] == x)
			break;
		else if (L.a[mid] > x)
			right = mid - 1;
		else
			left = mid + 1;
	}

	if (L.a[mid] == x && mid != L.length - 1)
	{
		int temp = L.a[mid];
		L.a[mid] = L.a[mid + 1];
		L.a[mid + 1] = temp;
	}
	else if (right < left)
	{
		int i;
		for (i = L.length - 1; i > right; i--)
			L.a[i + 1] = L.a[i];
		L.a[i+1] = x;
		L.length++;
	}
}

int main()
{
	SqList L1;

	printf("初始状态：n");
	for (int i = 0; i < L1.length; i++)
		printf("%3d", L1.a[i]);
	printf("n");

	seekNum_x(L1, 7);
	printf("查找7：n");
	for (int i = 0; i < L1.length; i++)
		printf("%3d", L1.a[i]);
	printf("n");
	
	SqList L2;

	seekNum_x(L2, 3);
	printf("查找3：n");
	for (int i = 0; i < L2.length; i++)
		printf("%3d", L2.a[i]);
	printf("n");

	return 0;
}

---

 10.设将n(n>1)个整数存放到一堆数组R中，试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0

#include 

int a[7] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(a) / sizeof(int); //数组的元素个数

void reverse(int a[], int left, int right)
{
	for (int i = left; i <= (left + right) / 2; i++)
	{
		int temp = a[i];
		a[i] = a[left + right - i];
		a[left + right - i] = temp;
	}
}

void print(int a[])
{
	for (int i = 0; i < n; i++)
		printf("%3d", a[i]);
	printf("n");
}

void changeArray(int a[], int left)
{
	printf("全部逆置：n");
	reverse(a, 0, n - 1);
	print(a);

	printf("前%d-%d个逆置：n",n,left);
	reverse(a, 0, n - left - 1);
	print(a);

	printf("后%d个逆置：n", left);
	reverse(a, n-left, n-1);
	print(a);
}

int main()
{
	printf("数组初始状态：n");
	print(a);

	changeArray(a, 6);
	
	return 0;
}

---

 11.一个长度为L(L>=1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1={11，13，15，17，19}，则S1的中位数是15，两个序列的中位数是含他们所有元素的升序序列的中位数。例如，若S2={2，4，6，8，20}，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

#include 

int a[5] = { 11,13,15,17,19 };
int b[5] = { 2,4,6,8,20 };
int c[10];
int n = 5;

int vergeArray(int a[], int b[], int c[])
{
	int i = 0;
	int j = 0;
	int k = 0;

	while (i < n && j < n)
	{
		if (a[i] <= b[j])
			c[k++] = a[i++];
		else
			c[k++] = b[j++];
	}
	while(i 
 

 12.已知一个整数序列A=(a0,a1,...,a(n-1)),其中0<=ain/2(0<=pk
 
 
#include 

int A[8] = { 0, 5, 5, 3, 5, 7, 5, 5 };
int B[8] = { 0, 5, 5, 3, 5, 1, 5, 7 };
int numA = sizeof(A) / sizeof(int);
int numB = sizeof(B) / sizeof(int);

int FindMainElem(int A[], int& num)
{
	int compare = A[0];
	int count = 1;

	for (int i = 1; i < numA; i++)
	{
		if (A[i] == compare)
			count++;
		else
		{
			if (count > 0)
				count--;
			else
			{
				compare = A[i];
				count = 1;
			}
		}
	}

	int k = 0;
	for (int i = 0; i < numA; i++)
	{
		if (A[i] == compare)
			k++;
	}

	if (k > numA / 2)
	{
		num = compare;
		return true;
	}
	else
		return false;
}

int main()
{
	int num;

	if (FindMainElem(A, num))
		printf("主元素为：%dn", num);
	else
		printf("没有找到主元素。n");

	return 0;
}
 
 
//用哈希表实现 我没有用过这种
bool hashmap(int a[], int& num)
{
	mapmp;

	for (int i = 0; i < n; i++)
		mp[A[i]]++;

	int compare, count = 0;

	for (auto v::ap)
	{
		if (v.second > count)
		{
			compare = v.first;
			compare = v.second;
		}
	}

	if (count > n / 2)
	{
		num = compare;
		return true;
	}
	else
		return false;
}
 
 13.给定一个含n(n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。 
 
 
 

#include 

int a[4] = { -5,3,2,3 };
int n = 4;

int findMin(int a[])
{
	int b[6] = { 0 };
	
	for (int i = 0; i < n; i++)
		if (a[i] > 0 && a[i] <= n + 1)
			b[a[i]] = 1;

	int ans = 0;
	for (int i = 1; i < n + 2; i++)
	{
		if (b[i] == 0)
		{
			ans = i;
			break;
		}
	}

	return ans;
}

int main()
{
	for (int i = 0; i < n; i++)
		printf("%3d", a[i]);
	printf("n");

	printf("最小正整数为：%dn", findMin(a));

	return 0;
}
 
 

14.定义三元组(a,b,c)(a,b,c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距离。例如S1={-1，0，9}，S2={-25，-10，10，11}，S3={2，9，17，30，41}，则最小距离为2，相应的三元组为{9，10，9}。 
 
 
 
#include 

#define Max 0x7fffffff

int absNum(int a)
{
	if (a < 0) return -a;
	else return a;
}

int min(int a, int b)
{
	if (a <= b)
		return a;
	else
		return b;
}

bool minNum(int a, int b, int c)
{
	if (min(a, min(b, c)) == a)
		return true;
	return false;
}

int findNum(int a[], int b[], int c[], int aNum, int bNum, int cNum)
{
	int i = 0, j = 0, k = 0;
	int result = Max;

	while (i < aNum && j < bNum && k < cNum && result >= 0)
	{
		int length = absNum(a[i] - b[j]) + absNum(b[j] - c[k]) + absNum(c[k] - a[i]);
		
		if (length < result)
			result = length;
		if (minNum(a[i], b[j], c[k]))
			i++;
		else if (minNum(b[j], a[i], c[j]))
			j++;
		else k++;
	}

	return result;
}

int main()
{
	int a[3] = { -1,0,9 };
	int b[4] = { -25,-10,10,11 };
	int c[5] = { 2,9,17,30,41 };
	int aNum = 3, bNum = 4, cNum = 5;
	int distant = findNum(a, b, c, aNum, bNum, cNum);
	
	printf("最小距离为%dn", distant);

	return 0;
}
 
 

举步维艰的数据结构起步阶段 加油~