不麻烦的数据结构

数据结构以及代码实现

前言

作者一直想要更新关于C语言方面的内容，奈何原本想更新的《速通C语言》在下手写的时候发现不是那么简单，毕竟C牵扯的太多了，小到hello world，大到语言本身对于计算机硬件、内存以及系统的影响，思来想去突然想起来去年冬天学的数据结构，既然硬骨头啃不动那就先吃点软的

本文章仅仅讲述各种数据结构的实现方式和结构理解，可以看作一个启蒙文章，以下是作者对各种数据结构的讲解方案

------数据结构名称
|----原理，效果图
|----代码解释
||--增（创建，插入）
||--删（删除）
||--改（修改数据）
||--查（遍历）

可见以上缺少了功能对比，这是因为所谓的功能对比需要读者自行总结，因为在同一种情景下可能有多种数据结构可以解决问题，但总有一种情况是最适合当下情景的，而因为情景的不同，并没有一个数据结构的优势可以在任何情况下成为他的优势

就好像glibc管理动态内存（堆内存）的ptmalloc库，它用的数据结构就是双向链表，这很好的解决了内存访问的速度以及堆块之间的插入合并，但相对于树又显得笨重以及缺少逻辑，而树这种数据结构却承载不了ptmalloc的逻辑以及堆块之间的合并问题会增加内存的开销，所以我的意思是，没有绝对的优势，只有在不同情况下相对的优势，以上需要读者在学习后的实践中自行摸索，毕竟作者也没有能力总结出一招鲜的“圣经”

而在笔记开始之前，请读者在刚打开的.c文件的开头加上以下内容

#include <stdio.h>
#include <string.h>
//与指针数组字符串关系紧密的头文件
#include <stdlib.h>
//与堆，内存分配关系紧密的头文件
#include <ctype.h>
//与数学相关的头文件
#define IK 666
//定义宏，666的大小已经足够我们后面代码的开销
typedef int elem;
//因为我们不知道结构体中数组的最佳类型是什么，就比如有的时候我们可能使用int就足够，但如果在实现的过程中发现好像这里需要使用浮点数类型，亦或者在此时int的大小已经不足以存下所有的数据可能需要使用类似于long int，所以使用typedef来定义elem，这就方便了后期如果有需要直接改这一行代码就可以了

哦对了，先介绍两个名词，

• 前驱
• 后继

其实前驱和后继的定义是比较简单的，前驱就是指前一个，后继就是指后一个，注意，在本篇文章中几乎不会使用到这两个词语，如果在学习之后看到了这两个词语，那么请读者自行理解，因为在本篇文章中我们主要关注的是数据结构的实现

一.线性表

结构原理

这是最简单的一种数据结构，里面只包含两个信息

• 线性数据库
• 已储存数据所占用的大小

这里先行批注一下,文章中的指针有时有索引之意，有时仅仅表示C语言中的指针，请读者按照上下文语意自行辨认

具体效果如下

所以我们在创建线性表的结构体时十分之简便

typedef struct{
    elem data[IK];
    int length;
}seplist;

以上就定义了一个线性表，首先data数组里存储信息，length作为指针来判断存储的位置以及是否超出了存储的极限

你可以这么理解，因为我们最开始定义了IK为666，所以这个数组最大就是一个666格的鞋柜，length代表你占用了多少个鞋柜，当length等于了666，就证明你的鞋柜满了，已经不能往里放东西了

那么这一时刻就有老铁要问了，煮波煮波，length不应该在等于665的时候鞋柜就满了吗，为什么你说是666

因为刚刚有讲到length指的是 已储存数据所占用的大小 也就是说当length为8的时候并不是说第九个柜子里有鞋，而是一共放了八双鞋

代码解释

增

• 创建新线性表

  seplist* create_and_init(){
    seplist* newdata;
    newdata->length=0;
    return newdata;
  }

  那么这一时刻又有老铁不明白了，既然初始化了，为什么不把数组给置零，而是仅仅把length给置零了

  煮波的回答是根本不需要，从另外一个角度来说，指针length没指向的地方就是还没利用到的空间，用鞋盒法来理解就是，我们既然已经确定这个鞋柜里只存鞋而且length这个指针指向了你存到了第几个格子，那为什么要管其他你还没存鞋的格子里存储的是什么呢

  就好比当你的length是0的时候，整个鞋柜里的各个格子里有雨伞，钥匙，钱包，充电宝之类的，当我的length为3的时候，那我就保证前三个格子里放的是鞋就好了，因为大于3的部分我没放鞋，就算闲的没事去看，你也没法在里面找到鞋，而等你想往别的地方存鞋的时候，那就把占用在格子里的杂物拿出来放进去鞋（直接赋值，相当于把原来的东西覆盖掉）再把length增加到你存储的位置就可以了，下面上代码

