【数据结构】链表

本文收录自【C语言数据结构】思想＋代码集】
文章目录
- 【数据结构】链表

【数据结构】链表

思想

二维指针作为函数参数的作用:

在函数外部定义一个指针p
在函数内给指针赋值
函数结束后对指针p生效，那么我们就需要二级指针。

初始化（头节点要改变）

Status InitList(LinkList* L);
L指针——>分配的第一个元素的内存空间
L的下一个指针——>下一个元素的指针

销毁（头节点要改变）

Status DestroyList(LinkList* L)
创建一个新的节点负责之后分别遍历指向L
从第一个元素开始free，然后把新的指针指向下一个一直循环直到新的指针是空指针结束
最后把第一个节点指向NULL

置空（头节点值为NULL）

Status ClearList(LinkList L)
创建两个指针首先一个负责遍历的指向每个节点防止后面free的时候把此节点的next清除，其次另外一个由第一个提供
最后把第一个节点的next指向NULL

判空

Status ListEmpty(LinkList L)
链表只有头结点时，L != NULL && L->next == NULL，认为该链表为空

计数

int ListLength(LinkList L)
初始化一个指针指向头节点，循环直到指向最后一个
循环内部有个计数变量

取值（获取链表中第i个元素，将其存储到e中。）

寻找第i-1个结点，且保证该结点的后继不为NULL
如果遍历到头了，或者i的值不合规(比如i<=0)，说明没找到合乎目标的结点
判断遍历到头的方法：p->next == NULL
j值：在遍历查找第i个的时候，循环判断条件j < i - 1 j在循环内部自增，保证没有不合规的
如果不合规，即j > i - 1

查找（返回链表中首个与e满足Compare关系的元素位序，元素e是Compare函数第二个形参）

int LocateElem(LinkList L, ElemType e, Status(Compare)(ElemType, ElemType))链表 | e | compare函数关系
循环遍历，判断条件p != NULL && !Compare(p->data, e)，i记录次数

前驱（取元素cur_e的前驱pre，如果存在，将其存储到pre_e中，返回OK）

Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e)
首先判断是否有前驱，pre->data == cur_e就没有
定义一个指针next指向pre，定义另外个指针指向pre的下一个
然后从第二个开始循环遍历找cur_e，循环时next赋值给pre，然后自增到下一个
找到的cur时next.data，所以pre就是前驱
存储*pre_e = pre->data

后继（获取元素cur_e的后继，如果存在，将其存储到next_e中，返回OK）

Status NextElem(LinkList L, ElemType cur_e, ElemType* next_e)
循环判断条件：pre->next != NULL && pre->data != cur_e
循环内pre自增
找到了过后返回*next_e = pre->next->data;

插入（向链表第i个位置上插入e，插入成功则返回OK，否则返回ERROR）

Status ListInsert(LinkList L, int i, ElemType e)
找到第i个节点：定义一个指针p循环遍历i-1次自增，j值：在遍历查找第i个的时候，循环判断条件j < i - 1 j在循环内部自增，保证没有不合规的。如果不合规，即j > i - 1
生成新节点：定义一个新的指针s，指向malloc后的节点。s.data=e
旧节点——>新节点——>下一个：s->next = p->next(新节点的下一个就是旧节点的下一个); p->next = s;（旧节点的下一个就是s）

删除（删除链表第i个位置上的元素，并将被删除元素存储到e中。删除成功则返回OK，否则返回ERROR。）

Status ListDelete(LinkList L, int i, ElemType* e)（这个时候取e的指针是因为要改变e的值了）
寻找节点，自增，计数防止错误（同上）
节点1——>要删除的节点——>节点2 ：节点1的next指向节点2，e的值为要删除的节点的值，并释放要删除的节点

遍历（用visit函数访问链表L）

void ListTraverse(LinkList L, void(Visit)(ElemType))
循环调用visit（p.data），p自增，循环条件：p到最后不是NULL

头插法创建链表（数据来源于terminal或者文件）

Status CreateList_Head(LinkList* L, int n, char* path)（path是定义的FILE不用管）
创建第一个头节点，p指向这个malloc后的节点，然后存数据进p.data，ReadData(fp, “%d”, &(p->data));见后文
先配置p的下一个是L的下一个p.next=（*L）.next，然后再把配置好的p赋值给*L，之后循环创建新节点

尾插法创建链表

