数据结构C语言—线性表【链式存储】动态单链表（malloc动态分配实现）
SingleLinkListMalloc.h
#define NOEXIST -1
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE 1
#define OVERFLOW 1
typedef int Status;
typedef int DataType;
typedef int *Pt;
typedef struct LNode
{
DataType data;//该结点的数据域
struct LNode* next;//指向下一个结点的指针
}LNode,*LinkList;//默认带头结点
typedef struct SLinkList
{
LinkList head,tail;//指向线性单链表头结点和最后一个结点
DataType len;//线性单链表中元素的个数，即顺序表长度
}SLinkList;
/*
Status InsFirst(LinkList h,LinkList s);
Status DelsFirst(LinkList h,LinkList q);
Status Append(LinkList L,LinkList s);
Status Remove(LinkList L,LinkList q);
..........等等，《数据结构》-C语言版——严蔚敏，书37页、38页其余带头结点的线性链表操作函数，不再具体实现，
因为，本代码已经实现了在任意合法位置的插入与删除函数，可以轻易的实现这些省略的函数，故不在重复实现！
*/
Status Init_SLinkList(SLinkList* S);//初始化一个空的线性表S
void Head_Init_SLinkList(SLinkList* S);//头插法建立线性动态单链表S
void Tail_Init_SLinkList(SLinkList* S);//尾插法建立线性动态单链表S
Status DestoryList(SLinkList* S);//销毁线性表S
void ClearList(SLinkList* S);//清空线性表S
Status IsEmptySLinkList(SLinkList* S);//若S为空表，则返回TRUE,否则返回FALSE
DataType SLinkListLength(SLinkList* S);//返回S中数据元素个数
DataType GetElem(SLinkList* S,DataType i,Pt e);//用e返回S中第i个元素的值,操作成功返回OK，否则返回ERROR
DataType LocateElem(SLinkList* S,DataType e);//返回e在S中的位置,有该数据元素则返回其位置，否则返回0
Status PriorElem(SLinkList* S,DataType e,Pt proe);//若e是S的数据元素，且不是第一个，则用proe返回它的前驱。操作成功返回OK,否则返回-6699
Status NextElem(SLinkList* S,DataType e,Pt nexte);//若e是S的数据元素，且不是最后一个，则用nexte返回它的后继。操作成功返回OK,否则返回-6699
Status SLinkListInsert(SLinkList* S,DataType i,DataType e);//在S第i个位置之前插入新的元素e，S长度加1,成功操作返回OK，否则返回ERROR
DataType SLinkListDelete(SLinkList* S,DataType i,Pt e);//删除S的第i个数据元素，并用e返回其值，S长度减1,操作成功返回删除的值，否则返回ERROR
Status SLinkListTraverse(SLinkList* S);//依次对S每个数据元素调用函数,成功遍历返回OK，否则返回ERROR
SingleLinkListMalloc.c
#include "SingleLinkListMalloc.h"
#include <stdio.h>
Status Init_SLinkList(SLinkList* S)//初始化一个空的线性表S，只创建一个头结点;成功，返回OK，否则返回ERROR
{
DataType i;
puts("====开始初始化动态单链表S！====");
S->head=(LinkList)malloc(sizeof(LNode));//创建一个头结点
if(S->head!=NULL)
{
S->head->next=NULL;//将头结点的指针域赋NULL，因为此时只有头结点
S->head->data=0;//头结点的数据域不存元素，只是给定义的变量赋个初始值
S->tail=S->head;//tail本来要指向最后最后一个结点，而目前只有一个头结点，也让它指向头结点，表示线性动态单链表空状态！
S->len=0;//同时把动态单链表长度len置0
puts("====动态单链表S初始化完成！====");
return OK;
}
else
{
puts("动态链表初始化（创建头结点）失败！");
return ERROR;
}
}
void Head_Init_SLinkList(SLinkList* S)//头插法建立动态单链表S
{
DataType n,k,co=0;
LinkList q;//定义一个q指向新分配且待链入的结点
fflush(stdin);
printf("\n开始头插法(以f结束)：");
while(1)
{
k=scanf("%d",&n);
if(k==0)
{
break;
}
else
{
q=(LinkList)malloc(sizeof(LNode));
if(q!=NULL)
{
q->data=n;//给分配的结点赋值
//下面开始头插法：
q->next=S->head->next;
S->head->next=q;
co++;
(S->len)++;//单链表长度加一
if(co==1)
{
S->tail=q;//由于是头插法，因此第一个插入的结点就始终都是最后一个结点，让尾指针指向它
}
}
else
{
puts("头插法创建元素结点失败！");
}
}
}
fflush(stdin);
}
void Tail_Init_SLinkList(SLinkList* S)//尾插法建立动态单链表S
{
DataType n,k;
LinkList q;//定义一个q指向新分配且待链入的结点
fflush(stdin);
printf("\n开始尾插法(以f结束)：");
while(1)
{
k=scanf("%d",&n);
if(k==0)
{
break;
}
else
{
q=(LinkList)malloc(sizeof(LNode));
if(q!=NULL)
{
q->data=n;//给分配的结点赋值
//下面开始头插法：
q->next=S->tail->next;
S->tail->next=q;
(S->len)++;//单链表长度加一
S->tail=q;//让尾指针指向最后一个结点
}
else
{
puts("尾插法创建元素结点失败！");
}
}
}
fflush(stdin);
}
Status DestoryList(SLinkList* S)//销毁线性表S
{
if(S->len==0)
{
puts("\n==开始【销毁】静态单链表S！==");
}
else
{
puts("\n==开始【销毁】静态单链表S！==");
LinkList p=S->head->next; //让p指向首元结点，即第一个元素;
LinkList q=p;//让q也指向p的所指
while(p!=NULL)
{
q=p->next;//让q保存p位置所指的下一个结点
free(p);//释放p所指的结点
p=q;//让p又指向q的所指
}
S->len=0;//让表长归0
S->tail=S->head;//让尾指针指向头结点
S->head->next=NULL;
}
free(S->head);
S->head=NULL;
puts("==【销毁】静态单链表S完成！==");
return OK;
}
void ClearList(SLinkList* S)//清空线性表S,使单链表长度为0，只保留头结点，释放其他结点即可
{
if(S->len==0)
{
puts("\n==开始【清空】静态单链表S！==");
puts("==【清空】静态单链表S完成！==");
}
else
{
puts("\n==开始【清空】静态单链表S！==");
LinkList p=S->head->next; //让p指向首元结点，即第一个元素;
LinkList q=p;//让q也指向p的所指
while(p!=NULL)
{
q=p->next;//让q保存p位置所指的下一个结点
free(p);//释放p所指的结点
p=q;//让p又指向q的所指
}
S->len=0;//让表长归0
S->tail=S->head;//让尾指针指向头结点
S->head->next=NULL;
puts("==【清空】静态单链表S完成！==");
}
}
Status IsEmptySLinkList(SLinkList* S)//若S为空表，则返回TRUE,否则返回FALSE;表若不存在，返回NOEXIST
{
if(S->head==NULL)
{
puts("======表不存在！不能判断是否为空表！======");
return NOEXIST;
}
if(S->len==0)
{
return TRUE;
}
else
{
return FALSE;
}
}
DataType SLinkListLength(SLinkList* S)//返回S中数据元素个数
{
return S->len;
}
DataType GetElem(SLinkList* S,DataType i,Pt e)//用e返回S中第i个元素的值,操作成功返回OK，否则返回ERROR
{
if(IsEmptySLinkList(S)==TRUE)
{
printf("\n当前表空，不能查询！\n",i);
return ERROR;
}
if(i>SLinkListLength(S)||i<1)
{
printf("\n当前查询位置%d不合法！\n",i);
return ERROR;
}
LinkList p=S->head->next;
DataType co=0;
while(p!=NULL)
{
co++;
if(co==i)
{
*e=p->data;
return OK;
}
p=p->next;
}
}
DataType LocateElem(SLinkList* S,DataType e)//返回e在S中的位置,有该数据元素则返回其位置，否则返回0
{
if(IsEmptySLinkList(S)==TRUE)
{
return ERROR;
}
LinkList p=S->head->next;
DataType co=0;
while(p!=NULL)
{
co++;
if(p->data==e)
{
return co;
}
p=p->next;
}
return ERROR;
}
Status PriorElem(SLinkList* S,DataType e,Pt proe)//若若e是S的数据元素，且不是第一个，则用proe返回它的前驱。操作成功返回OK,否则返回-6699
{
if(IsEmptySLinkList(S)==TRUE)
{
*proe=-6699;
printf("\n当前表S空，不能查询%d的前驱值！\n",e);
return ERROR;
}
if(IsEmptySLinkList(S)!=TRUE&&LocateElem(S,e)==ERROR)
{
*proe=-6699;
printf("\n值%d不在表S中，无法返回其前驱值！\n",e);
return ERROR;
}
if(LocateElem(S,e)==1)
{
*proe=-6699;
printf("值%d是表S第一个元素，无前驱值！\n",e);
return ERROR;
}
LinkList p=S->head->next;
DataType co=0;
while(p!=NULL)
{
co++;
if(co==LocateElem(S,e)-1)
{
*proe=p->data;
return OK;
}
p=p->next;
}
}
Status NextElem(SLinkList* S,DataType e,Pt nexte)//若e是S的数据元素，且不是最后一个，则用nexte返回它的后继。操作成功返回OK,否则返回-6699
{
if(IsEmptySLinkList(S)==TRUE)
{
*nexte=-6699;
printf("\n当前表S空，不能查询%d的前驱值！\n",e);
return ERROR;
}
if(IsEmptySLinkList(S)!=TRUE&&LocateElem(S,e)==ERROR)
{
*nexte=-6699;
printf("\n值%d不在表S中，无法返回其前驱值！\n",e);
return ERROR;
}
if(LocateElem(S,e)==S->len)
{
*nexte=-6699;
printf("值%d是表S最后一个元素，无后继值！\n",e);
return ERROR;
}
LinkList p=S->head->next;
DataType co=0;
while(p!=NULL)
{
co++;
if(co==LocateElem(S,e)+1)
{
*nexte=p->data;
return OK;
}
p=p->next;
}
}
Status SLinkListInsert(SLinkList* S,DataType i,DataType e)//在S第i个位置之前插入新的元素e，S长度加1,成功操作返回OK，否则返回ERROR
{
if(i>SLinkListLength(S)+1||i<1)
{
printf("\n插入位置%d不合法，不能再插入！\n",i);
return ERROR;
}
LinkList p=S->head;
LinkList q;
DataType co=-1;
q=(LinkList)malloc(sizeof(LNode));//q指向新分配的待插入元素结点;
if(q!=NULL)
{
q->data=e;
while(p!=NULL)
{
co++;
if(co==i-1)
{
q->next=p->next;
p->next=q;
S->len++;//新插入一个元素结点，长度加一
if(i==SLinkListLength(S))
{
S->tail=q;//如果待插入的是尾结点，则让尾指针指向它
}
return OK;
}
p=p->next;
}
}
else
{
puts("待插入元素结点失败！");
}
}
DataType SLinkListDelete(SLinkList* S,DataType i,Pt e)//删除S的第i个数据元素，并用e返回其值，S长度减1,操作成功返回删除的值，否则返回ERROR
{
if(SLinkListLength(S)==0)
{
printf("\n当前表S空，不能删除任何值！\n");
return ERROR;
}
if(i>SLinkListLength(S)||i<1)
{
printf("\n删除位置%d不合法，不能删除任何值！\n",i);
return ERROR;
}
LinkList p=S->head;
LinkList q;//指向待删除元素的前一个元素
DataType co=-1;
while(p!=NULL)
{
co++;
if(co==i-1)
{
q=p;
}
if(co==i)
{
//此时,p指向要被删除的元素
q->next=p->next;
free(p);
S->len--;//新插入一个元素结点，长度加一
if(i==SLinkListLength(S))
{
S->tail=q;//如果待删除的是尾结点，则让尾指针指向它的前一个元素，即指向q
}
return OK;
}
p=p->next;
}
}
Status SLinkListTraverse(SLinkList* S)//依次对LS每个数据元素调用函数,成功遍历返回OK，否则返回ERROR
{
if(S->head==NULL)
{
puts("<===============线性动态单链表S已被销毁！无法遍历检查！===============>");
return ERROR;
}
LinkList p=S->head->next;
if(S->len==0)
{
printf("【遍历检查】|长度：%d|头结点-->NULL\n",S->len);
}
else
{
printf("【遍历检查】|长度：%d|头结点",S->len);
while(p!=NULL)
{
printf("--->%d",p->data);
p=p->next;
}
printf("-->NULL\n");
}
return OK;
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include "SingleLinkListMalloc.h"
/* 线性表——链式表（动态单链表）【自编代码】 */
int main()
{
SLinkList S;
DataType i,e,proe,nexte,n;
Init_SLinkList(&S);
SLinkListTraverse(&S);
printf("S中当前元素个数是：%d",SLinkListLength(&S));
if(IsEmptySLinkList(&S))
{
printf("\n======S是空表！======\n");
}
else
{
printf("\n======S不是空表！======\n");
}
Tail_Init_SLinkList(&S);
SLinkListTraverse(&S);
// printf("尾结点元素值：%d\n",S.tail->data);
printf("S中当前元素个数是：%d\n",SLinkListLength(&S));
if(IsEmptySLinkList(&S))
{
printf("\n======S是空表！======\n");
}
else
{
printf("\n======S不是空表！======\n");
}
printf("请输入要查询的位置：");
scanf("%d",&i);
if(GetElem(&S,i,&e))
{
printf("S表中%d位置值是：%d\n",i,e);
}
printf("请输入要查询位置的值：");
scanf("%d",&n);
if(LocateElem(&S,n)!=ERROR)
{
printf("\nS表中值%d所在位置是：%d\n",n,LocateElem(&S,n));
}
else
{
if(IsEmptySLinkList(&S)==TRUE)
{
printf("\n当前表空，不能查询%d的位置！\n",n);
}
else
{
printf("\n值%d的不在表中，可以加入表中！\n",n);
}
}
printf("请输入要返回其前驱的元素值：");
scanf("%d",&e);
if(PriorElem(&S,e,&proe)!=ERROR)
{
printf("值%d的前驱值是：%d\n",e,proe);
}
printf("请输入要返回其后继的元素值：");
scanf("%d",&e);
if(NextElem(&S,e,&nexte)!=ERROR)
{
printf("值%d的后继值是：%d\n",e,nexte);
}
printf("请输入要插入的位置和值：");
scanf("%d %d",&i,&e);
SLinkListInsert(&S,i,e);
SLinkListTraverse(&S);
// printf("尾节点是：%d\n",S.tail->data);
fflush(stdin);
printf("请输入要删除的位置：");
scanf("%d",&i);
SLinkListDelete(&S,i,&e);
SLinkListTraverse(&S);
ClearList(&S);
SLinkListTraverse(&S);
printf("S中当前元素个数是：%d",SLinkListLength(&S));
if(IsEmptySLinkList(&S))
{
printf("\n======S是空表！======\n");
}
else
{
printf("\n======S不是空表！======\n");
}
Head_Init_SLinkList(&S);
SLinkListTraverse(&S);
// printf("尾结点元素值：%d\n",S.tail->data);
printf("S中当前元素个数是：%d\n",SLinkListLength(&S));
if(IsEmptySLinkList(&S))
{
printf("\n======S是空表！======\n");
}
else
{
printf("\n======S不是空表！======\n");
}
printf("请输入要查询的位置：");
scanf("%d",&i);
if(GetElem(&S,i,&e))
{
printf("S表中%d位置值是：%d\n",i,e);
}
printf("请输入要查询位置的值：");
scanf("%d",&n);
if(LocateElem(&S,n)!=ERROR)
{
printf("\nS表中值%d所在位置是：%d\n",n,LocateElem(&S,n));
}
else
{
if(IsEmptySLinkList(&S)==TRUE)
{
printf("\n当前表空，不能查询%d的位置！\n",n);
}
else
{
printf("\n值%d的不在表中，可以加入表中！\n",n);
}
}
printf("请输入要返回其前驱的元素值：");
scanf("%d",&e);
if(PriorElem(&S,e,&proe)!=ERROR)
{
printf("值%d的前驱值是：%d\n",e,proe);
}
printf("请输入要返回其后继的元素值：");
scanf("%d",&e);
if(NextElem(&S,e,&nexte)!=ERROR)
{
printf("值%d的后继值是：%d\n",e,nexte);
}
printf("请输入要插入的位置和值：");
scanf("%d %d",&i,&e);
SLinkListInsert(&S,i,e);
SLinkListTraverse(&S);
// printf("尾节点是：%d\n",S.tail->data);
fflush(stdin);
printf("请输入要删除的位置：");
scanf("%d",&i);
SLinkListDelete(&S,i,&e);
SLinkListTraverse(&S);
ClearList(&S);
SLinkListTraverse(&S);
printf("S中当前元素个数是：%d",SLinkListLength(&S));
if(IsEmptySLinkList(&S))
{
printf("\n======S是空表！======\n");
}
else
{
printf("\n======S不是空表！======\n");
}
DestoryList(&S);
SLinkListTraverse(&S);
system("pause");
return 0;
}
运行结果示例
------------------------------------------------------第四次发文章有点激动啊！-----------------------------------------------------
-----------------------------------------------------【数据结构代码自编练习】------------------------------------------------------
----------------------------------------------------------------【TDTX】-----------------------------------------------------------------