[数据结构与算法]数据结构C语言—线性表【链式存储】动态单链表（malloc动态分配实现）【2021-07-03】

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 
{
	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】-----------------------------------------------------------------