数据结构和算法（二）

小鱼儿 2022-12-13 12:54 131阅读 0赞

作业分析讲解  
======================  
    1.  补充单链表的销毁  
                释放每个节点的堆空间

单链表的基本操作  
==================  
    初始化  
    尾插和中间插入  
    打印  
    删除：有两种常用的思路  
                 思路一： 只用一个指针搞定(删除得不彻底)  
                 思路二： 用两个指针一前一后配合，搞定(推荐)

练习：  
      1.  完善删除的代码(判断删除的节点不存在的情况)  
      2.  利用刚才讲的删除思路，实现单链表的销毁  
                      先把答案弄出来--》成就感 --》摸索优化更好的方法

单向循环链表的基本操作  
=================  
    特点: 在单链表的基础上首尾相接  
    注意： 循环的写法发生改变了  
                while(p->next!=NULL) ---》变成while(p->next!=head)

作业：  
      1. 销毁链表，从前往后写一下  
      2. 利用所学的单链表操作，实现一个简单的图书管理系统，图书管理系统有如下功能：  
                书籍用结构体表示  
                     struct  book  
                    \{  
                              char  name\[20\]; //书名  
                              char  authorname\[20\]； //作者名  
                              float  price;  //价格  
                              int  num; //这本书总的数量  
                    \}；  
                1.  添加书籍  
                2.  删除书籍  
                3.  修改书籍信息  
                4.  查询书籍信息

## 单链表的销毁 ##

