数据结构和算法（三）

旧城等待， 2022-12-13 12:54 132阅读 0赞

作业分析讲解  
================  
    1.  结构体相关的  
                 结构体变量之间可以直接赋值  
                 结构体变量比较不能用 ==   >    <  
                 判断结构体大小，把结构体中所有的成员一个个比较

双向链表  
================  
    1.  原理： 在单向链表的基础上多增加了一个指针(指向前面一个节点的指针)  
             总结成公式           struct  双向链表的名字  
                                       \{  
                                                 int data;  //真实的数据     数据域  
                                                 struct 双向链表的名字 \*prev;   //指向前面一个节点的指针  
                                                 struct 双向链表的名字 \*next;   //指向后面一个节点的指针  
                                       \};  
        双向链表多了一个指针，没有增加代码书写的难度，相反降低了难度  
        双向链表： 一定是可以只用一个指针解决增删改查的操作  
        总结链表的几种写法技巧：  
                 while(p!=NULL)   //遍历完链表  p指向最后一个节点的后面  
                 while(p->next!=NULL)  //循环退出，p指向最后一个节点  
    2. 找好工作基础四大件  
               数据结构和算法 --》逻辑思维怎么样  
               操作系统 --》linux    
               网络编程 --》  
               刷题做好经验上的准备--》leetcode这个app刷题

练习：  
        训练大家对应链表代码书写的技巧(画图，配合代码书写)  
        双向循环链表的代码和图示分析

双向循环链表  
==============  
     1. 在双向链表的基础上，首尾相接  
                while(p!=NULL)  --》while(p!=head)  
         注意：双向循环链表，插入和删除注意最后一个节点的写法发生改变，中间位置的节点写法一样

作业：  
      1.  使用今天学习的双向循环链表配合目录操作，读取一个目录中所有的bmp图片路径，存放到双向循环链表，实现图片上一张，下一张的显示

内核链表  栈    队列   树和二叉树   BST    
============

## 单链表的销毁 ##

#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)
    {
    	//留给没有写出来的同学
    	plist q=head->next;
    	
    	//循环删除
    	while(q!=NULL)
    	{
    		head->next=head->next->next;
    		q->next=NULL;
    		free(q);
    		//q往后挪动
    		q=head->next;
    	}
    	return 0;
    }
    
    //打印链表
    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(999,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);  //从后往前
    	destroy_list2(myhead);  //从前往后
    	printf("======销毁链表========\n");
    	//打印链表
    	show_list(myhead);
    	free(myhead);
    }

# #

## 双向链表的基本操作 ##

