指针链表的实现

1.说明。

• 链表可以处理预先不知道变量个数的问题。
• 每一个结点都由两个部分组成。左边的部分用来存放具体的数值，用一个整型变量 就可以；右边的部分存储下一个结点的地址，可以用指针来实现（也称为后继指针）。 这里我们定义一个结构体类型来存储这个结点，如下：

struct node 
{
     
 int data; 
 struct node *next; 
}; 

• 第二个成员是一个指针，用来存储下一个结 点的地址。因为下一个结点的类型也是 struct node，所以这个指针的类型也必须是 struct node * 类型的指针。

2.链表如何建立？

1. 我们需要一个头指针 head 指向链表的最开始。当链表还没有建 立的时候头指针 head 为空（也可以理解为指向空结点）。

struct node *head; 
head = NULL;//头指针初始为空

2. 创建第一个结点，并用临时指针 p 指向这个结点。

struct node *p; 
//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p=(struct node *)malloc(sizeof(struct node)); 

3. 接下来分别设置新创建的这个结点的左半部分和右半部分。

scanf("%d",&a); 
p->data=a;//将数据存储到当前结点的data域中
p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空

• ->叫做结构体指针运算符，也是用 来访问结构体内部成员的。因为此处 p 是一个指针，所以不能使用.号访问内部成员，而要 使用->。

4. 设置头指针并设置新创建结点的*next 指向空。头指针的作用是方便以后从头遍 历整个链表。

if(head==NULL) 
 head=p;//如果这是第一个创建的结点，则将头指针指向这个结点
else 
 q->next=p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点

5. 最后要将指针 q 也指向当前结点，因为待会儿临时指针 p 将会指向新创建的结点。

q=p;//指针q也指向当前结点

3.链表的插入。

1. 首先用一个临时指针 t 从链表的头部开始遍历。

t=head;//从链表头部开始遍历

2. 等到指针 t 的下一个结点的值比 6 大的时候，将 6 插入到中间。即 t->next->data 大于 6 时进行插入，代码如下。

scanf("%d",&a);//读入待插入的数
while(t!=NULL)//当没有到达链表尾部的时候循环
{
     
 if(t->next->data > a)//如果当前结点下一个结点的值大于待插入数，将数插入到中间
 {
     
 p=(struct node *)malloc(sizeof(struct node));//动态申请一个空间，用来
存放新增结点
 p->data=a; 
 p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
 t->next=p;//当前结点的后继指针指向新增结点
 break;//插入完毕退出循环
 } 
 t=t->next;//继续下一个结点
} 

4.完整代码。

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

//创建一个结构体来表示链表的结点特征
struct node {
    
	int data;
	struct node* next;
};
int main(){
    
	struct node *head,*t,*q,*p;
	int i, a, n;
	//初始化要用到的节点
	head = NULL;
	q = NULL;
	//t = NULL; t可以不初始化
	printf("你要输入几位数：");
	scanf_s("%d", &n);
	printf("请输入数字：");
	for (i = 1; i <= n; i++) {
    //循环读入n个数
		
		p = malloc(sizeof(struct node));//申请内存空间
		scanf_s("%d",& p->data);//将数据存储到当前结点的data域中
		p->next = NULL;//设置当前结点的下一个结点为空
		if (head == NULL) {
    
			head = p;//如果这是第一个创建的结点，则将头指针指向这个结点
		}
		else {
    
			q->next = p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
		}
		q = p;//指针q变为当前结点
	}
	printf("请输入你要插入的数：");
	scanf_s("%d", &a);
	t = head;
	while (t != NULL) {
    //当链表不为空时
		if (t->next->data > a) {
    //如果下一个结点的data值大于要插入的数
			p = malloc(sizeof(struct node));
			p->data = a;//赋值
			p->next = t->next;//插入结点指向当前结点的后继
			t->next = p;//当前结点指向插入结点
			break;
		}
		t = t->next;

	}
	t = head;
	while (t != NULL) {
    //当链表不为空时，逐个输出
		printf("%d ", t->data);
		t = t->next;
	}
	/* while (head != NULL) { printf("%d", head->data); head = head->next; } */
	
	getchar(); getchar();
	return 0;
}

• 输入：

你要输入几位数：9
请输入数字：2 3 5 8 9 10 18 26 32
请输入你要插入的数：6

• 输出：

2 3 5 6 8 9 10 18 26 32

5.总结。

1. 头指针head指向链表最开始。
2. 链表插入时的处理顺序为：新增结点的后继–>然后当前结点的后继！