数据结构之链表（C语言）_c 链表

链表的概念：

  链表（Linked List）是数据结构中常见的一种基础数据结构，它由一些列节点（Node）组成，每一个节点都包含两部分，一部分是存储数据的数据域（Data），另一部分是记录下一个节点位置的指针域（Next）。链表中的节点在内存中存储的位置是不连续的，而是通过指针来相互连接。

链表有单向链表和双向链表两种形式。接下来我将通过C语言来实现单链表和双链表的一些基本操作，代码统一使用全局变量的头指针的形式来实现。

单链表：

1、建立单链表：

单链表的建立通常使用头插法或者尾插法；

通用代码：

struct Node {   //结构体定义
	int data;
	struct Node* next;
};
 
int count = 0; //计算节点的数量
struct Node* head = NULL; //头指针
 
struct Node* new(int x)  
{
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); //给新节点分配内存
    temp->data = x;  //赋值
    temp->next = NULL; 
	return temp;
}

头插法将新节点插入链表的开头；

代码实现：

void headList(int data)
{
	struct Node* A = new(data); //创建新节点
	A->next = head; //新节点的指针指向头指针指向的节点
	head = A; //头指针指向新节点
    count++;
}

尾插法将新节点插入链表的尾巴；

代码实现：

void lastList(int data)
{
	struct Node* k = head; //该变量用来替代头指针来进行移动
	struct Node* temp = new(data);
	if (k == NULL) //链表为空
	{
		temp->next = head;
		head = temp;
   
		return;
	}
	while (k->next != NULL) Move to the last node
		k = k->next;
	temp->next = k->next; 
	k->next = temp;
    count++;
}

2、单链表的按位插入

单链表的按位插入是指在指定位置插入一个节点。具体步骤如下：

1. 定义要插入的节点，并赋值。
2. 找到要插入位置前一个节点，并定义一个指向该节点的指针p。
3. 将要插入节点的next指针指向p的next指针所指向的节点。
4. 将p的next指针指向要插入的节点。

代码实现：

void insert(int x, int data) //x是插入位置 data是新节点的数据
{
	struct Node* sert = head; //因为head是全局变量
	struct Node* temp = new(data);
	if (x<1 || x>count) //插入位置非法
	{
		printf("error!");
		return;
	}
	for (int i = 1; i < x - 1; i++) //移动到插入的位置
		sert = sert->next;
	temp->next = sert->next;
	sert->next = temp;
}

3、单链表的按位查找和按值查找

步骤基本与按位插入一致；

代码实现：

//按位查找
void finder1(int x)
{
	struct Node* find = head; 
	if (head == NULL) //链表为空
	{
		printf("empty!\n");
		return;
	}
	if (x<1 || x > count) //查找位置非法
	{
		printf("error!\n");
		return;
	}
	for (int i = 1; i < x; i++)
	{
		find = find->next;
	}
	printf("number is %d \n", find->data); //打印
}
 
//按值查找
void finder2(int x)
{
	struct Node* find = head;
	while (find != NULL)
	{
		if (find->data == x)
		{
			printf("finding on");
			return;
		}
		find = find->next;
	}
	printf("false");
}

4、单链表的节点删除

代码实现：

void delete(int x)
{
	if (x<1 || x>count)
	{
		printf("error!\n");
		return;
	}
	struct Node* deleter = head;
	for (int i = 1; i < x - 1; i++) //移动到删除节点的前一个节点
	{
		deleter = deleter->next;
	}
	struct Node* A = deleter->next; //用于释放删除节点空间
	deleter->next = deleter->next->next;
	free(A);
}

完整代码实现：
 

struct Node {
	int data;
	struct Node* next;
};
 
struct Node* head = NULL; //头指针
 
