一、树(一对多)
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