数据结构2-线性表

时间:2024-10-26 21:33:08

目录

一、线性表介绍

     1、线性结构

    2、线性表

二、线性表的顺序的表示和存储

        注意

        优点

        缺点

三、线性表的链式表示和存储

    单向链表

        1、不带头节点的单向链表

        2、带头节点的单向链表

        3、单向链表的使用

            1、单链表逆序,要在原基础上进行逆序

            2、找到链表的倒数第n个节点

            3、判断链表中是否存在环

            4、找出环形链表的入口节点

            5、合并两个有序链表,合并后保持有序性

            6、判断两个链表是否构成Y型链表,如果是,找出第一个公共节点

四、静态链表

五、循环链表

六、双向链表(双向循环链表)

七、Linux内核链表

    函数

八、通用链表


一、线性表介绍

     1、线性结构

        在数据元素存在非空有限集中:

            存在唯一的一个被称为“第一个”的数据元素

            存在唯一的一个被称为“最后一个”的数据元素

            除了第一个外,集合中每个数据元素都只有一个前趋元素

            除了最后一个外,集合中每个数据元素都只有一个后继元素

    2、线性表

        线性表是一个有n个数据元素的有限序列,同一个线性表中的元素必定有相同特性,元素之间存在序偶关系

        线性表中的元素个数n(n>=0)定义为该表的长度,当n==0时称为空表,非空表中每个数据元素都有一个确定的位置(下标)

        线性表是一个相当灵活的数据结构,它的长度可以根据需要增长或缩短

二、线性表的顺序的表示和存储

        线性表的存储使用一组连续内存来依次存储线性表中的数据元素。

        注意

            1、要时刻保持元素之间的连续性

            2、千万不要越界

        优点

            1、支持随机访问 

            2、查找、修改、排序效率比较高

            3、大块的连续内存不容易产生内存碎片

        缺点

            1、对元素插入、删除时效率很低

            2、大块内存对内存要求较高

三、线性表的链式表示和存储

        链式存储结构不要求内存位置物理上是连续的,因此元素可以存储在内存的任何位置(可以是连续的,也可以不连续)

        元素a[i]和a[i+1]之间的逻辑关系不是依靠相互位置,而是在元素中增加一个一个指向其后继元素的数据项(元素指针),从而表示相互之间的逻辑关系,元素本身的数据+后继元素的地址 组成了存储映像,俗称 **节点**(node)

typedef struct Node
{
    TYPE data;          //  数据域  
    struct Node* next;  //  指针域
}Node;

        若干个节点通过指针域依次连接起来,形成的线性表结构称为链式表,简称链表,如果指针域中只有一个指向下一个节点的指针,这种链表称为单向链表。

    单向链表

        单向链表中必须要有一个指向第一个节点的指针,该指针称为头指针,被它指向的节点称为“头节点”,头节点可以存储、也可以不存储有效数据,如果不存储有效数据的话,那么头节点只是单纯地作为一个占位节点存在

        最后一个节点称为“尾节点”,尾节点的next指向空(NULL),作为结束标志

        1、不带头节点的单向链表

            定义:第一个节点中的数据域存储有效数据。

            注意:当需要对单链表的头指针发生修改时,例如头添加、头删除、插入等操作,参数需要传递头指针的地址(二级指针),当进行删除时,需要获取到待删除节点的前趋节点,但是如果删除的位置刚好是第一个节点,它没有前趋节点,所以需要额外判断处理

        2、带头节点的单向链表

            定义:第一个节点中的数据域不存储有效数据,该头节点只是用于指向第一个有效数据的节点而存在,所以,由于头节点不会因为添加、插入、删除该改变,所以不需要传递二级指针

typedef struct List
{
    ListNode* head;     //  永远指向头节点 必须要有
    ListNode* tail;     //  尾指针,可以有 也可以没有
    size_t size;        //  数量 可以有 也可以没有
}List;

            注意:尾指针tail,能直接找到最后一个节点,但是在尾删除操作时,发挥不了作用,因为要找尾节点的前趋。

        3、单向链表的使用
            1、单链表逆序,要在原基础上进行逆序
#include <stdio.h>

struct ListNode* ReverseList(struct ListNode* head ) {
    // 判断链表是否为空
    if(NULL == head || NULL == head->next)
        return head;

    // 初始化一个指向下一节点的指针,并让头节点指向空
    struct ListNode* prev = head;
    struct ListNode* newl = head->next;
    head->next = NULL;

    // 循环遍历,让下一个节点的next指针指向它的上一节点
    while(NULL != newl->next)
    {
        struct ListNode* next = newl->next;
        newl->next = prev;
        prev = newl;
        newl = next;
    }
    // 最后,让最后一个节点指向上一节点,并将其设置为头节点输出
    newl->next = prev;
    head = newl;

    return head;
}
            2、找到链表的倒数第n个节点
#include <time.h>

struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
    // 判断链表是否为空
    if(NULL == pHead)
        return NULL;

    // 初始化两个新指针,一个用来计算链表的长度,一个来找地n个节点
    struct ListNode* fast = pHead;
    struct ListNode* low = pHead;
    int len = 0;

    // 遍历链表,得出链表的总长度
    while(k--)
    {
        if(NULL == fast)
            return NULL;
        fast = fast->next;
    }

    // 遍历链表,找到第n个节点
    while(NULL != fast)
    {
        fast = fast->next;
        low = low->next;
    }
    
    return low;
}
            3、判断链表中是否存在环
bool hasCycle(struct ListNode* head ) {
    // 判断链表是否为空
    if(NULL == head || NULL == head->next)
        return false;

    // 初始化快慢指针
    struct ListNode* fast = head;
    struct ListNode* low = head;

    // 让快指针一次走两步,让慢指针一次走一步
    // 如果快慢相遇就说明存在环
    // 如果不存在环,链表就一定会有指向空的节点
    // 当快指针遍历完链表,循环便会结束
    while(NULL != fast->next)
    {
        fast = fast->next;
        if(NULL == fast->next)
            break;
            
        fast = fast->next;
        low = low->next;
        if(fast == low)
            return true;
    }
    return false;
}
            4、找出环形链表的入口节点
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // 判断链表是否为空
    if(NULL == pHead || NULL == pHead->next)
        return NULL;

    // 初始化快慢指针
    struct ListNode* fast = pHead;
    struct ListNode* low = pHead;

    // 快指针一次走两步,慢指针一次走一步
    // 链表头到环入口的距离=相遇点到环入口的距离+(k-1)圈环长度
    // 两个指针分别从链表头和相遇点出发,最后一定相遇于环入口
    while(NULL != fast->next)
    {
        fast = fast->next;
        if(NULL == fast->next)
            break;
            
        fast = fast->next;
        low = low->next;
        if(fast == low)
        {
            fast = pHead;
            while(fast != low)
            {
                fast = fast->next;
                low = low->next;
            }
            return fast;
        }
    }
    return NULL;
}
            5、合并两个有序链表,合并后保持有序性
#include <math.h>

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // 判断两个链表是否为空
    if (NULL == pHead1 && NULL == pHead2)
        return NULL;
    else if(NULL == pHead2)
        return pHead1;
    else if(NULL == pHead1)
        return pHead2;

    // 初始化新的链表存储
    struct ListNode* pHead3;
    
    // 比较两个链表的头节点大小
    if (pHead1->val < pHead2->val) 
    {
        pHead3 = pHead1;
        pHead1 = pHead1->next;
    } 
    else 
    {
        pHead3 = pHead2;
        pHead2 = pHead2->next;
    }

    struct ListNode* pHead = pHead3;

    // 循环遍历,让比较小的值接到新链表的最后,直到一条链表被完全遍历
    while (NULL != pHead1 && NULL != pHead2) 
    {
        if (pHead1->val < pHead2->val) 
        {
            pHead3->next = pHead1;
            pHead1 = pHead1->next;
        } 
        else 
        {
            pHead3->next = pHead2;
            pHead2 = pHead2->next;
        }
        pHead3 = pHead3->next;
    }

    // 将另一条链表后面的所有节点接入新链表
    if(NULL == pHead1)
        pHead3->next = pHead2;
    else
        pHead3->next = pHead1;

    return pHead;
}
            6、判断两个链表是否构成Y型链表,如果是,找出第一个公共节点
