二叉树的遍历因为使用二叉树最多是链式存储结构，所遍历的方式也是按照链式结构来的。遍历的宗旨在遍历是按照某种次序依次访问二叉树的所有节点，并且每个节点仅仅被访问一次。前序遍历（根左右）遍历顺序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");}输出：算法需要至少一个或者多个输出。有穷性是指在执行有限的步骤后，自动结束，并且每一步都是在可接受的时间范围内完成。确定性：算法的每一步都具有确定的含义，不会出现二义性。相同的输入只能有唯一的输出结果。可行性：算法的每一步都必须是可行的，就是说，每一步都能通过执行有限的次数完成。算法设计的要求正确性：是指算法至少应该具有输入、输出和加工处理无歧义，能得到正确的结果。大致分为以下四个层次算法程序没有语法错误算法程序对于合法的输入能得到满足要求的输出算法程序对于非法输入能产生相应的说明算法程序对于故意刁难的测试输入都有满足要求的输出结果可读性算法需要便于阅读、理解和交流，方便日后他人和自己的阅读和修改。健壮性当输入不合法时，算法也能做出相关的处理，而不是产生异常、崩溃或莫名其妙的结果时间效率高和存储量低在生活中大家都想找一个漂亮乖巧懂事，懂分寸的女朋友。好的算法就像好的女朋友，应该同时具备时间效率高和存储量低的特点，设计算法时，因尽量考虑这两方面的问题!!!