铜仁市论坛

首页 » 分类 » 分类 » 嵌入式数据结构04day
TUhjnbcbe - 2021/4/28 21:07:00

一、队列。

1、什么是队列?

在一条储存的结构中,插入节点与删除节点分别在两端进行的,例如:插入数据在队尾处理、删除数据在队头处理,那么这种逻辑就叫做队列。

其特点是先进先出、后进后出。

插入数据-入队。

删除数据-出队。

2、设计队列结构体。

1)设计队列节点结构体。

structnode{

  intdata;

  structnode*next;

};

2)设计管理队列的结构体。

structqueue{

  structnode*head;//指向队头节点的指针

  structnode*tail;//指向队尾节点的指针

  intsize;

}

二、实现队列的出队与入队的步骤。

#includestdio.h

#includestdlib.h

structnode{

  intdata;

  structnode*next;

};

structqueue{

  structnode*head;//指向队头-出队

  structnode*tail;//指向队尾-入队

  intsize;//统计当前队列中的节点个数

};

structqueue*init_queue()

{

  //1.为管理结构体申请空间。

  structqueue*q=malloc(sizeof(structqueue));

  if(q==NULL)

    printf("mallocqueueerror!\n");

  //2.为结构体赋值。

  q-head=NULL;

  q-tail=NULL;

  q-size=0;

  returnq;

}

intin_queue(structqueue*q,intnum)

{

  //1.为新节点申请空间。

  structnode*new=malloc(sizeof(structnode));

  if(new==NULL)

    printf("mallocerror!\n");

  //2.为新节点赋值。

  new-data=num;

  new-next=NULL;

  //3.将节点插入到队列中。

  if(q-size==0)//如果插入的节点是第一个节点,则需要特殊处理。

  {

    //如果队列只有你一个人,那么队头队尾都是你

    q-head=new;

    q-tail=new;

  }

  else{

    q-tail-next=new;//原来的那个队尾的指针域指向这个新节点。

    q-tail=new;//队尾就指向新节点。

  }

  q-size++;

  return0;

}

intshow_queue(structqueue*q)

{

  //1.先判断是不是空队。

  if(q-size==0)

    return-1;

  //2.遍历队列。

  structnode*tmp=NULL;

  for(tmp=q-head;tmp!=NULL;tmp=tmp-next)

  {

    printf("%d-",tmp-data);

  }

  printf("\n");

  return0;

}

intout_queue(structqueue*q,int*p)

{

  //1.出队之前先判断一下队列是否为空。

  if(q-size==0)

    return-1;

  //2.不为空,正常出队。

  structnode*tmp=q-head;//这个tmp就是等会需要出队的那个人。

  //3.分情况讨论。

  if(q-size==1)//整个队列中就剩一个节点

  {

    q-head=NULL;

    q-tail=NULL;

  }

  else{

    q-head=q-head-next;

  }

  *p=tmp-data;//其实就是给a赋值。

  //4.释放出队的节点的空间。

  free(tmp);

  q-size--;

  return0;

}

intdestroy_queue(structqueue*q)

{

  free(q);

}

intmain(intargc,char*argv[])

{

  //1.初始化一条空队。

  structqueue*q=NULL;

  q=init_queue();

  //2.入队

  in_queue(q,10);

  in_queue(q,20);

  in_queue(q,30);

  in_queue(q,40);

  //3.遍历队列。

  show_queue(q);

  //4.出队。

  inta;

  while(q-size!=0)

  {

    out_queue(q,a);

    printf("a=%d\n",a);

  }

  //5.销毁

  destroy_queue(q);  

  return0;

}

练习:写一个程序,处于一个不断输入整数状态。

  如果输入是正整数,则将该整数入队。---客户取号。

  如果输入是一个负数,则输出队列中头节点的值。---柜台工作人员按下按键、排在最开头的那个人就可以办理业务。

  如果输入是一个0,则结束程序。---今天收工。

三、二叉树。

1、为什么要学习二叉树?