Status CreateList_Tail(LinkList* L, int n, char* path)
定义指向*L的指针q，循环：生成新节点，配置q的下一个就是新节点，配置完了q自增，继续循环。
最后因为q没有指向，所以q指向NULL

代码

链表头文件 LinkList.h

/*===============================
 * 线性表的链式存储结构（链表）
 *
 * 包含算法: 2.8、2.9、2.10、2.11
 ================================*/

#ifndef LINKLIST_H
#define LINKLIST_H

#include <stdio.h>
#include <stdlib.h>     // 提供 malloc、realloc、free、exit 原型
#include <string.h>     // 提供 strstr 原型
#include "Status.h"     //**▲01 绪论**//

/* 单链表元素类型定义 */
typedef int ElemType;

/*
 * 单链表结构
 *
 * 注：这里的单链表存在头结点
 */
typedef struct LNode {
    ElemType data;      // 数据结点
    struct LNode* next; // 指向下一个结点的指针
} LNode;

// 指向单链表结点的指针
typedef LNode* LinkList;


/*
 * 初始化
 *
 * 初始化成功则返回OK，否则返回ERROR。
 */
Status InitList(LinkList* L);

/*
 * 销毁(结构)
 *
 * 释放链表所占内存。
 */
Status DestroyList(LinkList* L);

/*
 * 置空(内容)
 *
 * 这里需要释放链表中非头结点处的空间。
 */
Status ClearList(LinkList L);

/*
 * 判空
 *
 * 判断链表中是否包含有效数据。
 *
 * 返回值：
 * TRUE : 链表为空
 * FALSE: 链表不为空
 */
Status ListEmpty(LinkList L);

/*
 * 计数
 *
 * 返回链表包含的有效元素的数量。
 */
int ListLength(LinkList L);

/*
 * ████████ 算法2.8 ████████
 *
 * 取值
 *
 * 获取链表中第i个元素，将其存储到e中。
 * 如果可以找到，返回OK，否则，返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数，但这不符合编码的通用约定。
 * 通常，i的含义应该指索引，即从0开始计数。
 */
Status GetElem(LinkList L, int i, ElemType* e);

/*
 * 查找
 *
 * 返回链表中首个与e满足Compare关系的元素位序。
 * 如果不存在这样的元素，则返回0。
 *
 *【备注】
 * 元素e是Compare函数第二个形参
 */
int LocateElem(LinkList L, ElemType e, Status(Compare)(ElemType, ElemType));

/*
 * 前驱
 *
 * 获取元素cur_e的前驱，
 * 如果存在，将其存储到pre_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e);

/*
 * 后继
 *
 * 获取元素cur_e的后继，
 * 如果存在，将其存储到next_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status NextElem(LinkList L, ElemType cur_e, ElemType* next_e);

/*
 * ████████ 算法2.9 ████████
 *
 * 插入
 *
 * 向链表第i个位置上插入e，插入成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListInsert(LinkList L, int i, ElemType e);

/*
 * ████████ 算法2.10 ████████
 *
 * 删除
 *
 * 删除链表第i个位置上的元素，并将被删除元素存储到e中。
 * 删除成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListDelete(LinkList L, int i, ElemType* e);

/*
 * 遍历
 *
 * 用visit函数访问链表L
 */
void ListTraverse(LinkList L, void(Visit)(ElemType));

/*
 * ████████ 算法2.11 ████████
 *
 * 头插法创建链表
 *
 *
 *【备注】
 *
 * 教材中默认从控制台读取数据。
 * 这里为了方便测试，避免每次运行都手动输入数据，
 * 因而允许选择从预设的文件path中读取测试数据。
 *
 * 如果需要从控制台读取数据，则path为NULL或者为空串，
 * 如果需要从文件中读取数据，则需要在path中填写文件名信息。
 */
Status CreateList_Head(LinkList* L, int n, char* path);

/*
 * 尾插法创建链表
 *
 *
 *【备注】
 *
 * 教材中默认从控制台读取数据。
 * 这里为了方便测试，避免每次运行都手动输入数据，
 * 因而允许选择从预设的文件path中读取测试数据。
 *
 * 如果需要从控制台读取数据，则path为NULL或者为空串，
 * 如果需要从文件中读取数据，则需要在path中填写文件名信息。
 */
Status CreateList_Tail(LinkList* L, int n, char* path);

#endif

链表操作函数文件 LinkList.cpp

/*===============================
 * 线性表的链式存储结构（链表）
 *
 * 包含算法: 2.8、2.9、2.10、2.11
 ================================*/

