首页 > 其他分享 >数据结构——单链表查询、逆序、排序

数据结构——单链表查询、逆序、排序

时间:2024-09-04 21:53:28浏览次数:13  
标签:Node 单链 phead 数据结构 pdoulink NULL data pnext 逆序

1、思维导图

2、查、改、删算法

//快慢排序法找中间值
int mid_link(Link_t *plink)
{
    Link_Node_t *pfast = plink->phead;
    Link_Node_t *pslow = pfast;
    int m = 0;
    while(pfast != NULL)
    {
        pfast = pfast->pnext;
        ++m;
        if(m % 2 == 0)
        {
            pslow = pslow->pnext;
        }
    }
    printf("%d\n",pslow->data);
    printf("%p\n",pslow);
        
}


//快慢排序法查询倒数第k个
Link_Node_t *recipe_link_count(Link_t *plink)
{
    Link_Node_t *pfast = plink->phead;
    Link_Node_t *pslow = pfast;
    int m = 0;
    int n;
    scanf("%d",&n);
    while(pfast != NULL && m < n)
    {
        pfast = pfast->pnext;
        m++;
    }
    while(pfast != NULL)
    {
        pfast = pfast->pnext;
        pslow = pslow->pnext;
    }
    //printf("%d\n",pslow->data);
    //printf("%p\n",pslow);
    return pslow;
}


//删除指定节点
int pop_point_node(Link_t *plink)
{
    int n;
    int m = 0;
    printf("选择删除节点:");
    scanf("%d",&n);
    Link_Node_t *p = plink->phead;
    Link_Node_t *pdel = NULL;
    Link_Node_t *ptmp = NULL;
    if(p == NULL)
    {
        return 0;
    }
    else if(p->data == n)
    {
        pdel = p;
        plink->phead = p->pnext;
    }
    else if(p != NULL)
    {
        while(p->data != n)
        {
            ptmp = p;
            p = p->pnext;
        }
        pdel = p;
        ptmp->pnext = pdel->pnext;
    }
            free(pdel);
    return 0;
}

3、单链表逆序

//链表逆序
int reverse_link(Link_t *plink)
{
    if(is_empty_link(plink))
        return 0;
    Link_Node_t *ptmp = plink->phead;
    Link_Node_t *pinsert = NULL;
    plink->phead = NULL;
    while(ptmp != NULL)
    {
        pinsert = ptmp;
        ptmp = ptmp->pnext;
        pinsert->pnext = plink->phead;
        plink->phead = pinsert;
    }
}

4、插入排序(从未排序部分取出一个元素,插入到已排序部分的正确位置)

void insert_sort_link(Link_t *plink)
{
    if(is_empty_link(plink) || 1 == plink->clen)
    {
        return;
    }
    Link_Node_t *ptmp = plink->phead->pnext;
    Link_Node_t *pinsert = NULL;
    Link_Node_t *p = NULL;
    plink->phead->pnext = NULL;
    while(ptmp != NULL)
    {
    pinsert = ptmp;
    ptmp = ptmp->pnext;
    if(pinsert->data <= plink->phead->data)
    {
        pinsert->pnext = plink->phead; //头插
        plink->phead = pinsert;
    }
    else
    {
        p = plink->phead;
       while(p->pnext != NULL && p->pnext->data < pinsert->data)
       {
           p = p->pnext;
       }
        pinsert->pnext = p->pnext;  //尾插
        p->pnext = pinsert;   
    }
    }
}

双向链表——插删查改:

#include<stdio.h>
#include"dlink.h"
#include<stdlib.h>

DLink_t *create_doulink()
{
    DLink_t *pdoulink = malloc(sizeof(DLink_t));
    if(NULL == pdoulink)
    {
        perror("fail creat");
        return NULL;
    }
    pdoulink->phead = NULL;
    pdoulink->clen = 0;
    pthread_mutex_init(&pdoulink->mutex,NULL);
    return pdoulink;
}

