数据结构与算法 第四天-队列与栈的逻辑与单向循环链表_开发队列逻辑

建议边看图，边看代码，不然还是理解不容易

第一章 数据结构 队列 代码实现（先进先出）

先进先出：第一个放在第一位，其余依次放在后面，取出时遍历从第一个拿

联合函数inline：适合代码简短且固定的函数
静态函数static：防止函数重名，作用域只在本.c文件内

出队
入队

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

typedef struct list_node{
    int data;				//存放数据
    struct list_node *next;//本结构体指针变量
}node_t;//链表节点类型


//申请链表空间
node_t *request_queue_node(void)
{
    node_t *new_node;

    new_node = malloc(sizeof(node_t));
    if(new_node == NULL)
    {
        perror("申请链表节点失败");
        return NULL;
    }

    new_node->next = NULL;//初始化

    return new_node;
}
/*
    函数功能:
        将insert_node这个节点插入到refer_node这个节点之后的位置
    参数:
        refer_node:是链表中的任意一个节点
        insert_node:需要插入的节点
    返回值:
        无
*/
static inline void enqueue(node_t *list_head, node_t *insert_node)
{
    node_t *pos;

    for(pos=list_head; pos->next != NULL; pos=pos->next);

    pos->next = insert_node;
}

//显示队列数据
void show_queue(node_t *list_head)
{
    node_t *pos;

    printf("队列已有数据:");

    for(pos=list_head->next; pos!=NULL; pos = pos->next)
    {
        printf("%d ", pos->data);//遍历队列
    }

    printf("\n");
}

//判断队列是否为空
bool is_empty(node_t *head)
{
    return head->next == NULL;//头节点的下一个节点=NULL 没有数据
}

/*
    函数功能:
        在队列中获取一个
    参数:
        refer_node:链表当中的任意一个节点
*/
node_t *dequece(node_t *list_head)
{
    if(is_empty(list_head))
        return NULL;

    node_t *dequece_node;

    dequece_node = list_head->next;//头节点下一个节点

	//头节点下一个节点=头节点下一个节点的下一个节点
    list_head->next = dequece_node->next;//将节点移出队列

    return dequece_node;//返回头节点的下一个节点[下一次以此类推]
}

//销毁队列
void destroy_queue(node_t *list_head)
{
    node_t *pos, *next;

    pos = list_head;//等于头结点
   
    do{
        next = pos->next;//上一个节点的下一个节点
        free(pos);//释放空间
        pos=next;//等于下一个节点
    }while(pos!=NULL);//下一个节点之后没有了，退出

}


int main(void)
{

    int input_value;
    node_t *list_head, *new_node, *get_node;

    //新建头节点
    list_head = request_queue_node();//申请头节点空间
    if(list_head == NULL)
        return -1;
    
    list_head->data = -1;//初始化

    while(1)
    {
        scanf("%d", &input_value);

        if(input_value > 0)
        {

            //新建节点
            new_node = request_queue_node();//申请数据存放节点空间

            new_node->data = input_value;

            //将节点插入队伍
            enqueue(list_head, new_node);//【入队】

        }
        else if(input_value < 0)
        {
            //删除头节点之后的节点数据【出队】
            get_node = dequece(list_head);//获取节点空间
            if(get_node != NULL)
            {
                printf("出队节点为%d\n", get_node->data);
                free(get_node);//释放【删除】
            }
            else
            {
                printf("队列已空\n");
            }
        }
        else
            break;

        //打印表格当中的数据
        show_queue(list_head);
    }

    //销毁队列
    destroy_queue(list_head);

    return 0;
}
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

第二章 数据结构 栈和队列合并 代码实现（先进后出）

先进后出：先进的放在后面，下一次插入放在他前面，以此类推

两条栈合成一条队列

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

typedef struct list_node{
    int data;
    struct list_node *next;//代表本结构体节点的下一个节点
}node_t;//链表节点类型

