基础数据结构(1):链表

2023-12-20 07:24:26

? ? 在学习算法时,发现用什么数据结构来存储数据是很重要的,所以学习数据结构也是必须的,先从基础数据结构:数组,字符串,链表,栈,队列,树,矩阵,邻接表,哈希表等,数组和字符串我们已经了解的很多了,所以我们从链表开始学习,了解什么是链表,链表存储数据的方式,以及如何对链表进行各种操作,如何用数组来模拟链表,如何用栈来做链表相关的题目。

1.何为链表

??由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。同时因为单链表是非随机的存储结构,即不能直接找到表中某个特定的结点。查找某个特定的结点时,需要从表头开始遍历,依次查找。

? ? ? 我们再看链表是什么:

? ? ? 链表其实是由一个个结点组成,每个结点之间通过链接更新串联起来,每个结点都有一个后继结点,最后一个结点的后继结点为空结点

? ? ?图中就是一个链表其中橙色结点被称为黄色结点的前驱结点,黄色结点被称为橙色结点的后继结点,链表其实有单向链表、双向链表、循环链表等,这里先只介绍单向链表。那既然结点存储数据,怎么找到后驱结点呢?下面一起来看看吧

2.链表结点的定义

typedef struct ListNode
{
   int data;
   struct ListNode* next;
}ListNode;

? ? ?这就是一个结点的定义,我们把一个结点看成一个结构体,其中data是数据域,可以是任意类型,而struct ListNode* next定义了一个指向ListNode结构体的指针,这个指针的地址是后继结点,将指向下一个结点,这就是指针域,如下图所示??

? ? ? 下面看看具体怎么创建一个链表的结点

3.链表结点创建

ListNode* ListCreateNode(int data)
{
   ListNode* node=(List*)malloc(sizeof(ListNode));
   node->data=data;
   node->next=NULL;
   return node;
}

? ? ?我们先用malloc函数分配一块内存空间,用来存放ListNode即链表对象,将数据域置为函数传参data,将指针域置为NULL,代表这是一个孤立的链表结点,最后返回这个结点的指针。

4.虚拟头结点

? ? ?为了方便对链表进行操作,避免第一个结点无法操作的问题,我们往往会建立一个虚拟头结点,这个头结点上不存储数据,只是指向链表的第一个结点

ListNode* head=ListCreateNode(-1);

5.链表的创建及初始化

? ? ?单链表有两种:一种是带虚拟头结点的,一种不带虚拟头结点。总的来说,带头结点的单链表相对于不带头结点的单链表来说,更加方便对链表进行操作,所以很多时候我们都是用带头结点的单链表,这里我们也只用学习带头结点的即可

5.1初始化带头结点的单链表

void InitList(ListNode* head) {
	head=(ListNode*)malloc(sizeof(ListNode));
    head->next=NULL;
}

5.2创建带头结点的单链表

5.2.1头插法

? ? ? ? ?头插法顾名思义就是从链表开头插入,先插入的后输出,后插入的先输入,例如,我想创建一个链表(4,7,9),输出就是(9,7,4)。

ListNode* HeadInsert(ListNode* head) {
    initlist(head); //初始化
    int n;
    scanf_s("%d",&n);
    for(int i=0;i<n;i++) 
    {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        int data;
        scanf_s("%d", &data);
        node->data = data;
        node->next = head->next;
        head->next = node;
    }
    return head;
}

5.2尾插法

? ? ?尾插法顾名思义就是从链表末尾开始插入,先插入的先输出,后插入的后输出

ListNode* TailInsert(ListNode* head) {
    initlist(head); //初始化
    ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
    cur = head;
    int n,data;
    scanf_s("%d",&n);
    for(int i=0;i<n;i++) 
    {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        scanf_s("%d", &data)
        node->data = data;
        node->next =NULL;
        cur->next = node;
        cur = cur->next; 
    }
    return head;
}

6.链表基础操作?

? ? ?创建完链表之后,我们就要对链表进行操作了,常见的操作就是增删改查

6.1遍历操作

void PrintList(ListNode* head) {
    ListNode* cur = head->next;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

6.2求单链表的长度

int Length(ListNode* head) {
    ListNode* cur = head->next;
    int len = 0;
    while (cur) {
        len++;
        cur = cur->next;
    }
    return len;
}

6.3查找操作

6.3.1按值查找
ListNode* locateElem(ListNode* head, int data)
{
    ListNode* cur = head->next;
    while (cur && cur->data != data)
    {
        cur = cur->next;
    }
    return cur;
}
6.3.2按位查找
ListNode* getElem(ListNode* head, int i)
{
    int j = 1;
    ListNode* cur = head->next;
    if (i == 0)return head;
    if (i < 1)return NULL;
    while (cur && j < i)
    {
        cur = cur->next;
        j++;
    }
    return cur;
}

6.4插入操作

void Insert(ListNode* head, int i, int data)
{
    ListNode* pre = getElem(head, i - 1);
    ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
    cur->data = data;
    cur->next = pre->next;
    pre->next = cur;
}

6.5删除操作

? ? ?将链表的第i个结点删除

void Delete(ListNode* head, int i) {
    if (i<1 || i>Length(head))return;
    ListNode* pre = getElem(head, i - 1);
    ListNode* cur = pre->next;
    pre->next = cur->next;
    free(cur);
}

6.6判空操作

bool Empty(ListNode* head) {
    if (head->next == NULL) {
        printf("Head is null\n");
        return true;
    }
    else {
        printf("Head is not null\n");
        return false;
    }
}

文章来源:https://blog.csdn.net/pancodearea/article/details/135093273
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。