CW_qian的博客：8月24日笔记数据结构（补9）带头节点单向链表

当前位置博文首页 > CW_qian的博客：8月24日笔记数据结构（补9）带头节点单向链表

CW_qian的博客：8月24日笔记数据结构（补9）带头节点单向链表

作者：[db:作者] 时间：2021-08-25 21:41

????????????????????????????????????????????????????????????????????????链表的介绍都在前面无头节点单向链表的基础上展开

基本构造（特点）

// 定义头节点
struct headNode
{
?? ?struct node *first; // 指向第一个数据节点
?? ?struct node *last; // 指向最后一个数据节点
?? ?int nodeNumber; // 记录链表节点数
};

定义头节点：struct headNode

? ? ? ? 只存放头和尾相关指针next，和链表长度

定义数据节点：struct node

创建新链表：struct headNode *create_list()

插入新节点：

? ? ? ? 头插：void headAdd(struct node *pnew,struct headNode *head)

? ? ? ? 尾插：void?tailAdd(struct node *pnew,struct headNode *head)

主函数

? ? ? ? int main()

{??????????创建链表:
??????????struct headNode *head = create_list();
? ? 功能：

1.打印链表：void show_list(struct headNode *head)
?? ?????????show_list(head);

2.在对应的data前面增加newdata节点：struct headNode *add_node(struct headNode *head,dataType newdata,dataType data)
?? ?????????head = add_node(head,8,3);

3.删除所有对应data数据的节点：struct headNode *del_node(struct headNode *head,dataType data)
?? ?????????head = del_node(head,3);

4.实现排序功能：struct headNode *sort_list()
? ??????????struct headNode *head ?= sort_list();
? ?
?? ?return 0;

}

具体代码：LinkedListWithHead.c

#include <stdio.h>
#include <stdlib.h>

//-----------------------------------
typedef int dataType;
//-----------------------------------

// 定义数据节点
struct node
{
	dataType data; // 数据域
	struct node *next; // 指针域，存放(指向)下一个节点的地址
};
//-----------------------------------

// 定义头节点
struct headNode
{
	struct node *first; // 指向第一个数据节点
	struct node *last; // 指向最后一个数据节点
	int nodeNumber; // 记录链表节点数
};
//---------------------------------
// 尾插
void tailAdd(struct node *pnew,struct headNode *head)
{
	head->last->next=pnew;
	head->last=pnew;
}
//---------------------------------
// 头插
void headAdd(struct node *pnew,struct headNode *head)
{
	pnew->next=head->first;
	head->first=pnew;
}
//---------------------------------
struct headNode *create_list()
{
	// 创建头节点
	struct headNode *head = malloc(sizeof(struct headNode));
	if(head == NULL)
	{
		perror("create headNode failed");
		return NULL;
	}
	head->first = NULL;
	head->last = NULL;
	head->nodeNumber = 0;
	
	dataType data;
	
	while(1)
	{
		scanf("%d",&data);
		if(data == 0)// 链表生成
			break;
		
		// 创建新节点
		struct node *pnew = malloc(sizeof(struct node));
		if(pnew == NULL)
		{
			perror("create newnode failed");
			return NULL;
		}	
		pnew->data = data;
		pnew->next = NULL;
		
		//将新节点插入到链表
		if(head->first == NULL)//从无到有
		{
			head->first = pnew;
			head->last = pnew;
		}
		else // 从少到多
		{
			// 尾插法
			tailAdd(pnew,head);
			
			// 头插法
			//headAdd(pnew,head);
			
		}
		
		// 更新节点数
		head->nodeNumber++;
	}
	
	return head;
}
//------------------------------
// 打印链表节
void show_list(struct headNode *head)
{
	for(struct node *p = head->first;p != NULL;p = p->next)
	{
		printf("%d  ",p->data);
	}
	printf("\n");
	printf("此链表的节点数据数为%d个\n",head->nodeNumber);
}
//------------------------------
struct headNode *add_node(struct headNode *head,dataType newdata,dataType data)
{
	// 创建新节点
	struct node *pnew = malloc(sizeof(struct node));
	if(pnew == NULL)
	{
		perror("create new node failed:");
		return NULL;
	}
	// 初始化新节点
	pnew->data = newdata;
	pnew->next = NULL;
	
