笔记1：C语言指针和通用双向循环链表学习记录

概要

本节是笔记1：C语言的指针和通用双向循环链表学习记录。

指针

野指针

  • 野指针是指指向不可用内存的指针。当指针被创建时，指针不可能自动指向 NULL，这时默认值是随机的，此时指针成为野指针。
  • 当指针被 free 或 delete 释放掉时，如果没有将指针指向 NULL，就会产生野指针，因为释放掉的是指针指向的内存，没有将指针本身释放掉。造成野指针的原因也可能是指针操作超越了变量的作用范围。比如数组越界，避免野指针的方法即使使用完之后释放内存，并将指针赋 NULL。

空指针

  • 空指针是指没有指向任何一个存储单元的指针。

通用双向循环链表

通用双向循环链表可以包含单链表、通用链表、双向链表、循环链表的全部知识，所以只记录学习通用双向循环链表即可。

通用性

  • 指链表中结点包含数据域和指针域，而通用链表的指针域通常用通用的node指针来表示，与该链表本身类型关系不大，只需要包含通用指针域即可。如：(node为通用指针域)
1
2
3
4
5
6
7
//学生结构体
typedef struct student{
    int num;
    char name[20];
    float score;                    
    NODE node;      //通用指针域类型的变量
}STU,*PSTU;

双向性

  • 指针域包含前向指针pre和后向指针next
    1
    2
    3
    4
    5
    6
    //**************指针域************//
    //该结构体是专门的指针域，包含在每个节点之中
    typedef struct node_t{
        struct node_t *pre;              //前向指针
        struct node_t *next;             //后向指针
    }NODE,*PNODE;

循环性

  • 链表尾部结点的next需要指向链表头，而非NULL，形成一个循环，后续初始化链表会有代码体现。

新建和初始化链表

  • 初始化链表就是构造链表头结构体，分配内存。
1
2
3
4
5
6
//******链表********//
/* 构造链表头结构体 */
typedef struct List{
    char *name;
    NODE head;
}LIST,*PLIST;
1
PLIST stu_list;	//新建链表

可以在main函数中直接新建链表让编译器自动为我们分配内存

1
2
3
4
5
6
7
8
9
10
/********************************************************
* Description   : 新建一个链表头部
* @List         ：已分配好内存的链表
* Return        ：无
**********************************************************/
void NewListInit(PLIST List)
{
    List->head.next    = &List->head;  //头部next属性设置为自己
    List->head.pre     = &List->head;  //头部pre属性设置为自己
}

在这里我们可以发现，在建立循环链表的时候使需要把pre和next属性都指向自己的地址，形成循环。

尾插法插入结点

  • 获取链表尾部，此时链表里面只有头结点，所以头结点作为我们的尾部
  • 将被添加结点的next属性指向尾部结点的next属性
  • 将尾部结点的next属性指向被添加结点地址
  • 将被添加结点的pre属性指向尾部结点
  • 将此时被添加结点的next属性指向的结点的pre属性指向被添加结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/********************************************************
* Description   : 添加一个节点至链表尾部
* @pList        ：需要添加节点的链表指针
* @new_node     ：被添加的节点指针
* Return        ：无
**********************************************************/
void AddItemToList(PLIST pList, PNODE new_node)
{
	PNODE last = pList->head.pre;  //找到链表尾部节点
	
	new_node->next  = last->next; //设置新添加节点next属性
	last->next      = new_node;   //设置尾部（当前）节点next属性
	new_node->pre   = last;       //设置新添加节点pre属性
	pList->head.pre = new_node;   //设置新添加节点的next节点pre属性
}

链表中间插入结点

与尾插法的方法一致，只是这里知道被插入结点是位于哪个结点后面，就不需要获取尾部结点了。

1
2
3
4
5
6
7
8
9
10
11
12
13
/********************************************************
* Description   : 插入一个节点至目标节点后面
* @Target       ：目标节点指针
* @new_node     ：被添加的节点指针
* Return        ：无
**********************************************************/
void AddItemAfter(PNODE Target, PNODE new_node)
{
    new_node->next      = Target->next; //设置新添加节点next属性
    Target->next        = new_node;     //设置目标节点next属性
    new_node->next->pre = new_node;     //设置新添加节点的next节点pre属性
    new_node->pre       = Target;       //设置新添加节节点pre属性
}

