尾插建立单链表，C语言输出

本文讲述了使用尾插法建立单链表，并用C语言输出整个单链表的值。第二节使用该算法用链表实现了直接插入排序

1.尾插建立单链表，C语言输出。其中L表示头结点，L->next表示第一个元素

#include
#include
#include 
using namespace std;

typedef struct LNode {//单链表定义
	int data;
	struct LNode* next;
}LNode, * LinkList;

bool InitList(LinkList& L) {//初始化
	L = (LNode*)malloc(sizeof(LNode));//头指针L指向无数据的头结点
	if (L == NULL)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点的next指针域设为NULL
	return true;
}

LinkList List_TailInsert(LinkList& L) {//尾插法建立
	LNode* s;//工作指针
	LNode* r = L;//r做为表尾指针
	int x, i;
	cout << "单链表元素个数：";
	cin >> i;//插入i个元素
	cout << "请输入单链表元素：";
	scanf_s("%d", &x);
	while (1) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		i--;
		if (i == 0)//输完i个，跳出
			break;
		scanf_s("%d", &x);

	}
	r->next = NULL;
	return L;
}

int main() {
	LinkList L;//创建单链表L
	InitList(L);//初始化
	List_TailInsert(L);
	while (L->next) {
		printf("%d ", L->next->data);
		L = L->next;
	}
}
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

运行结果

2.用链表实现直接插入排序【个人想法，非最优】

#include
#include
#include 
using namespace std;
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;

bool InitList(LinkList& L) {//初始化
	L = (LNode*)malloc(sizeof(LNode));//头指针L指向无数据的头结点
	if (L == NULL)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点的next指针域设为NULL
	return true;
}
LinkList List_TailInsert(LinkList& L) {
	LNode* s;//工作指针
	LNode* r = L;//r做为表尾指针
	int x;
	int i = 5;
	scanf_s("%d", &x);
	while (1) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		i--;
		if (i == 0)
			break;
		scanf_s("%d", &x);
		
	}
	r->next = NULL;
	return L;
}

LinkList Sort(LinkList& L) {//排序过程
	if (L) {
		LNode* pre = L->next, * p = L->next->next;//工作指针p，前驱pre
		for (; p; p = p->next, pre = pre->next) {
			LNode* pres = L, * s = L->next;//s从头遍历，找到合适位置插入;pres是s的前驱
			for (; s != p; s=s->next,pres=pres->next) {
				if (p->data < s->data) {
					pre->next = p->next;
					p->next = pres->next;
					pres->next = p;

					pre = p;//pre和p先往前拉一位，此处拉pre
					p = pre->next->next;//p先去压S
				}
			}
			p = pre->next;//此处拉p
		}//因for循环p和pre同时后移
	}
	return L;
}

int main() {
	LinkList L;//创建单链表L
	InitList(L);//初始化
	List_TailInsert(L);
	Sort(L);//排序
	while (L->next) {
		printf("%d ", L->next->data);
		L = L->next;
	}
}
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

运行结果