一、事先在文件下创建两个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<stdio.h>
#include<stdlib.h>
#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("删除成功！删除的元素的值为：%d\n",e);
else
printf("删除失败！\n失败原因可能是输入的i值不合法或链表L没有创建！");
if (GetElem(LA, 2, e))
printf("取到的元素为%d\n", e);
else
printf("输入的i值不合法或链表不存在！");
OutputList(LA); //测试输出链表的函数是否正常运行。
OutputList(LB);
UnionList(LA, LB, LC); //测试将两个链表合并的函数是否正常运行
OutputList(LC);
ClearList(LA); //测试清空链表的函数是否正常运行
OutputList(LA);
return 0;
}四、总结
单链表实现的难点在于弄清楚指针和传值的关系，其次是定义的结构类型的区分。
版权声明：本文为weixin_52119195原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。