数据结构:线性表之链式存储结构

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其

直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像,称为结点(Node)。N个结点链结成一个链表,

即为线性表(a1,a2,...,an)的链式存储结构,因为此链表的每个节点中只包含一个指针域,所以叫做单链表。

我们把链表中的第一个结点的存储位置叫做头指针,,为了更方便地对链表进行操作,如删除第一个结点的特殊情况

(第一个结点没有前驱,而要摘除一个结点需要首先找到它的前驱才能做摘除操作),经常在单链表的第一个结点前附设一个结点,

称为头节点,这样头指针就指向了头节点。

单链表与数组的优缺点基本上是相反的,即单链表插入删除效率高,而查找需要遍历,效率较低。

示例程序:(改编自《大话数据结构》,增加了链表反转等)

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

typedef int ElemType;

typedef struct  Node
{
    ElemType data;
    struct Node *next;
} Node;

typedef Node *NodePtr;

bool InitList(NodePtr *Npp)
{
    *Npp = (NodePtr)malloc(sizeof(Node));/* 产生头结点,并使*Npp指向此头结点 */
    if (!(*Npp))
        return false; //分配失败

    (*Npp)->next = NULL;/* 指针域为空 */

    return true;
}

bool ListEmpty(NodePtr Np)
{
    if (Np->next == NULL)
        return true;
    else
        return false;
}

bool ClearList(NodePtr *Npp)
{
    cout << "Clear List..." << endl;
    NodePtr p = *Npp;
    if (!(p->next))
        return true;
    while (p->next)/*  没到表尾 */
    {
        NodePtr q = p->next;
        p->next = q->next;
        free(q);
    }

    return true;
}

int ListLength(NodePtr Np)
{
    cout << "List's length : ";
    NodePtr p = Np->next;/* p指向第一个结点 */
    int i = 0;

    while (p)
    {
        p = p->next;
        ++i;
    }

    return i;
}
/* 操作结果:用ptr返回Np中第pos个数据元素的值 */
bool GetElem(NodePtr Np, int pos, ElemType *ptr)
{
    cout << "Get Item from pos " << pos << " : ";
    NodePtr p = Np->next;
    int i = 1;
    /* p不为空或者计数器i还没有等于pos时,循环继续 */
    while (p && i < pos)
    {
        p = p->next;
        ++i;
    }

    if (!p)
        return false;
    *ptr = p->data;/*  取第pos个元素的数据 */
    return true;
}
/* 返回Np中第1个与Elem满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在,则返回值为0 */
int LocateElem(NodePtr Np, ElemType Elem)
{
    cout << "Item " << Elem << "'s pos : ";
    NodePtr p = Np->next;
    int i = 1;

    while (p && p->data != Elem)
    {
        p = p->next;
        ++i;
    }

    if (!p)
        return 0;
    return i;
}
/* 操作结果:在Np中第pos个位置之前插入新的数据元素Elem,Np的长度加1 */
bool ListInsert(NodePtr *Npp, int pos, ElemType Elem)
{
    cout << "Insert List pos " << pos << " Item " << Elem << endl;
    NodePtr p = *Npp;
    int i = 1;

    while (p && i < pos)
    {
        p = p->next;
        ++i;
    }

    if (!p)
        return false;

    NodePtr In = (NodePtr)malloc(sizeof(Node));
    In->data = Elem;
    In->next = p->next;/* 将p的后继结点赋值给In的后继  */
    p->next = In;  /* 将In赋值给p的后继 */

    return true;
}
/* 删除Npp的第pos个数据元素,并用ptr返回其值,Npp的长度减1 */
bool ListDelete(NodePtr *Npp, int pos, ElemType *ptr)
{
    cout << "Delete List Item in pos " << pos << endl;
    NodePtr p = *Npp;
    int i = 1;

    while (p && i < pos)
    {
        p = p->next;
        ++i;
    }

    if (!p)
        return false;

    NodePtr q = p->next;
    *ptr = q->data;
    p->next = q->next;/* 将q的后继赋值给p的后继 */
    free(q);

    return true;
}