前面我们都已经学习过链表了,大家都知道,如果我们需要检索出一个数据出来,有可能检索一次,就可以找到数据,有可能检索到最后一个节点才能找到节点,这就是链表的特点,也就是说,寻找一条长度为N个节点的链表,搜索次数处于1~N-1(头节点无效),二叉树的出现,就是为了减少检索数据时的次数。

2、什么是二叉树?

二叉树也是一种储存结构,也就是说跟链表一样,都是来储存数据的,但是链表是线性规则的结构,而二叉树是非线性的储存结构。二叉树有一个根节点作为起始点,这个根节点也是可以存放数据的。二叉树结构就是把小于根节点的数据储存到根节点的左边,把大于根节点的数据储存到根节点的右边。这样就实现了检索时,不需要更加多次数。

例如:根是20,根左边是18,根的右边是23,当我们寻找一个节点数据为23时,就不需要考虑去根的左边寻找,只需要考虑去根的右边寻找即可。二叉树,就是为了提高效率。

3、介绍二叉树基本概念。

1)双亲与孩子A就是B与C的双亲,B与C就是A的孩子。

2)兄弟:拥有共同双亲的两个节点称之为兄弟J与K就是兄弟,D与E就是兄弟。

3)度:形容一个节点孩子的个数A的度是2D的度是0L的度是1

4)层:A的层是1B/C的层是2

4、二叉树的种类。

1)只有根节点的二叉树

跟是一棵树的基本,哪怕是只有一个根节点,也可以形成一棵树。

2)普通二叉树。

树上面任意的一个节点的度都是小于或者等于2(任意一个节点小孩不得超过2个,可以0个,可以1个,可以2个,但是不可以3个或者以上)

3)满二叉树。

树上面任意的一个节点的度都是等于2,也就是说,假设一棵树有N层,其树的节点达到了2的N次方-1个,那么这颗树就是满二叉树。

4)非二叉树。

只要树上面有任意一个点其度超过2,那么这棵树就是非二叉树。

四、二叉树的增删改查?

1、设计节点。

通过分析,任意一个节点的度都是小于等于2,所以节点模型:

structnode{

  intdata;

  structnode*lchild;

  structnode*rchild;

};

2、初始化一棵二叉树的根节点。

structnode*init_new_node(intnum)

{

  //1.为节点申请空间。

  structnode*root=malloc(sizeof(structnode));

  if(root==NULL)

    printf("mallocerror!\n");

  //2.为节点赋值。

  root-data=num;  

  root-lchild=NULL;

  root-rchild=NULL;

  returnroot;

}

3、插入节点到二叉树中。

structnode*insert_node(structnode*new,structnode*root)

{

  //1.先判断树的根节点存不存在,如果不存在,则插入的数据就作为根节点。

  if(root==NULL)

  {

    returnnew;//那么新节点就作为根节点。

  }

  //2.如果树有根节点,则正常插入节点。

  if(new-dataroot-data)//该节点应该放在根节点的右边。

  {

    root-rchild=insert_node(new,root-rchild);

  }

  elseif(new-dataroot-data)//该节点应该放在根节点的左边。

  {

    root-lchild=insert_node(new,root-lchild);

  }

  else{

    printf("%dnodealreadyexists!\n",new-data);

  }

  returnroot;

}

4、搜索二叉树中的节点。

structnode*find_node(structnode*root,intnum)

{  

  if(root==NULL)//找到底都没有找到你啊

  {

    returnNULL;

  }

  if(numroot-data)//如果这个数字比root数字要小,则去root的左边寻找。

  {

    returnfind_node(root-lchild,num);

  }

  elseif(numroot-data)//如果这个数字比root数字要大,则去root的右边寻找。

  {

    returnfind_node(root-rchild,num);

  }

  else{//如果这个num与root-data一样,则这个root就是我想找的东西。

    returnroot;

  }

}

5、遍历二叉树。

1)先序遍历。

顺序:根-左-右

voidshow_node_first(structnode*root)

{

  if(root==NULL)

    return;

  printf("%d\n",root-data);//根

  show_node_first(root-lchild);//左

  show_node_first(root-rchild);//右

  return;

}

2)中序遍历。

