## 函数调用 通常，当一个函数运行期间调用另一个函数时，在运行被调函数之前，系统需要完成3件事： （1）将所有的实参，返回地址（个人理解是调用被调函数时的下一个语句的地址）等信息传递给被调函数保存。 （2）为被调函数的局部变量分配存储空间。 （3）将控制转移到被调函数入口。 从被调函数返回调用函数之前，系统完成3件事： （1）保存被调函数的计算结果。 （2）释放被调函数的数据区。 （3）依照被调函数保存的返回地址，将控制转移到调用函数。 ## 递归： 一个函数自己直接或间接调用自己。 思想就是：将问题规模不断缩小，化繁为简，求n！转化成（n-1）!,再转换成(n-2)！.......最后转换成(1)!.  有如汉诺塔问题，如果初始有10个砝码，要从A移动到C，这个看起来比较复杂。只要把前9个移动到B，然后移动第10个到Ｃ。那这9个怎么移动呢，也用这种方式。。。这就是递归实现汉诺塔详细代码见最下方 ### 循环和递归比较： 递归： 易于理解 速度慢 存储空间大 循环 不易于理解 速度快 存储空间小 ### 递归应用：     1.求阶乘 2.1+2+3+4+。。。+100的和 3.汉诺塔 4.走迷宫(CS的实现) 递归的运用： 树和森林就是以递归的方式定义的 树和图的很多算法都是以递归来实现的 很多数学公式就是以递归的方式定义的 斐波拉契序列 12 3 5 8 13 21 34。。。 C语言实现汉诺塔： ~~~ #include<stdio.h> void hanota(int num,char A,char B,char C) { //如果只有一个元素，那么直接把这个元素，移动到C if(1==num) { printf("把第%d个元素从%c移动到%c\n",num,A,C); }else{ //如果不是第一个元素，先把前n-1个元素，借助C移动到B hanota(num-1,A,C,B); //然后把A最下面的元素移动到C printf("把第%d个元素从%c移动到%c\n",num,A,C); //然后再把B上的元素借助A移动到C hanota(num-1,B,A,C); } } int main() { char A='A'; char B='B'; char C='C'; hanota(3,A,B,C); return 0; } ~~~ 现实生活中，如果我们解决的问题比较繁琐，不妨把问题规模减小考虑。

~~~ #include<stdio.h> #include<malloc.h> #include<stdbool.h> typedef struct Queue{ int * PBase;//指向数组第一个元素的指针 int front;//队列头部元素下标 int rear;//队列尾部元素下标 }QUEUE; /** *初始化队列，实现队列的数组长度为6。 **/ void initQueue(QUEUE * pQ) { pQ->PBase=malloc(sizeof(int)*6); pQ->front=0; pQ->rear=0; } /** 判断队列是否已满 */ bool isFull(QUEUE * pQ) { if((pQ->rear+1)%6==pQ->front) { printf("队列已满，无法插入"); return true; } return false; } /** 判断队列是否为空 */ bool isEmpty(QUEUE * pQ) { if(pQ->front==pQ->rear) { printf("队列为空"); return true; } return false; } /** 入队 */ bool insert(QUEUE * pQ,int val) { if(isFull(pQ)) return false; pQ->PBase[pQ->rear]=val; pQ->rear=(pQ->rear+1)%6; return true; } /** 遍历队列 */ void traverse(QUEUE * pQ) { int i=pQ->front; while(i!=pQ->rear) { printf("%d ",pQ->PBase[i]); i++; } printf("\n"); } /** 出队 */ bool out_queue(QUEUE * pQ) { if(isEmpty(pQ)) return false; pQ->front=(pQ->front+1)%6; } int main() { QUEUE Q; initQueue(&Q); insert(&Q,1); insert(&Q,2); insert(&Q,3); insert(&Q,4); insert(&Q,5); insert(&Q,6); traverse(&Q); out_queue(&Q); traverse(&Q); return 0; } ~~~ 涉及的知识点讲解见上一篇文章:[http://blog.csdn.net/davidluo001/article/details/46596553](http://blog.csdn.net/davidluo001/article/details/46596553) 关键:1.少用一个位置,用于区分队列是空还是满.

