線性表是n個相同數(shù)據(jù)類型的元素組成的有限序列冠息。
線性表按照存儲結(jié)構(gòu)可分為順序表和鏈表。
順序表都是內(nèi)存地址連續(xù)的元素組成的孕索！
順序表的構(gòu)建
- 定義元素個數(shù)和順序表最大容量，初始化指針
- 在構(gòu)造函數(shù)中傳參來確定size躏碳；length設(shè)為0搞旭；初始化指針地址。
#include <iostream>
#include <cstring>
using namespace std;
class Vector {
private:
int size, length;
int *data;
public:
Vector(int input_size) {
size = input_size;
length = 0;
data = new int[size];
}
~Vector() {
delete[] data; // 析構(gòu)函數(shù)中進行刪除
}
};
int main() {
Vector a(2);
return 0;
}
順序表的插入:
在insert方法中定義了參數(shù)loc菇绵，value肄渗。loc為插入的位置，value代表插入的數(shù)值咬最。每次插入都要將序列l(wèi)oc之后的元素向后移動一位翎嫡，并且長度length增加1。成功返回true永乌，否則false惑申。
-
判斷l(xiāng)oc位置是否合法。位于0到length之間（包括length）翅雏，有元素在序列上才可以進行插入圈驼，所以開始為空時要順序插入。并且元素左右兩邊都可插入（所以位置為length時依然合法）望几。 -
判斷元素個數(shù)是否超出最大容量（長度相等時就不能插入了绩脆，再插溢出）。 - 將loc（包括loc）之后的元素
右移。 - 插入
賦值靴迫。 - 元素
個數(shù)加1惕味。
在構(gòu)造函數(shù)中添加insert方法
bool insert(int loc, int value) {
if(loc < 0 || loc > length){
return false;
}
if (length >= size){
return false;
}
for (int i = length; i > loc; i--){
data[i] = data[i-1];
}
data[loc] = value;
length += 1;
return true;
}
順序表的擴容：
通產(chǎn)來說，擴容通常是將容量修改為以前的兩倍玉锌；擴容時要重新開辟一塊空間并把原有數(shù)據(jù) 依次 拷貝過去名挥，再將原來的 空間 釋放
- 保存原始數(shù)據(jù)到
舊指針。 - 容量
加倍芬沉。 - 指針指向新size
開辟的新空間躺同。 - 數(shù)據(jù)
拷貝。 - 在insert中
調(diào)用 回收
bool insert(int loc, int value) {
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
//return false;
expand();
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}
void expand(){
int *old_data = data
size = size * 2;
data = new int[size] ;
for(int i = 0; i <length;i ++){
data[i] = old_data[i];
}
delete[] old_data;
}
順序表的查找
接收一個int類型的value丸逸，返回該值對應(yīng)的下表蹋艺，沒有返回－1
從零循環(huán)到小于length，枚舉匹配：
int search(int value) {
for(int i=0; i < length; i++){
if (data[i] == value){
return i
}
}
return -1;
}
順序表的刪除：index之后的元素向前移動一位黄刚。
-
判斷index是否在元素中 - index之后的元素向
前移動 - 元素個素
減1捎谨，返回true
bool remove(int index) {
if(index < 0 || index >= length){
return false
}
for(int i = index + 1; i < length; i++){
data[i-1] = data[i];
}
length -= 1;
return true;
}
順序表的遍歷
把順序表的所有元素輸出到一行，并用空格分開憔维。
- 判斷第一個元素涛救，不要輸出空格
- 循壞遍歷輸出
void print() {
for(int i = 0; i<length; i++){
if(i > 0){
cout << " ";
}
cout << data[i];
}
cout << endl; //輸出空行
}
完整代碼：
#include <iostream>
#include <cstring>
using namespace std;
class Vector {
private:
int size, length;
int *data;
public:
Vector(int input_size) {
size = input_size;
length = 0;
data = new int[size];
}
~Vector() {
delete[] data;
}
bool insert(int loc, int value) {
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
return false;
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}
int search(int value) {
for (int i = 0; i < length; ++i) {
if (data[i] == value) {
return i;
}
}
return -1;
}
bool remove(int index) {
if (index < 0 || index >= length) {
return false;
}
for (int i = index + 1; i < length; ++i) {
data[i - 1] = data[i];
}
length = length - 1;
return true;
}
void print() {
for(int i = 0; i<length; i++){
if(i > 0){
cout << " ";
}
cout << data[i];
}
cout << endl
}
};
int main() {
Vector a(2);
cout << a.insert(0, 1) << endl;
cout << a.insert(0, 2) << endl;
a.print();
cout << a.remove(1) << endl;
a.print();
cout << a.search(0) << endl;
cout << a.search(1) << endl;
return 0;
}
引用：計蒜客
