2024.7.19 作业_C/C++

1.链表的排序

int list_sort(nodeptr l)
{
	    if(null==l || l->len<=1)
    	{
	 	    printf("排序失败");
        	return -1;
    	}
   
    	int len=l->len+1;
    	nodeptr p;
    	int i,j;
    	for( i=1;i<len;i++)
    	{
        	for( j=0,p=l;j<len-i;j++,p=p->next)
        	{
            		if( p->data > p->next->data )
            		{
                		datatype t=p->data;
                		p->data=p->next->data;
                		p->next->data=t;
            		}
        	}
    	}
	    printf("排序成功\n");
	    return 0;
}

2.链表的反转（递归实现）

// 递归反转链表  
nodeptr list_fz(nodeptr l) 
{  
	    // 基础情况：空链表或只有一个节点  
    	if (l == null || l->next == null) 
	    {  
        	return l;  
    	}  

   	    nodeptr new_l = list_fz(l->next);  

   	    l->next->next = l;  
    	l->next = null;

    	return new_l; 
}

3.链表去重


// 去重函数
int list_dr(nodeptr l) 
{
	 nodeptr current = l;
     nodeptr prev = null;

   	 while (current != null) 
	 {
        	nodeptr runner = l;
        	prev = null;
        	int flag = 0;

        	// 查找当前节点的重复项
        	while (runner != current) 
		    {
            		if (runner->data == current->data) 
			        {
                		flag = 1;
                		break;
            		}
            		prev = runner;
            		runner = runner->next;
        	}

        	if (flag) 
		    {
            		// 如果是重复节点，删除当前节点
            		nodeptr temp = current;
            		if (prev != null) 
			        {
                		prev->next = current->next;
            		} 
			        else 
			        {
                		l = current->next; // 更新头节点
            
			        }
            		current = current->next;
            		free(temp);
        	} 	
		    else 	
		    {
            		current = current->next;
        	}
    	}
}

linklist.h

#ifndef linklist_h

#define linklist_h
#include <myhead.h>

typedef int datatype;

typedef struct node
{
	union
	{
		int len;
		datatype data;
	};

	struct node *next;
}node,*nodeptr;

//创建链表
nodeptr list_create();

//申请节点封装数据函数
nodeptr apply_node(datatype e);

//链表判空
int list_empty(nodeptr l);

//头插
int list_insert_head(nodeptr l,datatype e);

//链表遍历函数
int list_show(nodeptr l);

//通过位置查找节点
nodeptr list_search_pos(nodeptr l,int pos);

//任意位置插入
int list_insert_pos(nodeptr l,int pos,datatype e);

//链表头删
int list_delete_head(nodeptr l);

//任意位置删除
int list_delete_pos(nodeptr l,int pos);

//通过值查找返回位置
int list_search_value(nodeptr l,datatype e);

//链表按位置进行修改
int list_update_pos(nodeptr l,int pos,datatype e);

//链表按值进行修改
int list_update_value(nodeptr l,datatype old_e,datatype new_e);

//将链表进行翻转
void list_reverse(nodeptr l);

//释放链表
void list_destroy(nodeptr l);

//链表排序
int list_sort(nodeptr l);

// 去重函数
int list_dr(nodeptr head);

// 递归反转链表 
nodeptr list_fz(nodeptr l);


#endif

linklist.c

#include "linklist.h"

nodeptr list_create()
{
	nodeptr l=(nodeptr)malloc(sizeof(node));
	if(null==l)
	{
		printf("创建失败\n");
		return null;
	}
	l->len=0;
	l->next=null;
	printf("链表创建成功\n");
	return l;
}

//申请节点封装数据函数
nodeptr apply_node(datatype e)
{
	nodeptr p=(nodeptr)malloc(sizeof(node));
	if(null==p)
	{
		printf("申请失败\n");
		return null;
	}
	p->data = e;
	p->next = null;
	return p;
}

//链表判空
int list_empty(nodeptr l)
{
	return l->next ==null;
}

//头插
int list_insert_head(nodeptr l,datatype e)
{
	if(null==l)
	{
		printf("链表不合法\n");
		return -1;
	}
	nodeptr p = apply_node(e);
	if(null==p)
	{
		return -1;
	}
	p->next=l->next;
	l->next=p;
	
	l->len++;
	printf("头插成功\n");
	return 0;

}

//链表遍历函数
int list_show(nodeptr l)
{
	if(null==l || list_empty(l))
	{
		printf("遍历失败\n");
		return -1;
	}	

	nodeptr q = l->next;
	while(q!=null)
	{
		printf("%d\t",q->data);
		q=q->next;
	}
	putchar(10);
}

//通过位置查找节点
nodeptr list_search_pos(nodeptr l,int pos)
{
	if(null==l || list_empty(l) || pos<0 || pos>l->len)
	{
		printf("查找失败\n");
		return null;
	}
	nodeptr q= l;
	for(int i=0;i<pos;i++)
	{
		q=q->next;
	}
	return q;
}

//任意位置插入
int list_insert_pos(nodeptr l,int pos,datatype e)
{
	if(null==l || pos<=0 ||pos>l->len+1)
	{
		printf("插入失败\n");
		return -1;
	}
	nodeptr p = apply_node(e);
	if(null==p)
	{
		return -1;
	}
	nodeptr q =list_search_pos(l,pos-1);

	p->next=q->next;
	q->next=p;
	
	l->len++;
	printf("插入成功\n");
	return 0;
}


//链表头删
int list_delete_head(nodeptr l)
{
	if(null==l || list_empty(l))
	{
		printf("删除失败\n");
		return -1;
	}
	nodeptr p=l->next;
	l->next=p->next;
	free(p);
	p=null;

	l->len--;
	printf("头删成功\n");
	return 0;
}

