东北大学数据结构

数据结构考研辅导材料考者能同学们，2007年考研专业课的辅导开始了。为使大家在准备过程中少走弯路，取得事半功倍的效果。首先我给大家谈几点意见，供同学们参考。一基本概念二基本结构的算法描述方式:顺序;链表;串;树;图.三基本操作类型:建立;查找；移动;插入;删除;合并;倒置;连接理解逻辑概念与物理表示之间的对应（或转换）关系学会把逻辑描述用形式语言实现的方法要求你们:深刻理解基本概念；熟练掌握基本结构；灵活运用基本算法绪论基本概念：一、数据与数据结构1、数据在计算机科学领域，凡是计算机能识别与处理的数字、符号、图形（象）、语音以及它们的汇集通称数据。2、数据结构数据本身以及数据与数据之间的关系。在数据处理时，为了用户存取、查找、修改、更新、插入、删除等操作方，对系统中提供的原始数据必须进行加工与组织，而经过人们加工得到的数据型式称为数据结构。它是一种抽象的逻辑结构（logicalstructure）=Data-Structure=（D,S）D是数据元素的有限集合；S是D上关系的有限集。计算机科学领域常用的四种基本的数据结（1）集合结构数据元素之间没有固定关系。（2）线性结构数据元素之间有一对一应关系。

