2019-9-14 829 0
2019-9-14 787 0
编程杂谈

二叉树的遍历因为使用二叉树最多是链式存储结构,所遍历的方式也是按照链式结构来的。遍历的宗旨在遍历是按照某种次序依次访问二叉树的所有节点,并且每个节点仅仅被访问一次。前序遍历(根左右)遍历顺序ABDHIEJCFKG中序遍历(左根右)遍历顺序HDIBEJAFKCG后序遍历(左右根)遍历顺序HIDJEBKFGC层序遍历遍历顺序ABCDEFGHIJK二叉树代码实现前序遍历(根左右)二叉树的遍历方式,在创建二叉树时就确定好了#include<stdio.h>#include<stdlib.h>typedefcharElemType;//二叉树结构typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//创建二叉树按照用户遵循的前序遍历的(根左右)方式输入数据voidcreateBiTree(BiTree*T){charc;printf("输入元素:");scanf("%c",&c);getchar();if(c=='#'){*T=NULL;}else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)->data=c;createBiTree(&(*T)->lchild);//先创建左子节点createBiTree(&(*T)->rchild);//再创建右子节点}}//遍历二叉树voidpreOrderTraverse(BiTreeT,intlevel){if(T!=NULL){printf("数据%c在第%d层\n",T->data,level);preOrderTraverse(T->lchild,level+1);preOrderTraverse(T->rchild,level+1);}}intmain(){intlevel=1;BiTNode*T;createBiTree(&T);preOrderTraverse(T,level);return0;}输入顺序中序遍历(左根右)输入方式还是前序的输入方式,只是遍历的打印位置修改了一下//中序遍历二叉树voidpreOrderTraverse(BiTreeT,intlevel){if(T!=NULL){preOrderTraverse(T->lchild,level+1);printf("数据%c在第%d层\n",T->data,level);preOrderTraverse(T->rchild,level+1);}}后序遍历(左右后)输入方式还是前序的输入方式,只是遍历的打印位置修改了一下//后序遍历二叉树voidpreOrderTraverse(BiTreeT,intlevel){if(T!=NULL){preOrderTraverse(T->lchild,level+1);preOrderTraverse(T->rchild,level+1);printf("数据%c在第%d层\n",T->data,level);}}

编程杂谈

