• C语言 -- 动态数组&链表


    目录

    动态数组

     动态数组的实现:

    用户test

    链表

    目的:

    链表的结构体:

    链表的实现:

    初始化链表

    插入节点

    遍历链表

    删除节点

    清空链表、销毁链表

    用户回调函数

    给用户提供接口获取链表长度

    用户test


    动态数组

    将数组开辟到堆区,实现动态扩展。

    问题:

    ① 用户的数据类型无法确定;

    ② 用户的数据无法确定创建在堆区还是栈区;

    ③ 不管数据在堆区还是栈上,都是在内存中,就会有地址,只需维护数据的地址就行。eg:如果数据类型是 int,则使用 int* 来指向该数据地址。

    所以,这里使用万能指针 void* 来指向用户的数据地址。

    第二点,我们是在堆区创建的一个数组,每一个元素都是 void* 类型的。如果要操纵这个数组,则可以使用二级指针 void** 来指向该数组的地址。

     动态数组的实现:

    1. typedef struct DynamicArray
    2. {
    3. void** pAddr; //维护真实在堆区开辟的数组的二级指针
    4. int m_Capacity; //数组容量
    5. int m_Size; //数组大小
    6. }dynamicArray;
    7. //初始化数组,参数:初始数组的容量。返回值:数组指针
    8. dynamicArray* init_dynamicArray(int capacity)
    9. {
    10. if (capacity <= 0)
    11. {
    12. return NULL;
    13. }
    14. //给数组分配内存
    15. dynamicArray* arr = malloc(sizeof(dynamicArray));
    16. if (arr == NULL)
    17. return NULL;
    18. //数组属性初始化
    19. arr->pAddr = malloc(sizeof(void*) * capacity); //我们维护的数据类型是void*,
    20. //这里是capacity个void*类型的数据大小,又malloc返回的是void**类型,pAddr同样是void**类型
    21. arr->m_Capacity = capacity;
    22. arr->m_Size = 0;
    23. }
    24. //数组元素插入
    25. void insert_dynamicArray(dynamicArray* arr, void* data, int pos)
    26. {
    27. if (arr == NULL)
    28. return;
    29. if (data == NULL)
    30. return;
    31. if (pos<0 || pos>arr->m_Size)
    32. pos = arr->m_Size;
    33. //判断数组是否满了
    34. if (arr->m_Size == arr->m_Capacity)
    35. {
    36. //计算新的空间大小
    37. int newCapacity = arr->m_Capacity * 2;
    38. //开辟新空间
    39. void** newSpace = malloc(sizeof(void*) * newCapacity);
    40. //将原空间下数据拷贝到新空间下
    41. memcpy(newSpace, arr->pAddr, sizeof(void*) * arr->m_Capacity);
    42. //释放原空间
    43. free(arr->pAddr);
    44. //更改指向
    45. arr->pAddr = newSpace;
    46. //更新容量
    47. arr->m_Capacity = newCapacity;
    48. }
    49. //将新元素插入到指定位置
    50. for (int i = arr->m_Size - 1; i >= pos; i--) //从最后边的数据开始移
    51. {
    52. arr->pAddr[i + 1] = arr->pAddr[i];
    53. }
    54. arr->pAddr[pos] = data;
    55. //更新数组大小
    56. arr->m_Size++;
    57. }
    58. //遍历
    59. void foreach_dynamicArray(dynamicArray* arr,void(*myPrint)(void*))
    60. {
    61. if (arr == NULL)
    62. return;
    63. for (int i = 0; i < arr->m_Size; i++)
    64. {
    65. myPrint(arr->pAddr[i]);
    66. }
    67. }
    68. //删除数组中元素
    69. //按照位置删除
    70. void removeByPos_dynamicArray(dynamicArray* arr, int pos)
    71. {
    72. if (arr == NULL)
    73. return;
    74. if (pos<0 || pos>arr->m_Size - 1)
    75. return;
    76. for (int i = pos; i < arr->m_Size; i++)
    77. {
    78. arr->pAddr[i] = arr->pAddr[i + 1];
    79. }
    80. arr->m_Size--;
    81. }
    82. //按照数值删除
    83. void removeByVal_dynamicArray(dynamicArray* arr, void* data, int(*myCompare)(void*,void*))
    84. {
    85. if (arr == NULL)
    86. return;
    87. if (data == NULL)
    88. return;
    89. for (int i = 0; i < arr->m_Size; i++)
    90. {
    91. if (myCompare(arr->pAddr[i], data))//利用回调函数让用户告诉我们如何对比数据
    92. {
    93. removeByPos_dynamicArray(arr,i);
    94. break;
    95. }
    96. }
    97. }
    98. void destory_dynamicArray(dynamicArray* arr)
    99. {
    100. if (arr == NULL)
    101. return;
    102. //内部维护在堆区数组指针先释放
    103. if (arr->pAddr != NULL)
    104. {
    105. free(arr->pAddr);
    106. arr->pAddr = NULL;
    107. }
    108. free(arr);
    109. arr = NULL;
    110. }

    用户test

    1. typedef struct Person //用户的数据类型
    2. {
    3. char name[32];
    4. int age;
    5. }person;
    6. //回调函数,打印用户数据
    7. void printPerson(void* data)
    8. {
    9. person* person = data;
    10. printf("Name:%s Age:%d\n", person->name, person->age);
    11. }
    12. int comparePerson(void* data1, void* data2)
    13. {
    14. person* p1 = data1;
    15. person* p2 = data2;
    16. return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
    17. }
    18. void test01()
    19. {
    20. dynamicArray* arr = init_dynamicArray(5);
    21. person p1 = { "sun",18 };
    22. person p2 = { "yu",19 };
    23. person p3 = { "hang",17 };
    24. person p4 = { "li",20 };
    25. person p5 = { "hai",21 };
    26. printf("插入数据前:容量 = %d,大小 = %d\n", arr->m_Capacity, arr->m_Size);
    27. insert_dynamicArray(arr, &p1, 0);
    28. insert_dynamicArray(arr, &p2, 1);
    29. insert_dynamicArray(arr, &p3, -1);
    30. insert_dynamicArray(arr, &p4, 0);
    31. insert_dynamicArray(arr, &p5, 2);
    32. foreach_dynamicArray(arr, printPerson);
    33. printf("插入数据后:容量 = %d,大小 = %d\n", arr->m_Capacity, arr->m_Size);
    34. printf("-------------------------------\n");
    35. //按位置删除
    36. removeByPos_dynamicArray(arr,0);
    37. foreach_dynamicArray(arr, printPerson);
    38. printf("-------------------------------\n");
    39. //按值删除
    40. removeByVal_dynamicArray(arr, &p5, comparePerson);
    41. foreach_dynamicArray(arr, printPerson);
    42. printf("删除数据后:容量 = %d,大小 = %d\n", arr->m_Capacity, arr->m_Size);
    43. destory_dynamicArray(arr);
    44. arr = NULL;
    45. }
    1. 插入数据前:容量 = 5,大小 = 0
    2. Name:li Age:20
    3. Name:sun Age:18
    4. Name:hai Age:21
    5. Name:yu Age:19
    6. Name:hang Age:17
    7. 插入数据后:容量 = 5,大小 = 5
    8. -------------------------------
    9. Name:sun Age:18
    10. Name:hai Age:21
    11. Name:yu Age:19
    12. Name:hang Age:17
    13. -------------------------------
    14. Name:sun Age:18
    15. Name:yu Age:19
    16. Name:hang Age:17
    17. 删除数据后:容量 = 5,大小 = 3

    链表

    目的:

    设计一个可以存不同类型数据的链表。

    首先来看一个存储void*类型数据的普通链表。

     其中的一个节点只是一个独立的个体,无法代表整个链表。

    链表的结构体:

    整个链表用一个新的结构体来维护,如下:

    1. struct LList
    2. {
    3. struct LinkNode pHeader; //链表的头结点,拿到链表的头结点即可还原整个链表
    4. int m_Size; //记录链表的节点个数
    5. }

    在动态数组的实现中,我们可以随时访问动态数组的容量arr->m_Capacity,但由于整个数组的结构体暴露给了用户,导致用户也可以随意修改。

    链表的实现中,我们就不直接让用户拿到链表的结构体 LList,防止其被篡改。进行如下操作:

    typedef void* LinkList;  //给 void* 起别名

    则用户拿到的数据永远都是 void* 类型的,我们在操作的时候,再把void*转为struct LList类型。

    链表的实现:

    1. //链表的节点结构体
    2. typedef struct LinkNode
    3. {
    4. void* data;
    5. struct LinkNode* next;
    6. }LinkNode;
    7. //链表结构体
    8. typedef struct LList
    9. {
    10. struct LinkNode pHeader;
    11. int m_Size;
    12. }Llist;
    13. //void别名
    14. typedef void* LinkList;

    初始化链表

    1. //初始化链表
    2. LinkList init_LinkList()
    3. {
    4. //分配内存
    5. Llist* mylist = malloc(sizeof(Llist));
    6. if (mylist == NULL)
    7. return;
    8. mylist->pHeader.data = NULL;
    9. mylist->pHeader.next = NULL;
    10. mylist->m_Size = 0;
    11. return mylist; //返回的是void*类型
    12. }

    插入节点

    1. //插入节点
    2. void insert_LinkList(LinkList list, int pos, void* data)
    3. {
    4. if (list == NULL)
    5. return;
    6. if (data == NULL)
    7. return;
    8. Llist* mylist = list;
    9. if (pos<0 || pos>mylist->m_Size)
    10. {
    11. //如果传进来的位置是无效位置
    12. pos = mylist->m_Size;
    13. }
    14. //创建临时节点
    15. LinkNode* pCurrent = &mylist->pHeader; //pHeader直接是一个节点,所以用&取到其地址
    16. for (int i = 0; i < pos; i++)
    17. {
    18. pCurrent = pCurrent->next;
    19. }
    20. //此时pCurrent就是插入位置的前驱节点
    21. //创建新节点
    22. LinkNode* newNode = malloc(sizeof(LinkNode));
    23. newNode->data = data;
    24. newNode->next = NULL;
    25. //建立节点之间的关系
    26. newNode->next = pCurrent->next;
    27. pCurrent->next = newNode;
    28. //更新链表长度
    29. mylist->m_Size++;
    30. }

    遍历链表

    1. //遍历链表
    2. void foreach_LinkList(LinkList list,void(*myPrint)(void*))
    3. {
    4. if (list == NULL)
    5. return;
    6. //还原链表真实结构体
    7. Llist* mylist = list;
    8. LinkNode* pCurrent = mylist->pHeader.next;
    9. for (int i = 0; i < mylist->m_Size; i++)
    10. {
    11. myPrint(pCurrent->data); //我们不知道data的类型,所以这里使用用户自己的回调来打印
    12. pCurrent = pCurrent->next;
    13. }
    14. }

    删除节点

    1. //删除链表节点之按位置删除
    2. void removeByPos_LinkList(LinkList list, int pos)
    3. {
    4. if (list == NULL)
    5. return;
    6. Llist* mylist = list;
    7. if (pos<0 || pos>mylist->m_Size - 1)
    8. return; //无效位置直接返回
    9. //找到待删除位置的前驱节点的位置
    10. LinkNode* pCurrent = &mylist->pHeader;
    11. for (int i = 0; i < pos; i++)
    12. {
    13. pCurrent = pCurrent->next;
    14. }
    15. //PCurrent就是待删除节点的前驱节点
    16. //利用一个指针记录待删除节点
    17. LinkNode* pDel = pCurrent->next;
    18. //更改指针的指向
    19. pCurrent->next = pDel->next;
    20. //释放待删除节点
    21. free(pDel);
    22. pDel = NULL;
    23. mylist->m_Size--;
    24. }
    25. //删除链表节点之按值删除
    26. void removeByVal_LinkList(LinkList list, void* data, int(*myCompare)(void*))
    27. {
    28. if (list == NULL)
    29. return;
    30. if (data == NULL)
    31. return;
    32. //将list还原为真实链表结构体
    33. Llist* mylist = list;
    34. //创建两个辅助指针变量
    35. LinkNode* pPrev = &mylist->pHeader;
    36. LinkNode* pCurrent = mylist->pHeader.next;
    37. //遍历链表,找用户要删的数据
    38. for (int i = 0; i < mylist->m_Size; i++)
    39. {
    40. if (myCompare(data, pCurrent->data))
    41. {
    42. //开始删除,更改指针指向
    43. pPrev->next = pCurrent->next;
    44. free(pCurrent);
    45. pCurrent = NULL;
    46. mylist->m_Size--;
    47. break;
    48. }
    49. //辅助指针向后移动
    50. pPrev = pCurrent;
    51. pCurrent = pCurrent->next;
    52. }
    53. }

    清空链表、销毁链表

    1. //请空链表
    2. void clear_LinkList(LinkList list)
    3. {
    4. if (list == NULL)
    5. return;
    6. Llist* mylist = list;
    7. LinkNode* pCurrent = mylist->pHeader.next;
    8. for (int i = 0; i < mylist->m_Size; i++)
    9. {
    10. //记录下一个节点的位置
    11. LinkNode* pNext = pCurrent->next;
    12. free(pCurrent);
    13. pCurrent = pNext;
    14. }
    15. mylist->pHeader.next = NULL;
    16. mylist->m_Size = 0;
    17. }
    18. //销毁链表
    19. void destory_LinkList(LinkList list)
    20. {
    21. if (list == NULL)
    22. return;
    23. //先清空链表再销毁头结点
    24. clear_LinkList(list);
    25. free(list);
    26. list = NULL;
    27. }

    用户回调函数

    另外涉及到:打印用户数据,以及比较用户数据。由于我们不知道用户的数据类型,所以需要用户自己提供回调函数。

    1. //回调函数之打印
    2. void printPerson(void* data)
    3. {
    4. Person* person = data;
    5. printf("Name:%s,Age:%d\n", person->name, person->age);
    6. }
    7. //回调函数之比较
    8. int ComparePerson(void* data1, void* data2)
    9. {
    10. Person* p1 = data1;
    11. Person* p2 = data2;
    12. return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
    13. }

    给用户提供接口获取链表长度

    1. //给用户提供接口获取链表长度
    2. int size_LinkList(LinkList list)
    3. {
    4. if (list == NULL)
    5. return -1;
    6. Llist* mylist = list;
    7. return mylist->m_Size;
    8. }

    用户test

    1. void test02()
    2. {
    3. //初始化链表
    4. LinkList mylist = init_LinkList(); //mylist本质是一个void*类型的,用来隐藏结构体里的数据属性
    5. //mylist->m_size = -1; //err,用户访问不到真实链表中的属性
    6. Person p1 = { "sun",18 };
    7. Person p2 = { "yu",19 };
    8. Person p3 = { "hang",17 };
    9. Person p4 = { "li",20 };
    10. Person p5 = { "hai",21 };
    11. insert_LinkList(mylist, 0, &p1);
    12. insert_LinkList(mylist, 1, &p2);
    13. insert_LinkList(mylist, -1, &p3);
    14. insert_LinkList(mylist, 0, &p4);
    15. insert_LinkList(mylist, 2, &p5);
    16. //遍历链表
    17. foreach_LinkList(mylist, printPerson);
    18. printf("--------------------\n");
    19. removeByPos_LinkList(mylist,1);
    20. foreach_LinkList(mylist, printPerson);
    21. printf("--------------------\n");
    22. removeByVal_LinkList(mylist,&p4,ComparePerson);
    23. foreach_LinkList(mylist, printPerson);
    24. printf("链表长度为:%d\n", size_LinkList(mylist));
    25. printf("--------------------\n");
    26. //清空链表
    27. clear_LinkList(mylist);
    28. printf("清空链表后链表长度为:%d\n", size_LinkList(mylist));
    29. //销毁链表
    30. destory_LinkList(mylist);
    31. mylist = NULL;
    32. }
    1. Name:li,Age:20
    2. Name:sun,Age:18
    3. Name:hai,Age:21
    4. Name:yu,Age:19
    5. Name:hang,Age:17
    6. --------------------
    7. Name:li,Age:20
    8. Name:hai,Age:21
    9. Name:yu,Age:19
    10. Name:hang,Age:17
    11. --------------------
    12. Name:hai,Age:21
    13. Name:yu,Age:19
    14. Name:hang,Age:17
    15. 链表长度为:3
    16. --------------------
    17. 清空链表后链表长度为:0

  • 相关阅读:
    计算机毕业设计Java校园兼职招聘系统(源码+系统+mysql数据库+Lw文档)
    ubuntu_定制文件系统[2]-清理日志log
    【PCL自学:Segmentation4】基于Min-Cut点云分割
    《吐血整理》进阶系列教程-拿捏Fiddler抓包教程(11)-Fiddler设置安卓手机抓包,不会可是万万不行的!
    python-字典(创建方式、常用的操作方式)
    qt常用控件1
    HTML+CSS大作业 格林蛋糕(7个页面) 餐饮美食网页设计与实现
    2022年全球市场液相导热油总体规模、主要生产商、主要地区、产品和应用细分研究报告
    后台开发核心技术与应用实践看书笔记(三):常用STL的使用
    2023高教社杯数学建模国赛C题思路解析+代码+论文
  • 原文地址:https://blog.csdn.net/woshizuopie/article/details/126635520