c语言单向链表和双向链表的操作

浅浅的花香味﹌ 2023-07-24 14:36 49阅读 0赞

1，单向链表

#include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    typedef struct student
    {
        int num;//学号
        char name[10];//姓名
        struct student *next;//指针域
    }STU;
    
    
    void print_help()
    {
    
        puts("****************************");
        puts("1.插入学生信息");
        puts("2.遍历学生信息");
        puts("3.查找学生信息");
        puts("4.删除学生信息");
        puts("5.按学号排序");
        puts("6.逆序排序");
        puts("7.查看帮助信息");
        puts("8.退出管理系统");
        puts("9.清空学生信息");
        puts("****************************");
    
        return ;
    }
    
    
    void link_insert(STU **p_head, STU *p_new)
    {
        STU *p_mov = *p_head;
        if (*p_head == NULL)//空链表时
        {
        	*p_head = p_new;
    	p_new->next = NULL;
        }	
        else//有一个或以上链表时
        {
    	while (p_mov->next != NULL)
    	{
    	    p_mov = p_mov->next;
    	}
    	p_mov->next = p_new;
    	p_new->next = NULL;
        }
    }
    
    void link_print(STU *head)
    {
        STU *p_mov = head;
        while(p_mov != NULL)
        {	
    	printf("%d %s",p_mov->num, p_mov->name);
    	p_mov = p_mov->next;
    	printf("\n");
        }
    }
    
    STU *link_search(STU *head, int num)
    {
        STU *p_mov = head;
        while(p_mov->num != num && p_mov->next != NULL)
        {  	     
    	p_mov = p_mov->next;
        }
        if(p_mov->next == NULL && p_mov->num != num)
        {
    	return NULL;
        }
        else
        {
    	head = p_mov;
    	return head;
        }	
    }
    
    void link_del(STU **head, int num)
    {
        STU *p_mov = *head, *pf = *head;
        while(p_mov->num != num && p_mov->next != NULL)
        {  	
    	pf = p_mov;	
    	p_mov = p_mov->next;
        }
        if(p_mov->num == num )
        {
    	if(pf == p_mov)
    	{
    	    *head = p_mov->next;
    	}
    	else
    	{
    	    pf->next = p_mov->next;
    	}
    	free(p_mov);
        }
        else
        {
    	puts("没有要删除的学生！");
        }
    }
    
    void link_swap(STU *pf, STU *pb)
    {
        
        STU temp;
        temp = *pf;
        *pf = *pb;
        *pb = temp;
        //交换指针
        temp.next = pf->next;
        pf->next = pb->next;
        pb->next = temp.next;
    }
    
    STU *link_order(STU *head)
    {
        STU *pf,*pb;
        pf = head;
    
        while(pf->next != NULL)
        {
    	pb = pf->next;
    	while(pb != NULL)
    	{
    	    if(pf->num > pb->num)
    	    {
    		link_swap(pf,pb);
    	    }
    	    else if (pf->num == pb->num)//如果学号相同再比名字字母
    	    {
    		if (*(pf->name) > *(pb->name))
    		{
    		    link_swap(pf,pb);
    		}
    	    }
    	    pb = pb->next;
    	}
    	pf = pf->next;
        }
        return head;
    }
    
    STU *link_reverse(STU *head)
    {
        STU *pb, *pf = head, *ps;
        pb = pf->next;
        while(pb != NULL)
        {
    	ps = pb->next;
    	pb->next = pf;
    	pf = pb;
    	pb = ps;
        }
        head->next = NULL;
        head = pf;
        return head;
    }
    
    STU *link_free(STU *head)
    {
        STU *pf,*pb;
        pf = head;
        while(pf != NULL)
        {
    	pb = pf->next;
    	free(pf);
    	pf = pb;
        }
        head = pf;
        return head;
    }
    
    int main(void)
    {
        int option, num,i=0;
        STU *head = NULL, *p_new= NULL, *ps = NULL; 
        print_help();
        while(1)
        {
    	puts("请输入需要的选项：");
    	scanf("%d",&option);
    	switch(option)
    	{
    	    case 1://插入学生
    		puts("请输入插入学生的个数:");
    		scanf("%d",&num);
    		for(i=0; i<num; i++)
    		 {
    		    puts("请输入学号  姓名");
    		    p_new = (STU*)malloc(sizeof(STU));//申请新的节点
    		    scanf("%d %s",&p_new->num, p_new->name);//给新申请的节点赋值	
    		    link_insert(&head,p_new);
    		 }
    		break;
    	    case 2://遍历学生
    		link_print(head);
    		break;
    	    case 3://查找学生
    		printf("请输入要查找学生的学号：");
    		scanf("%d",&num);
    		if (head == NULL)
    		{
    		    puts("对不起!没有学生信息!");
    		}
    		else
    		{
    		    ps = link_search(head,num);
    		    if (ps == NULL)
    		    {
    			puts("没有找到您要查找的学生！");
    		    }	
    		    else
    		    {
    			printf("%d %s\n", ps->num,ps->name);
    		    }
    		}   
    		break;
    	    case 4://删除
    		puts("请输入要删除的学生学号：");
    		scanf("%d",&num);
    		if(head == NULL)
    		{
    		    puts("对不起！没有学生信息!");
    		}
    		else
    		{
    		    link_del(&head,num);
    		}
    		break;
    	    case 5://排序
    		if(head == NULL)
    		{
    		    puts("对不起，没有学生信息！");
    		}
    		else
    		{
    		    head = link_order(head);
    		}
    		break;
    	    case 6://逆序
    		if(head == NULL)
    		{
    		    puts("对不起，没有学生信息！");
    		}
    		else
    		{
    		    head = link_reverse(head);
    		}
    		break;
    	    case 7://帮助
    		print_help();
    		break;
    	    case 8://退出
    		if(head == NULL)
    		{
    		    puts("链表清空！");
    		}
    		else
    		{
    		    link_free(head);
    		}
    		return 0;
    	    case 9://清空链表
    		head = link_free(head);
    		break;
    	}
        }
    
        return 0;
    }