/*
    函数功能:
        申请一个节点
    返回值:
        成功返回申请的节点
*/
node_t *request_list_node(void)
{
    node_t *new_node;

    new_node = malloc(sizeof(node_t));
    if(new_node == NULL)
    {
        perror("申请链表节点失败");
        return NULL;
    }

    new_node->next = NULL;

    return new_node;
}
/*
    函数功能:
        将insert_node这个节点插入到list_head这个栈当中
    参数:
        list_head:栈列表头节点
        insert_node:需要插入的节点
    返回值:
        无
*/
static inline void in_stack(node_t *list_head, node_t *insert_node)
{
	// 插入节点的下一个节点指向=头节点的下一个节点 
	//头【next->】 insert_node【next->】 【上次头节点next->这里】[链表要前后要连接完整]
    insert_node->next = list_head->next;
    list_head->next = insert_node;//以此类推，每次插入的数，下一次被挤到后面了
}

//打印数据
void show_list_data(node_t *list_head)
{
    node_t *pos;

    printf("队列已有数据:");
	//显然是按照先进后出打印，因为插入的时候最后插入的放在了最前面
    for(pos=list_head->next; pos!=NULL; pos = pos->next)
    {
        printf("%d ", pos->data);
    }

    printf("\n");
}

//判断链表是否空
bool is_empty(node_t *head)
{
    return head->next == NULL;
}

/*
    函数功能:
        从list_head这条栈中获取一个节点出来(并且移除栈表格)
    参数:
        list_head:栈链表头节点
    返回值:
        成功返回获取到的节点,失败返回NULL(链表已空)
*/
node_t *out_stack(node_t *list_head)//出栈【删除】
{
    if(is_empty(list_head))//为什么先判断，如果一个数据也没有，就没必要往下走了
        return NULL;

    node_t *get_stack_node;//临时指针

    get_stack_node = list_head->next;

	//get_stack_node->next=list_head->next->next【不这样写，是为了简化】
    list_head->next = get_stack_node->next;//将节点移出队列【头节点next已经指向了下一个节点】
//让这个节点初始化一下,没有下一个节点(因为队列中是将节点插入到最后,如果不是NULL,这循环会出现问题)
    get_stack_node->next = NULL;//【这只是临时变量，用完置空，防止野指针】
	

    return get_stack_node;
}

//由于出队逻辑与出栈逻辑一致,给出栈函数取个别名叫做出队
#define dequeue(list_head) out_stack(list_head)

//入队函数
static inline void enqueue(node_t *list_head, node_t *insert_node)
{
    node_t *pos;

    for(pos=list_head; pos->next != NULL; pos=pos->next);//队尾到文件末尾入队

    pos->next = insert_node;//直接将节点插入到表格最后(注意,这个插入的节点的next值应为NULL,不然逻辑会异常)
}

//销毁队列
void destroy_list(node_t *list_head)
{
    node_t *pos, *next;

    pos = list_head;
   
    do{
        next = pos->next;
        free(pos);
        pos=next;
    }while(pos!=NULL);

}


