带头结点的链表

1、链表和顺序表

链表是很常见的数据结构,链表总是会和线性顺序表来比较。

1.1、顺序表

  • 具有随机存储的特性,给定位置就能通过计算找到数据所在位置,因为在分配存储空间的时候,是连续分配的,所以读取很快。
  • 因为事先要开辟一块空间,过大会造成空间浪费,过小会溢出,所以在存储位置长度的数据时,表现不是很好。
  • 在插入和删除元素时,涉及到元素的移动,最坏情况下要移动表里所有元素,效率不高。

1.2、链表

  • 通过指向下一结点的指针,来找到下一个元素,每个节点要存储数据信息和指向下一结点的指针,从空间利用率上来说,不如顺序表。
  • 不具有随机存储的特点,例如想找到下标为5的元素,顺序表可以直接访问,而链表必须逐个调整,最后才能找到这个元素。
  • 插入、删除效率高,相较于顺序表的移动元素,链表只需调整指针指向的元素。

1.3、比较

  • 对于随机读取次数多,且对插入、删除需求小的时候,可以用顺序表来存储,更合理。
  • 对于插入、删除需求频繁的时候,可以用链表来存储,更合理。
  • 如果内存中碎片多,此时可能无法开辟一块连续的大空间,从而无法创建顺序表,此时可以使用链表。

2、单链表

2.1、两种类型

有许多种链表,单链表就是很常见的一种链表类型。即只能从前向后遍历,无法从后向前遍历。其中单链表又有带头和不带头之分,听起来怎么有点吓人……

  • 不带头链表中第一个结点就是我们所存储的元素的结点。
  • 带头链表中第一个结点存储的元素为空,这个就是所谓的头,第二个结点才是我们存储的元素。

2.2、比较

  • 不带头链表在第一个结点之前插入和删除第一个结点的时候,会出现特殊情况,使得操作不方便。
  • 带头链表,因为第一个有效的结点实际上是第二结点,所以避免了上述的情况。

3、基于C++的代码

3.1、给出类的基本构造

#include <iostream>
using namespace std;
template<class T>
class Node
{
private:
    Node* link;
    T element;
public:
    Node* getLink(){return link;}
    T getElement(){return element;}
    void setElement(T x){element = x;}
    void setLink(Node<T>* x){link = x;}
};
template<class T>
class SingleList
{
public:
    SingleList() { first = new Node<T>; first->setLink(NULL); length = 0; };
    ~SingleList();
    bool isEmpty() const;
    int Length() const;
    bool Find(int i, T& x)const;
    Node<T>* Find(int i)const;
    int Search(T x)const;
    bool Insert(int i, T x);
    bool Delete(int i);
    bool Update(int i, T x);
    void Clear();
    void Output(ostream& out)const;

private:
    Node<T>*first;
    int length;
};
  • Node类是结点类
  • isEmpty返回bool类型,判断表是否为空
  • Length返回表长度
  • Find(int i, T& x),找到第i个结点,并将结点内的值放在x中保存
  • Find(int i) 找到第i个结点并返回
  • Search找到指定元素,并返回其位置
  • Insert向指定位置插入元素
  • Delete删除指定位置元素
  • Update更新指定位置元素
  • Clear清除表
  • Output输出表中元素

3.2、类的实现

template<class T>
void SingleList<T>::Output(ostream& out) const
{
        if (length==0)
    {
        out<<"The SingeList is null";
        return;
    }
    Node<T>*p = first->getLink();
    while (p != NULL)
    {
        out << p->getElement() << " ";
        p = p->getLink();
    }
    out << endl;
}

template<class T>
void SingleList<T>::Clear()
{
    Node<T>*p = first->getLink();
    while (p != NULL)
    {
        Node<T>* q = p;
        p = p->getLink();
        delete q;
    }
    length = 0;
}

template<class T>
bool SingleList<T>::Update(int i, T x)
{
    Node<T>* p = Find(i);
    if (p == NULL) return false;
    p->setElement(x);
    return true;
}

template<class T>
bool SingleList<T>::Delete(int i)
{
    Node<T>*p;
    if (i == 0)
        p = first;
    else
    {
        p = Find(i - 1);
        if (p == NULL)return false;
    }
    //找到第i-1个结点
    Node<T>*q = p->getLink();//q是第i个结点
    p->setLink(q->getLink());//第i-1个结点指向第i+1个结点
    delete q;//删除第i个结点
    length--;//减小长度
    return true;

}

