链表的学习

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 457 阅读时长 ≈ 2 分钟

相关术语：首节点，尾节点，头节点，头指针，尾指针

1. 链表节点的相关术语

1.1 首节点

第一个有效节点

1.2 尾节点

最后一个有效节点

1.3 头节点

第一个有效节点之前的那个节点

头节点并不存放有效数据

加头节点的目的主要是为了方便对链表的操作

1.4 头指针

指向头节点的指针变量

1.5 尾指针

2. 链表创建示例

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <malloc.h>

//链表节点类型定义
typedef Node
{
    int data; // 数据域
    struct Node *pNext; // 指针域
}NODE, *PNODE;

// 创建链表
PNODE create_list(void)
{
    int len;
    int i;
    int val;
    PNODE pTail;
    
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL) {
        printf("分配失败，程序终止！\n");
        exit(-1);
    }
    
    pTail = pHead;
    pTail->pNext = NULL;
    
    printf("请输入您需要生成的链表节点的个数:\n");
    scanf("%d", &len);
    
    for (i = 0; i < len; i++) {
        printf("请输入第%d个节点的值:", i + 1);
        scanf("%d", &val;);
        
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->data = val;
        pTail->pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;
    }
    
    return pHead;
}

// 遍历链表
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
    
    return;
}

// 链表是否为空
bool is_empty(PNODE pHead)
{
    if (pHead->pNext == NULL) {
        return true;
    } else {
        return false;
    }
}

// 链表长度
int length_list(PNODE pHead)
{
    int len = 0;
    PNODE p = pHead->pNext;
    
    while (p != NULL) {
        len++;
        p = p->pNext;
    }
    
    return len;
}

bool insert_list(PNODE pHead, int position, int data)
{
    
}

bool delete_list(PNODE pHead, int position, int *data_buff)
{
    
}

// 链表排序
void sort_list(PNODE pHead)
{
    int i, j;
    int temp;
    int len = length_list(pHead);
    PNODE p_i, p_j;
    
    for (p_i = pHead->pNext, i = 0; i < len -1; i++, p_i = p_i->pNext) {
        for (p_j = p_i->pNext, j = i + 1; j < len; j++, p_j = p_j->pNext) {
            if (p_i->data > p_j->data) {
                temp = p_i->data;
                p_i->data = p_j->data;
                p_j->pNext = temp;
            }
        }
    }
    return;
}

int main()
{
    PNODE pHead = NULL;
    // create_list()功能：创建一个非循环单链表，并将该链表的头节点的地址赋给pHead
    pHead = create_list();
    traverse_list(pHead);
}

确定一个链表只需要一个参数——头指针