int main(void)
{
    node_t *src1_list, *src2_list, *new_node;
    node_t *queue_list;
    node_t *get_src1_node, *get_src2_node;
    int i;
    int src1_data[] = {2, 5, 8, 13, 18};
    int src2_data[] = {1, 3, 4, 7, 9, 10, 19};

    src1_list = request_list_node();//第一条栈列表
    src2_list = request_list_node();//第二条栈列表
    queue_list = request_list_node();//第三条队列

	//赋值第一条栈链表
    for(i=sizeof(src1_data)/sizeof(int)-1; i>=0; i--)//逆序的将数组1当中的每个元素放入栈中(实现后入先出的逻辑,这样表格出栈的时候便是按照后入先出的原则从小到大输出)
    {
        new_node = request_list_node();//申请节点内存,并且将其存放进去
        new_node->data = src1_data[i];//将数组的数据存放到新建的节点
        in_stack(src1_list, new_node);//将数据按照栈逻辑存放到第1条链表中
    }
	//第二条sizeof(src2_data)/sizeof(int)数组大小-1=数组有效下表最大值
    for(i=sizeof(src2_data)/sizeof(int)-1; i>=0; i--)//逆序的将数组2当中的每个元素放入栈中(实现后入先出的逻辑,这样表格出栈的时候便是按照后入先出的原则从小到大输出)
    {
        new_node = request_list_node();//申请节点内存,并且将其存放进去
        new_node->data = src2_data[i];//将数组的数据存放到新建的节点
        in_stack(src2_list, new_node);//将数据按照栈逻辑存放到第2条链表中
    }

    show_list_data(src1_list);//打印链表1内容

    show_list_data(src2_list);//打印链表1内容

	//上面是把最后一个数据先插入【挤到后面】，出栈时获取就是数组的第一个值
    get_src1_node = out_stack(src1_list);//先从表格1移除并且获取到一个节点(栈逻辑获取的(也就是表格中最小的那个值))

    get_src2_node = out_stack(src2_list);//先从表格2移除并且获取到一个节点(栈逻辑获取的(也就是表格中最小的那个值))

    while(1)
    {
        
        if(get_src1_node->data < get_src2_node->data)//判断哪个节点比较小,谁小谁插入第三条链表
        {
            //从链表1获取到的节点较小
            enqueue(queue_list, get_src1_node);//将链表1获取到的节点插入到第三条链表(队列入队(先入先出原则))
            get_src1_node = out_stack(src1_list);//重新从链表1中获取节点给get_src1_node这个变量(原先那个已经插入队列了)
        }
        else//从俩表2获取到的节点较小
        {
            enqueue(queue_list, get_src2_node);//将链表2获取到的节点插入到第三条链表(队列入队(先入先出原则))
            get_src2_node = out_stack(src2_list);//重新从链表2中获取节点给get_src2_node这个变量(原先那个已经插入队列了)
        }

        show_list_data(queue_list);//打印第三条链表的数据

        sleep(3);

        //如果上面out_stack函数返回值是NULL,这代表对应的链表已经空了
        if(get_src1_node == NULL)//表格1已经空了
        {
            enqueue(queue_list, get_src2_node);//将先获取出来的表格2节点写入队列中

            while((get_src2_node = out_stack(src2_list))!= NULL)//再将表格2中剩余的节点全部写入链表3里面去(入队)
            {
                enqueue(queue_list, get_src2_node);//将获取的节点数据入队
            }
            break;//完成,退出合并
        }
        else if(get_src2_node == NULL)//表格2已经空了
        {
            enqueue(queue_list, get_src1_node);//将先获取出来的表格1节点写入队列中

            while((get_src1_node = out_stack(src1_list))!= NULL)//再将表格1中剩余的节点全部写入链表3里面去(入队)
            {
                enqueue(queue_list, get_src1_node);//将获取的节点数据入队
            }
            break;
        }

    }
    
    show_list_data(queue_list);//显示栈数据

    return 0;
}
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

第三章 学生信息单向链表完整实现

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

//学生信息结构体
struct student_info{
	char name[4096];
	short age;
	float height;
};


typedef struct list_node{
    struct student_info data;//学生信息结构体数据变量
    struct list_node *next;
}node_t;//链表节点类型

//申请节点空间
node_t *request_link_list_node(void)
{
    node_t *new_node;

    new_node = malloc(sizeof(node_t));
    if(new_node == NULL)
    {
        perror("申请链表节点失败");
        return NULL;
    }

    new_node->next = NULL;

    return new_node;
}
/*
    函数功能:
        将insert_node这个节点插入到refer_node这个节点之后的位置
    参数:
        refer_node:是链表中的任意一个节点
        insert_node:需要插入的节点
    返回值:
        无
*/
static inline void insert_node_link_list(node_t *refer_node, node_t *insert_node)
{
    insert_node->next = refer_node->next;
    refer_node->next = insert_node;
}

//显示数据
void display_link_node_data(node_t *list_head)
{
    node_t *pos;

    printf("链表现有数据:\n");

    for(pos=list_head->next; pos!=NULL; pos = pos->next)
    {
        printf("学生信息:名字=%s, 年龄=%hd, 身高=%.2f\n", pos->data.name, pos->data.age, pos->data.height);
    }

    printf("____________________________\n");
}

//判断链表是否为空
bool is_empty(node_t *head)
{
    return head->next == NULL;
}

/*
    函数功能:
        删除refer_node的下一个节点出链表
    参数:
        refer_node:链表当中的任意一个节点
*/
int remove_list_next_node(node_t *refer_node)
{
    if(is_empty(refer_node))
    {
        fprintf(stderr, "表格已经空了\n");
        return -1;
    }

    node_t *rm_node;//临时指针

    rm_node = refer_node->next;//从前往后删

    refer_node->next = rm_node->next;

    free(rm_node);

    return 0;
}

