A
Published on
· Last modified on
· Public

简单数据结构学习:单向链表

嘛。。最近在用C++折腾链表,于是总结下,如有误欢迎指正 本文如无特殊说明,皆为C++代码,GCC编译通过

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针((Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。 链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。 ——维基百科《链表》

简单的说,就是一个结构的两个成员,一个放信息数据,另一个则指向下一个结点,依次遍历即可获得链上的数据,这就是单向链表。 看了这么多理论描述,来看看一张图,这样可能更好理解些。 简单数据结构:单向链表

用C/C++来表示即为这样的一个结构,包含两个成员变量,一个是数据(这里使用int,实际可根据需要自行替换类型),一个则为该结构类型的指针。

struct List
{
    int data; //信息域,存放数据
    List *pNext; //指针域,指向下一个链表元素结点
};

下面我们来构造一个链表,数据是0->2->4->6->8->10->12->14->16->18 根据链表特点,需要不断new List生成链表结点,然后使前一个结点指向后一个,整个链表的最后一个结点指向NULL。

List *CreateList()
{
    List *p = NULL; 
    List *q = NULL;
    List *head = NULL; 
    for (int i=0; i<10; i++){
        p = new List; //创建新的结点
        p->data = i * 2; //数据设定为i*2
        if (head == NULL) {
            head = p; //第一次循环,生成第一个结点
        }
        else {
            q->pNext = p; //将q的指针域指向新结点p
        } 
        q = p; //保存新指针到q,以便下次循环设定该结点的指针域
    }
    if (head != NULL){
        q->pNext = NULL; //若至少插入了一个结点,则将最后一个结点的指针域置为NULL,以此作为链表结束标识
    }

    return head;
}

那么接下来将链表打印出来看看吧!这就需要遍历链表了(・~・`)

void displayList(const List *head)
{
    while( head != NULL){
        cout << head->data; //输出数据
        head = head->pNext; //使head指向下一结点
        if ( head != NULL ){
            cout << "->"; //不是最后一结点则输出分隔符
        }
    }
    cout<< endl;
}

运行.成功≧∇≦ 输出结果:

0->2->4->6->8->10->12->14->16->18


完成了单向链表的创建和遍历,再来说说如何插入与删除。 因为链表的特性,插入与删除十分方便,只需要在前后两个结点进行操作。而数组等连续存储则必须重新申请全部数据的空间,并且复制。 因此插入与删除时,链表效率较高( ̄^ ̄゜)

单向链表之插入

还是先创建一个链表。

0->2->4->6->8->10->12->14->16->18

此时假设给定一个int,要求按数值大小插入链表中,此时有几步需要完成 1. 寻找要插入的位置 2. 创建新数据结点,插入数据,指针域指向插入位置的下一个结点 3. 修改前一数据结点的指针域,指向该新数据结点

  • 一个普遍的情形是,该位置在链表中,此时需要遍历并通过比较数据大小来找到位置。
  • 另一个特殊的情形则是,该位置位于第一个结点,此时第三步则变成修改head指针指向新结点。 (当链表存在头结点时还得处理下头结点的问题,注意“头结点”≠“第一个数据结点”,头结点并不用于存储数据,本文中不设头结点)

函数原型:void Insert(List *&head, List *node);

首先考虑特殊情形,当要插入的位置刚好位于链表首部时,此时较容易检测出,直接将node与head的数据比较即可(不会的自己回去复习( •̀д•́) ),而后直接执行第二步生成新结点后返回。

    if ( node->data <= head->data ) //1. 检测特殊情形
    {
        node->pNext = head; // 2. 指向之前的第一个第一个结点
        head = node;  //3. 修改
        return ; //完成了插入操作,可以返回啦
    }

更普遍的情形,就需要遍历链表并逐个比较数据大小啦( ̄^ ̄゜)

List *q = head->pNext, *p = head; // 因为首位置是特殊情形已处理,从第二个结点开始比较
while (q != NULL)
{
    if ( node->data > q->data )
    {
        p = q;
        q = q->pNext; //继续向下遍历
    }else{
        break; //找到位置,退出循环
    }

}

结束循环后,p所指向的即为要插入数据的前一结点 而后插入新结点

p->pNext = node;
node->pNext = q;

此时插入完成,执行返回return ; 整个函数如下:

void Insert(List *&head, List *node) //必须保证链表中数据为升序
{
    if ( node->data <= head->data )
    {
        node->pNext = head;
        head = node;
        return ;
    }
    List *q = head->pNext, *p = head;
    while (q != NULL)
    {
        if ( node->data > q->data )
        {
            p = q;
            q = q->pNext;
        }else{
            break;
        }
    }
    p->pNext = node;
    node->pNext = q;
    return ;
}

最后,我们可认为第一个结点之前还存在一个NULL结点,即可将该两种情形的代码逻辑合并。

void Insert(List *&head, List *node) //必须保证链表中数据为升序
{
    List *q = head, *p = NULL; //从第一个结点开始比较,设置第一个结点的前一个结点为NULL
    while (q != NULL)
    {
        if ( node->data > q->data )
        {
            p = q;
            q = q->pNext;
        }else{
            break;
        }
    }
    if (p != NULL) //要注意空指针问题,否则可能引起异常
        p->pNext = node;
    else
        head = node; //特殊情形,修改head指针指向新结点
    node->pNext = q;
    return ;
}

单向链表之删除

还是这个链表,与插入大同小异,除了插入中的那些坑,还需要注意下内存的释放。 直接上代码算了。相信只要会插入就可以看懂下面这段(/ω\)

void delete(List *&head, int data)
{
    List *q = head, *p = NULL;
    while (q != NULL)
    {
        if ( data != q->data )
        {
            p = q;
            q = q->pNext;
        }else{
            break;
        }
    }
    if (p != NULL){
        p->pNext = q->pNext; //链接前后结点
    }else{
        head = q->pNext; //修改head指针
    }
    delete q; //释放从链表脱离的结点所占用内存,否则内存泄漏
    return ;
}

转自我的个人博客,原文链接:link1 link2

S
Published on

还在很初级地学习 C++,已收藏。

顺带求星...

https://www.textarea.com/simodorg/solve-mactype-doesnt-work-in-visual-studio-2015-251/

S
Published on

顺便星了...

A
Published on
simodorg:

还在很初级地学习 C++,已收藏。

顺带求星...

https://www.textarea.com/simodorg/solve-mactype-doesnt-work-in-visual-studio-2015-251/

yixing

M
Published on
Sign in or Sign up Leave Comment