C++实现动态顺序表（vector）

2024-10-21 01:13:29

vector是连续存储结构，支持随机的高效的随机和在尾部进行插入、删除操作，其它位置的插入、删除操作相对来说效率较低。

vector相当于一个数组，但它的数组空间大小需要写一程序来实现。

它的内存分配原理大概可分为下面几步：

1）首先分配一块内存空间进行存储；
2）当所需存储的数据超过分配的空间时，再重新分配一块空间；
3）将旧元素复制到新空间；
4）释放旧空间。

实现代码如下：

vector.h

#pragma once

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<iostream>
using namespace std;

typedef int DataType;

class Vector
{
public:
 Vector()
  :_first(NULL),
  _finish(NULL),
  _endofstorage(NULL)
 {}

 Vector(const Vector& v){
  if (v.Size() > 0){
   _first = new DataType(v.Size());
   memcpy(_first, v._first, sizeof (DataType)*v.Size());
  }
  if (_first > 0){
   _finish = _first + v.Size();
   _endofstorage = _first + v.Size();
  }
  _first = _finish = _endofstorage = NULL;
 }

 Vector& operator=(const Vector& v){
  if (this != &v){
   /*swap(_first, v._first);
   swap(_finish, v._finish);
   swap(_endofstorage, v._endofstorage);*/

   DataType* tmp = new DataType(v.Size());
   memcpy(tmp, _first, sizeof(DataType)*v.Size());
   delete _first;
   _first = tmp;
   _finish = _first + v.Size();
   _endofstorage = _first + v.Size();
  }
  return *this;
 }

 ~Vector(){
  delete[] _first;
  _first = _finish = _endofstorage = NULL;
 }

 void Print(){
  DataType* cur = _first;
  while (cur != _first){
   cout << "*cur" << endl;
   cur++;
  }
  cout << endl;
 }

 size_t Size() const{
  return _finish - _first;
 }

 size_t Capacity() const{
  return _endofstorage - _first;
 }

 void Expand(size_t n){
  if (n > Capacity()){
   DataType* tmp = new DataType(n);
   size_t size = Size();
   memcpy(tmp, _first, sizeof(DataType)*size);
   delete[] _first;
   _first = tmp;
   _finish = _first + size;
   _endofstorage = _first + n;
  }
 }

 void PushBack(DataType x){
  if (_finish == _endofstorage){
   size_t capacity = Capacity() > 0 ? Capacity() * 2 : 3;
   Expand(capacity);
   /*if (Capacity() == 0){
    Expand(3);
   }
   else{
    Expand(Capacity() * 2);
   }*/
  }
  *_finish = x;
  ++_finish;
 }

 void PopBack(){
  assert(_finish > _first);
  --_finish;
 }

 void Reserve(size_t n){
  if (n > Capacity()){
   Expand(n);
  }
 }

 void Insert(size_t pos, DataType x){
  assert(pos < Size());
  if (_finish = _endofstorage){
   size_t capacity = Capacity() > 0 ? Capacity() * 2 : 3;
   Expand(capacity);
  }
  int tmp = Size() - 1;
  while (tmp >= (int)pos){
   _first[tmp + 1] = _first[tmp];
   --tmp;
  }
  _first[pos] = x;
  ++_finish;
 }

 void Erase(size_t pos){
  assert(pos < Size());
  size_t cur = pos;
  while (cur < Size()-1){
   _first[cur] = _first[cur] + 1;
   ++cur;
  }
  --_finish;
 }

 size_t Find(DataType x){
  DataType *cur = _first;
  while (cur != _finish){
   if (*cur == x){
    return cur - _first;
   }
   ++cur;
  }
  return -1;
 }
private:
 DataType* _first;
 DataType* _finish;
 DataType* _endofstorage;
};

test.cpp

#include"vector.h"

void Tset(){
 Vector v;
 v.PushBack(1);
 v.PushBack(2);
 v.PushBack(3);
 v.PushBack(4);
 v.PopBack();
 v.Print();

 size_t pos = v.Find(1);
 printf("pos->data:expcet 1,axtual %lu", pos);

 Vector v1;
 v1.Insert(1, 0);
 v1.Print();

 Vector v2;
 v2.Erase(3);
 v2.Print();
}