//销毁链表
void destroy_link_list(node_t *list_head)
{
    /*
    node_t *pos;
    node_t *next;

    for(pos=list_head, next=pos->next; pos!=NULL; pos = next, next=next->next)
    {
        printf("free %d \n", pos->data);
        free(pos);

        if(next == NULL)//如果没有下一个需要销毁的节点,这立即退出
            break;
    }

    */
    node_t *pos;

    while(!is_empty(list_head))
    {
        printf("free %s\n", list_head->next->data.name);
        remove_list_next_node(list_head);//删除指定节点的下一个节点(永远删除头节点的下一个节点)
    }

    free(list_head);//最后将头节点也释放
}


/*
    函数功能:
        寻找指定find_data这个数据值存放的节点
    参数:
        list_heasd:寻找的链表头节点
        find_data:寻找的数据值为多少
    返回值:
        成功返回找到的节点内存地址,失败返回NULL        
*/
node_t *find_link_node(node_t *list_head, const char *find_name)
{
    node_t *pos;//临时指针


    for(pos=list_head->next; pos!=NULL; pos = pos->next)
    {
        if(strcmp(pos->data.name, find_name) == 0)
        {
            return pos;//返回找到的节点
        }
    }

    return NULL;
}


//注册学生信息
int register_student_info(node_t *list_head)
{
	node_t *new_node;

	new_node = request_link_list_node();
	if(new_node == NULL)
	{
		perror("申请内存出错");
		return -1;
	}

	printf("开始注册学生信息:\n");

	printf("请输入学生名字:\n");
	scanf("%s", new_node->data.name);

	printf("请输入学生年龄:\n");
	scanf("%hd", &new_node->data.age);

	printf("请输入学生身高:\n");
	scanf("%f", &new_node->data.height);

	insert_node_link_list(list_head, new_node);


	return 0;
}

//查找学生信息
node_t *find_student_info(node_t *list_head)
{
	char name[16];
	node_t *find_node;

	printf("请输入需要搜索的学生名字\n");

	scanf("%s", name);

	find_node = find_link_node(list_head, name);
	if(find_node != NULL)
	{
		printf("寻找到的学生信息:名字=%s, 年龄=%hd, 身高=%.2f\n", 
			find_node->data.name, find_node->data.age, find_node->data.height);
	}
	else
	{
		printf("找不到该学生信息\n");
	}

	return find_node;
}

//删除学生信息
int remove_student_info(node_t *list_head)
{
	char name[16];
	node_t *prev, *pos;//临时指针

	printf("请输入需要开除的学生名字\n");

	scanf("%s", name);


    for(prev=list_head, pos=list_head->next; pos!=NULL; prev=pos, pos=pos->next)
    {
        if(strcmp(pos->data.name, name) == 0)
        {
            remove_list_next_node(prev);//删除prev的下一个节点，其实就是pos
            return 0;
        }
    }

    fprintf(stderr, "找不到你需要删除的学生信息\n");

    return -1;
}


int main(void)
{
	int input_cmd;
	node_t *list_head;
	

	list_head = request_link_list_node();
	if(list_head == NULL)
		goto request_list_err;


	while(1)
	{
		printf("欢迎进入学生信息系统:\n");
		printf("输入1:录入学生信息\n");
		printf("输入2:打印学生信息:\n");
		printf("输入3:寻找指定学生信息\n");
		printf("输入4:开除指定学生\n");
		printf("输入5:退出整个系统\n");
		scanf("%d", &input_cmd);

		switch(input_cmd)
		{
			case 1:
					register_student_info(list_head);//录入学生信息
					break;
			case 2:
					display_link_node_data(list_head);//打印学生信息
					break;
			case 3:
					find_student_info(list_head);//寻找学生信息
					break;
			case 4:
					remove_student_info(list_head);//删除指定学生信息
					break;
			case 5:
					goto system_exit;
			default:
					break;

		}

	}


system_exit:
	destroy_link_list(list_head);

	return 0;

request_list_err:
	return -1;

}

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285

第四章 单向非循环链表

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

