当前位置：首页 > news >正文

从0开始的数据结构复习 1

news 2024/10/24 21:31:51

At first ...

在那之前

连续的还是链式的？

std::array简单介绍

热身训练与范例

Reference

笔者最近开始需要复习数据结构，这里做一点笔记整理。

At first ...

首先要谈的是：我们需要按照需求来进行数据结构的选择。

数据结构本身谈论的就是数据的组织形式。我们可能存放很多数据：比如说我们的笔记，我们的人身信息等等。对于一个公开的大型的系统，如何存储他们就是数据结构在底层中真正关心的话题。

在那之前

我们需要补充一下大O理论。大O理论就是用来评估算法复杂度的。什么叫算法复杂度呢？其实倒不如叫：一个算法随同类数据规模增长的时间开销增长程度。我的另一个意思就是。当我们的数据越来越多的时候，毫无疑问的，处理时间会增长。但是增长的多慢呢？有的数据几乎不咋增长，换而言之，这些算法很神奇：无论给他们多么庞大的数据，他们的耗时增长几乎可以忽略不计！另一些可能有所增长，但是很缓慢。一些是线性增长，另一些则是指数增长。

值得一提的是：一个好的算法公开认为是增长越缓慢越好，最好是常数时间。我们将常数时间的算法复杂度为O(1)，对于线性的则是O(n)等。当然还有诸如O(n\log n), O(n^2)等复杂度。这些等到我们提及具体算法的时候一一进行分析。

连续的还是链式的？

这是一个所有入门数据结构设计的一个经典问题。对于数据的内存组织形式，我们是要连续的还是物理的？

// typical announcement in C
const int CONTIGUOUS_DATA[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

上面就是声明一个连续内存的数组！就是这样的简单！C/C++原生支持一个连续的数字（事实上汇编开始就支持，不过可能看起来不太顺眼，但是类似于上文的声明 :) ），如果我们透过计算机看到底下的内存，上面的十个数就是这样放置的：

+----+----+----+----+----+----+----+----+----+----+
| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
+----+----+----+----+----+----+----+----+----+----+^                    |
CONTIGUOUS_DATA

是的！我们现在就可以访问，比如说我们提供一个下标：

int fetch_data = CONTIGUOUS_DATA[1]

实际上我们就是：

+----+----+----+----+----+----+----+----+----+----+
| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
+----+----+----+----+----+----+----+----+----+----+^|fetch_data (值为 3)

换而言之，一个连续的内存的视图就是这样：一篇内存游泳池和一个索引:)。索引的办法是

$$
Element Address = BaseAddress+Index \times ElementSize
$$

+----+----+----+----+----+
| A0 | A1 | A2 | A3 | A4 |
+----+----+----+----+----+↑位置（索引）

比起来，链式的数据结构要稍微难以理解一些：

C语言原生没有链表，这是我们下面要做的事情。但是C++STL库有。办法是使用<forward_list>头文件而且声明存储类型：

std::forward_list<int> LIST = {1,2,3,4,5,6};

它的存储视图如下：

+------+      +------+      +------+      +------+      +------+      +------+
| 1    |      | 2    |      | 3    |      | 4    |      | 5    |      | 6    |
| Next |----->| Next |----->| Next |----->| Next |----->| Next |----->| Next |
+------+      +------+      +------+      +------+      +------+      +------+

我的意思是说：他们的下一个在内存上不连续！这里很有讲究。我说这个数据的“下一个”，意味着数据在逻辑上是存在前后关联的。我们仍然可以大胆放心的说这个数据的上一个怎么这么样，但是他们实际上在内存中并不连续。也就是说：

$$
Element Address \neq BaseAddress+Index \times ElementSize
$$

地址实际上是完全随机的！我们也不知道他们的下一个在哪里，但是每一个数据知道的是：我的下一个在哪里。等等，那也就意味着，假使我需要找到第N个元素，我需要从第0个开始一个一个爬下去直到我们找到为之！这也就意味着我们大概率需要爬遍一整个链表来查找一个数据！gosh!但是链表的好处在于插入删除的低成本。这一点，请你想象一下我需要在中间插入删除数据。对于连续内存者，我需要移动一！整！个！数组向前覆盖。但是对于链表，简单的拔出指针做指针数据更新就能完成数据的删除。how easy!

