• 数组、单链表和双链表介绍以及双向链表的C/C++实现

    数组

    数组有上界和下界，数组的元素在上下界内是连续的。

    存储10,20,30,40,50的数组的示意图如下：


    数组的特点是：数据是连续的；随机访问速度快。
    数组中稍微复杂一点的是多维数组和动态数组。对于C语言而言，多维数组本质上也是通过一维数组实现的。至于动态数组，是指数组的容量能动态增长的数组；对于C语言而言，若要提供动态数组，需要手动实现；而对于C++而言，STL提供了Vector；对于Java而言，Collection集合中提供了ArrayList和Vector。

    单向链表

    单向链表(单链表)是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。

    单链表的示意图如下：

    表头为空，表头的后继节点是"节点10"(数据为10的节点)，"节点10"的后继节点是"节点20"(数据为10的节点)，...

    单链表删除节点

    删除"节点30"
    删除之前："节点20" 的后继节点为"节点30"，而"节点30" 的后继节点为"节点40"。
    删除之后："节点20" 的后继节点为"节点40"。

    单链表添加节点

    在"节点10"与"节点20"之间添加"节点15"
    添加之前："节点10" 的后继节点为"节点20"。
    添加之后："节点10" 的后继节点为"节点15"，而"节点15" 的后继节点为"节点20"。

    单链表的特点是：节点的链接方向是单向的；相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很高。

    双向链表

    双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

    双链表的示意图如下：

    表头为空，表头的后继节点为"节点10"(数据为10的节点)；"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的前继节点是"节点10"；"节点20"的后继节点是"节点30"，"节点30"的前继节点是"节点20"；...；末尾节点的后继节点是表头。

    双链表删除节点

    删除"节点30"
    删除之前："节点20"的后继节点为"节点30"，"节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40"，"节点40" 的前继节点为"节点30"。
    删除之后："节点20"的后继节点为"节点40"，"节点40" 的前继节点为"节点20"。

    双链表添加节点

    在"节点10"与"节点20"之间添加"节点15"
    添加之前："节点10"的后继节点为"节点20"，"节点20" 的前继节点为"节点10"。
    添加之后："节点10"的后继节点为"节点15"，"节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20"，"节点20" 的前继节点为"节点15"。

    下面介绍双链表的实现，分别介绍C/C++/Java三种实现。

    1. C实现双链表

    实现代码

    1. #include 
    2. #include "double_link.h"
    3. void int_test()
    4. {
    5.     int iarr[4] = {10, 20, 30, 40};
    6.  
    7.     printf("\n----%s----\n", __func__);
    8.     create_dlink();        // 创建双向链表
    9.  
    10.     dlink_insert(0, &iarr[0]);    // 向双向链表的表头插入数据
    11.     dlink_insert(0, &iarr[1]);    // 向双向链表的表头插入数据
    12.     dlink_insert(0, &iarr[2]);    // 向双向链表的表头插入数据
    13.  
    14.     printf("dlink_is_empty()=%d\n", dlink_is_empty());    // 双向链表是否为空
    15.     printf("dlink_size()=%d\n", dlink_size());            // 双向链表的大小
    16.  
    17.     // 打印双向链表中的全部数据
    18.     int i;
    19.     int *p;
    20.     int sz = dlink_size();
    21.     for (i=0; i
    22.     {
    23.         p = (int *)dlink_get(i);
    24.         printf("dlink_get(%d)=%d\n", i, *p);
    25.     }
    26.  
    27.     destroy_dlink();
    28. }
    29.  
    30. void string_test()
    31. {
    32.     char* sarr[4] = {"ten", "twenty", "thirty", "forty"};
    33.  
    34.     printf("\n----%s----\n", __func__);
    35.     create_dlink();        // 创建双向链表
    36.  
    37.     dlink_insert(0, sarr[0]);    // 向双向链表的表头插入数据
    38.     dlink_insert(0, sarr[1]);    // 向双向链表的表头插入数据
    39.     dlink_insert(0, sarr[2]);    // 向双向链表的表头插入数据
    40.  
    41.     printf("dlink_is_empty()=%d\n", dlink_is_empty());    // 双向链表是否为空
    42.     printf("dlink_size()=%d\n", dlink_size());            // 双向链表的大小
    43.  
    44.     // 打印双向链表中的全部数据
    45.     int i;
    46.     char *p;
    47.     int sz = dlink_size();
    48.     for (i=0; i
    49.     {
    50.         p = (char *)dlink_get(i);
    51.         printf("dlink_get(%d)=%s\n", i, p);
    52.     }
    53.  
    54.     destroy_dlink();
    55. }
    56.  
    57. typedef struct tag_stu
    58. {
    59.     int id;
    60.     char name[20];
    61. }stu;
    62.  
    63. static stu arr_stu[] =
    64. {
    65.     {10, "sky"},
    66.     {20, "jody"},
    67.     {30, "vic"},
    68.     {40, "dan"},
    69. };
    70. #define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )
    71.  
    72. void object_test()
    73. {
    74.     printf("\n----%s----\n", __func__);
    75.     create_dlink();    // 创建双向链表
    76.  
    77.     dlink_insert(0, &arr_stu[0]);    // 向双向链表的表头插入数据
    78.     dlink_insert(0, &arr_stu[1]);    // 向双向链表的表头插入数据
    79.     dlink_insert(0, &arr_stu[2]);    // 向双向链表的表头插入数据
    80.  
    81.     printf("dlink_is_empty()=%d\n", dlink_is_empty());    // 双向链表是否为空
    82.     printf("dlink_size()=%d\n", dlink_size());            // 双向链表的大小
    83.  
    84.     // 打印双向链表中的全部数据
    85.     int i;
    86.     int sz = dlink_size();
    87.     stu *p;
    88.     for (i=0; i
    89.     {
    90.         p = (stu *)dlink_get(i);
    91.         printf("dlink_get(%d)=[%d, %s]\n", i, p->id, p->name);
    92.     }
    93.  
    94.     destroy_dlink();
    95. }
    96.  
    97. int main()
    98. {
    99.     int_test();        // 演示向双向链表操作“int数据”。
    100.     string_test();    // 演示向双向链表操作“字符串数据”。
    101.     object_test();    // 演示向双向链表操作“对象”。
    102.  
    103.     return 0;
    104. }

    2c++实现双链表

    实现代码

     

    1. #ifndef DOUBLE_LINK_HXX
    2. #define DOUBLE_LINK_HXX
    3.  
    4. #include 
    5. using namespace std;
    6.  
    7. template<class T>
    8. struct DNode
    9. {
    10.     public:
    11.         T value;
    12.         DNode *prev;
    13.         DNode *next;
    14.     public:
    15.         DNode() { }
    16.         DNode(T t, DNode *prev, DNode *next) {
    17.             this->value = t;
    18.             this->prev  = prev;
    19.             this->next  = next;
    20.            }
    21. };
    22.  
    23. template<class T>
    24. class DoubleLink
    25. {
    26.     public:
    27.         DoubleLink();
    28.         ~DoubleLink();
    29.  
    30.         int size();
    31.         int is_empty();
    32.  
    33.         T get(int index);
    34.         T get_first();
    35.         T get_last();
    36.  
    37.         int insert(int index, T t);
    38.         int insert_first(T t);
    39.         int append_last(T t);
    40.  
    41.         int del(int index);
    42.         int delete_first();
    43.         int delete_last();
    44.  
    45.     private:
    46.         int count;
    47.         DNode *phead;
    48.     private:
    49.         DNode *get_node(int index);
    50. };
    51.  
    52. template<class T>
    53. DoubleLink::DoubleLink() : count(0)
    54. {
    55.     // 创建“表头”。注意：表头没有存储数据！
    56.     phead = new DNode();
    57.     phead->prev = phead->next = phead;
    58.     // 设置链表计数为0
    59.     //count = 0;
    60. }
    61.  
    62. // 析构函数
    63. template<class T>
    64. DoubleLink::~DoubleLink()
    65. {
    66.     // 删除所有的节点
    67.     DNode* ptmp;
    68.     DNode* pnode = phead->next;
    69.     while (pnode != phead)
    70.     {
    71.         ptmp = pnode;
    72.         pnode=pnode->next;
    73.         delete ptmp;
    74.     }
    75.  
    76.     // 删除"表头"
    77.     delete phead;
    78.     phead = NULL;
    79. }
    80.  
    81. // 返回节点数目
    82. template<class T>
    83. int DoubleLink::size()
    84. {
    85.     return count;
    86. }
    87.  
    88. // 返回链表是否为空
    89. template<class T>
    90. int DoubleLink::is_empty()
    91. {
    92.     return count==0;
    93. }
    94.  
    95. // 获取第index位置的节点
    96. template<class T>
    97. DNode* DoubleLink::get_node(int index)
    98. {
    99.     // 判断参数有效性
    100.     if (index<0 || index>=count)
    101.     {
    102.         cout << "get node failed! the index in out of bound!" << endl;
    103.         return NULL;
    104.     }
    105.  
    106.     // 正向查找
    107.     if (index <= count/2)
    108.     {
    109.         int i=0;
    110.         DNode* pindex = phead->next;
    111.         while (i++ < index) {
    112.             pindex = pindex->next;
    113.         }
    114.  
    115.         return pindex;
    116.     }
    117.  
    118.     // 反向查找
    119.     int j=0;
    120.     int rindex = count - index -1;
    121.     DNode* prindex = phead->prev;
    122.     while (j++ < rindex) {
    123.         prindex = prindex->prev;
    124.     }
    125.  
    126.     return prindex;
    127. }
    128.  
    129. // 获取第index位置的节点的值
    130. template<class T>
    131. T DoubleLink::get(int index)
    132. {
    133.     return get_node(index)->value;
    134. }
    135.  
    136. // 获取第1个节点的值
    137. template<class T>
    138. T DoubleLink::get_first()
    139. {
    140.     return get_node(0)->value;
    141. }
    142.  
    143. // 获取最后一个节点的值
    144. template<class T>
    145. T DoubleLink::get_last()
    146. {
    147.     return get_node(count-1)->value;
    148. }
    149.  
    150. // 将节点插入到第index位置之前
    151. template<class T>
    152. int DoubleLink::insert(int index, T t)
    153. {
    154.     if (index == 0)
    155.         return insert_first(t);
    156.  
    157.     DNode* pindex = get_node(index);
    158.     DNode* pnode  = new DNode(t, pindex->prev, pindex);
    159.     pindex->prev->next = pnode;
    160.     pindex->prev = pnode;
    161.     count++;
    162.  
    163.     return 0;
    164. }
    165.  
    166. // 将节点插入第一个节点处。
    167. template<class T>
    168. int DoubleLink::insert_first(T t)
    169. {
    170.     DNode* pnode  = new DNode(t, phead, phead->next);
    171.     phead->next->prev = pnode;
    172.     phead->next = pnode;
    173.     count++;
    174.  
    175.     return 0;
    176. }
    177.  
    178. // 将节点追加到链表的末尾
    179. template<class T>
    180. int DoubleLink::append_last(T t)
    181. {
    182.     DNode* pnode = new DNode(t, phead->prev, phead);
    183.     phead->prev->next = pnode;
    184.     phead->prev = pnode;
    185.     count++;
    186.  
    187.     return 0;
    188. }
    189.  
    190. // 删除index位置的节点
    191. template<class T>
    192. int DoubleLink::del(int index)
    193. {
    194.     DNode* pindex = get_node(index);
    195.     pindex->next->prev = pindex->prev;
    196.     pindex->prev->next = pindex->next;
    197.     delete pindex;
    198.     count--;
    199.  
    200.     return 0;
    201. }
    202.  
    203. // 删除第一个节点
    204. template<class T>
    205. int DoubleLink::delete_first()
    206. {
    207.     return del(0);
    208. }
    209.  
    210. // 删除最后一个节点
    211. template<class T>
    212. int DoubleLink::delete_last()
    213. {
    214.     return del(count-1);
    215. }
    216.  
    217. #endif

  • 相关阅读:
    CCNA课程实验-14-Final_Lab
    c++之旅第七弹——继承
    初探PHP开源采集器----蓝天采集器
    vue项目启动npm install和npm run serve时出现错误Failed to resolve loader:node-sass
    linux安装zookeeper
    【软件与系统安全笔记】六、恶意代码的机理及其防护
    《荒野大镖客》游戏emp.dll丢失的修复方法，快速解决找不到emp.dll问题
    Nautilus Chain全球行分享会，上海站圆满举办
    导入现有项目maven到IDE的过程记录
    flutter简单的本地草稿箱功能
  • 原文地址：https://blog.csdn.net/SB202211/article/details/125865336