删除结点

  • 被删除结点左侧结点next属性指向右侧结点
  • 被删除结点右侧结点pre属性指向左侧结点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /********************************************************
    * Description   : 删除一个节点
    * @del_node     ：被删除的节点指针
    * Return        ：无
    **********************************************************/
    void DelItemFromList(PNODE del_node)
    {
        del_node->next->pre     = del_node->pre;
        del_node->pre->next     = del_node->next;
    }

==反推数据域==

根据指针域反推数据域是==通用链表==的核心知识，通用链表只通过node指针域进行连接，每个不同类型的链表都有自己的数据域格式，我们需要通过node反推出数据域的地址才能访问到里面的变量

学生链表：

1
2
3
4
5
6
7
//学生结构体
typedef struct student{
    int num;
    char name[20];
    float score;                    
    NODE node;      //通用指针域类型的变量
}STU,*PSTU;
1
(struct student *)((char *)p - (unsigned int)&((struct student *)0)->node)
  • 我们来分析这行代码，首先是最终值，它是一个 (struct student *)指针,我们的目的就是获取这样一个指针，使他可以访问到student学生结构体的所有信息，如num、name。
  • 我们所拥有的是node结点的地址，因为这可以从链表中获取到。
  • 这行代码中的p就是我们从链表中获取的node结点地址
  • 内存中结构体地址的递增的，所以我们只要获取到student结构体首地址到node属性的地址处递增了多少字节，然后我们再用p减去递增的字节数就可以得到student的首地址了。
  • (struct student *)0)->node这行代码是利用0地址下使用struct student *去访问node属性，为什么是0地址，因为我们把这个指针设置成0地址之后此时node属性的地址就正好是student 结构体中储存node属性递增的字节数了。
  • (unsigned int)&((struct student *)0)->node可看到中间有个取址符号，此时它的地址就是递增字节数，我们把他强转成(unsigned int)告诉编译器进行普通的指针加减运算。
  • (char *)p这里要强转char *告诉编译器进行普通指针加减运算。
  • (struct student *)最后强转成我们想要的student 首地址，接下来就可以通过这个指针访问里边的变量了。

链表排序

使用冒泡排序法，做两层排序，四步走

  • 两个结点，一个比较结点，一个被比较结点。比较结点是外循环，被比较结点内循环

  • 外循环的比较结点固定，然后内循环开始递增，逐个比较。

  • 比较函数后面讲，先关注排序逻辑，我们从小到大排序，比较函数返回小于时不交换，比较函数返回大于时进行交换

  • ==结点交换的实现==：

    • 记录下两个结点的前一个结点地址
    • 将两个结点都删除
    • 结点2插入结点1前一个结点之后，结点1插入结点2前一个结点之后
    • 还需要判断两个结点相邻的情况，相邻情况下需要特殊处理，删除结点之后直接将结点2插入结点1之后即可
      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
      void SortList(PLIST pList)
      {
      	struct node_t *pre1 = &pList->head;	//从链表头开始
      	struct node_t *pre2;				//这个是用来记录上一次比较时被比较数的pre指针
      	struct node_t *cur = pre1->next;	//开始比较的第一个结点
      	struct node_t *next;				//类比数组的索引，冒泡排序的i，j
      	struct node_t *tmp;					//用于交换的中间结点
      		
      	while (cur != &pList->head) //当前比较的目标不是链表尾部
      	{
      		pre2 = cur;
      		next = cur->next;
      		while (next != &pList->head)    //冒泡排序第二层
      		{
      			if (CmpStudentNum(cur, next) == 0)
      			{
      				/* 交换节点 */
      				/* 1. del cur */
      				DelItemFromList(cur);
      				/* 2. del next */
      				DelItemFromList(next);
      				/* 3. 在pre1之后插入next */
      				AddItemAfter(pre1, next);   //pre1记录的是比较数的pre指针
      				/* 4. 在pre2之后插入cur */
      				if (pre2 == cur)            //如果被比较数pre指针等于当前节点的指针,说明两个节点相邻
      					AddItemAfter(next, cur);
      				else
      					AddItemAfter(pre2, cur);
      				
      				/* 5. cur/next指针互换 */
      				tmp = cur;
      				cur = next;
      				next = tmp;				
      			}
      			
      			pre2 = next;            //这个是用来记录上一次比较时被比较数的pre指针
      			next = next->next;      //继续往前比较
      		}
      		
      		pre1 = cur;         //这个是用来记录上一次比较时比较数的pre指针
      		cur = cur->next;    //继续往前比较
      	}
      }

  • 比较函数