typedef struct list_node{
    int data;
    struct list_node *next;
}node_t;//链表节点类型


node_t *request_link_list_node(void)
{
    node_t *new_node;

    new_node = malloc(sizeof(node_t));
    if(new_node == NULL)
    {
        perror("申请链表节点失败");
        return NULL;
    }

    new_node->next = NULL;

    return new_node;
}
/*
    函数功能:
        将insert_node这个节点插入到refer_node这个节点之后的位置
    参数:
        refer_node:是链表中的任意一个节点
        insert_node:需要插入的节点
    返回值:
        无
*/
static inline void insert_node_link_list(node_t *refer_node, node_t *insert_node)
{
    insert_node->next = refer_node->next;
    refer_node->next = insert_node;
}


void display_link_node_data(node_t *list_head)
{
    node_t *pos;

    printf("链表现有数据:");

    for(pos=list_head->next; pos!=NULL; pos = pos->next)
    {
        printf("%d ", pos->data);
    }

    printf("\n");
}

bool is_empty(node_t *head)
{
    return head->next == NULL;
}

/*
    函数功能:
        删除refer_node的下一个节点出链表
    参数:
        refer_node:链表当中的任意一个节点
*/
int remove_list_next_node(node_t *refer_node)
{
    if(is_empty(refer_node))
    {
        fprintf(stderr, "表格已经空了\n");
        return -1;
    }

    node_t *rm_node;

    rm_node = refer_node->next;

    refer_node->next = rm_node->next;

    free(rm_node);

    return 0;
}

void destroy_link_list(node_t *list_head)
{
    /*
    node_t *pos;
    node_t *next;

    for(pos=list_head, next=pos->next; pos!=NULL; pos = next, next=next->next)
    {
        printf("free %d \n", pos->data);
        free(pos);

        if(next == NULL)//如果没有下一个需要销毁的节点,这立即退出
            break;
    }

    */

    node_t *pos;

    while(!is_empty(list_head))
    {
        printf("free %d\n", list_head->next->data);
        remove_list_next_node(list_head);//删除指定节点的下一个节点(永远删除头节点的下一个节点)
    }

    free(list_head);
}


/*
    函数功能:
        寻找指定find_data这个数据值存放的节点
    参数:
        list_heasd:寻找的链表头节点
        find_data:寻找的数据值为多少
    返回值:
        成功返回找到的节点内存地址,失败返回NULL        
*/
node_t *find_link_node(node_t *list_head, int find_data)
{
    node_t *pos;


    for(pos=list_head->next; pos!=NULL; pos = pos->next)
    {
        if(pos->data == find_data)
        {
            return pos;
        }
    }

    return NULL;
}


/*
    函数功能:
        实现insert_node顺序插入list_head说代表的链表中
    参数:
        list_heasd:寻找的链表头节点
        insert_node:要插入的节点
    返回值:
        无
*/
void sequence_insert_node_to_list(node_t *list_head, node_t *insert_node)
{
    node_t *prev, *pos;

    for(prev=list_head, pos=list_head->next; pos!=NULL; prev=pos, pos=pos->next)
    {
        if(pos->data > insert_node->data)
        {
            break;
        }
    }

    insert_node_link_list(prev, insert_node);

}


int main(void)
{

    int input_value;
    node_t *list_head, *new_node;

    //新建头节点
    list_head = request_link_list_node();
    if(list_head == NULL)
        return -1;
    
    list_head->data = -1;

    while(1)
    {
        scanf("%d", &input_value);

        if(input_value > 0)
        {

            //新建节点
            new_node = request_link_list_node();

            new_node->data = input_value;

            //将节点插入到表格当中
            sequence_insert_node_to_list(list_head, new_node);

            //打印表格当中的数据
            display_link_node_data(list_head);
        }
        else if(input_value < 0)
        {
            //删除头节点之后的节点数据
            remove_list_next_node(list_head);
            //打印表格当中的数据
            display_link_node_data(list_head);
        }
        else
            break;
    }

    //销毁表格
    destroy_link_list(list_head);

    return 0;
}
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214

第五章 单向循环链表【宏函数会玩吗？】

循环代表要收尾相连，一个圈
当头节点的下一个指向自己，就代表没数据了

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