• 新增数据(尾插法)

  void add_end(seplist *k,elem b){
    if(k->length>=IK){
        printf("满了捏\n");
        return 0;
    }
    //判断输入是否过多，数组空间是否有余
    k->data{k->length}=b;
    k->length++;
    //开始填东西
  }

• 新增数据(头、中间插入)

  int insert(seplist *k,int p,elem b){
    if(k->length>=IK){
        printf("满了捏\n");
        return 0;
    }
    if(p<1||p>k->length){
        printf("插的地方不对\n"):
        return 0;
    }
    //两个判断，先来判断一下是不是数组满了，再判断一下是不是在数组中间进行插入
    if(p<=k->length){
        for(int i=k->length-1;i>=p-1;i--){
            k->data[i+1]=k->data[i];
        }
        //每个数据都往后退一个字长，来让要插入的位置有空位置
        k->data[p-1]=e;
        k->length++;
        //时时记得长度要增加
    }
    return 1;
  }

删

• 定点删除

  int det(seplist *k,int p,elem b){
    if(p<1||p>k->length){
        printf("删的地方不对\n"):
        return 0;
    }
    if(p<=k->length){
        for(int i=p-1;i<k->length-1;i++){
            k->data[i]=k->data[i+1];
        }
        //每个数据都往前进一个字长直接覆盖上
    }
    k->length--;
    return 1;
  }

改

• 定点改动

  int change(seplist *k,int p,elem b){
    if(p<1||p>k->length){
        printf("改的地方不对\n"):
        return 0;
    }
    k->data[p-1]=b;
    return 1;
  }

查

• 遍历

  void print(seplist *k){
    for(int i=0;i<k->length;i++){
        printf("%d ",k->data[i]);
    }
    printf("\n");
  }

• 定点打印

  void print(seplist *k,int p){
    printf("%d ",k->data[p-1]);
  }

二.单双向链表

结构原理

在解释链表之前我们先上一个图片

可见上述的这个图片是一个铁链，这也就是链表的结构原理，当然，我知道这很抽象，那接下来的两张图片就可以将这种抽象转化成具象

以上就是单向链表的示意图，可见每个单项链表的元素中都包含两部分

• 数据域
• 指针域

数据域就是你要存储的信息，指针域就是指向下一个元素的指针，怎么样，这一时刻是不是有一种每个元素都由一个指针链在一起的感觉，这也就是单向链表的结构原理，前一个元素的指针存着下一个元素的地址，而最后一个元素的指针则指向了空（NULL），操作者可以顺着指针的走向实现元素的增删改查，但这就出现了一个问题，就是没法走”回头路”这就需要操作者必须知道第一个元素的地址，因为如果仅仅知道中间某个元素的地址，操作者就没法得知这个元素之前的元素都是什么内容，这也就导致了数据丢失，而此时双向链表出现了

以上就是双向链表的示意图，可见每个双向链表的元素中都包含三部分

• 数据域
• 前向指针域
• 后向指针域

数据域就是你要存储的信息，前向指针域就是指向上一个元素的指针，后向指针域就是指向下一个元素的指针，怎么样，这一时刻是不是有一种每个元素都由两个指针链在一起的感觉，这也就是双向链表的结构原理，前一个元素的后向指针存着下一个元素的地址，而最后一个元素的后向指针则指向了空（NULL），同时，后一个元素的前向指针存着上一个元素的地址，而最开始的那个元素的前向指针则指向了空（NULL）操作者可以顺着指针的走向实现元素的增删改查，同时也可以从后往前走

可能此时你觉得，双向链表的结构比单向链表更加高级，单向链表应该被淘汰，但事实上，单向链表因为只有一个指针域，所以在内存占用上要比双向链表小，操作速度也会更快，这就是为什么煮波在前言中说”没有绝对的优势”了。

话不多说，上代码

typedef struct{
	elem data;
	struck node *next;
}node;
//以上创造了一个单向链表，这个数据结构由两部分组成，一部分是自己存储的内容，另一部分是指向下一结构体的指针
typedef struct{
  elem data;
  struck dnode *next;
  struck dnode *prior;
}dnode;
//以上创造了一个双向链表，这个数据结构由三部分组成，一部分是自己存储的内容，另一部分是指向下一结构体的指针，另一部分是指向上一结构体的指针

这就定义了单向链表和双向链表

代码解释

增

