东北大学数据结构.docx

《东北大学数据结构.docx》由会员分享，可在线阅读，更多相关《东北大学数据结构.docx（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构考研辅导材料考者能 同学们，2007年考研专业课的辅导开始了。为使大家在准备过程中少走弯路，取得 事半功倍的效果。首先我给大家谈几点意见，供同学们参考。一基本概念二基本结构的算法描述方式:顺序;链表;串;树;图.三基本操作类型:建立;查找；移动;插入;删除;合并;倒置;连接理解逻辑概念与物理表示之间的对应（或转换）关系 学会把逻辑描述用形式语言实现的方法 要求你们:深刻理解基本概念； 熟练掌握基本结构； 灵活运用基本算法绪论基本概念：一、数据与数据结构1、数据在计算机科学领域，凡是计算机能识别与处理的 数字、符号、图形（象）、语音以及它们的汇集通称数据。2、数据结构数据本身以及数据与数

2、据之间的关系。在数据处理时，为了用户存取、查找、修改、更新、插入、删除等操作方，对系统 中提供的原始数据必须进行加工与组织，而经过人们加工得到的数据型式称为数据结构。它 是一种抽象的逻辑结构（logical structure）=Data-Structure = （D,S）D是数据元素的有限集合；S是D上关系的有限集。计算机科学领域常用的四种基本的数据结（1）集合结构 数据元素之间没有固定关系。（2）线性结构数据元素之间有一对一应关系。（3）树型结构数据元素之间有一对多的关系。二、存储结构存储结构是数据结构在存储介质上的具体表现形式。数据结构与存储结构关系举例例如原始数据：9,7,4,5,3,

3、6,1,2,8,0数据结构：0,2,3,4,5,6,7,8,9顺序存储0 12345678 9链式存储数据结构与存储结构的关系： 1）一种数据结构可以对应多种存储结构。但是，在一个系统中一种数据结构只能使 用一种存储结构。 2）存储结构在表现形式上可以与数据结构相同，也可以不同。但是，它们都必须能 准确无误地保证原数据结构的逻辑关系。两种基本的存储结构1、顺序存储顺序存储是按照数据结构中元素的顺序把数据依次存储到地址连续的存储区间。特点：1）必须预知最大空间量。2）每个数据元素都占用相同的存储单元。3）逻辑上相邻的元素，它们在存储介质上的物理位置一定相邻。4）在任意位置上的插入与删除元素浪费时

4、间。5）可以随机查找。2、链式存储是按照数据结构中元素的顺序把数据依次存储到任意的地址单元.特点：1）可用任意空闲地址单元实现对线性表的存储：2）线性表中元素的逻辑关系，是用指针来保证的；3）在任意位置上插入与删除数据元素方便：4）在单链表中查找数据只能用顺序查找方式：5）空间利用率比顺序存储低；3、抽象数据类型（abstract data type, ADT）是指一个数学模型以及定义在该模型上的一组操作.其定义仅取决于它的一组逻辑特 性，而与其在计算机内部如何表示和实现无关,即不论其内部结构如何变化，只要它的数学特 性不变，都不影响其外部的使用.一般用三元组表示：（D,S,P）D数据对象;S

5、是D上的关系;P是对D的基本操作.格式定义：ADT抽象数据类型名数据对象：（数据对象的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义）基本操作名（参数表）初始条件：（初始条件描述）操作结果:（操作结果描述）例，抽象数据类型三元组的定义：ADT Triplet 数据对象：D=el,e2,e3| el,e2, e3 GElemset（定义了关系运算的集合）数据关系:Rl=,（数据关系的定义）基本操作：（InitTriplet（&T,vl,v2,v3）结果把 el,e2,e3 分别赋给参数 vl,v2,v3。DestroyTriplet （&T）结果三元组 T 销毁.cneraticn

