[数据结构与算法] 数据结构与算法学习——关于单链表的一些基本处理

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构与算法学习——关于单链表的一些基本处理 -> 正文阅读

[数据结构与算法]数据结构与算法学习——关于单链表的一些基本处理

先做好准备工作：

1、创建链表的两种方法（尾插法、头插法）：

2、（遍历）输出链表：

3、链表的长度：

4、返回一个链表，由原链表的奇数位置项结点连接而成。创建一个新的链表来实现。

?5、返回一个链表，由原链表的偶数位置项结点连接而成。在原链表上操作。

先做好准备工作：

#include <stdio.h>
#include <stdlib.h>

#define size sizeof(struct Student)

typedef struct Student S;

struct Student{
	int num;
	char *name;
	struct Student *next;
};

1、创建链表的两种方法（尾插法、头插法）：

??????? 这里两种创建方法创建的前驱结点都是有内容的。

// 创建链表		尾插法
S *createListEnd(int *num, char *name[], int len){
	S *head = (S*)malloc(size);		// 指向链表的头，用来返回链表的
	S *p = (S*)malloc(size);
	S *temp = (S*)malloc(size);
	
	for(int i=0; i<len; i++){
		if(i == 0){					// 第一次先固定head
			temp->num = num[i];
			temp->name = name[i];
			temp->next = NULL;
			head = temp;
			p = temp;
		}else{
			temp = (S*)malloc(size);
			temp->num = num[i];		// temp 先创建一个结点，并储存好对应的元素
			temp->name = name[i];
			temp->next = NULL;
			p->next = temp;			// p 再指向temp
			p = p->next;
		}
	}
	return head;
}

// 创建链表  	头插法
S *createListStart(int *num, char *name[], int len){
	S *head = (S*)malloc(size);
	S *temp = (S*)malloc(size);
	
	for(int i=0; i<len; i++){
		if(i == 0){
			head->num = num[i];
			head->name = name[i];
			temp->next = NULL;
			temp = head;
		}else{
			temp = (S*)malloc(size);
			temp->num = num[i];
			temp->name = name[i];
			temp->next = head;
			head = temp;
		}
	}
	return head;
}

2、（遍历）输出链表：

// 输出链表
void outputList(S *L){
	while(L){
		printf("%s %d\n",L->name,L->num);
		L = L->next;
	}
}

3、链表的长度：

还是简单地遍历链表，跟（2）几乎差不多。

// 链表的长度
int length(S *List){	
	int n = 0;
	while(List){
		n++;
		List = List->next;
	}
	return n;
}

4、返回一个链表，由原链表的奇数位置项结点连接而成。创建一个新的链表来实现。

// 取出链表中奇数项结点;	创建一个新的链表来操作
S *selectODD(S *List){
	S *ret = (S*)malloc(size);			// 一开始就指向头，然后就不改变了，最后作为返回值返回
	S *p = (S*)malloc(size);			// 为ret添加结点
	S *temp = (S*)malloc(size);			// 要添加的奇数结点
	S *store = (S*)malloc(size);		// 储存temp后一个结点的地址     用到的方式与sortSmallToBig类似
	
	ret = List;
	temp = List->next;
	p = ret;
	
	p->next = NULL;
	
	while(temp->next != NULL){
		temp = temp->next;
		store = temp->next;
		p->next = temp;
		p = p->next;
		p->next = NULL;
		temp = store;
	}
	
	return ret;
}

?5、返回一个链表，由原链表的偶数位置项结点连接而成。在原链表上操作。

????????一开始调用*List = *(List->next); 直接让原链表的前驱结点为其原来的第二个结点（第一个偶数结点）。如果写成? List = List->next; 就会出错，在main函数中调用完该函数，然后输出链表，会发现前两个结点没有改变（即前驱结点还是那个前驱结点）。关于 *List = *(List->next); 改变原来链表的前驱结点，写了另一个小文章，来提醒一下自己跨过的坑：数据结构与算法学习——C单链表在被调用函数内部能否改变原链表的一个小坑点_六十三岁自学茜佳嘉的博客-CSDN博客。

// 提取出链表中的偶数项结点； 在当前线性表中操作
void selectEven(S *List){
	S *p = (S*)malloc(size);
	S *temp = (S*)malloc(size);
	
	*List = *(List->next);		// 这样才能利用地址 改变原来的值
	
	p = List;
	temp = List->next;
	
	while(temp && temp->next){
		temp = temp->next;
		p->next = temp;
		p = p->next;
		temp = temp->next;
	}
	p->next = NULL;
}