• 创建单向链表

    node *init(){
      node *head=(node*)malloc(sizeof(node));
      head->data=0;
      head->next=NULL;
      return head;
    }
    //初始化，指针指向空因为这个链中仅仅只有这一个节点，所以它的下一个节点就是空
    ~~~  
  * 创建双向链表
    ~~~c
    dnode *init(){
      dnode *head=(dnode*)malloc(sizeof(dnode));
      head->data=0;
      head->next=NULL;
      head->prior=NULL;
      return head;
    }
    //初始化，指针指向空因为这个链中仅仅只有这一个节点，所以它的下一个节点和上一个节点都是空

• 头插法之单向链表

   int inserthead(node *l,elmetype e){
  node *p=(node*)malloc(sizeof(node));
  p->data=e;
  p->next=l->next;
  l->next=p;
   }
   //链表头插法，先开辟一个空间，然后开始往里搞东西，然后指针指向本来的头

• 头插法之双向链表

  int inserthead(dnode *l,elmetype e){
    dnode *p=(dnode*)malloc(sizeof(dnode));
    p->data=e;
    //新节点填数据
    
    p->next=l->next;
    //新节点的后向指针指向本来头指针的下一个节点
    
    p->prior=l;
    //新节点的前向指针指向头指针
    
    if(l->next!=NULL){
      l->next->prior=p;
    }
    //如果头指针的下一个节点不是空，那么就把头指针的下一个节点的前向指针指向新节点
    
    l->next=p;
    //头指针的下一个节点指向新节点
  }

  这里画一个辅助图供大家理解
  
  可见双向链表如果想要插入一个元素，就需要调整四个指针

  • 新节点的后向指针指向头节点的下一个节点
  • 新节点的前向指针指向头节点
  • 如果头节点的下一个节点不是空，那么就把头节点的下一个节点的前向指针指向新节点
  • 头节点的下一个节点指向新节点

  这回再看上述代码是否更加清晰了呢

• 单向链表尾插法

   node *inserttail(node *l,elemtype e){
  node *p=(node*)malloc(sizeof(node));
   node *tail=l;
   p->data=e;
  while(tail->next!=null){
  	tail=tail->next;
    }
   tail->next=p;
   p->next=null;
   }

• 双向链表尾插法

  dnode *inserttail(dnode *l,elemtype e){
    dnode *p=(dnode*)malloc(sizeof(dnode));
    node *tail=l;
    p->data=e;
   while(tail->next!=null){
    tail=tail->next;
   }
    tail->next=p;
    p->next=null;
    p->prior=tail;
  }

  因为在结尾插入，所以只需要调整两个指针，一个是尾指针的后向指针，一个是新节点的前向指针

• 单双向链表的中间插入就不写了，因为与头插法很像，如果有兴趣读者可以试着自行实现

查

• 单向链表查询

  int search(node *l,elemtype e){
  //单向链表头节点为起点查询
    node *p=l;
    int i=0;
    while(p!=NULL){
      if(p->data==e){
        return i;
      }
      p=p->next;
      i++;
    }
    return -1;
  }

  i代表步数，i为多少就是走了多少步查到的，如果i为0，那就是头节点就是需要找的节点，如果为-1，那就是没有找到
• 双向链表查询

  void search(dnode *l,elemtype e){
  //双向链表任意节点查找  
    dnode* p=l,f=l;
    int i=0,q=0;
    while(p!=NULL||f!=NULL){
      if(p->data==e){
        return i;
      }
      else if(f->data==e){
        return q;
      }
      
      if(f!=NULL){
        f=f->prior;
      }
      if(p!=NULL){
        p=p->next;
      }
  
      i++;
      q--;
    }
    return printf("未找到");
  }

  双向链表查找

删

• 单向链表删除

   int deletenode(node *l,int pos){
  node *p=l;
  int i=0;
  while(i<pos-1){
  	p=p->next;
  	i++;
  	if(p=null){
  		return 0;
  	}
  }
  if(p->next=null){
  	printf("哥你删哪去了？")
  	return 0;
  }
  node *q=p->next;
  p->next=q->next;
  free(q)
  return 1;
   }

  首先我们先遍历了一遍去寻找要删除节点的前一个节点，在寻找的过程中去判断删除的位置是不是在链表外，然后我们来研究一下这个是不是最后一个节，在两个条件都满足的情况下，我们设置一个新的链表去存放我们要删除的链表紧接着把这个链表对下一个（后继）的定位赋值给上一个链表(前驱)的定位（p->next=q->next;），最后我们将这个内存free掉
