数据结构和算法（一）

逃离我推掉我的手 2022-12-13 12:54 156阅读 0赞

知识点概览  
=============  
         (增删改查)  ---》添加数据    删除数据   修改数据   查询打印  
    1.  线性结构  
             顺序表的基本操作  
             单链表  
             单向循环链表  
             双向链表  
             双向循环链表  
             栈(顺序栈，链式栈)  
             队列(顺序队列，链式队列)  
    2.  非线性结构  
             树和二叉树  
             二叉树的遍历  
             BST树  
    3   常见的算法  
             排序算法  
             查找算法

数据结构  
==============  
    1.  作用： 数据在内存中采用什么样的存储方式可以提升数据的访问效率  
    2.  顺序表  
               定义： 把我们前面学习的数组用结构体封装起来       
               总结成公式：  
                                struct  顺序表的名字  
                               \{  
                                       类型  a\[数据元素个数\];  //存放有效数据的一个数组  
                                       int last;  //标记数组最后一个有效成员的下标  
                               \}；  
              实现顺序表的基本操作  
                        初始化  
                        增删改查  
                        销毁顺序表

练习：  
       1.  顺序表插入的代码，判断顺序表是否满了  
       2.  封装顺序表删除元素   顺序表修改元素  
               int  remove\_list(int deldata, struct slist \*somelist)          //把deldata从顺序表中删除  
               int  updata\_list(int olddata,int newdata, struct slist \*somelist)  //用newdata替换顺序表中olddata

单链表  
============  
   1.  数组(顺序表)： 对内存的要求比较高(连续大片的存储空间，降低了内存的使用效率)  
                             插入，删除麻烦一点(数据的移动)  
        单链表的表示：  
                   特点：链表物理上不连续(内存地址不一定紧挨着)，逻辑上连续(通过指针串起来)  
                    struct  单链表的名字  
                   \{  
                          类型  变量名;  //真实的数据  
                           struct  单链表的名字 \*next;  //指向下一个数据节点的指针    
                   \};  
                   struct  单链表的名字  
                   \{  
                           数据域；  
                           指针域；  
                   \}；  
                 struct  siglist  
                 \{  
                       char  buf\[20\];  
                       struct  单链表的名字 \*next;  
                \}  
                 struct  siglist  //buf和age都是真实数据  
                 \{  
                       char  buf\[20\];  
                       int  age;  
                       struct  单链表的名字 \*next;  
                \}  
                 struct  siglist  //该链表存放学生结构体的  
                 \{  
                       struct student  somestu;   
                       struct  单链表的名字 \*next;  
                \}  
        实现单链表的基本操作  
                        初始化  
                        增删改查  
        学习链表的技巧：(学习链表很容易出现段错误)  
                  第一个： 你把指针的赋值运算翻译成指向(方便你理解)  
                                 p->next=newnode;  //p的next指针指向新的节点  
                  第二个：通过画图理清指针之间的关系(如果指针之间的关系不理清容易产生段错误)  
                               画图主要为了帮助你把指针的指向关系弄清楚  
                  第三个： 画图的时候一条路走不通，把步骤调整一下就可以       
                 
        总结：  
                 链表使用的时候不必考虑越界的问题(数组要考虑)

练习：  
       1.封装函数实现链表在中间插入  
作业：  
       1.简单点：  配合文件IO的目录操作，读取一个目录中所有普通文件和子目录的名字，把它们的名字存放到一个单链表中  
   
       2.复杂点：  实现单链表删除，修改

## **顺序表的基本操作** ##