#include "LinkList.h" //**▲02 线性表**//

/*
 * 初始化
 *
 * 只是初始化一个头结点。
 * 初始化成功则返回OK，否则返回ERROR。
 */
Status InitList(LinkList* L) {
    (*L) = (LinkList) malloc(sizeof(LNode));
    if(*L == NULL) {
        exit(OVERFLOW);
    }
    
    (*L)->next = NULL;
    
    return OK;
}

/*
 * 销毁(结构)
 *
 * 释放链表所占内存，头结点也会被清理。
 */
Status DestroyList(LinkList* L) {
    LinkList p;
    
    // 确保链表结构存在
    if(L == NULL || *L == NULL) {
        return ERROR;
    }
    
    p = *L;
    
    while(p != NULL) {
        p = (*L)->next;
        free(*L);
        (*L) = p;
    }
    
    *L = NULL;
    
    return OK;
}

/*
 * 置空(内容)
 *
 * 这里需要释放链表中非头结点处的空间。
 */
Status ClearList(LinkList L) {
    LinkList pre, p;
    
    // 确保链表存在
    if(L == NULL) {
        return ERROR;
    }
    
    p = L->next;
    
    // 释放链表上所有结点所占内存
    while(p != NULL) {
        pre = p;
        p = p->next;
        free(pre);
    }
    
    L->next = NULL;
    
    return OK;
}

/*
 * 判空
 *
 * 判断链表中是否包含有效数据。
 *
 * 返回值：
 * TRUE : 链表为空
 * FALSE: 链表不为空
 */
Status ListEmpty(LinkList L) {
    // 链表只有头结点时，认为该链表为空
    if(L != NULL && L->next == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/*
 * 计数
 *
 * 返回链表包含的有效元素的数量。
 */
int ListLength(LinkList L) {
    LinkList p;
    int i;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return 0;
    }
    
    i = 0;
    p = L->next;
    
    // 遍历所有结点
    while(p != NULL) {
        i++;
        p = p->next;
    }
    
    return i;
}

/*
 * ████████ 算法2.8 ████████
 *
 * 取值
 *
 * 获取链表中第i个元素，将其存储到e中。
 * 如果可以找到，返回OK，否则，返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数，但这不符合编码的通用约定。
 * 通常，i的含义应该指索引，即从0开始计数。
 */
Status GetElem(LinkList L, int i, ElemType* e) {
    LinkList p;
    int j;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return ERROR;
    }
    
    p = L;
    j = 0;
    
    // 寻找第i-1个结点，且保证该结点的后继不为NULL
    while(p->next != NULL && j < i - 1) {
        p = p->next;
        ++j;
    }
    
    // 如果遍历到头了，或者i的值不合规(比如i<=0)，说明没找到合乎目标的结点
    if(p->next == NULL || j > i - 1) {
        return ERROR;
    }
    
    *e = p->next->data;
    
    return OK;
}

/*
 * 查找
 *
 * 返回链表中首个与e满足Compare关系的元素位序。
 * 如果不存在这样的元素，则返回0。
 *
 *【备注】
 * 元素e是Compare函数第二个形参
 */
int LocateElem(LinkList L, ElemType e, Status(Compare)(ElemType, ElemType)) {
    int i;
    LinkList p;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return 0;
    }
    
    i = 1;          // i的初值为第1个元素的位序
    p = L->next;    // p的初值为第1个元素的指针
    
    while(p != NULL && !Compare(p->data, e)) {
        i++;
        p = p->next;
    }
    
    if(p != NULL) {
        return i;
    } else {
        return 0;
    }
}