1
2
#define container_of(ptr, type, member) \
	(type *)((char *)ptr - (unsigned int)&((type *)0)->member)

宏定义实现前面说的反推数据域操作，实现原理是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/********************************************************
* Description   : 比较两个学生的num属性
* @pre          ：目标节点1
* @next         ：目标节点2
* Return        ：大于时返回0， 小于时返回-1
**********************************************************/
int CmpStudentNum(PNODE pre, PNODE next)
{
	PSTU p;
	PSTU n;
	
	p = container_of(pre, struct student, node);
	n = container_of(next, struct student, node);
	
	if (p->num < n->num)
		return -1;
	else
		return 0;
}

代码很简单，反推出数据域之后比较他们的num参数，根据结果进行返回即可。

完整工程代码

完整工程代码如下，已经过验证，可以正常运行。

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include "stdio.h"
#include "stdlib.h"

#define container_of(ptr, type, member) \
	(type *)((char *)ptr - (unsigned int)&((type *)0)->member)

//**************指针域************//
//该结构体是专门的指针域，包含在每个节点之中
typedef struct node_t{
    struct node_t *pre;              //前向指针
    struct node_t *next;             //后向指针
}NODE,*PNODE;

//******链表********//
typedef struct List{
    char *name;
    NODE head;
}LIST,*PLIST;

//学生结构体
typedef struct student{
    int num;
    char name[20];
    float score;                    
    NODE node;      //通用指针域类型的变量
}STU,*PSTU;

typedef struct teacher              //教师
{
    int num;
    char name[20];
    char subj[20];                  
    NODE node;                     //同上
}TEA,*PTEA;

/********************************************************
* Description   : 新建一个链表头部
* @List         ：已分配好内存的链表
* Return        ：无
**********************************************************/
void NewListInit(PLIST List)
{
    List->head.next    = &List->head;  //头部next属性设置为自己
    List->head.pre     = &List->head;  //头部pre属性设置为自己
}

/********************************************************
* Description   : 添加一个节点至链表尾部
* @pList        ：需要添加节点的链表指针
* @new_node     ：被添加的节点指针
* Return        ：无
**********************************************************/
void AddItemToList(PLIST pList, PNODE new_node)
{
	PNODE last = pList->head.pre;  //找到链表尾部节点
	
	new_node->next  = last->next; //设置新添加节点next属性
	last->next      = new_node;   //设置尾部（当前）节点next属性
	new_node->pre   = last;       //设置新添加节点pre属性
	pList->head.pre = new_node;   //设置新添加节点的next节点pre属性
}

/********************************************************
* Description   : 插入一个节点至目标节点后面
* @Target       ：目标节点指针
* @new_node     ：被添加的节点指针
* Return        ：无
**********************************************************/
void AddItemAfter(PNODE Target, PNODE new_node)
{
    new_node->next      = Target->next; //设置新添加节点next属性
    Target->next        = new_node;     //设置目标节点next属性
    new_node->next->pre = new_node;     //设置新添加节点的next节点pre属性
    new_node->pre       = Target;       //设置新添加节节点pre属性
}

/********************************************************
* Description   : 删除一个节点
* @del_node     ：被删除的节点指针
* Return        ：无
**********************************************************/
void DelItemFromList(PNODE del_node)
{
    del_node->next->pre     = del_node->pre;
    del_node->pre->next     = del_node->next;
}