#include "myhead.h"
    
    //定义一个结构体表示双向链表
    struct doublelist
    {
    	int data; //真实数据
    	struct doublelist *prev;
    	struct doublelist *next; 
    };
    
    //初始化
    struct doublelist *init_list()
    {
    	struct doublelist *head=malloc(sizeof(struct doublelist));
    	head->prev=NULL;
    	head->next=NULL;
    	return head;
    }
    
    //尾插
    int insert_tail(int newdata,struct doublelist *head)
    {
    	//定义新的节点
    	struct doublelist *newnode=malloc(sizeof(struct doublelist));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	newnode->prev=NULL;
    	
    	//找到链表的尾部
    	struct doublelist *p=head;
    	while(p->next!=NULL)
    		p=p->next;
    	p->next=newnode;
    	newnode->prev=p;
    	return 0;
    }
    
    //中间插入  把newdata插入到olddata的后面
    int insert_mid(int olddata,int newdata,struct doublelist *head)
    {
    	//准备新的节点
    	struct doublelist *newnode=malloc(sizeof(struct doublelist));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	newnode->prev=NULL;
    	
    	//找到olddata
    	struct doublelist *p=head;
    	while(p!=NULL)  // 23  13  33  43
    	{
    		if(p->data==olddata)
    			break;
    		p=p->next;
    	}
    	//判断olddata不存在的情况
    	if(p==NULL)
    	{
    		printf("对不起，没有%d这个数据!\n",olddata);
    		return -1;
    	}
    	//特殊情况 p刚好指向最后一个节点时候
    	if(p->next==NULL)
    	{
    		p->next=newnode;
    		newnode->prev=p;
    		return 0;
    	}
    	else{
    		//插入新的节点
    		newnode->next=p->next;
    		p->next=newnode;
    		newnode->next->prev=newnode;
    		newnode->prev=p;
    		return 0;
    	}	
    }
    
    //删除
    int remove_list(int deldata,struct doublelist *head)
    {
    	//找到要删除的数据
    	struct doublelist *p=head;
    	while(p!=NULL)  
    	{
    		if(p->data==deldata)
    			break;
    		p=p->next;
    	}
    	//判断deldata不存在的情况
    	if(p==NULL)
    	{
    		printf("对不起，没有你要删除的数据:%d\n",deldata);
    		return -1;
    	}
    	
    	//判断p是最后一个节点的情况
    	if(p->next==NULL)
    	{
    		p->prev->next=NULL;
    		p->prev=NULL;
    		free(p);
    		p=NULL;
    	}
    	else
    	{
    		//删除p指向的节点
    		p->prev->next=p->next;
    		p->next->prev=p->prev;
    		p->next=NULL;
    		p->prev=NULL;
    		free(p);
    		p=NULL;
    	}
    
    }
    
    //打印
    int show_list(struct doublelist *head)
    {
    	struct doublelist *p=head;
    	while(p->next!=NULL)
    	{
    		p=p->next;
    		printf("当前节点中的数据是:%d\n",p->data);
    	}
    	return 0;
    }
    
    //销毁链表
    int destroy_list(struct doublelist *head)
    {
    	struct doublelist *p=head->next;
    	while(p->next!=NULL)  //循环删除中间部分的节点，最后一个节点单独删除
    	{
    		printf("p当前遍历的节点:%d\n",p->data);
    		head->next=p->next;
    		p->next->prev=head;
    		p->next=NULL;
    		p->prev=NULL;
    		free(p);
    		//p继续挪动
    		p=head->next;
    	}
    	//单独删除最后一个节点
    	head->next=NULL;
    	p->prev=NULL;
    	free(p);
    	p=NULL;
    }
    
    int main()
    {
    	int olddata,newdata;
    	int deldata;
    	//初始化一个双向链表
    	struct doublelist *myhead=init_list();
    	
    	//尾插数据
    	insert_tail(23,myhead);
    	insert_tail(13,myhead);
    	insert_tail(33,myhead);
    	insert_tail(43,myhead);
    	
    	printf("====尾插完毕======\n");
    	//打印
    	show_list(myhead);
    	
    	/* //中间插入
    	printf("请输入中间插入的数据！\n");
    	scanf("%d%d",&olddata,&newdata);
    	insert_mid(olddata,newdata,myhead);
    	printf("====中间插入完毕======\n");
    	//打印
    	show_list(myhead);
    	
    	//删除
    	printf("请输入要删除的数据!\n");
    	scanf("%d",&deldata);
    	remove_list(deldata,myhead);
    	printf("====删除完毕======\n");
    	//打印
    	show_list(myhead); */
    	
    	//销毁链表
    	destroy_list(myhead);
    	printf("====销毁完毕======\n");
    	//打印
    	show_list(myhead);
    	free(myhead);
    }

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

