数据结构和算法（七）

迈不过友情╰ 2022-12-13 12:54 110阅读 0赞

从今晚开始补课  
==================  
    1. 7点到八点半晚上

零长数组(柔性数组)  
==================  
     定义： char  buf\[0\];    0表示该数组不能存放任何数据(零长)  
               往往跟结构体配合使用，在一些网络通信中保存发送信息的  
     总结：零长数组最开始是没有大小的，后来通过耍花招，分配了堆空间(根据数据的实际长度，不造成浪费)

图像显示  
=============  
   1. 用算法来玩弄像素点

C语言测试题  
================  
    第29题  
          (double)5/2+2.5  
          第一种： 5--》double  5.0  
    第30题  
           for(i=0;  s\[i\];  i++)  //  中间的表达式判断s\[i\]的值是真还是假

int  a=7;  
           if(a)  //判断a的真假  
           if(  !strcmp(buf1,buf2))

常用的排序算法  
===============  
   1. 衡量一个算法效率  
             时间复杂度： 你的这个算法的执行次数  
   2.   
                for(i=0; i<n; i++)  
                \{  
                       for(j=0; j<n-1; j++)  
                                
                \}  
              总共执行了  n\*(n-1)次 --》n^2-n     时间复杂度  O(n^2)  
              算法时间复杂度  O(n^2)              
              算法时间复杂度  O(n)

排序算法：        
       冒泡排序  
       选择排序：每次找到最小的数，标记下标，然后交换到前面  
       直接插入排序：  
       快排：

查找算法：  
       bst树：小中大  
       折半查找：有序的序列采用折半

作业：  
      1.内存映射实现任意位置显示任意大小的bmp图片  
      2.折半查找代码实现

##    快速排序 ##

#include "myhead.h"
    int count=0;  //统计快排循环几次
    //找基准点的位置
    int getposition(int arr[],int low,int high)
    {
    	//临时变量存放基准值
    	int temp=arr[low];
    	//low和high撞到一起就结束
    	while(low<high)
    	{
    		//当后面的元素大于等于基准数据时，向前挪动high
    		while(low<high && arr[high]>=temp)
    		{
    			high--;
    		}
    			
    		//如果后面的元素小于基准数据，将high赋值给low
    		arr[low]=arr[high];
    		
    		//当前面的元素小于等于基准数据时，向后挪动low
    		while(low<high && arr[low]<=temp)
    		{
    			low++;
    		}
    		//如果前面的元素大于基准数据，将low赋值给high
    		arr[high]=arr[low];
    	}
    	//循环退出，说明low和high撞到一起
    	arr[low]=temp;
    	return low;  //返回基准值的正确位置
    }
    void quicksort(int arr[],int low,int high)
    {
    	//low和high撞到一起就结束
    	if(low<high)
    	{
    		// 找基准点的位置
    		int index=getposition(arr,low,high);
    		//递归调用继续排序,把基准值前后的数数据继续排序
    		quicksort(arr,0,index-1);
    		quicksort(arr,index+1,high);
    	}
    }
    
    int main()
    {
    	int arr[]={18,3,67,4,89,10,5};
    	quicksort(arr,0,6);
    	for(int i=0; i<7; i++)
    		printf("%d\n",arr[i]);
    	printf("count %d\n",count);
    }

## 选择排序 ##

#include "myhead.h"
    
    void selectsort(int buf[],int n)
    {
    	int i,j;
    	int min; //标记最小值的下标
    	int temp;
    	for(i=0; i<n-1; i++)
    	{
    		min=i; //假设下标i的是最小值
    		for(j=i+1; j<n; j++)
    		{
    			if(buf[j]<buf[min])
    				min=j;
    		} //循环完毕的时候，找到了当前最小值的小标
    		if(min!=i)
    		{
    			temp=buf[min];
    			buf[min]=buf[i];
    			buf[i]=temp;
    		}
    	}
    }
    
    int main()
    {
    	int i;
    	int array[]={23,4,15,7,89,6,32};
    	selectsort(array,7);
    	
    	for(i=0; i<7; i++)
    		printf("%d  ",array[i]);
    	
    	printf("\n");
    }

