C语言链表

head.h

typedef struct Node_s{
	int data; //数据域
	struct Node_s *pNext; //指针域
} Node_t, *pNode_t;

void headInsert(pNode_t *ppHead, pNode_t *ppTail, int data);
void print(pNode_t pHead);
void tailInsert(pNode_t *ppHead, pNode_t *ppTail, int data);
void sortInsert(pNode_t *ppHead, pNode_t *ppTail, int data);
void modify(pNode_t pHead, int findNum, int changeNum);
void listDelete(pNode_t *ppHead, pNode_t *ppTail, int deleteNum);
1
2
3
4
5
6
7
8
9
10
11

main.c

#include 
#include 
#include 
#include "head.h"
int main() {
	pNode_t pHead = NULL;
	pNode_t pTail = NULL;
	int data;
	while (scanf("%d", &data) != EOF) {
		//headInsert(&pHead, &pTail, data);
		//tailInsert(&pHead, &pTail, data);
		sortInsert(&pHead, &pTail, data);
		print(pHead);
	}
	/*int findNum, changeNum;
	while (scanf("%d%d", &findNum, &changeNum) != EOF) {
		modify(pHead, findNum, changeNum);
		print(pHead);
	}*/
	int deleteNum;
	while (scanf("%d", &deleteNum) != EOF) {
		listDelete(&pHead, &pTail, deleteNum);
		print(pHead);
	}
}
//头插法
void headInsert(pNode_t *ppHead, pNode_t *ppTail, int data) {
	//在堆上申请空间，存储链表结点
	pNode_t pNew = (pNode_t)malloc(sizeof(Node_t));
	memset(pNew, 0, sizeof(Node_t));//数据域为0，指针域为NULL
	pNew->data = data;
	if (*ppHead == NULL) {
		*ppHead = pNew;
		*ppTail = pNew;
	}
	else {
		pNew->pNext = *ppHead;
		*ppHead = pNew;
	}
}
//打印链表
void print(pNode_t pHead) {
	pNode_t pCur = pHead;
	while (pCur) {
		printf("%3d", pCur->data);
		pCur = pCur->pNext;
	}
	printf("\n");
}
//尾插法
void tailInsert(pNode_t *ppHead, pNode_t *ppTail, int data) {
	pNode_t pNew = (pNode_t)calloc(1, sizeof(Node_t));
	//使用calloc可以不用执行memset了
	pNew->data = data;
	if (*ppHead == NULL) {
		*ppHead = pNew;
		*ppTail = pNew;
	}
	else {
		(*ppTail)->pNext = pNew;
		*ppTail = pNew;
	}
}
//有序插入
void sortInsert(pNode_t *ppHead, pNode_t *ppTail, int data) {
	pNode_t pNew = (pNode_t)calloc(1, sizeof(Node_t));
	pNew->data = data;
	if (*ppHead == NULL) {
		//插入唯一的结点
		*ppHead = pNew;
		*ppTail = pNew;
	}
	else if (data < (*ppHead)->data) {
		//执行头插法
		pNew->pNext = *ppHead;
		*ppHead = pNew;
	}
	else {
		//存在某个结点，其指针域将要改变指向
		pNode_t pPre = *ppHead;//要修改指针域的结点
		pNode_t pCur = pPre->pNext;//是pPre的后继，pCur所指结点的数据域决定了是否要插入
		//经验：写出每次循环迭代的语句，根据这个语句是否有问题，判断循环的条件是否有问题
        while (pCur) {
			if (pCur->data > data) {
				//插入到中间的位置
				pPre->pNext = pNew;
				pNew->pNext = pCur;
				break;
			}
			pPre = pCur;
			pCur = pCur->pNext;
		}
		//如果退出循环时，pCur为NULL，说明没有找到中间位置，要执行尾插法
		if (pCur == NULL) {
			(*ppTail)->pNext = pNew;
			*ppTail = pNew;
		}
	}
}
//查找和修改
void modify(pNode_t pHead, int findNum, int changeNum) {
	pNode_t pCur = pHead;
	while (pCur) {
		if (pCur->data == findNum) {
			pCur->data = changeNum;
			break;
		}
		pCur = pCur->pNext;
	}
	if (pCur == NULL) {
		fprintf(stderr, "Cannot find the number!\n");
	}
}
//删除
void listDelete(pNode_t *ppHead, pNode_t *ppTail, int deleteNum) {
	pNode_t pCur = *ppHead;//pCur指向待删除的结点，以供后续free
	if (pCur == NULL) {
		fprintf(stderr, "List is empty!\n");
		return;//return 终止本次函数调用
	}
	else if(pCur->data == deleteNum){
		//删除的是第一个结点
		*ppHead = (*ppHead)->pNext;//pCur依然指向原来的pHead pHead后移了
		if (*ppHead == NULL) {
			//删除之后没有结点，意味着删除的是唯一的结点
			*ppTail = NULL;
		}
	}
	else {
		pNode_t pPre = *ppHead;//双指针法，pPre指向要修改指针域的结点
		pCur = pPre->pNext;
		while (pCur) {
			if (pCur->data == deleteNum) {
				//链表结点删除，意味着其前驱结点的指针域改变了指向
				pPre->pNext = pCur->pNext;
				break;
			}
			pPre = pCur;
			pCur = pCur->pNext;
		}
		if (pCur == *ppTail) {
			*ppTail = pPre;
		}
		if (pCur == NULL) {
			fprintf(stderr, "DeleteNum is not found!\n");
			return;
		}
	}
	free(pCur);
	pCur = NULL;
}
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