template<class T>
bool SingleList<T>::Insert(int i, T x)
{
    Node<T>*p;
    if (i==0)
        p = first;
    else
    {
        p = Find(i - 1);
        if (p == NULL)return false;
    }
    //以上是找到第i-1个结点,越界判断在Find函数里
    Node<T>* newNode = new Node<T>;//生成新插入的结点
    newNode->setElement(x);//赋值
    newNode->setLink(p->getLink());//新结点指向原来的第i个结点
    p->setLink(newNode);//第i-1个结点指向新结点
    length++;//表长度增加
    return true;
}

template<class T>
int SingleList<T>::Search(T x) const
{
    if (length == 0)//如果表里没有元素,则直接返回
    {
        cout << "The SingleList is null!";
        return -1;
    }
    Node<T>*p = first->getLink();
    int position = 0;//位置信息
    while (p != NULL)
    {
        if (p->getElement() == x) return position;//找到元素,返回位置
        p = p->getLink();
        position++;
    }
    cout << "Don't find the element!";
    return -1;
}
template<class T>
Node<T>* SingleList<T>::Find(int i) const
{
    if (i > length - 1 || i < 0)//越界检查
    {
        cout << "Out of Bounds!";
        return NULL;
    }
    Node<T>* p = first->getLink();//从第一个有效元素开始查找
    for (int j = 0; j < i; j++)
    {
        p = p->getLink();//逐个调整,知道指向第i个元素
    }
    return p;
}
template<class T>
bool SingleList<T>::Find(int i, T& x) const
{
    Node<T>* p = Find(i);
    if (p == NULL) return false;
    x = p->getElement();
    return true;
}

template<class T>
int SingleList<T>::Length() const
{
    return length;
}

template<class T>
bool SingleList<T>::isEmpty() const
{
    if (length == 0) return true;
    else return false;
}

template<class T>
SingleList<T>::~SingleList()
{
    Node<T>*p;
    while (first != NULL)
    {
        p = first->getLink();//找到当前删除结点的下一个结点
        delete first;//删除当前结点
        first = p;
    }
}

除了删除和插入以外,其他的方法实现起来都不困难,唯一有些复杂的就是插入和删除,要想好先后执行的操作,从老师的PPT里找到的图片


插入和删除.png
  • 插入时,先将新结点指向原来的第i个结点,再让第i-1个结点指向新结点。
  • 删除时,找到第i-1个结点和第i个结点,让第i-1个结点指向第i+1个结点,删除第i个结点。

至此整个基本的带头单链表就完成了,让我们来测试一下吧!

4、测试

测试代码如下

#include "SingleList.h"
#include "iostream"
using namespace std;
int main()
{
    SingleList<int> newlist;
    newlist.Insert(0, 1);
    newlist.Insert(0, 2);
    newlist.Insert(0, 3);
    newlist.Insert(0, 4);
    newlist.Insert(2, 20);
    newlist.Output(cout);
    newlist.Delete(1);
    newlist.Output(cout);
    cout<<newlist.Length()<<endl;
    cout << newlist.isEmpty() << endl;
    cout << newlist.Search(1)<<endl;
    cout << newlist.Search(5)<<endl;
    int n;
    newlist.Find(1, n);
    cout << n << endl;
    cout << newlist.Find(2)->getElement()<<endl;
    newlist.Update(2, 55);
    newlist.Output(cout);
    newlist.Clear();
    newlist.Find(0);
    cin >> n;
    return 0;
}

我们先预测一下输出,应该是
4 3 20 2 1
4 20 2 1
4
0
3
don't find the element!
20
2
4 20 55 1
out of bounds!

运行程序

测试.JPG

运行结果符合我们的预期,这样就基本实现了单链表

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,468评论 5 473
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,620评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,427评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,160评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,197评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,334评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,775评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,444评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,628评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,459评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,508评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,210评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,767评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,850评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,076评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,627评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,196评论 2 341

推荐阅读更多精彩内容

  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,140评论 0 25
  • 链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢? 可以...
    rainchxy阅读 1,909评论 0 6
  • 本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 2,860评论 0 7
  • 1.线性表的定义 线性表:零个或多个数据元素的有限序列序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元...
    e40c669177be阅读 2,024评论 6 15
  • 【以前的我们】 “妈,你别唠叨了,你说的我都知道!” “妈,我还有事要忙,下次再说!” “也不是很久没回家,不就半...
    一奕阅读 317评论 0 0