• 单向链表全部删除

  void freelist(node *l){
   node *p=l->next;
   node *q;
   while(p!=null){
    q=p->next;
    free(p);
    p=q;
   }
   l->next=null;
  }

  两个指针一个走一个删无需多言
• 双向链表删除

   int deleteNode(Node *l,int pos){
  Node *p=l;
  int i=0;
  while(i<pos-1){
  	p=p->next;
  	i++;
  }
  Node* q=p->next;
  p->next=q->next;
  q->next->prev=p;
  free(q);
  return 1;
   }

  和单项指针差不多，只不过多了前向指针需要调整
• 双向链表全部删除

  void freelist(Node *l){
   Node *p=l->next;
   Node *q;
   while(p!=null){
    q=p->next;
    free(p);
    p=q;
   }
   l->next=null;
  }

  这个可以说是跟单项指针删除一样了

改

• 单向链表改

  int changenode(node *l,int pos,elemtype e){
  node *p=l;
  int i=0;
  while(i<pos){
    p=p->next;
    i++;
    if(p=null){
      return 0;
    }
  }
  p->data=e;
  return 1;
  }

• 双向链表改

  int changenode(dnode *l,int pos,elemtype e){
  dnode *p=l;
  int i=0;
  while(i<pos){
    p=p->next;
    i++;
    if(p=null){
      return 0;
    }
  }
  p->data=e;
  return 1;
  }

  以上两个函数都比较简单，就不做过多解释了，这里说明一下，如果你不知道你想要改或者删的位置，可以套用查部分的函数来用信息查找位置或者直接改变传参来实现

三.链表的特殊情况与多指针算法

讲到链表不讲多指针等于没讲多指针，其实上述我们在实现链表的删除部分已经涉及到了双指针算法，但多指针又确确实实是一种独立且可以解决很多奇怪问题的算法，所以我们单独开辟一个模块来讲解多指针的相关内容

结构原理

首先，在链表中会有一大堆特别的链表，就比如


如上图就是两个特殊的链表，一个叫双线链表，一个叫循环链表

而多指针算法在这里就很方便的实现了一堆奇奇怪怪的问题，比如循环链表的入口节点是哪里，双线链表的焦点是什么，如何将一个单向链表倒叙，如何判断一个单向链表是否有环以及某个单相链表的倒数第k个节点是什么

下面我们边演示实现方式边解答上面的问题

代码解释

• 搜索链表的倒数第k个节点
  这里我们用到快慢指针，所谓快慢指针有两种情况

  • 快指针先移动，然后慢指针再跟着快指针同时同速移动
  • 快慢指针同时移动，但是快指针的速度是慢指针的倍数

  而为了查找链表的倒数第k个节点，我们就可以使用第一种情况，就是快指针先移动k-1个节点，然后慢指针再与快指针一起移动，就比如k=3，那么快指针就先走到第三个节点（移动两个节点：1->2，2->3）上然后慢指针与他同时移动，等快指针停下来的时候循环结束，此时慢指针就恰好指向了倒数第三个节点上，因为快指针与慢指针同速，所以二者的距离始终是两个节点，如下图
  
  代码实现如下：

   void findnodefs(node *l,int k){
  node *fast=l->next;
  node *slow=l->next;
  for(int i=0;i<k-1;i++){
  	fast=fast->next;
  }
  while(fast!=null){
  	fast=fast->next;
  	slow=slow->next;
  }
  printf("倒数第%d个节点是%d",k,slow->data);
   }

• 判断一个单项链表是否有环
  也是用双向链表解决这个问题，但用的是第二种快慢指针，一般设置快指针每次移动两个节点，慢指针每次移动一个节点，当快指针与慢指针相遇时，说明链表有环，否则说明链表无环

  那么这一时刻肯定又有老铁要问了，煮波煮波，为什么要用快慢指针，你怎么就断定有环的情况下快慢指针会相遇

  这个问题是一个数学问题，而且是一个很难用一张图片来展示的问题，所以一下我们只给出一张循环链表图，多余的部分请读者想象
  
  如果这个链表有环，那么快指针就会率先进入环中，慢指针则稍后进入环中，这一点没有问题吧？

  那么当慢指针进入环中时，这是不是一个经典的操场跑圈追及问题，快指针每次移动两个单位，慢指针每次移动一个单位，二者的速度差为一，也就是二者的相对距离每一个时间单位就减少一，那么如果有环，快慢指针一定可以相遇，而又因为单向链表只有一个方向，所以二者在跑道里也是同向而行，不用考虑相向错过的情况

   int incycle(node *head){
  node* fast=head;
  node *slow=head;
  while(fast!=null&&fast->next=!null){
     //如果快指针下一个为null，说明没有环
  	fast=fast->next->next;
  	slow=slow->next;
  	if(fast==slow){
  		return 1;
  	}
  }
  return 0;
   }