2.双向链表

#include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    #define BLOCK 1//0表示采用文本文件，1表示采用二进制文件
    #define BLOCK_NAME "data.bin"//二进制文件
    #define TXT_NAME   "data.txt"//文本文件
    typedef struct student
    {
        int num;//学号
        char name[10];//姓名
        struct student *front;//前指针
        struct student *next;//后针域
    }STU;
     
    void print_help()
    {
     
        puts("****************************");
        puts("1.插入学生信息");
        puts("2.遍历学生信息");
        puts("3.查找学生信息");
        puts("4.删除学生信息");
        puts("5.按学号排序");
        puts("6.逆序排序");
        puts("7.查看帮助信息");
        puts("8.保存退出管理系统");
        puts("9.退出管理系统");
        puts("10.清空学生信息");
        puts("****************************");
     
    }
     
    void link_insert(STU **head, STU *p_new)//创建链表
    {
        STU *pb, *pf = *head;
        if (*head == NULL)//空链表时
        {
        	*head = p_new;
    		p_new->next = *head;
    		p_new->front = *head;
        }	
        else//有一个或以上链表时
        {
    		pb = pf->next;
    		pf->next = p_new;
    		p_new->next = pb;
    		p_new->front = pf;
    		pb->front = p_new;
        }
    }
     
    STU *loader_data(STU *head)//加载链表
    {
    	STU *p_new;
    	FILE *fp = NULL;
    #if BLOCK 
    	fp = fopen(BLOCK_NAME,"rb");
    #else
    	fp = fopen(TXT_NAME,"rt");
    #endif	
    	if(fp == NULL)
    	{
    		perror("");//打印错误信息
    		return NULL;
    	}
    	// printf("%d:len = %ld\n",__LINE__,ftell(fp));
    	// fseek(fp,sizeof(STU)*2,SEEK_SET);//设置文件内容偏移
    	// printf("%d:len = %ld\n",__LINE__,ftell(fp));
    	while(feof(fp) == 0)//判断文件内容有没有结束
    	{
    		p_new = (STU*)malloc(sizeof(STU));//申请新的节点，sizeof()里应该是结构本的大小
    #if BLOCK	//以fread或fscanf方式读取
    		fread(p_new,sizeof(STU),1,fp);	//给新申请的节点赋值
    #else		
    		fscanf(fp,"%d %s",&(p_new->num), p_new->name);//给新申请的节点赋值
    #endif		
    		if (feof(fp) == 0)
    			link_insert(&head,p_new);//创建链表
    	}
    	fclose(fp);
    	return head;
    }
     
    void link_print(int line, STU *head)//打印链表
    {
    	STU *p_mov = head;
        if (head == NULL)
        {
    		return;
        }
    	while (p_mov->next != head)
    	{
    		printf("%d:%d %s\n",line,p_mov->num,p_mov->name);
    		p_mov = p_mov->next;
    	}
    	printf("%d:%d %s\n",line,p_mov->num, p_mov->name);
    }
     
    STU *link_search(STU *head, char *name)//查找信息
    {
        STU *p_mov = head;
        if (head == NULL)
        {
    		return NULL;
        }
        else
        {
    		while(p_mov->next !=head)
    		{
    			if(strcmp(p_mov->name, name) == 0)
    			{
    		//return p_mov;
    			break;
    			}
    			p_mov = p_mov->next;
    		}
    	if(strcmp(p_mov->name, name) == 0)
    	{
    	    return p_mov;
    	}
    	else 
    	{
    	    return NULL;
    	}
        }
    }
     
    STU *link_del(STU *head, char *name)//删除信息
    {
        STU *p_mov = head;
        if (head == NULL)//链表为空
        {
    		puts("没有学生信息！");
    		return NULL;
        }    
    	while(p_mov->next != head)//查找名字
    	{
    		if(strcmp(p_mov->name,name) == 0)
    		{
    			break;
    		}
    		p_mov = p_mov->next;	    
    	}
    	if(strcmp(p_mov->name,name) == 0)//找到了
    	{
    		if(p_mov != head)//删除的不是头节点
    		{
    			p_mov->front->next = p_mov->next;
    			p_mov->next->front = p_mov->front;
    		}
    		else//删的就是头节点
    		{
    			if(p_mov->next == head)//只有一个节点
    				head = NULL;
    			else//一个以上节点
    			{
    				head = p_mov->next;
    				p_mov->front->next = p_mov->next;
    				p_mov->next->front = p_mov->front;
    			}
    		}
    		free(p_mov);
    	}
    	else//没有找到
    	{
    		puts("没有你要删除的学生！\n");
    	}
    	return head;
    }
     
    void link_swap(STU *pf, STU *pb)//交换函数
    {
        
        STU temp;
        temp = *pf;
        *pf = *pb;
        *pb = temp;
        //交换指针
        temp.next = pf->next;
        pf->next = pb->next;
        pb->next = temp.next;
    	temp.front = pf->front;
    	pf->front = pb ->front;
    	pb->front = temp.front;
    }
     
    STU *link_order(STU *head)//按学号排序
    {
        STU *pf,*pb;
        pf = head;
     
        while(pf->next != head)
        {
    		pb = pf->next;
    	while(pb != head)
    	{
    		if(pf->num > pb->num)
    		{
    			link_swap(pf,pb);
    	    }
    	    else if (pf->num == pb->num)//如果学号相同再比名字字母
    	    {
    			if (*(pf->name) > *(pb->name))
    			{
    				link_swap(pf,pb);
    			}
    	    }
    	    pb = pb->next;
    	}
    	pf = pf->next;
        }
        return head;
    }
     
    STU *link_reverse(STU *head)//链表逆序
    {
        STU *pb, *pf = head, *ps;
        pb = pf->next;
        while(pb != head)
        {
    	ps = pb->next;
    	pb->next = pf;
    	pf->front = pb;
    	pf = pb;
    	pb = ps;
        }
    	pf->front = head;
        head->next = pf;
        head = pf;
        return head;
    }
     
    STU *link_free(STU *head)//链表释放
    {
        STU *pf = head;
    	if (head != NULL)
    	{
    		return NULL;
    	}
        while(pf->next != head)
        {
    		pf = pf->next;
    		free(pf->front);
        }
    	free(pf);
        return NULL;
    }
     
    int get_int(void)//验证输入的类型是否是整数
    {
    	int input;
    	char ch;
    	while (scanf("%d",&input) != 1 )
    	{
    		// while ((ch = getchar()) != '\n')//处理错误的输入
    		// {
    			// putchar(ch);//把缓冲区里的内容输出	
    			// setbuf(stdin, NULL);//把缓冲区里的内容清空
    		// }
    		scanf("%*[^\n]%*c");//把缓冲区里的内容清空
    		printf("输入有误.\n请重新输入一个的整数：");
    	}
     
    	return input;
     
    }
     
    void save_to_file(STU *head)//保存到文件
    {
    	STU *pb = head;
    	FILE *fp = NULL;
    	if(head == NULL)
    		return;
    #if BLOCK //以那种方式保存
    	fp = fopen(BLOCK_NAME,"wb");
    #else
    	fp = fopen(TXT_NAME,"wt");
    #endif	
    	if(fp == NULL)
    	{
    		perror("");//打印错误信息
    		return;
    	}
    	while (pb->next != head)//遍历链表存入文件
    	{
    #if BLOCK	//以那种方式保存
    		fwrite(pb,sizeof(STU),1,fp);
    #else		
    		fprintf(fp,"%d\t%s\n",pb->num,pb->name);
    #endif	
    		pb = pb->next;
    	}
    #if BLOCK
    	fwrite(pb,sizeof(STU),1,fp);
    #else	
    	fprintf(fp,"%d\t%s",pb->num, pb->name);
    #endif	
    	fclose(fp);
    }
     
    int main(void)
    {
        int option, num = 0 , i = 0;
        char name[10];
        STU *head = NULL, *p_new= NULL, *ps = NULL; 
    	head = loader_data(head);
        while(1)
    	{
    		print_help();
    		puts("请输入需要的选项：");
    		option = get_int();
    		switch(option)
    		{
    		    case 1://插入学生
    				puts("请输入插入学生的个数:");
    				num = get_int();
    				//scanf("%*[^\n]%*c");
    				setbuf(stdin, NULL);
    				for(i=0; i<num; i++)
    				 {
    				    puts("请输入学号  姓名");
    				    p_new = (STU*)malloc(sizeof(STU));//申请新的节点
    				    scanf("%d %s",&(p_new->num), p_new->name);//给新申请的节点赋值	
    				    link_insert(&head,p_new);
    				 }
    				break;
    		    case 2://遍历学生
    				link_print(__LINE__,head);
    				break;
    		    case 3://查找学生
    				printf("请输入要查找学生的姓名：");
    				scanf("%s",name);
    				ps = link_search(head,name);
    				if (ps == NULL)
    				{
    				    puts("没有找到您要查找的学生！");
    				}	
    				else
    				{
    				    printf("%d %s\n", ps->num,ps->name);
    				}
    				break;
    		    case 4://删除
    				puts("请输入要删除的学生姓名：");
    				scanf("%s",name);
    				head = link_del(head,name);
    				break;
    		    case 5://排序
    				if(head == NULL)
    				{
    					puts("对不起，没有学生信息！");
    				}
    				else
    				{
    					head = link_order(head);
    				}
    				break;
    		    case 6://逆序
    				if(head == NULL)
    				{
    					puts("对不起，没有学生信息！");
    				}
    				else
    				{	
    					head = link_reverse(head);
    				}
    				break;
    		    case 7://帮助
    				print_help();
    				break;
    		    case 8://保存退出
    				save_to_file(head);
    				return 0;
    		    case 9://退出
    				return 0;
    		    case 10://清空链表
    				head = link_free(head);
    				break;
    		}
    	}
    		
    	return 0;
    }