读《数据结构》 5-6章[数组和广义表和树]
2016.06.30 – 07.12 5 数组和广义表07.04 5.1 数组(1) 数组的定义数组抽象数据类型数组定义 L为每个数组元素所占存储单元个数。 (数组一般不进行插入、删除元素操作 —— 复杂度) n维数组类型为其 数据元素为n – 1维数组类型 的一维数组类型(的定义) (2) 数组的顺序表示和实现/* sequence_array.c * 数组的顺序表示描述和简单实现 * 2016.07.05 */
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX_ARRAY_DIM 8 // 规定数组维数最大值
#define OK 0 // 函数正常返回状态
#define NK 1 // 函数非正常返回
typedef char ElemType; // 数组元素类型
/* 描述数组的结构体 */
typedef struct {
ElemType *base; // 数组元素基址
int dim; // 数组维数
int *bounds; // 数组各维界基址
int *constants; // 数组映像函数常量基址
}Array;
/* 数组基本操作 */
// 构造相应合法的维数和各维度的数组
int init_array(Array *pa,int dim,...)
{
int i;
va_list ap;
unsigned elemtotal; // 类型由动态分配最大量决定
if (dim < 1 || dim > MAX_ARRAY_DIM) return NK;
pa->dim = dim;
pa->bounds = (int *)malloc(dim * sizeof(int)); // 保存各维长度的首地址
if (!pa->bounds) exit(NK);
// 求数组内存空间总大小
elemtotal = 1;
va_start(ap,dim);
for (i = 0; i < dim; ++i) {
pa->bounds[i] = va_arg(ap,int);
if (pa->bounds[i] < 0) exit(NK); // man va_arg()发生错误没说是小于0的错误
elemtotal *= pa->bounds[i]; // n维数组元素个数计算
}
va_end(ap);
pa->base = (ElemType *)malloc(elemtotal * sizeof(elemtotal));
if (!pa->base) exit(NK);
// 数组映像函数计算
pa->constants = (int *)malloc(dim * sizeof(int));
if (!pa->constants) exit(NK);
pa->constants[dim - 1] = 1; // 只以数组最右一列变化的数组元素直接数
for (i = dim - 2; i >= 0; --i)
pa->constants[i] = pa->bounds[i + 1] * pa->constants[i + 1];
return OK;
}
// 销毁数组
void destroy_array(Array *pa)
{
if (!pa) return ;
if (pa->base) {
free(pa->base);
pa->base = NULL;
}
if (pa->bounds) {
free(pa->bounds);
pa->bounds = NULL;
}
if (pa->constants) {
free(pa->constants);
pa->constants = NULL;
}
}
// 给数组指定元素赋值
int assign_array_value(Array *pa,ElemType e,...)
{
int i;
int arg;
va_list ap;
unsigned off;
if (!pa) return NK;
off = 0;
va_start(ap,e);
for (i = 0; i < pa->dim; ++i) {
arg = va_arg(ap,int);
if (arg < 0 || arg > pa->bounds[i]) return NK;
off += pa->constants[i] * arg; // 数组下标顺序要求是从左到右 - 得看constants存储数组下标对应
}
va_end(ap);
*(pa->base + off) = e;
printf("%2d = %d ",off,e);
return OK;
}
/* 简单测试数组的基本操作函数 */
int main(void)
{
int i,j,rv;
int dl,dr,dim;
Array a;
dim = 2;
dl = dr = 5;
init_array(&a,dim,dl,dr);
for (i = 0; i < dl; ++i) {
for (j = 0; j < dr; ++j) {
assign_array_value(&a,i + j,i,j);
}
printf("n");
}
destroy_array(&a);
return 0;
}
思路 man变长参数 type va_arg(va_list ap,type) void va_end(va_list ap) [变长参数宏实现 —— 根据参数在栈中的分布得来:《汇编语言》、《程序员的自我修养》] (3) 矩阵的压缩存储07.06 5.2 广义表(1) 广义表的定义广义表一般记作 在线性表中, (2) 广义表的存储结构由于广义表中的数据元素可以具有不同的结构(原子或子表),因此难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可用一个结点表示。 6 树和二叉树6.1 树07.07 6.1 二叉树(1) 定义 & 性质 二叉树性质。 满二叉树。一个深度为k且有
完全二叉树的性质。
07.08 (2) 存储结构(3) 二叉树的遍历遍历对于线性结构来说,是一件容易的事情。对于像二叉树这样的非线性结构,需要寻找一种规律,以便使二叉树上的结点能排列在一个现行队列上,从而便于遍历。 6.3 赫夫曼树07.11 (1) 赫夫曼树含义树中两个结点之间的路径长度。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。 树的路径长度。从树根到每一个结点的路径长度之和。 (2) 构造赫夫曼树根据赫夫曼算法构造赫夫曼树: 例。 07.12 (3) 赫夫曼编码6.4 红黑树[-来自度娘-] 二叉查找树。也称有序二叉树(排序二叉树),是指一棵空树或者具有以下性质的二叉树:[1] 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;[2] 若任意结点的右子树不为空,则右子树上所有结点的值绝大于它的根结点值;[3] 没有键值相等的结点。 平衡二叉树。平衡二叉树具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。(常用算法有红黑树、AVL、Treap、伸展树等) 红黑树。红黑树是一种具有二叉查找树性质的自平衡二叉树:在进行插入和删除操作时通过特定的操作保持二叉树的平衡,从而获得较高的查找性能。[它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并在在实践中是高效的:它可以在
红黑树性质。 一棵红黑树 树的旋转。左旋:当在某个结点node上,做左旋操作时,假设右孩子不为NULL,则node结点所代表的子树可以作为其右孩子的左结点,原来右节点中的左子结点依照具体情况成为node上的左结点或右结点。(右旋同理)左旋如下图 [2016.07.01 - 0:09] (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |