手撕顺序表

分类

概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。

接口声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;typedef struct SeqList {SLDataType* a;size_t size; //有效数据size_t capacity; //空间容量
}SL;void SLInit(SL* psl);//初始化
void SLDestroy(SL* psl); //销毁void SLPrint(SL* psl);//打印
void SLCheckCapacity(SL* psl);//扩容void SLPushBack(SL* psl, SLDataType x);//尾插
void SLPushFront(SL* psl, SLDataType x);//头插void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删int SLFind(SL* psl, SLDataType x);//找到第一个和x相等的下标
void SLInsert(SL* psl, int pos, SLDataType x);//插入
void SLErase(SL* psl, int pos);//删除

接口实现

#include"SeqList.h"void SLInit(SL* psl) {assert(psl);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}void SLDestroy(SL* psl) {assert(psl);if (psl->a != NULL) {free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;}
}void SLPrint(SL* psl) {assert(psl);for (int i = 0; i < psl->size; i++) {printf("%d ", psl->a[i]);}printf("\n");
}void SLCheckCapacity(SL* psl) {assert(psl);if (psl->size == psl->capacity) {//有效数据等于空间容量时需要扩容size_t NewCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//二倍扩容SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * NewCapacity);if (tmp == NULL) {perror("realloc fail");return;}psl->a = tmp;psl->capacity = NewCapacity;}
}void SLPushBack(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);psl->a[psl->size ++] = x;
}void SLPushFront(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);++ psl->size;for (size_t i = psl->size - 1; i > 0; i--) {psl->a[i] = psl->a[i - 1];}psl->a[0] = x;
}void SLPopBack(SL* psl) {assert(psl);assert(psl->size > 0);psl->size--;
}void SLPopFront(SL* psl) {assert(psl);assert(psl->size > 0);for (int i = 0; i < psl->size - 1; i++) {psl->a[i] = psl->a[i + 1];}psl->size--;
}int SLFind(SL* psl, SLDataType x) {assert(psl);for (int i = 0; i < psl->size; i++) {if (psl->a[i] == x) {return i;}}return -1;
}void SLInsert(SL* psl, int pos, SLDataType x) {assert(psl);assert(pos >= 0&& pos < psl->size);SLCheckCapacity(psl);psl->size++;for (size_t i = psl->size - 1; i > pos;i --) {psl->a[i] = psl->a[i - 1];}psl->a[pos] = x;
}void SLErase(SL* psl, int pos) {assert(psl);assert(pos >= 0 && pos < psl->size);for (int i = pos; i < psl->size - 1; i++) {psl->a[i] = psl->a[i + 1];}psl->size --;
}

接口测试

#include"SeqList.h"void test1() {SL p;SLInit(&p);SLPushBack(&p, 1);SLPushBack(&p, 3);SLPushBack(&p, 1);SLPushBack(&p, 4);SLPushFront(&p, 0);SLPushFront(&p, 2);SLPushFront(&p, 5);SLPrint(&p);SLDestroy(&p);
}void test2() {SL p;SLInit(&p);SLPushBack(&p, 1);SLPushBack(&p, 3);SLPushBack(&p, 1);SLPushBack(&p, 4);SLPushFront(&p, 0);SLPushFront(&p, 2);SLPushFront(&p, 5);SLPrint(&p);SLPopBack(&p);SLPopBack(&p);SLPrint(&p);SLPopFront(&p);SLPopFront(&p);SLPrint(&p);SLDestroy(&p);
}void test3() {SL p;SLInit(&p);SLPushBack(&p, 1);SLPushBack(&p, 3);SLPushBack(&p, 1);SLPushBack(&p, 4);SLPushFront(&p, 0);SLPushFront(&p, 2);SLPushFront(&p, 5);SLPrint(&p);int pos = SLFind(&p, 2);if(pos >= 0) SLErase(&p, pos);pos = SLFind(&p, 8);if (pos >= 0) SLErase(&p, pos);SLPrint(&p);SLInsert(&p, 4, 10);SLPrint(&p);SLInsert(&p, 2, 16);SLPrint(&p);SLDestroy(&p);
}int main() {test3();return 0;
}

vector

vector 为C++ STL中封装的一个类，它的功能类似于动态的顺序表，接下来我们进行实现一下。

封装实现

