首页 > 其他分享 >02手写链表

02手写链表

时间:2023-08-07 23:00:55浏览次数:38  
标签:02 NULL return list next 链表 pLinkedlist 手写 ListTailInsert

一、简介

手写链表实现以下功能

  1. 尾插
  2. 获取指定下标的元素
  3. 按照指定位置插入元素
  4. 打印链表内容
  5. 删除指定元素
  6. 释放整个链表
  7. 链表反转
  8. 链表中相邻元素的和最大的两个元素的第一个节点,且返回和的最大值

二、源代码

LinkedList.h

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H

#include <stdio.h>

// define a struct node
typedef int dataType;
typedef struct node
{
    dataType data;
    struct node *next;
} linkedlist, *pLinkedlist;

// fuctions
pLinkedlist ListCreate();
int ListTailInsert(pLinkedlist list, dataType value); // head
pLinkedlist ListGet(pLinkedlist list, int pos);
int ListInsert(pLinkedlist list, dataType value, int pos);
int ListShow(pLinkedlist list);
int ListElementDelete(pLinkedlist list, int pos);
pLinkedlist ListFree(pLinkedlist list);
int ListReverse(pLinkedlist list);
pLinkedlist ListAdjMax(pLinkedlist list, dataType *value);

#endif

LinkedList.c

#include <stdlib.h>
#include "LinkedList.h"
#include <errno.h>

/**
 * @brief create a linked list
 *
 * @return pLinkedlist: Address of the head node
 */
pLinkedlist ListCreate()
{
    pLinkedlist list = (pLinkedlist)malloc(sizeof(linkedlist));
    if (list == NULL)
    {
        printf("malloc error\n");
        return NULL;
    }

    list->data = 0;
    list->next = NULL;

    return list;
}

int ListTailInsert(pLinkedlist list, dataType value)
{
    if (list == NULL)
    {
        printf("TailInsert error:arg list is invalid\n");
        return -1;
    }

    // Apply for a new space
    pLinkedlist newNode = (pLinkedlist)malloc(sizeof(linkedlist));
    if (newNode == NULL)
    {
        printf("malloc error\n");
        return -1;
    }

    // update value
    newNode->data = value;
    newNode->next = NULL;

    // Find the last element of the old linked list
    pLinkedlist p = list;
    while (p->next)
    {
        p = p->next;
    }

    // update list
    p->next = newNode;

    return 0;
}

/**
 * @brief Gets the address of the element at the specified location
 *
 * @param list
 * @param pos
 * @return pLinkedlist
 */
pLinkedlist ListGet(pLinkedlist list, int pos)
{
    if (list == NULL)
    {
        printf("ListGet error:arg list is invalid\n");
        return NULL;
    }

    if (pos == -1)
    {
        return list;
    }

    pLinkedlist p = list;
    for (int i = 0; i < pos + 1; i++)
    {
        p = p->next;
        if (p == NULL)
        {
            printf("pos is invalid\n");
            return NULL;
        }
    }

    return p;
}

/**
 * @brief Insert an element into the specified position
 *
 * @param list
 * @param value
 * @param pos
 * @return int 0:success -1:failed
 */
int ListInsert(pLinkedlist list, dataType value, int pos)
{
    if (list == NULL)
    {
        printf("ListInsert error:arg list is invalid\n");
        return -1;
    }

    // Apply for a new space
    pLinkedlist newNode = (pLinkedlist)malloc(sizeof(linkedlist));
    if (newNode == NULL)
    {
        printf("malloc error\n");
        return -1;
    }

    // update value
    newNode->data = value;
    newNode->next = NULL;

    // Find the location to be inserted
    pLinkedlist lastNode = ListGet(list, pos - 1);
    if (lastNode == NULL)
    {
        printf("Insert an invalid position\n");
        return -1;
    }

    // Complete insertion operation
    newNode->next = lastNode->next;
    lastNode->next = newNode;

    return 0;
}

int ListShow(pLinkedlist list)
{
    if (list == NULL)
    {
        printf("ListShow error:arg list is invalid\n");
        return -1;
    }

    pLinkedlist p = list;
    while (p->next)
    {
        p = p->next;
        printf("%d ", p->data);
    }
    printf("\n");

    return 0;
}

int ListElementDelete(pLinkedlist list, int pos)
{
    if (list == NULL)
    {
        perror("(ListElementDelete) invalid arg list");
        return -1;
    }

    if (pos < 0)
    {
        perror("(ListElementDelete) invalid arg pos");
        return -1;
    }

    // Find the element at the current position
    pLinkedlist p = ListGet(list, pos);
    if (p == NULL)
    {
        perror("(ListElementDelete) invalid arg pos");
        return -1;
    }

    // Find the previous element of the element at the current position
    pLinkedlist q = ListGet(list, pos - 1);
    q->next = p->next;
    free(p);
    p = NULL;

    return 0;
}