6、从大到小排序链表

??????? 根据结点中的num 即学生的学号来排序；

??????? 类似数组排序的插入排序。不同点是数组的插入排序是两个数还要作位置交换。在这里的链表中，直接把num大的一个结点插入到参照结点前，然后就不用再管那个参照的结点了，其自然地往后移动一个位置，再作为下一次的参照结点。

??????? 这里因为前驱结点也有内容，前驱结点也要作为参照结点，因为有可能后面有比前驱结点大的结点要插入到前驱结点前面，这样的话，提前搞一个空的结点放在原来的前驱结点前面会比较好一点操作。

// 排序 大到小
S *sortBigToSmall(S *List){
	// 像数组的插入排序 第一次搞 搞了六个指针，主要是要开辟一个空的前驱，放到链表前面
	S *ret = (S*)malloc(size);		// 开一个空的前驱只有next的指针
	
	S *p = (S*)malloc(size);
	
	S *p1 = (S*)malloc(size);		//p1 p2往后遍历 p1在后 p2在前
	S *p2 = (S*)malloc(size);
	
	S *max = (S*)malloc(size);		// 存储目前最大项
	
	S *temp = (S*)malloc(size);
	
	ret->next = List;
	p = ret;
	
	while(p->next){			
		p1 = p;
		p2 = p1->next;
		temp = p;
		while(p2){
			if(temp->next->num < p2->num){
				temp = p1;
			}
			p1 = p1->next;
			p2 = p2->next;
		}
		if(temp != p){							// 把找到的最大结点，插入到temp后面
			max = temp->next;
			temp->next = temp->next->next;
			max->next = p->next;
			p->next = max;			
		}
		p = p->next;
	}
	return ret->next;
}

7、从小到大排序链表

??????? 用了另一种插入的方法。

??????? 构造一个含有两个结点的链表，首结点没有内容，第二个结点是原链表的前驱结点（在这里，原链表的前驱结点是有内容的）。然后原链表的前驱变成原来的第二个结点。

??????? 然后从原链表中按顺序不断读出一个结点（就是前驱结点），然后让一个p的指针保留剩余的链表，断开当前这个结点的next。遍历新构造的链表，将该结点插入到合适的位置。再循环，直到原链表中已经没有内容为止（p为空）。

// 排序 小到大
S *sortSmallToBig(S *List){
	S *ret = (S*)malloc(size);			// 创建一个空的前驱 指针指向List开头
	S *pre = (S*)malloc(size);			// 修改后的List的头一个元素，将被取出-》插入
	S *p = (S*)malloc(size);			// 修改后的List，取出头元素后 要保留的剩下部分
	
	S *p1 = (S*)malloc(size);
	S *p2 = (S*)malloc(size);
	
	ret->next = List;					// 空前驱的指针指向List
	pre = List->next;					// pre指向List的第二个节点
	p = pre->next;						// p指向List的第三个节点
	ret->next->next = NULL;				// ret暂时只保留List的第一个结点
	
	while(pre){							//如果List剩余的内容有取出结点
		p1 = ret;						// p1在后和p2在前，遍历ret
		p2 = ret->next;
		while(p2 && p2->num < pre->num){	// 找到合适的位置，将结点插到p1后面
			p2 = p2->next;
			p1 = p1->next;
		}
		pre->next = p2;
		p1->next = pre;
		
		if(p == NULL){						// 没有剩余的内容了
			break;
		}
		pre = p;
		p = p->next;
	}
	return ret->next;
}

? ? ? ? 调用没有返回值的函数来将原链表由小到大按学号排序。

? ? ? ? 算法与上面（6）大致一样?。

// 排序 从小到大,没有返回值
void sortSmallToBig_2(S *L){
	S *emptyHead = (S*)malloc(size);	// 创建一个空的前驱
	S *p1 = (S*)malloc(size);			// 往后遍历的后结点，紧随p2
	S *p2 = (S*)malloc(size);			// 往后遍历的前结点
	S *temp = (S*)malloc(size);			// 先用来保存整个L；再用来保存要往前插的结点的前一个结点
	S *refer = (S*)malloc(size);		// 当前的参照结点  
	S *store = (S*)malloc(size);		// 保存要往前插的结点的后一个结点
	
	*temp = *L;							// 关键性的两步，把L前驱给temp，
	L->next = NULL;						// 然后L变为一个孤立的结点，不然会影响整个函数的最后一步（从新确定原链表的顺序）
	emptyHead->next = temp;
	refer = emptyHead;
	
	while(refer){
		p1 = refer;
		p2 = p1->next;
		temp = (S*)malloc(size);
		temp = refer;
		while(p2){
			if(temp->next->num > p2->num){
				temp = p1;
			}
			p1 = p1->next;
			p2 = p2->next;
		}
		if(temp != refer){
			store = (S*)malloc(size);
			store->num = temp->next->num;
			store->name = temp->next->name;
			store->next = refer->next;
			temp->next = temp->next->next;
			refer->next = store;
		}
		refer = refer->next;
	}
	*L = *(emptyHead->next);			// 该函数没有返回值，用这种方式影响原链表
}

