【数据结构】二、线性表：2.单链表的建立（尾插法实例、头插法）

2.6求表长度

//求表的长度(带头结点，但是统计的时候不带头结点的数量)
int Length(LinkList L){
    int len = 0;	//统计表长
    LNode *p=L;
    while (p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}
1
2
3
4
5
6
7
8
9
10

时间复杂度为：O(n)

2.7单链表的建立

如果要把很多个数据元素存到一个单链表中，如何操作？

1. 初始化一个单链表

2. 每次取一个数据元素，插入到表尾/表头

2.7.1尾插法

使用尾插法建立单链表的一个常见应用是在计算机科学中进行数据输入。通过将用户输入的数据逐个添加到链表的尾部，可以方便地保存输入的数据，并在后续处理中使用。

void test(){
    LinkList L;		//声明一个指向单链表的指针
    InitList(L);	//初始化一个空表
    int length=0;	//设置变量length纪录链表长度
    While循环{
        每次取一个数据元素e;
        ListInsert(L, length+1, e)插到尾部;	//按位序插入
        length++;
	} 
1
2
3
4
5
6
7
8
9

当插入1个元素时，while需要循环一次，插入2个元素，while循环1此…插入n个元素，while循环n-1次。 每次都从开头开始之后遍历，循环次数为1+2+3+…+(n-1)。时间复杂度为：O($n^2$)。这种操作，时间复杂度太大，并不是最佳方案。

其实根本没必要每次都从头开始往后寻找， 我们可以设置一个指针r（尾指针），指向表尾，当要在尾部插入一个新的数据元素时，就只需要对r结点做一个后插操作就行了。

//后插操作:在p结点之后插入元素e
bool InsertNode(LNode *p, ElemType e){
	if(p == NULL)
		return false;
	LNode *newNode = (LNode *) malloc(sizeof(LNode));
	if(newNode==NULL)		//内存分配失败
		return false;
    
	newNode->data = e;		//用结点newNode保存数据元素
	newNode->next = p->next;   
	p->next = newNode; 		//将结点newNode连到p之后，完成后插操作
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(n)

尾插法实例：

#include <stdio.h>
#include <stdlib.h>
 
typedef int Elemtype;
//结构体的定义
struct LNode{
    Elemtype data;//数据域，存储数据
    struct LNode *next;//指针域，存储指针,存放后继节点信息
};
typedef struct LNode* LNodePtr;//定义结构体指针型变量，将结构体指针等价于Linklist
typedef struct LNode LNode;

 
//尾插法建立链表
LNodePtr CreateListTail(int n){//输入几个结点
    LNode *p;
    LNode *r;
    int i;

    //新建单链表L
    LNodePtr L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;//头结点
    L->data = 0;//防止脏数据
    r = L;//尾指针等于当前头结点
    
    for(i=0; i<n; i++){
        p = (LNode*)malloc(sizeof(LNode));//每次动态申请一个结构体空间存储
        p->data = i;
        r->next = p;
        r = p;//尾指针后移
    }
    r->next = NULL;
    return L;
}

//链表的遍历输出
void TraverseList(LNodePtr L){
    LNode *p, *x;
    p = L;//将头指针赋值给p
    while(p->next != NULL){
        x = p->next;
        printf("%d\n", x->data);
        p = p->next;
    }
}

int main()
{
    LNodePtr l1 = CreateListTail(5);
    TraverseList(l1);
    return 0;
}
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

0
1
2
3
4

2.7.2头插法

头插法建立单链表的特点是：新节点插入到链表的头部位置，因此建立完成的链表元素顺序是和输入数据集合的顺序相反的，即倒序排列。

对头结点的后插操作，如下所示：

1. 首先定义一个头节点，并将其初始化为空指针。
2. 遍历需要转化为链表的数据集合。
3. 对于数据集合中的每一个元素，创建一个新的节点，并设置其数据域为该元素的值。
4. 将新节点的指针域指向当前头节点，即将新节点插入到链表的头部。
5. 更新头节点为新节点。

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL)		//内存分配失败
		return false;	
	s->data = e;		//用结点s保存数据元素e
	s->next = p->next;
	p->next = s;		//将结点s连接到p之后
	return true；
}
1
2
3
4
5
6
7
8
9
10
11
12