## 队列的具体应用：  所有和事件有关的操作都有队列的影子。 （例如操作系统认为先进来的先处理） ## 定义： 一种可是实现“先进先出”的存储结构 ## 分类： 链式队列：用链表实现   静态队列：用数组实现 静态队列通常都必须是循环队列，为了减少内存浪费。  ## 循环队列 ： ### 1、静态队列为什么必须是循环队列 如果用传统意义的数组实现队列，无论入队还是出队，rear和front指针只能＋不能-； 比 F元素下标小的的数组元素下标就浪费了。 ###循环队列怎么用呢？  当出现这种情况时，如果仍然需要插入元素，那么f指向下一个位置，即5，r指向下一个位置即0.如图：  那么，我们在插入一个元素“国”，然后再删除中呢？  这就是所谓的循环队列。 ### 2、    循环队列需要几个参数来确定 及其含义 需要2个参数来确定 front rear   ### 3、 循环队列各个参数的含义 2个参数不同场合不同的含义?    建议初学者先记住，然后慢慢体会 1）队列初始化 front和rear的值都是零,初始化时队列就是空的。 2）队列非空 front代表队列的第一个元素 rear代表了最后一个有效元素的下一个元素 3）队列空 front和rear的值相等，但是不一定是零 ### 4、循环队列入队伪算法讲解 需要判断r是否指向数组最后一个元素。 两步完成： 1）将值存入r所代表的位置 2）将r后移，正确写法是rear = (rear+1)%数组长度 错误写法：rear=rear+1;   ### 5、 循环队列出队伪算法讲解  front = (front+1)% 数组长度 ### 6、 如何判断循环队列是否为空 如果front与rear的值相等， 则队列一定为空 ### 7、 如何判断循环队列是否已满  上图这种情况，如果再插入f,r指向同一个元素。如果这样的话就不能判断队列是空还是满。 所以为了判断循环队列是否已满,有一下两种方式: 1、多增加一个表标识的参数 2、少用一个队列中的元素（才一个，不影响的） 如果r和f紧挨着(r的下一个位置是f)，则队列已满 用C语言描述： If((r+1)%数组长度)==f   队列已满 Else   队列不满

写程序的时候，我们经常会说基本类型变量存在栈内存，引用类型的变量（对象，数组）存在堆内存。现在我们来看看栈这种数据结构是怎么实现的。 ## 定义 一种可以实现“先进后出” 的存储结构 栈类似于往箱子放衣服，先放的最后拿 ## 栈的分类： 静态栈：以数组方式实现，删除时删除下标最大的,插入时从最大下标+1插入 动态栈：以链表方式实现，删除和插入都是从头部 ## 算法：出栈（POP），入栈（PUSH） ## 应用： 1.函数调用 :在函数f中调用另一个g函数，在g函数中调用k函数 执行到要调用g函数位置，先把g函数执行后下一句的地址以及变量压栈，执行g函数，执行到调用k函数的位置，再把k函数执行后的下一句压栈，然后执行k函数，执行后取出栈顶元素，赋给CPU，执行g函数中调用k函数后的下一句。 2.中断 3.表达式求值：3*2+5/6-4两个栈实现，一个放运算符，一个放数据 4.内存分配：把函数形参压入栈中 5.缓冲处理 6.走迷宫 ## C语言实现： 下面是C语言实现动态栈的代码，为了方便在栈底部建立一个头结点，不存有效数据。先看图：  ~~~ #include<stdio.h> #include<malloc.h> #include<stdbool.h> //栈有一个不存放有效数据的头节点，Pbotom始终指向头结点。 /** **定义节点的结构体 */ typedef struct Node{ int data;//数据域 struct Node * PNext;//指针域 } Node,*PNext; /** **定义栈的结构体 */ typedef struct Stack { PNext top; PNext bottom; }Stack,* PStack; /** **初始化栈 */ void init(PStack PStack ) { //建立一个不存任何有限元素的头结点，作为栈底 PStack->bottom=malloc(sizeof(Node)); PStack->top=PStack->bottom; PStack->top->PNext=NULL; } /** *遍历栈 **/ void traverse(PStack Ps ) { if(Ps->bottom==Ps->top) { printf("栈为空\n"); return ; } PNext pt=Ps->top; while(pt!=Ps->bottom)//不能把pt换成ps->top这样就修改了链表。尴尬。。 { printf("%d ",pt->data); pt=pt ->PNext; } printf("\n"); return ; } /** **入栈 */ void push(PStack Pstack,int val) { PNext Pnew=malloc(sizeof(Node));//生成一个新节点 Pnew->data=val; Pnew->PNext=Pstack->top; Pstack->top=Pnew; } /** **出栈 */ void pop(PStack ps ) { if(ps->top==ps->bottom) { printf("栈为空，无法完成出栈操作\n"); return; } PNext temp=ps->top;//引入辅助变量，用于释放内存 ps->top=ps->top->PNext; free(temp); temp=NULL; } /** **清空栈 */ void clear(PStack ps) { while(ps->top!=ps->bottom) { PNext temp=ps->top; ps->top=ps->top->PNext; free(temp); } } int main() { Stack stack; init(&stack); push(&stack,6); push(&stack,7); push(&stack,8); traverse(&stack); pop(&stack); traverse(&stack); clear(&stack); traverse(&stack); push(&stack,7); traverse(&stack); return 0; } ~~~

