有空頭單連結清單和無空頭單連結清單

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;
}