数据结构基本概念

1 数据结构概述

数据结构是计算机组织（逻辑结构）、存储（物理结构）数据的方式。和具体的计算机编程语言无关，可以使用任何编程语言来实现数据结构

1.1 数据逻辑结构

反映数据元素之间的逻辑关系，逻辑关系和它们在计算机中的存储位置无关，常见的逻辑结构有：

线性结构：数据结构中的元素存在一对一的相互关系；

树形结构：数据结构中的元素存在一对多的关系；

图形结构：数据结构中的元素存在多对多的关系。

其中线性结构比较重要，应用的比较多

1.2 数据存储结构（物理结构）

数据的逻辑结构在计算机存储器中的存放形式称为数据的存储结构，又叫物理结构。

一般来说，一种逻辑结构根据需要可以表示成多种存储结构。常见的存储结构有：顺序存储、链式存储。

2 线性表

2.1 线性表的基本概念

线性表是由零个或多个数据元素组成的有序序列。

特点：

• 数据元素间是有顺序的；

• 数据元素的个数是有限的；

• 一般来说，数据元素的类型是相同的（强类型语言）。c/c++是强类型语言，必须指定数据类型。js、php、python等语言是弱类型就不需要指定数据类型。

2.2 数学定义

线性表是具有相同类型的n个元素的有限序列a1,a2,a3.....an,其中ai是表项，n是线性表的长度。

性质：其中a1为线性表中第一个元素，只有后继，没有前驱。

an为线性表中最后一个元素，只有前驱，没有后继。

除了a1和an，其他元素既有前驱又有后继。

2.3 线性表的顺序存储结构

线性表的顺序存储结构指的是用一段连续的存储空间来存储线性表中的数据元素，数组就是一个典型的顺序存储结构。有以下几个特点：

1.均匀性：所有元素类型相同，占用等长的存储单元，便于直接计算元素地址。

2.有序性：元素位置由序号唯一确定，仅首位元素无前驱或后继，其他元素有且仅有一个直接前驱和后继

3.随机存储：通过数组下标可以直接访问任意元素。

可以自己实现一个动态数组，初始化方法如下

头文件放函数声明：

class DynamicArray
{
private://成员变量int* data;//data指向存放数据元素的内存空间，堆区空间，数据元素类型默认是整数int size;//动态数组的大小，多少个数据元素，也就是线性表的长度int capacity;//动态数组容量
public://特殊成员函数DynamicArray();//无参构造DynamicArray(int capacity);//有参构造~DynamicArray();//析构
}

源文件放函数的实现

#include<iostream>
#include"dynamicArray.h"
using namespace std;
#include<time.h>
DynamicArray::DynamicArray()//无参构造,初始化成员变量
{capacity = 5;//动态数组默认长度为5data = new int[capacity];//data指向五个大小的内存空间size = 0;
}
DynamicArray::DynamicArray(int capacity)//有参构造，传入容量
{this->capacity = capacity;data = new int[capacity];size = 0;
}
DynamicArray::~DynamicArray()//析构,释放内存空间
{if(data!=nullptr){delete[]data;data = nullptr;}
}