pLinkedlist ListFree(pLinkedlist list)
{
    if (list == NULL)
    {
        printf("ListFree error:arg list is invalid\n");
        return list;
    }

    pLinkedlist p = list;
    while (list != NULL)
    {
        p = list;
        list = list->next;
        free(p);
    }
    p = NULL;

    return NULL;
}

int ListReverse(pLinkedlist list)
{
    pLinkedlist p, q;
    if (list == NULL)
    {
        printf("ListReverse: arg is invalid.\n");
        return -1;
    }

    if (list->next == NULL || list->next->next == NULL)
    {
        return 0;
    }

    p = list->next->next;
    list->next->next = NULL;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        q->next = list->next;
        list->next = q;
    }

    return 0;
}

/**
 * @brief Find the first node with the largest sum of two adjacent elements in the entire linked list
 *
 * @param list
 * @param value sum
 * @return pLinkedlist
 */
pLinkedlist ListAdjMax(pLinkedlist list, dataType *value)
{
    int sum = 0;
    pLinkedlist p, q, r;
    if (list == NULL)
    {
        printf("ListAdjMax: arg list is invalid.\n");
        return NULL;
    }

    if (list->next == NULL || list->next->next == NULL || list->next->next->next == NULL)
    {
        return list;
    }

    p = list->next;
    q = list->next->next;
    sum = p->data + q->data;
    r = p;

    while (q->next != NULL)
    {
        p = p->next;
        q = q->next;

        if (sum < (p->data + q->data))
        {
            r = p;
            sum = p->data + q->data;
        }
    }

    *value = sum;
    return r;
}

main.c

#include <stdio.h>
#include "LinkedList.h"

void test_insert();
void test_ListGet();
void test_ListInsert();
void test_ListElementDelete();
void test_ListFree();
void test_ListReverse();
void test_ListAdjMax();

int main(int argc, char const *argv[])
{
    // test_insert();
    // test_ListGet();
    // test_ListInsert();
    // test_ListElementDelete();
    // test_ListFree();
    // test_ListReverse();
    test_ListAdjMax();
    return 0;
}

void test_insert()
{
    pLinkedlist list = ListCreate();

    ListTailInsert(list, 10);
    ListTailInsert(list, 20);
    ListTailInsert(list, 30);
    ListTailInsert(list, 40);
    ListTailInsert(list, 50);

    ListShow(list);
}

void test_ListGet()
{
    pLinkedlist list = ListCreate();

    ListTailInsert(list, 10);
    ListTailInsert(list, 20);
    ListTailInsert(list, 30);
    ListTailInsert(list, 40);
    ListTailInsert(list, 50);

    ListShow(list);

    for (int i = 0; i < 5; i++)
    {
        printf("list[%d] = %d\n", i, (ListGet(list, i))->data);
    }
}

void test_ListInsert()
{
    pLinkedlist list = ListCreate();

    ListTailInsert(list, 10);
    ListTailInsert(list, 20);
    ListTailInsert(list, 30);
    ListTailInsert(list, 40);
    ListTailInsert(list, 50);

    ListShow(list);

    printf("-------------------\n");

    ListInsert(list, 200, 1);
    ListShow(list);
}

void test_ListElementDelete()
{
    pLinkedlist list = ListCreate();

    ListTailInsert(list, 10);
    ListTailInsert(list, 20);
    ListTailInsert(list, 30);
    ListTailInsert(list, 40);
    ListTailInsert(list, 50);

    ListShow(list);

    printf("-------------------\n");

    ListElementDelete(list, 4);
    ListShow(list);
}

void test_ListFree()
{
    pLinkedlist list = ListCreate();

    ListTailInsert(list, 10);
    ListTailInsert(list, 20);
    ListTailInsert(list, 30);
    ListTailInsert(list, 40);
    ListTailInsert(list, 50);

    ListShow(list);

    list = ListFree(list);
    ListTailInsert(list, 50);
    ListShow(list);
}

void test_ListReverse()
{
    pLinkedlist list = ListCreate();

    ListTailInsert(list, 10);
    ListTailInsert(list, 20);
    ListTailInsert(list, 30);
    ListTailInsert(list, 40);
    ListTailInsert(list, 50);

    ListShow(list);

    printf("-------------------\n");

    ListReverse(list);
    ListShow(list);
}

void test_ListAdjMax()
{
    int max = 0;
    pLinkedlist list = ListCreate();

    ListTailInsert(list, 10);
    ListTailInsert(list, 20);
    ListTailInsert(list, 30);
    ListTailInsert(list, 40);
    ListTailInsert(list, 50);

    ListShow(list);

    pLinkedlist p = ListAdjMax(list, &max);
    printf("p->data = %d,max = %d", p->data, max);
}

总结

未实现的接口

  1. 合并两个链表
  2. 求两个链表的并集
  3. 元素排序
  4. 消除链表中的相同元素

