当前位置:   article > 正文

链表的基本操作(C/C++)_c++链表的基本操作

c++链表的基本操作


前言


提示:以下是本篇文章正文内容

一、单链表定义

当需要建立一个学生信息表,学生的人数无法确定而且人数经常变化,此时若用顺序表来实现将会很麻烦

在这里插入图片描述

单链表:线性表的链接存储结构, 用一组任意(不联系, 零散分布) 的存储单元存放线性表的元素.

存储特点:
1.逻辑次序和物理次序不一定相同

2.元素之间的逻辑关系用指针表示

如(a1, a2 ,a3, a4)存储在内存中
在这里插入图片描述

结点结构

单链表是由若干结点构成的, 结点包含数据域和指针域在这里插入图片描述

data: 存储数据元素
next: 存储指向后继结点的地址

// 定义节点
typedef struct node
{
    int data;              //数据域
    struct node *next;     //指针域
}Node,*Link;               //定义别名 Node, Link
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

申请一个结点

p=(Link)malloc(sizeof(Node));
  • 1

在这里插入图片描述
结点建立之后,
引用数据元素: (*p).data <==> p->data
引用指针元素: p->next

链表(a1, a2, a3, a4)
在这里插入图片描述

头指针:指向第一个结点的地址

尾标志:终端节点的指针域为空

首元结点:链表第一个数据结点

头节点: 在单链表的第一个元素结点之前附设一个类型相同的结点, 以便空表和非空表的处理统一
在这里插入图片描述
注:头节点的数据域一般为空, 指针域指向第一个节点

二、单链表的基本操作

1.遍历操作

接口操作: void displayNode(Link head);

void displayNode(Link head)
{
    Link p = head->next;          //p指向首元结点
    while(p != NULL)
    {
        printf("%d\t",p->data);  //输出数据 
        p = p->next;             //移向下一个结点
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

2.链表长度

操作接口:int length(Link head);
在这里插入图片描述
伪代码:
1.工作指针p初始化, 累加器count初始化

2.重复执行下述操作, 直到p为空;

  (1)工作指针p后移
  (2)count++
  • 1
  • 2

3.返回累加器count的值

int length(Link head)
{
    int count = 0;
    Link p = head->next;
    while(p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

3.链表查找

操作接口:bool queryNode(Link head, int x);

思路: 依次遍历链表的数据域 与要查找的数据进行比较

bool queryNode(Link head, int x)
{
    Link p = head->next;
    while(p != NULL)
    {
        if(p->data == x) //查找成功
        {
            printf("d",p->data);
            return true;
        }
        p = p->next;   //没有找到,移动结点
    }
    return false;     //查找失败返回false
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

4.链表插入

操作接口:bool insertNode(Link head, int index, int item);

思路:
在这里插入图片描述
插入到第i个结点, 先找到第i-1 个节点, 然后, 让插入结点的指针域指向i-1个结点的指向的指针域, 再修改第i-1结点的指针域, 使其指向插入结点. 注意, 修改指针指向的顺序不要颠倒, 不然会导致找不到第i个结点. 对于边界情况也同样适合.

伪代码
1.工作指针p初始化
2.查找第i-1个结点, 并使该指针p指向该结点
3.若查找不成功,则返回false
否则:

3.1生成一个元素值为x的新结点node
3.2将新结点插入到p所指向的结点
3.3返回true

bool  insertNode(Link head, int index, int item)
{
	int count=0;
    Link p = head;
    Link node;
    while(p != NULL && count < index-1)   //找到第index前一个结点
    {
        p = p->next;
        count++;
    }
    if(p == NULL)
    {
        return false;                    //没有找到第i-1个结点
    }
    else
    {
        node = (Link)malloc(sizeof(Node));//申请一个结点
        node->data = item;                //结点的数据域
        node->next = p->next;             //修改指针指向关系
        p->next = node;
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

5.头插入法(创建链表)

操作接口:Link newList(const int a[],int n);
头插法:将待插入的结点插在头节点的后面,插入顺序最终相反
在这里插入图片描述

这与链表插入一样的, 若以数组传入参数, 则生成的链表的数据则与数组的数据刚好相反

template <class DataType>
Link newList(DataType a[],int n)
{
    int i=0;
    //创建头结点
    Link head = (Link)malloc(sizeof(Node));
    head->next = NULL;
    //创建后续结点
    for(i=0;i<n;i++)
    {
        Link node = (Link)malloc(sizeof(Node));
        node->data = a[i];
        node->next = head->next;
        head->next = node;
    }
    return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

6.尾插法(创建链表)

操作接口:Link new_List(const int a[],int n);
尾插法:将待插入结点插在终端结点的后面
在这里插入图片描述

Link new_List(const int a[],int n)
{
    int i=0;
    Link head = (Link)malloc(sizeof(Node));
    Link rear = (Link)malloc(sizeof(Node));
    head->next = NULL;
    rear = head;             //尾指针初始化
    for(i=0;i<n;i++)
    {
        Link node = (Link)malloc(sizeof(Node));
        node->data = a[i];
        rear->next = node;
        rear = node;
    }
    rear->next = NULL;  //保证最后一个结点指针域为空
    return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

7.删除结点

操作接口:bool deleteNode(Link head,DateType x);

思路:
引入两个指针p,q, p指向要删除的结点, q指向要删除结点的前一个结点
在这里插入图片描述
找到要删除的结点, 用free()函数释放该节点, 并修改删除结点两边指针关系情况,
要保证p,q指针一前一后: 在插在过程中, 若发现结点p指向的数据域不等于x, 则p,q指针同时向前移动即可

若在查找过程一直没有找到要删除的结点(链表遍历完毕),则退出循环,返回错误

bool deleteNode(Link head,DateType x)
{
    Link p,q;
    if(head==NULL || head->next==NULL)  //链表没有数据,返回错误
    {
        return false;
    }
    p=head->next;      //初始化p,q 并保证p,q 一前一后
    q=head;
    while(p!=NULL)
    {
        if(p->data==x) //找到结点x ,删除并将两边结点链接起来
        {
            q->next=p->next;
            free(p);
            return true;
        }
        else           //没有找到,p,q依次往前移动
        {
            q=p;
            p=p->next;
        }
    }
    //若循环结束了,说明没有找到该结点
    return false;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

8.链表释放

操作接口:void clearLink(Link head)
将单链表中所有结点存储空间释放, 要保证链表末处理的部分不断开
在这里插入图片描述

void clearLink(Link head)
{
    Link q;
    while(head->next!=NULL)
    {
        q=head;
        head=head->next;
        free(q);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

三、循环链表

将单链表的首尾相接,将终端结点的指针域由空指针改为指向头节点,构成单循环链表,简称循环链表。
在这里插入图片描述

循环链表没有明显的尾端,如何避免死循环?

单链表---->循环链表

p != NULL----> p !=head
p->next != NULL----> p->next != head
  • 1
  • 2

四、双向链表

在单链表的每个结点中再设置一个指向其前驱节点的指针域
在这里插入图片描述
data: 数据域,存储数据元素
prior: 指针域,存储该结点的前驱结点地址
next:指针域,存储该结点的后继结点地址

在这里插入图片描述


总结

提示:这里对文章进行总结:

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/756287
推荐阅读
相关标签
  

闽ICP备14008679号