数据结构和算法（四）

末蓝、 2022-12-13 12:54 124阅读 0赞

作业分析讲解  
=============  
    1.  代码的错误：  
               语法错误：最容易的，gcc编译的时候编译器就会告诉你(警告warning或者错误error)  
               逻辑错误：编译的时候，没有任何语法错误，但是运行的时候产生的现象跟你心中所想的不一致  
                              解决问题思路：  
                                    第一步：定位出错误的位置(通过打印语句)  
                                    第二步：在错误的位置一句句执行代码，把结果手动写出来，对照着看

内核链表    
============  
  1. 内核链表：只适用于linux系统(window不要去使用)，它是linux中专用的一种链表(本质上就是个双向循环链表)  
      优势：前面学习双向循环链表"很痛苦"(画图，理清指针的指向关系，关系理不清容易产生段错误)  
               内核链表把我们同学最讨厌的指针操作封装成了函数或者宏定义(方便你直接使用，隐藏了指针操作的细节)  
  2. 内核链表的原理：  
            普通的双向循环链表定义  
               struct  doublelist  
               \{  
                        //数据域  
                        //指针域两个指针struct  doublelist   \*prev ，  \*next  
               \}  
           内核链表的定义  
              struct  名字自定义  //把数据和指针做了剥离  
             \{  
                        //数据域  
                        struct list\_head   mypoint;  //存放了两个指针  
            \}  
             struct  kernellist   //大结构体(宿主结构体)  
             \{  
                    int data;  //数据域  
                    struct list\_head   mypoint;   //存放指针的结构体，小结构体  
             \}  
  3. 内核链表提供的接口函数或者宏定义  
            (1)  初始化指针  
                   INIT\_LIST\_HEAD(ptr)   //宏函数  
                            参数：ptr --》你要初始化的那个指针 struct list\_head   
            (2)  插入  
                  list\_add\_tail(struct list\_head \*new, struct list\_head \*head)  
                           参数: 两个小结构体指针  
                                   功能一： 把new这个节点插入到head表示的内核链表的尾部     
                                   功能二： 把new这个节点插入到另外一个节点的前面  list\_add\_tail(new, othernode)；

void list\_add(struct list\_head \*new, struct list\_head \*head)    
                           参数：同上  
                                   功能一：把new这个节点插入到head和第一个有效节点之间  
                                   功能二：把new这个节点插入到另外一个节点的后面  list\_add(new, othernode)；

(3)   遍历内核链表  
                写法一：  
                       list\_for\_each\_entry(pos, head, member)   //宏函数   //用一个指针，pos来遍历  
                                 参数：pos --》大结构体指针，用来遍历内核链表  
                                          head --》头节点里面的小结构体指针  
                                          member --》小结构体在大结构中的名字  
                                注意：这种循环适合遍历打印链表中的数据，不适合在遍历的过程中直接删除数据(容易导致段错误)  
               写法二：  
                       list\_for\_each\_entry\_safe(pos, n, head, member)    //用两个指针pos和n一前一后遍历       
                                    参数：pos --》大结构体指针，用来遍历内核链表  
                                             n --》大结构体指针，用来遍历内核链表，跟pos一起配合遍历链表  
                                             head --》头节点里面的小结构体指针  
                                             member --》小结构体在大结构中的名字  
                                注意：这种循环，遍历打印，删除节点都没有问题  
               写法三：  
                      list\_for\_each(pos, head)  
                                    参数：pos --》小结构体指针，用来遍历内核链表  
                                             head --》头节点里面的小结构体指针  
                      必须配合list\_entry(ptr, type, member)一起使用，原因是list\_for\_each()里面的pos是个小结构体指针(无法访问大结构体中的成员)  
                                    作用：通过小结构体得到对应的大结构体(地址转换，源码中通过小结构体指针计算得到大结构体的首地址)  
                                    参数：ptr --》小结构指针  
                                             type --》大结构体的类型名  
                                             member --》小结构体在大结构中的名字  
   
          (4)   删除  
                void list\_del(struct list\_head \*entry)  
                          参数:  小结构体指针  
                                   你要删除的那个节点的小结构体指针

4. 总结：  
              第一点：  内核链表中有两种转换  
                        第一种：大结构调用小结构        struct  kernellist  \*p;    p->mypoint       mypoint就是我的小结构体  
                        第二种：小结构体得到大结构体  struct  kernellist  \*p=list\_entry(小结构体指针, 大结构体类型名,小结构体名字)   
             第二点：   
练习：  
       1. 熟悉内核链表的接口函数，动手使用内核链表的函数，体会每个参数的含义  
       2. 用内核链表存放某个目录种读取的图片的路径，键盘输入next字符串表示下一张(打印下一个节点中的图片名字即可)  
                                                                             键盘输入prev字符串表示上一张(打印上一个节点中的图片名字即可)  
       3. 扩展： 内核链表还有其它的函数  
              //调整节点的位置  
              void list\_move(struct list\_head \*list,struct list\_head \*head)  //把list这个节点挪动到head表示的节点的后面  
              void list\_move\_tail(struct list\_head \*list,struct list\_head \*head)  //把list这个节点挪动到head表示的节点的前面      
              void  list\_splice(struct list\_head \*list, struct list\_head \*head)  //合并链表，把head表示的链表合并到list表示的链表尾部                          
      /usr/src/linux-headers-4.10.0-28/include/linux/list.h