• 查找循环链表的入口节点
  这次我们同时用到了快慢指针的两种原理，首先让快慢指针相遇（快指针二倍速，慢指针一倍速），这就证明了链表有环而且快慢指针都在环中，此时我们让慢指针单独走一圈，目的是知道环长，然后再让快慢指针都从头开始移动，但是将快指针的速度设置为和慢指针一样的速度也就是一倍速，然后快指针先走一个环长，当快慢指针相遇的时候，二者就指向了入口

  我们来详细讲一下思路，首先我们利用第一种快慢指针的原理以及搜索链表的倒数第k个节点这一版块的思想，假如设环入口节点为环结束节点，也就是假如一个指针走了n个节点之后进入环了，又走了一个环长我们将环长设为k，就相当于这个走了k+n的指针走到头了（入口节点），那么此时如果快指针先走了k个节点（一个环长），此时快慢指针同速移动，是不是快指针再走n个节点他就到了结束节点，而此时慢指针刚好走了n个节点到达入口节点，此时快慢指针相遇于入口节点，那么入口节点在哪里也就呼之欲出了，这下聪明的你应该理解了上述原理了吧

  附图如下：
  

  node* findcycleentry(node *head){
    node *fast=head;
    node *slow=head;
    while(fast!=null&&fast->next!=null){
      fast=fast->next->next;
      slow=slow->next;
      if(fast==slow){
        int count=1;
        while(slow!=fast){
          slow=slow->next;
          count++;
        }
        fast=head;
        slow=head;
        for(int i=0;i<count;i++){
          fast=fast->next;
        }
        while(fast!=slow){
          fast=fast->next;
          slow=slow->next;
        }
        return fast;
      }
    }
    return null;
  }

  以上为实现代码

• 双线链表寻找交点
  依旧第一类快慢指针，首先两个指针A,B从两个头同时同速开始移动，当其中一个移动到另外一个没到的时候（假设A到了B还没到），链表中没有相交的部分的长度差X就知道了，那么此时重置两个指针，让B先走X个单位，然后A,B同时移动，当A,B相遇时，二者就同时站在了交点上，如下图
  
  依旧上代码：

   node *findintersectionnode(node *head_a,node *head_b){
  if(head_a==null||head_b==null){
  	return null;
  }
  node *p=head_a;
  int len_a=0;
  int len_b=0;
  while(p!=null){
  	p=p->next;
  	len_a++;
  }
  p=len_b;
  while(p!=null){
  	p=p->next;
  	len_b++;
  }
  node *a;
  node *b;
  int step;
  if(len_a>len_b){
  	step=len_a-len_b;
  	a=head_a;
  	b=head_b;
  }
  else{
  	step=len_b-len_a;
  	a=head_b;
         		b=head_a;
  }
  for(int i=0;i<step;i++){
  	a=a->next;
  }
  while(a!=b){
  	a=a->next;
  	b=b->next;
  }
  return a;
   }

• 如何将一个单向链表倒叙这一问题用到了三个指针，过程就是首先第一个指针指向空，第二个指针指向第一个节点，然后让第三个指针指向第一个节点的后继，紧接着改变这个节点的next，往复循环，直到当前节点没有后继,最后设置头结点

  上了代码你就知道咋回事了

   node *reverselist(node *head){
  node *first=null;
  node *second=head->next;
  node *third;
  while(second!=null){
  	third=second->next;
     //可以把third当作一个记录员，记录原链表
  	second->next=first;
     //second和first一起蠕动构建出整个倒叙链表
  	first=second;
  	second=third;
  }
  node *hd=init();
  hd->next=first;
  return hd;
   }

  如果以上还是很懵的话推荐用纸和笔画一画图哦

链表的注意事项

有的时候链表的头节点可能并不是一个存数据的节点，仅仅只是提供给你真正的头节点的地址，请读者按情景分析

四.栈

结构原理

栈是一种先进后出的数据结构，可以看成下面的这种结构，如图

当你想要放书的时候，你只能把书放在最上面（栈顶），当你想要取书的时候，你也只能从最上面（栈顶）取书，这就是栈的原理，先进后出，就像你最先放上去的书最后才能取出来一样
所以创建一个栈十分的简单，仅仅只需要创建一个栈，和一个栈顶指针就可以了

typedef struct{
	elem data[IK];
	int top;
}stack;
//这里是在创建一个栈，但因为栈是线性表的一种，所以它的样子很像seplist，top指的是栈顶，会用做数组的下标