#include "myhead.h"
    
    //定义一个结构体表示双向循环链表
    struct doublelist
    {
    	int data; //真实数据
    	struct doublelist *prev;
    	struct doublelist *next; 
    };
    
    //初始化
    struct doublelist *init_list()
    {
    	struct doublelist *head=malloc(sizeof(struct doublelist));
    	head->prev=head;
    	head->next=head;
    	return head;
    }
    
    //尾插
    int insert_tail(int newdata,struct doublelist *head)
    {
    	//定义新的节点
    	struct doublelist *newnode=malloc(sizeof(struct doublelist));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	newnode->prev=NULL;
    	
    	//找到链表的尾部
    	struct doublelist *p=head;
    	while(p->next!=head)
    		p=p->next;
    	p->next=newnode;
    	newnode->prev=p;
    	newnode->next=head;
    	head->prev=newnode;
    	return 0;
    }
    
    //中间插入  把newdata插入到olddata的后面
    int insert_mid(int olddata,int newdata,struct doublelist *head)
    {
    	//准备新的节点
    	struct doublelist *newnode=malloc(sizeof(struct doublelist));
    	newnode->data=newdata;
    	newnode->next=NULL;
    	newnode->prev=NULL;
    	
    	//找到olddata
    	struct doublelist *p=head->next;
    	while(p!=head)  // 23  13  33  43
    	{
    		if(p->data==olddata)
    			break;
    		p=p->next;
    	}
    	//判断olddata不存在的情况
    	if(p==head)
    	{
    		printf("对不起，没有%d这个数据!\n",olddata);
    		return -1;
    	}
    	//特殊情况 p刚好指向最后一个节点时候
    	if(p->next==head)
    	{
    		p->next=newnode;
    		newnode->prev=p;
    		newnode->next=head;
    		head->prev=newnode;
    		return 0;
    	}
    	else{
    		//插入新的节点
    		newnode->next=p->next;
    		p->next=newnode;
    		newnode->next->prev=newnode;
    		newnode->prev=p;
    		return 0;
    	}	
    }
    
    //删除
    int remove_list(int deldata,struct doublelist *head)
    {
    	//找到要删除的数据
    	struct doublelist *p=head->next;
    	while(p!=head)  
    	{
    		if(p->data==deldata)
    			break;
    		p=p->next;
    	}
    	//判断deldata不存在的情况
    	if(p==head)
    	{
    		printf("对不起，没有你要删除的数据:%d\n",deldata);
    		return -1;
    	}
    	
    	//判断p是最后一个节点的情况
    	if(p->next==head)
    	{
    		p->prev->next=head;
    		head->prev=p->prev;
    		p->prev=NULL;
    		p->next=NULL;
    		free(p);
    		p=NULL;
    	}
    	else //删除中间的节点
    	{
    		//删除p指向的节点
    		p->prev->next=p->next;
    		p->next->prev=p->prev;
    		p->next=NULL;
    		p->prev=NULL;
    		free(p);
    		p=NULL;
    	}
    
    }
    
    //打印
    int show_list(struct doublelist *head)
    {
    	struct doublelist *p=head;
    	while(p->next!=head)
    	{
    		p=p->next;
    		printf("当前节点中的数据是:%d\n",p->data);
    	}
    	return 0;
    }
    
    //销毁链表
    int destroy_list(struct doublelist *head)
    {
    	struct doublelist *p=head->next;
    	while(p->next!=head)  //循环删除中间部分的节点，最后一个节点单独删除
    	{
    		head->next=p->next;
    		p->next->prev=head;
    		p->next=NULL;
    		p->prev=NULL;
    		free(p);
    		//p继续挪动
    		p=head->next;
    	}
    	//单独删除最后一个节点
    	p->prev->next=head;
    	head->prev=p->prev;
    	p->prev=NULL;
    	p->next=NULL;
    	free(p);
    	p=NULL;
    }
    
    int main()
    {
    	int olddata,newdata;
    	int deldata;
    	//初始化一个双向循环链表
    	struct doublelist *myhead=init_list();
    	
    	//尾插数据
    	insert_tail(23,myhead);
    	insert_tail(13,myhead);
    	insert_tail(33,myhead);
    	insert_tail(43,myhead);
    	
    	printf("====尾插完毕======\n");
    	//打印
    	show_list(myhead);
    	
    	//中间插入
    	printf("请输入中间插入的数据！\n");
    	scanf("%d%d",&olddata,&newdata);
    	insert_mid(olddata,newdata,myhead);
    	printf("====中间插入完毕======\n");
    	//打印
    	show_list(myhead);
    	
    	//删除
    	printf("请输入要删除的数据!\n");
    	scanf("%d",&deldata);
    	remove_list(deldata,myhead);
    	printf("====删除完毕======\n");
    	//打印
    	show_list(myhead); 
    	
    	//销毁链表
    	destroy_list(myhead);
    	printf("====销毁完毕======\n");
    	//打印
    	show_list(myhead);
    	free(myhead); 
    }

##      ##