首页 > itarticle > 数据结构

数据结构

admin 11月 28, 2020 0

数据结构是一个早就有所耳闻的东西，但是一直没有潜下心学习过，对数据结构的了解也仅限于 C++里的 STL，趁寒假有空闲，去听了浙江大学陈越老师的数据结构课程。当然，计算机领域的各种知识，只有亲自尝试了才能算是真的学得懂，因此，打算开个专题，将各个类型的数据结构都亲自实现一遍，并记录下来。

链表

以下内容摘自维基百科

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

实现

本次实现是拿 C 语言实现的，但是因为个人编程习惯的原因，将 int 包装成了 bool 类型并使用。多数函数采用 bool 作为返回值，用于检查是否执行成功。

节点

链表的一个很重要的特点是其结构由一些节点连接起来，各个节点是组成链表的最小单位。

一个节点由数据域和指针域组成，考虑用结构来表示。为表示方便，包装一个链表的数据类型。

1
2
3
4
5
6
 
typedef struct 
{
    ElementType data;
    struct  *next;
} Node;
typedef Node *LinkList;

创建

创建链表有两种基本的方式，分别是有头结点的链表和没有头结点的链表，在实际实现过程中，有头结点的链表实现起来更安全，也更加容易，因此采用有头结点的链表。

所以创建链表实际上就是建立了一个头结点，数据域不重要，指针域指向 NULL。

1
2
3
4
5
6
7
 
LinkList CreateLink()
{
    
    LinkList link = (LinkList)malloc(sizeof(Node));
    link->next = NULL;
    return link;
}

插入节点

在索引为index的位置插入值为data的节点。

假设在索引为 (index-1) 的位置有节点node1，索引为 (index) 的位置有节点node2,则node1指向node2。

实现的思路是先新建一个节点node3,先让node3指向node2,然后让node1指向node3

InsertNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
bool InsertData(const LinkList linkList, unsigned const int index, const ElementType data)
{
    //在对应索引的位置插入节点
    Node *iterator = linkList->next;
    int i = 0;
    for (; iterator; i++, iterator = iterator->next)
    {
        if (i == index - 1)
        {
            Node *node = (Node *)malloc(sizeof(Node));
            if (node)
            {
                node->data = data;
                node->next = iterator->next;
                iterator->next = node;
                return true;
            }
            return false;
        }
    }
    return false;
}

删除节点

删除索引为index的节点。

假设有连续三个节点node1，node2，node3，想要删除node2节点，只需要让node1的指针域指向node3，然后回收node2节点的内存即可。

DeleteNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
bool DeleteDataByIndex(const LinkList linkList, unsigned const int index)
{
    //删除对应索引的的节点
    Node *beforeIterator = linkList;
    Node *deleteIterator = linkList->next;
    int i = 0;
    for (; deleteIterator; i++, beforeIterator = deleteIterator, deleteIterator = deleteIterator->next)
    {
        if (i == index)
        {
            beforeIterator->next = deleteIterator->next;
            free(deleteIterator);
            return true;
        }
    }
    return false;
}

修改节点

修改索引为index的节点值为data。

基本思路来就是定位到索引的位置，然后修改具体的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
bool ChangeDataByIndex(const LinkList linkList, unsigned const int index, const ElementType data)
{
    //修改索引对应的节点
    Node *iterator = linkList->next;
    int i = 0;
    for (; iterator; i++, iterator = iterator->next)
    {
        if (i == index)
        {
            iterator->data = data;
            return true;
        }
    }
    return false;
}

反转

反转整条链表。

最开始我以为实现这个的做法改成双向链表，然后做标记，但后来才了解到,的确是一条单向链表的反转,而且实现过程相当巧妙。

基本思路是：

1. 用三个指针记录下连续的三个节点地址
2. 修改第二个节点的next使其指向第一个节点
3. 三个指针后移
4. 如果没有到达末尾，返回1
5. 修改头指针和第一个节点的next
6. 反转结束

不过要注意的是，节点数较少时要做特殊处理。

Reverse

Reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
void ReverseLink(const LinkList linkList)
{
    //反转链表
    Node *first = linkList->next;
    if (!first || !first->next)
    {
        return;
    }
    Node *second = first->next;
    if (!second->next)
    {
        linkList->next = second;
        second->next = first;
        first->next = NULL;
        return;
    }
    Node *third = second->next;

    while (true)
    {
        second->next = first;
        first = second;
        second = third;
        if (!third)
        {
            break;
        }
        third = third->next;
    }
    linkList->next->next = NULL;
    linkList->next = first;
}

排序

将整条链排序

emm…，学习过之后才发现链表竟然如此神奇，本来我以为链表只能访问相邻的元素顶多就冒泡排序了。

结果，至少可以冒泡、选择、插入、快排、归并、希尔、堆排序等等……

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能