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;
}