一、数据结构顺序表的实现

// Created by XuYiMing on 2020/2/2.
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

////////////////////顺序表///////////////////////////
#define InitSize 1000 //表长初始定义
typedef int ElemType; //在此例中数据类型使用int

typedef struct { //顺序表的定义
ElemType *data; //指示动态分配数组的指针
int length; //表当前长度
int MaxSize; //表当前分配的最大长度
} SeqList; //动态分配数组顺序表的类型定义

int InitList(SeqList &L) { //初始化线性表,这里如果采用SeqList *L,则调用时则为 L->data
L.data = (ElemType *) malloc(InitSize * sizeof(ElemType)); //这里数组是从0开始的,如果从1开始,则要为(InitSize+1)
if (L.data == nullptr) { //nullptr表示空指针,在C++中可以避免二义性问题
printf("内存分配错误!\n");
return 0;
}
L.length = 0;
L.MaxSize = InitSize;
printf("内存分配成功!\n");
return 1;
}

int ListInsert(SeqList &L, int i, ElemType e) { //线性表的插入,在指定位置插入某值(1<=i<=L.length)
if (i < 1 || i > L.length + 1) { //这里的i表示的是逻辑上的位置,而实际存储的是物理上的位置
printf("插入位置不合理!\n"); //判断插入的地址是否为负数或有间隔
return 0;
}
if (i >= L.MaxSize) {
printf("存储空间已满!\n");
return 0;
}
for (int j = L.length; j >= i; j--) { //平均插入时间为O(n)
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return 1;
}

int ListDelete(SeqList &L, int i, ElemType &e) { //线性表的删除,在指定位置删除某值(1<=i<=L.length)
if (i < 1 || i > L.length + 1) {
printf("删除位置不合理!\n");
return 0;
}
e = L.data[i - 1];
for (int j = i; j <= L.length; j++) { //平均删除时间为O(n)
L.data[j - 1] = L.data[j];
}
L.length--;
return e;
}

int ListLength(SeqList &L) { //求表长,计算元素个数
if (L.length == 0) {
printf("元素个数为0");
return 0;
}
int count = 0;
for (int i = 0; i < L.length; i++) {
if (L.data[i]) {
count++;
}
}
return count;
}

int locateElem(SeqList &L, ElemType e) { //按值查找逻辑下标
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1; //返回逻辑位置
}
}
return 0;
}

int GetElem(SeqList &L, int i) { //按位置查找
if (i < 1 || i > L.length) {
return 0;
}
return L.data[i - 1];
}

void PrintList(SeqList L) { //从前到后输出值
if (L.length == 0) {
cout << "顺序表为空";
exit(1);
}
printf("顺序表如下:");
for (int i = 0; i < L.length; i++) {
printf(" %d", L.data[i]);
}
cout << endl;
}

//////////////////第19页综合应用题////////////////////
//顺序表删除最小值,把最后一个值填补最小值的位置
int test1(SeqList &L, ElemType &value) {
if (L.length == 0) {
return false;
}
value = L.data[0];
int pos = 0;
for (int i = 0; i < L.length; i++) {
if (L.data[i] < value) {
value = L.data[i];
pos = i;
}
}
L.data[pos] = L.data[L.length - 1];
L.length--;
return true;
}

//把顺序表逆置,要求时间复杂度为O(1)
void test2(SeqList &L) {
ElemType temp;
for (int i = 0; i < L.length / 2; i++) {
temp = L.data[i];
L.data[i] = L.data[L.length - i - 1];
L.data[L.length - i - 1] = temp;
}
}

//线性表删除所有值为x的数据元素,要求时间复杂度O(n),空间复杂度O(1)
void test3(SeqList &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;
//法二
// int k = 0, i = 0;
// while (i < L.length) {
// if (L.data[i] == x) {
// k++;
// } else {
// L.data[i - k] = L.data[i];
// i++;
// }
// }
// L.length -= k;
}