/*
 * 前驱
 *
 * 获取元素cur_e的前驱，
 * 如果存在，将其存储到pre_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e) {
    LinkList pre, next;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return ERROR;
    }
    
    // 指向第1个元素
    pre = L->next;
    
    // 第1个元素没有前驱
    if(pre->data == cur_e) {
        return ERROR;
    }
    
    // 指向第2个元素
    next = pre->next;
    
    // 从第2个元素开始，查找cur_e的位置
    while(next != NULL && next->data != cur_e) {
        pre = next;
        next = next->next;
    }
    
    // 如果没找到元素cur_e，查找失败，返回ERROR
    if(next == NULL) {
        return ERROR;
    }
    
    *pre_e = pre->data;
    
    return OK;
}

/*
 * 后继
 *
 * 获取元素cur_e的后继，
 * 如果存在，将其存储到next_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status NextElem(LinkList L, ElemType cur_e, ElemType* next_e) {
    LinkList pre;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return ERROR;
    }
    
    // 指向第1个元素
    pre = L->next;
    
    // 从第1个元素开始，查找cur_e的位置，且保证该结点的后继不为NULL
    while(pre->next != NULL && pre->data != cur_e) {
        pre = pre->next;
    }
    
    // 如果没找到cur_e，或者找到了，但它没有后继，均返回ERROR
    if(pre->next == NULL) {
        return ERROR;
    }
    
    *next_e = pre->next->data;
    
    return OK;
}

/*
 * ████████ 算法2.9 ████████
 *
 * 插入
 *
 * 向链表第i个位置上插入e，插入成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListInsert(LinkList L, int i, ElemType e) {
    LinkList p, s;
    int j;
    
    // 确保链表存
    if(L == NULL) {
        return ERROR;
    }
    
    p = L;
    j = 0;
    
    // 寻找第i-1个结点，且保证该结点本身不为NULL
    while(p != NULL && j < i - 1) {
        p = p->next;
        ++j;
    }
    
    // 如果遍历到头了，或者i的值不合规(比如i<=0)，说明没找到合乎目标的结点
    if(p == NULL || j > i - 1) {
        return ERROR;
    }
    
    // 生成新结点
    s = (LinkList) malloc(sizeof(LNode));
    if(s == NULL) {
        exit(OVERFLOW);
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    
    return OK;
}

/*
 * ████████ 算法2.10 ████████
 *
 * 删除
 *
 * 删除链表第i个位置上的元素，并将被删除元素存储到e中。
 * 删除成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListDelete(LinkList L, int i, ElemType* e) {
    LinkList p, q;
    int j;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return ERROR;
    }
    
    p = L;
    j = 0;
    
    // 寻找第i-1个结点，且保证该结点的后继不为NULL
    while(p->next != NULL && j < i - 1) {
        p = p->next;
        ++j;
    }
    
    // 如果遍历到头了，或者i的值不合规(比如i<=0)，说明没找到合乎目标的结点
    if(p->next == NULL || j > i - 1) {
        return ERROR;
    }
    
    // 删除第i个结点
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    
    return OK;
}

/*
 * 遍历
 *
 * 用visit函数访问链表L
 */
void ListTraverse(LinkList L, void(Visit)(ElemType)) {
    LinkList p;
    
    // 确保链表存在且不为空表
    if(L == NULL || L->next == NULL) {
        return;
    }
    
    p = L->next;
    
    while(p != NULL) {
        Visit(p->data);
        p = p->next;
    }
    
    printf("
");
}

/*
 * ████████ 算法2.11 ████████
 *
 * 头插法创建链表
 *
 *
 *【备注】
 *
 * 教材中默认从控制台读取数据。
 * 这里为了方便测试，避免每次运行都手动输入数据，
 * 因而允许选择从预设的文件path中读取测试数据。
 *
 * 如果需要从控制台读取数据，则path为NULL或者为空串，
 * 如果需要从文件中读取数据，则需要在path中填写文件名信息。
 */
Status CreateList_Head(LinkList* L, int n, char* path) {
    int i;
    LinkList p;
    FILE* fp;
    int readFromConsole;    // 是否从控制台读取数据

    // 如果没有文件路径信息，则从控制台读取输入
    readFromConsole = path == NULL || strcmp(path, "") == 0;

    if(readFromConsole) {
        // 建立头结点
        *L = (LinkList) malloc(sizeof(LNode));
        (*L)->next = NULL;

        printf("请输入%d个降序元素：", n);

        for(i = 1; i <= n; ++i) {
            // 生成新结点
            p = (LinkList) malloc(sizeof(LNode));

            // 填充数据，并插入到链表中
            scanf("%d", &(p->data));

            p->next = (*L)->next;
            (*L)->next = p;
        }
    } else {
        // 打开文件，准备读取测试数据
        fp = fopen(path, "r");
        if(fp == NULL) {
            return ERROR;
        }

        // 建立头结点
        *L = (LinkList) malloc(sizeof(LNode));
        (*L)->next = NULL;

        for(i = 1; i <= n; ++i) {
            // 生成新结点
            p = (LinkList) malloc(sizeof(LNode));

            // 填充数据，并插入到链表中
            ReadData(fp, "%d", &(p->data));

            p->next = (*L)->next;
            (*L)->next = p;
        }

        fclose(fp);
    }

    return OK;
}

/*
 * 尾插法创建链表
 *
 *
 *【备注】
 *
 * 教材中默认从控制台读取数据。
 * 这里为了方便测试，避免每次运行都手动输入数据，
 * 因而允许选择从预设的文件path中读取测试数据。
 *
 * 如果需要从控制台读取数据，则path为NULL或者为空串，
 * 如果需要从文件中读取数据，则需要在path中填写文件名信息。
 */
Status CreateList_Tail(LinkList* L, int n, char* path) {
    int i;
    LinkList p, q;
    FILE* fp;
    int readFromConsole;    // 是否从控制台读取数据

    // 如果没有文件路径信息，则从控制台读取输入
    readFromConsole = path == NULL || strcmp(path, "") == 0;

    if(readFromConsole) {
        // 建立头结点
        *L = (LinkList) malloc(sizeof(LNode));
        (*L)->next = NULL;

        printf("请输入%d个升序元素：", n);

        for(i = 1, q = *L; i <= n; ++i) {
            // 生成新结点
            p = (LinkList) malloc(sizeof(LNode));

            // 填充数据，并插入到链表中
            scanf("%d", &(p->data));

            q->next = p;
            q = q->next;
        }

        q->next = NULL;
    } else {
        // 打开文件，准备读取测试数据
        fp = fopen(path, "r");
        if(fp == NULL) {
            return ERROR;
        }

        // 建立头结点
        *L = (LinkList) malloc(sizeof(LNode));
        (*L)->next = NULL;

        for(i = 1, q = *L; i <= n; ++i) {
            // 生成新结点
            p = (LinkList) malloc(sizeof(LNode));

            // 填充数据，并插入到链表中
            ReadData(fp, "%d", &(p->data));

            q->next = p;
            q = q->next;
        }

        q->next = NULL;

        fclose(fp);
    }

    return OK;
}

链表主文件 LinkList-main.cpp

#include <stdio.h>
#include "Status.h"
#include "LinkList.h"                        //**▲02 线性表**//

// 判断data>e是否成立
Status CmpGreater(ElemType data, ElemType e) {
    return data > e ? TRUE : FALSE;
}

// 测试函数，打印元素
void PrintElem(ElemType e) {
    printf("%d ", e);
}


int main(int argc, char** argv) {
    LinkList L;
    int i;
    ElemType e;
    
    printf("████████ InitList 
");
    {
        printf("█ 初始化单链表 L ...
");
        InitList(&L);
    }
    PressEnterToContinue();
    
    
    printf("████████ ListEmpty 
");
    {
        ListEmpty(L) ? printf("█ L 为空！！
") : printf("█ L 不为空！
");
    }
    PressEnterToContinue();
    
    
    printf("████████ ListInsert 
");
    {
        for(i = 1; i <= 8; i++) {
            printf("█ 在 L 第 %d 个位置插入 "%d" ...
", i, 2 * i);
            ListInsert(L, i, 2 * i);
        }
    }
    PressEnterToContinue();
    
    
    printf("████████ ListTraverse 
");
    {
        printf("█ L 中的元素为：L = ");
        ListTraverse(L, PrintElem);
    }
    PressEnterToContinue();
    
    
    printf("████████ ListLength 
");
    {
        printf("█ L 的长度为 %d 
", ListLength(L));
    }
    PressEnterToContinue();
    
    
    printf("████████ ListDelete 
");
    {
        printf("█ 删除前的元素：L = ");
        ListTraverse(L, PrintElem);
    
        printf("█ 尝试删除 L 中第 6 个元素...
");
    
        if(ListDelete(L, 6, &e) == OK) {
            printf("█ 删除成功，被删除元素是："%d"
", e);
        } else {
            printf("█ 删除失败，第 6 个元素不存在！
");
        }
    
        printf("█ 删除后的元素：L = ");
        ListTraverse(L, PrintElem);
    }
    PressEnterToContinue();
    
    
    printf("████████ GetElem 
");
    {
        GetElem(L, 4, &e);
        printf("█ L 中第 4 个位置的元素为 "%d" 
", e);
    }
    PressEnterToContinue();
    
    
    printf("████████ LocateElem 
");
    {
        i = LocateElem(L, 7, CmpGreater);
        GetElem(L, i, &e);
        printf("█ L 中第一个元素值大于 "7" 的元素是 "%d" 
", e);
    }
    PressEnterToContinue();
    
    
    printf("████████ PriorElem 
");
    {
        ElemType cur_e = 6;
    
        if(PriorElem(L, cur_e, &e) == OK) {
            printf("█ 元素 "%d" 的前驱为 "%d" 
", cur_e, e);
        } else {
            printf("█ 元素 "%d" 的前驱不存在！
", cur_e);
        }
    }
    PressEnterToContinue();
    
    
    printf("████████ NextElem 
");
    {
        ElemType cur_e = 6;
    
        if(NextElem(L, cur_e, &e) == OK) {
            printf("█ 元素 "%d" 的后继为 "%d" 
", cur_e, e);
        } else {
            printf("█ 元素 "%d" 的后继不存在！
", cur_e);
        }
    }
    PressEnterToContinue();
    
    
    printf("████████ ClearList 
");
    {
        printf("█ 清空 L 前：");
        ListEmpty(L) ? printf(" L 为空！！
") : printf(" L 不为空！
");
        
        ClearList(L);
        
        printf("█ 清空 L 后：");
        ListEmpty(L) ? printf(" L 为空！！
") : printf(" L 不为空！
");
    }
    PressEnterToContinue();
    
    
    printf("████████ DestroyList 
");
    {
        printf("█ 销毁 L 前：");
        L ? printf(" L 存在！
") : printf(" L 不存在！！
");
        
        DestroyList(&L);
        
        printf("█ 销毁 L 后：");
        L ? printf(" L 存在！
") : printf(" L 不存在！！
");
    }
    PressEnterToContinue();
    
    
    printf("████████ CreateList_Head 
");
    {
        LinkList L;
        CreateList_Head(&L, 5, "TestData_Head.txt");
        printf("█ 头插法建立单链表 L = ");
        ListTraverse(L, PrintElem);
    }
    PressEnterToContinue();
    
    
    printf("████████ CreateList_Tail 
");
    {
        LinkList L;
        CreateList_Tail(&L, 5, "TestData_Tail.txt");
        printf("█ 尾插法建立单链表 L = ");
        ListTraverse(L, PrintElem);
    }
    PressEnterToContinue();
    
    return 0;
}

测试文件 TestData_Head.txt 和 TestData_Tail.txt

注意：LinkList.cpp文件操作这一段，可以直接忽略除了数字的其他类型

// 填充数据，并插入到链表中    
ReadData(fp, "%d", &(p->data));

文件数据导入函数 ReadData()的思想（后续修改）

///fscanf()读取出来的都是字符串，因此不能直接给int类型，不然数据就出现不是你写入txt//中的数据，要把字符串变成数字才行，一下就是数字字符串变成数字atoi（）
//用法如下：a="4560"
//int b=atoi(a)
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
int read(int arr[])
{
       int i=0,n;
       char name[100];
       FILE *fp;//定义文件指针
       if((fp=fopen("data.txt","r"))==NULL)//如果文件名不存在
       {printf("cantfind the file!");}//则输出没有找到文件
       while(!feof(fp))//判断文件是否结束
       {  
              fscanf(fp,"%s",name);//逐个将文件中的数据放入字符串中
              arr[i++]=atoi(name);//把字符串转变成数字（int）类型
              printf("%d
",arr[i-1]);
       }
       n=i;//n为数组中数据个数
       fclose(fp);//关闭文件
       return n;//返回n即数据个数的值
}

【数据结构】链表

文章目录

【数据结构】链表

思想

初始化 （头节点要改变）

销毁（头节点要改变）

置空（头节点值为NULL）

判空

计数

取值（获取链表中第i个元素，将其存储到e中。）

查找（返回链表中首个与e满足Compare关系的元素位序，元素e是Compare函数第二个形参）

前驱（取元素cur_e的前驱pre，如果存在，将其存储到pre_e中，返回OK）

后继（获取元素cur_e的后继，如果存在，将其存储到next_e中，返回OK）

插入（向链表第i个位置上插入e，插入成功则返回OK，否则返回ERROR）

删除（删除链表第i个位置上的元素，并将被删除元素存储到e中。删除成功则返回OK，否则返回ERROR。）

遍历（用visit函数访问链表L）

头插法创建链表（数据来源于terminal或者文件）

尾插法创建链表

代码

链表头文件 LinkList.h

链表操作函数文件 LinkList.cpp

链表主文件 LinkList-main.cpp

测试文件 TestData_Head.txt 和 TestData_Tail.txt

文件数据导入函数 ReadData()的思想（后续修改）

初始化（头节点要改变）