栈相关概念什么是栈是限定仅在表尾(栈顶)进行插入和删除操作的线性表栈又称为后进先出(LastInFirstOut)的线性表,简称LIFO结构栈顶(top)我们把允许插入和删除的一端称为栈顶栈底(bottom)另一端称为栈底空栈不含任何任何数据元素的栈称为==空栈==栈的操作入栈入栈又称压栈,就是向栈中放数据,每次放入一个top指针就+1出栈取出栈中数据的操作,每取出一个top指针就-1清空栈清空栈,是把top指针直接指向bottom指针,原本物理空间上数据还存在栈的实现创建队列结构体#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_SIZE20//栈大小#defineSTACK_INCREMENT10//申请空间大小typedefcharElemType;//定义栈typedefstruct{ElemType*base;//栈低ElemType*top;//栈顶intstackSize;//当前栈容纳的大小}sqStack;初始化队列//初始化栈voidinitStack(sqStack*s){s->base=(ElemType*)malloc(STACK_INCREMENT*sizeof(ElemType));if(s->base==NULL)exit(-1);//空间申请失败s->top=s->base;s->stackSize=STACK_INIT_SIZE;printf("s->top:%p\n",s->top);printf("s->base:%p\n",s->base);}入栈(压栈)//压栈voidpush(sqStack*s,ElemTypee){//判断是否满栈,满栈则扩容if(s->top-s->base>=s->stackSize){s->base=(ElemType*)realloc(s->base,(s->stackSize+STACK_INCREMENT)*sizeof(ElemType));if(!s->base)exit(-1);}*(s->top)=e;//栈顶的值赋值es->top++;//栈顶地址向前推进}出栈//出栈voidpop(sqStack*s,ElemType*e){//判断下溢出if(s->top==s->base){return;}*e=*--s->top;//减之后赋值,*为取值,不是指针}当前栈长度//当前栈长度intsqStackLen(sqStack*s){returns->top-s->base;}主函数使用用户输入值,进行压栈,#号结束,输出栈内数据intmain(){sqStacks;initStack(&s);//初始化栈ElemTypec;printf("输入栈:");while((c=getchar())!='#'){getchar();push(&s,c);//压栈}getchar();//把\n从缓冲区去掉ElemTypee;while(sqStackLen(&s)){pop(&s,&e);//出栈printf("%c",e);}return0;}扩展(栈链)就是把栈和单链表结合,如下图一样栈链内元素是指针相连,而栈是顺序的地址队列概念什么是队列队列(queue)是只允许在一端进行插入的操作,而在另一端进行删除操作的线性表。队列主要特征是先进先出(FirstInFirstOut)队列操作队列的结构体#include<stdio.h>#include<stdlib.h>#defineElemTypechar//队列元素结构体(链表)typedefstructQNode{ElemTypedata;//队列节点数据structQNode*next;//队列指针}QNode,*QueuePrt;//队列头尾typedefstruct{QueuePrtfront,rear;//队头指针,队尾指针}LinkQueue;创建队列/*创建结构体在内存中创建一个头结点,将队列的头尾指针指向头结点,此时队列为空*/voidinitQueue(LinkQueue*q){q->front=q->rear=(QueuePrt)malloc(sizeof(QNode));if(!q->front)exit(-1);q->front->next=NULL;}入队列//入队列(下面是在从尾部入)voidinertQueue(LinkQueue*q,ElemTypee){QueuePrtnode=(QueuePrt)malloc(sizeof(QNode));if(!node)exit(-1);node->data=e;node->next=q->rear->next;q->rear->next=node;q->rear=node;}出队操作(取出队列的数据)//出队操作(下面是从队列头部取值)voidgetQueue(LinkQueue*q,ElemType*e){if(q->front==q->rear)return;//队列为空QueuePrtnode=q->front->next;*e=node->data;q->front->next=node->next;//队列头部向移动一位if(q->rear==node)q->rear=q->front;//队列最后数据被取出是,初始化为空free(node);};销毁队列//销毁队列voiddeleteQueue(LinkQueue*q){while(q->front){q->rear=q->front->next;free(q->front);q->front=q->rear;}}主函数使用intmain(){LinkQueueq;initQueue(&q);ElemTypee=0;printf("输入队列数据:");scanf("%c",&e);while(e!='#'){inertQueue(&q,e);scanf("%c",&e);}printf("队列中的数据:\n");while(q.rear!=q.front){getQueue(&q,&e);printf("%c",e);}return0;}

编程杂谈