//判空
int is_empty_doulink(DLink_t *pdoulink)
{
    return NULL == pdoulink->phead;
}

//头插
int push_doulink_head(DLink_t *pdoulink,DataType data)
{
    DLink_Node_t *pnode = malloc(sizeof(DLink_Node_t));
    if(NULL == pnode)
    {
        perror("fail malloc");
        return -1;
    }
    pnode->ppre = NULL;
    pnode->pnext = NULL;
    pnode->data = data;
    
    if(is_empty_doulink(pdoulink))
    {
        pdoulink->phead = pnode;
    }
    else
    {
        pnode->pnext = pdoulink->phead;
        pdoulink->phead->ppre = pnode;
        pdoulink->phead = pnode;
    }
    pdoulink->clen++;
}

//遍历
void print_pdoulink(DLink_t *pdoulink,int flag)
{
    if(is_empty_doulink(pdoulink))
        return;
    DLink_Node_t *p = pdoulink->phead;
    if(flag)
    {
        while(p != NULL)
        {
            printf(" %d %s %d\n",p->data.id,p->data.name,p->data.score);
            p = p->pnext;
        }
    }
    else
    {
        while(p->pnext != NULL)
        {
            p = p->pnext;
        }
        while(p != NULL)
        {
            printf(" %d %s %d\n",p->data.id,p->data.name,p->data.score);
            p = p->ppre;
        }
    }
    
}

//尾插
int push_doulink_tail(DLink_t *pdoulink ,DataType data)
{
    DLink_Node_t *pnode = malloc(sizeof(DLink_Node_t));
    if(pnode == NULL)
    {
        perror("fail malloc");
        return -1;
    }
    pnode->data = data;
    pnode->ppre = NULL;
    pnode->pnext = NULL;
    if((is_empty_doulink(pdoulink)))
    {
        push_doulink_head(pdoulink,data);
        free(pnode);
    }
    else
    {
        DLink_Node_t *p = pdoulink->phead;
        while(p->pnext != NULL)
        {
            p = p->pnext;
        }
        p->pnext = pnode;
        pnode->ppre = p;
    }

}

//头删
int pop_head(DLink_t *pdoulink)
{
    if(is_empty_doulink(pdoulink))
    {
        return 0;
    }
    DLink_Node_t *p = pdoulink->phead;
    pdoulink->phead = p->pnext;
    if(p->pnext != NULL)
    {
        p->pnext->ppre = NULL;
    }
    free(p);
}

//尾删
int pop_tail(DLink_t *pdoulink)
{
    DLink_Node_t *p = pdoulink->phead;
    if(is_empty_doulink(pdoulink))
    {
        return 0;
    }
    else if(p->pnext == NULL)
    {
        pop_head(pdoulink);
    }
    else
    {
        while(p->pnext->pnext != NULL)
        {
            p = p->pnext;
        }
        free(p->pnext);
        p->pnext = NULL;
    }
}

//查找 name
DataType *find_dliink_data(DLink_t *pdoulink,char *data)
{
    if(is_empty_doulink(pdoulink))
        return NULL;
    DLink_Node_t *p = pdoulink->phead;
    while(p != NULL)
    {
        if(strcmp(p->data.name,data) == 0)
        {
            return &(p->data);
        }
        p = p->pnext;
    }
    return NULL;
}

//修改(根据name查找)
void update_dlink_data(DLink_t *pdoulink,char *old_data,char *new_data)
{
    if(is_empty_doulink(pdoulink))
        return;
    DLink_Node_t *p = pdoulink->phead;
    while(p != NULL)
    {
        if(strcmp(p->data.name,old_data) == 0)
        {
            strcpy(p->data.name,new_data);
            break;
        }
        p = p->pnext;
    }
    
}

//销毁

void destory_dlink(DLink_t *pdoulink)
{
        while(!(is_empty_doulink(pdoulink)))
        {
            pop_head(pdoulink);
        }
        free(pdoulink);
}