代码解释

增

• 创建栈

   void initstack(stack *p){
  p->top=-1;
   }

  上文我有说top是用来做下标的，但是栈顶指针要一直指在栈之上，所以top也可以用作栈顶指针，进来一个元素就加一，也就是第一个就是0，而我们判断栈是不是空的就看一眼top就行了
• 入栈

   void push(stack *p,elem e){
  p->top++;
  p->data[p->top]=e;
   }

  top加一，然后把元素放到top的位置

删

• 出栈

   elem pop(stack *p){
  elem e=p->data[p->top];
  p->top--;
  return e;
   }

  把top的元素赋值给e，然后top减一，就实现了出栈的操作，如果不明白为什么不把原来的数据置零的同学可以看看前文对线性表的讲解
• 清空栈

   void leave(stack *p){
  p->top=-1;
   }

  把top设为-1，就实现了清空栈的操作

改和查不讲解，因为这个数据结构的改和查没有任何意义

五.队列

结构原理

可以把队列看作两端开口的曼妥思，先进来的可以先出去，后进来的也可以先出去，只不过从左边最后进来的可以第一个从左边出去但是想从右边出去就要最后了，右边也是同样，就像排队买东西一样
而队列又分为四种，分别是

• 单进单出队列

  从一头进从另外一头出去

• 双进单出队列

  两头都可以进但只有一头可以出

• 单进双出队列

  两头都可以出但只有一头可以进

• 双进双出队列

  两头既可以进又可以出
  而为了方便理解，我们仅仅只讲单进单出队列的代码实现，毕竟他是最典型的队列，其他的队列有兴趣的朋友可以自行实现

typedef struct{
	elem data[IK];
	int front;
	int rear;
}queue;

比栈就多了个开头

代码解释

增

• 创建队列

   void initqueue(queue *p){
  p->front=0;
  p->rear=0;
   }

  和栈同理，front和rear都指向0，就实现了创建队列的操作，但有一点需要注意的是，队列的前指针不能落后于后指针，这句话看起里是一句废话，但你仔细想一下我们新建的这个队列，front和rear都指向0，所以队列是空的，而当front指向1的时候这个队列才是真正存下了一个元素，而这个元素到底是存在了front指向的位置还是rear指向的位置这就看每个程序员的习惯了。
• 入队

   void enqueue(queue *p,elemtype e){
  p->data[p->rear]=e;
  p->rear++;
   }

  把元素放到rear的位置，然后rear加一

删

• 出队

   elem dequeue(queue *p){
  elem e=p->data[p->front];
  p->front++;
  return e;
   }

  把front的元素赋值给e，然后front加一，就实现了出队的操作
• 清空队列

   void leave(queue *p){
  p->front=0;
  p->rear=0;
   }

  把front和rear都设为0，就实现了清空队列的操作，或者你也可以图省事

  void leave(queue *p){
    p->rear=p->front;
  }

  直接将二者重合

改和查不讲解，因为这个数据结构的改和查同样没有任何意义

这里讲解一下为什么没有任何意义，因为无论是栈还是队列都是一种用来优化时间复杂度的结构，你可以把他们看成一个优化器而非一个存储器，而对于一个优化器来说，我们只关注他的入和出就行了，不需要关注他的内部数据究竟是什么，如果你还是不理解为什么，那这边推荐去洛谷或者力扣中找几道栈和队列的题做一下就明白了

六.链表形态栈与队列

结构原理

• 链表形态栈

  栈的链表形态就是用链表来实现栈，而不是用数组来实现栈，因为数组的大小是固定的，而链表的大小是动态的，所以链表形态栈的优势在于可以动态地调整栈的大小

   typedef struct node{
  elem data;
  struct node *next;
   }node;
  
   typedef struct{
  node *top;
   }linkstack;

  由上可见我们构建了两个结构体，一个用来表示每一个栈节点，另外一个表示栈顶指针
• 链表形态队列

  队列的链表形态就是用链表来实现队列，而不是用数组来实现队列，因为数组的大小是固定的，而链表的大小是动态的，所以链表形态队列的优势在于可以动态地调整队列的大小

   typedef struct node{
  elem data;
  struct node *next;
   }node;
  
   typedef struct{
  node *front;
  node *rear;
   }linkqueue;

  依旧是两个结构体，一个用来表示每一个队列节点，另外一个表示队列的头指针和尾指针

接下来演示具体操作

代码解释

