《2022年数据结构知识 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构知识 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章线性表2.1.1 线性表的定义特性：设 A=（a1,a2,.,ai-1,ai,ai+1,an）是一线性表线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；在表中 ai-1 领先于 ai，ai 领先于 ai+1，称 ai-1 是 ai 的直接前驱，ai+1 是ai 的直接后继；在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；线性表中元素的个数n 称为线性表的长度，n=0 时称为空表；ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线
2、性表中的位置，仅取决于它的序号；【例 2-3】已知一个非纯集合（即集合B中可能有相同元素），试构造一个纯集合A，使中只包含B中所有值各不相同的成员。【分析】假设仍以线性表表示集合，则此问题和例2-2 类似，即构造线性表La，使其只包含线性表 Lb 中所有值不相同的数据元素。所不同之处是，操作实施之前，线性表 La 不存在，则操作的第一步首先应该构造一个空的线性表，之后的操作步骤和例2-2 相同。【具体步骤】（1）构造一个空的线性表La；（2）从线性表Lb 中取得一个数据元素；（3）依该数据元素的值在线性表La 中进行查访；（4）若线性表La 中不存在和其值相同的数据元素，则从Lb 中删除的这个
3、数据元素插入到线性表 La 中。（5）重复（2）至（4）的操作直至Lb 为空表为止。【具体算法】_运行后 Lb 仍保持原先的值 void purge(List&La,List&Lb)InitList(La);La_len=0;/创建一个空的线性表La Lb_len=ListLength(Lb);/求线性表Lb 的长度 for(i=1;i next;return(k);算法的时间复杂度：O(n)，其中 n 为表长。2.查找元素操作【分析】在单链表L 中查找和给定值e 相等的数据元素的过程和顺序表类似，从第一个结点起，依次和e 相比较，直到找到一个其值和e 相等的元素，则返回它在链表中的“位置”；
4、或者查遍整个链表都不存在这样的一个元素后，返回“NULL”。【具体算法】LNode *LocateElem_L(LinkList L,ElemType e)p=L;while(p&p-data!=e)p=p-next;return(p);算法的时间复杂度：O(n)，其中 n 为表长。3.向单链表中插入一个元素链表插入的核心语句：Step 1：q-next=p-next;Step 2：p-next=q；4.删除结点操作【分析】和插入类似，在单链表中删除一个结点时，也不需要移动数据元素，仅需修改相应的指针链接。但由于删除结点时，需要修改的是它的“前驱”结点的指针域，因此和“前插”操作一样，首先应当
5、找到它的前驱结点。（1）q-next=p-next;（2）free(p);【具体算法】Status ListDelete_L(LinkList&L,int i,ElemType&e)/在带头结点的单链表L 中，删除第i 个元素，并由e 返回真值 p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;算法时间复杂度：O(n)，其中 n 为表长。【例 2-5】逆序创建链表。【分析】链表是一种动态管理的结构，它和顺序表不同，链表中每个
6、结点占用的存储空间不需预先分配划定，而是在运行时刻由系统根据需求即时生成的。因此，建立链表的过程是一个动态生成的过程。即从“空表”起，依次建立结点，并逐个插入链表。所谓“逆序”创建链表指的是，依和线性表的逻辑顺序相“逆”的次序输入元素，逆序生成链表可以为处理头指针提供方便。【具体算法】void CreateList_L(LinkList&L,int n)L=NULL;/建立一个空的单链表 for(i=n;i=0;i-)s=(LinkList)malloc(sizeof(LNode);/生成新结点 scanf(&s-data);/赋元素值 s-next=L;/插入在第一个结点之前 L=s;2.3
7、.4 循环链表1 循环链表的概念循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点说明:在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；循环链表与单链表操作的主要差别是算法中循环结束的条件不是p 或 p-next是否为NULL，而是它们是否等于首指针；对循环链表，有时不给出头指针，而是给出尾指针两循环链表合并：p=a-next;q=b-next;a-next=q-next;b-next=p;free(q);2.3.5 双向链表名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 16 页 -双向链表中
8、，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。线性表和有序表有两种存储表示：顺序表和链表顺序表：需要预分配一定长度的存储空间。太大易造成存储空间的浪费，太小又将造成频繁地进行存储空间的再分配。顺序表是一种随机存储的结构，对顺序表中任一元素进行存取的时间相同。顺序表对插入、删除操作需要移动近一半的数据元素。链表：存储分配灵活，链表中的结点可在程序执行过程中动态生成。链表是一种顺序存储的结构，对链表中的每个结点都必须从头指针所指结点起顺链扫描。链表对插入、删除操作不需要移动数据元素。第三章栈3.1 栈定义：是限定仅在表尾进行插入或删除操作的线性表。允许插入,删除的一
9、端称为栈顶(top),另一端称为栈底(bottom 逻辑特征：后进先出(LIFO 基本操作：创建一个空栈；判断栈是否为空栈；判断栈是否为满；往栈中插入(或称推入)一个元素；从栈中删除(或称弹出)一个元素；求栈顶元素的值。访问栈中每个元素3.1.1 栈的特点和操作一般线性表堆栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)2.存储结构顺序用栈或链栈存储均可,顺序栈更常见3.运算规则只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。4.实现方式关键是编写入栈和出栈函数，具体实现依顺序栈或链
10、栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建栈、判栈满、判栈空等。栈是仅在表尾进行插入、删除操作的线性表。表尾(即 an 端)称为栈顶 top;表头(即 a1 端)称为栈底base 例如：栈s=(a1,a2,a3,an-1,an)a1 称为栈底元素 an 称为栈顶元素插入元素到栈顶(即表尾)的操作，称为入栈。从栈顶(即表尾)删除最后一个元素的操作，称为出栈。强调：插入和删除都只能在表的一端（栈顶）进行！“进”压入=PUSH（x)“出”弹出=POP(y)问：为什么要设计堆栈？它有什么独特用途？1.调用函数或子程序非它莫属；2.递归运算的有力工具；3.用于保护现场和恢复现场；4.简化了程
11、序设计的问题。问：栈是什么？它与一般线性表有什么不同？答：栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 16 页 -与一般线性表的区别：仅在于运算规则不同。3.1.2 栈的表示和操作实现SqStack：结构类型名；SqStack:它的三个域分别是：base：栈底指针，指向栈底位置；top：栈顶指针；Stacksize：已分配的存储空间(一元素为单位)大小；约定栈顶指针指向栈顶元素的下(后面)一个位置顺序栈基本操作的实现：栈顶的初始化：S.top=S.base 栈空：S.base=S.top 栈满：S.top-S
12、.base=S.stacksize 入栈：*S.top+=e，出栈：e=*-S.top 约定：top 指向栈顶元素的下一个位置顺序栈算法的实现1)初始化操作InitStack_Sq(SqStack&S)参数：S是存放栈的结构变量；功能：建一个空栈S；void InitStack_Sq(SqStack&S,int maxsize=STACK_INIT_SIZE,int incresize=SRACKINCREMENTSIZE)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);
13、S.top=S.base;S.stacksize=maxsize;S.incrementsize=incresize;/InitStack_Sq 2)取栈顶元素操作GetTop_Sq(SqStack S,SElemType&e)功能：取栈顶元素，并用e 返回;Status GetTop_Sq(SqStack S,SelemType&e)if(S.top=S.base)return ERROR;e=*(S.top-1);return TRUE;3)入栈操作Push(SqStack&S,SElemType e)功能：将e 入栈;1)S 是否已满,若栈满，重新分配存储空间；2)将元素 e 写入栈顶；
14、3)修改栈顶指针,使栈顶指针指向栈顶元素的下(后面)一个位置；4)出栈操作Pop(SqStack&S,SElemType&e)功能：栈顶元素退栈，并用e 返回;2.栈的表示与实现链栈1.链式栈无栈满问题，空间可扩充2.插入与删除仅在栈顶处执行3.链式栈的栈顶在链名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 16 页 -头 4。适合于多栈操作可以不必引入头结点约定：top 指向栈顶元素所在的结点链栈的定义顺序栈算法typedef int bool;初始化#define TRUE 1;void InitStack_L(LinkStack*S)#define FALSE 0;S=NU
15、LL;typedef int ElemType;ElemType data;入栈 struct node*next;void Push_L(LinkStack*S,ElemType e)LNode;LNode*p=new LNode;p-data=e;Typedef LinkList LinkStack p-next=S;S=p;例三表达式求值限于二元运算符的表达式定义:表达式 :=(操作数)(运算符)(操作数)操作数 :=简单变量|表达式简单变量 :=标识符|无符号整数表达式的三种标识方法：设 Exp=S1 OP S2 则称 OP S1 S2 为前缀表示法S1 OP S2 为中缀表示法S1
16、S2 OP 为后缀表示法例如:Exp=a b+(c d/e)f 前缀式:+a b c/d e f 中缀式:a b+c d/e f 后缀式:a b c d e/f +结论:1)操作数之间的相对次序不变;2)运算符的相对次序不同;3)中缀式丢失了括弧信息,致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;例四实现递归递归的对象：一个对象部分地包含它自己，或用它自己给自己定义。(如某些数据结构的定义)线性表
17、的另一种定义:若元素个数为0，则称为空表若元素个数大于0,则有且仅有一个第一个元素(即表头),剩余元素形成一个表(即表尾)。递归的过程：一个过程直接或间接地调用自己如：0 的阶乘是1，n(n0)的阶乘等于n乘上(n-1)的阶乘当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：?将所有的实在参数、返回地址等信息传递给被调用函数保存;?为被调用函数的局部变量分配存储区;?将控制转移到被调用函数的入口。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 16 页 -从被调用函数返回调用函数之前,应该完成三项任务：?保存被调函数的计算结果;?释放被调函数的数据
18、区;?依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则是:后调用先返回！递归函数执行过程可视为同一函数进行嵌套调用,例如：递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。栈与递归的实现求解阶乘函数的递归算法long fact(long n)if(n=0)return 1;/递归结束条件 else return n*fact(n-1);/递归的规则 3.3 队列 (Queue)定义队列是只允许在一端删除，在另一端插入的顺序表,允许删除的一端叫做队头(fro
19、nt)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,First In First Out)常用操作初始化空队、入队、出队、判断队空、判断队满、取队头1.定义只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）2.逻辑结构与同线性表相同，仍为一对一关系。3.存储结构顺序队或链队，以循环顺序队更常见。4.运算规则只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。5.实现方式关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。基本操作有入队或出队，建空队列，判队空或队满等操作队列的进队和出队原则进队时队尾指针先进一 rear=rear+1
20、，再将新元素按 rear 指示位置加入。出队时队头指针先进一 front=front+1，再将下标为 front 的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列元素存放数组首尾相接,形成循环(环形)队列。3.3.2 队列的表示和操作实现链队列：基本操作的实现无队满问题(除非分配不出内存),空间可扩充引入头结点(一定需要吗？)1.队头在链头，队尾在链尾。链式队列在进队时无队满问题,但有队空问题。2、队空条件为:front=NULL?链式栈无栈满问题，空间可扩充?插入与删除仅在栈顶处执行名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 16 页 -?链
21、式栈的栈顶在链头?适合于多栈操作讨论：队列会满吗？一般不会，因为删除时有free动作。除非内存不足！怎样实现入队和出队操作？入队（尾部插入）：rear-next=S;rear=S;出队（头部删除）：front-next=p-next;循环队列队列的顺序存储约定与类型定义：Q.front和 Q.rear的含义删除：避免大量的移动-头指针增1 问题：假上溢?首尾相接的环（钟）基本操作的实现初始化空队：Q.front=Q.rear=0;入队：判断是否队满；非队满时，Q.rear位置放新插入的元素,Q.rear+出队：判断是否队空，非队空时，Q.front位置为待删除的元素,Q.front+队空条件：
22、Q.front=Q.rear 队满条件：Q.rear=MAXQSIZE 问题：假上溢()循环队列队列存放数组被当作首尾相接的表处理。队头、队尾指针加1 时从 maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针出:front=(front+1)%maxSize;队尾指针进:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front=rear;队满条件：(rear+1)%maxSize=front 队空：Q.front=Q.rear 队满：Q.front=(Q.rear+1)%maxSize 入队:Q.rear=(Q.rear+1)%
23、maxSize 出队:Q.front=(front+1)%maxSize;求队长:(Q.rear-Q.front+maxSize)%maxSize 线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表 FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。串
24、4.1 串的定义和操作?串（string）：由 0 个 或 多 个 字 符 组 成 的 有 限 序 列，也 称 字 符 串。记 为：s=a0a1a2,an-1 (n 0),其中s 是串的名，a0a1a2,an-1是串的值，名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 16 页 -ai(0 i n-1)可以是字母、数字或其它字符。?串长度：串中字符的数目n。?空串：不含任何字符的串，串长度=0?空格串：仅由一个或多个空格组成的串?子串：由串中任意个连续的字符组成的子序列?主串：包含子串的串。?串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。?注意：(1)串值
25、必须用一对单引号括起来?(2)串值大小是按词典次序进行比较的?StrCompare(data ,Stru )0显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。串的逻辑结构和线性表的区别:1.串的数据对象约束为字符集。2.线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。注：用 C 处理字符串时，要调用标准库函数#include 串比较，int strcmp(chars1,char s2);/StrCompare(S,T)求串长，int strlen(char s);/StrLength(S)串连接，char strcat(char*
26、to,char*from)/Concat(&T,S1,S2)子串定位，char strchr(char*s,char*c);/Index(S,T,pos)?gets(char*s)输入一个串；?puts(char*s)输出一个串；?strcat(char*s1,char*s2)串联接函数；?strcpy(char*s1,char*s2)串复制函数；?strcmp(char*s1,char*s2)串比较函数；?strlen(char*s)求串长函数；表示空串，空串的长度为零。串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大
27、多以单个元素作为操作对象；在串的基本操作中，通常以串的整体作为操作对象。串的整体操作赋值 StrAssign(S,“Data Structure”)复制 StrCopy(T,S)/T=S,T为“Data Structure”比较 StrCompare(S,T)连接 Concat(T,“Data”,“Structure”)/T为“DataStructure”取子串 SubString(sub,S,2,5)/sub为“ata S”子串在主串中的定位 Index(S,“a”,3)/4 子串置换 Replace(S,“a”,“b”)/S为“Dbtb Structure”子串插入 StrInsert(S
28、,3,“aha”)/“Daahata Structure”子串删除 StrDelete(S,3,5)/“Daructure”4.2 串的表示和实现首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 16 页 -串有三种机内表示方法：顺序存储定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列?堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。链式存储串的块链存储表示链式方式存储4.2.1 串的定长顺序存储表示定长顺序
29、存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。注：一般用SString0来存放串长信息；C语言约定在串尾加结束符 0，以利操作加速，但不计入串长；若字符串超过Maxstrlen 则自动截断（因为静态数组存不进去）。实现方式：两串连接和求子串通常，C/C+语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()/new和 free()/delete 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为堆。C语言中的串以一个空字符为结束符，串长是一个隐含值。这类串操作实现的算法为:先为新生成
30、的串分配一个存储空间，然后进行串值的复制。4.2.3 串的块链存储表示也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。4.3 串的模式匹配算法算法目的：确定主串中所含子串第一次出现的位置（定位）即如何实现Index(S,T,pos)函数?BF算法 (又称古典的、经典的、朴素的、穷举的)?KMP算法 (特点：速度快)模式匹配(Pattern Matching)即子串定位运算(Index函数).Index(S,T,pos)函数初始条件：串S和 T 存在，T 是非空串，1 posStrLength(s)操作结
31、果：若主串 S中存在和串T 值相同的子串，则返回它在主串S中第 pos 个字符之后第一次出现的位置；否则函数值为0。注：S称为被匹配的串，T称为模式串。若S包含串 T，则称匹配成功。否则称匹配不成功。BF算法设计思想：将主串的第pos 个字符和模式的第1 个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回值为S 中与 T 匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0.模式匹配的最简单的做法是：用 T中的字符依次与S中的字符比较：如果 S0=T0，S1=T1，,，Sm-1
32、=Tm-1，则匹配成功,调用求子串的操作subString(S,1,m)即是找到的子串。否则必有某个 i（0i m-1），使得 Si Ti，这时可将T 右移一个字符,用 T 中字符从头开始与S中字符依次比较；如此反复执行，直到下面两种情况之一：或者到达某步时，Si=T0，Si+1=T1，,，Si+m-1=Tm-1，匹配成功，subString(S,i+1,m)即是找到的（第一个）与模式T 相同的子串；或者一直将T 移到无法与S继续比较为止,则匹配失败。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 16 页 -BF算法的时间复杂度讨论：若 n 为主串长度，m为子串长度，则串的B
33、F匹配算法最坏的情况下需要比较字符的总次数为：(n-m+1)*m O(n*m)最恶劣情况是：主串前面n-m 个位置都部分匹配到子串的最后一位，即这n-m 位各比较了m次，再加上最后m位也各比较了1 次，所以总次数为：(n-m)*m+m(n-m+1)*m 最好的情况是：一配就中！一般的情况是：O(n+m)要从最好到最坏情况统计总的比较次数,然后取平均。4.4 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表定义特殊的线性表：一个数组中，数据元素的类型是一样的；数据元素的类型可能是非结构的原子类型，也可能是定长线性表。数组一旦被定义，它的维数和维界就不再改变。数组(数据结构
34、)vs 数组类型(程序设计语言中)数组(数据结构)反映数据元素之间的特殊逻辑关系可以用数组类型表示，也可以用链表示数组类型体现物理表示，如C 中规定按行优先存储?ADT Array 初始化、注销、存取元素值-无插入、删除操作?二维数组a00 a01 ,a0,n-1 a10 a11 ,a1,n-1,am-1,0 am-1,1 ,am-1,n-1 将二维数组看成是一个定长线性表，即A =(a0,a1,.,ap)p=m-1 或n-1 其中每个数据元素也是一个定长线性表，即aj=(a0j,a1j,.,am-1,j)0j n-1 aj是列向量形式的线性表ai=(ai0,ai1,.,ai,n-1)0i m
35、-1 ai是行向量形式的线性表4.4.1 数组的定义和操作数组：由一组名字相同、下标不同的变量构成注意：本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；本章的数组既可以是顺序的，也可以是链式结构。一维数组的特点：1 个下标，ai 是 ai+1 的直接前驱二维数组的特点：2 个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：N维数组的特点：n 个下标，每个元素受到n 个关系约束一个 n 维数组可以看成是由若干个n1 维数组组成的线性表。4.4.2 数组的顺序存储表示和实现注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；?约
36、定的次序不同，则计算元素地址的公式也有所不同；?C和 PASCAL 中一般采用行优先顺序；FORTRAN 采用列优先。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 16 页 -无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：开始结点的存放地址（即基地址）维数和每维的上、下界；每个数组元素所占用的单元数补充：计算二维数组元素地址的通式设一般的二维数组是Ac1.d1,c2.d2，这里 c1,c2不一定是 0。则行优先存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2
37、)*L 二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L 二维数组 A 中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2i j)L 若是 N维数组，其中任一元素的地址该如何计算？Loc(j1,j2,jn)=LOC(0,0,0)其中 Cn=L,Ci-1=bi Ci，1i n 例：一个二维数组A，行下标的范围是1 到 6，列下标的范围是0 到 7，每个数组元素用相邻的6 个字节存储，存储器按字节编址。那么，这个数组的体积是 288 个字节。Volume=m*n*L=(6-1+1)*(7-0+1)*6=4
38、8*6=288 例：已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)=Loc(a11)+(i-1)*m+(j-1)*K,按列存储的公式是？Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）例：设数组a1,60,1,70的基地址为2048，每个元素占2 个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 8950 。LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L 得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950 以常规方法，即以二维数
39、组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2）计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零;解决问题的原则:1)尽可能少存或不存零值元素;2)尽可能减少没有实际意义的运算;3)操作方便;即:能尽可能快地找到与下标值(i,j)对应的元素;能尽可能快地找到同一行或同一列的非零值元;4.4 矩阵的压缩存储讨论：1.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。3.什么样的矩阵具备以上压缩条件？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等
40、。4.什么叫稀疏矩阵？niii1jC名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 16 页 -矩阵中非零元素的个数较少（一般小于5%）4.4.1 特殊形状矩阵的存储表示所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1.对称矩阵在一个 n 阶方阵 A中，若元素满足下述性质：aij=aji 0i,jn-1 则称 A 为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。?对称矩阵为每一对对称元分配一个存储空间：n2n(n+1)/2 以行序
41、为主序存储下三角中的元下三角矩阵2.三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵：它的下三角(除主对角线)中的元素均为常数。下三角矩阵：它的主对角线上方均为常数。三角矩阵常数为零1、若 i j，则 ai j在下三角形中。ai j之前的 i 行(从第 0 行到第 i-1行)一共有:1+2+,+i=i(i+1)/2个元素，在第 i 行上,ai j之前恰有 j 个元素（即 ai0,ai1,ai2,aij-1），因此有：k=i*(i+1)/2+j 0kn(n+1)/2 2、若 ij，则 aij是在上三角矩阵中。因为 aij=aji，所以只要交换上述对应关系式中的i 和 j 即可得到
42、：k=j*(j+1)/2+i 0 kn(n+1)/2 3.对角矩阵Loc(aij)=Loc(a11)+2(i-1)+(j-1)|i-j|=1 稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值稀疏矩阵的三元组顺序表表示存储非零元：记录值、位置(行下标和列下标)三元组三元组的排列次序：这里以行序为主序，也可选择以列序为主序有序表稀疏矩阵的规模：行数、列数以及非零元的个数稀疏矩阵压缩存储的缺点：将失去随机存取功能如何求转置矩阵？用常规的二维数组表示时的算法 for(col=1;col=nu;+col)for(row=1;row=mu;
43、+row)Tcolrow=Mrowcol;其时间复杂度为:O(mu nu)【压缩转置算法的效率分析：1、主要时间消耗在查找M.datap.j=col的元素，由两重循环完成:for(col=1;col=M.nu;col+)循环次数 nu 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 16 页 -for(p=1;p=M.tu;p+)循环次数 tu 所以该算法的时间复杂度为O(nu*tu)-即 M的列数与M中非零元素的个数之积最恶劣情况：M中全是非零元素，此时tu=mu*nu，时间复杂度为 O(nu2*mu)注：若M 中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过
44、是O(nu*mu)结论：压缩转置算法不能滥用。前提：仅适用于非零元素个数很少（即tumu*nu）的情况。】链式存储结构 -带行指针向量的单链表表示每行的非零元用一个单链表存放设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空表头结点与单链表结点类型定义0 2、十字链表稀疏矩阵的十字链表表示结点：非零元的信息(三元组)、所在行和列的后继链域十字：每一个非零元结点既是某行链表中的一个结点，又是某列链表中的一个结点。稀疏矩阵的规模：行数、列数以及非零元的个数用十字链表表示用途：方便稀疏矩阵的加减运算；方法：每个非0 元素占用5 个域。十字链表的特点：每行非零元素链接成带表头结点的循环链表；每列非零元素也链接成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即呈十字链状。十字链表:设行指针数组和列指针数组，分别指向每行、列第一个非零元名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 16 页 -