链表的头插法和尾插法

表结构的声明

typedef int ElemType;
typedef struct node //定义链表的结点的结构
{
	ElemType data;//定义链表的数据域
	struct node *next;//定义链表中的指针域
}slink;

头插法

1，从一个空表开始，重复读入数据，生成新结点。
2，将读入数据存放到新结点的数据域中。
3，将新结点插入到当前链表的表头上。
4，直到读入n个元素为止。
现在配上代码

void Headinsert(slink *s,int n) //创造一个头插法的表,结构类型是slink;"n"是这个链表的长度
{
	slink *p;//再定义一个p（其结构与*s一样）
	int i;
	if (n < 1)
	{
		printf("链表的长度有误，请重新输入");
		return;
	}

	s = NULL;//在这里，我把s作为头指针 相当于head =NULL（目的是让头指针为空）
/*---------------------以下内容为核心，务必认真理解！！！----------------   */
	for (i = 1; i <= n; i++)//开始创建单链表
	{
		p = (slink*)malloc(sizeof(slink));
		printf("请输入第%d的数值\n",i);
		scanf_s("%d",&p->data);//输入的值存入到data里面；
		//把头指针里的内容给p的next
		s = p;//再让头指针s 指向p->data（因为在下一次循环中就会把s中的内容，赋值到p—>next） 
	}

我现在输入一下这几个数来演示下：

p->next = s;//把头指针里的内容给p的next

可以看到先输入的数25，在输出的时候变到了最后一个，我们可以这样考虑，头插法相当于你在食堂排队打饭，这时候来个人，突然插队，它插的位置还是第一个。

尾插法

void Tailinsert(slink *s,int n) //创建尾插法
{
	slink *r, *p;
	if (n < 1) 
	{
		printf("链表的长度有误，请重新输入");
		return;
	}
	r = s = (slink*)malloc(sizeof(slink));//创建头结点（注：头插法没有）
	for (int i = 1; i <= n; i++)
	{
		p = (slink*)malloc(sizeof(slink));
		printf("请输入第%d的数值\n",i);
		scanf_s("%d",&p->data);
		r->next = p;//把新声明的值p给 r->next(在这里我们定义的“r”是头结点，因为头结点不能移动所以用的是头结点的另一变量r)
		r = p;//使指针r指向p
	}
	r->next = NULL;//在结束循环后使最后一个结点为NULL；
	
}

尾插法相对简单，理解了头插法，尾插法就很简单了，我现在输入与头插法相同的数据。

可以发现，我们怎么输入的，它就怎么显示，按到我们的顺序来的

总体代码

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

typedef int ElemType;
typedef struct node //定义链表的结点的结构
{
	ElemType data;//定义链表的数据域
	struct node *next;//定义链表中的指针域
}slink;

void Headinsert(slink *s,int n) //创造一个头插法的表,结构类型是slink;"n"是这个链表的长度
{
	slink *p;//再定义一个p（其结构与*s一样）
	int i;
	if (n < 1)
	{
		printf("链表的长度有误，请重新输入");
		return;
	}

	s = NULL;//在这里，我把s作为头指针 相当于head =NULL（目的是让头指针为空）

	for (i = 1; i <= n; i++)//开始创建单链表
	{
		p = (slink*)malloc(sizeof(slink));
		printf("请输入第%d的数值\n",i);
		scanf_s("%d",&p->data);//输入的值存入到data里面；
		p->next = s;//把头指针里的内容给p的next
		s = p;//再让头指针s 指向p->data（因为在下一次循环中就会把s中的内容，赋值到p—>next） 
	}
	printf("该链表内的数据为：\n");
	for (int j = 0; j < n; j++)
	{
		printf("  %d  ", s->data);//显示当前数据
		s = s->next;
	}
	printf("\n");
}
void Tailinsert(slink *s,int n) //创建尾插法
{
	slink *r, *p;
	if (n < 1) 
	{
		printf("链表的长度有误，请重新输入");
		return;
	}
	r = s = (slink*)malloc(sizeof(slink));//创建头结点（注：头插法没有）
	for (int i = 1; i <= n; i++)
	{
		p = (slink*)malloc(sizeof(slink));
		printf("请输入第%d的数值\n",i);
		scanf_s("%d",&p->data);
		r->next = p;//把新声明的值p给 r->next(在这里我们定义的“r”是头结点，因为头结点不能移动所以用的是头结点的另一变量r)
		r = p;//使指针r指向p
	}
	r->next = NULL;//在结束循环后使最后一个结点为NULL；
	for (int j = 0; j < n; j++)
	{
		printf("  %d  ", s->next->data);//在这里我为啥用s->next->data 原因是直接用s->data 的话出现的数据是头结点，头结点没有数值，所以无法显示
		s = s->next;//定位到下个结点
	}
	printf("\n");
}
void selecttion(int button,int n) 
{
	slink s;
	if (button == 1)
	{
		printf("你选择的是头插法\n");
		Headinsert(&s, n);
	}
	else if (button == 2)
	{
		printf("你选择的是尾插法\n");
		Tailinsert(&s, n);
	}
	else
	{
		printf("输入错误指令,请重新输入\n");
		scanf_s("%d",&button);
		selecttion(button,n);
	}
}
int main() 
{
	int n,button;
	char Exit;
	printf("请输入链表的长度n\n");
	scanf_s("%d", &n);
	printf("以哪种方式生成链表？1.头插法 2.尾插法\n");
	scanf_s("%d", &button);
	selecttion(button, n);
	printf("是否退出？y/n\n");
	getchar();
	scanf_s("%c", &Exit);
	if (Exit == 'y')
	{
		exit(0);
	}
	return main();
}

总结

1，了解了尾插法与头插法的区别
2，在写main函数时，发现有些代码，只能在指定的结构完成。
3，我在写代码时，并没有声明head，我用的*s 就拿来代替了head
4，尾插法遍历的时候一定要写成s->next->data 因为他第一个是，空节点，如果运行的话会出现错误，所以要next
--------------------------------------------------------------------------------2020.03.16