	// 定义指针p遍历链表
	struct node *p = head->first;
	// 定义指针pre指向p的前一个节点
	struct node *pre = NULL;
	
	// 开始遍历链表查找对应的节
	while(p)
	{
		// 找到了,停止遍历
		if(p->data == data)
		{
			break;
		}
		else // 继续找
		{
			pre = p;
			p = p->next;
		}
	
	}
	// 找不到节点
	if(p == NULL) //尾插
	{
		tailAdd(pnew,head);
	}
	else
	{
		// 找打的是首节点
		if(p == head->first)
		{
			// 头插法
			headAdd(pnew,head);
		}
		else // 中间插
		{
			pre->next = pnew;
			pnew->next = p;
		}
	}
	// 链表节点加一
	head->nodeNumber++;
	return head;
}

/*
	del_node : 将head指向的链表中删除所有对应的data数据所对应的节点
*/
struct headNode *del_node(struct headNode *head,dataType data)
{
	// 遍历指针
	struct node *p = head->first;
	// 指向p的前一个节点
	struct node *pre = NULL;

	while(p)
	{
		if(p->data == data)// 找到需要删除的节点
		{
			// 链表节点减一
			head->nodeNumber--;
			
			if(p == head->first)// 需要删除的数据为首节点数据
			{
				head->first = head->first->next;
				p->next = NULL; // 断开链表
				free(p); // 释放空间
				p = head->first;//p重新指向新的首节点
			}
			else //删除的数据不是首节点
			{
				pre->next = p->next;
				p->next = NULL; // 断开链表
				free(p); // 释放堆空间
				p = pre->next; 
			}
		}
		else // 没有找到对应的节点，继续往下找
		{
			pre = p;
			p = p->next;
		}
	}
	
	return head;
}

struct headNode *sort_list()
{
	// 创建头节点
	struct headNode *head = malloc(sizeof(struct headNode));
	if(head == NULL)
	{
		perror("create headNode failed");
		return NULL;
	}
	head->first = NULL;
	head->last = NULL;
	head->nodeNumber = 0;
	
	// 用于存放数据的数据
	dataType data;
	// 循环创建节点,将节点插入到链表
	while(1)
	{
		// 输入数据
		scanf("%d",&data);
		// 链表创建完成
		if(data == 0)
			break;
		
		// 创建新节点
		struct node *pnew = malloc(sizeof(struct node));
		if(pnew == NULL)
		{
			perror("create new node failed:");
			return NULL;
		}
		// 初始化新节点里面的数据
		pnew->data = data;
		pnew->next = NULL;
		
		//如果链表为NULL
		if(head->first == NULL)
		{
			head->first = pnew;
			head->last  = pnew;
		}
		else // 链表不为空
		{
			// 定义遍历指针p指向链表的首节点，用于遍历链表
			struct node *p = head->first;
			// 定义一个指针pre指向p的前一个节点
			struct node *pre = NULL;
			while(p)
			{
				// 如果找到对应的节点
				if(p->data > pnew->data)
				{
					break;
				}
				else // 找不到，继续找
				{
					pre = p;
					p = p->next;
				}
			}
			
			// 如果找不到对应的数据
			// 将数据插入到链表的末尾
			if(p == NULL)
			{
				head->last->next = pnew;
				head->last = pnew;
			}
			else // 找到了对应的数据
			{
				// 如果找到的是首节点
				if(p == head->first) // 头插法
				{
					pnew->next = head->first;
					head->first = pnew;
				}
				else// 中间插
				{
					pre->next = pnew;
					pnew->next = p;
				}
			}	
		}
	}
	
	return head;
}



