#include <iostream>
using namespace std;
struct SqList {
int* elem;
int length;
int listsize;
};
int InitList_Sq(SqList &L) { //构造空表
L.elem = 0;
L.length = 0;
L.listsize = 0;
return 1;
}
int InsertList_Sq(SqList &L, int i, int x) { //在第i个位置插入x
if (L.listsize == 0) {
L.elem = new int[1];
L.listsize = 1;
}
if (i<0 || i>L.length) return 0;
if (L.length == L.listsize) {
int* newbase = new int[L.listsize * 2];
if (newbase == 0) return 0;
for (int j = 0; j < L.length; ++j) {
newbase[j] = L.elem[j];
}
delete L.elem;
L.elem = newbase;
L.listsize *= 2;
}
for (int j = L.length; j > i; --j) {
L.elem[j] = L.elem[j - 1];
}
L.elem[i] = x;
L.length++;
return 1;
}
int DeleteList_Sq(SqList& L, int i, int& x) { //删除第i个元素并用x返回删除的元素
if (i<0 || i>L.length - 1) return 0;
x = L.elem[i];
for (int j = i; j < L.length - 1; ++j) {
L.elem[j] = L.elem[j + 1];
}
L.length--;
return 1;
}
int DeleteList_Sq(SqList& L, int i) { //重载删除第i个元素不返回元素内容
if (i<0 || i>L.length - 1) return 0;
for (int j = i; j < L.length - 1; ++j) {
L.elem[j] = L.elem[j + 1];
}
L.length--;
return 1;
}
void PrintList_Sq(SqList L) { //打印顺序表
for (int i = 0; i < L.length; ++i) {
if (i) cout << ' ';
cout << L.elem[i];
}
cout << endl;
}
int FindElem(SqList L, int x) { // 查找x返回下标
int i;
for (i = 0; i < L.length - 1; ++i) {
if (x == L.elem[i]) return i;
}
return -1;
}
void UnionLists_Sq(SqList A, SqList B, SqList &C) { //合并两个有序表，并使其合并后依然有序
int i = 0, j = 0,k = 0, m = A.length, n = B.length;
while (i < m && j < n) {
if (A.elem[i] <= B.elem[j]) {
InsertList_Sq(C, k++, A.elem[i++]);
}
else {
InsertList_Sq(C, k++, B.elem[j++]);
}
}
if (j == n) {
while (i < m) {
InsertList_Sq(C, k++, A.elem[i++]);
}
}
if (i == m) {
while (j < n) {
InsertList_Sq(C, k++, B.elem[j++]);
}
}
}
void UnionLists2(SqList &A, SqList B) { // 将在B中不在A中的元素插入到A中
int i;
for (i = 0; i < B.length; ++i) {
if (FindElem(A, B.elem[i]) == -1) {
InsertList_Sq(A, A.length, B.elem[i]);
}
}
/*
int i, j;
for (j = 0; j < B.length; ++j) {
for (i = 0; i < A.length; ++i) {
if (A.elem[i] == B.elem[i]) break;
else {
InsertList_Sq(A,A.length, B.elem[j]);
break;
}
}
}
*/
}
void DeleteElem(SqList& L) { //删除重复元素
for (int i = 0; i < L.length; ++i) {
for (int j = i + 1; j < L.length; ++j) {
if (L.elem[i] == L.elem[j]) {
DeleteList_Sq(L, j);
j--;
}
}
}
}
int main() {
SqList LA, LB, LC, LD;
InitList_Sq(LA);
InitList_Sq(LB);
InitList_Sq(LC);
// InitList_Sq(LD);
int a[4] = { 3,4,8,11 };
int b[7] = { 2,6,8,9,11,15,20 };
for (int i = 0; i < 4; ++i) {
InsertList_Sq(LA, LA.length, a[i]);
}
PrintList_Sq(LA);
for (int i = 0; i < 7; ++i) {
InsertList_Sq(LB, LB.length, b[i]);
}
PrintList_Sq(LB);
int k;
k = FindElem(LB, 15);
cout << k << endl;
int x;
DeleteList_Sq(LB, 5, x);
cout << x << endl;
PrintList_Sq(LB);
UnionLists_Sq(LA, LB, LC);
PrintList_Sq(LC);
DeleteElem(LC);
PrintList_Sq(LC);
// UnionLists2(LA, LB);
// PrintList_Sq(LA);
return 0;
}
