嵌入式学习的第二十三天-数据结构-树+哈希表+内核链表

一、树（一对多）

1.树的定义

树：n（n>=0）个结点的有限集合。n = 0 ,空树。

2.在任意一个非空树中，

(1)，有且仅有一个特定的根结点

(2)，当n>1 时，其余结点可分为m个互不相交的有限集合T1,T2,T3.。。。。Tm，其中每一个

集合又是一个树，并且称谓子树。

3.度

结点拥有子树的个数称谓结点的度。度为0的结点称谓叶结点。度不为0，称谓分支结点。

树的度数是指，这棵树中，最大的结点的度数，称谓树的度数。

树的深度或高度，从根开始，根为第一层，根的孩子为第二层。

4.树的存储，顺序结构，链式结构。

二、二叉树 binary tree

1.定义

n个结点的有限集合，集合要么为空树，要么由一个根结点和两棵互不相交，分别称谓根结点的左

子树和右子树的二叉树组成。

相交：D-E  

2.特点

(1)，每个结点最多两个子树。

(2)，左子树和右子树是有顺序的，次序不能颠倒。

(3)，如果某个结点只有一个子树，也要区分左，右子树。

3.特殊的二叉树

(1)，斜树，所有的结点都只有左子树，左斜树，所有结点都只有右子树，右树。

(2)，满二叉树，所有的分支结点都存在左右子树，并且叶子都在同一层上。

(3)，完全二叉树，对于一颗有n个结点的二叉树按层序编号，如果编号i（1<=i<=n）的结点于同样

深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这可树为完全二叉树。

4.特性（选填）
(1)，在二叉树的第i层上最多有2^(i-1)个结点 i>=1

(2),深度为k的二叉树至多有2^k  -1 个结点 k>=1

(3）,任意一个二叉树T，如果其叶子结点的个数是n0,度数为2的结点数为n2， n0 = n2 +1;

(4),有n个结点的完全二叉树深度为(logn/log 2) +1;

        注：向下取整

5.树的遍历

（1）广度遍历：层序

（2）深度遍历

        前序，根左右，先访问根，然访问左，访问右。

        中序，左根右，先从根开始（不是先访问根），从左开始访问，在访问根，在访问右结点。

        后序，左右根，先从根开始（不是先访问根），先访问左，在访问右。在访问根。

三、树的链式存储的一般操作 

1.创建

void CreateTree(TreeNode **root)
{
    char c = data[ind++];
    if('#'==c)
    {
        *root=NULL;
        return;
    }
    else
    {
        *root = malloc(sizeof(TreeNode));
        if(NULL == *root)
        {
            fprintf(stderr, "CreateTree malloc error");
            return ;
        }
        (*root)->data=c;
        CreateTree(&(*root)->left);
        CreateTree(&(*root)->rigjt);
    }
}

2.前序

void PreOrderTraverse(TreeNode*root)
{
    if(NULL == root)
    {
        return;
    }
    printf("%c",root->data);
    PreOrderTraverse(root->left);
    PreOrderTraverse(root->rigjt);
}

3.中序

void InOrderTraverse(TreeNode*root)
{
    if(NULL == root)
    {
        return;
    }
    InOrderTraverse(root->left);
    printf("%c",root->data);
    InOrderTraverse(root->rigjt);
}

4.后序

void PostOrderTraverse(TreeNode*root)
{
    if(NULL == root)
    {
        return;
    }
    PostOrderTraverse(root->left);
    PostOrderTraverse(root->rigjt);
    printf("%c",root->data);
}

5.销毁

void DestoryTree(TreeNode *root)
{
    if(NULL == root)
    {
        return;
    }
    DestoryTree(root->left);
    DestoryTree(root->rigjt);
    free(root);
}

四、哈希表

1.创建

HSTable*CreateHsTable(int len)
{
    HSTable*hs = malloc(sizeof(HSTable));
    if(NULL == hs)
    {
        fprintf(stderr, "CreateHsTable malloc error");
        return NULL;
    }
    hs->head = malloc(sizeof(DATATYPE)*len);
    if(NULL == hs->head)
    {
        fprintf(stderr, "CreateHsTable malloc2 error");
        return NULL;
    }    
    hs->tlen =len;
    int i=0;
    for(i =0;i<len;i++)
    {
        hs->head[i]=-1;
    }
    return hs;
}

2.HSFun

int HSFun(HSTable*hs,DATATYPE*data)
{
    return *data % hs->tlen;
}

3.插入

int HSInsert(HSTable*hs,DATATYPE*data)
{
    int ind=HSFun(hs, data);
    while(hs->head[ind]!=-1)
    {
        printf("pos %d,num :%d\n",ind,*data);
        ind =(ind+1)%hs->tlen;
    }
    hs->head[ind]=*data;
    return 0;

}

4.查找

int HsSearch(HSTable*hs,DATATYPE*data)
{
    int ind=HSFun(hs, data);
    int old_ind=ind;
    while(hs->head[ind]!=*data)
    {
        ind =(ind+1)%hs->tlen;
        if(old_ind==ind)
        {
            return -1;
        }
    }
    return ind;
}

5.main.c

int main(int argc, char **argv)
{
    HSTable*hs=CreateHsTable(15);
    int array[]={12,67,56,16,25,37,22,29,15,47,48,34};
    int i = 0;
     for (i = 0; i < 12; i++)
    {
      HSInsert(hs, &array[i]);
    }

     int want_num = 37;
    int ret = HsSearch(hs, &want_num);
    if (-1 == ret)
    {
      printf("not find \n");
    }
    else
    {
      printf("find ,%d\n", hs->head[ret]);
    }

    return 0;
}

五、内核链表（双向链表）

 思想：将数据摘出来,没有耦合，需自己定义结构体，结构体内部包括节点和数据，可按照自己的

            需求设计

Linux第一宏：offset(地址偏移量) 和 contrainof（求地址）

相关操作：

1.klist.c

#include "./klist.h"

void klist_init(KLIST* head)
{
    head->prev = head;
    head->next = head;
}

void klist_add(KLIST* newnode,KLIST*prev,KLIST* next)
{
    newnode->next =next;
    newnode->prev = prev;
    prev->next = newnode;
    next->prev = newnode;


}

void klist_add_head(KLIST* head,KLIST* newnode)
{
    klist_add(newnode,head,head->next);
}
void klist_add_tail(KLIST* head,KLIST* newnode)
{

    klist_add(newnode,head->prev,head);
}

void klist_del(KLIST*prev,KLIST*next)
{
    prev->next = next;
    next->prev = prev;
}

2.klist.h

#ifndef __KLIST_H__
#define __KLIST_H__


typedef struct __klist
{
    struct __klist *next;
    struct __klist* prev;
}KLIST;

#define offset(type,mem) ((size_t)  &((type*)0)->mem)
/**
 * @brief ptr 结构体node的指针
            type 结构体 per 
 *       mem  node在结构中的变量名
 */
#define containerof(ptr,type,mem) ({ const typeof(((type*)0)->mem) * _mptr = (ptr);\
   (type*) ((char*)_mptr- offset(type,mem)); })