~~~ #include<stdio.h> #include<malloc.h> #include<stdbool.h> /** **链表节点的定义 */ typedef struct Node{ int data;//数据域 struct Node * PNext;//指针域，存放下一个节点的地址 } Node ,* PNode ; /** **创建链表 */ PNode create_list() { int len,i; printf("请输入链表的长度：len=\n"); scanf("%d",&len); PNode PHead=malloc(sizeof(Node)); PHead->PNext=NULL; PNode PTail=PHead;//PTail是永远指向尾节点的指针 for(i=0;i<len;i++) { int val; printf("请输入第 %d 个元素的值：", i+1); scanf("%d",&val); PNode PNew=malloc(sizeof(Node)); PNew->data=val; PNew->PNext=NULL; PTail->PNext=PNew; PTail=PNew; } return PHead; } /** **对链表进行遍历 */ void traverse(PNode pHead) { PNode p=pHead->PNext; while(p!=NULL) { printf("%d ",p->data); p=p->PNext; } printf("\n"); } /** *判断链表是否为空 */ bool isempty(PNode pHead) { if(NULL==pHead->PNext) { return true; }else{ return false; } } /** **获取链表的长度 */ int list_num (PNode pHead) { int num=0; PNode p=pHead->PNext; while(p!=NULL) { num++; p=p->PNext; } return num; } /** *向链表中插入元素 */ bool insert_list(PNode pHead,int val ,int pos){ //需要找到第pos个位置，并且需要判断这个位置pos是否合法 //i是p所指节点的位置，所以从一开始，为什么要pos-1呢，因为用的是while 当i=pos-1时跳出循环 int i=0; PNode p=pHead; while(NULL!=p&&i<pos-1) { i++; p=p->PNext; } //如果插入位置过大，那么P=NULL, //如果插入的位置是0或者负数，那么i>pos-1 if(i>pos-1||NULL==p) { printf("插入位置不合法\n"); return false; } PNode PNew=malloc(sizeof(PNode)); PNew->data=val; PNode temp=p->PNext; p->PNext=PNew; PNew->PNext=temp; return true; } /** **在链表中删除节点 */ delete (PNode PHead,int pos , int * pval) { int i=0; PNode p=PHead; //我们要删除p后面的节点，所以p不能指向最后一个节点 p->next!=NULL while(p->PNext!=NULL&&i<pos-1){ p=p->PNext; i++; } if(i>pos-1||p->PNext==NULL) { printf("删除位置不合法\n"); return false; } PNode temp=p->PNext; p->PNext=temp->PNext; free(temp); } int main() { PNode PHead= create_list(); if(isempty(PHead)) printf("链表为空\n"); printf("链表的长度为：%d\n",list_num(PHead)); traverse(PHead); //insert_list(PHead,55,1); int val; delete(PHead,6,&val); traverse(PHead); return 0; } ~~~

### 链表的优缺点： 优点： 空间没有限制 插入删除元素很快 缺点： 存取速度很慢。 定义： n个节点离散分配（在内存中不是连续存储） 彼此通过指针相连 每个节点只有一个前驱节点，每个节点只有一个后续节点 首节点没有前驱节点，尾节点没有后续节点。 首节点： 第一个有效节点 尾节点： 最后一个有效节点 头节点： 头结点的数据类型和首节点的类型一样 没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作。 头指针：（指向头） 指向头节点的指针变量 尾指针： 指向尾节点的指针 （头结点有可能很大，占的内存可能大，假设我想造一个函数输出所有链表的值，那你如果不用头指针类型做形参，那由于不同链表的头节点不一样大小，这样就没办法找出形参） 确定一个链表需要几个参数：（或者说如果期望一个函数对链表进行操作我们至少需要接收链表的那些信息？？？） 只需要一个参数:头指针，因为通过它我们可以推出 链表的所有信息。 （链表的程序最好一定要自己敲出来） 链表的分类： 单链表 双链表： 每一个节点有两个指针域 循环链表 能通过任何一个节点找到其他所有的节点 单链表伪算法： 1.插入节点： 在p指向的节点后面插入一个被q指向的节点：   P存放的是指向的节点的地址，q也是。next指针存放的是下一个元素的地址。   q->next=p->next;p->next=q; **也可以** **r=p->next; p->next=q;q->next=r;**   删除p后面的节点   P->next=p->next->next 会造成内存泄露，无法找到要删除的节点，无法释放内存。 正确做法：临时定义一个指针r 存放要删除节点的地址 r=p->next; p->next=p->next->next; free(r);//释放所指节点占用的内存

