单链表的基本操作及各操作对应典题

￡神魔★判官ぃ 2022-03-19 08:24 181阅读 0赞

在单链表中，我们假定每一个节点（结构体）用LinkList表示，一个节点包含一个储存元素的数据域（用名字为data的一维数组表示）和储存后继元素位置的指针域（用next表示）。节点声明如下

typedef struct node
    {
    	int data;			//数据域 
    	struct node *next;			//指针域指向后继结点 
    }LinkList;		//节点

1.建立单链表  
（1）头插法建立单链表：从一个空表开始读取数组中的元素，生成新节点，将读取的数据放到新节点的数据域中，然后将新节点插入到当前链表的头结点之前，直到数据读取结束为止。因为新数据总是被插入到旧数据的前面，因此**头插法会导致打印出来的数据与输入的数据顺序恰好相反**完成建表之后将链表之中的数据依次打印，例程如下:

void creat_list(LinkList **head)		//头插法建表 
    {
    	Linklist s;
    	int i;
    	(*head) = (Linklist)malloc(sizeof(LinkList));		//创建头节点
    	(*head) -> next = NULL;				//头结点指针域置空
    	for(i = 0;i < maxsize;i++) 
    	{
    		s = (Linklist)malloc(sizeof(LinkList));		//新节点申请内存
    		s -> data = i; 		//数据域赋值
    		s -> next = (*head) -> next;	//新节点插在头节点之前 
    		(*head) -> next = s;
    	}
    } 
    	
    void print(Linklist head)			//打印链表中的数据 
    {
    	Linklist s;
     	s = head -> next;			//s指向第一个有数据的节点 
     	while(s)
    		{
    			printf("%d\t", s -> data);	//打印数据 
    			s = s -> next;		//指针后继 
    		}
    }

（2）尾插法建表:与头插法相反，尾插法将新数据插入到原有数据之后，因此避免了头插法的缺陷，采用尾插法建立的链表，输出数据的顺序与输入的顺序相同，输出链表数据部分与头插法一样，例程如下：

void creat_list(Linklist *head)
    {
    	Linklist s, r;
    	int i;
    	(*head)= (Linklist)malloc(sizeof(LinkList));		//创建头节点
    	r = (*head);
    	for(i = 0;i < maxsize;i++)
    	{
    		s = (Linklist)malloc(sizeof(LinkList));		
    		s -> data = i;		//数据域赋值 
    		r -> next = s;		//新节点插入到首节点之前，头结点之后
    		r = s; 					//头结点指向新节点
    	}
    	r -> next = NULL;		//尾节点指针域置空 
    } 
     
    void print(Linklist head)			//打印链表中的数据 
    {
    	Linklist s;
     	s = head -> next;			//s指向第一个有数据的节点 
     	while(s)
    		{
    			printf("%d\t", s -> data);	//打印数据 
    			s = s -> next;		//指针后继 
    		}
    }

2.查找链表中元素值算法：从链表第一个有数据的节点开始向后遍历整个链表，直到有一个数据域的值与所找的值相等为止。

int find(Linklist head, int e)
    {
    	Linklist s =  head -> next;		//s指向第一个数据节点 
    	//int n;
    	while(s && s -> data != e)
    		s = s -> next;
    	if(s == NULL)
    		return 0;
    	else 
    		printf("%d  \n", s -> data);	//打印找到的元素值 
     }

3.插入节点的操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
对应的语句为:s -> next = p -> next;p -> = s;注意：***这两条语句顺序不可以颠倒，如果先执行第二句会导致指向b节点的指针就不存在了，在执行第一句的话相当于执行的是“s -> next = s;”。*** 例如：在有序单链表（从小到大排列），向单链表中插入一个数据元素为X的节点，使得在插入之后链表依然保持有序。算法：从第一个有数据的节点开始向后遍历链表并进行数据比较，找到合适的位置进行插入操作。例程如下：