（3）树型结构数据元素之间有一对多的关系。（3）树型结构数据元素之间有一对多的关系。二、存储结构存储结构是数据结构在存储介质上的具体表现形式。数据结构与存储结构关系举例例如原始数据：9,7,4,5,3,6,1,2,8,0数据结构：0』,2,3,4,5,6,7,8,9顺序存储01 2 3 4 5 6 7 89链式存储顺序存储01 2 3 4 5 6 7 89链式存储数据结构与存储结构的关系：1）一种数据结构可以对应多种存储结构。但是，在一个系统中一种数据结构只能使用一种存储结构。2）存储结构在表现形式上可以与数据结构相同，也可以不同。但是，它们都必须能准确无误地保证原数据结构的逻辑关系。两种基本的存储结构1、顺序存储顺序存储是按照数据结构中元素的顺序把数据依次存储到地址连续的存储区间。特点：1）必须预知最大空间量。2）每个数据元素都占用相同的存储单元。3）逻辑上相邻的元素，它们在存储介质上的物理位置一定相邻。4）在任意位置上的插入与删除元素浪费时间。5）可以随机查找。2、链式存储是按照数据结构中元素的顺序把数据依次存储到任意的地址单元.特点：1）可用任意空闲地址单元实现对线性表的存储：2）线性表中元素的逻辑关系，是用指针来保证的；3）在任意位置上插入与删除数据元素方便：4）在单链表中查找数据只能用顺序查找方式：5）空间利用率比顺序存储低；3、抽象数据类型（abstractdatatype,ADT）是指一个数学模型以及定义在该模型上的一组操作.其定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关,即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用.一般用三元组表示：（D,S,P）D数据对象;S是D上的关系;P是对D的基本操作.格式定义：ADT抽象数据类型名{数据对象：（数据对象的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义））基本操作名（参数表）初始条件：（初始条件描述）操作结果:（操作结果描述）例，抽象数据类型三元组的定义：ADTTriplet{数据对象：D={el,e2,e3|el,e2,e3GElemset}（定义了关系运算的集合）数据关系:Rl={<el,e2>,<e2,e3>}（数据关系的定义）基本操作：（InitTriplet（&T,vl,v2,v3）结果把el,e2,e3分别赋给参数vl,v2,v3。DestroyTriplet（&T）结果三元组T销毁. cneraticns dataGet（T,i,&e）初始条件:三元组T存在,l《iW3;in操作结果:用e返回T的第i元的值.InittripletPut（&T,i,e,）初始条件:三元组T存在，1Wi<3;getoTripietL操作结果:改变T的第i元的值为e.putoeiernMax（T,&e）初始条件:三元组T存在；maxrposition操作结果:用e返回T的3个元素中的最大值.desMin(T,&e)minrerror初始条件:三元组T存在；操作结果:用e返回T的3个元素中的最小值.}ADTTriplet三、算法的时间复杂度与空间复杂度1算法的定义:算法是对某类特定问题求解步骤的描述.它应满足下列特性：(1)有零个或多个输入量；(2)每一步都有唯一确定的含义；(3)至少有一个输出量；(4)执行有限步后自动停止；(5)能用现有的程序语言实现编程上机运行；2算法的描述方式自然语言；流程框图；伪形式语言(pascal,c,C++)3算法的时间复杂度*程序时间复杂性的计算一个程序P,所占用的时间T(P)=编译时间+运行时间。编译时间与程序的特征无关。因此主要讨论程序的运行时间，运行时间通常用TP表示。令n代表程序的特征(即对程序时间有影响的参数)。那么，TP的计算公式为：TP(n)=ClADD(n)+C2SUB(n)+C3MUL(n)+C4DIV(n)+-其中，Cl、C2、C3、C4分别表示，一次加、减、乘、除操作所需的时间。函数ADD(n)、SUB(n)>MUL(n)、DIV(n)分别表示程序P中，所使用的加、减、乘、除操作的次数。在应用中大都是估算运行时间。估算的方法往往用所有操作之中，最多的操作次数，作为该程序的时间复杂性。算法的时间相当于程序时间中的运行时间部分。同样，关键操作的次数对时间复杂性的影响最大。假设，算法中关键操作执行的次数是问题特征(规模)n的某个函数f(n)。那么，算法的时间量度(复杂性)记作：T(n)=O(Rn))它表示随问题特征n的增大，算法中关键操作执行次数(时间)与f(n)也增大，而且算法中关键操作执行时间的增长率和f(n)的增长率相同。所以称f(n)为算法的时间复杂性。算法中语句操作执行的次数又称为频度.在实际中，用算法中语句的最大频度，作为算法的时间复杂性。4算法的空间复杂度算法的空间相当于程序所需空间中的可变空间部分SP。所以，算法所需空间的量度记作： S(n>O(f(n))其中N为问题特征。表示除输入和程序之外所需的额外空间。四、关于算法时间在考试中的类型：1,给定一个算法，估算其时间复杂度;时间与空间的关系.2,给定两个算法，比较它们的语句最大频度及时间复杂度；3,限定算法时间复杂度，编写完成功能的算法；例如，设计用时间复杂度为。(n)级的算法，完成稀疏矩阵的转置阵.StatusTransposeMatrixM,TSMatrix&T)(//M为原阵T为转置T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){ 〃存在非零元素

q=1； 〃转置矩阵T的下标初值for(col=l;col<=M.nu;++col)//从M阵的第一列开始查找for(p=l;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].v=M.data[p].v;++q；}returnOK;}算法的时间复杂性为O(nu*tu).若用其求m*n矩阵的转置阵算法的时间复杂性为O(m*n*n).StatusFstTransposcSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T,tu=M.tu;if(T.tu){for(col=l;col<=M.nu;-H-col)num[col]=0;〃置初值，清空for(t=l;t<=M.tu;-H-t)++num[M.data[t].j];//计算每列非零个数copt=l; //得到第一列中第一个非零元素的位置for(col=2;col<=Mnu;—col)〃算每歹ij中第一个元素在T中的序号cpot[col]=cpot[col一11+num[col-1];for(p=l;p<=m.tu;++p){col=M.data[p].j;q=cpot[col];//当前列第一非零元素地址Tdata[q].i=M.data[p].j;T.data[q].j=M.dara[p].i;T.data[q].v=M.data[p].v;-H-cpot[coI];}fbr}ifReturnOK;}该算法的时间复杂度为O(n)或O(m). cc-ccuperaiion第二部分线性表的顺序存储cenlefI一、线性表的顺序存储线性表的定义：有限序列1第二部分线性表的顺序存储cenlefI一、线性表的顺序存储线性表的定义：有限序列1、线性表的抽象数据模型线性表(al,a2,a3,…・an)的数据结构：LinearList=(D,R)其中，D={aiIai£D0,i=l,2,3.n,n=0}priornextretrieveupdatafind

InsertrdeletelocateR={N},N={<ai-l,ai>Iai-l,aieD0i=2,3,…,n}。DO为某个数据对象。2、顺序存储的实现在高级程序语言中，一般都用数组来描述顺序存储。在C语言中可用动态分配的一维数组描述如下。defineLIST_INIT_SIZE100//初次分配用户预估空间量defineLISTINCREAENT10〃每次分配增量，一个元素占Typesetstruct{ 〃用空间量ElemType*elem;//数组指针表的基址intlength;//当前长度，实际已存元素个数intlistsize;//任何时刻能存最多元素个数}SqList;空间量=最多元素个数*每次分配增量(每个元素占用空间量)。3、顺序存储上的运算1)查找--随机查找随机查找是利用下面两个计算公式计算所要求元素物理地址.A)已知要查找元素的逻辑地址号.逻辑地址(相对地址)是元素的位置序号；物理地址是元素在存储介质上真正的存储地址.逻辑地址号转换成物理地址的公式：LOC(ai)=LOC(aO)+i*L(L>=1)i为元素在存储空间的位置序号(逻辑地址，i从0开始)。BF赞1要查找元素在表中的下标号.由元素的下标号计算物理地址的公式：LOC(ai)=LOC(al)+(i-l)*L(L>=1)i为元素在表中数据ai的下标.(i从1开始)注： L为每个元素占有的存储单元数(增量)举例：有线性表(al32a3a4...am),求元素a3的物理地址;在表中该元素的下标是3,所以根据公式：LOC(ai)=LOC(al)+(i-l)*L(L>=1)有LOC(a3)=LOC(al)+(3-l)*L(L>=1)=99+2*1=101又a3在内存的逻辑地址是2,所以根据公式：LOC(ai)=LOC(aO)+i*L(L>=1)有LOC(a3)=LOC(aO)+2*L(L>=1)=99+2*1=101涉辑地址.0 1 2 3 m-1ala2a3a4am物理地址 ►99100101 102103... ....2)顺序查找条件：不知要查找元素的逻辑地址和其在表中的元素下标，已知要查找元素的值和表的长度.只能从表的一端开始逐一比较.StatusListSearch-Sq(SqList&L,inti,EIemTypee){i=l;(i为线性表元素的下标)While(i<=L.length&&L.elem[i-1]<>e)i++；if(i>L.length)returnERROR;elseretum(i・1);该算法的时间复杂度为O(n)。} 查找的有效范围是0——length-10 1 2 3 ・・・ ・・・length-1ala2a3a4an问题：若要求时间复杂度不变，而要提高该算法的运算速度，应如何修改该算法？为提高实际查找速度，1)查找的有效范围改为1—length；2)将控制循环查找的两个条件去掉一个；3)引入辅助单元(0单元作为辅助空间)。其算法如下：StatusListSearch-Sq(SqList,&L,key,Typekey){L.elem[0]=key;〃将被查数据存放到0单元i=length;〃查找起始位置为高端While(!EQ(L.elem[i].key,key)〃循环查找■・i；if(i<l)returnERROR;〃超处查找范围查找失败returni; 〃查找成功}Search-seq0 1 2 3 4 lengthcabcd•・・n3)插入运算(1)在给定表中查找插入位置.(顺序或结合其他查找方式)(2)移动相关数据为新数据准备空间.(3)插入新数据.(4)修改当前长度.例题知线性表顺序存储，设计算法查找一个值为X的元素，若不存在将新元素X插入到表的首部;若存在将其删除.StatusListInsert-Sq(SqList&L,inti,ElemenTypee){i=l；(i为逻辑线性表的下标)While(i<=L.length&&L.elem[i-1]<>x)i++；if(i<L.length)p=&(L.elem[i-1]);〃P要被删除数据的地址x=*p; //把删除的数据放到x中q=L.elem+L.length-1; 〃需移动的最后数据的位置for(++p;p<=q;-H-p)*(p-l)=*p； 〃移动数据--L.length; //长度减1returnOK;}Else{if(L.length>=L.listsize){ 〃预定义空间用完newbase=(ElemType*)realloc(L.elem,(L.listsize+LlSTINCREMENT)*sizeof(ElemType));

//动态再分配if(inewbase)exit(OVERFLOW);//动态再分配if(inewbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}ifq=&(L.elem[i-l]);for(p=&(L.elem[L.length-1]);p>=q;—p)*(p+l)=*p；*q=x;++L」ength;returnOK;}〃再分配失败〃新基值〃增加存储容量//保存插入位置//移动相关数据为新数据插入准备空间//插入新数据//长度增加1}（i为逻辑线性表元素的卜标与该元素的逻辑地址差1）4）删除运算条件：删除表中第i个元素StatusListDelete-Sq(SqList&L,int,ElemType&x){if(L.length=0)returnERROR;if((i<l)〃(i>L.length))returnERROR;p=&(L.elem[i-1]);〃P要被删除的位置x=*p; //把删除的数据放到x中q=L.elem+L.length-1; //需移动的最后数据的位置❖ for(++p;p<=q;-H-p)*(p-l)=*p;//移动数据--L.length; //长度减1returnOK;❖(i为逻辑线性表元素的下标与该元素的逻辑地址差1)例题顺序存储，且元素递增有序.，若不存在插入，保持原序;若存在删除.(要求省时间)voidInsertSq-list(SqList&L){low=0;high=L.Iength-l;while(low<=high){ //在子表中查找插入位置m=(low+high)/2;ifeq(x,Lelem[m]){for(j=m+l;j>=L.length-L.elem[j-1]= 删除L.length=L.length-l;}elsehigh=m-l;//插入点在低半区elselow=m+1;}whilefor（j=L.length-l;j>=high+l;-j）L.elem[j+1]=L.elemfj];〃记录后移L.elem[high+1]=x;//插入L.length=L.length+l;}设有N个大小不等的数据组，顺序存放在空间区D内，总占用空间量为m,每个数据占有一个存储单元.编写将元素X插到第i个数据组末尾且属该于数据组的算法.（15）1）若第i（i=n）个数据组直接插入。修改S[i]的长度。2）i《》n从数据组1开始查找i,然后移动相关数据，为新元素插入准备位置，修改S[i+1]到S[n]数据绢地址与Sfil的长度。

L.lengthL.lengthvoidinsert-x(sqlist&L,inti,ElemTypex){If(i>=l&&i<=L.length){for(j=0,p=L.elem[j];j<=m;j-H-)//p=L.elem[j]不是空闲单元继续查找p++; 〃求D区空闲空间的首地址if(i=L.length)//插入第n个数组，即最后一个。*p=x; //直接插入，不用修改else{ 〃插入第N个数组前）位置fbr(q=L.elem[i];p>=q;-p)//q=L.elem[i]第i）位置*(p+l)=*p; 〃将(p・l)位置数据移到(p*p=X;//插入，修改从第[i+1]个数据组开始到S[n]数据组地址for(q=&L.elem[i],p=&L.elem[L.length-l];p>=q;q~H~)〃后边位置加1(*qM;}mH;}例题知顺序存储,且数据元素递增有序.设计算法查找值为X的元素，若存在与直接前驱元素交换.若不存在将X插入,仍保持原序;.(要求省时间)voidInsertSq-list(SqList&L){low=0;high=L.length-1;while(low<=high){ //在子表中查找插入位置m=(low+high)/2;ifeq(x,Lelem[m]){if(m=l)exit;else{temp=L.elem[m];〃直接前驱元素交换L.elem[m]=L.elem[m+1];L.elem[m+1]=temp;}}elsehigh=m-l;//插入点在低半区elselow=m+1;}whilefor(j=L.length-l;j>=high+1;—j)L.elem[j+1]=L.elem[j];//记录后移L.elem[high+1]=x;//插入

L.length=L.length+l;例：编写把从线性表(ala2a3…an)中值为X的元素开始到an的所有元素顺序倒置的算法。从a5=e开始到a9=I0123 4 5 6 7 8倒置前abcdefghiabcdihgfe0 1 23 4 5 6 7 8倒置后for(i；iW[i+n]/2){an-1+1temp=l.element[i-1]；an-1+1l.element[i-l]=l.element[n-i+4]；l.clement[n-i+l]=temp}倒置类型题：1编写把线性表(ala2a3…an)的顺序完全倒置的算法。并计算该算法的时间复杂性及决定时间复杂性的语句频度。与后面章中有联系的问题：二叉树的顺序存储;图的顺序存储;查找;排序第三部分链表**基本概念与术语一、结点(node)线性表中一个数据元素所占用的存储空间。它由数据域与指针域两部分组成，数据域用来存储用户的有用数据；指针域用来存储直接前驱或直接后继数据元素所在结点的地址.1、含有一个直接后继数据元素指针域的结点数据域指针域p n数据域指针域p n ►datanexttypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;2、含有两个指针域的结点.一个直接前驱结点指针域，一个直接后继结点指针域.在C语言中可用结构指针来描述结点：prioudatanext前驱指针域数据域 后继指针域TypedetstructDuLNode{ElemType data;前驱指针域数据域 后继指针域structDuLNode*priou;structDuLNode*next;}DuLNode,*DuLinkList;二、单链表:

如果，构成链表的每个结点都只含有一个指针域，那么称这个表为单链表.1、不带头结点单链表；不带头结点的单链表的标准形式：不带头结点的单链表的空表标准形式:H=NULL.2、带头结点单链表的标准形式.首部结点C6A］尾结点带头结点的空单链表标准形式.L->next=NULL首部结点C6A］尾结点带头结点的空单链表标准形式.L->next=NULL三、循环单链表：1、不带头结点的循环单链表;四、双向链表（循环，不循环）1、不带头结点的循环双向链表;（略）2、带头结点循环双向链表；空表结构**基本运算和例题一、单链表的插入运算1,首部插入（生成结点，插入结点）2,尾部插入（查找尾部结点，生成结点，插入结点）3,条件插入（查找条件结点,保存前驱结点，生成结点，插入结点）将y插入到将y插入到x之前Statusinsert-list(){Statusinsert-list(){p=h;ifp=nullreturnERROR;if(p->data<>x&&p->next<>null){q=p->next;while(q->data<>x&&q->next<>null){P=q；q=q->next;}}ifl(q->data=x)s=(LinkList)malloc(sizeofifLNode))s->data=y;Statusinsert-list(){P=L;q=p->next;while(q->data<>x&&q->nextonull){P=q;q=q->next;}if(q->data=x)s=(LinkList)malloc(sizeof(LNode))；s->data=y;s->next=p->next;P->next=s;s->next=p->next;P->next=s;）二、单链表的删除运算1,首部删除（结点，释放结点）.2,尾部删除（查找尾部结点，保存前驱结点,释放结点）.3,条件删除（查找条件结点，保存前驱结点,释放结点）.

三、循环单链表的插入与删除:可以从表中任意已知地址查遍全表例题：Josephus问题:n个人围成圆圈，从第s个开始计数到m,便将其删除，从下一个开始，重复上述过程,直到所有人都删除.Statusinsert-list(L){(不循环)Statusinsert-list(L){(不循环)P=L;q=p->next;while(q->data<>x&&q->nextonull){P=q;q=q->next;}if(q->data=x)s=(LinkList)malloc(sizeofi(LNode))s->data=y;s->next=p->next;P->next=s;Statusinsert-list(Lc){P=Lc;q=p->next;(循环)

while(q->data<>x&&q->nextoLc){

P=q;q=q->next;}

if(q->data=x)

s=(LinkList)malloc(sizeof(LNode))；

s->data=y;s->next=p->next;P->next=s;Av为可用链表,lc为一数据无用的循环链表,要求用最少的时间把1c表与Av为可用链表,lc为一数据无用的循环链表,要求用最少的时间把1c表与Av连接在一起.LcAv=pav(1)建立一个含有n个结点的循环单链表jos・clist.#definefalse0#definetrue1(2)从第s个开始查找，输出和删除m#definefalse0#definetrue1{PNodep,q;(构成循环链表)IntI;Typedefintdatatype;StuctNode;TypedefstuctNodepelist=p->link;PNode;pelist=p->link;StuctNode{datatypeinf;PNodelink;}；TypedefstuctNode*LinkList;Intinit_clink(PLinklistpclist,int,n)voidJosephus(PLinkIistpelist,ints,intm){PNodep,pre;intI;p=*pelist;if(s=l){pre=p;p=p->link;While(p!=*pelink){pre=p;p=p->link;})elsefbr(i=l;i<s;i-H-){pre=p;p=p->link;}While(p!=p->link){fbr(i=l;i<s;i++){pre=p;p=p->link;}prineflfUoutelement:p->infb)if(*pelist=p)q=(PNode)malloc(sizeof(stuctNode));Ifi(q=null)return(false);*pclist=q;Q->inf=1;q->link=q;If(n=l)return(true);For(i=2;i<n+l;i++){p=(PNodc)malloc(sizeofl(stuctNode)):Ifi(p:=null)return(false);p->inf=l;p-<link=q->link;q->link=p;q=pj/尾部插入)Pre->link=p->link;Free(p);p=Pre->link;}prinef(<4outelement:p->infb);*pelist=nullFree(p);)主程序Mia(){linklistjos-clist;intn,sm;Printfi("input"n);Scanfi(&n);Printf("input”s);Scanf(&s);PrintR“input"m);Scanfi(&m);Ifi(init-clink(&jos-clist,n))Josephus-clink(&jos-clist,s,m);Else print出“outofspace");四、循环双向链表上的操作1、循环双向链表上的插入2、循环双向链表上的删除插在P的后 插在P的前S->next=p->next; S->priou=P->priou;S->priou=p; S->next=p;P->next->priou=s; P->priou->next=s;P->next=s; P->priou=s;P为双循环链表中任意一结点地址，设计用最少的辅助空间将P与其直接后继结点交换的语句P->next->priou=p->priou;(1)P->priou->next=p->next;(2)p->priou=P->next;(3)例题：1、假设AB为按元素值递增排列的单链表.编写算法将AB归并成一个按元素值递减的C表(C中可以有相同元素;没有相同元素).1)AB保留，生成C表;2)AB不保存，用其空间生成C表.LB 1 _叵卫~卜30|_:0|八算法描述：(1)设定A为C表.并将其倒置.(2)qa,qb分别为两表中当前结点指针.(3)当qa,qb都存在时重复：比较qa,qb结点数值，若qa<qb,将qb插到C表之前.若qa=qb,将qaqb分别插到C表之前.(4)当qa空时，把qb剩余逐个插到C表之前；(5)当qb空时，把qa剩余逐个插到C表之前；算法LA —> —► —► ——► 7\LB —卜21I-I150八voidmrege(linklist&pajinklist&pb){Lc=la;〃A表作为结果表qa=la・>next;〃第一个结点lc->next=null;//结果表置空qb=lb->next;while(!qa){//A表倒置ra=qa->next;qa->next=lc->next;lc->next=qa;qa=ra;}qa=lc->next;pre=Lc;while(!qb){while(qa->data>qb->data&&qa->next)//qa的数大{pre=qa;qa=qa->next;}if(qa->next=null){u=qb->next;qb->next=qa->next;qa->next=qb;qb=u);}if(qa->data<=qb->data)//qa的数值小,qb前插入{u=qb->next;qb->next=pre->next;pre->next=qb;pre=qb;qb=u;)}例2知A,B,C为三个单链表数据递增有序，要求对A作如下处理:删除与BC中相同的数据；vioddelet(linklist&la){pa=la;qa=la->next;qb=lb->next;qc=lc->next;while(!qc&&qb->data<>qc->data&&!qb){〃找出BC中所有相同元素qb=qb->next;

if(qb->data=qc->data){qb=qb->next;〃修改qb〃并删除while(!qa&&qa・>dataoqc・>data)〃找出C中A中所有相同元素〃并删除{pa=qa;qa=qa->next;}if(qa->data=qc->data){pa->next=qa->next;free(qa);qa=pa->next;}}qc=qc->next;〃修改3、（12分）假设一个有向图G已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环（回路）的算法。解：对十字链表储存结构的有向图采用拓扑排序Statustoposort（OLGraphG）{findindegree(G,indegree);InitQueue(Q);Count=0;fbr(i=O;i<G.Vemum;i-H-)ifi(GVer[i].indegree=O)Enqueue(Q,i);findindegree(G,indegree);InitQueue(Q);Count=0;fbr(i=O;i<G.Vemum;i-H-)ifi(GVer[i].indegree=O)Enqueue(Q,i);While(!QueueEmpty(Q))Dequeue(Q,i)；Count-H-；P=Gver[i].firstout;while(p)(j=pfheadvex;〃对各顶点求入度〃队列初始化〃计数器初始化〃入度为零的顶点入队〃队头出队〃取邻接点〃处理邻接点的入度Gver[j].indegree—Gver[j].indegree—;ifi(Gver[j].indegree==O)Enqueue(Qj);〃顶点j入队p=pftlink;//指针后移}//while}//whileif((count<G.vemum)returnERROR;//有环elsereturnOK;elsereturnOK;}//toposortStatusfindindegree(G,indegree){(根据十字表计算每个顶点的入度数填到入度域)Count=0；fbr(i=O;ivG.Vemum;i++){〃循环p=G[i]oFirstin//while(p!=null)

{count=count+l；p=p-*next；}whileG[i]Indegree=count；}for}双向循环链表Id为表头结点地址LDsLDsviodchang-f(linklist&ld){(按使用频度大小排列)q=ld->next;q->freq=0;While(q->priou<>ld) 〃置所有频度初值{q->ferq=O;q=q->next;}scanfifx);while(x<>0){LOCATE(L,X))q->freq=q->freq+l;p=q->priou;while(pold&&p->freq<q->freq)p=p->freq;if(!(p->freq<q->freq)){q->next->priou=q->priou;q->priou->next=q->next;q->next=p->next;q->priou=p;p->next->priou=q;p->next=q;}scanf(x)）；}十字链表静态链表其构成：是按顺序方式分配空间，是由用户自己构造的结点来形成的一种链表。其结构类型说明如下：#defineMAXSIZE100 〃所需的最大空间量//初始备用空间链//初始备用空间链typedefstruct{ElemTypedata;//数据域intcur; 〃指针域}component,SLinkList[MAXSIZE];voidInitspace_SL(SLinkList&space){for(i=0;i<MAXSIZEspace[i].cur=i+1;space[MAXSIZE-l].CUR=0;}Initspace_SL由由图可以看出space[0].cur=1;〃第一个空闲结点space[l].cur=2;space[2].cur=3;space[3].cur=4;space[4].cur=5;space[6].cur=7;space[7].cur=0备用链上的删除运算(把一个结点分配给用户)当用户申请一个结点时，下边的算法就把备用链中的第一个空闲结点分配给用户。IntMallocSLfSLinkList&space){i=spacc[O].cur;if(space[0].cur)space[0].cur=space[i].cur;returni;}MallocSL备用链上的插入运算 把用户释放的一个结点返回备用链供用户再次使用。voidFree_SL(SLinkList&space,intk){space[k].cur=space[0].cur;space[0].cur=k;//采用首部插入}Free_SL假设集合A=(c,b,egf,d);B=(a,b,n,f),那么(A・B)U(B-A)为(c,e,g,d,n,a).0809备用链为0,6,9,10,llo数据链头指针备用链表为212C32c4343n88,9,10,11共有4个空闲单元。-4e5-1eb数据链表5g65g7为：2,4,6f76f95,7,3,数据链表为：r2,3,4,5,6,7共有6个数据结点。一1d0r下d38o共有6个数据结点898a09109101011101111()110图2-14集合Avoiddifference(SLinkList&space,int&s){InitSpacc_SL(spacc);

s=Malloc_SL(Space);r=s;scanffm,n);for(j=s=Malloc_SL(Space);r=s;scanffm,n);for(j=l;j<=m;++j){i=MallocSL(space);scanf(space[i].data);space[r].cur=i;r=i;space[r].cur=0;for(j=l;j<=n;++j){//R指向最后结点//输入A和B的元素个数//建立集合A的链表//分配结点//输入A的元素值//插入到表为尾//尾结点的指针为空//输入B的元素在表A中查找是否存在scanfifb);p=s;k=space[s].cur;//k指向A的第一个结点，P为前驱while(k!=space[r].cur&&space[k].datd!=b){//在当前表中找p=k;k=space[k].cur;}if(k=space[r].cur){〃表中没有该元素，插在r所指点后r位置不变i=MallocSL(space);space[i].data=b;space[i].cur=space[r].cur;space[r].cur=i}ifelse{ //该元素在表中，删除space[p].cur=space[k].cur;free_SL(space,k)if(r=k)r=p; 〃若删除的是尾元素，则修改尾指针}else}for}defference注r位置后边的元素都是B表中插入的元素，不用比较所以r不用改。单链表倒置.L 卜〃iTa12Hb =倒置前后一］十d倒置前后实现算法如下:statusListReverse_L(LinkList&L){P=L->next;〃保存第一个结点L->next=NULL;//将原表置成空表While(p){s=p->next;//保存直接后继p->next=L・>next;〃首部插入L->next=p;P=s；}returnOK;

}该算法是达到同样要求的所有算法中利用辅助空间最少的一个。俩表合并A=x+2x2-4x3+3x4B=2+3x+4x3-x$A=((1,1),(2,2),(-4,3),(3,4))；B=((2,0),(3,1),(4,3),(-1,5))；PaPbPaPb多项式各项生成的单链表假设La,Lb分别为两个单链表的头结点指针，m,n分别为两表的长度。要求把两表联接成一个表(需要较少的时间)。实现算法如下：voidUnionList_L(LinkList&La,LinkList&Lb,linklist&Lc){if(m<n){p=La->next;Lc=La;q=Lb：}if 把两表联接else{p=Lb->next;Lc=Lb;q=La} La I『pFrwhile(!P->next)p=p->next;p->next=q->next;侬(哂 Lb—{7/T] 卜bH一卜cI—TTTreturn(Lc);例：(17分)设有•个正整数序列组成的有序单链表(按递增次序有序，且允许有相等的整数存在)，试编写能实现下列功能的算法乂要求用最少的时间和最小的空间)(00)确定在序列中比正整数x大的数有几个(相同的数只计算•次，如序列(20,20,17,15,15,11,10,8,7,7,5,4)中比10大的数有5个)；在单链表中将比正整数x小的数按递减次序排列；在单链表中将比正整数x大的偶数从单链表中删除；解：voidexam(Linklist,La,int,x){p=La-*next;q=p;k=0; //p为工作指针pre=la;lafnext=NULL;.〃q指最小元素while(p&&p-*data<x){〃比x小的数递减r=p->next;p->next=La-^next;La-*next=p;p=r;〃置逆}//whileq-next=p;pre=q;〃重新链接while(p->data=x){//考察等于x的情况pre=p; p=pfnext;}//whilewhile(p){〃k为计数器k++;x=p->data; 〃避免重复计算if(x%2=0){ 〃删除偶数while(p-*data=x)(//考察等于x的情况u=p;p=pfnext;free(u);}//whilepre->next=p;}//ifelse//处理奇数whileCp->data=x){pre—next=p;pre=p;p=p-*next;}//while}//while(p)}//exam例：已知L为没有头结点的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符。编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含有同一个类字符。(要求用最少的时间和最少的空间)(15分)解：PROCA(L：linkisttp;VARLetter,Digit,Other:linkisttp);new(Letter);new(Digit);new(Other);Letter*.next:=Letter;Digif.next:=Digit;Other\next:=Other;Whilel<>nildo[p:=L;L:=L".next;if(p\data>=,a,Andp\data<=,z,)Or(p\data>=,A,Andp\data<=*z')Then[p*.next:=Letter.next; letter*.next:=p;Letter:=p]else[iftp*.data>=,O'Andp*.data<=,9')then[p\next:=DigiC.next;Digit".next:=p;Digit:=p]else[p".next:=Other*.next;Other*.next:=p;Other:=p]]ENDP;例：(15分)已知f为单链表的表头指针，链表中存储的都是整型数据，试设计算法将此链表的结点按照递增次序进行就地排序。voidInsertSort_L(Linklist&La){〃用直接插入排序使链表递增有序if(La-next){〃链表不空p=La->nextfnext;La—nextfnextfNull;while(p!=Null){r=pfnext;〃暂存p的后继q=La;while(q-*next&&q-*-next->data<p-*data){q=qfnext;〃查找插入位置p->next=qnext;〃插入q-*next=p;p=r;}//while}//if//InsertSortL例：(20分)某商店有一批手机，按价格从高价到底构成一个单链表，结点包括数量、价格、指针。现新到n台价格不同的手机，编写将新到手机插入到原链表中的算法。解：定义此单链表的结点结构：typedefstructLnode{intnumber://数量域intvalue： 〃价格域structLnode*next;〃指针域}Lnode,*Linklist;voidinsertlink(Linklist&L,intn){〃将新到n台价格不同的手机插到有序链表中fbr(i=l;i<=n;i++){Scanf(&price); //读入每台手机价格S=(Linklist)malloc(sifeof(Lnode));Sfvalue=price;s number=1;P=L->next;if(p-*value<s—value){〃插入首部Snext=L-*next;L->next=s;}//ifelse{while(p->next&&(p-*next-*-value>svalue))p=p-*next;if(!pfnext){〃插入表尾s—next=pfnext;p->next=s;}//ifelseifi(p—nextfvalue=svalue)pfnextfnumber++;else{s->next=pnext;p—next=s;}//else}//fbr练习题：1、把上题以单链表的存储形式再编写算法.2、知有正整数组成的无序单链表，编写完成下列功能的算法:(1)找出最小值结点,并打印输出.(2)若该数值是奇数,将其与直接后继交换.(3)若该数值是偶数,将其与直接后继删除.(00)

3、单链表存储的数据是按递增有序且都是正整数，编写完成下列功能的算法（用最少的时间和空间）:（1）计算比X大的数有几个？（相同的计算一次）.（2）将小于X的部分表倒置.（3）将大于X的部分表中的偶数删除.（01）4、L为无头结点单链表的第一个结点指针，每个结点存放一个字符，该字符可能是英文字母或数字或其他字符.编写构造三个带头结点循环单链表的算法.每个表中只含一类字符.（时空）.（02）5,L为单链表头结点指针，数据都是正整数，设计算法按递增就地排序.（03）6、知手机价格按递减构成单链表，现有N台新的价格不同的手机，编写把它们插到表中合适位置的算法.（04）7、（15分）已知递增有序的单链表AJB分别存储了一个集合，请设计算法以求出两个集合A和B的差集A-B（即仅由在A中而不在B中出现的元素所构成的集合），并以同样的形式存储。要求用最少的时间。（05）8、（17分）设单链表的表头指针为h,结点结构由data和next两个域构成，其中data域为字符型。编写算法，判断该链表的前n个字符组成的是否为回文，要求使用栈和队列。（回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。）（06）第四部分栈队列一、栈栈是允许数据元素的插入与删除从表的同一端进行的一种线性表（即输入、输出受限的一种线性表）栈上运算的最大特点是：先进后出或后进先出（FILO、LIFO）。栈可以用顺序方式实现，也可以用链式实现。opreation data允许数据元素插入、删除的一端称为栈顶另一端称为栈底端；栈顶指示器用top表;一)顺序存储的栈:用C语言栈的顺序存储表示如卜：//defineSTACKJNIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*bot;SEIemType*top;intstacksize;}SqStack;1、栈顶动进栈退栈时栈顶指示器移动stackelementerrorTop=boot=0;boot不动，数据进退栈由Top指示,

数据进栈后Top+1,Top静态位置为新数据要存放的位置。退栈时Top要先减1。stackelementerrorTop=boot=0;boot不动，数据进退栈由Top指示，。单元不存放数据，Top=Top+l的 枝顶端位置，为进栈数据的位置，也就是要退 3 I——栈数据的位置。 ； 2、栈底动进栈退栈时栈底指示器移动 ； Top=boot=nnTop不动，数据进栈后 ：一Boot-1,boot静态位置为新数据要存放的位置。 2 输入abcde，经过一个栈处理，是否能得到： TOP，二 对于一个非空栈，栈顶指示器始终是在当前栈顶数据元素位置 迄二 *s.top-H-=*s.top-H-=e;returnOK;//把数据进栈后TOP再加1加1的位置上。用C语言编写的算法如下： 栈顶端StatusPush(SqStack&,SElemTypee){ Top ,if(S.top-S.bot>=S.stacksize){ 〃判预分空间是否用完 bootS.bot=(SElemType*)realloc(S.bot//动态再分配空间—m(S.stacksize+STACKINCREMENT)*sizeofi(SElemType));if(!S.bot)exit(OVERFLOW); //空间分配失败S.top=S.bot+S.stacksize; 〃修改栈顶指示器S.stacksize+=STACKINCREMENT:3、设共有m个连续空间单元，要求分成2个栈，每个栈容量不知且不相等.要求在任何时刻存储数据个数只要小于m便能满足用户的需要./Topi=0 |Top2=m-1boot1=0U乂iboot2=m-10 1 2 m-1Top2=m-1Boot2=m-1Top2=m-1Boot2=m-1Boot1=0判两个栈是否满是关键if(topl>top2)或if(top2<topl)4、多个栈的设计设共有m个连续空间单元，要求分成n(n>2)个栈,每个栈容量不知且产】等空理湾遨翅分配空.间;■警再今照闻…Topi=0'bootl=Topi=0'bootl=0Top2=4boot2=4Topi=(i-1)*m/nbooti=(i-1)*m/nBoot(n+1)=m-11)静态预分配空间假使每个栈容量相等为m/n,则每个栈的栈顶,栈底初始位置便可以确定.for(i=l,i<=n,-*-+i){Topi=(i-l)*m/n;booti=(i-l)*m/n)Boot(n+l)=m-l;5、多个栈上的操作0 1 2 345 6 ii+1 m-1Top1=01bootl=0 1 2 345 6 ii+1 m-1Top1=01bootl=0Top2=3boot2=3Topi=(i-1)*m/nBoot(n+1)=m-1booti=(i-1)*m/n**当数据耍进第i个栈时若预分空间没有用完，可按单个栈操作.关键是如何判断第i个栈是否满？理论上讲，如果第i个栈的栈顶指示器的值与第i+1个栈的栈底指示器的值相等，则说明预分空间用完。实现时可用下面语句:if(topi!=boot(i+l)) 〃分空间没有用完if(topi=boot(i+l)) 〃预分空间用完若预分空间已经用完2)动态再分配空间(查找空闲单元)首先向右查找最小的j,即第j个栈与第j+1个栈之间有空闲单元;While(topj=botj+1)j=j+l;其次，移动从第i+1个栈到第j个栈之间的元素，把一个空闲单元到与第i个栈的栈顶相邻处供第i个栈使用.实现语句：For(k=topj-l;k=boti+l;k-)S[k+1]=S[k]最后，把第i+1个栈到第j个栈的栈顶、栈底指示器都向右移动一个位置。For(k=i+l;k<=j;k++)top[k]=top[k]+lboot[k]=boot[k]+16、栈上的基本操作进栈Push(s,top);退栈Pop(s,top);注意*一般正常操作每个数据只进一次栈，退一次栈.*栈顶指示器top的两种使用方式： top若top指示栈顶元素所在的实际位置，则新元素进栈前top+1;若top指示栈顶元素实际位置的下个位置，则新元素进栈后top+1.5栈应用例1)两个栈的设计(00).2)把串3*-y-a/yA2改为3y-*ay2A/-,X,S分别代表一次进退栈，写出操作步骤.XSXXXSSSXXSXXSXXSSSS.(Ol)3)从左向右释放二叉树所有叶子结点，并将它们存放在一向量中.(02)7、链式栈存储一个数据元素的空间单元为结点。数据操作满足栈的先进后出，其他操作满足链表特点。Top右图为线性表(abcde)栈顶按顺序输入构成的链式栈。显然,从图中可以看出数据a是第 一-———•个进栈的元素.所以，它将是最后出栈的•个数据。而数据c是top最后进栈的元素，但它确是第一个出栈的元素。这部分内 |d|容比较简单.，学生自己可以编写有关的进栈、退栈的算法。举例：算术表达式计算求值算法的基本思想是：(1)首先置操作符栈OPTR为空，表达式起始符"#"为运算符栈的栈底元素。(2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权，若栈顶符号小于当前C中符号的优先级，则C中符号进栈，否则退栈运算。直到整个表达boot►a式求值结束。符号的优先级查看书中给出的表。有算术表达式：3*(7-2) 栈底.求值过程描述步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#PUSH(OPND,3)2# 3*(7-2)#PUSH(OPTR,♦)3#♦ 3(7-2)#PUSH(OPTR,(4#♦( 37-2)#PUSH(OPND,7)5#♦( 37-2)#PUSH(OPTR,-)6#♦(- 372)#PUSH(OPTR,2)7#*(- 372)#OPREATE(7, 2)8#*( 35)#POP(OPTR)消除一对括号9#* 35#OPREATE(3,*,5)10# 15#RETURN(GETTOP(OPND)OperandTypeEvaluateExpression(){InitStack(OPTR);Push(OPTRJ#")；//运算符栈OPTR置结束符#InitStack(OPND);c=getchar():〃数栈置空，并得到表达式中一个号While(c!="#"GetTop(OPTR)!=){ 〃c与OPTR栈顶不是#if(!In(c,op)){Push((OPNDE,c);c=getchar();}//数进OPND栈elseswitch(Precede(GetTop(optr),c)){//栈顶符号与C进行比较栈顶小casey'：Push(OPTR,c);c=getchar();break;〃运算符号C进栈case4=':Pop(OPTR,X);c=getchar();break;〃相等为()号case:Pop(OPTR,theta); 〃栈顶符号权高退栈,c中符号不变Pop(OPND,b);Pop(OPND,a); 〃退出栈顶元素a,bPush(OPND,Operatc(a,theta,b))break;; 〃运算结果进栈}switch}whilereturnGetTop(OPND);}算法执行过程参考书中P54例3-1o例:有数据"al2b3c4de“要求经过处理得到abed,4321设计结构m-11 2m-11 2Top=m-1Boot=m-1请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈定元素出栈，赋给变量x;sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enquence:插入一个元素入队列；dequence:删除一个元素出队列；quenceempty：判对列为空。m-11 2m-11 2Top1=0Boot1=001 2.出队歹ir 队头frontala2a3an-1rearTop1=0Boot1=001 2.出队歹ir 队头frontala2a3an-1rear队尾•--n-1进队列出队列- 队头队尾frontrearTop2=m-1Boot2=m-1二、队列抽象数据类型定义ADTQueue{数据对象：D={aiIaiGElemSet,i=l,2,3....n,n20}数据关系：RI={<ai-l,ai>Iai-l,aiGD,i=2,3,…n}基本操作：EnQueue(&Q,e)Q为非空队列。插入元素e为Q的新队尾。DeQueue(&Q,&e)Q为非空队列。删除Q的队头元素。队列是允许数据元素从一端插入，而从另一端删除的一种线性表。特点，先进先出。即经过队列输出数据的顺序与输入数据的顺序完全相同。允许数据元素插入的一端称为队尾(rear),允许数据元素删除的一端称为队头(fh)nt)。假设,q=(a1,a2,a3..…an)为队列，其存储形式如下图所示。进队列是利用循环的方式安排使用队列中有限空间的队列。一个具有使用价值的循环队列,是利用模数运算来判断队列是否满的循环队列.注意 Q.fh)nt=Q.rear=O为初次队列空的标志；一个空满循环队列如下图(1)示。Q.front指示要删除元素的位置。Q.rear指示当前队尾元素的下一个位置。允许数据从一端输入两端输出的，称为输入受限双端队列。•队头•队尾•队头•队尾2)输出受限双端队列允许数据从一端输出两端输入的，称为输出受限双端队列。队头队尾示例:假设有队头队尾示例:假设有m个连续的存储单元，要求分成一个栈和一个队列使用，每个容量不知且不相等，可以随机进入.队首0 1 2 m-1 队尾 4共用区间| 「栈底端例，用循环数组表示队列，且只有一个首指针front,设一个计数器记录队列中个数.1)编写判空，入队歹打出队列;(2)队列能容纳数据最多个数.(02)TYPEqu=ARRAY。..m・l]ofelemtp(l)FUNCempty(VARq:qu;VARfront,count;int):bollean;{if(count=0)empty=true;elseempty=false;}〃进队列FUNCenqueue(VARq:qu;VARfront,count;int;VARx:elemtp):bollean;{if(count==m)return;〃队歹U满elseJcount+4-;i=(front+count)MODm;q[i]=x}}PROCdequeue(VARq:qu;VARfront,count;int);{〃出队歹Uif(count=0)empty;//队歹性

else{front=(front+1)MODm;II修改首指针count—})}链式队列队列的链式表示和实现存储数据的空间单元为结点。存储结构为单链表。操作满足队列先进先出，以及单链表的运算方式。一个空的链队列完全类似一个空链表(如卜页图示)。一个链式队列完全类似一个带头结点的单链表(如下图示)：front链队列的存储结构用C语言描述如下：TypedefstructQNode{〃结点结构front链队列的存储结构用C语言描述如下：TypedefstructQNode{〃结点结构QEIemTypedata;structQnode*next;}Qnode,*QueuePtr;typeddefstruct{ （队头、队尾定义）QueuePtrfront;QueuePtrrear:JLinkQueue;Q.frontQ.rear空链队列进队列运算功能：把新的元素e从队尾插入，成为当前队列的队尾。出队列运算功能：将一个非空队列的队头元素删除Q.front队头队尾■|Q.front队头队尾■|a—b-c——>dQ.rear第五部分串(一)串上的基本操作1赋值运算Assign(s,ss);Creat(s,ch);2长度运算Len(s)3求子串运算Substr(I,j,length)4定位运算 Index(s,t)联接运算Concat(T,sl,s2)替换运算Rplace(s,t,v)(二)串的存储1、串的顺序存储(1)串的定长顺序存储是用一个地址连续的存储单元存储字符串的字符序列。其实现的方法是按照用户予定义的大小，系统为每个串的变量分配一个固定长度的存储区。串的实际长度可在予定义长度的范围内随意调整，超过予定义长度的串值将被舍去。(2)堆分配存储这仍然是用一组地址连续的存储单元存放字符序列，但它们的空间是在执行过程中动态分配的.在C语言中存在一个称为"堆''的自由存储区.C语言用函数malloc和free来管理.2、串的链表存储1)数组(1)二维数组的存储与寻址设有二维数组A,bl〈i〈dl,b2〈j〈d2,其按行主序存储的寻址公式：Loc(aij)=L0+[(i-bl)*(d2-b2+l)+(j-b2)]*l按列主序存储的寻址公式：Loc(aij)=L0+[(j-b2)*(dl-bl+l)+(i-bl)]*l其中L0为基址;1为每个数据元素占有的存储单元.(2)特殊矩阵的压缩存储对称阵;三角阵;带状(对角)矩阵N阶时称矩阵A中的元素满足下述性质aij=ajiIWiJWnN阶对称矩阵的存储矩阵中的每一对对称元素分配一个存储空间，则可将n*n个元素压缩存储到n(n+1)/2个存储空间中。假设以•维数组Sa[n(n+1)⑵作为n阶对称矩阵A的存储结构，则Sa[K]和矩阵元素aij之间存在着一一对应的关系：i(i-l)/2+j-1 i2jK=j(j-l)/2+i-li<j对称矩阵的压缩存储K=i(i-l)/2+j-1 iej.j(j-l)/2+i-l i<j对称矩阵的压缩存储alla21a22a31a32a33an1an2an3....annalla21a22a31 an,l ... an,nK=0 1 2带状(对角)矩阵3 n(n-l)/2n(n+l)/2-l1)主对角线一i=j.2)主对角线之下的对角线(低对角线)一i=j+l.3)主对角线之上的对角线(高对角线)一三条对角线上的元素总数为3*n-2,故可用含有3*n-2个存储空间的一维数组实现存储。l)K=2*(i-l)+j(以行优先存储如下)

allal2al3al4allal2a21a22a23a32a33a34a43a445 6 7 8 9102)K=2*(j-l)+i(以列优先存储如下)a23a24a3b^32^a3?a34a41a22^43^44al1a21al2a22K=1 23 4allal2al3al4allal2a21a22a23a32a33a34a43a445 6 7 8 9102)K=2*(j-l)+i(以列优先存储如下)a23a24a3b^32^a3?a34a41a22^43^44al1a21al2a22K=1 23 4a32a23a33a435 6 7 8a34a449 10LS=(al,a2,a3....an)其中LS是广义表的名字，n是它的长度。ai(lWn)是表中任意元素。在线性表中它只能是单元素，但在广义表中它可以是单元素，也可以是一个广义表(称为子表)。习惯上广义表的名字用大写字母表示，单元素用小写字母表示。当广义表不空时，称第一个元素al为LS的表头(head)元素，而称其余的元素为尾元素.(1)广义表的表头，表尾元素的划分与图形表示广义表的头元素可以是单元素，也可以是表元素来充当。但是广义表的尾元素，只能是表元素来充当。例如： /D)GetHead(B)=e;GetTail(B)=(). W@GetHead(D)=A;GetTail(D)=(B,C); 七| 不大由于(B,C)为非空列表，还可以继续分解得到：GetHead((B,C))=B; ~~/r-LhcGetTail((B,C))=