總結(jié)歸納

• 動態(tài)分配對內(nèi)存有著更大的控制權(quán)，但也會花費相應(yīng)的時間。
• 順序表的查找時間復(fù)雜度為O(1)，這是單鏈表所不具備的。
• 順序表的插入，要從后往前遍歷，因為數(shù)據(jù)要后移；順序表的刪除，要從前往后遍歷，因為數(shù)據(jù)要前移。

/*
順序表————動態(tài)分配
*/

define InitSize 5 // 順序表初始長度

include <iostream>

include <stdio.h>

using namespace std;

struct SqList {
int *data; // 數(shù)組
int MaxSize; // 順序表的最大長度
int length; // 順序表的當(dāng)前長度
};

// 初始化順序表
void InitList(SqList &L) {
L.data = new int[InitSize];
L.MaxSize = InitSize;
L.length = 0;
}

// 為順序表中的數(shù)據(jù)賦值
void AssginList(SqList &L) {
for (int i = 0; i < InitSize; i++) {
L.data[i] = i;
L.length++;
}
}

// 求表長
int Length(SqList &L) { return L.length; }

// 動態(tài)增加順序表長度
void IncreaseSize(SqList &L, int len) {
int *p = L.data;
L.data = new int[L.MaxSize + len];
for (int i = 0; i < L.length; i++) {
L.data[i] = p[i]; // 將原數(shù)據(jù)賦值到新內(nèi)存中
}
L.MaxSize = L.MaxSize + len;
delete p;
}

// 按位查找：查找第i個位置的元素
int GetElem(SqList &L, int i) {
return L.data[i - 1];
}

// 按值查找：查找值為i的元素位置
int LocateElem(SqList &L, int i) {
for (int j = 0; j < L.length; j++) {
if (L.data[j] == i) {
return j + 1;
}
}
return 0; // 沒有查找到則返回0
}

// 插入：在第i個位置插入e
void ListInsert(SqList &L, int i, int e) {
if (L.length = L.MaxSize) { // 內(nèi)存已滿需要擴(kuò)充
IncreaseSize(L, 1);
}
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1]; // 插入位置之后的數(shù)據(jù)后移
}
L.data[i - 1] = e;
L.length++;
}

// 刪除：刪除第i個位置的元素
bool ListDelete(SqList &L, int i, int &e) {
if (i < 0 || 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]; // 數(shù)據(jù)前移
}
L.data[L.length] = 0; //最后一個元素初始化
L.length--;
return true;
}

// 按順序輸出
void PrintList(SqList &L) {
for (int i = 0; i < L.length; i++) {
cout << L.data[i] << " ";
}
cout << endl;
}

int main() {
struct SqList L;

InitList(L);
AssginList(L);
PrintList(L);

// 求表長
int len = Length(L);
cout << "表長：" << len << endl;

// 插入數(shù)據(jù)
ListInsert(L, 3, 44);
Length(L);
PrintList(L);

// 刪除數(shù)據(jù)
int e = -1;
if (ListDelete(L, 3, e)) {
    cout << "刪除的數(shù)據(jù)：" << e << endl;
    PrintList(L);
} else {
    cout << "刪除數(shù)據(jù)超出范圍" << endl;
}

// 按值查找
int locate_elem;
locate_elem = LocateElem(L, 3);
cout << "查找到的位置：" << locate_elem << endl;

// 按位查找
int get_elem;
get_elem = GetElem(L, 3);
cout << "查找到的數(shù)據(jù)：" << get_elem << endl;

}