专栏首页趣学算法数据结构 第4讲 单链表

数据结构 第4讲 单链表

数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位置。如图所示:

从图中可以看出,每个结点包含两个域:数据域和指针域,指针域存储下一个结点的地址,因此指针指向的类型也是结点类型。

结点结构体的定义:

定义了结点之后,我们就可以把若干个结点连接在一起,形成一个链表:

是不是像一个铁链子,一环扣一环的连在一起?

不管这个铁链子有多长,只要我们找到它的头,就可以拉起整个铁链子,因此我们给这个链表设置一个头指针,这个链表中的每个结点都可以找到了。

有时候为了操作方便,我们还会给链表增加一个不存放数据的头结点:

就像是给铁链子加个钥匙扣:

我们可以看到刚才的链表每个指针都是指向下一个结点,都是朝向一个方向的,这样的链表称为单向链表,或单链表

在顺序表中,想找第i个元素,就可以立即通过L.elem[i-1]找到,称为随机存取方式,而在单链表中,想找第i个元素?没那么容易,必须从头开始,按顺序一个一个来,一直数到第i个元素,称为顺序存取方式。

下面以带头结点的单链表为例,讲解单链表的初始化、创建、取值、查找、插入、删除操作。

1. 单链表初始化

单链表初始化是指构建一个空表:

bool InitList_L(LinkList &L)//构造一个空的单链表L

{

L=new LNode; //生成新结点作为头结点,用头指针L指向头结点

    if(!L)

return false; //生成结点失败

    L->next=NULL; //头结点的指针域置空

    return true;

}

2. 单链表的创建

创建单链表分为前插法尾插法两种,前插法创建的单链表和输入顺序正好相反,因此称为逆序建表,尾插法创建的单链表和输入顺序一致,因此称为正序建表。

前插法建表如图:

  • 初始状态
  • 输入数据元素1,创建新结点,把元素1放入新结点数据域:

s=new LNode; //生成新结点s cin>>s->data; //输入元素值赋给新结点的数据域

  • 前插操作,插入到头结点的后面:
  • 输入数据元素2,创建新结点,把元素2放入新结点数据域:
  • 前插操作,插入到头结点的后面:

解释:

为什么要先修改后面那个指针呢?

因为一旦修改了L结点的指针域指向s,那么原来L结点后面的结点就找不到了,

注意:修改指针顺序的原则:先修改没有指针标记的那一端。

如果要插入结点的两端都有标记,例如再定义一个指针q指向第1个结点,那么先修改哪个指针都无所谓了。

拉直链表之后:

  • 继续依次输入数据元素3,4,5,6,7,8,9,10,前插法创建链表的结果:
void CreateList_H(LinkList &L)//前插法创建单链表
{
    int n; //输入n个元素的值,建立到头结点的单链表L
    LinkList s; //定义一个指针变量
    L=new LNode;
    L->next=NULL; //先建立一个带头结点的空链表
    cout <<"请输入元素个数n:" <<endl;
    cin>>n;
    cout <<"请依次输入n个元素:" <<endl;
    cout <<"前插法创建单链表..." <<endl;
    while(n--)
{
        s=new LNode; //生成新结点s
        cin>>s->data; //输入元素值赋给新结点的数据域
        s->next=L->next;
        L->next=s; //将新结点s插入到头结点之后
    }
}

尾插法建表如图:

  • 初始状态(尾插法需要一个尾指针永远指向链表的尾结点)
  • 输入数据元素1,创建新结点,把元素1放入新结点数据域:

s=new LNode; //生成新结点s cin>>s->data; //输入元素值赋给新结点的数据域

  • 尾插操作,插入到尾结点的后面:

解释:

  • 输入数据元素2,创建新结点,把元素2放入新结点数据域:
  • 尾插操作,插入到尾结点的后面:
  • 继续依次输入数据元素3,4,5,6,7,8,9,10,前插法创建链表的结果:
void CreateList_R(LinkList &L)//尾插法创建单链表
{
    //输入n个元素的值,建立带表头结点的单链表L
    int n;
    LinkList s, r;
    L=new LNode;
    L->next=NULL; //先建立一个带头结点的空链表
    r=L; //尾指针r指向头结点
    cout <<"请输入元素个数n:" <<endl;
    cin>>n;
    cout <<"请依次输入n个元素:" <<endl;
    cout <<"尾插法创建单链表..." <<endl;
    while(n--)
{
        s=new LNode;//生成新结点
        cin>>s->data; //输入元素值赋给新结点的数据域
        s->next=NULL;
        r->next=s;//将新结点s插入尾结点r之后
        r=s;//r指向新的尾结点s
    }
}

