《数据结构（C语言版）》动态单链表的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对该紫皮书第二章线性表中动态单链表的代码实现，函数部分与课本基本相同，并额外补充了一点代码
（貌似专栏把我缩进吃了，懒得加了，建议用visual studio编译）
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, * LinkList;
/*
关于一个带*号一个不带的解释：
typedef struct LNode LNode; //将结构体类型struct LNode重命名为LNode
typedef struct LNode *LinkList; //将struct LNode *重命名为LinkList
LinkList L; //等价于 struct LNode * L
可以理解为，通过typedef，将struct LNode *替换为LinkList,当我们在使用LinkList L定义变量时,
实际上就是在使用 struct LNode * L定义变量。使得以后想定义指向struct LNode类型的指针变量时，
不需要写struct LNode * ,只需要使用LinkList，减少了代码的书写。
*/
/*
重要操作：
p = L; //p指向头结点
s = L->next; //s指向首元结点
p = p->next; //p指向下一结点
*/
Status InitList(LinkList& L);//链表初始化
Status ListInsert_L(LinkList& L, int i, ElemType e);//在第i个位置之前插入元素e
int ListEmpty(LinkList L);//判断链表是否为空
int ListLength_L(LinkList L);//求线性表表长
Status GetElem_L(LinkList L, int i, ElemType& e);//按位查找第i个元素是什么
int LocateElem_L_Value(LinkList L, ElemType e);//按值查找值为e的元素并返回其位置
void Output(LinkList L);//打印线性链表中所有元素
Status ListDelete_L(LinkList& L, int i, ElemType& e);//删除第i个元素并由e返回其值
Status ClearList(LinkList& L);//清空单链表
Status DestoryList_L(LinkList& L);//销毁单链表
void CreatList_H(LinkList& L, int n);//用头插法快速建立链表
void CreatList_R(LinkList& L, int n);//尾插法快速建立链表
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc);//已知单链线性表La和Lb的元素按值递增排列，归并得递增排列的Lc
void Menu()
{
printf("***************************\n");
printf("********开 始 菜 单********\n");
printf("********0：退出系统********\n");
printf("********1：插入元素********\n");
printf("********2：判断空表********\n");
printf("********3：计算表长********\n");
printf("********4：按位查找********\n");
printf("********5：按值查找********\n");
printf("********6：打印表单********\n");
printf("********7：删除元素********\n");
printf("********8：清空链表********\n");
printf("********9：销毁链表********\n");
printf("********10：头插法*********\n");
printf("********11：尾插法*********\n");
printf("********12：合并表*********\n");
printf("********13：清 屏*********\n");
printf("***************************\n");
}
int main()
{
int input = 0;
int ret = 0;
int value = 0;
int position = 0;
int Length = 0;
int num = 0;
LinkList head;
InitList(head);
do
{
Menu();
printf("请输入你想使用的功能：");
scanf("%d", &input);
switch (input)
{
case 1:
printf("请输入你想插入的元素：");
scanf("%d", &value);
printf("请输入你想插入的位置：");
scanf("%d", &position);
ret = ListInsert_L(head, position, value);
if (!ret)
{
printf("插入失败，请重试\n");
}
else
{
printf("插入成功！\n");
}
break;
case 2:
if (ListEmpty(head))
{
printf("该链表为空表\n");
}
else
{
printf("该链表不是空表\n");
}
break;
case 3:
Length = ListLength_L(head);
printf("该链表的长度为：%d\n", Length);
break;
case 4:
printf("请输入你想查找的位置：");
scanf("%d", &position);
if (GetElem_L(head, position, value))
{
printf("第%d位的元素为%d\n", position, value);
}
else
{
printf("您输入的位置不合法\n");
}
break;
case 5:
printf("请输入你想查找的值：");
scanf("%d", &value);
position = LocateElem_L_Value(head, value);
if (position)
{
printf("你想查找的元素%d第一次出现在第%d位\n", value, position);
}
else
{
printf("未找到\n");
}
break;
case 6:
Output(head);
break;
case 7:
printf("请输入你想删除的位置：");
scanf("%d", &position);
if (ListDelete_L(head, position, value))
{
printf("你成功删除了第%d个元素%d\n", position, value);
}
else
{
printf("删除失败，请重试\n");
}
break;
case 8:
if (ClearList(head))
{
printf("清空链表成功\n");
}
else
{
printf("清空失败，请重试\n");
}
break;
case 9:
printf("您真的要销毁链表吗？\n1：确认\t0：取消\n");
scanf("%d", &ret);
if (ret == 1)
{
if (DestoryList_L(head))
{
printf("销毁成功\n");
}
else
{
printf("销毁失败\n");
}
}
else
{
printf("取消销毁\n");
}
break;
case 10:
//此时使用头插法会清空之前插入的链表
printf("请输入你想插入的元素个数：");
scanf("%d", &num);
CreatList_H(head, num);
printf("插入成功\n");
break;
case 11:
//此时使用尾插法会清空之前插入的链表
printf("请输入你想插入的元素个数：");
scanf("%d", &num);
CreatList_R(head, num);
printf("插入成功\n");
break;
case 12:
printf("使用尾插法建立两个递增链表:\n");
printf("请输入你想新建的链表1元素个数：");
scanf("%d", &num);
LinkList head1;
InitList(head1);
CreatList_R(head1, num);
printf("请输入你想新建的链表2的元素个数：");
scanf("%d", &num);
LinkList head2;
InitList(head2);
CreatList_R(head2, num);
LinkList head3;
InitList(head3);
MergeList_L(head1, head2, head3);
printf("合并后的链表：");
Output(head3);
break;
case 13:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误，请重新输入\n");
break;
}
} while (1);
return 0;
}
Status InitList(LinkList& L)//链表初始化
{
L = (LinkList)malloc(sizeof(LNode));
if (!L)
{
exit(OVERFLOW);
}
L->next = NULL;
return OK;
}
Status ListInsert_L(LinkList& L, int i, ElemType e)//在第i个位置之前插入元素e
{
LinkList p = L;
int j = 0;
while (p && j < i - 1)//注意是i-1,因为要找被插入元素的前一个元素
{
p = p->next;
j++;
}
if (!p || j > i - 1)
{
return ERROR;
}
LinkList s = (LinkList)malloc(sizeof(LNode));
if (!s)
{
exit(OVERFLOW);
}
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
int ListEmpty(LinkList L)//判断链表是否为空
//空表：头指针和头结点仍然存在，但头结点指向NULL
{
if (L->next)
{
return 0;
}
else
{
return 1;
}
}
int ListLength_L(LinkList L)//求线性表表长
{
LNode* p;
p = L->next;
int i = 0;
while (p)
{
i++;
p = p->next;
}
return i;
}
Status GetElem_L(LinkList L, int i, ElemType& e)//查找第i个元素是什么
{
LinkList p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i)
{
return ERROR;//表示第i个元素不存在
}
e = p->data;
return OK;
}
int LocateElem_L_Value(LinkList L, ElemType e)//按值查找值为e的元素并返回其位置
//查找失败返回NULL
{
LNode* p = L->next;
int j = 1;
while (p && p->data != e)
{
p = p->next;
j++;
}
if (p)
{
return j;
}
else
{
return 0;
}
}
void Output(LinkList L)//打印线性链表中所有元素
{
if (L->next == NULL)
{
printf("该链表为空表\n");
return;
}
LNode* p = L->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
Status ListDelete_L(LinkList& L, int i, ElemType& e)//删除第i个元素并由e返回其值
{
LinkList p = L;
int j = 0;
while (p->next && j < i - 1)//注意删除是p->next，插入是p
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)
{
return ERROR;
}
LinkList q = p->next;//注意删除要先定义一个指针记录被删除的元素，再把指针free掉
p->next = q->next;
e = q->data;//用e来保存被删除的元素
free(q);
return OK;
}
Status ClearList(LinkList& L)//清空单链表
//清空保留头指针、头结点
{
LNode* p, * q;
p = L->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}
Status DestoryList_L(LinkList& L)//销毁单链表
//销毁包括头指针、头结点
{
LNode* p;
while (L)
{
p = L;
L = L->next;
free(p);
}
return OK;
}
void CreatList_H(LinkList& L, int n)//用头插法快速建立链表
{
L = (LinkList)malloc(sizeof(LNode));
if (!L)
{
exit(OVERFLOW);
}
L->next = NULL;
for (int i = n; i > 0; i--)//倒序插入
{
LNode* p = (LinkList)malloc(sizeof(LNode));
if (!p)
{
exit(OVERFLOW);
}
scanf("%d", &p->data);
p->next = L->next;
L->next = p;
}
}
void CreatList_R(LinkList& L, int n)//尾插法快速建立链表
{
L = (LinkList)malloc(sizeof(LNode));
if (!L)
{
exit(OVERFLOW);
}
L->next = NULL;
LNode* r = L;//尾指针
for (int i = 0; i < n; i++)
{
LNode* p = (LinkList)malloc(sizeof(LNode));
if (!p)
{
exit(OVERFLOW);
}
p->next = NULL;
scanf("%d", &p->data);
r->next = p;//插入到表尾
r = p;//尾指针指向新的尾结点
}
}
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc)//已知单链线性表La和Lb的元素按值递增排列，归并得递增排列的Lc
{
LNode* pa = La->next;
LNode* pb = Lb->next;
LNode* pc = La;
Lc = pc;
while (pa && pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;//指针后移
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
free(Lb);
}
