【建立单链表：头插法，尾插法；循环列表，带尾指针的循环链表合并（将Tb合并在Ta之后）】

一、单链表的基本操作的实现

1.建立单链表：头插法----元素插入在链表头部，也叫头插法。

1.从一个空表开始，重复读取数据。
2.生成新结点，将读入数据存放到新结点的数据域中。
3.从最后一个结点开始，依次将各结点插入到链表的最前端。

void CreateList(LinkList& L, int n) {
	L = new LNode;
	L->next = NULL;//先创建一个带头结点的单链表
	LinkList p;
	int i;
	for (i = n; i > 0; --i) {
		p = new LNode;//生成新结点p = (LNode*)malloc(sizeof(LNode));
		cin >> p->data;//输入元素值scanf(&p->data);
		p->next = L->next;
		L->next = p;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

2.建立单链表：尾插法----元素插入在链表尾部，也叫尾插法。

1.从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
2.初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。

void CreateList(LinkList& L, int n) {
	L = new LNode;
	L->next = NULL;
	int i;

	LinkList r = L;//尾指针r指向头结点
	for (i = 0; i < n; ++i) {
		LinkList p = new LNode;
		cin >> p->data;//生成新结点，输入元素值
		p->next = NULL;
		r->next = p;//插入到表尾
		r = p;//r指向新的尾结点

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、线性表的链式表示和实现

1.循环列表

循环列表：是一种头尾相连的链表（即：表中的最后一个结点的指针域指向头指针，整个链表形成一个环）。

优点：从表中任一结点出发均可找到表中的其他结点。
注意：由于循环指针没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是他们是否等于头指针。
p != L;
P -> next != L;

头指针表示单循环链表：①找a1的时间复杂度：O（1）；②找an的时间复杂度：O（n）。
注意：表的操作常常在表的首尾进行。
尾指针表示单循环链表：①a1的存储位置：R->next->next;
②an的存储位置是：R。时间复杂度都是O（1）。

2.带尾指针的循环链表合并（将Tb合并在Ta之后）

分析的操作：
①p存表头结点（p=Ta->next）
②Tb表头连接在Ta表尾(Ta->next = Tb->next->next)
③释放Tb表结点(delete Tb->next)
④修改指针(Tb->next = p)

LinkList Connect(LinkList Ta, LinkList Tb) {
	//假设Ta和Tb都是非空的单循环链表
	LinkList p;
	p = Ta->next;//p存表头结点
	Ta->next = Tb->next->next;//Tb表头连接Ta表尾
	delete Tb->next;//释放Tb的头结点
	Tb->next = p;//修改指针
	return Tb;
}
1
2
3
4
5
6
7
8
9