郑州营销网站建设公司,新媒体营销论文选题方向,找人做网站推广,大连百度推广优化栈、队列和数组 栈队列数组数组的顺序表示和实现顺序表中查找和修改数组元素 矩阵的压缩存储特殊矩阵稀疏矩阵 栈 初始化
#define MaxSize 50//栈中元素的最大个数
typedef char ElemType;//数据结构
typedef struct{int top;//栈顶指针ElemType data[MaxSize];//存放栈中的元… 栈、队列和数组 栈队列数组数组的顺序表示和实现顺序表中查找和修改数组元素 矩阵的压缩存储特殊矩阵稀疏矩阵 栈 初始化
#define MaxSize 50//栈中元素的最大个数
typedef char ElemType;//数据结构
typedef struct{int top;//栈顶指针ElemType data[MaxSize];//存放栈中的元素
}SqStack;//初始化栈给top赋值为-1
void InitStack(SqStack *stack){stack-top -1;
}判断是否为空
//判断栈是否为空,空返回true反之即返回false
bool StackEmpty(SqStack stack){if(stack.top-1) return true;return false;
}进栈
//进栈
bool Push(SqStack *stack,ElemType e){//判断是否满栈if(stack-topMaxSize-1) return false;//指针先加1再入栈stack-data[stack-top]e;return true;
}出栈
//出栈
ElemType Pop(SqStack *stack){//判断是否为空栈if(stack-top-1) return false;//先取值再自减return stack-data[stack-top--];
}读取栈顶元素
//读取栈顶元素
ElemType GetTop(SqStack stack){//判断是否为空栈if(stack.top-1) return false;return stack.data[stack.top];
}队列 初始化
#define MaxSize 5
typedef char ElemType;typedef struct
{ElemType data[MaxSize];int rear,front;
}SqQueue;//初始化
void InitQueue(SqQueue *queue){queue-front queue-rear0;
}判断空
//判断是否为空即判断首尾指针是否相等
bool QueueEmpty(SqQueue queue){if(queue.frontqueue.rear) return true;return false;
}入队
//入队
bool EnQueue(SqQueue *queue,ElemType e){//判断是否是满队即尾指针的下一个指向首指针if((queue-rear1)%MaxSizequeue-front) return false;queue-data[queue-rear]e;//赋值//尾指针1取模queue-rear (queue-rear1)%MaxSize;return true;
}出队
//出队
ElemType DeQueue(SqQueue *queue){//判断是否为空if(queue-frontqueue-rear) return false;//先取值首指针再1取模ElemType e queue-data[queue-front];queue-front;return e;
}数组
提到数组大家首先会想到的是很多编程语言中都提供有数组这种数据类型比如 C/C、Java、Go、C# 等。但本节我要讲解的不是作为数据类型的数组而是数据结构中提供的一种叫数组的存储结构。
和线性存储结构相比数组最大的不同是它存储的数据可以包含多种“一对一”的逻辑关系。举个简单的例子 上图中{a1, a2, a3, a4}、{b1, b2, b3, b4}、{c1, c2, c3, c4}、{d1, d2, d3, d4} 中各自包含的元素具有“一对一”的逻辑关系同时 a、b、c、d 这 4 个序列也具有“一对一”的逻辑关系。
这样存储不止一种“一对一”逻辑关系的数据数据结构就推荐使用数组存储结构。 对于数组存储结构我们可以这样理解它数组是对线性表的扩展是一种“特殊”的线性存储结构用来存储具有多种“一对一”逻辑关系的数据。
实际场景中存储具有 N 种“一对一”逻辑关系的数据通常会建立 N 维数组
一维数组和其它线性存储结构很类似用来存储只有一种“一对一”逻辑关系的数据 二维数组用来存储包含两种“一对一”逻辑关系的数据。二维数组可以看作是存储一维数组的一维数组 n 维数组用来存储包含 n 种“一对一”逻辑关系的数据可以看作是存储 n-1 维数组的一维数组 数组存储结构还具有一些其它的特性包括
无论数组的维度是多少数组中的数据类型都必须一致数组一旦建立它的维度将不再改变数组存储结构不会对内部的元素做插入和删除操作常见的操作有 4 种分别是初始化数组、销毁数组、取数组中的元素和修改数组中的元素。 数组的顺序表示和实现
数组可以是多维的而顺序表只能是一维的线性空间。要想将 N 维的数组存储到顺序表中可以采用以下两种方案
以列序为主先列后行按照行号从小到大的顺序依次存储每一列的元素以行序为主先行后序按照列号从小到大的顺序依次存储每一行的元素。
多维数组中最常用的是二维数组接下里就以二维数组为例讲解数组的顺序存储结构。 所示的二维数组按照“列序为主”的方案存储时数组中的元素在顺序表中的存储状态如下图所示 同样的道理按照“行序为主”的方案存储数组时各个元素在顺序表中的存储状态如图 顺序表中查找和修改数组元素
注意只有在顺序表内查找到数组中的目标元素之后才能对该元素执行读取和修改操作。
在 N 维数组中查找目标元素需知道以下信息
数组的存储方式数组在内存中存放的起始地址目标元素在数组中的坐标。比如说二维数组中是通过行标和列标来确定元素位置的数组中元素的类型即数组中单个数据元素所占内存的大小通常用字母 L 表示
根据存储方式的不同查找目标元素的方式也不同。仍以二维数组为例如果数组采用“行序为主”的存储方式则在二维数组 anm 中查找 aij 位置的公式为
LOC(i, j) LOC(0, 0) (i * m j) * L;其中LOC(i, j) 为 aij 在内存中的地址LOC(0, 0) 为二维数组在内存中存放的起始位置也就是 a00 的位置。
而如果采用以列存储的方式在 anm 中查找 aij 的方式为
LOC(i, j) LOC(0, 0) (j * n i) * L;根据以上两个公式就可以在顺序表中找到目标元素自然也就可以进行读取和修改操作了。 代码实现
#includestdarg.h
#includemalloc.h
#includestdio.h
#includestdlib.h // atoi()
#includeio.h // eof()
#includemath.h#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW 3
#define UNDERFLOW 4
typedef int Status; //Status是函数的类型,其值是函数结果状态代码如OK等
typedef int Boolean; //Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;#define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8
typedef struct
{ElemType* base; //数组元素基址由InitArray分配int dim; //数组维数int* bounds; //数组维界基址由InitArray分配int* constants; // 数组映象函数常量基址由InitArray分配
} Array;Status InitArray(Array* A, int dim, ...)
{//若维数dim和各维长度合法则构造相应的数组A并返回OKint elemtotal 1, i; // elemtotal是元素总值va_list ap;if (dim1 || dimMAX_ARRAY_DIM)return ERROR;(*A).dim dim;(*A).bounds (int*)malloc(dim * sizeof(int));if (!(*A).bounds)exit(OVERFLOW);va_start(ap, dim);for (i 0; i dim; i){(*A).bounds[i] va_arg(ap, int);if ((*A).bounds[i] 0)return UNDERFLOW;elemtotal * (*A).bounds[i];}va_end(ap);(*A).base (ElemType*)malloc(elemtotal * sizeof(ElemType));if (!(*A).base)exit(OVERFLOW);(*A).constants (int*)malloc(dim * sizeof(int));if (!(*A).constants)exit(OVERFLOW);(*A).constants[dim - 1] 1;for (i dim - 2; i 0; --i)(*A).constants[i] (*A).bounds[i 1] * (*A).constants[i 1];return OK;
}Status DestroyArray(Array* A)
{//销毁数组Aif ((*A).base){free((*A).base);(*A).base NULL;}elsereturn ERROR;if ((*A).bounds){free((*A).bounds);(*A).bounds NULL;}elsereturn ERROR;if ((*A).constants){free((*A).constants);(*A).constants NULL;}elsereturn ERROR;return OK;
}Status Locate(Array A, va_list ap, int* off) // Value()、Assign()调用此函数 */
{//若ap指示的各下标值合法则求出该元素在A中的相对地址offint i, ind;*off 0;for (i 0; i A.dim; i){ind va_arg(ap, int);if (ind 0 || ind A.bounds[i])return OVERFLOW;*off A.constants[i] * ind;}return OK;
}Status Value(ElemType* e, Array A, ...) //在VC中...之前的形参不能是引用类型
{//依次为各维的下标值若各下标合法则e被赋值为A的相应的元素值va_list ap;Status result;int off;va_start(ap, A);if ((result Locate(A, ap, off)) OVERFLOW) //调用Locate()return result;*e *(A.base off);return OK;
}Status Assign(Array* A, ElemType e, ...)
{//依次为各维的下标值若各下标合法则将e的值赋给A的指定的元素va_list ap;Status result;int off;va_start(ap, e);if ((result Locate(*A, ap, off)) OVERFLOW) //调用Locate()return result;*((*A).base off) e;return OK;
}int main()
{Array A;int i, j, k, * p, dim 3, bound1 3, bound2 4, bound3 2; //a[3][4][2]数组ElemType e, * p1;InitArray(A, dim, bound1, bound2, bound3); //构造342的3维数组Ap A.bounds;printf(A.bounds);for (i 0; i dim; i) //顺序输出A.boundsprintf(%d , *(p i));p A.constants;printf(\nA.constants);for (i 0; i dim; i) //顺序输出A.constantsprintf(%d , *(p i));printf(\n%d页%d行%d列矩阵元素如下:\n, bound1, bound2, bound3);for (i 0; i bound1; i){for (j 0; j bound2; j){for (k 0; k bound3; k){Assign(A, i * 100 j * 10 k, i, j, k); // 将i*100j*10k赋值给A[i][j][k]Value(e, A, i, j, k); //将A[i][j][k]的值赋给eprintf(A[%d][%d][%d]%2d , i, j, k, e); //输出A[i][j][k]}printf(\n);}printf(\n);}p1 A.base;printf(A.base\n);for (i 0; i bound1 * bound2 * bound3; i) //顺序输出A.base{printf(%4d, *(p1 i));if (i % (bound2 * bound3) bound2 * bound3 - 1)printf(\n);}DestroyArray(A);return 0;
}矩阵的压缩存储
特殊矩阵
这里所说的特殊矩阵主要分为以下两类
含有大量相同数据元素的矩阵比如对称矩阵含有大量 0 元素的矩阵比如稀疏矩阵、上下三角矩阵
针对以上两类矩阵数据结构的压缩存储思想是矩阵中的相同数据元素包括元素 0只存储一个 数据元素沿主对角线对应相等这类矩阵称为对称矩阵矩阵中有两条对角线对角线称为主对角线另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。
对称矩阵的实现过程是若存储下三角中的元素只需将各元素所在的行标 i 和列标 j 代入下面的公式 存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式 最终求得的 k 值即为该元素存储到数组中的位置矩阵中元素的行标和列标都从 1 开始。
例如在数组 skr[6] 中存储图 1 中的对称矩阵则矩阵的压缩存储状态如图所示存储上三角和下三角的结果相同 注意以上两个公式既是用来存储矩阵中元素的也用来从数组中提取矩阵相应位置的元素。例如如果想从图中的数组提取矩阵中位于 (3,1) 处的元素由于该元素位于下三角需用下三角公式获取元素在数组中的位置即 稀疏矩阵 如果矩阵中分布有大量的元素 0即非 0 元素非常少这类矩阵称为稀疏矩阵。
压缩存储稀疏矩阵的方法是只存储矩阵中的非 0 元素与前面的存储方法不同稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。
例如存储上图中的稀疏矩阵需存储以下信息
(1,1,1)数据元素为 1在矩阵中的位置为 (1,1)(3,3,1)数据元素为 3在矩阵中的位置为 (3,1)(5,2,3)数据元素为 5在矩阵中的位置为 (2,3)除此之外还要存储矩阵的行数 3 和列数 3 **若对其进行压缩存储矩阵中各非 0 元素的存储状态如图 ** 三元组的结构体
//三元组结构体
typedef struct {int i,j;//行标i列标jint data;//元素值
}triple;由于稀疏矩阵中非 0 元素有多个因此需要建立 triple 数组存储各个元素的三元组。除此之外考虑到还要存储矩阵的总行数和总列数因此可以采用以下结构表示整个稀疏矩阵
#define number 20
//矩阵的结构表示
typedef struct {triple data[number];//存储该矩阵中所有非0元素的三元组int mu, nu, tu;//mu和nu分别记录矩阵的行数和列数tu记录矩阵中所有的非0元素的个数
}TSMatrix;#includestdio.h
#define NUM 3
//存储三元组的结构体
typedef struct {int i, j;int data;
}triple;
//存储稀疏矩阵的结构体
typedef struct {triple data[NUM];int mu, nu, tu;
}TSMatrix;
//输出存储的稀疏矩阵
void display(TSMatrix M);
int main() {TSMatrix M;M.mu 3;M.nu 3;M.tu 3;M.data[0].i 1;M.data[0].j 1;M.data[0].data 1;M.data[1].i 2;M.data[1].j 3;M.data[1].data 5;M.data[2].i 3;M.data[2].j 1;M.data[2].data 3;display(M);return 0;
}
void display(TSMatrix M) {int i, j, k;for (i 1; i M.mu; i) {for (j 1; j M.nu; j) {int value 0;for (k 0; k M.tu; k) {if (i M.data[k].i j M.data[k].j) {printf(%d , M.data[k].data);value 1;break;}}if (value 0)printf(0 );}printf(\n);}
}
