本文最后更新于166 天前，其中的信息可能已经过时，如有错误请发送邮件到nullaura@outlook.com
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <limits.h> // INT_MAX等
#include <stdio.h> // NULL等
#include <stdlib.h> // atoi( ), exit( )
#include <math.h> // floor( ), ceil( ), abs( ), OVERFLOW宏定义，其值为3。
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW 3
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
//单链表的初始化
Status InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L
L = (LinkList)malloc(sizeof(LNode));
if (!L)
return ERROR;
L->next = NULL;
return OK;
}
//单链表的销毁
Status DestroyList(LinkList &L)
{ // 初始条件：线性表L已存在。
// 操作结果：销毁线性表L
LinkList p, q;
p = L->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
free(L);
L = NULL;
return OK;
}
//单链表的清空
void ClearList(LinkList L) // 不改变L
{ // 初始条件：线性表L已存在。
// 操作结果：将L重置为空表
LinkList p, q;
p = L->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
}
//单链表的判空
Status ListEmpty(LinkList L)
{ // 初始条件：线性表L已存在。
// 操作结果：若L为空表，则返回TRUE，否则返回FALSE
return L->next == NULL ? TRUE : FALSE;
}
//求单链表长度
int ListLength(LinkList L)
{ // 初始条件：线性表L已存在。
// 操作结果：返回L中数据元素个数
int len = 0;
LinkList p = L->next;
while (p)
{
len++;
p = p->next;
}
return len;
}
//头插法建立单链表
void CreateList_HeadInsert(LinkList &L, int n)
{ // 初始条件：线性表L已存在。
// 操作结果：逆位序输入n个元素的值，建立带表头结构的单链线性表L
LinkList p, q;
int e;
for (int i = 0; i < n; i++)
{
scanf("%d", &e);
p = (LinkList)malloc(sizeof(LNode));
p->data = e;
p->next = L->next;
L->next = p;
}
}
//尾插法建立单链表
void CreateList_TailInsert(LinkList &L, int n)
{ // 初始条件：线性表L已存在。
// 操作结果：正位序输入n个元素的值，建立带表头结构的单链线性表L
LinkList p, q;
int e;
for (int i = 0; i < n; i++)
{
scanf("%d", &e);
p = (LinkList)malloc(sizeof(LNode));
p->data = e;
p->next = NULL;
if (L->next == NULL)
{
L->next = p;
}
else
{
q = L;
while (q->next)
{
q = q->next;
}
q->next = p;
}
}
}
//单链表中按序号查找数据元素
Status GetElem(LinkList L, int i, ElemType &e)
{ // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
LinkList p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
e = p->data;
return OK;
}
//单链表中按值查找数据元素的位序
int LocateElem(LinkList L, ElemType e)
{ // 返回L中第1个值为e 的数据元素的位序，若这样的数据元素不存在,则返回值为0
LinkList p = L->next;
int i = 1;
while (p)
{
if (p->data == e)
return i;
p = p->next;
i++;
}
return 0;
}
//查找直接前驱
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{ // 初始条件: 线性表L已存在
// 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
// 返回OK；否则操作失败，pre_e无定义，返回ERROR
LinkList p = L;
LinkList q = L->next;
while (q != NULL && q->data != cur_e)
{
p = q;
q = q->next;
}
if (q == NULL)
return ERROR;
if (p == L)
return ERROR;
pre_e = p->data;
return OK;
}
//插入节点
Status ListInsert(LinkList L, int i, ElemType e)
{ // 在带头结点的单链线性表L中第i个位置之前插入元素e
LinkList p = L;
int j = 0;
while (p && j < i - 1)
{
p = p->next;
j++;
}
if (!p || j > i - 1)
return ERROR;
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
//删除结点
Status ListDelete(LinkList L, int i, ElemType &e)
{ // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
LinkList p = L;
int j = 0;
while (p->next && j < i - 1)
{
p = p->next;
j++;
}
if (!p->next || j > i - 1)
return ERROR;
LinkList q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
//单链表数据元素的输出
Status visit(LinkList L)
{ // 按序输出单链表的各个元素值
LinkList p = L->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
int main()
{
int n = 5;
int index; // 位序
Status s; // 状态返回值
ElemType cur_e;
ElemType pre_e;
int value, delvalue;
LinkList La, Lb;
InitList(La);
InitList(Lb);
printf("头插法建立单链表,请输入5个数据：");
CreateList_HeadInsert(La, n);
printf("链表的长度为%d\n", ListLength(La));
printf("链表的内容为：");
visit(La);
// 按位置查找
printf("输入待查找元素位置：");
scanf("%d", &index);
s = GetElem(La, index, cur_e);
if (s == OK)
printf("第%d个元素的值为:%d\n", index, cur_e);
else
printf("不存在第%d个元素！\n", index);
// 找前驱
printf("输入待查找前驱的数据元素值：");
scanf("%d", &cur_e);
s = PriorElem(La, cur_e, pre_e);
if (s == OK)
printf("数据元素%d的前驱为:%d\n", cur_e, pre_e);
else
printf("数据元素%d的前驱不存在！\n", cur_e);
// 按值查找
printf("输入待查找元素的值：");
scanf("%d", &cur_e);
index = LocateElem(La, cur_e);
printf("值为%d的元素在链表中的位置是%d\n", cur_e, index);
// 清空链表
s = ListEmpty(La);
if (s == TRUE)
printf("该链表为空，该链表的长度为%d\n", ListLength(La));
else
printf("该链表非空，该链表的长度为%d\n", ListLength(La));
printf("清空链表\n");
ClearList(La);
s = ListEmpty(La);
if (s == TRUE)
printf("该链表为空，该链表的长度为%d\n", ListLength(La));
else
printf("该链表非空，该链表的长度为%d\n", ListLength(La));
printf("\n");
printf("尾插法建立单链表,请输入5个数据：");
CreateList_TailInsert(Lb, n);
printf("链表的长度为%d\n", ListLength(Lb));
printf("链表的内容为：");
visit(Lb);
// 按位置查找
printf("输入待查找元素位置：");
scanf("%d", &index);
s = GetElem(Lb, index, cur_e);
if (s == OK)
printf("第%d个元素的值为:%d\n", index, cur_e);
else
printf("不存在第%d个元素！\n", index);
// 按值查找
printf("输入待查找元素的值：");
scanf("%d", &cur_e);
index = LocateElem(Lb, cur_e);
printf("值为%d的元素在链表中的位置是%d\n", cur_e, index);
// 插入元素
printf("请输入插入元素的位置和内容：");
scanf("%d%d", &index, &value);
if (index > 0)
{ // 检查插入位置是否有效
s = ListInsert(Lb, index, value);
if (s == OK)
printf("插入成功！\n");
else
printf("插入失败！\n");
}
else
{
printf("插入位置无效！\n");
}
printf("链表的内容为：");
visit(Lb);
// 删除元素
printf("请输入要删除元素的位置：");
scanf("%d", &index);
if (index > 0)
{ // 检查删除位置是否有效
s = ListDelete(Lb, index, delvalue);
if (s == OK)
printf("删除成功！\n");
else
printf("删除失败！\n");
}
else
{
printf("删除位置无效！\n");
}
printf("链表的内容为：");
visit(Lb);
int lengthBeforeDestroy = ListLength(Lb);
DestroyList(Lb);
printf("销毁链表，该链表的长度为0");
return 0;
}