6、sdataGet（T,i,&e）初始条件:三元组T存在,liW3;in 操作结果:用e返回T的第i元的值.InittripletPut（&T, i,e,）初始条件:三元组T存在，1 Wi MUL(n)、DIV (n)分别表示程序P中，所使用的加、减、乘、除操作的次数。 在应用中大都是估算运行时间。估算的方法往往用所有操作之中，最多的操作次数，作为该 程序的时间复杂性。算法的时间相当于程序时间中的运行时间部分。同样，关键操作的次数对时间复杂性的影响 最大。假设，算法中关键操作执行的次数是问题特征(规模)n的某个函数f (n)。那么， 算法的时间量度(复杂性)记作：T(n) = O(Rn)它表示随

7、问题特征n的增大，算法中关键操作执行次数(时间)与f (n)也增大，而且算 法中关键操作执行时间的增长率和f (n)的增长率相同。所以称f (n)为算法的时间复杂 性。算法中语句操作执行的次数又称为频度.在实际中，用算法中语句的最大频度，作为算法的时间复杂性。4算法的空间复杂度算法的空间相当于程序所需空间中的可变空间部分SP。所以，算法所需空间的量度记作：S (nO(f(n)其中N为问题特征。表示除输入和程序之外所需的额外空间。四、关于算法时间在考试中的类型：1,给定一个算法，估算其时间复杂度;时间与空间的关系.2,给定两个算法，比较它们的语句最大频度及时间复杂度；3,限定算法时间复杂度，编写

8、完成功能的算法；例如，设计用时间复杂度为。(n)级的算法，完成稀疏矩阵的转置阵.Status TransposeMatrix M,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.datap .j=col) 找到非零元素所在列号T.dataq. i=M.datap.j;T.dataq.j=M.datap

9、. i；T.dataq.v =M .datap.v; +q；return OK;算法的时间复杂性为O (nu*tu).若用其求m*n矩阵的转置阵算法的时间复杂性 为 O (m*n*n).Status FstTransposcSMatrix(TSMatrix M,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) numcol =0; 置初值，清空for( t=l; t = M.tu; -H-t) +numM.datat.j; / 计算每列非零个数copt=l;/得到第一列中第一个

10、非零元素的位置for(col = 2;col = Mnu; col) 算每歹ij中第一个元素在T中的序号cpotcol = cpotcol 一11+ numcol -1;for( p=l;p=m.tu;+p) col = M.datap.j; q = cpotcol; / 当前列第一非零元素地址Tdataq.i =M.datap.j; T.dataq.j =M.darap.i;T.dataq.v = M.datap.v; -H-cpotcoI;fbrifReturn OK;该算法的时间复杂度为O (n)或O (m).cc-ccuperaiion第二部分线性表的顺序存储cenlef I一、线性表

11、的顺序存储线性表的定义：有限序列1、线性表的抽象数据模型线性表(al,a2 ,a3,an)的数据结构：Linear List =( D,R )其中，D=ai I ai D0,i= l,2,3 . n,n =0 prior next retrieve updatafindInsert rdelete locateR=N,N= I ai-l,aie D0i = 2,3,n。DO为某个数据对象。2、顺序存储的实现在高级程序语言中，一般都用数组来描述顺序存储。在C语言中可用动态分配的一维数 组描述如下。define LIST_INIT_SIZE 100/初次分配用户预估空间量define LISTIN

12、CREAENT 10 每次分配增量，一个元素占Typeset struct 用空间量ElemType *elem; /数组指针表的基址 int length; /当前长度，实际已存元素个数 int listsize;/任何时刻能存最多元素个数SqList;空间量=最多元素个数*每次分配增量(每个元素占用空间量)。3、顺序存储上的运算1)查找-随机查找随机查找是利用下面两个计算公式计算所要求元素物理地址.A)已知要查找元素的逻辑地址号.逻辑地址(相对地址)是元素的位置序号； 物理地址是元素在存储介质上真正的存储地址.逻辑地址号转换成物理地址的公式：LOC(ai) = LOC(aO) + i*L

