数据结构--链表的ADT实现(头插,尾插,查找,定位,创建...)

1 人赞了该文章

实现截图为:

代码为:

// 线性表--链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include "pch.h"
#include <iostream>
#include  "malloc.h"
#define ERROR -1
#define OVERFLOW -2
#define SUCCESS  1
typedef  int  ElemType;

//链表结构体
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}Lnode,*LinkNode;

//初始化链表
void InitLinkList(LinkNode &L)
{
    L = (LinkNode)malloc(sizeof(Lnode));
    L->data = 0;
    L->next = NULL;
}
//创建一个链表(头插法)
void CreateLinkList(LinkNode &L)
{
    int i;
    printf("您想存储几个数(头插法):\r\n");
    scanf("%d", &i);
    for (int j = 0; j < i; j++)
    {
        ElemType m;
        LinkNode s;
        s = (LinkNode)malloc(sizeof(Lnode));
        if (s==NULL)
        {
            printf("空间分配失败\r\n");
        }
        else
        {
            printf("您想输入的第%d个数为:\r\n", j + 1);
            scanf("%d", &m);
            s->data = m;
            s->next = L->next;
            L->next = s;
            printf("第%d个数字插入成功!\r\n", j + 1);
        }

    }
}
//创建一个链表(尾插法)
void CreateLinkListTail(LinkNode &L)
{
    LinkNode p = L;
    int i;
    printf("您想存储几个数(尾插法):\r\n");
    scanf("%d", &i);
    for (int j = 0; j < i; j++)
    {
        ElemType m;
        LinkNode s;
        s = (LinkNode)malloc(sizeof(Lnode));
        if (s == NULL)
        {
            printf("空间分配失败\r\n");
        }
        else
        {
            printf("您想输入的第%d个数为:\r\n", j + 1);
            scanf("%d", &m);
            s->data = m;
            s->next = p->next;
            p->next = s;
            p = s;
            printf("第%d个数字插入成功!\r\n", j + 1);
        }

    }
}
//销毁链表
void DestroyLinkList(LinkNode &L)
{
    LinkNode pre = L;
    L = L->next;
    while (pre->next!=NULL)
    {
        free(pre);
        pre = L;
        L = L->next;
    }
    free(L);
    printf("内存空间释放成功\r\n");
}
//判断链表是否为空
void  LinkListEmpty(LinkNode L)
{
    if (L->next==NULL)
    {
        printf("该链表为空\r\n");
    }
    else
    {
        printf("该链表不为空\r\n");
    }
}
//求链表的长度
int LinkListLength(LinkNode L)
{
    int length=0;
    while (L->next!=NULL)
    {
        length++;
        L = L->next;
    }
    printf("链表的长度为%d\r\n",length);
    return  length;
}
//输出链表中存储的值
void DispLinkList(LinkNode L)
{
    int i = 1;
    printf("**************遍历链表*******************\r\n");
    while (L->next!=NULL)
    {
        printf("第%d个位置的值为%d\r\n", i,L->next->data);
        L = L->next;
        i++;
    }
    printf("***************************************\r\n");
}
//求链表中指定位置的某个值
void  GetElem(LinkNode L, int i, ElemType &e)
{
    //L = L->next;
    //int i = 1;
    for (int j = 1; j <=i; j++)
    {
        L = L->next;
    }
    e = L->data;
    printf("第%d个位置的值为%d\r\n", i, e);
}
//定位查找链表中的值
void LocateElem(LinkNode L, ElemType e)
{
    int i = 1;
    while (L->next!=NULL)
    {
        if (L->next->data == e)
        {
            printf("查找成功,存在,在第%d个位置\r\n",i);
            break;
        }
        else
        {
            L = L->next;
            i++;
        }
    }
}
//在链表中插入一个数据元素
ElemType LinkListInsert(LinkNode &L, int i, ElemType e)
{
    LinkNode p = L;
    LinkNode s=(LinkNode)malloc(sizeof(Lnode));
    int length = LinkListLength(L);
    if (i<1 || i>length + 1)
    {
        printf("输入错误\r\n");
        return ERROR;
    }
    else
    {
        for (int j = 1; j < i; j++)
        {
            p =p->next;
        }
        s->data = e;
        s->next = p->next;
        p->next = s;
        printf("插入成功\r\n");
        return  SUCCESS;
    }
}

//删除链表中的元素
ElemType  LinkListDelete(LinkNode &L, int i, ElemType &e)
{
    LinkNode s,p ;
    p = L;
    int length = LinkListLength(L);
    if (i<1 || i>length + 1)
    {
        printf("输入错误\r\n");
        return ERROR;
    }
    else
    {
        for (int j = 1; j < i; j++)
        {
            p = p->next;
        }
        s =p->next;
        p->next = p->next->next;
        free(s);
        printf("删除成功!\r\n");
        LinkListLength(L);

    }
}
int main()
{
    LinkNode L;
    ElemType e,m;
    printf("--------------初始化链表--------------\r\n");
    InitLinkList(L);
    printf("-----------------创建链表--------------------\r\n");
    //CreateLinkList(L);
    CreateLinkListTail(L);
    DispLinkList(L);
    printf("-----------判断链表是否为空-------------------\r\n");
    LinkListEmpty(L);
    printf("-----------------求链表的长度-----------------------------\r\n");
    LinkListLength(L);
    printf("------------------求第2个位置,元素的值--------------------------\r\n");
    GetElem(L, 2, e);
    printf("--------------在第2个位置插入一个元素666----------------------------\r\n");
    LinkListInsert(L, 2, 666);
    DispLinkList(L);
    printf("--------查找链表中是否存在666这个元素------------\r\n");
    LocateElem(L, 666);
    printf("----------------删除第3个元素-----------------------------\r\n");
    LinkListDelete(L, 3, m);
    DispLinkList(L);
    DestroyLinkList(L);
}

评论

暂无评论