8、快慢指针法，输出链表中间的一个结点。

// 输出链表中间的结点；
// 链表长度为n，n为偶数时，输出n/2位置上的结点；n为奇数，输出n/2+1位置上的结点；
// 快慢指针
void findMiddle(S* List){
	S *p1 = List;
	S *p2 = List->next;
	
	while(p2->next){			// 试探
		p2 = p2->next;			// p2先往后走一步
		if(p2->next){			// 再试探
			p1 = p1->next;		// p1、p2都走一步
			p2 = p2 ->next;
		}else{					// p2只走了一步，可以判断链表的长度是奇数，则让p1走多一步到中间
			p1 = p1->next;
			break;
		}
	}
	printf("%s %d\n",p1->name,p1->num);
}

9、反转链表? 用到三指针法

// 反转链表 
S *reverse(S *List){
	S *p1 = (S*)malloc(size);
	S *p2 = (S*)malloc(size);
	S *p3 = (S*)malloc(size);
	
	if(!List->next){
		return List;
	}else if(!List->next->next){
		p1 = List;
		p2 = List->next;
		p2->next = p1;
		p1->next = NULL;
		return p2;
	}else{						// 三指针法
		p1 = List;
		p2 = List->next;
		p3 = List->next->next;	// p3 保留p2后的一个结点
		
		p2->next = p1;			// 第一遍让第二个结点指向第一个结点，第一个结点指向null
		p1->next = NULL;		// p1的地址原本和list的地址一样，即指向相同，这里p1->next = NULL也导致了原来的list发生改变
		
		while(p3->next){		// 三个指针同时后退 一个结点的位置 
			p1 = p2;
			p2 = p3;
			p3 = p3->next;
			p2->next = p1;
		}
		p3->next = p2;			// 最后一个结点指向前一个结点
		
		return p3;
	}
	
}

10、销毁链表两个方式

// 销毁链表 递归
void clear_a(S *List){
	S* temp = List->next;
	List->next = NULL;
	free(List);
	if(temp){
		clear_a(temp);
	}
}

// 销毁线性表 
void clear_b(S *List){
	S *p = List;
	while(List){
		p = p->next;
		List->next = NULL;
		free(List);
		List = p;
	}
}

在主函数中测试

int main(){
	int num[] = {15,2,1,13,45,3,6,21};
	char *name[] = {"张三","李四","王五","赵六","林七","胡八","许九","郑十"};
	
//	int num[] = {15,2,1};
//	char *name[] = {"张三","李四","王五"};
	
	int len = sizeof(num)/4;
	
	S *list = createListEnd(num, name, len);
	printf("\n尾插法，原链表：\n");
	outputList(list);

//	S *list = createListStart(num, name, len);
//	printf("\n头插法原链表：\n");
//	outputList(list);
	
//	S *rev = reverse(list);
//	printf("\n链表翻转:\n");
//	outputList(rev);
//	printf("\n\n");
//	outputList(list);				// 这里输出的list只有张三，因为调用reverse函数进行翻转之前，使list->next = NULL了

//	S *odd = selectODD(list);
//	printf("\n取出链表的奇数位置的结点\n");
//	outputList(odd);

//	selectEven(list);
//	printf("\n取出链表的偶数位置结点（改变了原链表）\n");
//	outputList(list);

//	printf("\n找到链表的中间结点\n");
//	findMiddle(list);

//	S *list1 = sortSmallToBig(list);
//	printf("\n按num从小到大输出链表：\n");
//	outputList(list1);

//	S *list2 = sortBigToSmall(list);
//	printf("\n按num从大到小输出链表\n");
//	outputList(list2);

//	printf("测试没有返回值的排序方法：\n");
//	sortSmallToBig_2(list);
//	outputList(list);
	
}