void insert(Linklist *head, int x)		//递增链表插入 
    {
    	LinkList *s, *pre = *head, *p = pre -> next;
    	s= (Linklist)malloc(sizeof(LinkList));
    	s -> data = x;		//新节点赋值
    	s -> next = NULL;		//新节点指针域先置空 
    	while(p && p -> data < x)
    	{
    		pre = p;
    		p = p -> next;			//两个指针均后移一位 
    	}
    	s -> next = pre -> next;		//插入节点操作 
    	pre -> next = s;
     }

4.删除节点的操作：先在单链表中找到要删除的节点的前驱节点（第i - 1个节点），再删除其后的节点。注：***对于单链表，删除操作一定要有前驱节点***。  
![在这里插入图片描述][2019021522544697.png]  
例题：（1）设计算法删除单链表中第一个值为x的节点。算法如下：

int delete(Linklist *head, int x)
    {
    	LinkList *p = *head, *pre = p -> next;
    	while(p && p -> data != x)
    	{
    		pre = p;
    		p = p -> next;			//两个节点均后移 
    	}
    	if(p)
    	{
    		pre -> next = p -> next;	//找到要删除的节点 
    		free(p);
    		return 1;
    	}
    	else
    		return 0;
    }

（2）有一个带头结点的单链表，设计算法删除其中第1.3.5…即奇数号的节点，算法为：用s遍历链表中为奇数号的节点，用pre指向其前驱节点，以完成删除操作。时间复杂度O（n），空间复杂度O（1）。

void delete_jishu(Linklist *head)
    {
    	Linklist  pre = *head, s = pre -> next;
    	while(s)
    	{
    		pre -> next = s -> next;
    		free(s);			//释放节点
    		pre = pre -> next;	//指向偶数号节点
    		if(!pre)
    			break;
    		s = pre -> next;	//指向奇数节点 
    	} 
    }

（3）删除并释放带有头结点的链表中的所有节点，用两个结构指针来遍历链表，并进行同步后移和释放节点操作。例程如下：

void delete_all(Linklist *head)
    {
    	LinkList *pre = *head;
    	Linklist s = pre -> next;
    	while(s)
    	{
    		free(pre);
    		pre = s;			//pre节点后移一位 
    		s = s -> next;		//p后移一位	 
    	}
    	free(pre);				//最后释放pre节点 
    	puts("删除成功");
    }

（4）设计一个带头结点链表中值大于或等于min、小于或等于max之间的节点，（若存在这样的节点）释放被删除节点的空间，这里给出min和max。算法：用p从第一个有数据的节点开始向后遍历整个链表，若节点p满足删除条件，则进行删除操作并将p下移一个节点。例程如下：

void delete_data(Linklist *head, int min, int max)
    {
    	Linklist post, pre = *head;
    	LinkList *p = pre -> next;
    	while(p)
    	{
    		if(p -> data <= max && p -> data >= min)
    		{
    			post = p -> next;
    			pre -> next = p -> next;		//删除p（满足条件）节点 
    			free(p);
    			p = post;						//p后移至下一个节点 
    		}
    		else
    		{
    			pre = p;
    			p = p -> next;
    		}	
    	}
    }

所有代码如下：（由于顺序问题，直接一起运行有的函数会出错 ）

