[数据结构与算法]有空头单链表和无空头单链表

https://blog.csdn.net/songsong2017/article/details/88024883
初学者参照上面博客的图

指针 <- 结点地址
有空头链表

• 头插法创建链表

//编译器vs2019
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>

typedef struct Node {
	int data;
	struct Node* next;
}Node;

//头插法创建链表
Node* head_insert(int n) {
	//创建头结点（注意结构体结点和结构体指针的区别：结构体结点用指针定义但是需要申请空间；结构体指针只需要用指针定义不用申请空间）
	Node* head = (Node*)malloc(sizeof(Node));
	head->next = NULL;

	while (n--) {
		Node* node = (Node*)malloc(sizeof(Node));
		scanf_s("%d", &node->data);//scanf不安全
		node->next = head->next;
		head->next = node;
	}
	return head;

}




void scan_list(Node* l) {
	Node* p = l; //p是指针无需申请空间
	while (p->next) {
		p = p->next;
		printf_s("%d", p->data);
	}
}

int main() {
	int n;
	scanf_s("%d", &n);
	Node* head = head_insert(n);
	scan_list(head);
	return 0;
}

• 尾插法创建链表

Node* tail_insert(int n) {
	//创建头结点
	Node* head = (Node*)malloc(sizeof(Node));

	//定义一个尾指针
	Node* tail = head;
	tail->next = NULL;

	Node* node;
	node = head;//新节点指针指向头指针所指结点地址
	while (n--) {

		node = (Node*)malloc(sizeof(Node));//为新节点申请空间
		scanf_s("%d", &node->data);//scanf不安全；创建新节点

		tail->next = node;//表尾指针所指结点的下一个节点是node
		tail = node;//表尾指针移动到新节点
	}
	tail->next = NULL;//!!!!别忘记了
	return head;
}


void scan_list(Node* l) {
	Node* p = l; //p是指针无需申请空间
	while (p->next) {
		p = p->next;
		printf_s("%d\n", p->data);
	}
}

int main() {
	int n;
	scanf_s("%d", &n);
	Node* head = tail_insert(n);
	scan_list(head);
	return 0;
}

• 增加结点

Node* tail_insert(int n) {
	//创建头结点
	Node* head = (Node*)malloc(sizeof(Node));

	//定义一个尾指针
	Node* tail = head;
	tail->next = 0;

	Node* node;
	node = head;//新节点指针指向头指针所指结点地址
	int num;
	while (n--) {

		node = (Node*)malloc(sizeof(Node));//为新节点申请空间
		scanf_s("%d", &node->data);//scanf不安全；创建新节点
		tail->next = node;//表尾指针所指结点的下一个节点是node
		tail = node;//表尾指针移动到新节点
	}
	tail->next = NULL;//!!!!别忘记了
	return head;
}

/*将n插到pos位*/
void insert_node(int n,int pos, Node* list) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = n;

	//查找pos位置
	Node* p = list; 
	int cnt = 1;
	while (p->next != NULL) {
		p = p->next;
		cnt++;
		if (cnt == pos)break;
	}

	//插入
	node->next = p->next;
	p->next = node;


}

void scan_list(Node* l) {
	Node* p = l; //p是指针无需申请空间
	while (p->next) {
		p = p->next;
		printf_s("%d", p->data);
	}
}

int main() {
	int n;
	scanf_s("%d", &n);
	Node* head = tail_insert(n);
	insert_node(9, 3, head);
	scan_list(head);
	return 0;
}

• 删除节点

/*删除pos位*/
void delete_node(int pos, Node* list) {

	//查找pos位置
	Node* p = list;
	int cnt = 1;
	while (p->next != NULL) {
		p = p->next;
		cnt++;
		if (cnt == pos)break;
	}//p指在了pos位之前

	//删除
	Node* q = p->next;
	p->next = p->next->next;
	free(q);

}

void scan_list(Node* l) {
	Node* p = l; //p是指针无需申请空间
	while (p->next) {
		p = p->next;
		printf_s("%d", p->data);
	}
}

int main() {
	int n;
	scanf_s("%d", &n);
	Node* head = tail_insert(n);
	delete_node(2, head);
	scan_list(head);
	return 0;
}