• 栈

  • 创建栈

    linkstack* initstack(){
     linkstack *p=(linkstack *)malloc(sizeof(linkstack));
      p->top=NULL;
      return p;
    }

    把栈顶指针设为NULL，就实现了创建栈的操作

  • 入栈

     void push(linkstack *p,elem e){
    node *s=(node *)malloc(sizeof(node));
    s->data=e;
    s->next=p->top;
    p->top=s;
     }

    申请一个新节点，把元素赋值给它，然后把它的next指向栈顶指针，最后把栈顶指针指向它，就实现了入栈的操作

    这里解释一下两个指针为什么要互相指向，如下图
    
    如图可见，当新的节点入栈时，它的next指向栈顶指针就相当于指向了栈最上面的那个节点，也就是说这个新的节点成为了链表的头节点，而此时栈顶指针指向这个节点完成栈增;

    而此时有的朋友就有疑惑了，为什么栈顶节点是链表的头节点，而不是尾节点，这个问题由接下来的出栈操作解释

  • 出栈

     elem pop(linkstack *p){
    elem e=p->top->data;
    node *s=p->top;
    p->top=p->top->next;
    free(s);
    return e;
     }

    如这一段代码

    p->top=p->top->next;

    栈顶指针需要在pop的时候向下移动一个位置才叫出栈，但如果你的栈顶节点为单向链表的尾节点，就会导致p->top->next为null，没办法找到下一个节点

• 队列
  • 创建队列

    void initQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
    }

  • 入队

    void enqueue(LinkedQueue* queue, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (isEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    }

    讲过栈之后这部分内容已经没什么好说的了，大家可以自行研究理解
  • 出队

    int dequeue(LinkedQueue* queue) {
    if (isEmpty(queue)) {
        printf("队列已空，无法出队！\n");
        return -1;
    }
    QueueNode* temp = queue->front;
    int value = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return value;
    }

七.树与二叉树

作者在这里声明一下，因为树和图部分更偏向于算法，比如哈夫曼树，红黑树，搜索二叉树，图搜索之类的，所以作者只讲解最基础的树的结构以及相关二叉树一些简单的算法应用，毕竟本文是在讲解数据结构而非算法，所以如果有对图论和树算法感兴趣的朋友欢迎移步到洛谷和力扣去动手实践探索

结构原理

首先在正式讲树之前先将抽象具象起来，假如你在你的桌面新建了一个文件夹，然后在文件夹之中又新建了好几个文件夹，再之后继续套娃如下示意图

恭喜你，你已经创建了一个类似于树的结构：每个文件夹就是一个节点，而每个节点可以有多个子节点，而每个子节点又可以有多个子节点，以此类推，就形成了树的结构

如果以上内容你理解了，那就说明你已经知道树是什么东西了，而我们在这篇文章中，主要讲解的是树的一种特殊结构————二叉树，也就是每一个节点最多只有两个子节点，而这两个子节点分别叫做左子节点和右子节点（左子树和右子树），接下来上代码

typedef struct TreeNode {
  int data;
  struct TreeNode *left;
  struct TreeNode *right;
} TreeNode;

可见，上诉结构体定义了一个数据域和两个指针域，数据域用来存储节点的数据，而指针域则用来指向左子节点和右子节点

代码解释

这里只讲解二叉树的初始化根节点以及查找操作，其余操作如插入新节点，修改节点以及删除节点全部建立在了查找操作中，简单来说，假如你先指定节点改，那首先你需要查找到这个节点然后再进行修改，而如果你想要删除一个节点，就要把不止这一个节点删掉，还要把以这个节点作为根节点的整棵树都删掉，就好像你删除了某个文件夹，这个文件夹中的所有文件和文件夹也会被删掉一样，但如果你说我只想删除这一个节点，他里面的东西并不想删掉，那就需要遍历这个文件夹，将他里面的东西拷贝到根文件夹里然后再删除这个文件夹，说到底还是在查找操作中增加了一些改进，同理增加节点也是如此，由此可见查找操作是重中之重

增

• 初始化

  TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
  }

查

• 前序遍历

  根-左-右

  前序遍历就是先访问根节点，然后递归地访问左子树，最后递归地访问右子树，如下图
  
  图画的有一点小问题，没有体现出递归的过程，但至少你应该理解了啥是前序遍历，那么我们上代码

  void preOrder(TreeNode* root) {
    if (root == NULL) return;
    // 先访问根节点
    printf("%d ", root->data);
    // 递归遍历左子树
    preOrder(root->left);
    // 递归遍历右子树
    preOrder(root->right);
  }

  由上可见，在函数中

  preOrder(root->left);

  这段代码会先递归地访问左子树，而

  preOrder(root->right);

  这段代码会在左子树全部递归访问完开始访问右子树
