单链表数据结构代码(C语言)

资讯 2023-12-06 17:23:54

利用单链表数据结构实现一组数据的存储,通过简单的交互实现单链表的增删改查。

//ADT 线性表(List) 链式存储结构 LinkList
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;
//定义单链表
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList; //定义结点结构体指针

//初始化单链表
Status InitList(LinkList *L, int *Length)
{
    *L = (LinkList)malloc(sizeof(Node)); //创建头结点,用头指针L指向
    *Length = 0;                         //初始化单链表长度为0
    if (*L == 0)                         //创建头结点失败返回EEOR
        return ERROR;
    else
        return OK;
}

//判断单链表是否初始化成功
Status ListEmpty(LinkList L)
{
    if (L->next == 0)
        return FALSE;
    else
        return TRUE;
}

//清空单链表
Status ClearList(LinkList *L, int *Length)
{
    LinkList p = NULL;
    LinkList q = NULL;
    p = (*L)->next; //指向第一个结点
    if (p == 0)
        return ERROR;
    else
        while (p)
        {
            q = p->next;
            free(p); //释放结点申请的动态内存空间
            p = q;
        }
    (*L)->next = NULL; //将头结点指针域清空
    free(*L);          //释放头结点
    *Length = 0;
    return OK;
}

//查询数据元素的个数
Status ListLength(int Length)
{
    return Length;
}

//单链表数据元素的输入
Status CreateList(LinkList *L, int *Length)
{
    LinkList s = (*L);
    printf("请输入一组整型数据:");
    while (TRUE)
    {
        int a = 0;
        LinkList p = NULL;
        scanf("%d", &a);
        char c = getchar();
        p = (LinkList)malloc(sizeof(Node));
        p->data = a;
        s->next = p;
        s = p;
        p->next = NULL;
        *Length = *Length + 1;
        if (c == '\n')
            break;
    }
    return OK;
}

//关于单链表的增删改查操作
//单链表的取值,用e将单链表中第i个数据元素的值取出
Status GetElem(LinkList L, int i, ElemType *e, int Length)
{
    int j;
    LinkList p = L->next;
    if (i > Length || p == 0)
        return ERROR;
    for (j = 1; j < i; j++)
    {
        p = p->next;
        if (p == 0)
            return ERROR;
    }
    *e = p->data;
    return OK;
}

//单链表的查询,查询单链表中数据元素的值为e的位序i
Status LocateElem(LinkList L, ElemType e)
{
    int i = 0;
    LinkList p = L->next;
    while (p)
    {
        i++;
        if (p->data == e)
            return i;
        p = p->next;
    }
    return ERROR;
}

//单链表的插入,将值为e的数据元素插入到单链表的第i个位置
Status ListInsert(LinkList *L, int i, ElemType e, int *Length)
{
    int j;
    LinkList p = (*L)->next;
    LinkList s = NULL;
    if (i > *Length)
        return ERROR;
    for (j = 1; j < i - 1; j++)
    {
        p = p->next;
        if (p == 0)
            return ERROR;
    }
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    *Length = *Length + 1;
    return OK;
}

//单链表的删除,将单链表第i个数据元素删除,用e返回其值。
Status ListDelete(LinkList *L, int i, ElemType *e, int *Length)
{
    int j;
    LinkList p = (*L)->next;
    LinkList q = NULL;
    if (i > *Length)
        return ERROR;
    for (j = 1; j < i - 1; j++)
    {
        p = p->next;
        if (p == 0)
            return ERROR;
    }
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    *Length = *Length - 1;
    return OK;
}

//单链表主函数
int main()
{
    LinkList L = NULL;
    ElemType e = 0;
    Status i = 0;
    int Length = 0;
    printf("单链表自动初始化中......\n");
    i = InitList(&L, &Length); //初始化单链表
    i = ListEmpty(L);          //判断单链表是否初始化成功
    if (i == 1)
        printf("单链表初始化成功,单链表长度为%d\n", Length); //输出初始化结果
    else
        printf("单链表初始化失败\n");
    i = CreateList(&L, &Length);
    if (i == 1)
        printf("数据元素存储完毕,数据元素个数为%d\n", Length);
    while (TRUE) //该循环意在实现交互性。
    {
        int a;
        printf("请选择要进行的操作:\n1:查询单链表数据元素个数\n2:取出相应位序数据元素的值\n3:查询数据元素的值的相应位置\n4:数据元素的插入\n5:数据元素的删除\n6:清空单链表并结束程序\n");
        scanf("%d", &a);
        switch (a)
        {
        case 1:
        {
            int b;
            b = ListLength(Length);
            printf("单链表数据元素个数为%d\n", b);
            break;
        }
        case 2:
        {
            int b;
            printf("请输入将要取值的位序:");
            scanf("%d", &i);
            b = GetElem(L, i, &e, Length);
            if (b == 0)
                printf("将要取值的位序不正确\n");
            else
                printf("取值成功,值为%d\n", e);
            break;
        }
        case 3:
        {
            int b;
            printf("请输入将要查询的值:");
            scanf("%d", &e);
            b = LocateElem(L, e);
            if (b == 0)
                printf("将要查询的值不在顺序表中\n");
            else
                printf("查询成功,位序为:%d\n", b);
            break;
        }
        case 4:
        {
            int b;
            printf("请输入将要插入的值:");
            scanf("%d", &e);
            printf("请输入将要插入的位序:");
            scanf("%d", &i);
            b = ListInsert(&L, i, e, &Length);
            if (b == 0)
                printf("插入失败\n");
            else
                printf("插入成功\n");
            break;
        }
        case 5:
        {
            int b;
            printf("请输入将要删除的位序:\n");
            scanf("%d", &i);
            b = ListDelete(&L, i, &e, &Length);
            if (b == 0)
                printf("删除失败\n");
            else
                printf("删除成功,删除的值为%d\n", e);
            break;
        }
        case 6:
        {
            int b;
            b = ClearList(&L, &Length);
            if (b == 0)
                printf("单链表清空失败\n");
            else
                printf("单链表清空成功\n");
            exit(0);
        }
        default:
            break;
        }
    }
    return 0;
}
声明:该文观点仅代表作者本人,必看呐发布平台,仅提供信息存储空间服务。