#define klist_for_entry(ptr,type,mem)  containerof(ptr,type,mem)
/**
 * @brief p , 指向结构体的指针
 *        n, 指向当前结构体的下一个指针
         head， 链表的头节点指针
         mem， node在结构体中变量的名字
 */
//for(p=klist_for_entry(&(head)->next,typeof(*p),mem),n=klist_for_entry((p)->mem.next,typeof(*p),mem);
#define klist_for_each(p,n,head,mem) \
for(p=klist_for_entry(head->next,typeof(*p),mem),n=klist_for_entry((p)->mem.next,typeof(*p),mem);\
&p->mem != (head); p=n,n=klist_for_entry((n)->mem.next,typeof(*n),mem))

// #define offset(type,mem) ((size_t) &((type*)0)->mem)
// #define containerof(p,type,mem) ({\
// const typeof(  ((type*)0)->mem ) * _mptr = (p);\
// (type*)((char*)_mptr - offset(type,mem));})
// #define klist_entry(p,type,mem) containerof(p,type,mem)

// #define klist_for_each(p,n,head,node)\
// for(p=klist_entry((head)->next,typeof(*p),node),\
//     n=klist_entry(p->node.next,typeof(*p),node);        \
//     &p->node != (head);p=n,n=klist_entry(n->node.next,typeof(*n),node))

void klist_init(KLIST* head);
void klist_add_head(KLIST* head,KLIST* newnode);
void klist_add_tail(KLIST* head,KLIST* newnode);
void klist_del(KLIST*prev,KLIST*next);

#endif 

3.per.c

#include "./per.h"
#include "klist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int add_per(int id,char *name,KLIST* head)
{
    PER* per = malloc(sizeof(PER));
    if(NULL == per)
    {
        perror("add_per malloc\n");
        return 1;
    }
    strcpy(per->name,name);
    per->id = id;
    klist_add_tail(head,&per->node);
    return 0;
}

int show_per(KLIST* head)
{
    PER *p ,*n;
   klist_for_each(p,n,head,node)
   {
    printf("%d %s\n",p->id,p->name);
   }
    return 0;
}

int del_per(KLIST* head,int id)
{
     PER *p ,*n;
   klist_for_each(p,n,head,node)
   {
    //printf("%d %s\n",p->id,p->name);
    if(p->id == id)
    {
        klist_del(p->node.prev, p->node.next);
        free(p);
    }
   }

   return 0;

}

4.per.h

#ifndef __PER_H__
#define __PER_H__
#include "./klist.h"
typedef struct 
{
    int id;
    char name[40];
    KLIST node;
} PER;


int add_per(int id,char *name,KLIST* head);
int show_per(KLIST* head);
int del_per(KLIST* head,int id);
#endif