C语言 单向列表 *** 作详解

单链表 *** 作 大纲

链表形式
单项，双向
带头（头节点不存有效数据），不带头
循环，不循环

组合起来有：2x2X2=8种组合方式
本文只讲解单向链表的 *** 作

核心⭐

• TIPS:通过指针的修改，都是通过形参和实参同时指向一块区域，通过形参简介修改实参，而对于形参本身的赋值，删除无法影响到实参本身；若要修改实参本身，只能通过二级指针的方式；
• 如果有可能第一个节点会发生改变，那就要传二级指针（带头节点可以不传）

1-链表的建立

#include
#include
typedef struct _list {
	int num;
	struct _list* next;
}list;
list* build();
int main() {
	list* head;
	head = build();
	Print_Stu_Doc(head);
	system("pause");
	return 0;
}
struct _list* build() {
	int val;
	list* head, * tail;
	head = tail = NULL;
	scanf("%d", &val);
	if (-1 == val) {
		return head;
	}
	while (-1 != val) {
		list* p = (list*)malloc(sizeof(list));
          		p->num = val;
		p->next = NULL;
		if (NULL == head) {
			head = p;
		}
		else tail->next = p;
		tail = p;
		scanf("%d", &val);

	}
	return head;
}

1.1head,tail，p相关问题

head,tail,p属于三个不同的地址，即便三者指向同一区域，三者互不影响；

head=tail=NULL;
head=p; 
tail=p

	p->num = val;
	p->next = NULL;
	if (NULL == head) {
		head = p;
	}
	else tail->next = p;
	tail = p;
	scanf("%d", &val);

由于tail和head同时指向同一个指针域；tail->next所修改的是tail和head同时指向的指针域，也会影响到head->next;

在这里，第一步赋值时候；

head=p; 
tail=p

在这里由于head和tail不是同一指针，所以对tail=p；进行修改不会影响到head;

2-链表的打印

void Print_Stu_Doc(list* head)；
void Print_Stu_Doc(list* head) {
	list * ptr;
	if (head == NULL) {
		printf("No Records\n");
		return;
	}
	for (ptr = head; ptr; ptr = ptr->next)
		printf("%d ", ptr->num);
	printf("\n");
}

3-链表的插入 3.1 尾插法

要改变头指针，传二级指针，不改变头指针，传一级指针

int main() {
     ...........
	list_pushback(&head, 5);
     .......
}
void list_pushback(list** pplist, int val);
void list_pushback(list** pplist, int val) {
	list* newnode = newchain(val);
	if (NULL == *pplist) {//判断是否为空指针
		*pplist = newnode;
	}
	else {
		list* tail = *pplist;
		while (tail->next) {//定位到尾
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

函数：值的传递，并对值进行 *** 作：

一级指针的值：所指向的数据

二级指针的值:所指向的二级指针

3.1.1一级指针无法对空链表进行尾插问题

（实则是函数实参形参问题）

void list_pushback(list* plist, int val) {
	list* newnode = newchain(val);
	if (NULL == plist) {
		plist = newnode;
	}
	else {
		list* tail = plist;
		while (tail->next) {//定位到尾
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

如果使用一级指针，那么当传入的plist为空的时候，对形参plist的修改无法影响到实参，故无法成功尾插;

//当为非空指针的时候，是通过tail指向和实参plist一样的区域，在对tail->next赋值的同时修改了实参plist->next指向区域的值!

当head是空时，我们要让实参head被赋值（newcode），是修改head本身

当head不是空时，我们修改的他next指向的值，是修改head里的指针

3.2 头插法

void list_pushfront(list** pplist, int val)

void list_pushfront(list** pplist, int val) {
	list* newcode = newchain(val);
	newcode->next = *pplist;
	*pplist = newcode;
}

头插法即便头指针是空，也能照场头插；

//newcode->next=*pplist(NULL)

3.3 单项链表的节点后插入

void list_insertafter(list* node, int x);
//链表节点后插入  （对于单向链表，节点前前插需要传头地址，效率低麻烦，多不使用）
void list_insertafter(list* node, int x) {
	assert(node);//断言，防止node是空   
	list *next =newchain(x);
	next->next = node->next;
	node->next = next;
}

4-链表的删除 4.1 尾删法

void list_popback(list**pplist)；

void list_popback(list**pplist) {
	if ( *pplist== NULL)return;
	else if ((*pplist)->next == NULL) {
		free(*pplist);
		*pplist = NULL;
	}
	else {
		list* pre = NULL;
		list* tail = *pplist;
		while (tail->next) {
			pre = tail;
			tail = tail->next;
		}
		free(tail);//动态删除空间
		tail = NULL;
		pre->next = NULL;
	}
}

一级指针无法处理没有节点，或者只有一个节点的情况；

只有一个节点时，不存在pre，故无法通过pre使plist指向NULL；

//形参本身=NULL的修改无法影响到实参

4.2 头删法

void list_popfront(list** pplist);
void list_popfront(list** pplist) {
	if (*pplist == NULL) {
		return;
	}
	else {
		list* next = (*pplist)->next;//保存头节点的下一个地址；
		free(*pplist);              //便于free掉内存
		*pplist = next; //也可以解决*pplist只有一个节点的问题(直接等于*pplist->next(NULL))
	}
}

4.3 单向节点的后删除

void list_popafter(list* node);
//链表节点后删  （对于单向链表，节点前前删需要传头地址，效率低麻烦，多不使用）
void list_popafter(list* node) {
	list* next = node->next;
	if (next) {
		node->next = next->next;
		free(next);
		next = NULL;
	}
}

5-链表的查找

list* list_find(list* head, int x);
list* list_find(list* head, int x) {
	list* cur = head;
	while (cur) {
		if (x == cur->num)return cur;
		cur = cur->next;
	}
	return NULL;
}

5.1查找兼具修改功效

代码如下 👇

list* node = list_find(head, 2);
if (node) {
	printf("找到了\n");//查找兼具修改作用
	node->num = 20;
}
else {
	printf("没找到\n");
}

运行如下👇