顺序:左-根-右

voidshow_node_middle(structnode*root)

{

  if(root==NULL)

    return;

  show_node_middle(root-lchild);//左

  printf("%d\n",root-data);//根

  show_node_middle(root-rchild);//右

  return;

}

3)后序遍历。

顺序:左-右-根

voidshow_node_last(structnode*root)

{

  if(root==NULL)

    return;

  show_node_last(root-lchild);//左

  show_node_last(root-rchild);//右

  printf("%d\n",root-data);//根

  return;

}

4)按层遍历。

步骤如下:

1.初始化一条空的队列。

2.将根节点入队。

3.出队,如果出队失败,则结束程序,如果成功,则打印该节点。

4.找到出队的那个节点。

5.判断刚刚出队的那个节点有没有左孩子,如果有则将左孩子入队。

6.判断刚刚出队的那个节点有没有右孩子,如果有则将右孩子入队。

7.重复第3步。

intshow_node_level(structnode*root)

{

  if(root==NULL)

    return-1;

  //1.初始化一条空队列。

  structqueue*q=NULL;

  q=init_queue();

  //2.将根节点入队。

  in_queue(q,root-data);

  //3.出队,如果出队失败,则结束程序,如果成功,则打印该节点。

  inta;

  structnode*tmp=NULL;

  while(1)

  {

    if(out_queue(q,a)==-1)//出队失败

      break;

    printf("%d\n",a);

    //4.找到出队的那个节点。

    tmp=find_node(root,a);

    //5.判断刚刚出队的那个节点有没有左孩子,如果有则将左孩子入队。

    if(tmp-lchild!=NULL)//不为NULL,则说明有左孩子。

      in_queue(q,tmp-lchild-data);

    //6.判断刚刚出队的那个节点有没有右孩子,如果有则将右孩子入队。

    if(tmp-rchild!=NULL)//不为NULL,则说明有右孩子。

      in_queue(q,tmp-rchild-data);

  }

  free(q);

  return0;

}

6、删除节点。

1)如果需要删除的节点有左子树(不管有没有右子树),其方法是将左子树中最大值替换掉该节点。

第一步:通过递归寻找到需要删除的节点。

第二步:找到删除的那个节点的左子树的最大值。

第三步:将这个最大值替换需要删除的节点。

第四步:通过调用删除函数,递归地去删除这个最大值。(不能直接删除,需要递归删除,因为这个节点虽然肯定没有右子树(因为如果有右,该节点就不是最大),但是有可能有左子树。)

2)如果需要删除的节点只有右子树,其方法就把右子树中最小值替换该节点。

第一步:通过递归寻找到需要删除的节点。

第二步:找到删除的那个节点的右子树的最小值。

第三步:将这个最小值替换需要删除的节点。

第四步:通过调用删除函数,递归地去删除这个最小值。(不能直接删除,需要递归删除,因为这个节点虽然肯定没有左子树(因为如果有左,该节点就不是最小),但是有可能有右子树。)

3)如果需要删除的节点的度为0,则直接删除。

第一步:通过递归寻找到需要删除的节点。

第二步:直接调用free()释放该节点的空间。

structnode*delete_node(structnode*root,intnum)

{

  //1.找到底都没有找到该节点,直接返回NULL。

  if(root==NULL)

    returnNULL;

  //2.寻找需要删除的节点。

  if(numroot-data)//应该去左边找

  {

    root-lchild=delete_node(root-lchild,num);

  }

  elseif(numroot-data)

  {

    root-rchild=delete_node(root-rchild,num);

  }

  else{//找到你想删除的节点了,这个节点就是root

    //3.判断需要删除的节点有没有左子树

    structnode*tmp=NULL;  

    if(root-lchild!=NULL)//不为NULL,说明有左子树

    {

      //4.寻找该节点左子树中的最大值。

      for(tmp=root-lchild;tmp-rchild!=NULL;tmp=tmp-rchild);

      //从循环中出来时,tmp就是左子树中的最大值。

      

      //5.将tmp指向数据赋值给需要删除的节点的数据域,

      root-data=tmp-data;

      //6.递归删除这个tmp

      root-lchild=delete_node(root-lchild,tmp-data);

    }

    elseif(root-rchild!=NULL)//不为NULL,说明有右子树

    {

      //4.寻找该节点右子树中的最小值。

      for(tmp=root-rchild;tmp-lchild!=NULL;tmp=tmp-lchild);

      //从循环中出来时,tmp就是右子树中的最小值。

      

      //5.将tmp指向数据赋值给需要删除的节点的数据域,

      root-data=tmp-data;

      //6.递归删除这个tmp

      root-rchild=delete_node(root-rchild,tmp-data);

    }

    else{

      free(root);

      returnNULL;//最后的节点释放了,需要返回一个NULL,给指向这个最后的节点的左/右指针。

    }

  }

  returnroot;

}