基本思想：数组是最常用的数据结构，在内存中连续存储，可以静态初始化（int a[2]={1,2}），可以动态初始化 malloc（）。 难点就是数组在删除或者插入元素的时候，要移动元素的坐标不好确定。规律： 1.如果要在数组中第pos个位置插入一个元素（应该从后面开始移动） for( i=cnu;i>=pos;i--) pBase[i]=pBase[i-1]; 2.删除数组第pos位置的元素 for(i=pos+1;i<=cnu;i--) pBase[i-2]=pBase[i-1]; 使用malloc动态分配内存并将返回值赋给整形指针 int *pBase=(int *)malloc(sizeof(int)*len);//分配4*len字节长度的内存 这是pBase可以指向数组中的第一个元素，可以作为数组变量名称使用。 数组的优缺点： 优点： 存取速度快 o(1) 可以直接根据下标找到内存位置 缺点： 事先必须知道数组的长度 插入删除元素很慢 空间通常是有限制的 需要大块连续的内存块 插入删除元素的效率很低 ~~~ #include<stdio.h> #include<malloc.h> #include<stdbool.h> struct Arr{ int len;//数组能存取的最大元素个数 int cnu;//数组中当前元素个数 int * pBase;//存储指向数组的指针 }; /** *初始化数组 */ void init_array(struct Arr * pArray,int len){ pArray->pBase=(int *)malloc(sizeof(int)*len);//分配4*len字节长度的内存 if(NULL== pArray->pBase)//判断内存是否分配失败 { printf("动态分配内存失败\n"); // exit(-1); }else{ pArray->len=len; pArray->cnu=0; } return ; } /** *判断数组是否为空，传地址省内存4字节，传结构体变量需要进行拷贝，12字节 */ bool isempty(struct Arr * pArray){ if(0==pArray->cnu) { return true; }else{ return false; } } /** **判断数组是否满了 */ bool isfull(struct Arr * pArray) { if(pArray->len==pArray->cnu) { return true; }else { return false; } } /** *显示数组内容 */ void show_array(struct Arr * pArray){ if(isempty(pArray)) printf("数组为空！\n"); else{ int i; for( i=0; i<pArray->cnu;i++) { printf("%d \n",pArray->pBase[i]); } printf("------------------------------------\n"); } } /** **向数组追加元素 */ bool append(struct Arr * pArray,int val){ if(isfull(pArray)) { printf("数组已经满了！\n"); return false; }else{ pArray->pBase[pArray->cnu]=val; pArray->cnu++; } } /** **向数组中插入元素,pos为数组中第几个位置，pos=3就是向a[2]插入元素 */ bool insert(struct Arr * pArray,int pos,int val) { if(pos<1||pos>pArray->len+1)//插入的位置不能小于1，同时不能比最后一个元素大二 { printf("插入的位置输入的不合法\n"); return false; } if(isfull(pArray)) { printf("数组已经满了,插入失败！\n"); return false; } int i; //循环将pos位置开始的数组后移 for(i=pArray->cnu;i>=pos;i--) //移动范围是从第pos个到底cnu个 { pArray->pBase[i]=pArray->pBase[i-1]; /** 若以i表示要移动元素的位置，从一开始的。右边都是i-1,若左移，左边是i-2,右移，左边是i */ } pArray->pBase[pos-1]=val; pArray->cnu++; pArray->len++; return true; } /** **删除数组中的第pos个元素，同时返回删除的元素的值 */ bool delete(struct Arr * pArray,int pos,int * val) { if(pos<1||pos>pArray->cnu) { printf("删除失败，位置不合法\n"); return false; } int i; *val=pArray->pBase[pos-1]; for(i=pos+1;i<=pArray->cnu;i++) { //移动单位是从第pos+1个到cnu pArray->pBase[i-2]=pArray->pBase[i-1]; } pArray->cnu--; return true; } /** **数组倒置 */ bool inverse(struct Arr * pArray) { if(isempty(pArray)) { printf("倒置失败，因数组为空"); return false; } int i=0; int j=pArray->cnu-1; int temp; while(i<j) { temp=pArray->pBase[i]; pArray->pBase[i]= pArray->pBase[j]; pArray->pBase[j]=temp; i++; j--; } return true; } int main() { struct Arr arr; init_array(&arr,6);//将结构体的地址作为实参，这样才能修改结构体中的值，如果传的是结构体变量，那么将进行拷贝，不会改变值 append(&arr,1); append(&arr,2); append(&arr,3); append(&arr,4); show_array(&arr); insert(&arr,2,88); show_array(&arr); int val; delete(&arr,1,&val); show_array(&arr); printf("删除了 %d\n",val); inverse(&arr); show_array(&arr); return 0; } ~~~

> 原文出处：[手把手教你数据结构C语言实现](http://blog.csdn.net/column/details/datastructbyc.html) 作者：[davidluo001](http://blog.csdn.net/davidluo001) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 手把手教你数据结构C语言实现 > 手把手教你数据结构C语言实现