3. 单链表取值

单链表的取值不像顺序表那样可以随机访问任何一个元素,单链表只有头指针,各个结点的物理地址是不连续的,要想找到第i个结点,就必须从第一个结点开始按顺序往后数,一直数到第i个结点。

那么具体怎么做呢?

注意:链表的头指针不可以随意改动!一个链表是由头指针来标识的,一旦头指针改动或丢失,这个链表就不完整或找不到了。想想看,你拉着铁链子一头,另一端绑着水桶,到井里打水,你手一松,链子掉井里,找不到了。所以链表的头指针是不能随意改动的,如果需要用指针移动,可定义一个指针变量进行移动。

可以定义一个p 指针,指向第一个元素结点,用j作为计数器,j=1;

然后p指向p的下一个结点,即:

p=p->next; //p指向下一个结点

j++; //计数器j加1

直到p为空或者j=i停止,p为空说明没有数到i,链表就结束了,j=i说明找到了第i个结点。

bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
{
    //在带头结点的单链表L中查找第i个元素
    //用e记录L中第i个数据元素的值
    int j;
    LinkList p;
    p=L->next; //p指向第一个数据结点
    j=1; //j为计数器
    while (j<i && p) //顺着链表向后扫描,直到p指向第i个元素或p为空
{
        p=p->next; //p指向下一个结点
        j++; //计数器j相应加1
    }
    if (!p || j>i)
        return false; //i值不合法i>n或i<=0
    e=p->data; //取第i个结点的数据域
    return true;
}

4. 单链表查找

在一个单链表中查找是否存在元素e,可以定义一个p 指针,指向第一个元素结点,比较p指向结点的数据域是否为e,如果相等,查找成功返回true,如果不等,则p指向p的下一个结点,即:

p=p->next; //p指向下一个结点

继续比较,如果p为空,查找失败返回false。

bool LocateElem_L(LinkList L, int e) //在带头结点的单链表L中查找值为e的元素
{
    LinkList p;
    p=L->next;
    while (p && p->data!=e)//沿着链表向后扫描,直到p空或p所指结点数据域等于e
        p=p->next; //p指向下一个结点
    if(!p)
return false; //查找失败p为NULL
return true;
}

5. 单链表插入

如果要在第i个结点之前插入一个元素,则必须先找到第i-1个结点,想一想:为什么?

单链表只有一个指针域,是向后操作的,不可以向前处理,第i个结点之前插入一个元素相当于把新结点放在第i-1个结点和第i个结点之间。

解释:

是不是有似曾相识的感觉?

前面讲的前插法建链表,就是每次将新结点插入到头结点和第一个结点之间。

bool ListInsert_L(LinkList &L, int i, int &e)//单链表的插入
{
    //在带头结点的单链表L中第i个位置插入值为e的新结点
    int j;
    LinkList p, s;
    p=L;
    j=0;
    while (p&&j<i-1) //查找第i-1个结点,p指向该结点
{
        p=p->next;
        j++;
    }
    if (!p || j>i-1) //i>n+1或者i<1
        return false;
    s=new LNode; //生成新结点
    s->data=e; //将新结点的数据域置为e
    s->next=p->next; //将新结点的指针域指向结点ai
    p->next=s; //将结点p的指针域指向结点s
    return true;
}

6. 单链表删除

删除一个结点,实际上是把这个结点跳过去。如图:

要想跳过第i个结点,就必须先找到第i-1个结点,否则是无法跳过去的。

p->next=q->next;含义是将q结点的下一个结点地址赋值给p结点的指针域。在这些有关指针的赋值语句中,很多同学不理解,容易混淆,在此说明一下,等号的右侧是结点的地址,等号的左侧是结点的指针域:

q结点的下一个结点地址存储在q->next里面,等号右侧的q->next就相当于把q结点的下一个结点地址读出来,赋值给p结点的next指针域,这样,就把q结点跳过去了。然后用delete q释放被删除结点的空间。

bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
    //在带头结点的单链表L中,删除第i个位置
    LinkList p, q;
    int j;
    p=L;
    j=0;
    while((p->next)&&(j<i-1)) //查找第i-1个结点,p指向该结点
    {
        p=p->next;
        j++;
    }
    if (!(p->next)||(j>i-1))//当i>n或i<1时,删除位置不合理
        return false;
    q=p->next; //临时保存被删结点的地址以备释放空间
    p->next=q->next; //改变删除结点前驱结点的指针域
    delete q; //释放被删除结点的空间
    return true;
}

单链表基本操作完整代码:

完整代码:
#include<iostream>
#include<string>
#include<iomanip>
#include<stdlib.h>
using namespace std;
typedef struct LNode {
    int data; //结点的数据域
    struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
bool InitList_L(LinkList &L)//构造一个空的单链表L
{
L=new LNode; //生成新结点作为头结点,用头指针L指向头结点
    if(!L)
return false; //生成结点失败
    L->next=NULL; //头结点的指针域置空
    return true;
}
void CreateList_H(LinkList &L)//前插法创建单链表
{
    //输入n个元素的值,建立到头结点的单链表L
    int n;
    LinkList s; //定义一个指针变量
    L=new LNode;
    L->next=NULL; //先建立一个带头结点的空链表
    cout <<"请输入元素个数n:" <<endl;
    cin>>n;
    cout <<"请依次输入n个元素:" <<endl;
    cout <<"前插法创建单链表..." <<endl;
    while(n--)
{
        s=new LNode; //生成新结点s
        cin>>s->data; //输入元素值赋给新结点的数据域
        s->next=L->next;
        L->next=s; //将新结点s插入到头结点之后
    }
}
void CreateList_R(LinkList &L)//尾插法创建单链表
{
    //输入n个元素的值,建立带表头结点的单链表L
    int n;
    LinkList s, r;
    L=new LNode;
    L->next=NULL; //先建立一个带头结点的空链表
    r=L; //尾指针r指向头结点
    cout <<"请输入元素个数n:" <<endl;
    cin>>n;
    cout <<"请依次输入n个元素:" <<endl;
    cout <<"尾插法创建单链表..." <<endl;
    while(n--)
{
        s=new LNode;//生成新结点
        cin>>s->data; //输入元素值赋给新结点的数据域
        s->next=NULL;
        r->next=s;//将新结点s插入尾结点r之后
        r=s;//r指向新的尾结点s
    }
}
bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
{
    //在带头结点的单链表L中查找第i个元素
    //用e记录L中第i个数据元素的值
    int j;
    LinkList p;
    p=L->next;//p指向第一个结点,
    j=1; //j为计数器
    while (j<i && p) //顺链域向后扫描,直到p指向第i个元素或p为空
{
        p=p->next; //p指向下一个结点
        j++; //计数器j相应加1
    }
    if (!p || j>i)
        return false; //i值不合法i>n或i<=0
    e=p->data; //取第i个结点的数据域
    return true;
}
bool LocateElem_L(LinkList L, int e) //按值查找
{
    //在带头结点的单链表L中查找值为e的元素
    LinkList p;
    p=L->next;
    while (p && p->data!=e)//顺链域向后扫描,直到p为空或p所指结点的数据域等于e
        p=p->next; //p指向下一个结点
    if(!p)
return false; //查找失败p为NULL
return true;
}
bool ListInsert_L(LinkList &L, int i, int &e)//单链表的插入
{
    //在带头结点的单链表L中第i个位置插入值为e的新结点
    int j;
    LinkList p, s;
    p=L;
    j=0;
    while (p&&j<i-1) //查找第i-1个结点,p指向该结点
{
        p=p->next;
        j++;
    }
    if (!p || j>i-1)//i>n+1或者i<1
        return false;
    s=new LNode; //生成新结点
    s->data=e; //将新结点的数据域置为e
    s->next=p->next; //将新结点的指针域指向结点ai
    p->next=s; //将结点p的指针域指向结点s
    return true;
}
bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
    //在带头结点的单链表L中,删除第i个位置
    LinkList p, q;
    int j;
    p=L;
    j=0;
    while((p->next)&&(j<i-1)) //查找第i-1个结点,p指向该结点
    {
        p=p->next;
        j++;
    }
    if (!(p->next)||(j>i-1))//当i>n或i<1时,删除位置不合理
        return false;
    q=p->next; //临时保存被删结点的地址以备释放空间
    p->next=q->next; //改变删除结点前驱结点的指针域
    delete q; //释放被删除结点的空间
    return true;
}
void Listprint_L(LinkList L) //单链表的输出
{
LinkList p;
p=L->next;
while (p)
{
cout <<p->data <<"\t";
        p=p->next;
}
cout<<endl;
}
int main()
{
    int i,x,e,choose;
    LinkList L;
    cout << "1. 初始化\n";
    cout << "2. 创建单链表(前插法)\n";
    cout << "3. 创建单链表(尾插法)\n";
    cout << "4. 取值\n";
    cout << "5. 查找\n";
    cout << "6. 插入\n";
    cout << "7. 删除\n";
    cout << "8. 输出\n";
    cout << "0. 退出\n";
    choose=-1;
    while (choose!=0)
{
        cout<<"请输入数字选择:";
        cin>>choose;
        switch (choose)
        {
        case 1: //初始化一个空的单链表
            if (InitList_L(L))
                cout << "初始化一个空的单链表!\n";
            break;
        case 2: //创建单链表(前插法)
            CreateList_H(L);
cout << "前插法创建单链表输出结果:\n";
Listprint_L(L);
            break;
case 3: //创建单链表(尾插法)
            CreateList_R(L);
cout << "尾插法创建单链表输出结果:\n";
Listprint_L(L);
            break;
        case 4: //单链表的按序号取值
            cout << "请输入一个位置i用来取值:";
            cin >> i;
            if (GetElem_L(L,i,e))
{
                cout << "查找成功\n";
                cout << "第" << i << "个元素是:"<<e<< endl;
            }
            else
                cout << "查找失败\n\n";
            break;
        case 5: //单链表的按值查找
            cout<<"请输入所要查找元素x:";
            cin>>x;
            if (LocateElem_L(L,x))
                cout << "查找成功\n";
            else
                cout << "查找失败! " <<endl;
            break;
        case 6: //单链表的插入
            cout << "请输入插入的位置和元素(用空格隔开):";
            cin >> i;
            cin >> x;
            if (ListInsert_L(L, i, x))
                cout << "插入成功.\n\n";
            else
                cout << "插入失败!\n\n";
            break;
        case 7: //单链表的删除
            cout<<"请输入所要删除的元素位置i:";
            cin>>i;
            if (ListDelete_L(L, i))
                cout<<"删除成功!\n";
            else
                cout<<"删除失败!\n";
            break;
        case 8: //单链表的输出
            cout << "当前单链表的数据元素分别为:\n";
            Listprint_L(L);
            cout << endl;
            break;
        }
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 第4-2讲 双向链表

    链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?

    rainchxy
  • 数据结构 第11讲 二叉树及其创建

    二叉树(Binary Tree)是n(n≥0)个结点所构成的集合,它或为空树(n = 0);或为非空树,对于非空树T:

    rainchxy
  • 数据结构 第6讲 链栈

    进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储。顺序栈和链栈图解:

    rainchxy
  • 编程小白 | 每日一练(42)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    C语言入门到精通
  • 讲透学烂二叉树(二):图中树的定义&各类型树的特征分析

    日常中我们见到的二叉树应用有,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,以及B-Tree,...

    周陆军
  • B树 B-树 B+树 B*树

    B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

    用户1154259
  • Python数据结构__树

        有且只有一个特殊元素根,剩余元素都可以划分为m个不相交的集合T1、T2、T3...Tm,

    py3study
  • 6.1 数据结构树的定义

    (2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2...,其中每一个集合本身又是一棵树,并且称为根的子树。

    C语言入门到精通
  • 前端学习数据结构与算法系列(四):哈希、堆和二叉查找树

    当元素进行 mod 运算后,可能会与其他元素的 mod 值一样,此时数组中已经有其他元素占了这个下标位置,这种存储位置重复了的情况便叫做 冲突,我们来看个例子:

    一只图雀
  • 什么是红黑树?

    当在10亿数据中只需要进行10几次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀! —— 学红黑树有感。

    小东啊

扫码关注云+社区

领取腾讯云代金券