栈和队列  
==================  
     1.  栈：先进后出  
                两种常见的实现方法：  顺序栈(用顺序表实现栈的逻辑)  
                                                  链式栈(用单链表实现栈的逻辑)  
                (1) 顺序栈  
                          栈的初始化  
                          压栈(入栈)  
                          弹栈(出栈)  
                          栈的销毁  
                       struct  stack  
                       \{  
                               int  a\[10\];  //存放整数的顺序栈  
                               int  top;  //标记目前栈顶位置  
                       \};  
                      struct  stack  \*init\_stack()  
                      \{  
                              struct  stack  \*mystack=malloc();  
                              mystack->top=0;  
                              return mystack;  
                      \}  
                      //压栈  push\_stack  
                      int push\_stack(int newdata,struct  stack  \*stack)  
                     \{  
                             //判断栈是否满了  
                              
                            //newdata入栈  
                            stack->a\[stack->top\]=newdata;  
                           //更新栈顶  
                           stack->top++；  
                    \}‘  
                    //出栈   pop\_stack  
                    int pop\_stack(struct  stack  \*stack)  
                    \{  
                           //判断栈是否空了  
                          stack->top--;    
                          //出栈  
                          return  stack->a\[stack->top\];  
                    \}

队列：先进先出  
    
作业：  
     1.  完成顺序栈的代码，三个函数的封装，利用封装的函数实现将键盘输入的任意整数转换成2进制保存到栈里面，然后打印出来    
                                                               用栈实现字符串的逆序输出

##    内核链表 ##

#include "myhead.h"
    #include "kernel_list.h"
    
    //定义一个结构体表示内核链表
    struct kernellist
    {
    	char bmppath[30]; //真实数据,存放图片的路径名
    	struct list_head mypoint;
    };
    
    struct kernellist *myhead;
    
    //初始化
    struct kernellist *init_list()
    {
    	struct kernellist *head=malloc(sizeof(struct kernellist));
    	strcpy(head->bmppath,"./pic/1.bmp");  //头节点中存放一张图片的路径
    	INIT_LIST_HEAD(&(head->mypoint));
    	return head;
    }
    
    //尾插
    int insert_tail(char *newdata,struct kernellist *head)
    {
    	//定义新的节点
    	struct kernellist *newnode=malloc(sizeof(struct kernellist));
    	strcpy(newnode->bmppath,newdata);
    	INIT_LIST_HEAD(&(newnode->mypoint));
    	
    	//尾插
    	list_add_tail(&(newnode->mypoint),&(myhead->mypoint));
    	return 0;
    }
    
    
    //封装递归函数
    int myreaddir(char *dirpath)
    {
    	char filepath[256];
    	char subdirpath[256];
    	//洋葱剥皮
    	DIR *dirp=opendir(dirpath);
    	if(dirp==NULL)
    	{
    		perror("打开目录失败!\n");
    		return -1;
    	}
    	struct dirent *p;
    	//循环读取目录
    	while((p=readdir(dirp))!=NULL)
    	{
    		//排除掉.和..  
    		if(strcmp(p->d_name,".")==0 || strcmp(p->d_name,"..")==0)
    			continue;
    		if(p->d_type==DT_REG) //普通文件
    		{
    			bzero(filepath,256);
    			//判断该文件是不是bmp图片
    			if(strstr(p->d_name,".bmp")!=NULL)
    			{
    				//拼接绝对路径打印
    				sprintf(filepath,"%s/%s",dirpath,p->d_name);
    				//把bmp图片的路径存放到内核链表中
    				insert_tail(filepath,myhead);
    			}
    		}
    		if(p->d_type==DT_DIR) //子目录
    		{
    			bzero(subdirpath,256);
    			//拼接绝对路径打印
    			sprintf(subdirpath,"%s/%s",dirpath,p->d_name);
    			myreaddir(subdirpath); //递归调用自己
    		}
    	}
    }
    int main(int argc,char **argv)
    {
    	char cmd[10];
    	//初始化一个内核链表
    	myhead=init_list();
    	
    	//递归读取目录并把bmp图片的绝对路径存放到内核链表中
    	myreaddir(argv[1]);
    	
    	//定义一个小结构体指针指向链表的表头
    	struct list_head *q=&(myhead->mypoint);
    	struct kernellist *bigq;
    	//打印上一张，下一张
    	while(1)
    	{
    		bzero(cmd,10);
    		printf("请输入next或者prev分别表示下一张和上一张!\n");
    		scanf("%s",cmd);
    		if(strcmp(cmd,"next")==0)  //下一张
    		{
    			//指针往后挪动
    			q=q->next;
    			//把小结构体转换成对应节点的大结构体
    			bigq=list_entry(q,struct kernellist,mypoint); //源码返回的是整个结构体的起始地址
    			printf("当前遍历的是:%s\n",bigq->bmppath);
    		}
    		if(strcmp(cmd,"prev")==0)  //上一张
    		{
    			//指针往前挪动
    			q=q->prev;
    			//把小结构体转换成对应节点的大结构体
    			bigq=list_entry(q,struct kernellist,mypoint); //源码返回的是整个结构体的起始地址
    			printf("当前遍历的是:%s\n",bigq->bmppath);
    		}
    	}
    }