13、(L= 1)i为元素在存储空间的位置序号(逻辑地址，i从0开始)。BF赞1要查找元素在表中的下标号.由元素的下标号计算物理地址的公式：LOC(ai) = LOC(al) + (i-l)*L (L = 1)i为元素在表中数据ai的下标.(i从1开始)注：L为每个元素占有的存储单元数(增量)举例：有线性表(al 32 a3 a4 . 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

14、,所以根据公式：LOC(ai) = LOC(aO) + i*L ( L = 1)有LOC(a3) = LOC(aO) + 2* L ( L = 1) =99 + 2*1=101涉辑地址.0123 m-1ala2a3a4am物理地址 99 100 101102 103 .2)顺序查找条件：不知要查找元素的逻辑地址和其在表中的元素下标，已知要查找元素的值和表的长 度.只能从表的一端开始逐一比较.Status ListSearch-Sq(SqList &L, int i, EIemTypee)i=l; ( i为线性表元素的下标)While (i = L.length & L.elem i-1 e )

15、i+；if (i L.length) return ERROR;else retum(i 1);该算法的时间复杂度为O ( n )。查找的有效范围是0length-10123length -1ala2a3a4an问题：若要求时间复杂度不变，而要提高该算法的运算速度，应如何修改该算法？为提高实际查找速度，1)查找的有效范围改为1length ； 2)将控制循环查找的两个条件 去掉一个；3)引入辅助单元(0单元作为辅助空间)。其算法如下：Status ListSearch-Sq(SqList, &L,key,Type key) L.elem0 = key; 将被查数据存放到0单元i=length;

