2.3 带头结点的单链表：理论+编程实战（C语言详细）

1、顺序存储：线性表/栈/队列：理论+C语言实现–详细

2.1 链式存储概述 和 2.2 线性表的链式存储–单链表（C语言详细实现）

• • • 2.3 带头结点的单链表
    • • 1、 带头结点的单链表基本概念
      • 2、ADT描述
      • 3、编程实战

单连表的缺点：

• 单链表的插入和删除操作必须对在空的单链表插入新结点、删除结点后单链表成为空表等特殊情况做特殊处理。
• 为减少对特殊情况的判断处理，可以在单链表中设置一个特殊的结点，这个结点有单链表的首指针指示，只要有这个单链表，该结点就永远不会被删除。

数据集合 K：K={k1,k2,k3…,kn},n≥0，K中的元素是datatype类型；

数据关系R：R={r} ， r = {|i=1,2,…，n-1};

操作集合如下：

3、重要操作

1. 插入（在第i-1(1<= i <=n+1 )）个结点后插入一个值为x的新结点
   • 1 先构造一个新结点，用s指向
   • 2 在找到链表的第i-1个结点，用p指向
   • 3 然后修改指针，插入结点（p之后插入新结点是s）

2. 删除（删除链表的第i(1<=i<=n)）个位置上的结点

• 1 先找到链表的第i-1个结点，用p指向
• 2 再用指针s指向要删除的结点（p的下一个结点）
• 3 然后修改指针，删除s所指结点
• 最后释放s所指结点的空间，这样内存空间才不会泄漏
  

1. 头文件：head_single_linked_list.h

   #pragma once
   #ifndef __HEAD_SINGLE_LINKED_LIST_H
   #define __HEAD_SINGLE_LINKED_LIST_H
   
   #include
   #include
   #define error  NULL
   typedef int datatype;
   
   typedef struct hslink_list {
   	datatype info;
   	struct hslink_list* next;
   }hs_node;
   //建立一个空的带头结点的单链表
   hs_node* init();
   //输出带头结点的单链表中各个结点的值
   void display(hs_node* head);
   //按序号查找，在带头结点的单链表中查找第i个结点
   hs_node* findth(hs_node* head, int i);
   //按值查找，在带头结点的链表中查找值为x的结点
   int  find(hs_node* head, datatype x);
   //在带头结点的单链表中插入一个值为x的结点
   void insert(hs_node* head, datatype x, int pos);
   //在带头结点的单链表中删除一个值为x的结点
   void  dele(hs_node* head, datatype x);
   //查询带头结点的链表的长度
   int length(hs_node* head);
   
   
   
   #endif // !__HEAD_SINGLE_LINKED_LIST_H
   
   

2. 函数定义：head_single_linked_list.c

   #include"head_single_linked_list.h"
   
   hs_node* init()  
   {
   	hs_node* head;
   	head = (hs_node*)malloc(sizeof(hs_node));
   	head->next = NULL;
   	printf("链表创建成功！n");
   	return head;
   }
   
   
   void display(hs_node* head)
   {
   	hs_node* p;
   	p = head->next;
   	if (!p)
   	{
   		printf("The head single linked list is empty, can not displayn");
   		//exit(1);
   	}
   	else
   	{
   		printf("The head single linked list's value is :n");
   		while (p)
   		{
   			printf("%5d", p->info);
   			p = p->next;
   		}
   		printf("n");
   	}
   }
   
   hs_node* findth(hs_node* head, int i)
   {
   	hs_node* p=head;
   	int j = 0;
   	//p = head;
   	if (i < 0)
   	{
   		printf("this--%d node is not exit!n", i);
   	}
   	else if (i == 0) return p;
   	else
   	{
   		while (p&&j!=i)  //当p不为空且j小于i时，往下查找
   		{
   			p = p->next;
   			j++;
   		}
   		return p;  //如果找到则返回指向i结点的指针；否则返回指向为NULL尾结点的指针
   	}
   }
   
   int  find(hs_node* head, datatype x)
   {
   	hs_node* p;
   	p = head->next;
   	int i = 1;
   	while (p!=NULL&&p->info!=x)
   	{
   		p = p->next;
   		i++;
   	}
   	if (!p)
   	{
   		return 0;
   	}
   	else
   	{
   		return i;
   	}
   
   }
   
   void insert(hs_node* head, datatype x, int pos)
   {
   	hs_node* p, * q;
   	q=findth(head, pos);
   	if (!q)
   	{
   		printf("链表中不存在第%d个结点！不能插入%d", pos, x);
   		exit(1);
   		//return 0;
   	}
   
   	p = (hs_node*)malloc(sizeof(hs_node));
   	p->info = x;
   	p->next = q->next;
   	q->next = p;
   	printf("%3d插入成功！n",x);
   	//return 1;
   }
   
   
   void  dele(hs_node* head, datatype x)
   {
   	hs_node* pre=head, * q;
   	q = head->next;
   	while (q&&q->info!=x)
   	{
   		pre = q;
   		q = q->next;
   	}
   	if (q)  //当q指针不为空时，说明找到了值为x的结点
   	{
   		pre->next = q->next;  //跳过q指向的结点
   		free(q); //释放q指向的结点，防止内存泄漏
   		printf("删除操作成功！n");
   	}
   	else printf("删除失败！n");
   }
   
   
   int length(hs_node* head)
   {
   	int len = 0;
   	hs_node* p ;
   	p = head->next;
   	while (p)
   	{
   		len++;
   		p = p->next;
   	}
   	return len;
   }
   

3. main.c

   #include"head_single_linked_list.h"
   
   void main()
   {
   	struct hslink_list* head;
   	head = init();
   	int command = 0, position;
   	while (command<5)
   	{
   		insert(head, command, command );
   		command++;
   	}
   	while (command<10)
   	{
   		printf("input command:1:init  2:findth  3:find  4:insert  5:dele 6:length  7:displayn");
   		scanf_s("%d", &command);
   		switch (command)
   		{
   		case 1:free(head); head = init(); break;
   		case 2: {
   			printf("请输入要查找结点的序号：n");
   			scanf_s("%d", &command);
   			findth(head, command);
   			break;
   		}
   		case 3: {
   			printf("请输入要查找结点的值：n");
   			scanf_s("%d", &command);
   			command=find(head, command);
   			printf("该结点在第%d个位置n", command);
   			break;
   		}
   		case 4: {
   			printf("请输入要查找结点的值和位置：n");
   			scanf_s("%d%d", &command,&position);
   			insert(head, command, position);
   			break;
   		}
   		case 5: {
   			printf("请输入要删除结点的值：n");
   			scanf_s("%d", &command);
   			dele(head, command);
   			break;
   		}
   		case 6:printf("该链表不包含头结点一共有%d个结点n", length(head)); break;
   		case 7:display(head); break;
   		default:printf("The command is error ,please input again!n");break;
   		}
   	}
   }
   

4、程序运行结果：