int count = 0; //计算节点的数量
struct Node* new(int x)
{
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x; 
    temp->next = NULL;
	return temp;
}
头插法
void headList(int data)
{
	struct Node* A = new(data); //创建新节点
	A->next = head;
	head = A;
	count++;
 
}
尾插法
void lastList(int data)
{
	struct Node* k = head; //该变量用来替代头指针来进行移动
	struct Node* temp = new(data);
	if (k == NULL) //链表为空
	{
		temp->next = head;
		head = temp;
		count++;
		return;
	}
	while (k->next != NULL) //移动到最后一个节点
		k = k->next;
	temp->next = k->next; 
	k->next = temp;
	count++;
}
//按位插入
void insert(int x, int data)
{
	struct Node* sert = head; //因为head是全局变量
	struct Node* temp = new(data);
	if (x<1 || x>count) //查找位置非法
	{
		printf("error!");
		return;
	}
	for (int i = 1; i < x - 1; i++) //移动到插入的位置
		sert = sert->next;
	temp->next = sert->next;
	sert->next = temp;
}
//按位查找
void finder1(int x)
{
	struct Node* find = head;
	if (head == NULL)
	{
		printf("empty!\n");
		return;
	}
	if (x<1 || x > count)
	{
		printf("error!\n");
		return;
	}
	for (int i = 1; i < x; i++)
	{
		find = find->next;
	}
	printf("number is %d \n", find->data);
}
//按值查找
void finder2(int x)
{
	struct Node* find = head;
	while (find != NULL)
	{
		if (find->data == x)
		{
			printf("finding on");
			return;
		}
		find = find->next;
	}
	printf("false");
}
//删除
void delete(int x)
{
	if (x<1 || x>count)
	{
		printf("error!\n");
		return;
	}
	struct Node* deleter = head;
	for (int i = 1; i < x - 1; i++)
	{
		deleter = deleter->next;
	}
	struct Node* A = deleter->next;
	deleter->next = deleter->next->next;
	free(A);
}
打印
void Print()
{
	struct Node* h = head;
	while (h != NULL)
	{
		printf("%d ", h->data);
		h = h->next;
	}
	printf("\n");
}
int main()
{
	lastList(3);
	lastList(1);
	lastList(8);
	lastList(2);
	lastList(31);
	lastList(32);
	Print();
	delete(4);
	Print();
	insert(4, 9);
	Print();
	finder1(5);
    finder2(2);
	return 0;
}

双链表：

1、建立双链表：

通用代码：

struct Node {
	int data;
	struct Node* per;
	struct Node* next;
};
 
int count = 0;
 
struct Node* head = NULL;
 
struct Node* new(int n) //新节点
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = n;
    temp->next = NULL;
    temp->per = NULL;
	return temp;
}

头插法：

代码实现：

void headList(int x)
{
	struct Node* temp = new(x);
	if (head == NULL) 
	{
		temp->next = head;
		head = temp;
		temp->per = NULL;
		count++;
		return;
	}
	temp->next = head; //新节点指向head指向的节点
	head->per = temp; //head指向的节点指向新节点
	head = temp;  //改变head指向 
    temp->per = NULL;
	count++;
}

尾插法：

代码实现：

void lastList(int x)
{
	struct Node* header = head;
	struct Node* temp = new(x);
	if (head == NULL)
	{
		temp->next = head;
		head = temp;
		temp->per = NULL;
		count++;
		return;
	}
	while (header->next != NULL) //移动到最后节点
	{
		header = header->next;
	}
	temp->next = header->next;
	header->next = temp;
	temp->per = header;
	count++;
}

2、双链表的按位插入

代码实现：

void Insert(int x,int data)
{
	if (x<1 || x>count) //判断插入位置是否非法
	{
		printf("error!\n");
		return;
	}
	struct Node* header = head;
	struct Node* temp = new(data);
	for (int i = 1; i < x-1; i++)//移动到插入位置前一个位置
	{
		header = header->next;
	}
	temp->next = header->next;
	temp->per = header;
	header->next->per = temp; //插入位置的前节点指向新节点
	header->next = temp; 
	count++;
}

3、双链表的按位删除

双链表的删除操作需要注意边界问题，若删除为首节点时，应及时更新头指针的指向，若删除尾节点时，应做特殊处理。

代码实现：

void delete(int x)
{
	struct Node* header = head;
	if (x<1 || x>count)
	{
		printf("error!\n");
		return;
	}
	if (x == 1) //删除首节点
	{
		struct Node* B = header;
		header = B->next;
		head = header; //注意要更新头指针
		header->per = NULL;
		printf("delete a number : %d\n", B->data);
		free(B);
		count--;
		return;
	}
	for (int i = 1; i < x-1 ; i++) //前一个节点
	{
		header = header->next;
	}
	struct Node* A = header->next;
	if (A->next == NULL) //若删除节点为最后的节点
	{
		printf("delete a number : %d\n", A->data);
		header->next = A->next;  //直接更新前节点的next指针就行
		free(A);
		count--;
		return;
	}
	header->next = A->next;
	A->next->per = header;
	printf("delete a number : %d\n", A->data);
	free(A);
	count--;
}