16、 查找起始位置为高端While (!EQ(L.elemi.key, key) 循环查找i；if(il) return ERROR; 超处查找范围查找失败return i;查找成功 Search-seq01234 lengthcabcdn3)插入运算(1)在给定表中查找插入位置.(顺序或结合其他查找方式)(2)移动相关数据为新数据准备空间.(3)插入新数据.(4)修改当前长度.例题知线性表顺序存储，设计算法查找一个值为X的元素，若不存在将新元素X插入到表的首部;若存在将其删除.Status ListInsert-Sq(SqList &L,int i,ElemenType e) i=l；( i为逻

17、辑线性表的下标)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 = L.listsize) 预定义空间用完newbase=(ElemType*)realloc(L.elem,(L.listsize+LlSTINCREMENT)*sizeof(ElemType);/动态再分配 if(inewbase) exit (OVERFLOW);L.elem

18、=newbase;L.listsize +=LISTINCREMENT;ifq=&(L.elemi-l);for ( p = &(L.elemL.length -1); p=q; p)* (p+l)=*p；*q=x;+Length;return OK;再分配失败新基值增加存储容量/保存插入位置/移动相关数据为新数据插入准备空间/插入新数据/长度增加1 （ i为逻辑线性表元素的卜标与该元素的逻辑地址差1）4）删除运算条件：删除表中第i个元素Status ListDelete-Sq(SqList &L, int, ElemType &x) if (L.length=0) return ERROR;

19、 if( i L.length) return ERROR; 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;/ 长度减 1return OK; ( i为逻辑线性表元素的下标与该元素的逻辑地址差1)例题顺序存储，且元素递增有序.，若不存在插入，保持原序;若存在删除.(要求省时间) void InsertSq-list (SqList & L ) low = 0; high

20、 =L.Iength-l;while (low= L.length-L.elemj-1 =删除L.length =L.length-l; else high = m-l;/插入点在低半区 else low = m+1; whilefor（ j=L.length-l; j= high +l;-j）L.elemj+1 = L.elemfj;记录后移L.elemhigh+1 = x ; / 插入L.length =L.length+l;设有N个大小不等的数据组，顺序存放在空间区D内，总占用空间量为m,每个数据占有一个 存储单元.编写将元素X插到第i个数据组末尾且属该于数据组的算法.（15）1）若第i

21、 （i=n）个数据组直接插入。修改Si 的长度。2） in从数据组1开始查找i,然后移动相关 数据，为新元素插入准备位置，修改Si+1到Sn 数据绢地址与Sfil的长度。L.lengthvoid insert-x(sqlist &L,int i,ElemType x)If (i=l&i=L.length)for (j=0,p=L.elem j; j=q; - p) /q=L.elem i第 i 个数据组的首址，*(p+l)=*p;将(pl)位置数据移到(p* p = X; /插入，修改从第i +1个数据组开始到Sn数据组地址for (q=&L.elem i, p=& L.elemL.lengt

22、h-l; p=q; qH)后边位置加 1 (*qM;mH;例题知顺序存储,且数据元素递增有序.设计算法查找值为X的元素，若存在与直接 前驱元素交换.若不存在将X插入,仍保持原序;.(要求省时间)void InsertSq-list (SqList & L) low = 0; high =L. length-1;while (low= high +1;j) L.elemj+1 = L.elemj;/ 记录后移L.elemhigh+1 = x ; / 插入L. length =L.length+l;例：编写把从线性表(al a2 a3an )中值为X的元素开始到an的所有元素顺序 倒置的算法。从a

23、5=e开始到a9=I012 345678倒置前 a b c d e f g h iabcdihgfe012 345678倒置后for ( i； i Wi+n/2) an-1 +1temp=l.elementi-1 ；ai-l.elementi-l = l.elementn-i+4；l.clementn-i+l= temp倒置类型题：1编写把线性表(al a2 a3an )的顺序完全倒置的算法。并计算 该算法的时间复杂性及决定时间复杂性的语句频度。与后面章中有联系的问题：二叉树的顺序存储;图的顺序存储;查找;排序第三部分链表*基本概念与术语一、结点(node)线性表中一个数据元素所占用的存储空间

24、。它由数据域与指针域两部分组 成，数据域用来存储用户的有用数据；指针域用来存储直接前驱或直接后继数据元素所在 结点的地址.1、含有一个直接后继数据元素指针域的结点数据域指针域p n data next在C语言中可用结构指针来描述结点：typedef struct Lnode ElemType data;struct Lnode * next; Lnode, *LinkList;2、含有两个指针域的结点.一个直接前驱结点指针域，一个直接后继结点指针域. 在C语言中可用结构指针来描述结点：prioudatanext前驱指针域数据域后继指针域Typedet struct DuLNode ElemTy

25、pedata;struct DuLNode *priou;struct DuLNode *next; DuLNode,*DuLinkList;二、单链表:如果，构成链表的每个结点都只含有一个指针域，那么称这个表为单链表.1、不带头结点单链表；不带头结点的单链表的标准形式：不带头结点的单链表的空表标准形式:H=NULL.2、带头结点单链表的标准形式.首部结点C6A尾结点带头结点的空单链表标准形式.L-next=NULL三、循环单链表：1、不带头结点的循环单链表;四、双向链表（循环，不循环）1、不带头结点的循环双向链表;（略）2、带头结点循环双向链表；空表结构*基本运算和例题一、单链表的插入运算1

26、,首部插入（生成结点，插入结点）2,尾部插入（查找尾部结点，生成结点，插入结点）3,条件插入（查找条件结点,保存前驱结点，生成结点，插入结点）将y插入到x之前Status insert-list() p=h ;ifp=null return ERROR;if (p-datax &p-nextnull) q=p-next;while (q-datax &q-nextnull) P=q；q=q-next;ifl(q-data=x)s=(LinkList) malloc (sizeofifLNode) s-data=y;Status insert-list() P=L; q=p-next;while

27、 (q-datax &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,便将其删除，从 下一个开始，重复上

28、述过程,直到所有人都删除.Status insert-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;Status insert-list (Lc) P=Lc; q=p-next;(循环)while (q-datax &q-nexto Lc)P=q; q=q-next;if (q-data=x)s=(LinkList) malloc(siz

29、eof(LNode)；s-data=y;s-next=p-next;P-next=s;Av为可用链表,lc为一数据无用的循环链表,要求用最少的时间把1c表与Av连接在一起.LcAv=pav(1)建立一个含有n个结点的循环单链表josclist.#define false 0#define true 1(2)从第s个开始查找，输出和删除m由josephus-clist完成.PNode p,q;(构成循环链表)Int I;Typedef int datatype;Stuct Node;Typedef stuct Node pelist= p-link;PNode;Stuct Nodedatatyp

30、e inf;PNode link;；Typedef stuct Node *LinkList;Int init_clink(PLinklist pclist,int,n)voidJosephus(PLinkIist pelist,int s,int m) PNode p,pre;int I;p=*pelist;if(s=l)pre=p;p=p-link;While(p!=*pelink)pre=p;p=p-link; )else fbr(i=l;ilink; While(p!=p-link) fbr(i=l;ilink; prineflf Uout element:p-infb) if(*pe

31、list=p)q=(PNode)malloc(sizeof(stuct Node);Ifi(q=null) return (false);*pclist=q;Q-inf= 1 ;q-link=q;If(n=l) return (true);For(i=2;iinf=l ;p-link;q-link=p; q=pj/尾部插入 )Pre-link= p-link;Free(p);p= Pre-link;prinef( infb);*pelist=nullFree(p);)主程序 Mia() linklist jos-clist; int n,s m;Printfi( input n); Scanf

32、i(&n);Printf( input” s); Scanf(&s); PrintR “input m); Scanfi(&m); Ifi(init-clink (&jos-clist,n) Josephus-clink(&jos-clist, s,m); Elseprint出“out of space );四、循环双向链表上的操作 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

33、;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结点数值，若qa7L

34、B卜 21 I - I 150 八 void mrege(linklist& pajinklist &pb) Lc=la;A表作为结果表qa =lanext; 第一个结点 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-dataqb-data&qa-next) / qa 的数大pre=qa;qa=qa-next;if (qa-next=null) u=qb-next;qb

35、-next=qa-next;qa-next=qb;qb =u);if (qa-datadata) / qa 的数值小,qb 前插入 u=qb-next;qb-next=pre-next;pre-next=qb; pre= qb; qb =u;)例2知A,B,C为三个单链表数据递增有序，要求对A作如下处理:删除与BC中相同的 数据；viod delet (linklist &la)pa=la; qa=la-next;qb=lb-next;qc=lc-next;while (!qc& qb-dataqc-data & !qb) 找出 BC 中所有相同元素 qb=qb-next;if (qb-dat

36、a=qc-data) qb=qb-next; 修改 qb并删除while (!qa& qadataoqcdata)找出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已经以十字链表形式存储在内存中，试写一个判断该 有向图中是否有环（回路）的算法。解：对十字链表储存结构的有向图采用拓扑排 序Status toposort （OLGraph G） findindegree (G, indegree);InitQue

37、ue (Q);Count=0;fbr(i=O;iG.Vemum;i-H-)ifi(GVer i .indegree=O) Enqueue(Q,i);While(! QueueEmpty (Q) Dequeue(Q,i)；Count-H-；P=G ver i .firstout;while(p)(j=pf headvex;对各顶点求入度队列初始化计数器初始化入度为零的顶点入队队头出队取邻接点处理邻接点的入度Gver j .indegree;ifi(Gver j .indegree=O)Enqueue (Qj); 顶点 j 入队p=pf tlink;/指针后移 /while /whileif (countnext; q-freq=0;While (q-priould)置所有频度初值 q-ferq=O;q=q-next;scanfifx);while (x0)LOCATE(L,X)q-freq= q-freq+l; p=q-priou;while(pold&p-freqfreq) p= p-freq;if( !(p-freq q