数据结构笔记(二):线性表之链表的简单实现

发布于 / 程序猿 / 0 条评论

使用C++简单实现链表,完成增删查改以及输出与合并功能。若文中存在错误,敬请指出,感谢阅读。

不得不说,想要完全理解链表还是有一定难度的,所以,一步一步来提高吧。


基本知识

单链表是一种链式存储的数据结构,用一组地址(任意的存储单元)存放线性表中的数据元素。它的数据是以节点(类型一般为结构体)来表示的,每个节点构成:数据 + 指针(结构体指针),数据就是链表里具体要存储的东西,指针就是用来把每个节点连接起来,使它们形成一个链状。

链表是一次只开辟一个节点的空间,用来存储当前要保存的数据及指向下一个节点或NULL的指针,所以其空间大小为动态变化的。

单链表访问随机元素的平均时间复杂度为O(n),随机插入删除元素的时间复杂度为0(1)[忽略找到位置的时间]。


演示

  • 创建一个线性表

  • 在第二个位置(77前)进行插入操作

  • 在第四个位置(6)进行删除操作


代码

#include <iostream>
#include <cstdio>
#include <cstdlib>

/*
纯C写法
struct node_t{
    int data;
    struct node_t *next; // struct不可省略
};

typedef struct node_t Node; // 使用node代替struct node_t

typedef Node* LinkedList; // 指向Node的LinkedList
*/

struct  Node
{
    int data; // 节点数据(存储当前节点数据)
    Node * next; // 节点指针(指向下一个指针)
};

typedef Node* LinkedList; // 指向Node的LinkedList

Node* _advanceLinkedList(LinkedList List, int pos) // 用循环使指针找到相应位置
{
    Node* pt = List;
    int i = -1; // 初始位置从-1开始
    while (pt && i < pos)
    {
        pt = pt->next; // 后移一个节点
        ++i;
    }
    return pt; // 返回
}

LinkedList createLinkedList() // 创建链表
{
    LinkedList ret = NULL; // 初始化
    ret = (LinkedList)malloc(sizeof(LinkedList)); // 分配内存
    // ret = new int [sizeof(LinkedList)]; // -- CPP
    ret->next = NULL; // 指向空
    return ret;
}

int insertLinkedList(LinkedList List, int pos, int newvalue) // 插入
{
    Node* pt = _advanceLinkedList(List, pos - 1); // 找到插入位置前一个
    if (!pt) // 如果链表为空则返回-1
        return -1;

    Node* q = (Node *)malloc(sizeof(Node)); // 分配内存存储插入的值
    q->data = newvalue; // 三步操作完成插入
    q->next = pt->next;
    pt->next = q;
    return 0;
}

int removeLinkedList(LinkedList List, int pos) // 删除
{
    Node *pt = _advanceLinkedList(List, pos - 1); // 找到删除位置前一个
    if (!pt) // 如果链表为空则返回-1
        return -1;

    Node* q = pt->next; // 三步操作完成删除
    pt->next = q->next;
    free(q);
    return 0;
}

int atLinkedList(LinkedList const List, int pos, int *pResult) // 查询
{
    Node *pt = _advanceLinkedList(List, pos); // 找到查询位置
    if (!pt) // 如果链表为空则返回-1
        return -1;

    *pResult = pt->data; // 保存查询的值 -- 改掉线性表中bug
    return 0;
}

int modifyLinkedList(LinkedList const List, int pos, int newvalue) // 修改
{
    Node *pt = _advanceLinkedList(List, pos); // 找到修改位置
    if (!pt) // 如果链表为空则返回-1
        return -1;
    pt->data = newvalue; // 修改值
    return 0;
}

int sizeLinkedList(LinkedList const List) // 链表大小,无需修改故加const限定
{
    int ret = -1; // 初始位置从-1开始
    Node const *pt = List;
    while (pt) // 不停后移直至为空
    {
        pt = pt->next; // 后移一个节点
        ++ret;
    }
    return ret;
}

int printLinkedList(LinkedList const List) // 输出,无需修改故加const限定
{
    if (!List) // 如果链表为空则返回-1
        return -1;
    Node const *pt = List->next;
    int ret = 0;
    while(pt)
    {
        printf("%d ", pt->data); // 从第一个位置(0)开始输出值
        pt = pt->next; // 后移一个位置
        ++ret;
    }
    printf("\n");
    return ret;
}