#pragma once
#include<assert.h>
#include<initializer_list>namespace yxw {template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;//迭代器iterator begin() {return start;}iterator end() {return finish;}const_iterator begin() const {return start;}const_iterator end() const {return finish;}//构造函数vector() : start(nullptr), finish(nullptr), end_of_storage(nullptr) {}vector(const vector<T>& v) {reverse(v.capacity());for (auto& e : v) {//加引用防止浅拷贝push_back(e);}}//应对 vector<int> a = { 0， 1， 2， 3， 4}vector(std::initializer_list<T> v) {reverse(v.size());for (auto& e : v) {push_back(e);}}template<class InputIterator>vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first);++first;}}vector(size_t n, const T& val = T()) {reverse(n);for (size_t i = 0; i < n;i ++) {push_back(val);}}vector(int n, const T& val = T()) {//防止与上面模板发生冲突reverse(n);for (size_t i = 0; i < n; i++) {push_back(val);}}//主函数size_t size() const{ //有效数据大小return finish - start;}size_t capacity() const { //空间容量return end_of_storage - start;}bool empty() {return start == finish;}T& operator[](size_t pos) {assert(pos < size());return start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return start[pos];}void swap(vector<T>& v) {std::swap(start, v.start);std::swap(finish, v.finish);std::swap(end_of_storage, v.end_of_storage);}vector<T>& operator=(vector<T> v) {swap(v);return *this;}void reverse(size_t n) {if (n > capacity()) {T* tmp = new T[n];size_t old_size = size();for (size_t i = 0; i < size(); i++) {tmp[i] = start[i];}delete[]start;start = tmp;finish = tmp + old_size;end_of_storage = tmp + n;}}void resize(size_t n, const T& val = T()) {if (n > size()) {reverse(n);for (iterator it = finish; it != start + n; it++) {*it = val;}finish = start + n;}else {finish = start + n;}}//尾插void push_back(const T& val) {insert(end(), val);}//插入void insert(iterator pos, const T& val) {assert(pos >= start);assert(pos <= finish);if (finish == end_of_storage) {size_t len = pos - start;reverse(capacity() == 0 ? 4 : capacity() * 2);pos = start + len;//防止迭代器失效}++ finish;for (iterator it = finish - 1; it > pos; it --) {*it = *(it - 1);}*pos = val;}//尾删void pop_back() {erase(end() - 1);}//删除iterator erase(iterator pos) {assert(pos >= start);assert(pos < finish);--finish;for (iterator it = pos; it != finish; it++) {*it = *(it + 1);}return pos;}//析构函数~vector() {delete[] start;start = finish = end_of_storage = nullptr;}private:iterator start = nullptr;iterator finish = nullptr;iterator end_of_storage = nullptr;};
}

封装测试

#include<iostream>
#include<cstdio>
#include<vector>
#include"vector.h"void test1() {yxw::vector<int> a;a.push_back(1);a.push_back(3);a.push_back(1);a.push_back(4);a.insert(a.begin(), 0);a.insert(a.begin(), 2);a.insert(a.begin(), 5);for (int i = 0; i < a.size(); i++) {std::cout << a[i] << " ";}std::cout << "\n";for (yxw::vector<int>::iterator it = a.begin(); it != a.end(); it++) {std::cout << *it << " ";}std::cout << "\n";for (auto e : a) {std::cout << e << " ";}std::cout << "\n";
}void test2() {yxw::vector<int> a;a.push_back(1);a.push_back(3);a.push_back(1);a.push_back(4);a.insert(a.begin(), 0);a.insert(a.begin(), 2);a.insert(a.begin(), 5);for (auto e : a) {std::cout << e << " ";}std::cout << "\n";a.pop_back();a.pop_back();for (auto e : a) {std::cout << e << " ";}std::cout << "\n";a.erase(a.begin());for (auto e : a) {std::cout << e << " ";}std::cout << "\n";
}void test3() {std::vector<int> a;a.push_back(2);a.push_back(3);a.push_back(4);a.push_back(5);for (auto e : a) {std::cout << e << " ";}std::cout << "\n";a.resize(10, 1);for (auto e : a) {std::cout << e << " ";}std::cout << "\n";yxw::vector<int> b;b.push_back(1);b.push_back(2);b.push_back(3);b.push_back(4);b.push_back(5);for (auto e : b) {std::cout << e << " ";}std::cout << "\n";b.resize(10, 1);for (auto e : b) {std::cout << e << " ";}std::cout << "\n";
}void test4() {yxw::vector<int> a(10, 1);for (auto e : a) {std::cout << e << " ";}std::cout << "\n";
}void test5() {yxw::vector<std::string> a = { "yixuan", "shajdh", "jsdhkf", "kdshkf"};for (auto e : a) {std::cout << e << " ";}std::cout << "\n";}void test6() {yxw::vector<int> a(10, 1);yxw::vector<int> b(a.begin(), a.end());for (auto e : b) {std::cout << e << " ";}std::cout << "\n";
}void test7() {yxw::vector<int> a;a.push_back(1);a.push_back(3);a.push_back(1);a.push_back(4);a.insert(a.begin(), 0);a.insert(a.begin(), 2);a.insert(a.begin(), 5);yxw::vector<int>::iterator it = a.begin();while (it != a.end()) {if (*it % 2 == 0) {it = a.erase(it);//用完erase或者insert原来的迭代器可能会失效记得更新}else {++it;}}for (auto e : a) {std::cout << e << " ";}std::cout << "\n";
}int main() {test7();return 0;
}