int main()
{
	// 创建新链表
	//struct headNode *head = create_list();
	
	//head = add_node(head,8,3);
	
	//  删除节点
	//head = del_node(head,3);
	
	// 排序
	struct headNode *head  = sort_list();
	
	//打印链表
	show_list(head);
	return 0;
}

扩展功能：

1.冒泡排序：struct headNode *sort_list(struct headNode *head)
?? ?????????head ?= sort_list(head);

/*
?? ?冒泡法实现排序
?? ?交换节点的数值
*/
struct headNode *sort_list(struct headNode *head)
{
?? ?for(int i = 0;i < head->nodeNumber-1;i++)
?? ?{
?? ??? ?struct node *p = head->first;
?? ??? ?
?? ??? ?for(int j = 0;j < head->nodeNumber-i-1;j++)
?? ??? ?{
?? ??? ??? ?if(p->data > p->next->data)
?? ??? ??? ?{
?? ??? ??? ??? ?int tmp;
?? ??? ??? ??? ?tmp = p->data;
?? ??? ??? ??? ?p->data = p->next->data;
?? ??? ??? ??? ?p->next->data = tmp;
?? ??? ??? ?}
?? ??? ??? ?p = p->next;
?? ??? ?}
?? ?}

?? ?return head;
}

2.链表逆序：struct headNode *reverse_list(struct headNode *head)
?? ?????????reverse_list(head);

/*
?? ?链表实现逆序功能
*/
struct headNode *reverse_list(struct headNode *head)
{
?? ?// 定义指针p指向链表的第一个节点
?? ?struct node *p = head->first;
?? ?// 定义指针pnew用于指向链表的首节点
?? ?struct node *pnew = NULL;
?? ?// 拆头节点
?? ?head->first = NULL;
?? ?head->last = NULL;
?? ?
?? ?// 遍历链表
?? ?while(p)
?? ?{
?? ??? ?// 拆节点
?? ??? ?// 定义pnew指向链表的首节点
?? ??? ?pnew = p;
?? ??? ?// p指向下一个节点
?? ??? ?p = p->next;
?? ??? ?// 将pnew节点从链表中断开
?? ??? ?pnew->next = NULL;
?? ??? ?
?? ??? ?// 将拆下来的节点进行头插法
?? ??? ?// 链表为空
?? ??? ?if(head->first == NULL)
?? ??? ?{
?? ??? ??? ?head->first = pnew;
?? ??? ??? ?head->last = pnew;
?? ??? ?}
?? ??? ?else // 链表不为空,头插法
?? ??? ?{
?? ??? ??? ?headAdd(pnew,head);
?? ??? ?}
?? ??? ?
?? ?}
?? ?
?? ?return head;
}

3.就地排序：struct headNode *sort1_list(struct headNode *head)
?? ?????????head = sort1_list(head);

/*
?? ?就地排序 ： 编写思想就是 先要拆链表，保证链表不丢失
?? ??? ??? ??? ?再拆节点，然后将拆下来的节点重新布局插入到原来的链表
*/

