C++——数据结构算法归纳

2_2 线性表的顺序表示

• 2_1 删除顺序表中最小元素，并返回最小值，空出的元素由最后一个元素填补，若顺序表为空显示错误信息并退出。
• 2_2 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的的空间复杂度为O(1)
• 2_3 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素
• 2_4 有序顺序表，删除值在s与t之间的所有元素(s<t),若s或t不合理或顺序表为空，则显示出错信息并退出运行
• 2_5 顺序表，删除值在s与t之间的所有元素(s<t),若s或t不合理或顺序表为空，则显示出错信息并退出运行
• 2_6 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同
• 2_7 将两个有序顺序表合并为一个新的有序顺序表，并有函数返回结果顺序表

#pragma once
#include<iostream>
using namespace std;

#define MaxSize 50
#define Initsize 10
typedef int ElemType;
//静态分配
/*
struct SqList {
	ElemType data[MaxSize];
	int length;
};
*/
//动态分配
struct SqList {
	ElemType* data;
	int length;
	int initsize;
};

/*
线性表的基本操作
InitList(&L)
Length(L)
ListInsert(&L,i,e);
ListDelete(&L,i,e);
LocateElem(L,e);
GetElem(L,i);
PrintList(L);
Empty(L);
DestroyList(&L)
*/
void InitList(SqList& L) {
	L.data = new ElemType[Initsize];
	L.length = 0;
	L.initsize = Initsize;	//初始顺序表的大小
}

