C 单向链表之动态链表：尾插法

C 单向链表之动态链表：尾插法

尾插法：在尾节点后插入，每插入一个元素，将其作为尾节点。

一、动态链表

静态链表的意义不是很大，主要是因为数据存储在栈上，栈的存储空间有限，不能动态分配。所以链表要实现存储的自由，要动态申请堆里的空间。

二、动态链表的实现

节点和静态链表节点的定义一样：

typedef struct node
{
	int data;             //数据域：存储数据
	struct node * next;   //指针域：指向下一个节点（指向谁，就保存了谁的地址）
}Node;

可将动态链表的结构用如下小火车表示：

实现代码

创建一个动态链表，输入0结束。

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int data;             //数据域：存储数据
	struct node * next;   //指针域：指向下一个节点（指向谁，就保存了谁的地址）
}Node;
Node * createList();
int main()
{
	Node * head = createList();
	Node * pHead = head;
	pHead = pHead->next;
	while (pHead)
	{
		printf("%d\n",pHead->data);
		pHead = pHead->next;
	}
	return 0;
}
Node * createList()
{
	Node *head = (Node*)malloc(sizeof(Node));
	if(NULL == head)
		exit(-1);
	head->next = NULL;
	Node *tmp = head, *ptr;
	int inputData;
	scanf_s("%d", &inputData);
	while (inputData)
	{
		ptr = (Node*)malloc(sizeof(Node));
		if (NULL == ptr)
			exit(-1);
		ptr->data = inputData;
		tmp->next = ptr;
		tmp = ptr;
		scanf_s("%d", &inputData);
	}
	tmp->next = NULL;
	return head;
}

运行结果：

三、程序过程图分析

创建列表

Node * head = createList();

1）创建空链表(假设头结点地址为0x10，后面节点地址依次为0x20,0x30…)

	Node *head = (Node*)malloc(sizeof(Node));
	if(NULL == head)
		exit(-1);
	head->next = NULL;

2)创建尾插法用到的两个指针。指针tmp：指向链表的尾结点（最后一个节点），指针ptr：指向新生成的节点

	Node *tmp = head, *ptr;

3）输入数据，若输入数据不为零，生成节点，保存数据。

    int inputData;
	scanf_s("%d", &inputData);
	while (inputData)
	{
		ptr = (Node*)malloc(sizeof(Node));
		if (NULL == ptr)
			exit(-1);
		ptr->data = inputData;
	}

4）尾插法：每次插入节点时，令tmp指向最后一个节点

	    tmp->next = ptr;//（链接）插入新节点
		tmp = ptr;//令tmp指向最后一个节点

5)继续输入
①如果输入 inputData==0
跳出循环，返回链表头

	tmp->next = NULL;
	return head;

②如果输入inputData!=0，ptr指向生成的新节点，保存数据

 tmp->next = ptr;

tmp = ptr;