[数据结构与算法]2021-08-13

小白学算法的感想

今天在B站学习了单链表(头插法,删除,使用递归和迭代的方式反转链表,打印链表),下面是我的代码以及我的一些理解

其次我认为递归就是无限套娃,并且将原来的循环重复的地方单独拿出来封装成一个函数并且设置停止运行的条件,然后在函数中再次调用该函数达到和循环一样的作用
刚刚开始学习,如果有不足的地方请大家指出

#include<stdio.h>
#include <malloc.h>

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

struct Node* head;
//头插法
void Insert(int data) {
	//创建要插入的节点
	struct Node* insert = (struct Node*)malloc(sizeof(struct Node));
	insert->data = data;
	insert->next = head;
	head = insert;
}

//在任意位置插入
void InsertByOrder(int data, int location) {
	//创建要插入的节点
	struct Node* insert = (struct Node*)malloc(sizeof(struct Node));
	insert->data = data;
	if (location == 1) {
		insert->data = data;
		insert->next = head;
		return;
	}
	//创建临时节点temp从head开始遍历链表
	struct Node* temp = head;
	for (int i = 0; i < location - 2; i++) {
		temp = temp->next;
	}
	insert->next = temp->next;
	temp->next = insert;
}

//在任意位置删除节点
void Delete(int location) {
	//创建临时节点temp从head开始遍历链表
	struct Node* temp1 = head;
	if (location == 1) {
		head = temp1->next;
		free(temp1);
		return;
	}
	for (int i = 0; i < location - 2; i++) {
		temp1 = temp1->next;
	}
	//在创建一个临时节点记录要删除的节点存储的下一个节点的位置
	struct Node* temp2 = temp1->next;
	temp1->next = temp2->next;
	free(temp2);
}
//用迭代的方式反转链表
struct Node* Reserve1(struct Node* head) {
	//创建临时节点temp从head开始遍历链表
	struct Node* temp = head;
	//要想反转链表就要让每个节点储存下一个节点地址的next指向上一个节点的地址,所以创建一个新节点来记录当前节点位置
	struct Node* prev = NULL;
	//在创建一个新节点记录当前节点存储的下一个节点的地址
	struct Node* next = NULL;
	while (temp != NULL) {
		//记录现在的节点的next指针指向的地址
		next = temp->next;
		//现节点的next指针指向上一个节点
		temp->next = prev;
		//让prev指向temp,下次循环时下个节点的next指针就可以指向当前节点
		prev = temp;
		temp = next;
	}
	head = prev;
	return head;
}
//用递归的方式反转链表
void Reserve2(struct Node* p) {
	if (p->next == NULL) {
		head = p;
		return;
	}
	//递归调用
	Reserve2(p->next);
	//创建节点指向下一个节点
	struct Node* temp1 = p->next;
	//使现在的节点next指针为空
	p->next = NULL;
	//使下一个节点的next指向现在的节点
	temp1->next = p;

}
//打印链表(迭代)
void Print1() {
	//计数器
	int count = 0;
	//创建临时节点temp从head开始遍历链表
	struct Node* temp = head;
	
	//遍历链表各个节点并输出
	while (temp != NULL) {
		count++;
		printf("该链表第%d个元素为:%d\n",count, temp->data);
		temp = temp->next;
	}
}
//打印链表(递归)
void Print2(struct Node* p) {
	if (p == NULL) {
		printf("\n");
		return;
	}
	
	printf("%d\n", p->data);
	Print2(p->next);
}

int main(void) {
	head = NULL;
	Insert(0);
	Insert(2);
	Insert(8);
	Insert(5);
	InsertByOrder(4, 2);
	printf("反转前的链表为:\n");
	Print1();
	//递归反转链表
	Reserve2(head);
	printf("反转后的链表为:\n");
	//迭代打印
	Print1();
	//递归打印
	Print2(head);
}