数据结构_单链表(c语言)

(一)单链表图文解析

线性表链式存储结构的特点

结点	包括两个域:其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。
数据域：	用一组任意的存储单位存储线性表的数据元素(该组存储单元的地址可以是连续的，也可以是不连续的)。
指针域：	为了表示每个数据元素ai与其直接后继数据元素a(i+1)之间的逻辑关系，除了存储其本身的信息之外，还需要一个指示其直接后继的信息(即直接后继的存储位置）。

图示

用通俗简单的话来讲：

单链表就像过去靠挂钩连接的火车，一节车厢代表着一个结构体，车厢里面装着的东西代表着数据域，车厢的挂钩代表着指针域，车厢可以装载货物或者人或者其他的都是数据，而每一节车厢可以依靠挂钩（指针）连接着其他车厢，火车车头就是单链表的表头，火车车尾就是单链表的表尾。

(二)单链表代码解析

(1)单链表的基本操作

1.1 创建单链表

typedef char ElemType;	//定义ElemType的数据类型尾char字符类型
typedef struct LNode	//定义结构体LNode
{
	ElemType data;		//数据域，存放数据
	struct LNode *next;	//指针域，存放指针
}LinkList;				//结点

1.2 初始化单链表

void InitList(LinkList *&L)		//初始化单链表，即单链表初始只有一个没有数据且指针为空的结点
{
	L = (LinkList *)malloc(sizeof(LinkList));//为结点分配空间
	L->next = NULL;		//指针所指为空
}

1.3 销毁单链表

void DestroyList(LinkList *&L)//销毁单链表
{
	LinkList *q;
	if (!L)		//首先判断单链表是否存在
		printf("单链表不存在\n");
	else	
	{
		while (L)		//若存在，进入循环，直到单链表L为空
		{
			q = L->next;	//q为单链表的下一个结点
			free(L);		//释放头结点
			L = q;			//转到下一个结点进入下一次循环进行释放
		}
	}
}

1.4 清空单链表

void ClearList(LinkList *&L)		//与销毁单链表操作类似
{
	LinkList *p = L->next, *q;		//但不释放头结点,因为清空后还需要继续使用单链表
	if (!p)
		printf("单链表已空\n");
	else
	{
		while (p)
		{
			q = p->next;
			free(p);
			p = q;
		}
		L->next = NULL;			//最后只剩下头结点指向空，若还需要用可继续在头结点后增加结点
	}
}

1.5 单链表表长

void ListLength(LinkList *L)
{
	LinkList *p = L;
	int i = 0;
	while (p->next != NULL) //遍历结点
	{
		i++;			//每遍历到一个结点通过i来记录长度
		p = p->next;	//移动位置到下一个结点
	}
	printf("链表长为%d\n", i); //当尾节点指向为空NULL，退出循环输出所计数i的值
}

1.6 遍历单链表

void DispList(LinkList *L)
{
	LinkList *p = L->next;
	if (!p) 	//若头结点的next为空结点，则该单链表为空
		printf("链表为空");
	while (p != NULL)		//遍历
	{
		printf("%c ",p->data);	//每遍历到一个结点，就输出该结点的数据元素
		p = p->next;		//指向下一个结点
	}
	printf("\n");
}

1.7 单链表插入结点

void ListInsert(LinkList *&L)
{
	ElemType e;    
	int i,j = 0;
	LinkList *p = L, *s;
	printf("请输入插入结点的位置和元素值:");
	scanf("%d %c", &i, &e);		//输入插入结点的位置和数据元素
	while (j < i - 1 && p != NULL)	//查找所要插入的位置的前一个结点，且确保插入位置合法（即存在该位置）
	{
		j++;
		p = p->next;
	}
	if (p == NULL)			//若p为空，即一直遍历位置的到表尾结点也未找到所输入的位置
		printf("未查询到该位置信息\n");
	else		//在确保位置信息正确后
	{
		s = (LinkList *)malloc(sizeof(LinkList));	//创建一个用于插入的新结点
		s->data = e;		//将输入的数据赋值给新结点的数据域
		s->next = p->next;	//将插入结点的前一个结点p的下一个结点赋值给新结点的指针域
		p->next = s;		//最后将新结点接在插入结点前的结点p的后面，完成插入
		printf("插入成功！\n");
	}

}

1.8 判断单链表是否为空

void ListEmpty(LinkList *L)   //直接判断头结点的下一个结点是否为空
{
	if (L->next == NULL)
		printf("单链表为空\n");
	else
		printf("单链表非空\n");
}

1.9 查找单链表某数据的位置

void LocateElem(LinkList *L)
{
	ElemType e;
	int i = 1;
	LinkList *p = L->next;
	printf("请输入查询的元素值:");
	rewind(stdin);		//在使用scanf（）函数之前先清空键盘缓存区,防止回车键的干扰跳过输入函数
	scanf("%c",&e);		//输入查询的元素值
	while (p != NULL&&p->data!=e)	//遍历单链表并判断每个结点的数据域元素是否与查找元素相等
	{
		p = p->next;	//转到下一个结点 
		i++;			//通过i来记录结点位置
	}
	if (p == NULL)		//若p为空则未查询到输入元素位置
		printf("未查询到该元素位置\n");
	else			//若查询到元素值，则输入元素位置
		printf("该元素位置为:%d\n", i);	
}

1.10 取单链表第i个结点的数据

void GetElem(LinkList *L)
{
	int i,j = 0;
	LinkList *p = L;
	printf("请输入需要查找的位置:");
	scanf("%d", &i);	//输入需要查找的位置
	while (j < i&&p != NULL)	//遍历单链表查找位置
	{
		j++;
		p = p->next;
	}
	if (p == NULL)		//若p为空，则未查询到该位置的元素
		printf("未查询到该位置的元素\n");
	else			//若不为空，即查询到该结点位置，输出该结点数据元素
		printf("该位置的元素为:%c\n",p->data);
}

1.11 删除单链表的某个结点

void ListDelete(LinkList *&L, ElemType &e)
{
	int i,j = 0;
	LinkList *p = L, *q;
	printf("请输入需要删除的结点位置:");
	scanf("%d", &i);	//输入需要删除的结点位置
	while (j < i - 1 && p != NULL)	//遍历单链表，查询所输入位置的前一个结点，且确保输入的位置合法
	{
		j++;
		p = p->next;
	}
	if (p == NULL)	//未查询到该位置的前一个结点，即所查询位置的前一个结点为空
		printf("未查询到该位置信息\n");
	else		//若查询到该位置的前一个结点
	{
		q = p->next;
		if (q == NULL)	//但查询位置的所在结点为空
			printf("该结点为空\n");	//即所查询位置的结点为空
		else	//若查询结点不为空，即查询位置结点和其前一个结点都存在
		{
			e = q->data;	//将该结点数据域赋值给e
			p->next = q->next;	//将删除结点的下一个结点赋值给删除结点的前一个结点指针域，即将删除结点的下一个结点交给前一个结点的指针next
			free(q); //最后释放删除结点
		}
		printf("删除成功!\n");
	}

}

(2)单链表源代码及测试

2.1 源代码

#include <stdio.h>
#include<malloc.h>

typedef char ElemType;

typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LinkList;

void InitList(LinkList *&L)
{
	L = (LinkList *)malloc(sizeof(LinkList));
	L->next = NULL;
}

void DestroyList(LinkList *&L)//销毁单链表
{
	LinkList *q;
	if (!L)
		printf("单链表不存在\n");
	else
	{
		while (L)
		{
			q = L->next;
			free(L);
			L = q;
		}
	}
}

void ClearList(LinkList *&L)
{
	LinkList *p = L->next, *q;
	if (!p)
		printf("单链表已空\n");
	else
	{
		while (p)
		{
			q = p->next;
			free(p);
			p = q;
		}
		L->next = NULL;
	}
}

void ListEmpty(LinkList *L)
{
	if (L->next == NULL)
		printf("单链表为空\n");
	else
		printf("单链表非空\n");
}

void ListLength(LinkList *L)
{
	LinkList *p = L;
	int i = 0;
	while (p->next != NULL)
	{
		i++;
		p = p->next;
	}
	printf("链表长为%d\n", i);
}

void DispList(LinkList *L)
{
	LinkList *p = L->next;
	if (!p)
		printf("链表为空");
	while (p != NULL)
	{
		printf("%c ",p->data);
		p = p->next;
	}
	printf("\n");
}

void GetElem(LinkList *L)
{
	int i,j = 0;
	LinkList *p = L;
	printf("请输入需要查找的位置:");
	scanf("%d", &i);	
	while (j < i&&p != NULL)
	{
		j++;
		p = p->next;
	}
	if (p == NULL)
		printf("未查询到该位置的元素\n");
	else
		printf("该位置的元素为:%c\n",p->data);
}

void LocateElem(LinkList *L)
{
	ElemType e;
	int i = 1;
	LinkList *p = L->next;
	printf("请输入查询的元素值:");
	rewind(stdin);
	scanf("%c",&e);	
	while (p != NULL&&p->data!=e)
	{
		p = p->next;
		i++;
	}
	if (p == NULL)
		printf("未查询到该元素位置\n");
	else
		printf("该元素位置为:%d", i);	
}


void ListInsert(LinkList *&L)
{
	ElemType e;
	int i,j = 0;
	LinkList *p = L, *s;
	printf("请输入插入结点的位置和元素值:");
	scanf("%d %c", &i, &e);
	while (j < i - 1 && p != NULL)
	{
		j++;
		p = p->next;
	}
	if (p == NULL)
		printf("未查询到该位置信息\n");
	else
	{
		s = (LinkList *)malloc(sizeof(LinkList));
		s->data = e;
		s->next = p->next;
		p->next = s;
		printf("插入成功！\n");
	}

}

void ListDelete(LinkList *&L, ElemType &e)
{
	int i,j = 0;
	LinkList *p = L, *q;
	printf("请输入需要删除的结点位置:");
	scanf("%d", &i);
	while (j < i - 1 && p != NULL)
	{
		j++;
		p = p->next;
	}
	if (p == NULL)
		printf("未查询到该位置信息\n");
	else
	{
		q = p->next;
		if (q == NULL)
			printf("该结点为空\n");
		else
		{
			e = q->data;
			p->next = q->next;
			free(q);
		}
		printf("删除成功!\n");
	}

}

void main()
{
	int k;
	ElemType e;
	LinkList *h;
	InitList(h);
	printf("单链表已初始化\n");
	while (1)
	{
		printf("0：退出 1：插入 2：删除 3：查询位置 4：查询元素 5：表长 6：遍历单链表 7：清空 8：销毁 9：表空\n请选择:");
		scanf("%d", &k);
		switch (k)
		{
		case 1:
			ListInsert(h);
			break;
		case 2:
			ListDelete(h, e);
			break;
		case 3:
			LocateElem(h);
			break;
		case 4:
			GetElem(h);
			break;
		case 5:
			ListLength(h);
			break;
		case 6:
			DispList(h);
			break;
		case 7:
			ClearList(h);
			break;
		case 8:
			DestroyList(h);
			break;
		case 9:
			ListEmpty(h);
			break;
		}
		if (k == 0)
			break;
	}
}