• 中序遍历

  左-根-右

  void inOrder(TreeNode* root) {
    if (root == NULL) return;
    // 递归遍历左子树
    inOrder(root->left);
    // 访问根节点
    printf("%d ", root->data);
    // 递归遍历右子树
    inOrder(root->right);
  }

• 后序遍历

  左-右-根

  void postOrder(TreeNode* root) {
    if (root == NULL) return;
    // 递归遍历左子树
    postOrder(root->left);
    // 递归遍历右子树
    postOrder(root->right);
    // 访问根节点
    printf("%d ", root->data);
  }

  因为已经解释了前序遍历，中序遍历和后序遍历就留给读者自己使用纸笔记录或者代码调试理解

八.我的室友说打航天不打绝密等于白打，那我觉得将二叉树不讲线索二叉树等于没讲

结构原理

所谓线索二叉树就是在二叉树的基础上，将空指针域指向中序遍历的前驱或后继节点，从而避免了递归遍历的过程，而这一过程被称为线索化附图如下：

可见每一个元素的左右指针基本都没有浪费，左指针指向他的前驱而右指针指向他的后继，这也就加快了下一次便利的速度

// 线索标志枚举类型
typedef enum { Link, Thread } PointerTag;

// 线索二叉树节点结构
typedef struct ThreadedNode {
    int data;
    struct ThreadedNode *lchild, *rchild;
    PointerTag ltag, rtag;
} ThreadedNode;
// 全局变量，用于记录前驱节点
ThreadedTree pre = NULL;

这里展示一下中序遍历线索查找的代码，如果当你仔细算了一下时间复杂度，你会发现时间复杂度为O(n)，而空间复杂度为O(1)，这说明线索二叉树的查找操作是非常高效的

void InThreading(ThreadedTree p) {
    if (p) {
        InThreading(p->lchild);  // 递归线索化左子树
        if (!p->lchild) {
            p->ltag = Thread;
            p->lchild = pre;
        }
        if (pre && !pre->rchild) {
            pre->rtag = Thread;
            pre->rchild = p;
        }
        pre = p;  // 更新前驱节点
        InThreading(p->rchild);  // 递归线索化右子树
    }
}

代码解释

这里仅仅提供中序遍历线索化代码，其他遍历线索化代码读者可以自己尝试实现

void InOrderThreading(ThreadedTree *Thrt, ThreadedTree T) {
    *Thrt = (ThreadedTree)malloc(sizeof(ThreadedNode));
    (*Thrt)->ltag = Link;
    (*Thrt)->rtag = Thread;
    (*Thrt)->rchild = *Thrt;// 全局变量，用于记录前驱节点
ThreadedTree pre = NULL;
// 中序线索化二叉树
void InThreading(ThreadedTree p) {
    if (p) {
        InThreading(p->lchild);  // 递归线索化左子树
        if (!p->lchild) {
            p->ltag = Thread;
            p->lchild = pre;
        }
        if (pre && !pre->rchild) {
            pre->rtag = Thread;
            pre->rchild = p;
        }
        pre = p;  // 更新前驱节点
        InThreading(p->rchild);  // 递归线索化右子树
    }
}
// 创建中序线索二叉树
    void InOrderThreading(ThreadedTree *Thrt, ThreadedTree T) {
    *Thrt = (ThreadedTree)malloc(sizeof(ThreadedNode));
    (*Thrt)->ltag = Link;
    (*Thrt)->rtag = Thread;
    (*Thrt)->rchild = *Thrt;
    if (!T) (*Thrt)->lchild = *Thrt;
    else {
        (*Thrt)->lchild = T;
        pre = *Thrt;
        InThreading(T);
        pre->rchild = *Thrt;
        pre->rtag = Thread;
        (*Thrt)->rchild = pre;
    }
}
    if (!T) (*Thrt)->lchild = *Thrt;
    else {
        (*Thrt)->lchild = T;
        pre = *Thrt;
        InThreading(T);
        pre->rchild = *Thrt;
        pre->rtag = Thread;
        (*Thrt)->rchild = pre;
    }
}

以上为所有基础数据结构，但其实说实话，所有的数据结构基本上就是在花式创建结构体，如果读者仅仅是为了应付期末考试或者感兴趣学一下，上述的所有内容基本够用，如果有考研或者深入学习算法和开发的朋友，建议在本篇文章的基础上，多多加大内容的深度，而且要有大量题目辅助，上述代码可能出现问题，还请大佬们指出，作者菜菜，佬们带带