## 直接插入排序 ##

#include "myhead.h"
    int count=0;
    void insertsort(int buf[],int n)
    {
    	int i,j;
    	int temp;
    	//最开始有序序列只有一个数: buf[0]
    	//从下标为1的开始逐一往有序序列中插入
    	for(i=1; i<n; i++)
    	{
    		if(buf[i]<buf[i-1])
    		{
    			temp=buf[i]; //把待插入的数据存放到temp中
    			//把前面排好序的挪动，找到temp存放的位置
    			for(j=i-1; buf[j]>temp && j>=0; j--)
    			{
    				buf[j+1]=buf[j];
    				count++;
    			}
    			//循环结束以后，把temp放到正确的位置
    			buf[j+1]=temp;
    		}
    	}
    }
    
    int main()
    {
    	int i;
    	int arr[]={18,3,67,4,89,23,99,12,6,888};
    	insertsort(arr,10);
    	for(i=0; i<10; i++)
    		printf("%d\n",arr[i]);
    	printf("count %d\n",count);
    	
    }

## 内存映射显示bmp图片 ##

#include "myhead.h"
    //把图片的长宽定义宏
    #define W  800
    #define H  480
    #define X  0
    #define Y  0
    
    int main(int argc,char **argv)
    {
    	int bmpfd;
    	int lcdfd;
    	int i;
    	int x,y;
    	//定义数组存放读取到的RGB数值
    	unsigned char bmpbuf[W*H*3];  //char每个数据占1个字节
    	//定义int数组存放转换得到的ARGB数据
    	unsigned int lcdbuf[W*H]; //int每个数据占4个字节
    	unsigned int tempbuf[W*H]; //int每个数据占4个字节
    	
    	//打开W*H大小的bmp图片
    	bmpfd=open(argv[1],O_RDWR);
    	if(bmpfd==-1)
    	{
    		printf("打开bmp失败!\n");
    		return -1;
    	}
    	
    	//打开lcd的驱动
    	lcdfd=open("/dev/ubuntu_lcd",O_RDWR);
    	if(lcdfd==-1)
    	{
    		printf("打开lcd失败!\n");
    		return -1;
    	}
    	
    	//映射得到lcd的首地址
    	unsigned int *lcdmem=mmap(NULL,800*480*4,PROT_READ|PROT_WRITE,MAP_SHARED,lcdfd,0);
    	if(lcdmem==NULL)
    	{
    		printf("映射lcd失败!\n");
    		return -1;
    	}
    	
    	//跳过前面没有用的54个字节，从55字节开始读取真实的RGB
    	lseek(bmpfd,54,SEEK_SET);
    	
    	//读取bmp的rgb数据，从图片的第55个字节开始读取
    	read(bmpfd,bmpbuf,W*H*3);
    	//bmpbuf[0] --》R
    	//bmpbuf[1] --》G
    	//bmpbuf[2] --》B
    	//把三个字节的RGB--》转换成四个字节的ARGB
    	//思路：用位或运算和左移实现数据拼接
    	for(i=0; i<W*H; i++)
    		lcdbuf[i]=bmpbuf[3*i]|bmpbuf[3*i+1]<<8|bmpbuf[3*i+2]<<16|0x00<<24;
    	              // 00[2][1][0]  ABGR
    				  // 00[5][4][3]
    	/*	
    		lcdbuf[0]--lcdbuf[799]放到    lcdmem---lcdmem+799
    		lcdbuf[800]--lcdbuf[1599]放到 lcdmem+800---lcdmem+1599
    	*/
    	for(x=0; x<W; x++)
    	{
    		for(y=0; y<H; y++)
    			tempbuf[(479-y)*W+x]=lcdbuf[y*W+x]
    	}
    	
    	
    	for(i=0; i<W*H; i++)
    		*(lcdmem+i)=tempbuf[i];  //直接把ARGB数值往地址里面存放即可，效率最高
    
    	//关闭
    	close(bmpfd);
    	close(lcdfd);
    	//解除映射
    	munmap(lcdmem,800*480*4);
    	return 0;
    }