int main(){
 Tset();
 return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

如何在C++中建立一个顺序表

准备数据复制代码代码如下: #define MAXLEN 100 //定义顺序表的最大长度struct DATA{ char key[10]; //结点的关键字 char name[20]; int age;};struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 int ListLen; //顺序表已存结点的数量 }; 定义了顺序表的最大长度MAXLEN.顺序表数据元素的类型DATA以及顺序表的数据结构SLTyp
C++实现基于静态数组的顺序表

本文实例为大家分享了C++实现基于静态数组的顺序表,供大家参考,具体内容如下实现的基本操作有: 1. 初始化 2. 尾插 3. 尾删 4. 头插 5. 头删 6.查找任意元素 7. 读任意位置元素 8. 修改任意位置元素 9. 查找指定元素值的下标 10. 在任意位置插入元素 11.删除指定位置的元素 12.删除任意元素 13.打印数据头文件seqlist.h: #pragma once #include<stdio.h> #include<stdlib.h> #include
C++实现动态顺序表

本文实例为大家分享了C++实现动态顺序表的具体代码,供大家参考,具体内容如下 Vector.h #pragma once #include <stdio.h> #include <iostream> #include <assert.h> #include <string.h> using namespace std; typedef int DataType; class Vector { public: Vector() :_first(NULL) ,
利用C++简单实现顺序表和单链表的示例代码

本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍: 一.顺序表示例代码: #include <assert.h> #include <iostream> using namespace std; typedef int Datatype; class SeqList { public: SeqList() :_array(NULL) ,_size(0) ,_capacity(0) { } SeqList(const
C++顺序表的基本操作（使用模版类）

本文实例为大家分享了C++顺序表的基本操作,供大家参考,具体内容如下一.遇到问题: 原因:类的函数定义不能放在SeqList.cpp中,必须放在Seqlist.h(类的函数声明和定义放在同一个文件下)中,否则会出现以下问题. 二.实现程序: 1.SeqList.h #ifndef SeqList_h #define SeqList_h #include <iostream> using namespace std; const int defaultSize = 100; template
C++实现顺序表的常用操作(插入删出查找输出)

实现顺序表的插入,删除,查找,输出操作在C语言中经常用到.下面小编给大家整理实现代码,一起看下吧代码如下所示: #include<iostream> using namespace std; #define MAXSIZE 15 typedef int DataType; typedef struct { DataType data[MAXSIZE]; //通常用一位数组来描述顺序表的数据存储 int SeqLength; /*线性表长度*/ } SeqList; SeqList *Init
C++实现顺序表的方法

废话不多说了,直接给大家上关键代码了. #pragma once #include <assert.h> template<class T> class SeqList { public: SeqList() :_a(NULL) ,_size(1) ,_capacity(1) {} SeqList(T* a, size_t size) :_a(new T[size]) ,_size(size) ,_capacity(size) { for (size_t i = 0; i <
C++顺序表的实例代码

本文实例为大家分享了C++实现顺序表的具体代码,供大家参考,具体内容如下 #include <iostream> using namespace std; typedef int DataType; class SeqList { public: SeqList() :_a(NULL) , _size(0) , _capacity(0) {} SeqList(const SeqList& s) :_a(new DataType[s._size]) , _size(s._size) ,
C语言实现动态顺序表详解

目录什么是顺序表? 1. 定义顺序表结构体: 2. 初始化顺序表: 3. 销毁顺序表: 4. 打印顺序表: 5. 判断容量+扩容: 6. 头插数据: 7. 尾插数据: 8. 指定下标位置插入数据: 9. 删除数据: 10. 尾删数据: 11. 指定下标位置删除数据: 12. 查找数据: 13. 修改数据: 14. 源代码: 1. SeqList.h: 2. SeqList.cpp: 3. test.cpp: 15. 测试: 总结什么是顺序表? 顺序表是在计算机内存中以数组的形式保存的线性表,
C语言实现动态顺序表的实现代码

C语言实现动态顺序表的实现代码顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 静态实现:结构体内部只需两个成员,其中一个为固定大小(MAX)的数组,用来存放我们的数据.数组大小我们可以通过在头文件中改变MAX的值来改变. 动态实现:在内存中开辟一块空间,可以随我们数据数量的增多来扩容. 来看看动态的顺序表实现: 1.seqli
新手向超详细的C语言实现动态顺序表

目录一.各个函数接口的实现 1.1 不太好''李姐''的"容量检测函数" 1.2 在任意位置插入的函数"坑!" 1.3 在任意位置删除数据的函数 1.4 其余简单的接口函数二.顺序表结构体声明与定义三.头文件的调用一.各个函数接口的实现 1.1 不太好''李姐''的"容量检测函数" 对顺序表进行插入数据时,需要判断顺序表的容量是否充足,增加数据的同时需要反复地检测容量,所以推荐直接将以上步骤封装成一个函数. 函数实现算法:若容量大小 ==
C语言动态顺序表实例代码

目录顺序表概念: 一.准备工作二.顺序表的基本操作 1.顺序表的初始化函数 2.尾插函数(在尾部插入数据) 3.头插函数(在数组头部插入数据) 4.尾删函数 5.头删函数 6.在第pos的位置插入数据 7.删除第pos个位置的数据 8.修改第pos个位置的数据 9.查找函数. 10.销毁函数 11.打印函数三.总代码: 顺序表概念: 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构.一般情况下用数组存储.在数组上完成数据的增删查改. 代码解析: 一.准备工
C语言实现动态顺序表的示例代码

目录顺序表概念及结构基本操作功能实现程序运行顺序表概念及结构顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改. 分类: 一般分为静态顺序表和动态顺序表: 静态顺序表:数组大小是固定的用完了无法增容:同时我们无法控制给数组开多少空间合适,开少了,空间不够:开多了,有回会存在空间浪费: 动态顺序表:空间是可以变动的,空间满了我们就增容:解决了静态顺序表的空间不足问题,同时也在一定程度上减少了空间浪费: 因此本篇博客主要实现
C++实现动态顺序表（vector）

vector是连续存储结构,支持随机的高效的随机和在尾部进行插入.删除操作,其它位置的插入.删除操作相对来说效率较低. vector相当于一个数组,但它的数组空间大小需要写一程序来实现. 它的内存分配原理大概可分为下面几步: 1)首先分配一块内存空间进行存储: 2)当所需存储的数据超过分配的空间时,再重新分配一块空间: 3)将旧元素复制到新空间: 4)释放旧空间. 实现代码如下: vector.h #pragma once #include<stdio.h> #include<asser
C语言实现静态顺序表的实例详解