//有序顺序表中,删除元素的值在s和t之间的所有元素(不包括s和t)
int test4(SeqList &L, ElemType s, ElemType t) {
int i, j;
if (s >= t || L.length == 0)
return false;
for (i = 0; i < L.length && L.data[i] < s; i++);
if (i >= L.length)
return false;
for (j = i; j < L.length && L.data[j] <= t; j++);
for (; j < L.length; i++, j++)
L.data[i] = L.data[j];
L.length = i;
return true;
}

//顺序表中,删除元素的值在s和t之间的所有元素(包括s和t)
int test5(SeqList &L, ElemType s, ElemType t) {
int i, k = 0;
if (L.length == 0 || s >= t)
return false;
for (i = 0; i < L.length; i++) {
if (L.data[i] >= s && L.data[i] <= t)
k++;
else
L.data[i - k] = L.data[i];
}
L.length -= k;
return true;
}

//删除有序顺序表中重复的元素,使其值均不同
int test6(SeqList &L) {
//法一
if (L.length == 0)
return 0;
int i, k = 0;
for (i = 1; i < L.length; i++) {
if (L.data[i] == L.data[i - 1]) {
k++;
} else {
L.data[i - k] = L.data[i];
}
}
L.length -= k;
return 1;

//法二
// if (L.length == 0)
// return 0;
// int i, j;
// for (i = 0, j = 1; j < L.length; j++) {
// if (L.data[i] != L.data[j])
// L.data[++i] = L.data[j];
// }
// L.length = i + 1;
// return 1;
}

//合并两个有序顺序表为一个有序顺序表
int test7(SeqList &L1, SeqList &L2, SeqList &L3) {
if (L1.length + L2.length > L3.MaxSize) {
return false;
}
int i = 0, j = 0, k = 0;
while (i < L1.length && j < L2.length) {
if (L1.data[i] <= L2.data[j]) {
L3.data[k++] = L1.data[i++];
} else {
L3.data[k++] = L2.data[j++];
}
}
while (i < L1.length) {
L3.data[k++] = L1.data[i++];
}
while (j < L2.length) {
L3.data[k++] = L2.data[j++];
}
L3.length = k;
return true;
}

//将数组A[m+n]中两个序列表位置整体互换
void Reverse(ElemType A[], int left, int right, int ArraySize) {
if (left >= right || right >= ArraySize) {
return;
}
int mid = (left + right) / 2;
for (int i = 0; i < mid - left; i++) {
ElemType temp = A[i];
A[i] = A[right - i];
A[right - 1] = temp;
}
}

void test8(ElemType A[], int m, int n, int ArraySize) {
Reverse(A, 0, m + n - 1, ArraySize);
Reverse(A, 0, n - 1, ArraySize);
Reverse(A, n, m + n - 1, ArraySize);
}

//用最少时间的方法查找x,找到则与后继交换位置,没找到则插入且任然递增有序
int test8(ElemType A[], ElemType x, int n) {
int low = 0, high = n - 1, mid;
mid = (low + high) / 2;
while (low <= high) { //二分法
if (A[mid] == x)
break;
else if (A[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
if (A[mid] == x && mid != n - 1) {
int t = A[mid];
A[mid] = A[mid + 1];
A[mid + 1] = t;
}
//不管是比A[0]小还是比A[n-1]大,都可以插入;因为当在A[0,n-1]之间找不到时,最后会出现low>high的情况
if (low > high) {
int i = 0;
for (i = n - 1; i > high; i--) {
A[i + 1] = A[i];
}
A[i + 1] = x;
}
return true;
}

int main() {
SeqList L;
InitList(L);
int i, e;
cout << "请输入元素个数:";
cin >> L.length;
for (i = 0; i < L.length; i++) {
scanf("%d", &L.data[i]);
}
PrintList(L);
// cout << "test6";
// test6(L);
// PrintList(L);
// cout << "请输入插入的位置和插入的元素:";
// scanf("%d%d", &i, &e);
// ListInsert(L, i, e);
// PrintList(L);
// cout << "请输入删除的位置:";
// scanf("%d", &i);
// ListDelete(L, i, e);
// cout << e << "被删除了!";
// PrintList(L);
return 0;
}