=============================================

例程1:

#includestdio.h

#includestdlib.h

//二叉树的节点

structnode{

  intdata;

  structnode*lchild;

  structnode*rchild;

};

//队列的节点

structq_node{

  intdata;

  structq_node*next;

};

//管理队列的结构体

structqueue{

  structq_node*head;//指向队头-出队

  structq_node*tail;//指向队尾-入队

  intsize;//统计当前队列中的节点个数

};

structqueue*init_queue()

{

  //1.为管理结构体申请空间。

  structqueue*q=malloc(sizeof(structqueue));

  if(q==NULL)

    printf("mallocqueueerror!\n");

  //2.为结构体赋值。

  q-head=NULL;

  q-tail=NULL;

  q-size=0;

  returnq;

}

intin_queue(structqueue*q,intnum)

{

  //1.为新节点申请空间。

  structq_node*new=malloc(sizeof(structq_node));

  if(new==NULL)

    printf("mallocerror!\n");

  //2.为新节点赋值。

  new-data=num;

  new-next=NULL;

  //3.将节点插入到队列中。

  if(q-size==0)//如果插入的节点是第一个节点,则需要特殊处理。

  {

    //如果队列只有你一个人,那么队头队尾都是你

    q-head=new;

    q-tail=new;

  }

  else{

    q-tail-next=new;//原来的那个队尾的指针域指向这个新节点。

    q-tail=new;//队尾就指向新节点。

  }

  q-size++;

  return0;

}

intout_queue(structqueue*q,int*p)

{

  //1.出队之前先判断一下队列是否为空。

  if(q-size==0)

    return-1;

  //2.不为空,正常出队。

  structq_node*tmp=q-head;//这个tmp就是等会需要出队的那个人。

  //3.分情况讨论。

  if(q-size==1)//整个队列中就剩一个节点

  {

    q-head=NULL;

    q-tail=NULL;

  }

  else{

    q-head=q-head-next;

  }

  *p=tmp-data;//其实就是给a赋值。

  //4.释放出队的节点的空间。

  free(tmp);

  q-size--;

  return0;

}

structnode*init_new_node(intnum)

{

  //1.为节点申请空间。

  structnode*root=malloc(sizeof(structnode));

  if(root==NULL)

    printf("mallocerror!\n");

  //2.为节点赋值。

  root-data=num;  

  root-lchild=NULL;

  root-rchild=NULL;

  returnroot;

}

structnode*insert_node(structnode*new,structnode*root)

{

  //1.先判断树的根节点存不存在,如果不存在,则插入的数据就作为根节点。

  if(root==NULL)

  {

    returnnew;//那么新节点就作为根节点。

  }

  //2.如果树有根节点,则正常插入节点。

  if(new-dataroot-data)//该节点应该放在根节点的右边。

  {

    root-rchild=insert_node(new,root-rchild);

  }

  elseif(new-dataroot-data)//该节点应该放在根节点的左边。

  {

    root-lchild=insert_node(new,root-lchild);

  }

  else{

    printf("%dnodealreadyexists!\n",new-data);

  }

  returnroot;

}

structnode*find_node(structnode*root,intnum)