#include "myhead.h"
    
    //使用了C语言的一些小花招
    #define SIZE  10
    typedef int DATATYPE;
    
    //定义一个结构体来表示顺序表
    struct slist
    {
    	DATATYPE a[SIZE];  //存放数据的数组
    	int last; //标记最后一个有效成员的下标
    };
    
    //顺序表的初始化
    struct slist *init_list()
    {
    	struct slist *mylist=malloc(sizeof(struct slist));  //堆空间
    	if(mylist==NULL)
    		return NULL;
    	bzero(mylist->a,SIZE*sizeof(DATATYPE));
    	mylist->last=-1;
    	return mylist;
    }
    
    //判断顺序表是否满了， 没有满--》false   满了 --》true
    bool if_full(struct slist *somelist)
    {
    	if((somelist->last)>=(SIZE-1)) //满了
    		return true;
    	else
    		return false;
    }
    
    //判断顺序表是否空的   不是空--》false   空的 --》true
    bool if_empty(struct slist *somelist)
    {
    	if((somelist->last)<0)  //空的
    		return true;
    	else
    		return false;
    }
    
    //往顺序表中插入数据（最后一个有效成员的后面插入）
    /*
    	返回值： 插入失败  -1
    	         插入成功  0
    */
    int insert_list(DATATYPE newdata,struct slist *somelist)
    {
    	//判断顺序表是否满了
    	if(if_full(somelist))
    	{
    		printf("顺序表已经满了!\n");
    		return -1;
    	}
    	//先更新last
    	somelist->last++;
    	somelist->a[somelist->last]=newdata;
    	return 0;
    }
    
    //删除顺序表中的数据
    /*
    	删除数据无非如下几种情况：
    	     情况1：删除的数据存在，只有一个
    		 情况2：删除的数据存在，多个
    		 情况3：删除的数据不存在
    */
    int remove_list(DATATYPE deldata, struct slist *somelist)
    {
    	int i,j;
    	int flag=0;  //标记是否找到要删除的数据
    	//先判断顺序表是否为空
    	if(if_empty(somelist))
    	{
    		printf("顺序表已经是空的！\n");
    		return -1;
    	}
    	//找到要删除的数据，然后删除
    	for(i=0; i<=somelist->last; i++)
    	{
    		if(somelist->a[i]==deldata) //找到了
    		{
    			flag=1;
    			//后面的数据往前挪动
    			for(j=i; j<=somelist->last; j++)
    			{
    				somelist->a[j]=somelist->a[j+1];
    			}
    			//更新last
    			somelist->last--;
    			i--;  //防止漏掉重复的数据
    		}
    	}
    	//判断要删除的数据是不是不存在
    	if(flag==0)
    	{
    		printf("你要删除的数据不存在!\n");
    		return -1;
    	}
    	return 0;
    }
    
    //修改olddata
    int updata_list(DATATYPE olddata,DATATYPE newdata, struct slist *somelist)
    {
    	int i;
    	int flag=0;  //用来标记olddata是否存在的
    	//先判断顺序表是否为空
    	if(if_empty(somelist))
    	{
    		printf("顺序表已经是空的！\n");
    		return -1;
    	}
    	//找到要修改的数据，然后修改
    	for(i=0; i<=somelist->last; i++)
    	{
    		if(somelist->a[i]==olddata) //找到了
    		{
    			somelist->a[i]=newdata;
    			flag=1;
    		}
    	}
    	if(flag==0)
    	{
    		printf("你要修改的数据不存在!\n");
    		return -1;
    	}
    	
    	return 0;
    }
    
    //打印顺序表
    int print_list(struct slist *somelist)
    {
    	int i;
    	for(i=0; i<=somelist->last; i++)
    		printf("%d\n",somelist->a[i]);
    	return 0;
    }
    
    //销毁顺序表
    int destroy_list(struct slist *somelist)
    {
    	//释放堆空间
    	free(somelist);
    	return 0;
    }
    
    int main()
    {
    	int i;
    	DATATYPE data;
    	DATATYPE deldata;
    	DATATYPE olddata;
    	DATATYPE newdata;
    	//先初始化一个顺序表
    	struct slist *p=init_list();
    	
    	//往顺序表中插入数据（最后一个有效成员的后面插入）
    	for(i=0; i<5; i++)
    	{
    		printf("请输入要插入的数据!\n");
    		scanf("%d",&data);
    		insert_list(data,p);
    	}
    	printf("=========插入之后=========\n");
    	//打印顺序表
    	print_list(p);
    	
    /* 	//删除数据
    	printf("请输入要删除的数据!\n");
    	scanf("%d",&deldata);
    	remove_list(deldata,p);
    	printf("=========删除之后=========\n");
    	//打印顺序表
    	print_list(p); */
    	
    	//修改数据
    	printf("请输入你想要修改哪个数据，新数据是多少!\n");
    	scanf("%d%d",&olddata,&newdata);
    	updata_list(olddata,newdata,p);
    	printf("=========修改之后=========\n");
    	//打印顺序表
    	print_list(p);
    	
    	//销毁顺序表
    	destroy_list(p);
    	
    	return 0;
    }