//任意位置删除
int list_delete_pos(nodeptr l,int pos)
{
	if(null==l || list_empty(l) || pos<1 || pos>l->len)
	{
		printf("删除失败\n");
		return -1;
	}
	nodeptr q=list_search_pos(l,pos-1);
	nodeptr p=q->next;
	q->next =p->next;
	free(p);
	p=null;

	l->len--;
	printf("删除成功\n");
	return 0;
}

//通过值查找返回位置
int list_search_value(nodeptr l,datatype e)
{
	if(null==l || list_empty(l))
	{
		printf("查找失败\n");
		return -1;
	}

	nodeptr q=l->next;
	for(int index=1;index<=l->len;index++)
	{
		if(q->data==e)
		{
			return index;
		}
		q=q->next;
	}
	printf("没找到\n");
	return -1;
}

//链表按位置进行修改
int list_update_pos(nodeptr l,int pos,datatype e)
{
	if(null==l || list_empty(l) || pos<1 || pos>l->len )
	{
		printf("修改失败\n");
		return -1;
	}

	list_search_pos(l,pos)->data = e;
	printf("修改成功\n");
	return 0;
}

//链表按值进行修改
int list_update_value(nodeptr l,datatype old_e,datatype new_e)
{
	if(null==l || list_empty(l))
	{
		printf("修改失败\n");
		return -1;
	}
	int res = list_search_value(l,old_e);
	if(res == -1)
	{
		printf("没有要修改的值\n");
		return -1;
	}
	list_update_pos(l,res,new_e);
	printf("修改成功\n");
	return 0;

}

//将链表进行翻转
void list_reverse(nodeptr l)
{
	if(null==l || l->len<=1)
	{
		printf("翻转失败\n");
		return;
	}
	nodeptr h = l->next;
	l->next = null;
	nodeptr p = null;
	while(h!=null)
	{
		p=h;
		h=h->next;
		p->next =l->next;
		l->next =p;
	}
	printf("翻转成功\n");
	return;
}

//释放链表
void list_destroy(nodeptr l)
{
	//判断逻辑
    	if(null == l)
    	{
        	return;
    	}

    	//将所有结点进行释放
    	while(!list_empty(l))
    	{
        	//头删
        	list_delete_head(l);
    	}

    	//释放头结点
    	free(l);
    	l = null;

    	printf("释放成功\n");
}




//链表排序
int list_sort(nodeptr l)
{
	if(null==l || l->len<=1)
    	{
	 	printf("排序失败");
        	return -1;
    	}
   
    	int len=l->len+1;
    	nodeptr p;
    	int i,j;
    	for( i=1;i<len;i++)
    	{
        	for( j=0,p=l;j<len-i;j++,p=p->next)
        	{
            		if( p->data > p->next->data )
            		{
                		datatype t=p->data;
                		p->data=p->next->data;
                		p->next->data=t;
            		}
        	}
    	}
	printf("排序成功\n");
	return 0;
}


// 递归反转链表  
nodeptr list_fz(nodeptr l) 
{  
	// 基础情况：空链表或只有一个节点  
    	if (l == null || l->next == null) 
	{  
        	return l;  
    	}  

   	nodeptr new_l = list_fz(l->next);  

   	l->next->next = l;  
    	l->next = null;

    	return new_l; 
} 




// 去重函数
int list_dr(nodeptr l) 
{
	nodeptr current = l;
    	nodeptr prev = null;

   	 while (current != null) 
	 {
        	nodeptr runner = l;
        	prev = null;
        	int flag = 0;

        	// 查找当前节点的重复项
        	while (runner != current) 
		{
            		if (runner->data == current->data) 
			{
                		flag = 1;
                		break;
            		}
            		prev = runner;
            		runner = runner->next;
        	}

        	if (flag) 
		{
            		// 如果是重复节点，删除当前节点
            		nodeptr temp = current;
            		if (prev != null) 
			{
                		prev->next = current->next;
            		} 
			else 
			{
                		l = current->next; // 更新头节点
            
			}
            		current = current->next;
            		free(temp);
        	} 	
		else 	
		{
            		current = current->next;
        	}
    	}
}

main.c

#include"linklist.h"

int main(int argc, const char *argv[])
{
    
	//调用函数创建一个链表
    	nodeptr l = list_create();
    	if(null == l)
    	{
        	return -1;
    	}

    	//调用头插函数
    	list_insert_head(l, 520);
    	list_insert_head(l, 1314);
    	list_insert_head(l, 666);
    	list_insert_head(l, 999);
    
    	//调用遍历函数
    	list_show(l);

    	//调用任意位置插入函数
    	list_insert_pos(l, 1, 100);
   	    list_insert_pos(l, 3, 100);
    	list_insert_pos(l, l->len+1, 100);
    	list_show(l);
	    printf("排序: ");
	    list_sort(l);
	    list_show(l);
	    printf("去重：");
	    list_dr(l);
	    list_show(l);
	    printf("反转：");
	    l->next=list_fz(l->next);
	    list_show(l);
    	return 0;
}

2024.7.19 作业

2024年08月03日 • C/C++ •我要评论

1.链表的排序

2.链表的反转（递归实现）

3.链表去重

linklist.h

linklist.c

main.c

思维导图

相关文章:

（全网最详细攻略）【Crypto++】在Visual studio2022中运行Cryptopp

Blend for Visual Studio 概述

ESP32-WROOM-32E最小开发板编程入门(物联网篇)

C语言：扫雷游戏实现

发表评论


验证码：