/********************************************************
* Description   : 链表排序
* @pList        ：目标链表
* Return        ：无
**********************************************************/
int CmpStudentNum(PNODE pre, PNODE next);
void SortList(PLIST pList)
{
	struct node_t *pre1 = &pList->head;	//从链表头开始
	struct node_t *pre2;				//这个是用来记录上一次比较时被比较数的pre指针
	struct node_t *cur = pre1->next;	//开始比较的第一个结点
	struct node_t *next;				//类比数组的索引，冒泡排序的i，j
	struct node_t *tmp;					//用于交换的中间结点
		
	while (cur != &pList->head) //当前比较的目标不是链表尾部
	{
		pre2 = cur;
		next = cur->next;
		while (next != &pList->head)    //冒泡排序第二层
		{
			if (CmpStudentNum(cur, next) == 0)
			{
				/* 交换节点 */
				/* 1. del cur */
				DelItemFromList(cur);
				/* 2. del next */
				DelItemFromList(next);
				/* 3. 在pre1之后插入next */
				AddItemAfter(pre1, next);   //pre1记录的是比较数的pre指针
				/* 4. 在pre2之后插入cur */
				if (pre2 == cur)            //如果被比较数pre指针等于当前节点的指针,说明两个节点相邻
					AddItemAfter(next, cur);
				else
					AddItemAfter(pre2, cur);
				
				/* 5. cur/next指针互换 */
				tmp = cur;
				cur = next;
				next = tmp;				
			}
			
			pre2 = next;            //这个是用来记录上一次比较时被比较数的pre指针
			next = next->next;      //继续往前比较
		}
		
		pre1 = cur;         //这个是用来记录上一次比较时比较数的pre指针
		cur = cur->next;    //继续往前比较
	}
}


/********************************************************
* Description   : 比较两个学生的num属性
* @pre          ：目标节点1
* @next         ：目标节点2
* Return        ：大于时返回0， 小于时返回-1
**********************************************************/
int CmpStudentNum(PNODE pre, PNODE next)
{
	PSTU p;
	PSTU n;
	
	p = container_of(pre, struct student, node);
	n = container_of(next, struct student, node);
	
	if (p->num < n->num)
		return -1;
	else
		return 0;
}

/********************************************************
* Description   : 打印链表
* @pList        ：目标链表
* Return        ：无
**********************************************************/
void PrintList(PLIST pList)
{
	int i = 0;
	
	PNODE node_1 = pList->head.next;      //得到链表头部的next属性
	PSTU p;
	
	while (node_1 != &pList->head)        //如果头部的next不是头部，代表还没有到链表尾部
	{
		p = container_of(node_1, struct student, node);
		printf("person %d: num is %d\r\n", i++, p->num);
		
		/* 后面还有人, 移动到下一个 */
		node_1 = node_1->next;
	}
}

int main(int argc, char *argv[])
{
    PLIST stu_list;
    PSTU stus1,stus2,stus3,stus4,stus5,stus6;

    stu_list = (PLIST)malloc(sizeof(LIST)); //分配内存
    NewListInit(stu_list);                  //初始化链表

    stus1 = (PSTU)malloc(sizeof(STU)); //分配内存
    stus2 = (PSTU)malloc(sizeof(STU)); //分配内存
    stus3 = (PSTU)malloc(sizeof(STU)); //分配内存
    stus4 = (PSTU)malloc(sizeof(STU)); //分配内存
    stus5 = (PSTU)malloc(sizeof(STU)); //分配内存
    stus6 = (PSTU)malloc(sizeof(STU)); //分配内存

    stus1->num = 20;
    stus2->num = 40;
    stus3->num = 30;
    stus4->num = 10;
    stus5->num = 50;
    stus6->num = 100;

    AddItemToList(stu_list, &stus1->node);  //添加进链表尾部，尾插法
    AddItemToList(stu_list, &stus2->node);  //添加进链表尾部，尾插法
    AddItemToList(stu_list, &stus3->node);  //添加进链表尾部，尾插法
    AddItemToList(stu_list, &stus4->node);  //添加进链表尾部，尾插法
    AddItemToList(stu_list, &stus5->node);  //添加进链表尾部，尾插法

    PrintList(stu_list);

    printf("\r\n Del node3\r\n");
    DelItemFromList(&stus3->node);
    PrintList(stu_list);

    printf("\r\n add node1->node6\r\n");
    AddItemAfter(&stus1->node, &stus6->node);
    PrintList(stu_list);

    printf("\r\n Sort List\r\n");
    SortList(stu_list);
    PrintList(stu_list);

    printf("yes!\r\n");
}
笔记1：C语言指针和通用双向循环链表学习记录
http://example.com/2024/08/30/笔记1：C语言的指针和通用双向循环链表学习记录/
作者
John Doe
发布于
2024年8月30日
许可协议