【单链表】尾插法建立，头插法就地逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;

typedef struct node{
	  
	  datatype num;
	  struct node *next; 	
}Node, * LinkList; 


//函数
void LinkInitialize(LinkList head);			//用于链表初始化
void LinkBuildRear(LinkList head);			//尾插法建立单链表
void LinkPrint(LinkList head);  			//用于链表输出
void LinkReverse(LinkList head);			//就地逆置（迭代法） 
										

int main()
{
	
	Node node1;
	LinkList p;
	p = &node1;
	//结点指针，用于传入函数改变链表内容 
	LinkInitialize(p);				//结点的初始化 
	LinkBuildRear(p);               //链表的尾插法建立 
	printf("打印原链表：n");
	LinkPrint(p);
	LinkReverse(p);  				//链表的逆置 
	printf("打印逆置后链表：n");
	LinkPrint(p);
	
	return 0;
}


/*用于链表初始化*/ 
void LinkInitialize(LinkList head)  //先动态分配内存，再进行结点的指针域赋初值 
{
     head = (LinkList)malloc(sizeof(Node));
     head->next = NULL;
} 


/*尾插法建立单链表*/ 

//先定义结点指针 rear , p ;分别用来指向尾结点，新结点;
//接着新结点中存入数据，让新结点成为 rear 的后继结点
//然后rear指向尾结点
//最后新结点创建结束，即输入数据结束；将 rear 的指针域置为 NULL 
void LinkBuildRear(LinkList head)	
{
	LinkList  rear = head , p;
	datatype num1;
	printf("请输入若干个datatype型数据，以-1为结束：n");
	while(scanf("%d",&num1),num1 != -1)
	{
		p = (LinkList)malloc(sizeof(Node)); //开辟新结点并输入数据 
		p->num = num1;
		
		rear->next = p;			//让新结点作为rear的后继结点 
		rear = p;      			//让rear总是指向尾结点 	
	}
	  rear->next = NULL;	//数据输入结束，即新结点开辟结束 	
}			


/*用于链表输出*/
//先定义一个结点指针，用于指向首元结点
//接着循环遍历输出每个结点的数据域中的数据
//最后为了输出后看起来清晰，记得换行 
void LinkPrint(LinkList head)
{
	LinkList p = head->next;
	
	while(p != NULL)  //循环遍历，直至指向尾结点的后继结点（NULL） 
	{
		printf("%d ",p->num);
		p = p->next; 	
	}
	printf("n");
}



/*就地逆置（头插法）*/	
//首先定义两个结点指针 p ,q;分别指向首元结点和次首元结点（p用来遍历，q用来头插） 
//接着先让头结点的指针域置为 NULL；
// q先去找 p 所指的结点，让 p 后移遍历链表；
//然后让 q 指向的结点进行头插		
void LinkReverse(LinkList head)
{
	LinkList p , q;
	p = head->next;
	head->next = NULL; 
	
	while(p != NULL)
	{
	   q = p; 
	   p = p->next; 			//指针p用来遍历链表中的结点 
	   
	   q->next =head->next;		//q进行头插 （核心代码） 
	   head->next = q;	
	}
}