LinkList.c 4.6 KB
Newer Older
大熊人's avatar
大熊人 已提交
1 2 3 4
/*
 * @Description: 单链表
 * @Author: 大熊人
 * @Date: 2020-10-30 20:17:20
大熊人's avatar
大熊人 已提交
5
 * @LastEditTime: 2020-11-08 00:09:04
大熊人's avatar
大熊人 已提交
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
 */
#include <stdio.h>
#include <stdlib.h>
#include "includes/LinkList.h"

/**
 * @description: 初始化带头结点的单链表
 * @param {struct **}L  用二级指针间接修改掉头指针的指向 使其指向初始化的头结点
 */
void InitList(LinkList *L)
{
    LinkList temp = (LinkList)malloc(sizeof(LinkNode));
    temp->Data = -1;
    temp->Next = NULL;
    *L = temp;
}

/**
 * @description: 头插法
 * @param {struct *}L
 * @param {LIST_DATA_TYPE}X
 */
void HeadInsert(LinkList L, LIST_DATA_TYPE X)
{
    LinkList temp = (LinkList)malloc(sizeof(LinkNode));
    temp->Data = X;
    temp->Next = L->Next;
    L->Next = temp;
}

/**
 * @description: 尾插法
 * @param {struct *}L
 * @param {LIST_DATA_TYPE}X
 */
void TailInsert(LinkList L, LIST_DATA_TYPE X)
{
    LinkList temp = (LinkList)malloc(sizeof(LinkNode));

    /* 查找最后一个结点 */
    while (L->Next)
    {
        L = L->Next;
    }
    temp->Data = X;
    temp->Next = NULL;
    L->Next = temp;
}

/**
 * @description: 在第i个位置插入元素 1<=i<=ListLength(L)+1
 * @param {struct *}L
 * @param {int}i
 * @param {LIST_DATA_TYPE}X
 * @return {int}
 */
int ListInset(LinkList L, int i, LIST_DATA_TYPE X)
{
    LinkList temp;
    int j = 1;

    /* 查找第i个结点的前驱或最后一个结点 */
    while (L && j < i)
    {
        L = L->Next;
        j++;
    }
    /* 防止输入 i<1 或 i>ListLength(L)+1 的情况 */
    if (!L && j > i)
    {
        return FALSE;
    }

    temp = (LinkList)malloc(sizeof(LinkNode)); //申请一个内存空间作为新结点
    temp->Data = X;                            //把数据存入新结点
    temp->Next = L->Next;                      //使新结点的后继指针指向L的后继 (L是第i个结点的前驱,L的后继就是第i个结点)
    L->Next = temp;                            //再使L的后继指针指向新结点
    return TRUE;
}

/**
 * @description: 删除第i个位置的元素,并存储在X中 1<=i<=ListLength(L)
 * @param {struct *}L
 * @param {int}i
 * @param {LIST_DATA_TYPE *}X
 * @return {int}
 */
int ListDelete(LinkList L, int i, LIST_DATA_TYPE *X)
{
    LinkList temp;
    int j = 1;

    /* 查找第i个结点的前驱 */
    while (L->Next && j < i) //L->Next代表当前要删除的结点不能为空
    {
        L = L->Next;
        j++;
    }
    /* 防止输入 i<1 或 i>ListLength(L) 的情况 */
    if (!(L->Next) && j > i)
    {
        return FALSE;
    }

    temp = L->Next;
    *X = temp->Data;
    L->Next = temp->Next;
    free(temp); //释放内存空间
    return TRUE;
}

/**
 * @description: 获取第i个位置元素,并存储在X中 1 <= i <= ListLength(L)
 * @param {struct *}L
 * @param {int}i
 * @param {LIST_DATA_TYPE *}X
 * @return {int}
 */
int GetElem(LinkList L, int i, LIST_DATA_TYPE *X)
{
    int j = 1;

    /* 查找第i个结点的前驱 */
    while (L && j < i)
    {
        L = L->Next;
        j++;
    }
    /* 防止输入 i<1 或 i>ListLength(L) 的情况 */
    if (!L && j > i)
    {
        return FALSE;
    }

    *X = L->Next->Data;
    return TRUE;
}

/**
 * @description: 打印链表
 * @param {struct *}L
 */
void PrintLinkList(LinkList L)
{
    L = L->Next; //跳过头结点
    printf("%d", L->Data);
    while (L->Next)
    {
        L = L->Next;
        printf("->%d", L->Data);
    }
}

/**
 * @description: 返回元素个数
 * @param {struct *}L
 * @return {int}
 */
int ListLength(LinkList L)
{
    int count = 0;
    while (L->Next)
    {
        count++;
        L = L->Next;
    }
    return count;
}

大熊人's avatar
大熊人 已提交
175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
/**
 * @description: 销毁单链表
 * @param {struct **}L
 */
void Destroy(LinkList *L)
{
    if (*L == NULL)
    {
        return;
    }
    Destroy(&(*L)->Next);
    free(*L);
    *L = NULL;
}

大熊人's avatar
大熊人 已提交
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
/**
 * @description: 测试单链表
 */
void TestLinkList()
{
    LinkList head = NULL;
    LIST_DATA_TYPE value;

    InitList(&head);
    HeadInsert(head, 1);
    HeadInsert(head, 2);
    HeadInsert(head, 3);
    TailInsert(head, 2);
    TailInsert(head, 3);
    PrintLinkList(head);

    printf("\n\nListInset(6)=4 %s\n", ListInset(head, 6, 4) ? "TRUE" : "FALSE");
    PrintLinkList(head);
    printf("\nListInset(1)=100 %s\n", ListInset(head, 1, 100) ? "TRUE" : "FALSE");
    PrintLinkList(head);
    printf("\n\nListDelete(7) %s\n", ListDelete(head, 7, &value) ? "TRUE" : "FALSE");
    PrintLinkList(head);
    printf("\n\nGetElem(4) %s\n", GetElem(head, 4, &value) ? "TRUE" : "FALSE");
    printf("GetElem(4)=%d\n\n", value);

    PrintLinkList(head);
    printf("\nListLength=%d\n", ListLength(head));
大熊人's avatar
大熊人 已提交
217 218 219 220 221 222
    Destroy(&head);
}

void main()
{
    TestLinkList();
大熊人's avatar
大熊人 已提交
223
}