{  

  if(root==NULL)//找到底都没有找到你啊

  {

    returnNULL;

  }

  if(numroot-data)//如果这个数字比root数字要小,则去root的左边寻找。

  {

    returnfind_node(root-lchild,num);

  }

  elseif(numroot-data)//如果这个数字比root数字要大,则去root的右边寻找。

  {

    returnfind_node(root-rchild,num);

  }

  else{//如果这个num与root-data一样,则这个root就是我想找的东西。

    returnroot;

  }

}

voidshow_node_first(structnode*root)

{

  if(root==NULL)

    return;

  printf("%d\n",root-data);//根

  show_node_first(root-lchild);//左

  show_node_first(root-rchild);//右

  return;

}

voidshow_node_middle(structnode*root)

{

  if(root==NULL)

    return;

  show_node_middle(root-lchild);//左

  printf("%d\n",root-data);//根

  show_node_middle(root-rchild);//右

  return;

}

voidshow_node_last(structnode*root)

{

  if(root==NULL)

    return;

  show_node_last(root-lchild);//左

  show_node_last(root-rchild);//右

  printf("%d\n",root-data);//根

  return;

}

intshow_node_level(structnode*root)

{

  if(root==NULL)

    return-1;

  //1.初始化一条空队列。

  structqueue*q=NULL;

  q=init_queue();

  //2.将根节点入队。

  in_queue(q,root-data);

  //3.出队,如果出队失败,则结束程序,如果成功,则打印该节点。

  inta;

  structnode*tmp=NULL;

  while(1)

  {

    if(out_queue(q,a)==-1)//出队失败

      break;

    printf("%d\n",a);

    //4.找到出队的那个节点。

    tmp=find_node(root,a);

    //5.判断刚刚出队的那个节点有没有左孩子,如果有则将左孩子入队。

    if(tmp-lchild!=NULL)//不为NULL,则说明有左孩子。

      in_queue(q,tmp-lchild-data);

    //6.判断刚刚出队的那个节点有没有右孩子,如果有则将右孩子入队。

    if(tmp-rchild!=NULL)//不为NULL,则说明有右孩子。

      in_queue(q,tmp-rchild-data);

  }

  free(q);

  return0;

}

structnode*delete_node(structnode*root,intnum)

{

  //1.找到底都没有找到该节点,直接返回NULL。

  if(root==NULL)

    returnNULL;

  //2.寻找需要删除的节点。

  if(numroot-data)//应该去左边找

  {

    root-lchild=delete_node(root-lchild,num);

  }

  elseif(numroot-data)

  {

    root-rchild=delete_node(root-rchild,num);

  }

  else{//找到你想删除的节点了,这个节点就是root

    //3.判断需要删除的节点有没有左子树

    structnode*tmp=NULL;  

    if(root-lchild!=NULL)//不为NULL,说明有左子树

    {

      //4.寻找该节点左子树中的最大值。

      for(tmp=root-lchild;tmp-rchild!=NULL;tmp=tmp-rchild);

      //从循环中出来时,tmp就是左子树中的最大值。

      

      //5.将tmp指向数据赋值给需要删除的节点的数据域,

      root-data=tmp-data;

      //6.递归删除这个tmp

      root-lchild=delete_node(root-lchild,tmp-data);

    }

    elseif(root-rchild!=NULL)//不为NULL,说明有右子树

    {

      //4.寻找该节点右子树中的最小值。

      for(tmp=root-rchild;tmp-lchild!=NULL;tmp=tmp-lchild);

      //从循环中出来时,tmp就是右子树中的最小值。

      

      //5.将tmp指向数据赋值给需要删除的节点的数据域,

      root-data=tmp-data;

      //6.递归删除这个tmp

      root-rchild=delete_node(root-rchild,tmp-data);

    }

    else{

      free(root);

      returnNULL;//最后的节点释放了,需要返回一个NULL,给指向这个最后的节点的左/右指针。

    }

  }

  returnroot;

}

intmain(intargc,char*argv[])