#include "myhead.h"
    
    //封装一个结构体表示单链表
    typedef struct siglist
    {
    	int data; //存放真实数据
    	struct siglist *next; //指向下一个节点的指针
    }list,*plist;
    
    //链表的初始化
    plist init_list()
    {
    	//初始化了一个空的头节点(没有存放任何有效数据)
    	plist head=malloc(sizeof(list));
    	head->next=NULL;
    	return head;
    }
    
    //插入数据(尾部插入)
    int insert_tail(int newdata,plist head)
    {
    	//准备一个新的节点
    	plist newnode=malloc(sizeof(list));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	
    	//把新的节点插入到链表的尾部
    	plist p=head;
    	while(p->next!=NULL) //找到尾部
    		p=p->next;  //p=p+1;错误，链表中节点并不是连续(可能连续可能不连续)
    	//插入新的节点
    	p->next=newnode;
    	return 0;
    }
    
    //插入数据，中间插入 把newdata插入到olddata的后面
    int insert_mid(int olddata,int newdata,plist head)
    {
    	//准备好新的节点
    	plist newnode=malloc(sizeof(list));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	
    	//找到olddata节点的位置
    	plist p=head;
    	while(p->next!=NULL)
    	{
    		p=p->next;
    		if(p->data==olddata) //找到了就结束循环
    			break;
    	}
    	//循环结束，并且最后一个节点也不等于olddata，说明没有olddata
    	if(p->next==NULL && p->data!=olddata)
    	{
    		printf("对不起，你要插入的数据 %d 不存在!\n",olddata);
    		return -1;
    	}
    	//把新的节点插入到p的后面
    	newnode->next=p->next;
    	p->next=newnode;
    	return 0;
    }
    
    //单链表删除，只用一个指针(有bug的,删除不干净)
    int remove_list(int deldata,plist head)
    {
    	//找到要删除的节点的前一个节点
    	plist p=head;
    	while(p->next!=NULL)
    	{
    		//if(p->data==deldata)  //p指向的是要删除的节点，不对
    		if(p->next->data==deldata) //p指向的是要删除的节点前面一个
    			break;
    		p=p->next;
    	}
    	//删除p后面的一个节点
    	p->next=p->next->next;  //删除得不够彻底
    	return 0;
    }
    
    //用两个指针删除节点
    int remove_list2(int deldata,plist head)
    {
    	plist q=head;
    	plist p=head->next;
    	int flag=0;
    	//往后一前一后遍历
    	while(p->next!=NULL) //漏掉最后一个节点
    	{
    		if(p->data==deldata)  //把链表中所有重复出现的都删除
    		{
    			flag=1;
    			//删除节点
    			q->next=p->next;
    			p->next=NULL;
    			free(p);
    			p=q->next;
    			continue;
    		}			
    		p=p->next;
    		q=q->next;
    	}
    	//判断最后一个节点,刚才循环漏掉了
    	if(p->data==deldata)
    	{
    		//删除节点
    		q->next=p->next;
    		p->next=NULL;
    		free(p);
    	}
    	//判断deldata不存在的情况
    	if(flag==0)
    	{
    		printf("对不起，没有找到要删除的数据:%d\n",deldata);
    		return -1;
    	}
    	
    	return 0;
    }
    
    //每次删除链表的最后一个节点
    int remove_tail(plist head)
    {
    	plist q=head;
    	plist p=head->next;
    	//往后一前一后遍历
    	while(p->next!=NULL)
    	{
    		//两个指针一前一后挪动
    		p=p->next;
    		q=q->next;
    	}
    	
    	//删除节点
    	q->next=p->next;
    	p->next=NULL;
    	free(p);
    	return 0;
    }
    
    //链表的销毁--》从最后一个节点开始(从后往前)一个个删除
    int destroy_list(plist head)
    {
    	//统计一下链表中节点个数
    	int count=0;
    	plist p=head;
    	while(p->next!=NULL)  
    	{
    		p=p->next;
    		count++;
    	}
    	for(int i=0; i<count; i++) //删除所有的有效节点，头节点没有删除
    		remove_tail(head);	
    }
    
    //链表的销毁--》从前往后一个个删除
    int destroy_list2(plist head)
    {
    	//留给没有写出来的同学
    }
    
    //打印链表
    int show_list(plist head)
    {
    	plist p=head;
    	//循环遍历打印
    	while(p->next!=NULL)  //p的下一个节点不为NULL
    	{
    		p=p->next; //p指向下一个节点
    		printf("我遍历到的节点中数据是:%d\n",p->data);
    	}
    	return 0;
    }
    
    int main()
    {
    	int delnum;
    	//初始化一个头节点
    	plist myhead=init_list();
    	
    	//尾部插入数据
    	insert_tail(999,myhead);
    	insert_tail(999,myhead);
    	insert_tail(999,myhead);
    	insert_tail(999,myhead);
    	
    	//中间插入
    	insert_mid(77,44,myhead);
    	
    	printf("======插入完毕========\n");
    	//打印链表
    	show_list(myhead);
    	
    	//删除某个节点
    	printf("请输入要删除的节点!\n");
    	scanf("%d",&delnum);
    	//remove_list(delnum,myhead);
    	remove_list2(delnum,myhead);
    	printf("======删除完毕========\n");
    	//打印链表
    	show_list(myhead); 
    	
    	//销毁链表
    	destroy_list(myhead);
    	printf("======销毁链表========\n");
    	//打印链表
    	show_list(myhead);
    	free(myhead);
    }

# #

## 单向循环链表的基本操作 ##

