【数据结构实验】链表的创建与功能的实现

一、事先在文件下创建两个txt。

例如在D盘下创建LA.txt和LB.txt，里面写上两个链表所需要的数据。

内容：

二、使用Visual Studio 2022写代码

1.创建一个结构体类型，包含链表所需要的一些类型

typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode,*LinkList;        //单链表结点类型

2.初始化单链表

void InitList(LNode* &L) //初始化单链表
{
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
}

3.写一个函数用于将d盘下创建好的LA.txt和LB.txt数据以数组的形式导入作为函数返回值

void Input(int v[])    //从已经在目录下创建好的链表数据txt文本里导入数据至数组里返回。
{
    char filename[100];
    printf("请输入链表数据文件位置：");
    scanf("%s", filename);
    FILE* fp = fopen(filename, "r");
    int a[6] = { 0 };
    int i = 0;
    while (!feof(fp))
    {
        fscanf(fp, "%d ", &a[i]);
        i++;
    }
    for (i = 0; i < 6; i++)
    {
        v[i] = a[i];
    }
    fclose(fp); //读完就退出循环
}

4.创建链表，即向初始化好的链表里填入数据

void CreateList(LNode* &L, int a[], int n) //创建List,(链表的数据从传入的列表a中输入。)
{
    LNode* s, * r;            //指向新结点的指针s，始终指向尾结点的指针r
    L = (LNode*)malloc(sizeof(LNode));
    r = L;
    for (int i = 0; i < n; i++) {
        s = (LNode*)malloc(sizeof(LNode));//为存储数据域的结点s分配内存
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
}

5.判断是否为空链表功能

bool ListEmpty(LNode* L) //判断是否为空链表。
{
    if (L->next == NULL)
    {
        return true;
    }
    return false;
 
}

6.将链表设置为空链表功能

void ClearList(LNode* &L)//将L设置为空链表。
{
    LinkList p = L->next;
    while (p != NULL)
    {
        p->data = NULL;
        p = p->next;
    }
}

7.返回链表元素个数功能

int ListLength(LNode* L) //计算单链表的元素个数，存在n中返回。
{
    int n = 0;
    LNode* p = L;    //设置一个指针，初始时指向头结点
    while (p->next != NULL) 
    {
        n++;
        p = p->next;
    }
    return n;
}

8.返回链表中第i个元素功能，是“第i个”，也就是索引值为i-1的元素，之后的第i个也是这个意思

bool GetElem(LNode* L, int i, int& e)  //求第i个元素的值，赋值给e返回。
{
    int j = 0;
    LNode* p = L->next;
    if (i <= 0|| i > (ListLength(L))) return false;    //无效传入值i
    while (j < i-1 && p != NULL) {        //移动指针p
        p = p->next;
        j++;
    }
    if (p == NULL) return false;        //若i超出链表长度
    else {
        e = p->data;            //数据域赋值给e，e是传入的提前定义了的int变量
        return true;
    }
}

9.插入元素至链表第i个元素位置

bool ListInsert(LinkList &L, int i, int e) //插入新的元素在链表中第i个元素的位置。
{
    LinkList p = L,s;
    int j = 0;
    if (!p || i<1 || i>(ListLength(L)))//i小于1或大于表长。
        return false;
    while (p && j < i-1)//寻找第i-2个节点，并且p指向第i-1个节点。
    {
        p = p->next;
        ++j;
    }
    s = (LinkList)malloc(sizeof(LNode));//创建一个新指针s指向新元素e。
    s->data = e;
    s->next = p->next;//插入新元素至链表中。
    p->next = s;
    return true;
}

10.删除链表第i个元素，并返回删除的元素值

bool ListDelete(LinkList& L, int i, int& e) //删除链表中第i个元素，并用e返回其值。
{
    LinkList p = L, q;
    int j = 0;
    while (p->next && j < i-1)//找到第i个节点的直接前驱，令p指向它。
    {
        p=p->next;
        ++j;
    }
    if (!(p->next) || i<1 || i>(ListLength(L)))//删除位置不合理
        return false;
    q = (LinkList)malloc(sizeof(LNode));//创建一个新指针q用于指向第i+1个节点。
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);//释放第i个节点的存储空间。
    return true;

}