4、双链表的前后遍历

代码实现：

//链表的遍历
void Print()
{
	struct Node* header = head;
	while (header != NULL) //从前遍历
	{
		if (header->next == NULL) //方便从后面遍历
		{
			printf("%d", header->data);
			break;
		}
		printf("%d ", header->data);
		header = header->next;
	}
	printf("\n");
	while (header != NULL)
	{
		if (header->next == NULL)
			break;
		header = header->next;
	}
	while (header != NULL)
	{
		printf("%d ", header->data);
		header = header->per;
	}
	printf("\n");
}

完整代码：
 

struct Node {
	int data;
	struct Node* per;
	struct Node* next;
};
 
int count = 0;
struct Node* new(int n) //新节点
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = n;
    temp->next = NULL;
    temp->per = NULL;
	return temp;
}
 
struct Node* head = NULL;
//头插法
void headList(int x)
{
	struct Node* temp = new(x);
	if (head == NULL) 
	{
		temp->next = head;
		head = temp;
		temp->per = NULL;
		count++;
		return;
	}
	temp->next = head;
	head->per = temp;
	head = temp;
	temp->per = NULL;
	count++;
}
//
//尾插法
void lastList(int x)
{
	struct Node* header = head;
	struct Node* temp = new(x);
	if (head == NULL)
	{
		temp->next = head;
		head = temp;
		temp->per = NULL;
		count++;
		return;
	}
	while (header->next != NULL) //移动到最后节点
	{
		header = header->next;
	}
	temp->next = header->next;
	header->next = temp;
	temp->per = header;
	count++;
}
//按位插入
void Insert(int x,int data)
{
	if (x<1 || x>count)
	{
		printf("error!\n");
		return;
	}
	struct Node* header = head;
	struct Node* temp = new(data);
	for (int i = 1; i < x-1; i++)//移动到插入位置前一个位置
	{
		header = header->next;
	}
	temp->next = header->next;
	temp->per = header;
	header->next->per = temp; //插入位置的前节点指向新节点
	header->next = temp; 
	count++;
}
//删除
void delete(int x)
{
	struct Node* header = head;
	if (x<1 || x>count)
	{
		printf("error!\n");
		return;
	}
	if (x == 1) //删除首节点
	{
		struct Node* B = header;
		header = B->next;
		head = header; //注意要更新头指针
		header->per = NULL;
		printf("delete a number : %d\n", B->data);
		free(B);
		count--;
		return;
	}
	for (int i = 1; i < x-1 ; i++) //前一个节点
	{
		header = header->next;
	}
	struct Node* A = header->next;
	if (A->next == NULL) //若删除节点为最后的节点
	{
		printf("delete a number : %d\n", A->data);
		header->next = A->next;
		free(A);
		count--;
		return;
	}
	header->next = A->next;
	A->next->per = header;
	printf("delete a number : %d\n", A->data);
	free(A);
	count--;
}
//链表的遍历
void Print()
{
	struct Node* header = head;
	while (header != NULL) //从前遍历
	{
		if (header->next == NULL) //方便从后面遍历
		{
			printf("%d", header->data);
			break;
		}
		printf("%d ", header->data);
		header = header->next;
	}
	printf("\n");
	while (header != NULL)
	{
		if (header->next == NULL)
			break;
		header = header->next;
	}
	while (header != NULL)
	{
		printf("%d ", header->data);
		header = header->per;
	}
	printf("\n");
}
int main()
{
	lastList(3);
	lastList(1);
	lastList(8);
	lastList(2);
	lastList(31);
	lastList(32);
	Print();
	Insert(3, 5);
	Print();
	delete(1);
	Print();
	return 0;
}

其他的链表操作基本上都是大同小异，例如双链表查找最小值、按值查找、暗值删除等一些扩展的操作，可根据基础代码进行编写，加深对链表操作的理解和熟练度。