#include <stdbool.h>

struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // 判断链表是否为空
    if(NULL == pHead1 || NULL == pHead2)
        return NULL;

    // 初始化指针遍历链表
    struct ListNode* head1 = pHead1;
    struct ListNode* head2 = pHead2;
    bool f1=0,f2=0;

    // 让两条链表的指针同步遍历链表
    // 当指针遍历完一条链表之后,让它从另一条链表的头节点开始重新遍历,另一个指针也同样
    // 如果存在Y型,两指针就会相遇在入口位置
    // 如果不存在就会返回空指针
    while(head1 != head2)
    {
        head1 = (head1 == NULL)?pHead2:head1->next;
        head2 = (head2 == NULL)?pHead1:head2->next;
    }
    return head1;
}

四、静态链表

        静态链表的节点存储在一段连续内存中,通过节点中称为游标的一个正整数来访问后继节点

typedef StaticNode
{
    TYPE data;      //  数据域
    int index;  //  游标
}StaticNode;

int main()
{
    StaticNode arr[100] = {};
    arr[0].data = 1;
    arr[0].index = 5;
    arr[5].index = 3;
    arr[3].index = 8;
    arr[8].index = -1;
}

        在静态链表中进行插入、删除时,只需要修改游标的值即可不需要拷贝内存,也能达到链表的效果,但是也牺牲了随机访问节点的功能,而且链表的优点也有缺失。

        是给没有指针的编程语言提供一种操作单链表的方式。

五、循环链表

        循环链表的最后一个节点的next不再指向NULL,而是指向头节点。如果是单链表就称为单循环链表。

        循环链表的最大优点就是能够通过任意节点可以遍历整个链表。

六、双向链表(双向循环链表)

        所谓的双向链表就是链表节点中有两个指针域,一个指向前一个节点,叫做前趋指针(prev),另一个指向后一个节点,称为后继指针(next)。

        因此可以从后往前遍历链表,对于要访问链表后半部的节点的操作效率更高。

//  双向链表的节点结构
typedef struct ListNode
{
    struct ListNode* prev;      //  前趋
    TYPE data;
    struct ListNode* next;      //   后继
}ListNode;

        在双向链表的基础上,让最后一个节点的next指向头节点,让头节点的prev指向最后一个节点,构成了双向循环链表

七、Linux内核链表

        在普通的链表中,目前面临无法做到任何类型的数据都可以存储的问题。

        Linux内核链表是一种通用的双向循环链表,面对通用的问题,Linux内核链表的节点干脆不存储任何数据域,只有指针域,节点只负责串联起每个节点,不负责存储数据。

        如果要使用Linux内核链表时,把节点放入到数据中。

    函数

        目的:根据结构体中某个成员的地址,能够计算出所在结构体的首地址,从而用户在设计Linux内核链表的节点时,不需要一定放在在数据的首位成员,增加可用性

//  计算出结构体type的成员mem所在的地址距离第一个成员位置的字节数
#define offsetof(type,mem) \
    ((unsigned long)(&(((type*)0)->mem)))

//  根据结构成员mem的地址(ptr) 计算出它所在结构(type)变量的首地址
//  ptr要计算的某个节点的地址  type是ptr所在结构体名 mem是它的结构成员名
#define node_to_obj(ptr,type,mem) \
    ((type*)((char*)ptr - offsetof(type,mem)))

八、通用链表

        Linux内核链表虽然设计很巧妙,但是不利于初学者使用,另一种通用的设计思路是借助void*的兼容性,来设计一种链表,称为通用链表,这种链表还需要借助回调函数。

//  定义了一个函数指针变量                返回值 (*函数指针变量名)(参数列表);
    void (*funcp)(int num1,int num2);
//  该函数指针的类型是                返回值 (*)(参数列表);  
    void (*)(int,int);
//  函数指针类型重定义                typedef 返回值 (*重定义后的类型名)(参数列表);
    typedef void (*fp)(int,int);
//  fp 就是 void (*)(int,int)这个函数指针类型 可以用来定义该类型的函数指针变量
    fp p;   //  p就是函数指针变量