11.输出链表功能

void OutputList(LNode* L) //输出链表。
{
    int element;
    int count=0; //用于计算链表里有多少个元素。
    LNode* p = L->next;
    if (p == NULL)
        printf("链表不存在。n");
    else
    {
        while (p != NULL)
        {
            element = p->data;
            printf("%d ", element);
            p = p->next;
            count++;
        }
        printf("n");
        printf("链表中此时一共有%d个元素。n", count);
    }
}

12.合并两个链表功能（元素按升序排列）

void UnionList(LinkList &LA, LinkList &LB, LinkList &LC)  //合并单链表LA和LB得到新的单链表LC，LC元素按非减排列。
{
    LinkList pa=LA->next, pb=LB->next, pc;
    LC = pc = LA;//先用LA的头节点作为LC的头节点。
    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;//pc指向LA中的节点。
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        pc->next = pa ? pa : pb;//当pa或pb读完后插入另一个的剩余段。
    }
}

13.销毁单链表功能

void DestroyList(LNode* &L)//销毁单链表
{
    LNode* pre, * p;
    pre = L;
    p = L->next;
    while (p != NULL) {
        free(pre);
        pre = p;       
        p = p->next;
    }
    free(pre);
}

三、完整代码（包含main函数）

#include
#include
#pragma warning(disable : 4996) //防止报fopen,fscanf,fprintf  是 unsafe的报错。

typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode,*LinkList;        //单链表结点类型

void InitList(LNode* &L) //初始化单链表
{
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
}

void Input(int v[])    //从已经在目录下创建好的链表数据txt文本里导入数据至数组里返回。
{
    char filename[100];
    printf("请输入链表数据文件位置：");
    scanf("%s", filename);
    FILE* fp = fopen(filename, "r");
    int a[6] = { 0 };
    int i = 0;
    while (!feof(fp))
    {
        fscanf(fp, "%d ", &a[i]);
        i++;
    }
    for (i = 0; i < 6; i++)
    {
        v[i] = a[i];
    }
    fclose(fp); //读完就退出循环
}

void CreateList(LNode* &L, int a[], int n) //创建List,(链表的数据从传入的列表a中输入。)
{
    LNode* s, * r;            //指向新结点的指针s，始终指向尾结点的指针r
    L = (LNode*)malloc(sizeof(LNode));
    r = L;
    for (int i = 0; i < n; i++) {
        s = (LNode*)malloc(sizeof(LNode));//为存储数据域的结点s分配内存
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
}


void DestroyList(LNode* &L)//销毁单链表
{
    LNode* pre, * p;
    pre = L;
    p = L->next;
    while (p != NULL) {
        free(pre);
        pre = p;       
        p = p->next;
    }
    free(pre);
}

void ClearList(LNode* &L)//将L设置为空链表。
{
    LinkList p = L->next;
    while (p != NULL)
    {
        p->data = NULL;
        p = p->next;
    }
}

bool ListEmpty(LNode* L) //判断是否为空链表。
{
    if (L->next == NULL)
    {
        return true;
    }
    return false;
 
}

int ListLength(LNode* L) //计算单链表的元素个数，存在n中返回。
{
    int n = 0;
    LNode* p = L;    //设置一个指针，初始时指向头结点
    while (p->next != NULL) 
    {
        n++;
        p = p->next;
    }
    return n;
}

bool GetElem(LNode* L, int i, int& e)  //求第i个元素的值，赋值给e返回。
{
    int j = 0;
    LNode* p = L->next;
    if (i <= 0|| i > (ListLength(L))) return false;    //无效传入值i
    while (j < i-1 && p != NULL) {        //移动指针p
        p = p->next;
        j++;
    }
    if (p == NULL) return false;        //若i超出链表长度
    else {
        e = p->data;            //数据域赋值给e，e是传入的提前定义了的int变量
        return true;
    }
}

bool ListInsert(LinkList &L, int i, int e) //插入新的元素在链表中第i个元素的位置。
{
    LinkList p = L,s;
    int j = 0;
    if (!p || i<1 || i>(ListLength(L)))//i小于1或大于表长。
        return false;
    while (p && j < i-1)//寻找第i-2个节点，并且p指向第i-1个节点。
    {
        p = p->next;
        ++j;
    }
    s = (LinkList)malloc(sizeof(LNode));//创建一个新指针s指向新元素e。
    s->data = e;
    s->next = p->next;//插入新元素至链表中。
    p->next = s;
    return true;
}

bool ListDelete(LinkList& L, int i, int& e) //删除链表中第i个元素，并用e返回其值。
{
    LinkList p = L, q;
    int j = 0;
    while (p->next && j < i-1)//找到第i个节点的直接前驱，令p指向它。
    {
        p=p->next;
        ++j;
    }
    if (!(p->next) || i<1 || i>(ListLength(L)))//删除位置不合理
        return false;
    q = (LinkList)malloc(sizeof(LNode));//创建一个新指针q用于指向第i+1个节点。
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);//释放第i个节点的存储空间。
    return true;

}

