[数据结构与算法] 数据结构

? ? ? ? 单向链表根据使用情况还分为单向不循环链表、单向循环链表两种。

（1）单向不循环链表

????????单向不循环链表是一种单向的链式结构，节点之间通过指针域互相关联，最后一个节点的指针域为空（NULL）。如下图所示：

???????

??下面用C语言实现一个单向不循环链表的代码。

1）先定义一个链表的节点。如下：

// 定义一个链表节点的数据域。以记录一个苹果的信息为例，为方便说明，假设每个苹果的信息各不相同
typedef struct LinkData_struct
{
	int  weight; // 苹果的重量
	int  hight;  // 苹果的高度
	// ... 		 // 还可以定义更多的其他的数据
}LinkData_t;

/*** 定义一个链表节点 ******/
typedef struct LinkNode_Struct
{
	LinkData_t data;				// 链表节点的数据域
	struct LinkNode_Struct *Next; 	// 链表节点的指针域
}LinkNode_t;

2）定义一个单向链表的头结点。如下：

/*** 定义一个单向链表的头结点 ***/
LinkNode_t AppleInfo_head; //作为单向链表的一个头结点

3）初始化单向链表。如下：

// 初始化单向链表的头结点
void Init_LinkNode(LinkNode_t * HeadNode)
{
	HeadNode->Next = NULL;
}

4）创建链表节点并接入到链表中。如下：

// 创建一个链表节点并接入到链表中
LinkNode_t * LinkNode_Create(LinkNode_t * HeadNode, LinkData_t *InsetData)
{
	LinkNode_t *Node,*pf;
	LinkNode_t *xReturn = NULL;
	Node = (LinkNode_t *)malloc(sizeof(LinkNode_t));

	if (Node == NULL)
	{
		printf("节点创建失败！！！\r\n");
		return NULL;
	}

	pf = HeadNode;
	while(pf->Next != NULL)
	{
		pf = pf->Next;
	}
	pf->Next = Node;
	Node->Next = NULL;
	Node->data.hight = InsetData->hight;
	Node->data.weight = InsetData->weight;
	xReturn = Node;

	printf("完成一个链表节点的创建，地址 = 0x%X\r\n",xReturn);
	return xReturn;
}

5）删除链表中的节点。如下：

// 删除链表中的某个节点,根据weight进行删除
void destroy_LinkNode(LinkNode_t * HeadNode, int weight)
{
	int deleteFlag = 0;
	LinkNode_t *pf,*preStre;

	pf = preStre = HeadNode;

	do
	{
		if (pf->data.weight == weight){
			deleteFlag = 1;
			break;
		}
		preStre = pf;
		pf = pf->Next;
	}while (pf->Next != NULL);

	if (!deleteFlag)
	{
		printf("找不到这个节点！！！\r\n");
	}
	else
	{
		if(pf->Next == NULL)	// 该点是尾节点
		{
			preStre->Next = NULL;
		}
		else
		{
			preStre->Next = pf->Next;
		}
		free(pf);
		printf("节点weight = %d 销毁成功！\r\n",weight);
	}
}

6）输出整条链表的数据。如下：

// 输出显示整条链表
void print_LinkNode_Info(LinkNode_t * HeadNode)
{
	int length = 0;
	LinkNode_t *pf = HeadNode;

	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}

	do	
	{
		pf = pf->Next;
		printf("weight = %d\r\n", (int)pf->data.weight);
		printf("height = %d\r\n", (int)pf->data.hight);
		printf("\r\n");
		length++;
	}while (pf->Next != NULL);
	printf("链表输出完成。长度为：%d\r\n",length);
}

7）按条件查询链表中某个节点的数据。如下：

// 按条件查询链表中某个节点的数据
void search_LinkNode_Info(LinkNode_t * HeadNode, int weight)
{
	int length = 0;
	char search_flag = 0;
	LinkNode_t *pf = HeadNode;

	if (pf->Next == NULL)
	{
		printf("该链表长度为零，不能输出结果！\r\n");
		return;
	}

	do	
	{
		pf = pf->Next;
		if(pf->data.weight == weight)
		{
			search_flag = 1;
			printf("weight = %d\r\n", (int)pf->data.weight);
			printf("height = %d\r\n", (int)pf->data.hight);
			printf("\r\n");
		}
		length++;
	}while (pf->Next != NULL);

	if(search_flag)
	{
		printf("链表查找结束。所在节点位置为：%d\r\n",length);
	}
	else
	{
		printf("整个链表中无满足此条件的节点！\r\n");
	}
}

? ? ? ?单向不循环链表的演示demo

????????注意：这个demo可以直接运行在控制台上输出显示！

void print_debug_info(void)
{
	printf("******** 链表控制台 *****************\r\n");
	printf("*                                  \r\n");
	printf("*  1：创建链表                      \r\n");
	printf("*  2：删除链表                      \r\n");
	printf("*  3：显示整条链表的数据             \r\n");
	printf("*  4：按条件查找链表节点             \r\n");
	printf("*  8：清空显示                      \r\n");
	printf("*  9：结束运行                      \r\n");
	printf("*                                  \r\n");
	printf("************************************\r\n");
}

int main(int argc, char *argv[]) 
{
	int Num,i,j;
	int Options;
	int weight,height;
	LinkData_t InsetData;

	Init_LinkNode(&AppleInfo_head);

	while (1)
	{
		print_debug_info();
		printf("\r\n请输入需要操作的键值，按回车键确认！\r\n");
		scanf("%d", &Options);
		switch (Options)
		{
			case 1:
				/*** 创建任意长度的链表 **********************************************************/
				printf("请输入需要创建的链表节点的数量,按回车结束！\r\n");
				scanf("%d", &Num);

				printf("请输入节点的数据：\r\n");
				for (i = 0; i < Num; i++)
				{
					printf("请输入第 %d 节点的数据,weight = Height = ,输入完毕按回车结束！\r\n",i+1);
					scanf("%d %d", &weight,&height);
					InsetData.weight = weight;
					InsetData.hight  = height;
					printf("weight = %d height = %d\r\n",weight,height);

					if(LinkNode_Create(&AppleInfo_head, &InsetData) > NULL)
					{
						printf("节点 %d 创建成功！\r\n\r\n\r\n",i+1);
					}
					else
					{
						printf("节点 %d 创建失败！\r\n\r\n\r\n",i+1);
					}
				}
				printf("\r\n");
				break;
			
			case 2:
				/******* 删除链表中的某个节点 ***************************************************/
				printf("请输入需要删除的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				destroy_LinkNode(&AppleInfo_head, Num);
				printf("\r\n");
				break;

			case 3:
				printf("链表数据为：\r\n");
				print_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;

			case 4:
				printf("请输入需要查找的链表节点的weight,按回车结束！\r\n");
				scanf("%d", &Num);
				search_LinkNode_Info(&AppleInfo_head, Num);
				printf("\r\n");
				break;

			case 8:
				system("cls");
				break;

			case 9:
				printf("退出链表控制台，请再次运行程序！\r\n");
				return;
				break;
			
			default:
				printf("无效的键值，请重新输入！\r\n");
				break;
		}
	}
	return 0;
}

（2）单向循环链表

????????单向循环链表是一种单向的可回头的链表，节点之间通过指针域互相关联，最后一个节点的指针域为头结点的地址。如下图所示：

下面用C语言实现一个单向循环链表的代码。