#include "myhead.h"
    
    //封装一个结构体表示单向循环链表
    typedef struct siglist
    {
    	int data; //存放真实数据
    	struct siglist *next; //指向下一个节点的指针
    }list,*plist;
    
    //链表的初始化
    plist init_list()
    {
    	//初始化了一个空的头节点(没有存放任何有效数据)
    	plist head=malloc(sizeof(list));
    	head->next=head;
    	return head;
    }
    
    //插入数据(尾部插入)
    int insert_tail(int newdata,plist head)
    {
    	//准备一个新的节点
    	plist newnode=malloc(sizeof(list));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	
    	//把新的节点插入到链表的尾部
    	plist p=head;
    	while(p->next!=head) //找到尾部
    		p=p->next;  //p=p+1;错误，链表中节点并不是连续(可能连续可能不连续)
    	//插入新的节点
    	
    	
    	return 0;
    }
    
    //插入数据，中间插入 把newdata插入到olddata的后面
    int insert_mid(int olddata,int newdata,plist head)
    {
    	//准备好新的节点
    	plist newnode=malloc(sizeof(list));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	
    	//找到olddata节点的位置
    	plist p=head;
    	while(p->next!=NULL)
    	{
    		p=p->next;
    		if(p->data==olddata) //找到了就结束循环
    			break;
    	}
    	//循环结束，并且最后一个节点也不等于olddata，说明没有olddata
    	if(p->next==NULL && p->data!=olddata)
    	{
    		printf("对不起，你要插入的数据 %d 不存在!\n",olddata);
    		return -1;
    	}
    	//把新的节点插入到p的后面
    	newnode->next=p->next;
    	p->next=newnode;
    	return 0;
    }
    
    //单链表删除，只用一个指针(有bug的,删除不干净)
    int remove_list(int deldata,plist head)
    {
    	//找到要删除的节点的前一个节点
    	plist p=head;
    	while(p->next!=NULL)
    	{
    		//if(p->data==deldata)  //p指向的是要删除的节点，不对
    		if(p->next->data==deldata) //p指向的是要删除的节点前面一个
    			break;
    		p=p->next;
    	}
    	//删除p后面的一个节点
    	p->next=p->next->next;  //删除得不够彻底
    	return 0;
    }
    
    //用两个指针删除节点
    int remove_list2(int deldata,plist head)
    {
    	plist q=head;
    	plist p=head->next;
    	int flag=0;
    	//往后一前一后遍历
    	while(p->next!=NULL) //漏掉最后一个节点
    	{
    		if(p->data==deldata)  //把链表中所有重复出现的都删除
    		{
    			flag=1;
    			//删除节点
    			q->next=p->next;
    			p->next=NULL;
    			free(p);
    			p=q->next;
    			continue;
    		}			
    		p=p->next;
    		q=q->next;
    	}
    	//判断最后一个节点,刚才循环漏掉了
    	if(p->data==deldata)
    	{
    		//删除节点
    		q->next=p->next;
    		p->next=NULL;
    		free(p);
    	}
    	//判断deldata不存在的情况
    	if(flag==0)
    	{
    		printf("对不起，没有找到要删除的数据:%d\n",deldata);
    		return -1;
    	}
    	
    	return 0;
    }
    
    //每次删除链表的最后一个节点
    int remove_tail(plist head)
    {
    	plist q=head;
    	plist p=head->next;
    	//往后一前一后遍历
    	while(p->next!=NULL)
    	{
    		//两个指针一前一后挪动
    		p=p->next;
    		q=q->next;
    	}
    	
    	//删除节点
    	q->next=p->next;
    	p->next=NULL;
    	free(p);
    	return 0;
    }
    
    //链表的销毁--》从最后一个节点开始(从后往前)一个个删除
    int destroy_list(plist head)
    {
    	//统计一下链表中节点个数
    	int count=0;
    	plist p=head;
    	while(p->next!=NULL)  
    	{
    		p=p->next;
    		count++;
    	}
    	for(int i=0; i<count; i++) //删除所有的有效节点，头节点没有删除
    		remove_tail(head);	
    }
    
    //链表的销毁--》从前往后一个个删除
    int destroy_list2(plist head)
    {
    	//留给没有写出来的同学
    }
    
    //打印链表
    int show_list(plist head)
    {
    	plist p=head;
    	//循环遍历打印
    	while(p->next!=NULL)  //p的下一个节点不为NULL
    	{
    		p=p->next; //p指向下一个节点
    		printf("我遍历到的节点中数据是:%d\n",p->data);
    	}
    	return 0;
    }
    
    int main()
    {
    	int delnum;
    	//初始化一个头节点
    	plist myhead=init_list();
    	
    	//尾部插入数据
    	insert_tail(999,myhead);
    	insert_tail(999,myhead);
    	insert_tail(999,myhead);
    	insert_tail(999,myhead);
    	
    	//中间插入
    	insert_mid(77,44,myhead);
    	
    	printf("======插入完毕========\n");
    	//打印链表
    	show_list(myhead);
    	
    	//删除某个节点
    	printf("请输入要删除的节点!\n");
    	scanf("%d",&delnum);
    	//remove_list(delnum,myhead);
    	remove_list2(delnum,myhead);
    	printf("======删除完毕========\n");
    	//打印链表
    	show_list(myhead); 
    	
    	//销毁链表
    	destroy_list(myhead);
    	printf("======销毁链表========\n");
    	//打印链表
    	show_list(myhead);
    	free(myhead);
    }