typedef struct list_node{
    int data;
    struct list_node *next;
}node_t;//链表节点类型

//不安全的遍历
#define list_for_each(head, pos)    for(pos=head->next; pos!=head; pos=pos->next)

//安全的遍历
#define list_for_each_safe(head, pos, n)  for(pos=head->next, n=pos->next; pos!=head; pos=n, n=n->next)


node_t *request_link_list_node(void)
{
    node_t *new_node;

    new_node = malloc(sizeof(node_t));
    if(new_node == NULL)
    {
        perror("申请链表节点失败");
        return NULL;
    }

    new_node->next = new_node;

    return new_node;
}
/*
    函数功能:
        将insert_node这个节点插入到refer_node这个节点之后的位置
    参数:
        refer_node:是链表中的任意一个节点
        insert_node:需要插入的节点
    返回值:
        无
*/
static inline void insert_node_link_list(node_t *refer_node, node_t *insert_node)
{
    insert_node->next = refer_node->next;
    refer_node->next = insert_node;
}


void display_link_node_data(node_t *list_head)
{
    node_t *pos;

    printf("链表现有数据:");

    //不安全的遍历方式,可以打印机搜索数据
    //for(pos=head->next; pos!=head; pos=pos->next)
    list_for_each(list_head, pos)
    {
        printf("%d ", pos->data);
    }

    printf("\n");
}

bool is_empty(node_t *head)
{
    return head->next == head;
}

/*
    函数功能:
        删除refer_node的下一个节点出链表
    参数:
        refer_node:链表当中的任意一个节点
*/
int remove_list_next_node(node_t *refer_node)
{
    if(is_empty(refer_node))
    {
        fprintf(stderr, "表格已经空了\n");
        return -1;
    }

    node_t *rm_node;

    rm_node = refer_node->next;

    refer_node->next = rm_node->next;

    free(rm_node);

    return 0;
}

void destroy_link_list(node_t *list_head)
{
    
    node_t *pos;
    node_t *n;

    //安全的遍历方式,可以任意的pos节点
    //for(pos=list_head, n=pos->next; pos!=list_head; pos = n, n=n->next)
    list_for_each_safe(list_head, pos, n)
    {
        printf("free %d \n", pos->data);
        free(pos);
    }

    free(list_head);

}


/*
    函数功能:
        寻找指定find_data这个数据值存放的节点
    参数:
        list_heasd:寻找的链表头节点
        find_data:寻找的数据值为多少
    返回值:
        成功返回找到的节点内存地址,失败返回NULL        
*/
node_t *find_link_node(node_t *list_head, int find_data)
{
    node_t *pos;


    list_for_each(list_head, pos)
    {
        if(pos->data == find_data)
        {
            return pos;
        }
    }

    return NULL;
}


/*
    函数功能:
        实现insert_node顺序插入list_head说代表的链表中
    参数:
        list_heasd:寻找的链表头节点
        insert_node:要插入的节点
    返回值:
        无
*/
void sequence_insert_node_to_list(node_t *list_head, node_t *insert_node)
{
    node_t *prev, *pos;

    for(prev=list_head, pos=list_head->next; pos!=list_head; prev=pos, pos=pos->next)
    {
        if(pos->data > insert_node->data)
        {
            break;
        }
    }

    insert_node_link_list(prev, insert_node);//只有满足插入的数据小于先前的数据，才插入

}


int main(void)
{

    int input_value;
    node_t *list_head, *new_node;

    //新建头节点
    list_head = request_link_list_node();
    if(list_head == NULL)
        return -1;
    
    list_head->data = -1;

    while(1)
    {
        scanf("%d", &input_value);

        if(input_value > 0)
        {

            //新建节点
            new_node = request_link_list_node();

            new_node->data = input_value;

            //将节点插入到表格当中
            sequence_insert_node_to_list(list_head, new_node);

            //打印表格当中的数据
            display_link_node_data(list_head);
        }
        else if(input_value < 0)
        {
            //删除头节点之后的节点数据
            remove_list_next_node(list_head);
            //打印表格当中的数据
            display_link_node_data(list_head);
        }
        else
            break;
    }

    //销毁表格
    destroy_link_list(list_head);

    return 0;
}
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212