void OutputList(LNode* L) //输出链表。
{
    int element;
    int count=0; //用于计算链表里有多少个元素。
    LNode* p = L->next;
    if (p == NULL)
        printf("链表不存在。n");
    else
    {
        while (p != NULL)
        {
            element = p->data;
            printf("%d ", element);
            p = p->next;
            count++;
        }
        printf("n");
        printf("链表中此时一共有%d个元素。n", count);
    }
}

void UnionList(LinkList &LA, LinkList &LB, LinkList &LC)  //合并单链表LA和LB得到新的单链表LC，LC元素按非减排列。
{
    LinkList pa=LA->next, pb=LB->next, pc;
    LC = pc = LA;//先用LA的头节点作为LC的头节点。
    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;//pc指向LA中的节点。
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        pc->next = pa ? pa : pb;//当pa或pb读完后插入另一个的剩余段。
    }
}

int main()
{
    int La[6] = { 0 };//创建两个数组用于存储LA和LB的元素。
    int Lb[6] = { 0 };
    int e=0;
    LinkList LA,LB,LC;
    Input(La);        //将文件中已经写好的链表元素导入La和Lb的数组中。
    Input(Lb);
    InitList(LA);     //初始化链表。
    InitList(LB);
    InitList(LC);
    CreateList(LA, La, 4);//从La和Lb数组中取元素创建两个具体的链表LA和LB。
    CreateList(LB, Lb, 6);
    if (ListEmpty(LA))    //测试判非空函数是否正常运行
        printf("The List is empty!n");
    else
        printf("The List is not empty!n");
    if (ListInsert(LA, 2, e))   //测试插入元素的函数是否正常运行
    {
        printf("新元素插入链表成功！n");
        OutputList(LA);
    }    
    else
        printf("新元素插入链表失败！n失败原因可能是输入的i值不合法或链表L没有创建！");
    if (ListDelete(LA, 2, e))   //测试删除元素的函数是否正常运行
        printf("删除成功！删除的元素的值为：%dn",e);
    else
        printf("删除失败！n失败原因可能是输入的i值不合法或链表L没有创建！");
    if (GetElem(LA, 2, e))
        printf("取到的元素为%dn", e);
    else
        printf("输入的i值不合法或链表不存在！");
    OutputList(LA);        //测试输出链表的函数是否正常运行。
    OutputList(LB);
    UnionList(LA, LB, LC); //测试将两个链表合并的函数是否正常运行
    OutputList(LC);       
    ClearList(LA);     //测试清空链表的函数是否正常运行
    OutputList(LA);
    return 0;
}

四、总结

单链表实现的难点在于弄清楚指针和传值的关系，其次是定义的结构类型的区分。