C语言实现静态顺序表的实例详解线性表定义一张顺序表也就是在内存中开辟一段连续的存储空间,并给它一个名字进行标识.只有定义了一个顺序表,才能利用该顺序表存放数据元素,也才能对该顺序表进行各种操作. 接下来看看静态的顺序表,直接上代码: SeqList.h #define _CRT_SECURE_NO_WARNINGS 1 #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include <stdio.h> #include <stdlib.h&g
Python中顺序表原理与实现方法详解

本文实例讲述了Python中顺序表原理与实现方法.分享给大家供大家参考,具体如下: Python中的顺序表 Python中的list和tuple两种类型采用了顺序表的实现技术,具有顺序表的所有性质. tuple是不可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作,而其他方面,则与list的性质类似. list的基本实现技术 Python标准类型list就是一种元素个数可变的线性表,可以加入和删除元素,并在各种操作中维持已有元素的顺序(即保序),而且还具有以下行为特征: 基于下标(位置
什么是Python中的顺序表

1.顺序表介绍顺序表是最简单的一种线性结构,逻辑上相邻的数据在计算机内的存储位置也是相邻的,可以快速定位第几个元素,中间不允许有空,所以插入.删除时需要移动大量元素.顺序表可以分配一段连续的存储空间Maxsize,用elem记录基地址,用length记录实际的元素个数,即顺序表的长度上图1表示的是顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc (e0)加上逻辑地址(第i个元

C++实现动态顺序表（vector）

相关推荐

随机推荐