int destroyLinkedList(LinkedList *pt) //销毁链表,回收内存
{
    while ((*pt)->next) // 不为空,则删除
        removeLinkedList(*pt, 0);
    // free(pt); // segmentation fault
    pt = NULL;
    // delete [] pt; // -- CPP
    return 0;
}

LinkedList mergeLinkedList(LinkedList a, LinkedList b) // 合并
{
    LinkedList ret = createLinkedList();
    if (!ret)
        return NULL;

    Node *pa = a->next;
    Node *pb = b->next;
    Node *pc = ret;
    while (pa) // 先保存a表
    {

        pc->next = pa;
        pa = pa->next;
        pc = pc->next;
    }
    pc->next = pb; // 后存b表
    return ret; // 返回合并后的表
}

int main()
{
    return 0;
}


  • main()函数操作1
int main()
{
    LinkedList A = createLinkedList(); // 创建一个链表
    int a[10] = {2, 3, 5, 6, 9, 4, 8, 7}; 
    for (int i = 0; i < 8; ++i) // 插入
        insertLinkedList(A, i, a[i]);
    printLinkedList(A); // 输出
    for (int i = 0; i < 8; ++i)
    {
        // removeLinkedList(A, i); // 这个bug改了一个小时我脑抽了
        removeLinkedList(A, 0); // 删除
        printLinkedList(A);
    }
    destroyLinkedList(&A); // 销毁链表,回收内存
    return 0;
}
/*
2 3 5 6 9 4 8 7
3 5 6 9 4 8 7
5 6 9 4 8 7
6 9 4 8 7
9 4 8 7
4 8 7
8 7
7
*/
  • main()函数操作2
int main()
{
    LinkedList B = createLinkedList();
    int b[10] = {1, 2, 3, 9, 8, 7, 5, 6, 4};
    for (int i = 0; i < 9; ++i)
        insertLinkedList(B, i, b[i]);
    printLinkedList(B);
    int idx, pos, value;
    while (scanf("%d", &idx) == 1 && idx)
    {
        if (idx == 1) // 增
        {
            scanf("%d%d", &pos, &value);
            insertLinkedList(B, pos, value);
        }
        else if (idx == 2) // 删
        {
            scanf("%d", &pos);
            removeLinkedList(B, pos);
        }
        else if (idx == 3) // 查
        {
            scanf("%d", &pos);
            int result = 0;
            atLinkedList(B, pos, &result);
            printf("%d\n", result);
        }
        else if (idx == 4) // 改
        {
            scanf("%d%d", &pos, &value);
            modifyLinkedList(B, pos, value);
        }
        else if (idx == 5) //输出
            printLinkedList(B);
    }
    destroyLinkedList(&B);
    return 0;
}
/*
1 2 3 9 8 7 5 6 4
1 0 21
5
21 1 2 3 9 8 7 5 6 4
1 8 666
5
21 1 2 3 9 8 7 5 666 6 4
2 1
2 2
2 3
5
21 2 9 7 5 666 6 4
3 4
5
5
21 2 9 7 5 666 6 4
4 4 233
5
21 2 9 7 233 666 6 4
0
*/
  • main()函数操作3
int main()
{
    LinkedList C = createLinkedList();
    LinkedList D = createLinkedList();

    int c[10] = {2, 3, 5, 6, 9, 4, 8, 7};
    int d[10] = {1, 2, 3, 9, 8, 7, 5, 6, 4};
    for (int i = 0; i < 8; ++i)
        insertLinkedList(C, i, c[i]);
    for (int i = 0; i < 9; ++i)
        insertLinkedList(D, i, d[i]);
    printLinkedList(mergeLinkedList(C, D));

    destroyLinkedList(&C);
    destroyLinkedList(&D);
    return 0;
}
/*
2 3 5 6 9 4 8 7 1 2 3 9 8 7 5 6 4
*/

时间复杂度分析

  • 插入:O(1)[头插入/尾插入]
  • 删除:O(1)[头删除/尾删除]
  • 合并:O(n)

推荐

其中知乎这个问题下有些很不错的回答,认真去看了,你会回来感谢我的,CSDN的这篇有关链表各种操作的博客讲解的非常详细。

不多说了。

最后,致敬迅哥


The end.
2017-10-21 星期六

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(二):线性表之链表的简单实现
Not Comment Found