struct headNode *sort1_list(struct headNode *head)
{
?? ?// 定义指针p用于指向head所指向的首节点，防止等下拆链表头的时候导致链表丢失
?? ?struct node *p = head->first;
?? ?
?? ?// 定义一个指针pnew指向拆下来的节点
?? ?struct node *pnew = NULL;
?? ?
?? ?// 拆链表的头节点
?? ?head->first = NULL; // 断链表头
?? ?head->last = NULL; // 断链表尾?
?? ?
?? ?// 循环拆节点
?? ?while(p)
?? ?{
?? ??? ?// 拆节点
?? ??? ?// 定义一个指针pnew指向拆下来的节点
?? ??? ?pnew = p;
?? ??? ?// p指向下一个节点
?? ??? ?p = p->next;
?? ??? ?// 将pnew所指向的节点与原链表断开
?? ??? ?pnew->next = NULL;
?? ??? ?
?? ??? ?// 重新将节点插入到链表
?? ??? ?// 判断链表是否为空
?? ??? ?if(head->first == NULL) // 没有节点
?? ??? ?{
?? ??? ??? ?head->first = pnew;
?? ??? ??? ?head->last= pnew;
?? ??? ?}
?? ??? ?else // 链表不为空
?? ??? ?{
?? ??? ??? ?// 定义指针p1指向链表的首节点
?? ??? ??? ?struct node *p1 = head->first;
?? ??? ??? ?// 定义pre指针指向p的前驱节点
?? ??? ??? ?struct node *pre = NULL;
?? ??? ??? ?// 循环链表节点与pnew比较
?? ??? ??? ?while(p1)
?? ??? ??? ?{
?? ??? ??? ??? ?// 链表里面的节点大于pnew，那么表示找到了
?? ??? ??? ??? ?if(p1->data > pnew->data)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else // 没找到，继续往下找
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?pre = p1;
?? ??? ??? ??? ??? ?p1 = p1->next;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?//printf("__%d___\n",__LINE__);
?? ??? ??? ?// 如果p1不为空表示找到了对应的节点
?? ??? ??? ?if(p1 != NULL)
?? ??? ??? ?{
?? ??? ??? ??? ?// 表示新节点要插入到链表的首节点前面
?? ??? ??? ??? ?if(p1 == head->first) // 头插法
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?headAdd(pnew,head);
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else // 中间插入
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?pnew->next = p1;
?? ??? ??? ??? ??? ?pre->next = pnew;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?else // 找不到对应的节点进行尾插
?? ??? ??? ?{
?? ??? ??? ??? ?tailAdd(pnew,head);
?? ??? ??? ?}
?? ? ? ?}
?? ? }
? ? return head;
}

4.归并两条有序列表排序：struct headNode *merge_two_list(struct headNode *headA,struct headNode *headB)
?????????创建新链表
?? ?????????struct headNode *headA = create_list();
?? ?????????struct headNode *headB = create_list();??

????????????struct headNode *head ?= merge_two_list(headA,headB);

//归并两条有序链表
struct headNode *merge_two_list(struct headNode *headA,struct headNode *headB)
{
	// 定义指针pA和pB指向第一个节点
	struct node *pA = headA->first;
	struct node *pB = headB->first;
	
	// 创建头节点
	struct headNode *head = malloc(sizeof(struct headNode));
	if(head == NULL)
	{
		perror("create head failed : ");
		return NULL;
	}
	// 初始化头节点
	head->first = NULL;
	head->last = NULL;
	head->nodeNumber = headA->nodeNumber + headB->nodeNumber;
	
	// 定义指针pnew指向拆下来的节点
	struct node *pnew = NULL;
	
	// 同时遍历AB两条链表
	while(pA && pB)
	{
		// 如果pA小于pB节点则拆pA节点
		if(pA->data < pB->data)
		{
			pnew = pA;
			// pA指向下一个节点
			pA = pA->next;
			
			// 断开pnew
			pnew->next = NULL;
		}
		else
		{
			pnew = pB;
			// pA指向下一个节点
			pB = pB->next;
			
			// 断开pnew
			pnew->next = NULL;
		}
		
		// 将拆下来的节点依次插入到head链表
		if(head->first == NULL) // 链表为空
		{
			head->first = pnew;
			head->last = pnew;
		}
		else // 链表不为空,节点尾插
		{
			head->last->next = pnew;
			head->last = pnew;
		}
		
	}
	
	// 将A，B链表多余的节点插到head链表后面
	if(pA != NULL)
	{
		head->last->next = pA;
		//更新尾指针
		head->last = headA->last;
	}
	else
	{
		head->last->next = pB;
		//更新尾指针
		head->last = headB->last;
	}
	
	// 释放A，B两条链表
	headA->first = NULL;
	headA->last = NULL;
	free(headA);
	
	headB->first = NULL;
	headB->last = NULL;
	free(headB);
	
	return head;
}

上一篇：CW_qian的博客：8月25日笔记数据结构（补10）双向链表

下一篇：没有了

立即下载 - IIS7 站长工具包