int Length(SqList L) {
	return L.length;
}
bool ListInsert(SqList& L, int i, ElemType e) {
	if (i<1 || i>L.length + 1)
		return false;
	if (L.length > MaxSize) {
		return false;
	}
	for (int j = L.length;j >= i;j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	return true;
}

bool ListDelete(SqList& L, int i, ElemType& e) {
	if (i<1 || i>L.length) {
		return false;
	}
	e = L.data[i - 1];
	for (int j = i;j < L.length;j++) {
		L.data[j - 1] = L.data[j];
	}
	L.length--;
	return true;
}

int LocateElem(SqList L, ElemType e) {
	int i;
	for (int i = 0;i < L.length;i++) {
		if (L.data[i] == e) {
			return i + 1;
		}
	}
	return 0;
}
ElemType GetElem(SqList L, int i) {
	if (i < 1 || i < L.length) {
		return false;
	}
	else {
		return L.data[i - 1];
	}
}
void PrintList(SqList L) {
	for (int i = 0;i < L.length;i++) {
		cout << L.data[i] << " ";
	}
	cout << endl;
}

bool Empty(SqList L) {
	if (L.length < 1) {
		return true;
	}
	return false;
}

void DestroyList(SqList &L) {
	L.length = 0;
	delete L.data;
}

#include<iostream>
#include"Unit2_2顺序.h"

using namespace std;

//测试
void test() {
	/*
	动态分配空间
	SeqList L;
	L.data = new ElemType(10);
	*/
	SqList L;
	InitList(L);
	for (int i = 0;i < 5;i++) {
		ListInsert(L, i+1, i);
	}
	PrintList(L);
	
	cout << "元素值为3是第 " << LocateElem(L, 3) << " 个数" << endl;
	
	ElemType e;
	ListDelete(L, 3, e);
	cout << "删除的第3个元素为" << e << endl;

	cout << "第4个元素的值是： " << GetElem(L, 4) << endl;

	DestroyList(L);
	PrintList(L);
}

//2_1 删除顺序表中最小元素，并返回最小值，空出的元素由最后一个元素填补，若顺序表为空显示错误信息并退出。
bool Del_Min(SqList& L, ElemType& e) {
	ElemType minIndex;
	if (L.length < 1) {
		return false;
	}
	else {
		minIndex =0;
		for (int i = 0;i < L.length;i++) {
			if (minIndex > L.data[i]) {
				minIndex = i;
			}
		}
		e = L.data[minIndex];
		L.data[minIndex] = L.data[L.length - 1];
		L.length--;
		return true;
	}
}
void test2_1() {
	//创建顺序表，并赋值
	SqList L;
	InitList(L);
	ElemType arr[5] = { 2,6,3,5,8 };
	L.data = arr;
	L.length = 5;
	PrintList(L);

	ElemType e;
	Del_Min(L, e);
	cout << "删除的最小值为:" << e << endl;
	PrintList(L);
}

//2_2 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的的空间复杂度为O(1)
void Reverse(SqList& L) {
/*
0+4 1+3 2+2
*/	ElemType t = 0;
	for (int i = 0;i < L.length/2;i++) {
		t = L.data[i];
		L.data[i] = L.data[L.length - i - 1];
		L.data[L.length - i - 1] = t;
	}
}
void test2_2() {
	//创建顺序表，并赋值
	SqList L;
	InitList(L);
	ElemType arr[5] = { 2,6,3,5,8 };
	L.data = arr;
	L.length = 5;
	PrintList(L);

	Reverse(L);
	PrintList(L);
}

//2_3 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素
void del_x_1(SqList& L, ElemType x) {
	int k = 0;
	for (int i = 0;i < L.length;i++) {
		if (L.data[i] != x) {
			L.data[k] = L.data[i];
			k++;
		}
	}
	L.length = k;
}
void test2_3() {
	//创建顺序表，并赋值
	SqList L;
	InitList(L);
	ElemType arr[5] = { 2,6,3,5,8 };
	L.data = arr;
	L.length = 5;
	PrintList(L);

	del_x_1(L, 3);
	PrintList(L);
}

//2_4 有序顺序表，删除值在s与t之间的所有元素(s<t),若s或t不合理或顺序表为空，则显示出错信息并退出运行
bool Del_s_t2(SqList& L, ElemType s, ElemType t) {
	int i, j;
	if (s >= t || L.length < 1) {
		return false;
	}
	else {
		for (i = 0;i < L.length && L.data[i] < s;i++);
		if (i >= L.length) {
			return false;
		}
		for (j = L.length - 1;j >= 0 && L.data[i] > t;j--);
		//取得下标i-j;
		for (;j < L.length;i++, j++) {
			L.data[i] = L.data[j];
		}
		L.length = i;
		return true;
	}
}
void test2_4() {
	SqList L;
	InitList(L);
	ElemType arr[5] = { 2,4,5,6,7 };
	L.data = arr;
	L.length = 5;
	PrintList(L);

	Del_s_t2(L, 3, 6);
	PrintList(L);
}

//2_5 顺序表，删除值在s与t之间的所有元素(s<t),若s或t不合理或顺序表为空，则显示出错信息并退出运行
bool Del_s_t(SqList& L, ElemType s, ElemType t) {
	if (s >= t || L.length <= 0) {
		return false;
	}
	int k = 0;
	for (int i = 0;i < L.length;i++) {
		if (L.data[i]<s || L.data[i]>t) {
			L.data[k] = L.data[i];
			k++;
		}
	}
	L.length = L.length - k;
	return true;
}
void test2_5() {
	SqList L;
	InitList(L);
	ElemType arr[5] = { 2,4,5,6,7 };
	L.data = arr;
	L.length = 5;
	PrintList(L);

	Del_s_t(L, 3, 6);
	PrintList(L);
}

//2_6 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同
bool Delete_same(SqList& L) {
	int k = 0;
	for (int i = 0;i < L.length;i++) {
		if (L.data[i] != L.data[i + 1]) {
			L.data[k] = L.data[i];
			k++;
		}
	}
	L.length = k;
	return true;
}
void test2_6() {
	SqList L;
	InitList(L);
	ElemType arr[5] = { 4,4,4,7,7 };
	L.data = arr;
	L.length = 5;
	PrintList(L);

	Delete_same(L);
	PrintList(L);
}

//2_7 将两个有序顺序表合并为一个新的有序顺序表，并有函数返回结果顺序表
bool Merge(SqList A, SqList B, SqList& C) {
	if (A.length + B.length > C.initsize) {
		return false;
	}
	int i = 0, j = 0, k = 0;
	for (;j < A.length && k<B.length;i++) {
		if (A.data[j] <= B.data[k]) {
			C.data[i] = A.data[j];
			j++;
		}
		else {
			C.data[i] = B.data[k];
			k++;
		}
	}
	cout << i << endl;
	if (j >= A.length) {
		while (k < B.length) {
			C.data[i++] = B.data[k++];
		}
	}
	if (k >= B.length) {
		while (j < A.length) {
			C.data[i++] = B.data[j++];
		}
	}
	C.length = i;
	return true;
}
void test2_7() {
	ElemType arr1[5] = { 2,4,5,6,7 };
	ElemType arr2[5] = { 3,9,10, };
	//创建顺序表A
	SqList A,B,C;
	InitList(A);
	A.data = arr1;
	A.length = 5;
	PrintList(A);
	//创建顺序表B
	InitList(B);
	B.data = arr2;
	B.length = 3;
	PrintList(B);

	InitList(C);
	Merge(A, B, C);
	PrintList(C);
}
int main() {
	test2_7();
	return 0;
}