利用C++简单实现顺序表和单链表的示例代码

C++实现顺序表和单链表的示例代码 本文将为大家介绍如何使用C++语言实现顺序表和单链表，提供详细的示例代码供大家参考学习。 顺序表的实现 顺序表是一种常用的数据结构，使用数组来存储数据。下面是使用C++语言实现顺序表的示例代码： ```cpp class SeqList { public: SeqList() : _array(NULL), _size(0), _capacity(0) {} SeqList(const SeqList& s) { _array = (Datatype*)malloc(s._size * (sizeof(Datatype))); memcpy(_array, s._array, s._size * (sizeof(Datatype))); _size = _capacity = s._size; } SeqList& operator=(SeqList& s) { free(_array); Swap(s); return *this; } void Swap(SeqList& s) { _array = s._array; _size = s._size; _capacity = s._capacity; } ~SeqList() { if (_array) { free(_array); _array = NULL; _size = _capacity = 0; } } void Print() { for (size_t i = 0; i < _size; i++) { cout << _array[i] << " "; } cout << endl; } void CheckCapcacity() { if (_size == _capacity) { _capacity = 2 * _capacity + 3; _array = (Datatype*)realloc(_array, _capacity * sizeof(Datatype)); assert(_array); } } void PushBack(Datatype x) { Insert(_size, x); } void PushFront(Datatype x) { Insert(0, x); } void PopBack() { Erase(_size); } void PopFront() { Erase(0); } Datatype& operator[](size_t pos) { assert(pos < _size); return _array[pos]; } void Insert(size_t pos, Datatype x) { assert(pos <= _size); CheckCapcacity(); int end = (int)_size - 1; if (pos == 0) { while (end >= 0) { _array[end + 1] = _array[end]; end--; } _array[0] = x; } else { while (end >= (int)pos) { _array[end + 1] = _array[end]; end--; } _array[pos] = x; } _size++; } void Erase(size_t pos) { assert(pos < _size); if (_size > 0) { if (pos == 0) { int end = 0; while (end < (int)_size - 1) { _array[end] = _array[end + 1]; end++; } _size--; } else if (pos == _size) { _size--; } else { int end = (int)pos; while (end < (int)_size - 1) { _array[end] = _array[end + 1]; end++; } _size--; } } } }; ``` 单链表的实现 单链表是一种常用的数据结构，使用链表来存储数据。下面是使用C++语言实现单链表的示例代码： ```cpp class ListNode { public: Datatype data; ListNode* next; ListNode(Datatype x) : data(x), next(NULL) {} }; class LinkedList { public: LinkedList() : _head(NULL), _size(0) {} ~LinkedList() { while (_head) { ListNode* temp = _head; _head = _head->next; delete temp; } } void PushFront(Datatype x) { ListNode* node = new ListNode(x); node->next = _head; _head = node; _size++; } void PushBack(Datatype x) { ListNode* node = new ListNode(x); if (!_head) { _head = node; } else { ListNode* temp = _head; while (temp->next) { temp = temp->next; } temp->next = node; } _size++; } void PopFront() { if (_head) { ListNode* temp = _head; _head = _head->next; delete temp; _size--; } } void PopBack() { if (_head) { if (_head->next == NULL) { delete _head; _head = NULL; _size--; } else { ListNode* temp = _head; while (temp->next->next) { temp = temp->next; } delete temp->next; temp->next = NULL; _size--; } } } ListNode* Find(size_t pos) { ListNode* temp = _head; size_t i = 0; while (temp && i < pos) { temp = temp->next; i++; } return temp; } }; ``` 总结 通过上面的示例代码，我们可以看到如何使用C++语言实现顺序表和单链表。顺序表使用数组来存储数据，而单链表使用链表来存储数据。两种数据结构都可以用于存储和管理大量数据。 优点 * 顺序表可以快速访问任何一个元素，因为数组的索引可以快速计算。 * 单链表可以快速插入和删除元素，因为链表可以快速改变指针的指向。 缺点 * 顺序表需要预先分配固定的内存空间，可能会浪费内存。 * 单链表需要更多的内存来存储链表的指针，可能会浪费内存。 应用 * 顺序表可以用于实现数组、矩阵和向量等数据结构。 * 单链表可以用于实现链表、栈和队列等数据结构。 希望本文能够帮助大家更好地理解顺序表和单链表的实现原理和应用场景。