bool ListTraverse(NodePtr Np)
{
    cout << "List's Items : ";
    NodePtr p = Np->next;
    while (p)
    {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
    return true;
}
/*  随机产生n个元素的值,建立带表头结点的单链线性表Npp(头插法) */
void CreateListHead(NodePtr *Npp, int num)
{
    cout << "Create List from Head ..." << endl;
    if (*Npp != NULL)
        free(*Npp);
    *Npp = (NodePtr)malloc(sizeof(Node));
    (*Npp)->next = NULL;/*  先建立一个带头结点的单链表 */
    srand(time(NULL));

    for (int i = 0; i < num; i++)
    {
        NodePtr p = (NodePtr)malloc(sizeof(Node));
        p->data = rand() % 100 + 1; //随机数
        p->next = (*Npp)->next;
        (*Npp)->next = p;/*  插入到表头 */
    }

}
/*  随机产生n个元素的值,建立带表头结点的单链线性表Npp(尾插法) */
void CreateListTail(NodePtr *Npp, int num)
{
    cout << "Create List from Tail ..." << endl;
    if (*Npp != NULL)
        free(*Npp);
    *Npp = (NodePtr)malloc(sizeof(Node));
    (*Npp)->next = NULL;
    srand(time(NULL));

    NodePtr tail = *Npp; /* tail为指向尾部的结点 */
    for (int i = 0; i < num; i++)
    {
        NodePtr p = (NodePtr)malloc(sizeof(Node));
        p->data = rand() % 100 + 1;
        tail->next = p;  /* 将表尾终端结点的指针指向新结点 */
        tail = p; /* 将当前的新结点定义为表尾终端结点 */
    }

    tail->next = NULL;
}
/* 反转单链表*/
NodePtr ReverseList(NodePtr head)
{
    cout << "Reverse List ...." << endl;
    if(NULL == head->next || NULL == head->next->next)
        return head;
    NodePtr p;
    NodePtr q;
    NodePtr r;
    p = head->next;
    q = p->next;
    head->next->next = NULL;
    while(q)
    {
        r = q->next; //
        q->next = p;
        p = q; //
        q = r; //
    }
    head->next = p;
    return head;
}

int main(void)
{
    NodePtr Np; //头指针
    InitList(&Np);
    for (int i = 1; i < 5; i++)
        ListInsert(&Np, i, i);

    if (!ListEmpty(Np))
        cout << ListLength(Np) << endl;
    ListTraverse(Np);

    cout << LocateElem(Np, 3) << endl;

    int get;
    GetElem(Np, 2, &get);
    cout << get << endl;

    ClearList(&Np);
    cout << ListLength(Np) << endl;

    CreateListHead(&Np, 10);
    ListTraverse(Np);
    int result;
    ListDelete(&Np, 5, &result);
    ListTraverse(Np);

    ClearList(&Np);
    CreateListTail(&Np, 10);
    ListTraverse(Np);
    ListTraverse(ReverseList(Np));

    ClearList(&Np);

    return 0;
}

输出为:

注意:程序中使用的单链表反转的方法是:使用p和q连个指针配合工作,使得两个节点间的指向反向,同时用r记录剩下的链表。

下图是不含头节点时的单链表反转情况,含头节点的单链表反转有细微区别,需小心。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏恰同学骚年

数据结构基础温故-2.栈

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,...

483
来自专栏互扯程序

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:...

4436
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

694
来自专栏和蔼的张星的图像处理专栏

数据结构栈队列链表树二叉查找树

这学期刚回到所里的时候把c++数据结构看了一遍,基本的数据结构照着视频也敲了一遍,不过那个时候自己对c++的了解只限于一些基本的语法,c++primer也还没有...

954
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(三) ——Redis中的链表

《Redis设计与实现》读书笔记(三) ——Redis中的链表 (原创内容,转载请注明来源,谢谢) 一、概述 链表在redis底层实现广泛,例如redis的li...

3496
来自专栏流浪猫的golang

golang 的container/list (一)

问题1:有了slice,还要list做什么? 问题2:list的底层实现是什么? 带着这两个问题来什么有浅入深的学习golang 语言 。 首先来看...

632
来自专栏codingforever

经典算法巡礼(七) -- 排序之堆排序

很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现...

222
来自专栏Java3y

TreeMap就这么简单【源码剖析】

1785
来自专栏深度学习与计算机视觉

算法-两个栈实现队列

题目: 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的...

18910
来自专栏MelonTeam专栏

图解Objective-C对象模型

目录: 1.这就是Objective-C对象模型吗? 2.Objective-C对象结构 3.Meta Class(元类) 4.代码验证 5.推荐...

2019

扫码关注云+社区