• 【数据结构】线性表

    • 基本概念

    线性表是 0 个或者多个数据元素的有序序列。

    -

    特性：

    1. 数据元素之间是有序的
    2. 数据元素个数是有限的
    3. 数据元素类型是相同的
    • 性质
    • a_{0} 为线性表的第一个元素，只有一个后继。
    • a_{n} 为线性表的最后一个元素，只有一个前驱。
    • 除 a_{0} 和 a_{n} 外的其他元素 a_{i} ，既有前驱，又有后继。
    • 线性表能够逐项访问和顺序存放。
    • 线性表存储的方式

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

     C 语 言 实 现 单 链 表

    • 结构体框架
    1. typedef struct {
    2.     int* pArr;     // 存放数据地址
    3.     int size;      // 长度，当前元素个数
    4.     int capacity;  // 容量，当前最大能容纳元素
    5. }Dynamic_Array;
    • 操作函数声明
    1. // 初始化
    2. Dynamic_Array* Init_Array();
    3.  
    4.  
    5. // 插入
    6. void Push_back_Array(Dynamic_Array* arr，int val);
    7.  
    8.  
    9. // 根据 位置 删除
    10. void RemoveByPos_Array(Dynamic_Array* arr, int pos);
    11.  
    12.  
    13. // 根据 数据 删除
    14. void RemoveByValue_Array(Dynamic_Array* arr, int val);
    15.  
    16.  
    17. // 查找
    18. int Find_Array(Dynamic_Array* arr, int val);
    19.  
    20.  
    21. // 打印
    22. void Print_Array(Dynamic_Array* arr);
    23.  
    24.  
    25. // 释放动态数组内存
    26. void FreeSpace_Array(Dynamic_Array* arr, int pos);
    27.  
    28.  
    29. // 清空数组
    30. void Clear_Array(Dynamic_Array* arr);
    31.  
    32.  
    33. // 获取容量
    34. int Capactiy_Array(Dynamic_Array* arr);
    35.  
    36.  
    37. // 获取长度
    38. int Size_Array(Dynamic_Array* arr);
    39.  
    40.  
    41. // 根据 位置 获取元素
    42. int At_Array(Dynamic_Array* arr, int pos);
    • 操作函数实现
    1. // 初始化
    2. Dynamic_Array* Init_Array() {
    3.  
    4.     // 申请空间
    5.     Dynamic_Array* myArray = (Dynamic_Array*)malloc(sizeof(Dynamic_Array));
    6.     // 初始化
    7.     myArray->size = 0;
    8.     myArray->capacity = 20;
    9.     myArray->pArr = (int*)malloc(sizeof(int) * myArray->capacity);
    10.  
    11.     return myArray;
    12. }
    13.  
    14. // 插入
    15. void Push_back_Array(Dynamic_Array* arr, int val) {
    16.  
    17.     if (arr == NULL) return;
    18.  
    19.     // 判断容量是否足够
    20.     if (arr->size >= arr->capacity) {
    21.         
    22.         // 申请更大空间 默认两倍
    23.         int* NewSpace = (int*)malloc(sizeof(int) * arr->capacity * 2);
    24.  
    25.         // 拷贝数据到新空间
    26.         if (NewSpace != NULL) {
    27.             memcpy(NewSpace, arr->pArr, arr->capacity * sizeof(int));
    28.         }
    29.  
    30.         // 释放旧空间内存
    31.         free(arr->pArr);
    32.  
    33.         // 更新容量
    34.         arr->capacity = arr->capacity * 2;
    35.  
    36.         // 更新指针指向
    37.         arr->pArr = NewSpace;
    38.     }
    39.     // 尾插 插入 新元素
    40.     arr->pArr[arr->size] = val;
    41.     
    42.     // 更新长度
    43.     arr->size++;
    44. }
    45.  
    46. // 根据位置删除
    47. void RemoveByPos_Array(Dynamic_Array* arr, int pos) {
    48.    
    49.     if (arr == NULL) return;
    50.  
    51.     // 判断 位置 是否有效
    52.     if (pos < 0 || pos >= (arr->size)) return;
    53.  
    54.     // 删除
    55.     for (int i = pos; i < arr->size - 1; i++) {
    56.         arr->pArr[i] = arr->pArr[i + 1];
    57.     }
    58.  
    59.     // 更新长度
    60.     arr->size--;
    61. }
    62.  
    63. // 根据值删除
    64. void RemoveByValue_Array(Dynamic_Array* arr, int val) {
    65.     
    66.     if (arr == NULL) return;
    67.  
    68.     int pos = Find_Array(arr, val);
    69.  
    70.     // 调用 按位置 删除
    71.     RemoveByPos_Array(arr, pos);
    72. }
    73.  
    74. // 查找
    75. int Find_Array(Dynamic_Array* arr, int val) {
    76.     
    77.     int pos = -1;
    78.  
    79.     if (arr == NULL) return pos;
    80.  
    81.     for (int i = 0; i < arr->size; i++) {
    82.         if (arr->pArr[i] == val) {
    83.             pos = i;
    84.             break;
    85.         }
    86.     }
    87.     return pos;
    88. }
    89.  
    90. // 打印
    91. void Print_Array(Dynamic_Array* arr) {
    92.     
    93.     if (arr == NULL) return;
    94.  
    95.     for (int i = 0; i < arr->size; i++) 
    96.         printf("%d ", arr->pArr[i]);
    97.  
    98.     printf("\n");
    99. }
    100.  
    101. // 释放动态数组内存
    102. void FreeSpace_Array(Dynamic_Array* arr) {
    103.     
    104.     if (arr == NULL) return;
    105.  
    106.     if (arr->pArr != NULL) free(arr->pArr);
    107.  
    108.     free(arr);
    109. }
    110.  
    111. // 清空数组
    112. void Clear_Array(Dynamic_Array* arr) {
    113.     
    114.     if (arr == NULL) return;
    115.  
    116.     arr->size = 0;
    117. }
    118.  
    119. // 获取容量
    120. int Capactiy_Array(Dynamic_Array* arr) {
    121.    
    122.     if (arr == NULL) return 0;
    123.  
    124.     return arr->capacity;
    125. }
    126.  
    127. // 获取长度
    128. int Size_Array(Dynamic_Array* arr) {
    129.    
    130.     if (arr == NULL) return 0;
    131.  
    132.     return arr->size;
    133. }
    134.  
    135. // 根据位置获取元素
    136. int At_Array(Dynamic_Array* arr, int pos) {
    137.     
    138.     if (arr == NULL) return -1;
    139.  
    140.     return arr->pArr[pos];
    141. }

    CPP 实 现 单 链 表

    • DynamicArray类声明
    1. class DynamicArray {
    2. public:
    3.     // 构造
    4.     DynamicArray();
    5.  
    6.     // 插入
    7.     void Pushback_Array(const Person& p);
    8.  
    9.     // 根据 下标 删除
    10.     void RemoveByPos_Array(const int& pos);
    11.  
    12.     // 根据 数据 删除
    13.     void RemoveByVal_Array(const Person& p);
    14.  
    15.     // 根据 下标 修改
    16.     void ModifyByPos_Array(const int& pos);
    17.  
    18.     // 根据 数据 修改
    19.     void ModifyByVal_Array(const Person& p);
    20.  
    21.     // 根据 下标 查找
    22.     Person& FindByPos_Array(const int& pos);
    23.  
    24.     // 根据 数据 查找
    25.     int FindByVal_Array(const Person& p);
    26.  
    27.     // 打印
    28.     void Print_Array();
    29.  
    30.     // 清空
    31.     void Clear_Array();
    32.  
    33.     // 获取长度
    34.     int Get_Size_Array();
    35.  
    36.     // 获取容量
    37.     int Get_Capactiy_Array();
    38.  
    39.     // 析构
    40.     ~DynamicArray();
    41.  
    42.     DynamicArray& operator=(const DynamicArray& da);
    43.  
    44. public:
    45.     Person* m_Parr;
    46.     int m_Size;
    47.     int m_Capactiy;
    48. };
    • Person类声明
    1. class Person {
    2.  
    3.     friend std::ostream& operator<<(std::ostream& cout, const Person& p);
    4.  
    5. public:
    6.     Person(std::string name, std::string sex, int age);
    7.     Person();
    8.  
    9.     void Set_Name(std::string name);
    10.     void Set_Sex(std::string sex);
    11.     void Set_Age(int age);
    12.  
    13.     std::string Get_Name();
    14.     std::string Get_Sex();
    15.     int Get_Age();
    16.     Person& operator=(const Person& p);
    17.     bool operator==(const Person& p);
    18. private:
    19.     std::string m_Name;
    20.     std::string m_Sex;
    21.     int m_Age;
    22. };
    23.  
    24. std::ostream& operator<<(std::ostream& cout, const Person& p);
    • DynamicArray类方法实现
    1. // 构造
    2. DynamicArray::DynamicArray() {
    3.     this->m_Capactiy = 20;
    4.     this->m_Parr = new Person[this->m_Capactiy];
    5.     this->m_Size = 0;
    6. }
    7.  
    8. // 尾插
    9. void DynamicArray::Pushback_Array(const Person& p) {
    10.     // 空间不足
    11.     if (this->m_Size >= this->m_Capactiy) {
    12.         // 创建一个新空间
    13.         Person* NewSpace = new Person[this->m_Capactiy * 2];
    14.  
    15.         // 旧数据放到新空间
    16.         for (int i = 0; i < this->m_Capactiy; i++) {
    17.             NewSpace[i].Set_Name(this->m_Parr[i].Get_Name());
    18.             NewSpace[i].Set_Sex(this->m_Parr[i].Get_Sex());
    19.             NewSpace[i].Set_Age(this->m_Parr[i].Get_Age());
    20.             //NewSpace[i] = this->m_Parr[i];
    21.         }
    22.  
    23.         // 释放原有空间
    24.         delete[] this->m_Parr;
    25.  
    26.         // 更改指针指向
    27.         this->m_Parr = NewSpace;
    28.  
    29.         // 更新容量
    30.         this->m_Capactiy = this->m_Capactiy * 2;
    31.     }
    32.  
    33.     // 插入元素
    34.     this->m_Parr[this->m_Size] = p;
    35.  
    36.     // 更新长度
    37.     this->m_Size++;
    38. }
    39.  
    40. // 根据 下标 删除
    41. void DynamicArray::RemoveByPos_Array(const int& pos) {
    42.  
    43.     if (pos < 0 || pos >= this->m_Size) {
    44.         return;
    45.     }
    46.  
    47.     // pos 位置之后开始往前移动
    48.     for (int i = pos; i < this->m_Size - 1; i++) {
    49.         this->m_Parr[i] = this->m_Parr[i + 1];
    50.     }
    51.  
    52.     // 更新长度
    53.     this->m_Size--;
    54. }
    55.  
    56. // 根据 数据 删除
    57. void DynamicArray::RemoveByVal_Array(const Person& p) {
    58.  
    59.     // 通过值查找
    60.     int pos = FindByVal_Array(p);
    61.  
    62.     // 通过下标删除
    63.     RemoveByPos_Array(pos);
    64. }
    65.  
    66. // 根据 下标 查找
    67. Person& DynamicArray::FindByPos_Array(const int& pos) {
    68.     return this->m_Parr[pos];
    69. }
    70.  
    71. // 根据 数据 查找
    72. int DynamicArray::FindByVal_Array(const Person& p) {
    73.  
    74.     int pos = -1;
    75.     for (int i = 0; i < this->m_Size; i++) {
    76.         if (this->m_Parr[i] == p) {
    77.             pos = i;
    78.             break;
    79.         }
    80.     }
    81.     return pos;
    82. }
    83.  
    84. // 打印
    85. void DynamicArray::Print_Array() {
    86.     for (int i = 0; i < this->m_Size; i++) {
    87.         std::cout << this->m_Parr[i].Get_Name() << " "
    88.             << this->m_Parr[i].Get_Sex() << " "
    89.             << this->m_Parr[i].Get_Age()
    90.             << std::endl;
    91.     }
    92.     std::cout << std::endl;
    93.  
    94. }
    95.  
    96. // 清空
    97. void DynamicArray::Clear_Array() {
    98.  
    99.     this->m_Size = 0;
    100.  
    101.     delete[] this->m_Parr;
    102.  
    103.     this->m_Parr = NULL;
    104. }
    105.  
    106. // 获取长度
    107. int DynamicArray::Get_Size_Array() {
    108.     return this->m_Size;
    109. }
    110.  
    111. // 获取容量
    112. int DynamicArray::Get_Capactiy_Array() {
    113.     return this->m_Capactiy;
    114. }
    115.  
    116. // 析构
    117. DynamicArray::~DynamicArray() {
    118.     if (this->m_Parr != NULL) {
    119.         delete[] this->m_Parr;
    120.         this->m_Parr = NULL;
    121.     }
    122.  
    123. }
    124.  
    125. // 重载 =
    126. DynamicArray& DynamicArray::operator=(const DynamicArray& da) {
    127.     // 容量复制
    128.     this->m_Capactiy = da.m_Capactiy;
    129.     
    130.     // 长度复制
    131.     this->m_Size = da.m_Size;
    132.     
    133.     // 内容复制
    134.     for (int i = 0; i < this->m_Size; i++) {
    135.         this->m_Parr[i].Set_Name(da.m_Parr[i].Get_Name());
    136.         this->m_Parr[i].Set_Sex(da.m_Parr[i].Get_Sex());
    137.         this->m_Parr[i].Set_Age(da.m_Parr[i].Get_Age());
    138.     }
    139.     
    140.     return *this;
    141. }
    • Person类实现
    1. Person::Person(std::string name, std::string sex, int age){
    2.     this->m_Name = name;
    3.     //if (sex != "男" || sex != "女") {
    4.     //    throw sex;
    5.     //}
    6.     this->m_Sex = sex;
    7.     this->m_Age = age;
    8. }
    9.  
    10. Person::Person(){}
    11.  
    12. void Person::Set_Name(std::string name){
    13.     this->m_Name = name;
    14. }
    15.  
    16. void Person::Set_Sex(std::string sex){
    17.     this->m_Sex = sex;
    18. }
    19.  
    20. void Person::Set_Age(int age){
    21.     this->m_Age = age;
    22. }
    23.  
    24. std::string Person::Get_Name(){
    25.     return this->m_Name;
    26. }
    27.  
    28. std::string Person::Get_Sex(){
    29.     return this->m_Sex;
    30. }
    31.  
    32. int Person::Get_Age(){
    33.     return this->m_Age;
    34. }
    35.  
    36. Person& Person::operator=(const Person& p){
    37.     this->m_Age = p.m_Age;
    38.     this->m_Name = p.m_Name;
    39.     this->m_Sex = p.m_Sex;
    40.     return *this;
    41. }
    42.  
    43. bool Person::operator==(const Person& p) {
    44.     if (this->m_Name == p.m_Name && this->Get_Age() == p.m_Age && this->Get_Sex() == p.m_Sex) {
    45.         return true;
    46.     }
    47.     else false;
    48. }
    49.  
    50. std::ostream& operator<<(std::ostream& cout, const Person& p) {
    51.     std::cout << p.m_Name << " " << p.m_Sex << " " << p.m_Age << std::endl;
    52.     return std::cout;
    53. }

    在写 cpp 线性表的时候出现很奇怪的bug，平时一般都是头文件（.h）写声明，源文件（.cpp）写实现，两个文件名写成相同的，但是总是出现 LNK2019 的错误链接器工具错误 LNK2019 | Microsoft Docs

    文档看了半天也没看出来哪里有问题，最后把写实现的（.cpp）文件改了名字（不和 .h 头文件一样）结果就好了

    期间试了很多方法，说把头文件后缀改为 （.hpp、.H 、....）都尝试过，但都不行

  • 相关阅读:
    SpringBoot学习小结之Swagger
    基于Python Web的学生成绩管理系统--文档
    论文中的小细节——为什么论文中总是写WX而不是XW？
    MySQL使用简单教程
    信息系统基础选择题真题
    企业级DevOps平台搭建及技术选型-项目管理篇
    17_方法
    Android 开发错误集合
    Python 使用Scapy构造特殊数据包
    计算机网络（四）
  • 原文地址：https://blog.csdn.net/xuan3215/article/details/126296359