标签:02,NULL,return,list,next,链表,pLinkedlist,手写,ListTailInsert
From: https://www.cnblogs.com/goldenFantome/p/17612989.html

相关文章

  • 【专题】2023年预制菜产业发展观察报告PDF合集分享(附原数据表)
    报告链接:https://tecdat.cn/?p=33388近年来,中国的预制菜行业迅速发展,已成为消费者生活中不可或缺的一部分。研究报告显示,预制菜行业在美国和日本等国家已经发展了很长时间,与中国市场相比,中国的预制菜市场仍有巨大的增长潜力。预制菜行业的蓬勃发展主要受到两个方面的推动:企业端通......
  • 【专题】2023年中国预制菜产业白皮书 报告PDF合集分享(附原数据表)
    报告链接:https://tecdat.cn/?p=33388近年来,中国的预制菜行业迅速发展,已成为消费者生活中不可或缺的一部分。研究报告显示,预制菜行业在美国和日本等国家已经发展了很长时间,与中国市场相比,中国的预制菜市场仍有巨大的增长潜力。预制菜行业的蓬勃发展主要受到两个方面的推动:企业端通......
  • 【专题】2023中国预制菜企业竞争力百强研究 报告PDF合集分享(附原数据表)
    报告链接:https://tecdat.cn/?p=33388近年来,中国的预制菜行业迅速发展,已成为消费者生活中不可或缺的一部分。研究报告显示,预制菜行业在美国和日本等国家已经发展了很长时间,与中国市场相比,中国的预制菜市场仍有巨大的增长潜力。预制菜行业的蓬勃发展主要受到两个方面的推动:企业端通......
  • 【专题】2022年预制菜行业现状问题、政策标准及趋势分析报告PDF合集分享(附原数据表)
    报告链接:https://tecdat.cn/?p=33388近年来,中国的预制菜行业迅速发展,已成为消费者生活中不可或缺的一部分。研究报告显示,预制菜行业在美国和日本等国家已经发展了很长时间,与中国市场相比,中国的预制菜市场仍有巨大的增长潜力。预制菜行业的蓬勃发展主要受到两个方面的推动:企业端通......
  • 【专题】2022中国预制菜行业蓝皮书 报告PDF合集分享(附原数据表)
    报告链接:https://tecdat.cn/?p=33388近年来,中国的预制菜行业迅速发展,已成为消费者生活中不可或缺的一部分。研究报告显示,预制菜行业在美国和日本等国家已经发展了很长时间,与中国市场相比,中国的预制菜市场仍有巨大的增长潜力。预制菜行业的蓬勃发展主要受到两个方面的推动:企业端通......
  • 【专题】2022年预制菜市场展望-乘风而来,群雄逐鹿 报告PDF合集分享(附原数据表)
    报告链接:https://tecdat.cn/?p=33388近年来,中国的预制菜行业迅速发展,已成为消费者生活中不可或缺的一部分。研究报告显示,预制菜行业在美国和日本等国家已经发展了很长时间,与中国市场相比,中国的预制菜市场仍有巨大的增长潜力。预制菜行业的蓬勃发展主要受到两个方面的推动:企业端通......
  • 2023.8.7
    今天把花式栈溢出的framefaking结束了,并且记成了笔记,查东西的时候发现活用最近兴起的ai生成挺有用的,可以很方便地查到很多基础知识,比如pwntools的一些函数,到pwntools官网去查,就感觉查起来有点难受,而且还不一定能找到满意的解答,用ai生成的答案,虽然也不能保证一定正确,但至少也有不......
  • 2023牛客+杭电补题和总结记录(后半)
    前半继续写要被编辑器卡飞了,换个档杭电第六场\(1002.Pair\Sum\and\Perfect\Square\)对于每个位置可以求出该位置的数和哪些位置的数能够组成完全平方数,因为原序列是排列,并且完全平方数个数不多,所以预处理的复杂度不高。(也可以在后续统计过程中处理)处理出点对以后就变成了......
  • 2023.8.6
    今天早起啦,早起化妆准备出发!外面很冷,感觉像是秋天来了其实也快秋天了哈哈,一年过的真的很快啊和朋友做的不是同一辆的火车但是基本上是同时到第一天去了太原街和山姆超市,晚上去了彩电塔夜市拍了很多照片,开心!酒店很便宜但是也很好......
  • 【专题】2022年中国预制菜行业发展趋势研究报告PDF合集分享(附原数据表)
    报告链接:https://tecdat.cn/?p=33388近年来,中国的预制菜行业迅速发展,已成为消费者生活中不可或缺的一部分。研究报告显示,预制菜行业在美国和日本等国家已经发展了很长时间,与中国市场相比,中国的预制菜市场仍有巨大的增长潜力。预制菜行业的蓬勃发展主要受到两个方面的推动:企业端通......