#include<stdio.h>
    #include<malloc.h>
    #define maxsize 10
    
    typedef struct node
    {
    	int data;			//数据域 
    	struct node *next;			//指针域指向后继结点 
    }LinkList;		//节点 
    
    typedef struct node *Linklist;	//结构指针 
    	
    void creat_list(Linklist *head)
    {
    	Linklist s, r;
    	int i;
    	(*head)= (Linklist)malloc(sizeof(LinkList));		//创建头节点
    	r = (*head);
    	for(i = 1;i <= maxsize;i++)
    	{
    		s = (Linklist)malloc(sizeof(LinkList));		
    		s -> data = i;		//数据域赋值 
    		r -> next = s;		//新节点插入到首节点之前，头结点之后
    		r = s; 					//头结点指向新节点
    	}
    	r -> next = NULL;		//尾节点指针域置空 
    } 
     
    void print(Linklist head)			//打印链表中的数据 
    {
    	Linklist s;
     	s = head -> next;			//s指向第一个有数据的节点 
     	while(s)
    		{
    			printf("%d \t", s -> data);	//打印数据 
    			s = s -> next;		//指针后继 
    		}
    	//printf("链表中此时没有数据"); 
    	puts("");
    }
    
    int find(Linklist head, int e)
    {
    	Linklist s =  head -> next;		//s指向第一个数据节点 
    	//int n;
    	while(s && s -> data != e)
    		s = s -> next;
    	if(s == NULL)
    		return 0;
    	else 
    		printf("查找到的数据为:\t\t%d\n", s -> data);	//打印找到的元素值 
     } 
    
    void insert(Linklist *head, int x)		//递增链表插入 
    {
    	LinkList *s, *pre = *head, *p = pre -> next;
    	s= (Linklist)malloc(sizeof(LinkList));
    	s -> data = x;		//新节点赋值
    	s -> next = NULL;		//新节点指针域先置空 
    	while(p && p -> data < x)
    	{
    		pre = p;
    		p = p -> next;			//两个指针均后移一位 
    	}
    	s -> next = pre -> next;		//插入节点操作 
    	pre -> next = s;
    }
    
    int delete(Linklist *head, int x)
    {
    	LinkList *p = *head, *pre = p -> next;
    	while(p && p -> data != x)
    	{
    		pre = p;
    		p = p -> next;			//两个节点均后移 
    	}
    	if(p)
    	{
    		pre -> next = p -> next;	//找到要删除的节点 
    		free(p);
    		return 1;
    	}
    	else
    		return 0;
    }
    
    void delete_jishu(Linklist *head)
    {
    	Linklist  pre = *head, s = pre -> next;
    	while(s)
    	{
    		pre -> next = s -> next;
    		free(s);			//释放节点
    		pre = pre -> next;	//指向偶数号节点
    		if(!pre)
    			break;
    		s = pre -> next;	//指向奇数节点 
    	} 
    } 
    
    void delete_all(Linklist *head)
    {
    	LinkList *pre = *head;
    	Linklist s = pre -> next;
    	while(s)
    	{
    		free(pre);
    		pre = s;			//pre节点后移一位 
    		s = s -> next;		//p后移一位	 
    	}
    	free(pre);				//最后释放pre节点 
    	puts("删除成功");
    }
    
    void delete_data(Linklist *head, int min, int max)
    {
    	Linklist post, pre = *head;
    	LinkList *p = pre -> next;
    	while(p)
    	{
    		if(p -> data <= max && p -> data >= min)
    		{
    			post = p -> next;
    			pre -> next = p -> next;		//删除p（满足条件）节点 
    			free(p);
    			p = post;						//p后移至下一个节点 
    		}
    		else
    		{
    			pre = p;
    			p = p -> next;
    		}	
    	}
    }
    
    int main()
    {
    	Linklist head;
    	creat_list(&head);
    	printf("链表中的原有数据:\t");
    	print(head);
    	find(head, 5);
    	insert(&head, 6);	
    	printf("插入6之后的链表为:\t");
    	print(head);
    	delete(&head, 1);
    	printf("删除1之后的链表为:\t");
    	print(head);
    	delete_jishu(&head);
    	printf("删除奇数项之后的链表为:\t");
    	print(head);
    	delete_all(&head);
    	delete_data(&head, 5, 9);
    	printf("删除一段区间数据之后的链表为\t");
    	print(head);
    		
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220319/485b9a04958a4dccbb2cfd3d4da4aff4.png
[2019021522544697.png]: /images/20220319/b7d47fd0a6fa49bd9449a202170e365d.png