1、1.绪论绪论 2.线性表线性表3.栈和队列栈和队列4.串串5.数组和广义表数组和广义表6.树和二叉树树和二叉树8.动态存储管理动态存储管理9.查找查找10.内部排序内部排序7.图图主菜单主菜单n用计算机解决具体问题需要经过的步骤用计算机解决具体问题需要经过的步骤（1 1）从具体问题抽象出适当的数学模）从具体问题抽象出适当的数学模（2 2）设计解数学模型的算法；）设计解数学模型的算法；（3 3）编制、运行并调试程序，直到解决实际问题。）编制、运行并调试程序，直到解决实际问题。学号学号姓名姓名性别性别入学总分入学总分01丁一丁一男男44002马二马二男男43503张三张三女女43804李四李四男男
2、43005王五王五女女44506赵六赵六男男42807钱七钱七女女43208孙八孙八男男43709冯九冯九女女42610郑十郑十女女435图1.1 学生入学情况登记示例图1.2 井字棋对奕问题示例图1.3 教学计划编排问题示例 （a）集合结构（b）线性结构（c）树型结构 （d）图形结构图1.4 四类基本结构的示意图数据元素之间的逻辑关系，称为数据的逻辑结构。数据元素之间的逻辑关系，称为数据的逻辑结构。一个数据的逻辑结构可以用二元组来表示：一个数据的逻辑结构可以用二元组来表示：G=(D,R)G=(D,R)其中：其中：D D是数据元素的集合；是数据元素的集合；R R是是D D上所有数据元素之间关系
3、的有限集合。上所有数据元素之间关系的有限集合。数据结构数据结构Line=Line=（D D，R R）其中其中:D=01,02,03,04,05,06,07,08,09,10 D=01,02,03,04,05,06,07,08,09,10 R=r R=r r=,r=,n1 1数据（数据（DataData）n2 2数据元素（数据元素（Data ElementData Element）n3 3数据项数据项(Data Item)(Data Item)n4 4数据对象（数据对象（Data ObjectData Object）n5 5数据逻辑结构（数据逻辑结构（Data StructureData Str
4、ucture）Tree=Tree=（D D，R R）其中其中:D=01,02,03,04,05,06,07,08,09,10 D=01,02,03,04,05,06,07,08,09,10 R=r R=rr=,r=,01020803070605040910图图1.5 树形结构树形结构graph=graph=（D D，R R）其中其中:D=D=a,b,c,d,ea,b,c,d,e R=r R=r r=r=（a,ba,b）,(,(a,da,d),),（b,db,d）,（b,cb,c）,（b,eb,e）,（c,dc,d）,（d,ed,e）badce图1.6 图形结构 n1 1顺序存储顺序存储n2 2
5、链式存储链式存储n3 3索引存储索引存储n4 4散列存储散列存储n1.1.数据类型（数据类型（Data TypeData Type）是一个值的集合和定义）是一个值的集合和定义在这个值集上的一组操作的总称。在这个值集上的一组操作的总称。n2.2.数据类型可分为两类：一类是原子类型，另一数据类型可分为两类：一类是原子类型，另一类则是结构类型。类则是结构类型。n3.3.抽象数据类型（抽象数据类型（AbstructAbstruct Data Type Data Type，简称，简称ADTADT）是指一个数学模型以及定义在该模型上的一组操作。是指一个数学模型以及定义在该模型上的一组操作。n1.1.算法特
6、性算法特性n2.2.算法要求算法要求n3.3.算法描述算法描述n4.4.算法性能分析与度量算法性能分析与度量n1 1有究性有究性n2 2确定性确定性n3 3可行性可行性n4 4输入输入n5.5.输出输出n1 1正确性正确性n2 2可读性可读性n3 3健壮性健壮性n4 4高效率高效率n5.5.低存储低存储n1 1自然语言自然语言n2 2流程图流程图n3 3N-SN-S结构图结构图n4 4伪代码伪代码n5.5.计算机语言计算机语言n1 1时间复杂度时间复杂度n2 2空间复杂度空间复杂度时间复杂度:是指程序运行从开始到结束所需要的时间。分析方法:从算法中选取一种对于所研究的问题来说是基本运算的原操作
7、，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。常见的渐进时间复杂度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)空间复杂度:是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分：固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。主菜
8、单主菜单u线性表（线性表（Linear ListLinear List）：是最常用且最）：是最常用且最简单的一种数据结构。简言之，一个线性简单的一种数据结构。简言之，一个线性表是表是n n个数据元素的有限序列。个数据元素的有限序列。n1 1表长表长n2 2空表空表n3 3直接后继直接后继n4 4直接前驱直接前驱n5.5.位序位序1.InitList(&L)1.InitList(&L)初始化表初始化表2.ListLength(L)2.ListLength(L)求表长求表长3.GetElem(L,3.GetElem(L,cur_ecur_e,&,&next_enext_e)取表中元素取表中元素 4
9、.LocateElem(L,e,compare()4.LocateElem(L,e,compare()定位。定位。5.ListInsert(&L,i,e)5.ListInsert(&L,i,e)插入元素插入元素6.ListDelete(&L,i,&e)6.ListDelete(&L,i,&e)删除元素删除元素u1.1.线性表的顺序存储结构线性表的顺序存储结构u2.2.基本运算在顺序表上的实现基本运算在顺序表上的实现 u3.3.插入和删除性能分析插入和删除性能分析n 线性表的顺序存储是指在内存中用地址连续的一块存储空线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素间顺序
10、存放线性表的各元素(顺序表顺序表)。n 地址关系地址关系:Loc(aiLoc(ai)=)=Loc(aLoc(a)+(i-1)+(i-1)*d 1Ind 1Inn 顺序表类型：顺序表类型：TypedefTypedef structstruct ElemTypeElemType *elemelem;/;/存储空间基址存储空间基址 intint length length；/当前长度当前长度 intint listsizelistsize；/当前分配的存储容量当前分配的存储容量 SqListSqList；n 1.构造一个空线性表算法n 2.线性表的的插入算法n 3.线性表的的删除算法Status I
11、nitList_Sq(SqList&L)/构造一个空线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;/空表长度为 0L.listsize=LIST_INIT_SIZE;return OK;/InitList_Sq 序号 元素 序号 元素 1 12 1 12 2 13 2 13 3 21 3 21 4 24 4 24 5 28 5 2525 6 30 6 28 7 42 7 30 8 77 8 42 9 77 (a)(b)图2.1 线性表插入前后的情况
12、 (a)插入前n=8;(b)插入后n=9。序号 元素 序号 元素 1 12 1 12 2 13 2 13 3 21 3 21 4 2424 4 25 5 28 5 28 6 30 6 30 7 42 7 42 8 77 (a)(b)图2.2 线性表删除前后的情况 (a)删除前n=8;(b)删除后n=7。顺序表上的插入运算，时间主要消耗在了数据的移动上，平均移动数据元素的次数：11)1(Eniiininp设：Pi=1/(n+1)，即为等概率情况，则：11112)1(11)1(Eniniiinninninp时间复杂度为(n)顺序表上的删除运算，时间主要消耗在了数据的移动上，平均移动数据元素的次数：
13、设：Pi=1/n，即为等概率情况，则：时间复杂度为(n)niideinp1)(E11121)(1)(Eniniideninninpu1.1.线性链表线性链表(单链表单链表)u2.2.循环链表循环链表 u3.3.双向链表双向链表n1 1链式存储结构的特点链式存储结构的特点 n2 2结点（结点（NodeNode）n3 3线性链表线性链表 n4 4头结点头结点 n1 1建立单链表建立单链表 n2 2查找查找 n3 3插入插入 n4 4删除删除 算法思想算法思想插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。具体步骤：具体步骤：（1）找到ai-1存储位置p（2）生成
14、一个数据域为x的新结点*s（3）新结点的指针域指向结点ai。（s-next=p-next）（4）令结点*p的指针域指向新结点(p-next=s)void ListInsert(LinkList head,int i,ElemType e,)p=head;j=0;while(p&jnext;+j;)if(!p|ji-1)return ERROR；s=(ListNode*)malloc(sizeof(ListNode);s-data=e;s-next=p-next;p-next=s;return OK；/ListInsert 时间复杂度亦为时间复杂度亦为O(nO(n)算法思想算法思想删除运算是将表
15、的第i个结点删去。具体步骤：具体步骤：（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）（2）令p-next指向ai的直接后继结点（即把ai从链上摘下）（p-next=p-next-next）（3）释放结点ai的空间，将其归还给存储池。(free(q)void ListDelete(LinkList head,int i)p=head;j=0;while(p-next&jnext;+j;if(p=NULL|p-next=NULL)return ERROR;/退出程序运行 q=p-next;/使q指向被删除的结点ai p-next=q-
16、next;/将ai从链上摘下 free(q);/释放结点ai的空间给存储池算法的时间复杂度也是算法的时间复杂度也是O O（n n）对于单链表而言，最后一个结点的指针域是空指针，对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。头尾结点相连，就构成了单循环链表。双（向）链表中有两条方向不同的链，即每个结点双（向）链表中有两条方向不同的链，即每个结点中除中除nextnext域存放后继结点地址外，还增加一个指域存放后继结点地址外，还增加一个指向其直接前趋的指针域向其直接前趋的指针域pri
17、orprior 特点：特点：1）双链表由头指针head惟一确定的。2）带头结点的双链表的某些运算变得方便。3）将头结点和尾结点链接起来，为双（向）循环链表。typedef struct DuLNode ElemType data;struct DuLNode*prior,*next;DuLNode,*DuLinkList;s-prior=p-prior;/s-next=p;/p-prior-next=s;/p-prior=s;/p-prior-next=p-next;/p-next-prior=p-prior;/free(p);/主菜单主菜单u1.1.栈的定义及相关概念栈的定义及相关概念u2.
18、2.栈的基本运算栈的基本运算 u3.3.栈的表示与实现栈的表示与实现n栈（栈（StackStack）：）：是限制仅在表的一端进行插入和删除运算的线性表。是限制仅在表的一端进行插入和删除运算的线性表。n1 1栈顶（栈顶（TopTop）n2 2栈底（栈底（BottomBottom）n3 3空栈空栈 n4 4LIFOLIFO表表 n5.5.退栈退栈 n6.6.进栈进栈 1.InitStack(&L)1.InitStack(&L)初始化栈初始化栈2.StackEmpty2.StackEmpty（S S）判栈空）判栈空 3.StackFull3.StackFull（S S）判栈满）判栈满 4.Push4
19、.Push（S S，x x）进栈）进栈 5.Pop5.Pop（S S）退栈）退栈 6.StackTop6.StackTop（S S）取栈顶元素）取栈顶元素 1 1、顺序栈的类型定义顺序栈的类型定义#define#define StackSizeStackSize 100/100/假定预分配的栈空间假定预分配的栈空间最多为最多为100100个元素个元素 typedeftypedef char char DataTypeDataType;/;/假定栈元素的数据类假定栈元素的数据类型为字符型为字符 typedeftypedef structstruct DataTypeDataType dataSt
20、ackSizedataStackSize;intint top;top;SeqStackSeqStack;2 2、顺序栈的进栈操作顺序栈的进栈操作进栈时，需要将进栈时，需要将S-S-toptop加加1 1注意：注意：S-S-top=StackSize-1top=StackSize-1表示栈满表示栈满 上溢上溢 现象现象-当栈满时，再做进栈运算产生空间溢出的现象。当栈满时，再做进栈运算产生空间溢出的现象。3 3、顺序栈的退栈操作顺序栈的退栈操作退栈时，需将退栈时，需将S-S-toptop减减1 1注意：注意：S-S-top0topdata=x;p-next=NULL;if(QueueEmpty(
21、Q)Q-front=Q-rear=p;/将x插入空队列 else /x插入非空队列的尾 Q-rear-next=p;/*p链到原队尾结点后 Q-rear=p;/队尾指针指向新的尾 QElemType DeQueue(LinkQueue*Q)QElemType x;QueueNode*p;if(QueueEmpty(Q)Error(Queue underflow);/下溢 p=Q-front;/指向对头结点 x=p-data;/保存对头结点的数据 Q-front=p-next;/头结点从链上摘下 if(Q-rear=p)Q-rear=NULL;free(p);/释放被删队头结点 return x
22、;/返回原队头数据 QElemType QueueFront(LinkQueue*Q)if(QueueEmpty(Q)Error(Queue if empty.);return Q-front-data;顺序队列是用内存中一组连续的存储单元顺序存放顺序队列是用内存中一组连续的存储单元顺序存放队列中各元素。所以可以用一维数组队列中各元素。所以可以用一维数组QMAXLENQMAXLEN作作为队列的顺序存储空间，其中为队列的顺序存储空间，其中MAXLENMAXLEN为队列的容为队列的容量，队 列 元 素 从量，队 列 元 素 从 Q 0 Q 0 单 元 开 始 存 放，直 到单 元 开 始 存 放，
23、直 到QMAXLEN1QMAXLEN1单元。因为队头和队尾都是活动的，单元。因为队头和队尾都是活动的，因此，除了队列的数据以外，一般还设有队首因此，除了队列的数据以外，一般还设有队首（frontfront）和队尾（）和队尾（rearrear）两个指针。）两个指针。Rear=0front=0 rear=5 rear=8 rear=10 front=0 front=5 front=5(a)(a)(b)(c)(d)为了克服顺序队列中假溢出，通常将一维数组为了克服顺序队列中假溢出，通常将一维数组queue0queue0到到qmaxsize-1qmaxsize-1看成是一个首尾相接的圆看成是一个首尾相接
24、的圆环，即环，即queue0queue0与与queuemaxsize-1queuemaxsize-1相接在一起。相接在一起。将这种形式的顺序队列称为循环队列将这种形式的顺序队列称为循环队列 。若若rear+1=rear+1=maxsizemaxsize,则令则令rear=0.rear=0.这样运算很不方便，这样运算很不方便，可利用数学中的求模运算来实现。可利用数学中的求模运算来实现。入队：入队：rear=(rear+1)mod rear=(rear+1)mod maxsizemaxsize;squeuerearsqueuerear=x.=x.出队：出队：front=(front+1)mod f
25、ront=(front+1)mod maxsizemaxsize.n 1.进队列算法（1）检查队列是否已满，若队满，则进行溢出错误处理；（2）将队尾指针后移一个位置（即加1），指向下一单元；（3）将新元素赋给队尾指针所指单元。n 2.出队列算法（1）检查队列是否为空，若队空，则进行下溢错误处理；（2）将队首指针后移一个位置（即加1）；（3）取队首元素的值。n 3.队列初始化front=rear=0;主菜单主菜单u1.1.串的定义及相关概念串的定义及相关概念u2.2.串的基本运算串的基本运算n 串串(string)(string)是由零个或多个字符组成的有限序列是由零个或多个字符组成的有限序列。
26、n 1.1.空串空串n 2.2.空白串空白串n 3.3.子串子串n 4.4.主串主串 1.1.strcpy(S,Tstrcpy(S,T)串复制串复制2.2.strcat(S,Tstrcat(S,T)串联接串联接3.3.strlenstrlen(T)(T)求串长度求串长度4.4.strsub(S,i,jstrsub(S,i,j,T),T)子串子串5 5 strcmp(S,Tstrcmp(S,T)串比较大小串比较大小6.6.index(S,Tindex(S,T)求子串位置求子串位置7.replace(7.replace(S,i,j,TS,i,j,T)串替换串替换u1.1.顺序串顺序串 u2.2.静
27、态存储分配的顺序串静态存储分配的顺序串 u3.3.动态存储分配的顺序串动态存储分配的顺序串 u4.4.串的链式存储串的链式存储 u5.5.串运算的实现串运算的实现 顺序串顺序串:串的顺序存储结构。串的顺序存储结构。与顺序表类似，顺序串是用一组地址连续的存储单元与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列。因此可用高级语言的字符来存储串中的字符序列。因此可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为数组来实现，按其存储分配的不同可将顺序串分为如下两类：如下两类：（1 1）静态存储分配的顺序串）静态存储分配的顺序串（2 2）动态存储分配的顺序串）动态存储分配的
28、顺序串直接使用定长的字符数组来定义直接使用定长的字符数组来定义该种方法顺序串的具体描述：该种方法顺序串的具体描述：#define#define MaxStrSizeMaxStrSize 256 256 /该值依赖于应用，由用户定义该值依赖于应用，由用户定义typedeftypedef char char SeqStringMaxStrSizeSeqStringMaxStrSize;/SeqStringSeqString是顺序串类型是顺序串类型SeqStringSeqString S;S;/S /S是一个可容纳是一个可容纳255255个字符的顺序串个字符的顺序串注意：注意：串值空间的大小在编译时
29、刻就已确定，是静态的。串值空间的大小在编译时刻就已确定，是静态的。难以适应插入、链接等操作难以适应插入、链接等操作直接使用定长的字符数组存放串内容外，一般可直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。所以串空间最大值为末尾来表示串的结束。所以串空间最大值为MaxStrSizeMaxStrSize时，最多只能放时，最多只能放MaxStrSize-1MaxStrSize-1个字符。个字符。顺序串的字符数组空间可使用顺序串的字符数组空间可使用C C语言的语言的mallocmalloc和和freefr
30、ee等动态存等动态存储管理函数，来根据实际需要动态地分配和释放。储管理函数，来根据实际需要动态地分配和释放。（1 1）较简单的定义）较简单的定义typedeftypedef char char*string;string;/C /C中的串库中的串库 相当于使用此类型定义串相当于使用此类型定义串（2 2）复杂定义）复杂定义typedeftypedef structstruct char char*chch;/若串非空，按实际的串长分配存储区，否则若串非空，按实际的串长分配存储区，否则chch为为NULLNULL intint length;length;HStringHString;1 1、链串
31、：用单链表方式存储串值，串的这种链式存储、链串：用单链表方式存储串值，串的这种链式存储结构简称为链串。结构简称为链串。2 2、链串的结构类型定义、链串的结构类型定义 typedeftypedef structstruct node node char data;char data;structstruct node node*next;next;LinkStrNodeLinkStrNode;/;/结点类型结点类型 typedeftypedef LinkStrNodeLinkStrNode *LinkStringLinkString;/LinkStringLinkString为链串类型为链串类型
32、 LinkStringLinkString S;/S S;/S是链串的头指针是链串的头指针u模式匹配即子串定位运算。设模式匹配即子串定位运算。设s s和和t t是给定的是给定的两个串，在主串两个串，在主串s s中找到等于子串中找到等于子串t t的过程称的过程称为模式匹配。其中被匹配的主串为模式匹配。其中被匹配的主串s s称为目标串，称为目标串，匹配的子串匹配的子串t t称为模式。称为模式。首先将首先将s1s1与与t1t1进行比较，若不同，就将进行比较，若不同，就将s2s2与与t1t1进行进行比较，直到比较，直到s s的某一个字符的某一个字符sisi和和t1t1相同，再将它相同，再将它们之后的字
33、符进行比较，若也相同，则如此继续们之后的字符进行比较，若也相同，则如此继续往下比较，当往下比较，当s s的某一个字符的某一个字符sisi与与t t的字符的字符tjtj不同不同时，则时，则s s返回到本趟开始字符的下一个字符，即返回到本趟开始字符的下一个字符，即si-j+2si-j+2，t t返回到返回到t1t1，继续开始下一趟的比较，继续开始下一趟的比较，重复上述过程。若重复上述过程。若t t中的字符全部比较完，则说中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是明本趟匹配成功，本趟的起始位置是ij+1ij+1，否，否则，匹配失败。则，匹配失败。主串主串s=“ABABCABCACBAB
34、”s=“ABABCABCACBAB”模式模式t=“ABCAC”t=“ABCAC”主菜单主菜单u1 1、一维数组（向量）是存储于计算机的连续存储空、一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。间中的多个具有统一类型的数据元素。u2 2、二维数组、二维数组二维数组二维数组AmnAmn可视为由可视为由m m个行向量组成的向量，或由个行向量组成的向量，或由n n个个列向量组成的向量。列向量组成的向量。u3 3、多维数组、多维数组三维数组三维数组AmnpAmnp可视为以二维数组为数据元素的向量。四可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量维
35、数组可视为以三维数组为数据元素的向量n 1 1、行优先顺序、行优先顺序将数组元素按行向量排列，第将数组元素按行向量排列，第i+1i+1个行向量紧接在第个行向量紧接在第i i个行向量个行向量后面。后面。例、二维数组例、二维数组AmnAmn的按行优先存储的线性序列为：的按行优先存储的线性序列为：a11,a12,a1n,a21,a22,a2n,a11,a12,a1n,a21,a22,a2n,，am1,am2,am1,am2,，amnamnn 2 2、列优先顺序、列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第i+1i+1个列向量紧接在第个列向量紧接在第i i个列向量个列向量后面。后面。
36、例、二维数组例、二维数组AmnAmn的按列优先存储的线性序列为：的按列优先存储的线性序列为：a11,a21,am1,a12,a22,am2,a11,a21,am1,a12,a22,am2,，a1n,a2n,a1n,a2n,，amnamn3 3、地址的计算、地址的计算1 1）按行优先顺序存储的二维数组）按行优先顺序存储的二维数组AmnAmn地址计算公式地址计算公式 LOC(aijLOC(aij)=LOC(a11)+(i-1)=LOC(a11)+(i-1)n+j-1n+j-1d d2 2）按列优先顺序存储的二维数组）按列优先顺序存储的二维数组AmnAmn地址计算公式地址计算公式 LOC(aijLO
37、C(aij)=LOC(a11)+(j-1)=LOC(a11)+(j-1)m+i-1m+i-1d d3 3）按行优先顺序存储的三维数组）按行优先顺序存储的三维数组AmnpAmnp地址计算公式地址计算公式 LOC(aijkLOC(aijk)=LOC(a111)+(i-1)=LOC(a111)+(i-1)n np+(j-1)p+(j-1)p+k-1p+k-1d d4 4）下界不为）下界不为1 1的二维数组的地址计算公式的二维数组的地址计算公式二维数组二维数组Ac1.d1,c2.d2Ac1.d1,c2.d2的地址计算公式：的地址计算公式：LOC(aijLOC(aij)=LOC(ac1c2)+(i-c1
38、)=LOC(ac1c2)+(i-c1)(d2-c2+1)+j-c2(d2-c2+1)+j-c2d d 下界为下界为0 0的二维数组的地址计算公式（的二维数组的地址计算公式（C C语言中使用）语言中使用）LOC(aijLOC(aij)=LOC(a00)+i)=LOC(a00)+i(d2+1)+j(d2+1)+jd du1.1.矩阵的二维数组描述矩阵的二维数组描述u2.2.矩阵的压缩存储矩阵的压缩存储u3.3.特殊矩阵特殊矩阵 u4.4.稀疏矩阵稀疏矩阵 n 矩阵用二维数组描述时，存储矩阵用二维数组描述时，存储的密度为的密度为1 1。可以对其元素进。可以对其元素进行随机存取，各种矩阵运算也行随机存
39、取，各种矩阵运算也非常简单。非常简单。n 矩阵中非零元素呈某种规律分矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元布或者矩阵中出现大量的零元素的情况下，为了节省存储空素的情况下，为了节省存储空间，我们可以对这类矩阵进行间，我们可以对这类矩阵进行压缩存储：即为多个相同的非压缩存储：即为多个相同的非零元素只分配一个存储空间；零元素只分配一个存储空间；对零元素不分配空间。对零元素不分配空间。n 1.1.对称矩阵对称矩阵n 2.2.三角矩阵三角矩阵n 3.3.对角矩阵对角矩阵n 1.1.对称矩阵中的元素关于主对角线对称，故只要存对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的
40、元素，让每两个对称储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的的元素共享一个存储空间。这样，能节约近一半的存储空间。存储空间。n 2.2.按按“行优先顺序行优先顺序”存储主对角线存储主对角线(包括对角线包括对角线)以以下的元素下的元素 n 3.aij3.aij和和saksak 之间的对应关系：之间的对应关系：若若ijij，k=ik=i(i+1)(i+1)2+j 0kn(n+1)2+j 0kn(n+1)2 2 若若i ij j，k=jk=j(j+1)(j+1)2+i 0kn(n+1)2+i 0kn(n+1)2 2 令令I=I=max(imax(i，j)
41、j)，J=J=min(imin(i，j)j)，则，则k k和和i i，j j的对的对应关系可统一为：应关系可统一为：k=ik=i(i+1)(i+1)2+j 0kn(n+1)2+j 0kn(n+1)22三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间，其余可共享一个存储空间，其余的元素正好有的元素正好有n n(n+1)(n+1)2 2个，因此，三角矩阵可个，因此，三角矩阵可压缩存储到向量压缩存储到向量sa0sa0n(n+1)n(n+1)22中，其中中，其中c c存存放在向量的最后一个分量中。放在向量的最后一个分量中。上三角矩阵中上三角矩阵中aijaij和和saksak 之间的对应
42、关系之间的对应关系 i i(2n-i+1)(2n-i+1)2+j-i 2+j-i 当当ijij k=k=n n(n+1)/2(n+1)/2 当当i ij j下三角矩阵中下三角矩阵中aijaij和和saksak 之间的对应关系之间的对应关系 i i(i+1)(i+1)2+j 2+j 当当ijij k=k=n n(n+1)/2(n+1)/2 当当i ij jn 一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。n 1.1.稀疏矩阵稀疏矩阵n 2.2.三元组顺序表三元组顺序表 n 3.3.十字链表十字链表 n 设矩阵设矩阵AmnA
43、mn中有中有s s个非零元素，若个非零元素，若s s远远小于矩阵远远小于矩阵元素的总数元素的总数(即即ssm mn n)，则称，则称A A为稀疏矩阵。为稀疏矩阵。n 为了节省存储单元，可只存储非零元素。由于非为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。取功能
44、。n 其中每一个非零元素所在的其中每一个非零元素所在的行号、列号和值行号、列号和值组成组成一个三元组一个三元组(i(i，j j，aijaij)，并由此三元组惟一确，并由此三元组惟一确定。定。n 用十字链表表示稀疏矩阵的基本思想是：对每个非零元素存储为一个结点，结点由5个域组成，其结构如图表示，其中：row域存储非零元素的行号，col域存储非零元素的列号，v域存储本元素的值，right，down是两个指针域。u广义表：是广义表：是n(n0)n(n0)个元素个元素a1a1，a2a2，aiai，anan的有限序列。的有限序列。广义表通常记作：广义表通常记作：GL=(a1GL=(a1，a2a2，aia
45、i，an)an)。u1.1.基本概念基本概念u2.2.广义表表示广义表表示u3.3.广义表运算广义表运算n 1.1.原子原子n 2.2.子表子表n 3.3.长度长度n 4.4.深度深度n 5.5.表头表头n 6.6.表尾表尾n 1.1.广义表常用表示广义表常用表示 n 2.2.带名字的广义表表示带名字的广义表表示 n 3.3.广义表的图形表示广义表的图形表示 E=()E是一个空表，其长度为0。L=(a，b)L是长度为2的广义表，它的两个元素都是原子，深度为1。A=(x，L)=(x，(a，b)A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L，深度为2。B=(A，y)=(x，(a，b)
46、，y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y，深度为3。C=(A，B)=(x，(a，b)，(x，(a，b)，y)C的长度为2，两个元素都是子表，深度为4。D=(a，D)=(a，(a，(a，()E()L(a，b)A(x，L(a，b)B(A(x，L(a，b)，y)C(A(x，l(a，b)，B(A(x，L(a，b)，y)D(a，D(a，D()图中的分支结点对应广义表 非分支结点一般是原子 但空表对应的也是非分支结点。由于广义表中的数据元素可以具有不同的结构，因此难以由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵用顺序的存储结
47、构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个结点表示。数据元素可用一个结点表示。u1.1.头尾表示法u2.2.孩子兄弟表示法表结点、原子结点表结点、原子结点typedeftypedef emnuATOM,LISTemnuATOM,LIST ElemTagElemTag;typedeftypedef structstruct GLNodeGLNode ElemTagElemTag tag;t
48、ag;unionunionAtomTypeAtomType atom;atom;structstructstructstruct GLNodeGLNode *hp,hp,*tp;ptrtp;ptr;：*GlistGlist；u在孩子兄弟表示法中，也有两种结点形式：一种是有在孩子兄弟表示法中，也有两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结
49、点中包括一个指向兄弟的指针和该元素的元素孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为标志域。如果标志为1 1，则表示该结点为有孩子结点；，则表示该结点为有孩子结点；如果标志为如果标志为0 0，则表示该结点为无孩子结点。，则表示该结点为无孩子结点。主菜单主菜单u1.1.树的定义树的定义u2.2.基本术语基本术语u3.3.树的表示树的表示树树(Tree)(Tree)是是n(n0)n(n0)个结点的有限集个结点的有限集T T，T T为空时称为空树，为空时称为空树，否则它满足如下两个条件：否
50、则它满足如下两个条件：(1)(1)有且仅有一个特定的称为根有且仅有一个特定的称为根(Root)(Root)的结点；的结点；(2)(2)其余的结点可分为其余的结点可分为m(m0)m(m0)个互不相交的子集个互不相交的子集TlTl，T2T2，TmTm，其中每个子集本身又是一棵树，并称其为，其中每个子集本身又是一棵树，并称其为根的子树根的子树(SubreeSubree)AACGBDEFKLHMIJn 结点：包含一个数据元素及若干指向其子树的分支结点：包含一个数据元素及若干指向其子树的分支n 结点的度：结点拥有的子树数结点的度：结点拥有的子树数n 叶结点：度为叶结点：度为0 0的结点的结点 没有子树的
