链表的一些基础应用

Hugo888

#include <stdlib.h>

#include "LinkedList.h"

typedef struct linkedlist {
    struct linkedlistnode *head;
} linkedlist;

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

ll LLCreate(void)
{
    // TODO: replace this with your code
    // make the compiler happy
    return NULL;
}

void LLDestroy(ll list)
{
    // TODO: replace this with your code
    // make the compiler happy
    (void) list;
}

/**
* Add an element to the end of the link-list
*/
ll LLAppend(ll list, int item)
{
    // TODO: replace this with your code
    // make the compiler happy
    (void) list;
    (void) item;
    return NULL;
}

/**
* Add an element to the start of the link-list
*/
ll LLPrepend(ll list, int item)
{
    // TODO: replace this with your code
    // make the compiler happy
    (void) list;
    (void) item;
    return NULL;
}

/**
* Remove and return the last element from the link-list
* Or 0 if the list is empty
*/
int LLShrink(ll list)
{
    // TODO: replace this with your code
    // make the compiler happy
    (void) list;
    return 0;
}

/**
* Remove and return the first element from the link-list
* Or 0 if the list is empty
*/
int LLShift(ll list)
{
    // TODO: replace this with your code
    // make the compiler happy
    (void) list;
    return 0;
}

Hugo888

                               
登录/注册后可看大图

Hugo888

有偿！！！方便的话加个好友救救孩子

Gacy

Hugo888 发表于 2021-6-21 10:07
有偿！！！方便的话加个好友救救孩子

你得等大佬们有时间回答你的问题

yuxijian2020

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct linkedlist {
    struct linkedlistnode* head;
} linkedlist;

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

//你没给 ll 的定义， 我猜的
typedef linkedlist* ll;

ll LLCreate(void)
{
    // TODO: replace this with your code
    // make the compiler happy
    ll list = (ll)malloc(sizeof(linkedlist));   //申请内存
    if (list == NULL)                           //申请失败退出
        return NULL;

    list->head = NULL;                          //设置初始值

    return list;
}

void LLDestroy(ll list)
{
    // TODO: replace this with your code
    // make the compiler happy
    //(void)list;
    linkedlistnode* cur = list->head;   //当前对象指针
    linkedlistnode* next;               //下个对象指针

    while (cur != NULL)
    {
        next = cur->next;               //下个对象指针 = 当前对象指针的next
        free(cur);                      //释放当前对象
        cur = next;                     //进入下一个对象
    }

    free(list);                         //释放玩所有节点后，释放链表对象
}

/**
* Add an element to the end of the link-list
*/
ll LLAppend(ll list, int item)
{
    // TODO: replace this with your code
    // make the compiler happy
    //(void)list;
    //(void)item;
    if (list->head == NULL)     //如果头节点为空，则初始化头节点就可以了
    {
        list->head = (linkedlistnode*)malloc(sizeof(linkedlistnode));
        if (list->head == NULL)
            return list;

        list->head->data = item;
        list->head->next = NULL;
        return list;
    }

    linkedlistnode* tail = list->head;      //尾节点
    linkedlistnode* next = list->head;      //下个节点
    while (next != NULL)                    //循环找到最后一个节点
    {
        tail = next;                        //当前的next就是当前的尾
        next = next->next;                  //next往下遍历
    }
    //找到尾节点后，在尾节点后添加新的节点
    tail->next = (linkedlistnode*)malloc(sizeof(linkedlistnode));
    if (tail->next == NULL)
        return list;
    //初始化
    tail->next->data = item;
    tail->next->next = NULL;

    return list;
}

/**
* Add an element to the start of the link-list
*/
ll LLPrepend(ll list, int item)
{
    // TODO: replace this with your code
    // make the compiler happy
    //(void)list;
    //(void)item;
    //创建新节点
    linkedlistnode* head = (linkedlistnode*)malloc(sizeof(linkedlistnode));
    if (head == NULL)
        return list;
    
    head->data = item;          //初始化数据
    head->next = list->head;    //新节点的下个节点 设为 之前的头节点
    list->head = head;          //让链表的头节点指向新节点

    return list;
}

/**
* Remove and return the last element from the link-list
* Or 0 if the list is empty
*/
int LLShrink(ll list)
{
    // TODO: replace this with your code
    // make the compiler happy
    //(void)list;
    if (list == NULL || list->head == NULL)     //链表为空直接返回
        return 0;

    int index = 0;                              //记录序号
    linkedlistnode* next = list->head;          //下个节点
    linkedlistnode* tail = list->head;          //尾节点
    while (next->next != NULL)                  //遍历找到尾节点的前一个节点
    {
        tail = next;
        next = next->next;
        index++;                                //遍历时，找到尾节点的序号
    }

    tail->next = NULL;          //断开最后一个节点的连接
    free(next);                 //释放空间

    return index;
}

/**
* Remove and return the first element from the link-list
* Or 0 if the list is empty
*/
int LLShift(ll list)
{
    // TODO: replace this with your code
    // make the compiler happy
    //(void)list;
    if (list == NULL || list->head == NULL) //空链表直接返回
        return 0;
    else if (list->head->next == NULL)      //链表只有头节点，直接删除头节点然后返回
    {
        free(list->head);
        list->head = NULL;
        return 0;
    }

    linkedlistnode* head = list->head->next;    //记录链表头节点的下个节点(链表的第2个节点)
    free(list->head);                           //删除头节点
    list->head = head;                          //链表头变为之前的第2个节点

    return 1;
}

void ShowList(ll list)      //遍历输出链表内容，测试用....
{
    linkedlistnode* cur = list->head;           //
    while (cur != NULL)
    {
        printf_s("%d ", cur->data);
        cur = cur->next;
    }
    printf_s("\n");
}

int main()
{
    ll list = LLCreate();
    LLAppend(list, 1);
    ShowList(list);
    LLAppend(list, 2);
    ShowList(list);
    LLAppend(list, 3);
    ShowList(list);
    LLAppend(list, 4);
    ShowList(list);
    LLAppend(list, 5);
    ShowList(list);

    LLPrepend(list, 1);
    ShowList(list);
    LLPrepend(list, 2);
    ShowList(list);
    LLPrepend(list, 3);
    ShowList(list);
    LLPrepend(list, 4);
    ShowList(list);
    LLPrepend(list, 5);
    ShowList(list);

    LLShrink(list);
    ShowList(list);
    LLShrink(list);
    ShowList(list);
    LLShrink(list);
    ShowList(list);

    LLShift(list);
    ShowList(list);
    LLShift(list);
    ShowList(list);
    LLShift(list);
    ShowList(list);

    return 0;
}