【数据结构】单链表的相关操作（头插和尾插建立）_带头结点单键表插入

头插法建立单链表

头插法建立一个单链表：每次都是在单链表的头部插入结点，从而建立一个单链表。
带头结点的：就是每次都插在头结点后面的第一个
不带头结点的：就是每次都插在单链表的第一个实际结点上
注意：是建立，从单链表为空状态开始建立，不是在某个位序或者某个结点的前面插入

思路：
1、无论如何，结构体成员和初始化单链表是必做的事情
2、头插法建立：
	(1)调用scanf函数输入新结点的数据域的值
	(2)要给定一个范围，不然永远无法结束输入
	(3)声明一个指针变量s，指向新建的结点，简称s结点
	(4)要给新结点分配存储空间，新结点的数据域就等于刚刚输入的值
	(5)新结点的next指针指向头结点的下一个结点，再让头结点的next指针指向s结点，这样新结点s才能成为
	头结点后面的第一个结点
	(6)然后要再调用scanf函数让用户再输入下一个结点的值，依次循环，知道单链表建立完跳出循环体
	(7)此时返回单链表，那么调用头插法函数，就可以通过在终端输入而建立一个单链表了
3、在main函数中声明一个指针变量L作为单链表的头指针，头指针指向头结点，调用头插建立函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

带头结点的

// 头插法建立单链表（带头结点单链表） 
#include<stdio.h>
#include<stdlib.h>

// 声明单链表结构体成员
typedef struct LNode {
	int data;
	struct LNode *next;	
}LNode, *LinkList;

// 初始化单链表
LinkList initList() {
	LinkList L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL) {
		return NULL;
	}
	L->next=NULL;
	return L;
} 

// 头插法建立
LinkList head_insert(LinkList &L) {
	int value;
	printf("请输入结点值：");
	scanf("%d", &value);
	while(value!=-1) {
		LNode *s=(LNode *)malloc(sizeof(LNode ));
		s->data=value;
		s->next=L->next;
		L->next=s;
		printf("请输入结点值：");
		scanf("%d", &value);
	}
	return L;
}


// 打印单链表 
void printLinkList(LinkList L)
{
    LNode* p = L;
    printf("单链表元素为：");
    while(p)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
}

int main() {
	LinkList L = initList();
	head_insert(L);
	printLinkList(L);
} 
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

不带头结点的

// 头插法建立不带头的单链表
#include<stdio.h> 
#include<stdlib.h>

typedef struct LNode {
	int data;
	struct LNode *next;
}LNode, *LinkList;


// 初始化单链表 
LinkList initList() {
	LinkList L=NULL;
	return L;
} 

// 头插法建立
LinkList head_insert(LinkList &L) {
	int value;
	printf("请输入结点值：");
	scanf("%d", &value);
	while(value!=-1) {
		LNode *s=(LNode *)malloc(sizeof(LNode));
		if(s==NULL) {
			return NULL;
		}
		s->data=value;
		s->next=L;
		L=s;
		printf("请输入结点值：");
		scanf("%d", &value);
	}
	return L;
} 

// 打印单链表
LinkList printLinkList(LinkList &L) {
	LNode *p=L;
	while(p!=NULL) {
		printf("%d\t", p->data);
		p=p->next;
	}
} 

int main() {
	LinkList L=initList();
	head_insert(L);
	printLinkList(L);
}
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

尾插法建立单链表

在单链表的最后一个结点后面插入一个结点，从而建立一个单链表。
带头结点的：第一次插入是在头结点后面插，让头结点的next指针指向新结点，之后的再插入，就是让尾指针
指向的结点的next指针指向新结点
不带头节点的：第一次插入就是让头指针指向插入的这个，之后的再插入，才是让尾结点的指针指向插入的这个
1
2
3
4

带头结点的

// 尾插法建立带头结点的单链表
#include<stdio.h> 
#include<stdlib.h>

// 声明结构体成员
typedef struct LNode {
	int data;
	struct LNode *next;
}LNode, *LinkList;

// 初始化单链表
LinkList initList() {
	LNode *L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL) {
		return L;
	}
	L->next=NULL;
} 

// 尾插建立
LinkList tail_insert(LinkList &L) {
	LNode *tail=L;		// 尾指针，初始时指向头结点 
	int value;
	printf("请输入结点值：");
	scanf("%d", &value);
	while(value!=-1) {
		LNode *s=(LNode *)malloc(sizeof(LNode));
		if(s==NULL) {
			return NULL;
		}
		s->data=value;
		s->next=NULL;
		tail->next=s;
		tail=s;		// s是插入的最后一个结点，当插入完成后，尾指针要指向s结点
		printf("请输入结点值：");
		scanf("%d", &value);
	}
	return L; 
} 

void printLinkList(LinkList L) {
	LNode *p=L;
	while(p!=NULL) {
		printf("%d\t", p->data);
		p=p->next;
	}
}

int main() {
	LinkList L=initList();
	tail_insert(L);
	printLinkList(L);
}
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

不带头结点的

// 尾插法建立不带头的单链表
#include<stdio.h> 
#include<stdlib.h>

typedef struct LNode {
	int data;
	struct LNode *next;
}LNode, *LinkList;

// 初始单链表 
LinkList initList() {
	LNode *L=NULL;
	return L;
} 

// 尾插建立
LinkList tail_insert(LinkList &L) {
	LNode *tail=L;
	int value;
	printf("请输入结点值：");
	scanf("%d",&value);
	while(value!=-1) {
		LNode *s=(LNode *)malloc(sizeof(LNode));
		if(s==NULL) {
			return NULL;
		}
		s->data=value;
		s->next=NULL;
		
		if(L==NULL) {		// 头指针指向空，表示单链表为空，第一个结点由头指针指向 
			L=s;		
		}else {				// 单链表中已有结点，tail指向最后一个结点，就让tail的指向指向新建的s结点即可 
			tail->next=s;
		} 
		
		tail=s;				// 尾指针tail在每次插入完成后都要指向新建的s 
		printf("请输入结点值：");
		scanf("%d",&value);
	}
	return L;
}

void printLinkList(LinkList L) {
	LNode *p=L;
	while(p!=NULL) {
		printf("%d\t", p->data);
		p=p->next;
	}
}

int main() {
	LinkList L=initList();
	tail_insert(L);
	printLinkList(L);
}
 
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