下面这个表供以参考两者的区别

特点	数组 (Array)	链表 (Linked List)
内存分配	连续内存分配	不连续内存分配，节点可能分散在内存中
访问时间	O(1)（随机访问）	O(n)（线性访问，需从头遍历）
插入时间	O(n)（需要移动元素）	O(1)（在已知位置插入）
删除时间	O(n)（需要移动元素）	O(1)（在已知位置删除）
空间效率	固定大小，若需要扩展可能导致内存浪费	动态大小，按需分配内存
存储类型	存储基本数据类型或对象的直接值	存储节点，包含数据和指向下一个节点的指针
内存使用	内存使用相对简单	每个节点需额外存储指针，增加内存开销
遍历	可通过索引快速遍历	需通过指针逐个遍历
多维支持	支持多维数组	不支持，需手动实现多维结构
缓存友好性	由于连续内存，提高缓存命中率	不一定，有可能导致缓存未命中
简单性	简单易用，语法直观	较复杂，涉及指针操作和内存管理
适用场景	适合固定大小、频繁访问的情况	适合频繁插入删除、大小动态变化的情况

std::array简单介绍

为什么是std::array呢？

从软件工程规范上讲：他是一个合格的对象，我们使用“方法”（What a Javaish!）来访问这个对象，比如说让他取出，删除数据等。
从异常处理上讲：一般的数组不会支持抛出异常，但是STL的容器会，我们接受异常来处理异常的程序来保证我们的程序不是一篇薄纸一碰就碎。

热身训练与范例

任务一：实现一个简单的std::array. 名字任意:)

一些简单的接口提示：

template<typename DataType, size_t SIZE>
class CCArray
{DataType core_data[SIZE];
public:/* Following three are the basic usage */ CCArray();CCArray(const CCArray& array);CCArray(const CCArray&& array);const CCArray& operator=(const CCArray&);const CCArray& operator=(const CCArray&&);const CCArray& operator==(const CCArray&);/* Other creator Functions are placed here */ /* Welp, it welcomes the initializer_list, reason why c++11 above:) */CCArray(const std::initializer_list<DataType> ins);CCArray(const DataType (&raws)[]);
[[nodiscard]] std::size_t    size() const noexcept;bool                    empty() const noexcept;/* As Told, the operator[] shell no exception, if so, program shell crash :) */[[nodiscard]] DataType& operator[](const std::size_t size) noexcept;[[nodiscard]] DataType& at(const std::size_t size);
/* To fit in the STL algorithm. one shell provide begin() and end() */[[nodiscard]] const DataType* begin() const;[[nodiscard]] const DataType* end() const;
};

Reference

实现文件如下

array.hpp

/*Implemented STL Standard array in a simple way :)
*/
#include <initializer_list>
#include <stdexcept>

template<typename DataType, size_t SIZE>
class CCArray
{DataType core_data[SIZE];
public:/* Following three are the basic usage */ CCArray();CCArray(const CCArray& array);CCArray(const CCArray&& array);const CCArray& operator=(const CCArray&);const CCArray& operator=(const CCArray&&);const CCArray& operator==(const CCArray&);/* Other creator Functions are placed here */ /* Welp, it welcomes the initializer_list, reason why c++11 above:) */CCArray(const std::initializer_list<DataType> ins);CCArray(const DataType (&raws)[]);
[[nodiscard]] std::size_t    size() const noexcept;bool                    empty() const noexcept;/* As Told, the operator[] shell no exception, if so, program shell crash :) */[[nodiscard]] DataType& operator[](const std::size_t size) noexcept;[[nodiscard]] DataType& at(const std::size_t size);
/* To fit in the STL algorithm. one shell provide begin() and end() */[[nodiscard]] const DataType* begin() const;[[nodiscard]] const DataType* end() const;
};