常规想法遍历一遍单链表,记录长度再一次遍历,输出中间元素这样的效率不是最优另一种方式(来源于网络)search的速度是mid的两倍,search走完恰好mid走一半voidprintInt(intList*head){intList*mid,*search;//search的速度是mid的两倍,search走完恰好mid走一半mid=search=head;//保证midsearch启点一样while(search->next!=NULL){search=search->next;//search取下一个if(search->next!=NULL){search=search->next;//search再去下一个mid=mid->next;//mid就取一次}else{mid=mid->next;//search取到头,mid再往下取一位}}printf("\n%d",mid->num);}完整代码随机生成任意长度单链表输出单链表值输出位于中间的值奇数个是最中间值,偶数个是中间两个的前一个#include<stdio.h>#include<stdlib.h>#include<time.h>typedefstructIntList{intnum;structintList*next;}intList;intList*applyList();//生成随机长度单链表voidprintList(intList*head);//查看单链表voidprintInt(intList*head);//输出单链表中间值intList*applyList(){srand((unsigned)time(NULL));intlen=rand()%10+10;//10到20的随机数intList*head=(intList*)malloc(sizeof(intList));if(head==NULL)exit(-1);//链表头部申请失败head->next=NULL;while(len){intList*node=(intList*)malloc(sizeof(intList));node->num=rand()%10+20;node->next=head->next;head->next=node;len--;}returnhead;}voidprintList(intList*head){intList*t=head->next;while(t){printf("%d",t->num);t=t->next;}};voidprintInt(intList*head){intList*mid,*search;//search的速度是mid的两倍,search走完恰好mid走一半mid=search=head;//保证midsearch启点一样while(search->next!=NULL){search=search->next;//search取下一个if(search->next!=NULL){search=search->next;//search再去下一个mid=mid->next;//mid就取一次}else{mid=mid->next;//search取到头,mid再往下取一位}}printf("\n%d",mid->num);}intmain(){intList*list=applyList();//随机生成单链表printList(list);//查看链表的值printInt(list);//输出中间值return0;}

编程杂谈

什么是数据结构简单点就是程序设计=数据结构+算法逻辑结构&物理结构传统上把数据结构分为逻辑结构&物理结构逻辑结构:是指数据对象中数据元素之间的相互关系,是需要着重关注和讨论的问题。四大逻辑结构:集合结构:数据元素之间相互没有关系。线性结构:数据元素之间是一对一的关系。树性结构:数据元素之间有一对多的层级关系。图形结构:数据元素是多对多的关系。物理结构:指数据的逻辑结构在计算机中的存储形式。根据物理结构的定义,我们实际上研究的就是如何把数据元素存储到计算器的存储器中。数据元素的存储形式有两种:顺序存储:把数据元素存放在地址连续的存储单元里,其数据之间的逻辑关系和物理关系是一致的。就如:一些编程语言的数组就是这样。链式存储:把数据元素存放在任意的存储单元里,这组储存单元可以是连续的,也可以是不连续。就如单链表,只要知道下一个数据元素指向的地址就行`。什么是算法引入计算1+2+3+4+…+99+100的值常规算法(使用循环一个一个加):inti,sum=0,n=100;for(i=1;i<100;i++){sum=sum+i;}printf("sum=%d",sum);使用高斯算法:inti,sum=0,n=100;sum=(1+n)*n/2;printf("sum=%d",sum);这样是不是效率高很多。算法的特征算法有五大特征解决问题并不只有一种算法输入算法具有零个或者多个输入。尽管大多数时候算法来说,输入参数是必要的,但是就像打印bigdataboy.cn,就不需要参数。voidprint(){printf("bigdataboy.cn");}输出:算法需要至少一个或者多个输出。有穷性是指在执行有限的步骤后,自动结束,并且每一步都是在可接受的时间范围内完成。确定性:算法的每一步都具有确定的含义,不会出现二义性。相同的输入只能有唯一的输出结果。可行性:算法的每一步都必须是可行的,就是说,每一步都能通过执行有限的次数完成。算法设计的要求正确性:是指算法至少应该具有输入、输出和加工处理无歧义,能得到正确的结果。大致分为以下四个层次算法程序没有语法错误算法程序对于合法的输入能得到满足要求的输出算法程序对于非法输入能产生相应的说明算法程序对于故意刁难的测试输入都有满足要求的输出结果可读性算法需要便于阅读、理解和交流,方便日后他人和自己的阅读和修改。健壮性当输入不合法时,算法也能做出相关的处理,而不是产生异常、崩溃或莫名其妙的结果时间效率高和存储量低在生活中大家都想找一个漂亮乖巧懂事,懂分寸的女朋友。好的算法就像好的女朋友,应该同时具备时间效率高和存储量低的特点,设计算法时,因尽量考虑这两方面的问题!!!

编程杂谈

格式化读写‘fscanf()’、’fprintf()’格式化读‘fsanf()’用于从指定文件中读取格式化字符串。#include<stdio.h>...intfscanf(FILE*stream,constchar*format,...);用法:跟scanf()一样,只是多了stream参数fscanf(fp,"%d-%d-%d",&year,&month,&day);返回值调用成功,返回值是成功获取并填充到附加参数中的个数。调用失败,返回值小于附加参数的个数(甚至是0)。如果读取到标准输入流的结尾处,则返回EOF。格式化读‘fprintf()’用于打印格式化字符串到指定的文件。#include<stdio.h>...intfprintf(FILE*stream,constchar*format,...);用法:跟printf()一样,只是多了stream参数fprintf(fp,"IloveYou!\n");fprintf(fp,"Todayis%d-%d-%d\n",2021,1,22);返回值调用成功,返回值是实际打印的字符数(不包含表示字符串结束的‘\0’);调用失败,返回值是一个负数。实例格式化文件读写#include<stdio.h>#include<stdlib.h>#definePATH"./lines.txt"intmain(void){//打开文件FILE*fpw=fopen(PATH,"w");if(fpw==NULL)exit(1);//文件写入打开失败//格式化写入文件fprintf(fpw,"Todayis%d-%d-%d\n",2021,1,22);//关闭文件fclose(fpw);//打开文件FILE*fpr=fopen(PATH,"r");if(fpr==NULL)exit(2);//文件读取打开失败//读取文件intyear,month,day;fscanf(fpr,"Todayis%d-%d-%d",&year,&month,&day);printf("%d-%d-%d\n",year,month,day);//关闭读取文件fclose(fpr);return0;}二进制读写‘fread()’、’fwrite()’格式化读‘fread()’用于从指定的文件中读取指定尺寸的数据。#include<stdio.h>...size_tfread(void*ptr,size_tsize,size_tnmemb,FILE*stream);参数:ptr:指向存放数据空间的指针,该内存块的尺寸最小应该是size*nmemb个字节size:要读取的每个元素的尺寸nmemb:要读取的元素个数stream:是一个FILE对象的指针返回值成功:实际读取到的元素个数(nmemb);失败:返回比nmemb参数的值小,表示可能读取到文件末尾或者有错误发生(可以使用feof函数或ferror函数进一步判断)。格式化读‘fwrite()’将指定尺寸的数据写入到指定的文件中。#include<stdio.h>...size_tfwrite(constvoid*ptr,size_tsize,size_tnmemb,FILE*stream);参数:ptr:指向存放数据空间的指针,该内存块的尺寸最小应该是size*nmemb个字节size:要写入的每个元素的尺寸nmemb:要写入的元素个数stream:是一个FILE对象的指针返回值成功:返回实际写入到文件中的元素个数(nmemb);失败:如果返回值与nmemb参数的值不同,则有错误发生。实例#include<stdio.h>#include<stdlib.h>#definePATH"data.txt"structData{intyear;intmonth;intday;};intmain(void){//打开文件FILE*fpw=fopen(PATH,"w");if(fpw==NULL)exit(1);//打开写入文件失败//以二进制形式写入结构体到文件structData*data_write=(structData*)malloc(sizeof(structData));data_write->year=2021;data_write->month=1;data_write->day=21;fwrite(data_write,sizeof(structData),1,fpw);free(data_write);//关闭文件fclose(fpw);//打开文件FILE*fpr=fopen(PATH,"r");if(fpw==NULL)exit(2);//打开读取文件失败//以二进制形式读取文件structData*data_read=(structData*)malloc(sizeof(structData));fread(data_read,sizeof(structData),1,fpr);printf("%d-%d-%d\n",data_read->year,data_read->month,data_read->day);free(data_read);return0;}

编程杂谈

打开文件&关闭文件打开文件需要文件指针接收;关闭文件需要传入文件指针FILE*fp;//定义文件指针打开文件使用到的函数fopen()#include<stdio.h>FILE*fopen(constchar*path,constchar*mode);参数参数含义*path文件的路径,支持相对路径、绝对路径*mode指定文件打开的模式:r、w、a、r+、w+、a+b:以二进制形式打开文件,可以与上面的6种结合("rb","wb","ab","r+b","w+b","a+b")返回值打开成功,则返回一个指向FILE结构的文件指针;打开失败,则返回NULL并设置errno为指定的错误。打开文件模式文件打开模式说明“r”1.以只读的模式打开一个文本文件,从文件头开始读取2.该文本文件必须存在“w”1.以只写的模式打开一个文本文件,从文件头开始写入2.如果文件不存在则创建一个新的文件3.如果文件已存在则将文件的长度截断为0(重新写入的内容将覆盖原有的所有内容)“a”1.以追加的模式打开一个文本文件,从文件末尾追加内容2.如果文件不存在则创建一个新的文件“r+”1.以读和写的模式打开一个文本文件,从文件头开始读取和写入2.该文件必须存在3.该模式不会将文件的长度截断为0(只覆盖重新写入的内容,原有的内容保留)“w+”1.以读和写的模式打开一个文本文件,从文件头开始读取和写入2.如果文件不存在则创建一个新的文件3.如果文件已存在则将文件的长度截断为0(重新写入的内容将覆盖原有的所有内容)“a+”1.以读和追加的模式打开一个文本文件2.如果文件不存在则创建一个新的文件3.读取是从文件头开始,而写入则是在文件末尾追加“b”1.与上面6中模式均可结合(”rb”,“wb”,“ab”,“r+b”,“w+b”,“a+b”)关闭文件使用到的函数fclose()#include<stdio.h>intfclose(FILE*fp);参数参数含义fp指向一个待关闭的文件指针返回值:关闭成功,返回值是0;关闭失败,返回值是EOF,并设置errno为指定的错误。备注:磁盘已满、设备出错或者I/O错误均可能导致fclose函数调用失败。实例(打开文件&关闭文件)#include<stdio.h>#include<stdlib.h>intmain(void){FILE*fp;//定义文件指针//打开文件fp=fopen("data.txt","r");if(fp==NULL){printf("打开文件失败!!!\n");exit(EXIT_FAILURE);};//关闭文件if(fclose(fp)!=EOF){printf("关闭文件成功~~~");exit(EXIT_SUCCESS);};return0;}文件读写字符读写字符读‘fgetc()’、’getc()’fgetc()说明#include<stdio.h>...intfgetc(FILE*stream);参数说明:stream该参数是一个FILE对象的指针,指定一个待读取的文件流返回值:成功:将读取到的unsignedchar类型转换为int类型并返回;失败:如果文件结束或者遇到错误则返回EOF。getc()说明fgetc()、getc()两个的功能和描述基本上是一模一样的,它们的区别主要在于实现上:fgetc()是一个函数;而getc()则是一个宏的实现实例#include<stdio.h>#include<stdlib.h>intmain(){//定义文件指针FILE*fp;//打开文件if((fp=fopen("./data.txt","r"))==NULL){//文件打开失败exit(EXIT_FAILURE);}//读取文件的内容charch;while((ch=fgetc(fp))!=EOF){putchar(ch);;}//关闭文件流fclose(fp);return0;}字符写‘fputc()’、’putc()’将一个字符写入到指定的文件中并推进文件的位置指示器(用来指示接下来要读写的下一个字符的位置)。fputc()说明#include<stdio.h>...intfputc(intc,FILE*stream);参数说明:c:指定待写入的字符stream:该参数是一个FILE对象的指针,指定一个待写入的文件流返回值:成功:返回写入的字符;失败:如果文件结束或者遇到错误则返回EOF。putc()说明fputc()、putc()两个的功能和描述基本上是一模一样的,它们的区别主要在于实现上:fputc()是一个函数;而putc()则是一个宏的实现实例#include<stdio.h>#include<stdlib.h>intmain(){//定义文件指针FILE*fp;//打开文件if((fp=fopen("./data.txt","w"))==NULL){//文件打开失败exit(EXIT_FAILURE);}//写入一个字符charch='A';if(fputc(ch,fp)==EOF){//写入失败exit(EXIT_FAILURE);};//关闭文件流fclose(fp);return0;}字符串读写字符读‘fgets()’用于从指定文件中读取字符串。最多可以读取size-1个字符,因为结尾处会自动添加一个字符串结束符'\0'。当读取到换行符('\n')或文件结束符(EOF)时,表示结束读取('\n'会被作为一个合法的字符读取)。fgets()说明#include<stdio.h>...char*fgets(char*s,intsize,FILE*stream);参数说明:s:字符型指针,指向用于存放读取字符串的位置size:指定读取的字符数(包括最后自动添加的‘\0’)stream:该参数是一个FILE对象的指针,指定一个待操作的数据流返回值:成功:返回s参数指向的地址失败:如果在读取字符的过程中遇到EOF,则eof指示器被设置;如果还没读入任何字符就遇到这种EOF,则s参数指向的位置保持原来的内容,函数返回NULL。如果在读取的过程中发生错误,则error指示器被设置,函数返回NULL,但s参数指向的内容可能被改变。实例#include<stdio.h>#include<stdlib.h>#defineMAX1024intmain(){//打开文件FILE*fp;if((fp=fopen("./data.txt","r"))==NULL){exit(1);}//读取文件chars[MAX];if(fgets(s,MAX,fp)==NULL){//读取失败exit(2);};printf("%s",s);//输出读取内容//关闭文件fclose(fp);return0;}字符写‘fputs()’fputs函数用于将一个字符串写入到指定的文件中,表示字符串结尾的‘\0’不会被一并写入fputs()说明#include<stdio.h>...intfputs(constchar*s,FILE*stream);参数说明:s:字符型指针,指向用于存放待写入字符串的位置stream:是一个FILE对象的指针,指定一个待操作的数据流返回值:成功:返回一个非0值失败:返回EOF实例#include<stdio.h>#include<stdlib.h>intmain(void){//打开文件FILE*fp;if((fp=fopen("./data.txt","w"))==NULL){exit(1);//打开文件失败};//写入内容chars[]="iloveyou***";if(fputs(s,fp)!=0){exit(2);//写入失败}//关闭失败fclose(fp);return0;}

编程杂谈

位域(是表示二进制的位)使用位域是节省内存的一种操作,它能是int不用占用4字节的空间虽然现在的机器都是8G、16G的,但是在单片机的寸土寸金的内存上,还是需要对内存占用进行自定义的控制位的大小:8位构成1字节。1byte(字节)=8bit(位);字节的大小:1024字节等于1KB。1KB=1024B(字节);//位域的定义是在结构体里structToDay{unsignedintmouth:3;//在成员名后加冒号:位的大小undignedintday:2;};位于的使用#include<stdio.h>structToDay{unsignedintmouth:3;//在成员名后加冒号:位的大小unsignedintday:2;}toDay;intmain(void){toDay.mouth=8;toDay.day=3;printf("sizeoftoDay:%d\n",sizeof(toDay));printf("toDay.mouth=%d\n",toDay.mouth);printf("toDay.day=%d\n",toDay.day);return0;}位操作位操作时对二进制位进行一元和二元操作逻辑操作在许多古老的微处理器上,位运算比加减运算略快,通常位运算比乘除法运算要快很多在现代架构中,情况并非如此:位运算的运算速度通常与加法运算相同(仍然快于乘法运算)。运算符含义优先级举例说明~按位取反高~a如果a为1,则~a为0;如果a为0,则~a为1;&按位取与中a&b只有ab同时为1,结果才为1;只要ab其中一个为0,结果就为0;^按位取异或低a^b如果ab不同,则结果为1;如果ab相同,则结果为0;|按位取或最低a|b如果ab其中一个为1,则结果为1;如果ab同时为0,则结果为0;按位取反(~)~000000=>111111按位取与(&)001010&010110=>000010按位取异或(^)010110^011001=>001111按位取或(|)010011|100110=>110111