各种存储结构结构体.doc

数据结构-结构体的声明 一般来说，知道了各种存储结构的结构体，或者各种算法(其实算法是在各种特定的存储结构下实现)所需的结构体，所以我觉得记住或者牢记各种场合，各种情形下所需要的存储结构的结构体，对算法的创建和表达就会轻松和容易许多。一、顺序存储 1、 顺序表#define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;2、栈（顺序栈）#define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int top; sequence_stack;3、队列（顺序队列，顺序循环队列）#define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int front;int rear; sequence_queue;其中循环队列判满条件：(rear+1)%MAXSIZE=front；判空条件：rear=front二、链式存储 1、 单链表（带头结点的单链表，循环单链表） typedef int datatype; typedef struct link_node datatype info; struct link_node *next; node;2、双链表 typedef int datatype; typedef struct dlink_node datatype info; struct link_node *llink,*rlink; dnode;3、链式栈 typedef int datatype; typedef struct link_node datatype info; struct link_node *next; node; node *top;4、链式队列 typedef int datatype; typedef struct link_node datatype info; struct link_node *next; node; typedef struct node *front,*rear; queue;三、字符串 1、顺序串：模式匹配（朴素的模式匹配算法，KMP算法）#define MAXSIZE 100 typedef structchar strMAXSIZE; int length; seqstring; 2、链式串 typedef struct node char data; struct node *next; linkstrnode; typedef linkstrnode *linkstring; 3、N维数组：行优先存储，列优先存储 (三维数组) typedef int datatype; typdef struct datatype *base;/数组存储区的首地址指针 int index3;/存放三维数组各维的长度 int c3; /存放三维数组各维的ci值array;四、树1、双亲表示法#define MAXSIZE 100 typedefchar datatype;/节点值的类型 typedef struct node/结点类型 datatype data; int parent;/结点双亲的下标 node; typedef struct tree node treelistMAXSIZE;/存放结点的数组 int length,root;/树中实际所含结点的个数，根节点的位置tree;/树的类型2、孩子表示法（指针方式）#define m 3/树的度数 typedefchar datatype;/节点值的类型 typedef struct node datatype data; struct node *childm;/指向子女的指针数组 node,*tree; tree *node;3、孩子表示法（数组方式）#define m 3/树的度数 #define MAXSIZE 20/存放树结点的数组大小 typedefchar datatype;/结点值的类型 typedef struct node/结点类型 datatype data; int childm; treenode; treenode treeMAXSIZE;/存储树结点的数组 int root;/根节点的下标 int length;/树中实际所含结点的个数4、孩子表示法（链式方式） #define MAXSIZE 50 typedefchar datatype;/结点值的类型 typedef struct chnode/孩子结点的类型 int child; struct chnode *next; chnode,*chpoint; typedef struct/树中每个结点的类型 datatype data;chpoint firstchild;/指向第一个子女结点的指针 node; typedef struct/树的类型 node treelistMAXSIZE; int length,root;/树中实际所含结点的个数，根结点的位置tree;5、孩子兄弟表示法 typedefchar datatype;/结点值的类型 typedef struct node/孩子结点的类型 datatype data; struct node *firstchild,*rightsibling; node,*pnode; pnode root;6、树的括号表示7、树的层号表示五、二叉树1、完全二叉树 #define MAXSIZE 20 typedefchar datatype;/结点值的类型 datatype treeMAXSIZE; int n;/树中实际所含结点的个数2、一般二叉树（顺序存储） #define MAXSIZE 20 typedefchar datatype;/结点值的类型 typedef struct datatype data; int lchild,rchild;/存放左，右子女的下标 int parent;/存放双亲结点的下标（当需要带双亲指示时声明） node; node treeMAXSIZE;int n;/树中实际所含结点的个数int root;/存放根结点的下标3、链式存储 typedefchar datatype;/结点值的类型 typedef struct node datatype data;struct node*lchild,*rchild;/存放左，右子女的下标 int *parent;/指向双亲结点的指针（当需要带双亲指示时声明） bintnode; typedef bintnode *bintree; bintree root;/指向二叉树根节点的指针六、图1、邻接矩阵类型定义 #define FINITY 5000/用5000表示无穷大 #define M 20/最大顶点数 typedefchar vertextype;/顶点值的类型 typedef int edgetype;/权值类型 typedef struct vertextype vexM;/顶点信息域 edgetype degesMM;/邻接矩阵 int n,e;/图中顶点总数，边数 Mgraph;2、邻接表类型定义 #define M 20/最大顶点数 typedefchar datatype;/顶点信息数据类型 typedef struct node/边表结点 int adjvex;/邻接点 struct node *next; edgenode; typedef struct vnode/头结点类型 datatype vertex;/顶点信息 edgenode *firstedge;/邻接链表 头指针 vertexnode; typedef struct/邻接表类型 vertexnode adjlistM;/存放头结点的顺序表 int n,e;/顶点数，边数 linkedgraph;七、检索1、顺序检索，二分法检索(存储有序)#define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int len; sequence;2、分块检索#define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int len; sequence; typedef struct datatype key;/块中最大值 int address;/分界点 indexnode;3、二叉排序树 typedefint datatype;/结点值的类型 typedef struct node datatype data;struct node*lchild,*rchild; bsnode; typedef bsnode *bstree;4、Huffman树 typedef struct node int data;/权值struct node*lchild,*rchild,*next; hufnode; typedef hufnode