标签:Node,单链,phead,数据结构,pdoulink,NULL,data,pnext,逆序
From: https://blog.csdn.net/xgshxjhs_/article/details/141891338

相关文章

  • 【数据结构】时间复杂度空间复杂度
    1、时间复杂度1.1大O渐进表示法大O符号(BigOnotation):是用于描述函数渐进行为的数学符号。推导大O阶方法:用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中,只保留最高阶项。如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶......
  • 54.《数据结构绪论处解》
    结构和算法为程序的核心所在先谈数据和信息的关系之前计基中背诵理解的数据是信息的具体表现形式数据是信息的载体信息的符号化是数据是数据加工后的结果为了弄清五个XX概念我最烦的就是xiajiba的概念数据数据元素数据对象数据类型数据结构废话不多说上图语......
  • 数据结构--链表
    单向链表链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。相较于数组,链表有以下优点:逻辑结构(1)链表采用动态内存分配的方式,在内存中不连续(2)支持动态增加或者删除元素(3)需要时可以使用malloc或者new来申请内存,不用......
  • 算法与数据结构——AVL树(平衡二叉搜索树)
    AVL树在“二叉搜索树”章节提到,在多次插入和删除操作后,二叉搜索树可能退化为链表。在这种情况下,所有操作的时间复杂度将从O(logn)劣化为O(n)。如下图,经过两次删除节点操作,这棵二叉搜索树便会退化为链表再例如,下图所示的完美二叉树中插入两个节点后,树将严重向左倾斜,查找操作的......
  • 数据结构和算法
    数据结构和算法数据结构数组(Array):一种线性数据结构,可以存储相同类型的元素,支持基于索引的快速访问。链表(LinkedList):由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针。栈(Stack):遵循后进先出(LIFO)原则的线性数据结构,只能在一端(栈顶)进行添加或删除操作。队列(Queue):......
  • PART1-Oracle关系数据结构-分区、视图以及其他的对象
    4.分区、视图与其他对象4.1.分区概述分区允许您将非常大的表和索引分解成更小、更易于管理的部分,称为分区。每个分区是一个独立的对象,有自己的名称,并且可以选择拥有自己的存储特性。为了说明分区的概念,假设一个人力资源经理有一个大盒子,里面装着员工文件夹。每个文件夹都列出......
  • 【数据结构和算法实践-树-LeetCode100-判断是否是相同的树】
    数据结构和算法实践-树-LeetCode100-判断是否是相同的树题目MyThought代码示例JAVA-8题目给你两棵二叉树的根节点p和q,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。示例输入:p=[1,2,3],q=[1,2......
  • 【数据结构和算法实践-链表-LeetCode23-合并K个有序数组】
    合并K个有序数组题目MyThought代码示例JAVA-8题目合并K个有序数组MyThought一、将ListNode放入PriorityQueue中1.1、设置PriorityQueue的比较器规则1.2、将ListNode[]放入priorityQueue二、再将数据依次弹出放到ListNode中代码示例JAVA-8publicListNod......
  • Python 默认列表(Default List):一种灵活的数据结构
    Python中的默认列表(DefaultList)是一种特殊的数据结构,它允许我们创建一个包含特定元素类型的列表,并在需要时动态地添加或删除元素。这种灵活性使得默认列表成为了处理一些不确定或变化的数据的有力工具。创建列表时指定元素类型在Python中,我们可以在创建列表时指定元素类型,如果......
  • C++ 数据结构——二叉树(最最最最最实用的二叉树教程)
    本文章以实用为主,所以不多废话直接开整本文所介绍的二叉树是最基础的二叉树,不是二叉搜索树,也不是平衡二叉树,就基本的二叉树若需要Python版,请跳转到 Python数据结构——二叉树(最最最最最实用的二叉树教程)二叉树的构建二叉树为一个父节点连接到两个子节点,若还要加入新的......