{

  //1.初始化二叉树的根节点。

  structnode*root=NULL;

  root=init_new_node(20);

  //2.插入节点

  structnode*new=NULL;

  new=init_new_node(35);

  insert_node(new,root);

  new=init_new_node(25);

  insert_node(new,root);

  new=init_new_node(40);

  insert_node(new,root);

  new=init_new_node(33);

  insert_node(new,root);

  new=init_new_node(30);

  insert_node(new,root);

  new=init_new_node(34);

  insert_node(new,root);

  new=init_new_node(29);

  insert_node(new,root);

  new=init_new_node(31);

  insert_node(new,root);

  new=init_new_node(32);

  insert_node(new,root);

  //3.搜索节点。

  structnode*tmp=NULL;

  tmp=find_node(root,15);

  if(tmp!=NULL)

  {

    printf("tmp-data:%d\n",tmp-data);

  }

  //4.先序遍历二叉树。

  //show_node_first(root);

  

  //5.中序遍历二叉树。

  //show_node_middle(root);

  

  //6.后序遍历二叉树。

  //show_node_last(root);

  //7.按层遍历。

  show_node_level(root);

  printf("===============\n");

  delete_node(root,33);

  show_node_level(root);

  return0;

}

=============================================

例程2:

#includestdio.h

#includestdlib.h

structnode{

  intdata;

  structnode*next;

};

structqueue{

  structnode*head;//指向队头-出队

  structnode*tail;//指向队尾-入队

  intsize;//统计当前队列中的节点个数

};

structqueue*init_queue()

{

  //1.为管理结构体申请空间。

  structqueue*q=malloc(sizeof(structqueue));

  if(q==NULL)

    printf("mallocqueueerror!\n");

  //2.为结构体赋值。

  q-head=NULL;

  q-tail=NULL;

  q-size=0;

  returnq;

}

intin_queue(structqueue*q,intnum)

{

  //1.为新节点申请空间。

  structnode*new=malloc(sizeof(structnode));

  if(new==NULL)

    printf("mallocerror!\n");

  //2.为新节点赋值。

  new-data=num;

  new-next=NULL;

  //3.将节点插入到队列中。

  if(q-size==0)//如果插入的节点是第一个节点,则需要特殊处理。

  {

    //如果队列只有你一个人,那么队头队尾都是你

    q-head=new;

    q-tail=new;

  }

  else{

    q-tail-next=new;//原来的那个队尾的指针域指向这个新节点。

    q-tail=new;//队尾就指向新节点。

  }

  q-size++;

  return0;

}

intshow_queue(structqueue*q)

{

  //1.先判断是不是空队。

  if(q-size==0)

    return-1;

  //2.遍历队列。

  structnode*tmp=NULL;

  for(tmp=q-head;tmp!=NULL;tmp=tmp-next)

  {

    printf("%d-",tmp-data);

  }

  printf("\n");

  return0;

}

intout_queue(structqueue*q,int*p)

{

  //1.出队之前先判断一下队列是否为空。

  if(q-size==0)

    return-1;

  //2.不为空,正常出队。

  structnode*tmp=q-head;//这个tmp就是等会需要出队的那个人。

  //3.分情况讨论。

  if(q-size==1)//整个队列中就剩一个节点

  {

    q-head=NULL;

    q-tail=NULL;

  }

  else{

    q-head=q-head-next;

  }

  *p=tmp-data;//其实就是给a赋值。

  //4.释放出队的节点的空间。

  free(tmp);

  q-size--;

  return0;

}

intdestroy_queue(structqueue*q)

{

  free(q);

}

intmain(intargc,char*argv[])

{

  //1.初始化一条空队。

  structqueue*q=NULL;

  q=init_queue();

  //2.入队

  in_queue(q,10);

  in_queue(q,20);

  in_queue(q,30);

  in_queue(q,40);

  //3.遍历队列。

  show_queue(q);

  //4.出队。

  inta;

  while(q-size!=0)

  {

    out_queue(q,a);

    printf("a=%d\n",a);

  }

  //5.销毁

  destroy_queue(q);  

  return0;

}

善解人意是特么什么东西?委屈我自己让你开心吗?

该用户名已注册

你我轻松一赞,金钱或多或少。

1
查看完整版本: 嵌入式数据结构04day