北京网站建设飞沐,心得体会万能模板,荆州市网站建设,网络营销方式整理目录 1、数组定义 1#xff09;数组存储地址计算示例①行优先②列优先 2#xff09;稀疏矩阵的转置三元组顺序表结构定义 ①普通矩阵转置②三元组顺序表转置稀疏矩阵③稀疏矩阵的快速转置 3#xff09;十字链表结构定义 2、广义表定义 1#xff09;基本操作①GetHead②GetT… 目录 1、数组定义 1数组存储地址计算示例①行优先②列优先 2稀疏矩阵的转置三元组顺序表结构定义 ①普通矩阵转置②三元组顺序表转置稀疏矩阵③稀疏矩阵的快速转置 3十字链表结构定义 2、广义表定义 1基本操作①GetHead②GetTail 2构造存储结构的两种方法表头表尾结构定义 3递归算法①求广义表深度②复制广义表③创建广义表 1、数组
定义 数组是一种用于存储多个相同类型数据的集合其元素在内存中连续存放并按照一定的顺序排列。这种有序性和连续性使得数组在访问时具有较高的效率。数组的特点包括所有元素具有相同的数据类型、可以通过索引快速访问任意元素、支持各种操作如遍历和排序等并且数组的定义和初始化方式在不同编程语言中有所不同。 1数组存储地址计算 数组存储地址的计算主要依赖于数组的起始地址、元素的数据类型即每个元素所占的字节数以及元素的下标位置 一维数组的存储地址计算
首元素地址假设一维数组A的首地址为L且每个元素占用C个字节。则数组中任意元素A[i]的地址可以通过公式Loc(A[i]) L i * C来计算。 示例如果数组A的首地址是1000每个元素占4个字节那么A[3]的地址就是1000 3 * 4 1012。
二维数组的存储地址计算
行优先存储在行优先存储中二维数组的元素按照行的顺序依次存储。对于二维数组B[m][n]元素B[i][j]的地址计算公式为Loc(B[i][j]) Loc(B[0][0]) (i * n j) * C其中C是每个元素占用的字节数。 列优先存储在列优先存储中二维数组的元素按照列的顺序依次存储。对于二维数组B[m][n]元素B[i][j]的地址计算公式为Loc(B[i][j]) Loc(B[0][0]) (j * m i) * C。 示例假设有一个3x4的二维数组B按行优先存储首地址为1000每个元素占2个字节。那么B[2][3]的地址就是1000 (2*4 3) * 2 1026。
多维数组的存储地址计算
对于更高维度的数组地址计算方法类似只是需要考虑更多维度的索引和步长。 例如按行优先存储的三维数组D[m][n][p]的元素D[i][j][k]的地址计算公式为Loc(D[i][j][k]) Loc(D[0][0][0]) ((i * n * p j * p k) * C)。 列优先Loc(D[i][j][k]) Loc(D[0][0][0]) (knmj*mi)*C
示例
数组A[9][3][5][8],首地址为100每个元素占4个字节求a[8][2][4][7]的地址
①行优先
100(8358258487)*4
②列优先
100(7539439298)*4
2稀疏矩阵的转置
三元组顺序表 由于稀疏矩阵中含有大量的零元素空间利用率很低所以需要三元组顺序表来表示稀疏矩阵中的非零元素它通过行优先的顺序将非零元素及其位置信息存储在一个线性表中节省存储空间并简化运算 结构定义
typedef struct{int i,j;//该非零元的行下标和列下标ElemType e;
}Triple;
typedef struct{Triple data[MAXSIZE 1];//非零元三元组表data[0]未用int mu,nu,tu;//矩阵的行数、列数和非零元总数
TSMatrix;①普通矩阵转置
for(col 1;col nu;col)for(row 1;row mu;row)T[col][row] M[row][col];②三元组顺序表转置稀疏矩阵
Status TransposeSMatrix(TSMatrix M, TSMatrix T){//采用三元组表存储表示求稀疏矩阵M的转置矩阵TT.mu M.nu; T.nu M.mu; T.tu M.tu;if(T.tu){q 1;for(col 1; col M.nu; col)for(p 1; p M.tu; p)if(M.data[p].j col){T.data[q].i M.data[p].j; T.data[q].j M.data[p].i;T.data[q].e M.data[p].e; q;}}return OK;
}//TransposeSMatrix③稀疏矩阵的快速转置 如果能预先确定就诊M中每一列即T中的每一行的第一个非零元在b.data中应有的位置那么在对a.data中的三元组一次作转置时便可直接放到b.data中恰当的位置上去提高运算效率。 为此需要附设num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个数cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有 cpot[1] 1; cpot[col] cpot[col - 1] num[col - 1], 2 col a.nu
接下来就可以利用num和cpot向量快速确定转置后各元素在三元组表中的位置提高运行效率
Status FastTransposeSMatrix(TSMatrix M, TSMatrix T){//采用三元组顺序表存储表示求稀疏矩阵M的转置矩阵TT.mu M.nu; T.nu M.mu; T.tu M.tu;if(T.tu){for(col 1; col M.nu; col)num[col] 0;for(t 1; t M.tu; t)num[M.data[t].j];//求M中每一列含非零元个数cpot[1] 1;//求第col列中第一个非零元在b.data中的序号for(col 2; col M.nu; col)cpot[col] cpot[col - 1] num[col - 1];for(p 1; p M.tu; p){col M.data[p].j; q cpot[col];T.data[q].i M.data[p].j; T.data[q].j M.data[p].i;T.data[q].e M.data[p].e; cpot[col];//当一列的第一个元素转置完成后下一个需要转置的是三元组表的下一个位置}//for}//ifreturn OK;
//FastTransposeSMatrix3十字链表 十字链表是一种用于表示稀疏矩阵的特殊存储结构它通过行优先的顺序将非零元素及其位置信息存储在一个线性表中。每个节点包含五个字段行号、列号、值、向下指针和向右指针从而形成一个十字交叉的链表结构。这种结构不仅节省了存储空间还提高了运算效率并使得对稀疏矩阵的操作更加灵活和高效。 结构定义
typedef struct OLNode{int i,j;//该非零元的行和列下标ElemType e;struct OLNode *right,*down;//该非零元所在行表和列表的后继链域
}OLNode; *OLink;typedef struct{OLink *rhead,*chead;int mu,nu,tu;//稀疏矩阵的行数、列数、非零元总数
}CrossList;2、广义表
定义 广义表是一种非线性的数据结构它允许表中的元素既可以是单个数据项原子也可以是另一个广义表。这种结构使得广义表能够表示复杂的嵌套关系和层次结构。广义表的特点包括其元素的多样性可以是原子或其他广义表、结构的灵活性可以嵌套任意深度以及操作的复杂性如求表头、表尾等。在存储上广义表通常采用链式结构来表示以方便处理其复杂的嵌套关系。 1基本操作
①GetHead
获取广义表的第一个元素可以是原子可以是列表
②GetTail
除了广义表中第一个元素的所有其他元素的集合无论该元素是什么都需要在外面额外套上一个即使是空表或该值本来就有
该部分主要是在给出一个广义表时能正确获取表头和表尾
2构造存储结构的两种方法
表头表尾
结构定义
typedef struct GLNode{ElemTag tag;//公共部分用于区分原子结点和表结点union{//原子结点和表结点的联合部分AtomType atom;//atom是原子结点的值域AtomType由用户定义struct{struct GLNode *hp,*tp;}ptr;//ptr是表结点的指针域ptr.hp和[tr.tp分别指向表头和表尾};
}*GList;//广义表类型示例 A B e C abcd D ABC E aE//递归表 E aaa…
另一种方法我还没理解就不在这里说了
3递归算法 由于广义表的定义本身就具有一定的递归性且其子表问题与其本身的问题具有极高相似度、关联性所有递归算法与广义表操作具有极好的适配性 ①求广义表深度
int GListDepthGList L//采用头尾链表存储结构求广义表L的深度。if C!L return 1// 空表深度1if (L— tag ATOM) return 0;// 原子深度 0for (max0, ppL; PP; pppp-ptr. tp) {dep GListDepthpp—Ptr.hp// 求以 pp—ptr.hp 为头指针的子表深度if (dep max) max dep;}return max 1//非空表的深度是各元素的深度的最大值1
}// GListDepth②复制广义表
Status CopyGList(GList T, GList L) {// 采用头尾链表存储结构由广义表L复制得到广义表T。if(!L) T NULL;// 复制空表else {ifT GList mallocsizeofGL.NodeexitOVERFLOW// 建表结点T - tag L - tagif (L— tag ATOM) T - atom L - atom;// 复制单原子else {CopyGList(T- ptr. hp, L-ptr. hp) ;// 复制广义表L-ptr.hp 的一个副本T-ptr.hpCopyGList(T— ptr. tp, L-ptr. tp);// 复制广义表L-ptr.tp 的一个副本T-ptr.tp} // else} // elsereturn OK;
}// CopyGList③创建广义表
三种情况
带括弧的空白串长度为1的单字符串长度1的字符串
显然前两种情况为递归的终结状态子表为空表或只含一个原子结点后一种情况为递归调用
Status CreateGList (GList L, SString S) {//采用头尾链表存储结构由广义表的书写形式串S创建广义表L。设 empif StrCompareS, empLNULL //创建空表else {if (! (L (GList) malloc (sizeof (GLNode)))) exit (OVERFLOW); //建表结点if StrLengthS1L-tag ATOM; L-atom S// 创建单原子广义表else {L-tag LIST; p L;SubString (sub, S, 2, Strength(S)—2) ;// 脱外层括号do// 重复建n 个子表seversub,hsub// 从 sub中分离出表头串hsubCreateGListp-ptr. hp,hsubq pif StrEmptysub// 表尾不空if (!(p (GLode * ) malloc (sizeof (GLNode))))exit (OVERFLOW) ;p-tag LIST; q-ptr.tp p}//if}while (! StrEmpty (sub)) ;q—ptr. tp NULL;}//else} // elsereturn OK;
}// CreateGListStatus sever(SString str, SString hstr) {// 将非空串 str 分割成两部分hsub 为第一个‘’之前的子串str 为之后的子串n StrLengthstr i0;k0//k记尚未配对的左括号个数do {// 搜索最外层的第一个逗号i;SubStringch, str,i,1ifch 十十kelse if ch‘’ --k} while (in (ch! || k! 0));if (in){SubString (hstr, str, 1, i—1) SubString(str, str, i1, n—i) } else {StrCopy (hstr, str); ClearString(str) }
} // sever
