2.1 线性表的链式存储--单链表（C语言详细实现）

• • 2 线性表的链式存储
  • • 2.1 链式存储
    • 2.2 单链表
    • • 2.2.1 单链表的基本概念及描述
      • 2.2.2 单链表编程实战

如果一个结点有多个前驱和后继，采用顺序表需要足够大的连续存储分区，否则无法实现。为了解决连续分区不足的问题，我们可以采用链式存储方式。

在链式存储方式下，实现时除存放一个结点的信息外，还需附设指针，用指针体现结点之间的逻辑关系。如果一个结点有多个后继或前驱，那么可以附设多个指针。

在线性结构中，每个结点有最多只有一个前驱和后继，第一个结点没有前驱；最后一个结点没有后继，C语言中指针未空用NULL表示，结点结构如下：

• info：存放该结点的数据信息
• next：存放指向下一个结点的指针

在C语言的动态分配函数malloc()和free()分别实现内存空间的动态分配和回收，所以一般用户不必知道某个结点具体的地址是多少。

注意：在这种链式存储方式下，必须有一个头指针指向第一个结点的存储位置，否则无法访问整个数据结构的各个结点。，头指针用head表示。

1、概念

单链表是线性表链式存储的一种形式，其中的结点一般含有两个域。信息域：info和指针域next。单链表必须有一个头指针指向单链表的第一个结点：

2、描述

数据集合 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)）个位置上的结点
   • 先找到链表的第i-1个结点，用p指向
   • 再用指针s指向要删除的结点（p的下一个结点）
   • 然后修改指针，删除s所指结点
   • 最后释放s所指结点的空间，这样内存空间才不会泄漏

​ 创建一个单链表可以从一个空的单链表开始，通过不断插入心结点增加单链表的长度，已知一个单链表的首指针就可以找到单链表中的第一个结点，依据该结点得到指针与可以获得它的后继结点，反复这一操作，直到遇到一个阶段的指针域为空，表明已经遍历到最后一个结点了，依次可以访问单链表中的所有结点。

1、头文件：slnklist.h

#ifndef __SLNKLIST_H
#define __SLNKLIST_H
#include
#include
#define error NULL
typedef int datatype;

typedef struct link_node { //结构体标签link_node
	datatype info;
	struct link_node* next;
}node;  //结构体变量node

typedef struct link_node  *Linklist;
int create(Linklist* L); //创建链表

node* init(); //链表初始化

void display(node* head);//打印结点信息

node* findth(node* head, int i);  //按序号查找

node* find(node* head, datatype x);  //按值查找

node* insert(node* head, datatype x, int i);//插入在i位置新结点x

node* dele(node* head, datatype x);//删除结点中值为x的结点

int length(node* head); //返回链表的长度



#endif

2、函数定义：slnklist.c

#include"slnklist.h"

//建立一个空的单链表
// 参数：无
//返回值：指向node类型变量的指针

node* init()
{
	return NULL;
}

//int create(Linklist* L)
//{
//	L = (Linklist)malloc(sizeof(node));
//	if (!(*L))
//	{
//		return 0;
//	}
//	(*L)->next = NULL;
//	return 1;
//}

//输出单链表中各个结点的值
// 参数：指向node类型的变量的指针
//返回值：无
void display(node* head)
{
	node* p;
	p = head;
	if (!p)
	{
		printf("single linked list is NULLn");
	}
	else
	{
		printf("The values from the list header to the list tail are :n");
		while (p)
		{
			printf("%5d", p->info);
			p = p->next;       //point to the next node
		}
		printf("n");
	}
}

//按序号查找，在单链表中查找第i个结点

node* findth(node* head, int i)
{
	int j=1;
	node* p = head;
	if (i<0)
	{
		return NULL;  //查找错误
	}
	while (p&&i!=j)
	{
		p = p->next;
		j++;
	}
	return p;		//找到则返回指向x结点的指针，否则返回NULL
}
//按值查找，在单链表中查找第i个结点
node* find(node* head, datatype x)
{
	node* p = head;
	while (p!=NULL && p->info!=x)
	{
		p = p->next;
	}
	return p; //找到则返回指向x结点的指针，否则返回NULL
}

//在单链表中插入一个值为x的新结点

node* insert(node* head, datatype x, int i)
{
	node* s=NULL, * q;
	q = findth(head , i);
	if (!q && i!=0)
	{
		printf("找不到%d个结点，不能插入%dn",i,x);
	}
	else
	{
		s = (node*)malloc(sizeof(node));  //开辟新将插入结点的空间
		s->info = x;
		if (i==0)		//如果插入的结点为单链表的第一个结点时
		{
			s->next = head;
			head = s;
		}
		else
		{
			s->next = q->next;
			q->next = s;
		}
	}
	return head;  //返回头结点
}

//在单链表中删除一个值为x的结点
node* dele(node* head, datatype x)
{
	node* pre = NULL, * s;
	if (!head)
	{
		printf("单链表是空的n");
		return head;
	}
	s = head;
	while (s &&s->info!=x)   //寻找到指向数据位x的前驱
	{
		pre = s;
		s = s->next;
	}
	if (s)
	{
		if (!pre)
			head = head->next;
		else
		{
			pre->next = s->next;
			free(s);   //释放s结点内存空间
		}
	}
	return head;
}

int length(node *head)
{
	node* p = head;  //p指向表的第一个结点
	int j = 0;
	while (p)
	{
		p = p->next;
		j++;
	}
	return j;
}

3、主函数：main.c

#include"slnklist.h"
node* p;
void main()
{
	int j = 0;
	struct link_node* head=NULL;
	int command = 0, position;
	head = init();
	//if (j)
	//{
	//	printf("链表创建成功n");
	//}
	//else
	//{
	//	printf("链表创建失败n");
	//}
	while (j>=0&&j<=10)
	{
		head=insert(head, j, j);
		j++;
	}

	while (command<10)
	{
		printf("请输入要执行的操作：0:free		1:display		2:findth		3:find		4:insert	5:dele		6:lengthn");
		scanf_s("%d", &command);
		switch (command)
		{
		case 0:free(head); init(); break;
		case 1:display(head); break;
		case 2: {
			printf("请输入要查找的结点的序号n");
			scanf_s("%d", &j);
			p = findth(head, j);
			printf("info: %5d  next:%5d", p->info, p->next);
			break;
		}
		case 3: {
			printf("请输入要查找的结点的值n");
			scanf_s("%d", &j);
			p = find(head, j);
			printf("info: %5d  next:%5d", p->info, p->next);
			break;
		}
		case 4: {
			printf("please input the datatype and position that you want：n");
			scanf_s("%d %d", &j, &position);
			head=insert(head, j, position);
			break;
		}
		case 5: {
			printf("input delete datatype ：n");
			scanf_s("%d", &j);
			dele(head, j);
			break;
		}
		case 6:printf("The Linklist length is :%5dn", length(head)); break;
		default:printf("input is error,input againn"); break;
		}
	}
	
}

4、运行结果