template<typename DataType, size_t SIZE>
bool operator==(const CCArray<DataType, SIZE>& self,const CCArray<DataType, SIZE>& other_array);

template<typename DataType, size_t SIZE>
// do_nothing
CCArray<DataType, SIZE>::CCArray(){}

template<typename DataType, size_t SIZE>
CCArray<DataType, SIZE>::CCArray(const CCArray& array)
{for(std::size_t i = 0; i < SIZE; i++){core_data[i] = array.core_data[i];}
}

template<typename DataType, size_t SIZE>
CCArray<DataType, SIZE>::CCArray(const CCArray&& target){if(&target == this){return *this;}for(std::size_t i = 0; i < SIZE; i++){core_data[i] = std::move(target.core_data[i]);}
}

template<typename DataType, size_t SIZE>
const CCArray<DataType, SIZE>& 
CCArray<DataType, SIZE>::operator=(const CCArray& target){if(&target == this){return *this;}for(std::size_t i = 0; i < SIZE; i++){core_data[i] = target.core_data[i];}
}

template<typename DataType, size_t SIZE>
const CCArray<DataType, SIZE>& 
CCArray<DataType, SIZE>::operator==(const CCArray& target){if(&target == this){return *this;}for(std::size_t i = 0; i < SIZE; i++){core_data[i] = std::move(target.core_data[i]);}
}


template<typename DataType, size_t SIZE>
CCArray<DataType, SIZE>::CCArray(const std::initializer_list<DataType> ins)
{const size_t src_size = ins.size();if(src_size > SIZE){throw std::out_of_range("Exceeds of Size is not permitted :)");}size_t index = 0;for(const auto& each: ins){core_data[index] = each;index++;}// this is for the default initializationsfor(;index < SIZE;index++){// Call defaultscore_data[index] = DataType();index++;}
}

template<typename DataType, size_t SIZE>
CCArray<DataType, SIZE>::CCArray(const DataType (&raws)[])
{static_assert(sizeof(raws)/sizeof(DataType) == SIZE, "Can not accept this array: size mismatch!");for(size_t index = 0; index < SIZE; index++)core_data[index] = raws[index];
}

template<typename DataType, size_t SIZE>
std::size_t CCArray<DataType, SIZE>::size() const noexcept
{return SIZE;
}

template<typename DataType, size_t SIZE>
bool CCArray<DataType, SIZE>::empty() const noexcept
{return SIZE == 0;
}

template<typename DataType, size_t SIZE>
DataType& CCArray<DataType, SIZE>::operator[](const std::size_t size) noexcept
{return core_data[size];
}

template<typename DataType, size_t SIZE>
DataType& CCArray<DataType, SIZE>::at(const std::size_t size)
{if(size > SIZE){throw std::out_of_range("Exceeds of Size is not permitted :)");}return core_data[size];
}

template<typename DataType, size_t SIZE>
const DataType* CCArray<DataType, SIZE>::begin() const
{return core_data;
}

template<typename DataType, size_t SIZE>
const DataType* CCArray<DataType, SIZE>::end() const
{return core_data + SIZE;
}

test_my_array.cpp: 测试文件

#include "array.hpp"
#include <iostream>
template<typename DataType, size_t size>
void test_range_display(const CCArray<DataType, size>& array){for(const auto& each : array){std::cout << each << " ";}std::cout << std::endl;
}


void test_arrays()
{CCArray<int, 5> arr;for(int i = 0; i < 5; i++){arr[i] = i;}
CCArray<int, 5> arr2(arr); // test copyCCArray<int, 5> arr3 = arr; // test =CCArray<int, 5> arr4{1, 2, 3, 4, 5};// one shell try call this, using in test the exception // CCArray<int, 5> arr4{1, 2, 3, 4, 5, 6};test_range_display(arr);test_range_display(arr2);test_range_display(arr3);
CCArray<double, 0> is_empty_arr;if(is_empty_arr.empty()){std::cout << "Pity array with empty :(" << std::endl;}

}

查看全文

http://www.mrgr.cn/news/57869.html