东北大学数据结构.doc

数据结构考研辅导材料李景银v 同学们，2007年考研专业课的辅导开始了。为使大家在准备过程中少走弯路，取得事半功倍的效果。首先我给大家谈几点意见，供同学们参考。一 基本概念二基本结构的算法描述方式:顺序;链表;串;树;图.三基本操作类型:建立;查找; 移动;插入;删除;合并;倒置;连接v 理解逻辑概念与物理表示之间的对应（或转换）关系v 学会把逻辑描述用形式语言实现的方法v 要求你们:深刻理解基本概念;v 熟练掌握基本结构;v 灵活运用基本算法v绪论基本概念：一、数据与数据结构1、数据 在计算机科学领域，凡是计算机能识别与处理的数字、符号、图形（象）、语音以及它们的汇集通称数据。2、数据结构 数据本身以及数据与数据之间的关系。 在数据处理时，为了用户存取、查找、修改、更新、插入、删除等操作方，对系统中提供的原始数据必须进行加工与组织，而经过人们加工得到的数据型式称为数据结构。它是一种抽象的逻辑结构(logical structure)。 Data-Structure = (D,S) D是数据元素的有限集合; S是D上关系的有限集。计算机科学领域常用的四种基本的数据结 （1）集合结构 数据元素之间没有固定关系。（ 2）线性结构 数据元素之间有一对一应关系。 （3）树型结构 数据元素之间有一对多的关系。 （4）图形结构 数据元素之间有多对多的关系 二、存储结构 存储结构是数据结构在存储介质上的具体表现形式。 数据结构与存储结构关系举例 例如原始数据 :9,7,4,5,3,6,1,2,8,0 数据结构:0,1,2,3,4,5,6,7,8,9顺序存储链式存储v 数据结构与存储结构的关系:v 1）一种数据结构可以对应多种存储结构。但是，在一个系统中一种数据结构只能使用一种存储结构。v 2）存储结构在表现形式上可以与数据结构相同，也可以不同。但是，它们都必须能准确无误地保证原数据结构的逻辑关系。两种基本的存储结构1、 顺序存储 顺序存储是按照数据结构中元素的顺序把数据依次存储到地址连续的存储区间。特点:1）必须预知最大空间量。2）每个数据元素都占用相同的存储单元。3）逻辑上相邻的元素，它们在存储介质上的物理位置一定相邻。4）在任意位置上的插入与删除元素浪费时间。5）可以随机查找。2 、链式存储 是按照数据结构中元素的顺序把数据依次存储到任意的地址单元.特点:1）可用任意空闲地址单元实现对线性表的存储；2）线性表中元素的逻辑关系，是用指针来保证的；3）在任意位置上插入与删除数据元素方便；4）在单链表中查找数据只能用顺序查找方式；5）空间利用率 比顺序存储低；3、抽象数据类型(abstract data type, ADT) 是指一个数学模型以及定义在该模型上的一组操作.其定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关,即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部的使用.一般用三元组表示: (D,S,P)D数据对象;S是D上的关系;P是对D的基本操作.格式定义:ADT抽象数据类型名 数据对象: (数据对象的定义) 数据关系:(数据关系的定义) 基本操作:(基本操作的定义)基本操作名(参数表) 初始条件: (初始条件描述) 操作结果: (操作结果描述)例,抽象数据类型三元组的定义:ADT Triplet 数据对象: D=e1,e2,e3| e1,e2, e3 Elemset(定义了关系运算的集合) 数据关系:R1=,(数据关系的定义) 基本操作:(InitTriplet(&T,v1,v2,v3) 结果把e1,e2,e3分别赋给参数v1,v2,v3。dataoperationsDestroyTriplet（&T）结果三元组T销毁.Get(T,i,&e) 初始条件:三元组T存在,1i3;in操作结果:用e返回T的第i元的值. Put(&T, i,e,)初始条件:三元组T存在,1i3;操作结果:改变T的第i元的值为e.Max(T,&e)初始条件:三元组T存在;操作结果:用e返回T的3个元素中的最大值.Min(T,&e)初始条件:三元组T存在;操作结果:用e返回T的3个元素中的最小值. ADT Triplet 三 、算法的时间复杂度与空间复杂度1 算法的定义:算法是对某类特定问题求解步骤的描述.它应满足下列特性： （1）有零个或多个输入量； （2）每一步都有唯一确定的含义； （3）至少有一个输出量； （4）执行有限步后自动停止； （5）能用现有的程序语言实现编程上机运行；2 算法的描述方式 自然语言; 流程框图; 伪形式语言(pascal , c, c+)3 算法的时间复杂度*程序时间复杂性的计算 一个程序P，所占用的时间T（P）= 编译时间+运行时间。编译时间与程序的特征无关。因此主要讨论程序的运行时间， 运行时间通常用TP表示。令n代表程序的特征（即对程序时间有影响的参数）。那么， TP的计算公式为： TP（n）= C1ADD(n) + C2SUB(n) + C3MUL(n) + C4DIV(n)+其中，C1、C2、C3、C4分别表示，一次加、减、乘、 除操作所需的时间。函数ADD (n) 、SUB (n) 、MUL (n) 、DIV (n)分别表示程序P中，所使用的加、减、乘、除操作的次数。在应用中大都是估算运行时间。估算的方法往往用所有操作之中，最多的操作次数，作为该程序的时间复杂性。算法的时间相当于程序时间中的运行时间部分。同样，关键操作的次数对时间复杂性的影响最大。假设, 算法中关键操作执行的次数是问题特征（规模）n 的某个函数f（n）。那么，算法的时间量度(复杂性)记作： T (n) = O(f(n)它表示随问题特征n的增大，算法中关键操作执行次数（时间）与f（n）也增大，而且算法中关键操作执行时间的增长率和f（n）的增长率相同。所以称f（n）为算法的时间复杂性。算法中语句操作执行的次数又称为频度. 在实际中，用算法中语句的最大频度，作为算法的时间复杂性。4 算法的空间复杂度 算法的空间相当于程序所需空间中的可变空间部分SP。所以，算法所需空间的量度记作： S (n)=O(f(n)其中N 为问题特征。表示除输入和程序之外所需的额外空间。四、 关于算法时间在考试中的类型:1,给定一个算法,估算其时间复杂度;时间与空间的关系.2,给定两个算法,比较它们的语句最大频度及时间复杂度;3,限定算法时间复杂度,编写完成功能的算法;例如,设计用时间复杂度为o(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 =1;col= M.nu;+col) /从M阵的第一列开始查找 for( p =1;p= M.tu; +p) /从第一个非零元素开始 if(M.datap.j=col) /找到非零元素所在列号 T.dataq. i=M.datap.j; T.dataq.j=M.datap. i； T.dataq.v =M.datap.v; +q; return OK; 算法的时间复杂性为O（nu*tu).若用其求m*n矩阵的转置阵算法的时间复杂性为O（m*n*n).Status FstTransposeSMatrix(TSMatrix M,TSMatrix &T) T.mu =M.nu; T.nu =M.mu; T,tu =M.tu;if(T.tu) for(col =1;col=M.nu;+col) numcol =0; / 置初值，清空 for( t =1; t = M.tu; +t) +numM.datat.j; / 计算每列非零个数 copt =1; / 得到第一列中第一个非零元素的位置 for(col = 2;col = Mnu; +col) /算每列中第一个元素在T中的序号 cpotcol = cpotcol 1+ numcol 1; for( p =1;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; +cpotcol; for if Return OK;该算法的时间复杂度为O (n)或 O (m).第二部分线性表的顺序存储一、线性表的顺序存储线性表的定义: 有限序列1 、线性表的抽象数据模型线性表（a1,a2 ,a3,an)的数据结构： Linear List =( D,R )其中，D =aiai D0,i= 1,2,3n,n 0 R =N,N =ai-1,ai D0 i = 2,3,n。 D0为某个数据对象。2、 顺序存储的实现 在高级程序语言中，一般都用数组来描述顺序存储。在C语言中可用动态分配的一维数组描述如下。define LIST_INIT_SIZE 100 /初次分配用户预估空间量 define LISTINCREAENT 10 /每次分配增量，一个元素占Typeset struct /用空间量 ElemType *elem; / 数组指针表的基址 int length; / 当前长度，实际已存元素个数 int listsize; /任何时刻能存最多元素个数SqList;空间量 = 最多元素个数 *每次分配增量(每个元素占用空间量)。3 、顺序存储上的运算1)查找-随机查找 随机查找是利用下面两个计算公式计算所要求元素物理地址.A）已知要查找元素的逻辑地址号.逻辑地址（相对地址） 是元素的位置序号; 物理地址是元素在存储介质上真正的存储地址.逻辑地址号转换成物理地址的公式: LOC(ai) = LOC(a0) + i * L ( L = 1) i为元素在存储空间的位置序号(逻辑地址， i从0开始)。B）已知要查找元素在表中的下标号.由元素的下标号计算物理地址的公式: LOC(ai) = LOC(a1) + (i 1) * L (L = 1) i为元素在表中数据ai的下标. （i从1开始）注： L为每个元素占有的存储单元数（增量）举例 ：有线性表（ a1 a2 a3 a4 am ），求元素a3 的物理地址；在表中该元素的下标是3，所以根据公式：2)顺序查找 条件：不知要查找元素的逻辑地址和其在表中的元素下标,已知要查找元素的值和表的长度.只能从表的一端开始逐一比较.Status ListSearch-Sq(SqList &L, int i, ElemTypee) i = 1;（ i为线性表元素的下标 ） While ( i = L.length & L.elem i-1 e ) i+; if (i L.length) return ERROR; else return(i -1);该算法的时间复杂度为（ n ）。 查找的有效范围是0length 1 问题： 若要求时间复杂度不变，而要提高该算法的运算速度，应如何修改该算法？为提高实际查找速度，1）查找的有效范围改为1length ；2）将控制循环查找的两个条件去掉一个；3）引入辅助单元(0单元作为辅助空间) 。其算法如下：Status ListSearch-Sq(SqList , &L ,key,Type key) L.elem0 = key; /将被查数据存放到0单元 i=length;/查找起始位置为高端While (!EQ(L.elemi.key, key) /循环查找 - -i; if (i1) return ERROR; /超处查找范围查找失败 return i; /查找成功v Search-seqv ;3)插入运算(1)在给定表中查找插入位置.(顺序或结合其他查找方式)(2)移动相关数据为新数据准备空间.(3)插入新数据.(4)修改当前长度.例题 知线性表顺序存储, 设计算法查找一个值为X的元素,若不存在将新元素X插入到表的首部;若存在将其删除. Status ListInsert-Sq(SqList &L,int i,ElemenType e) i = 1;（ i为逻辑线性表的下标 ） While ( i = L.length & L.elem i-1 x) i+;v if (i L.length)v p = & ( L.elem i-1 ) ; / P要被删除数据的地址v x=*p; / 把删除的数据放到x中v q = L.elem +L. length 1; / 需移动的最后数据的位置v for (+ +p; p = L.listsize) /预定义空间用完 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); / 动态再分配 if (!newbase) exit (OVERFLOW); /再分配失败 L.elem=newbase; /新基值 L.listsize +=LISTINCREMENT; /增加存储容量 if q=&(L.elemi-1); / 保存插入位置 for ( p = &(L.elemL.length 1); p=q; -p) * (p+1) =*p; / 移动相关数据为新数据插入准备空间 *q=x; / 插入新数据 +L.length; / 长度增加1 return OK; （ i为逻辑线性表元素的下标 与该元素的逻辑地址差1）4)删除运算 条件：删除表中第i个元素v Status ListDelete-Sq(SqList &L, int, ElemType &x)v if (L.length=0) return ERROR;v if ( i L.length) return ERROR;v p = & ( L.elem i-1 ) ; / P要被删除的位置v x=*p; / 把删除的数据放到x中v q = L.elem +L. length 1; / 需移动的最后数据的位置v for (+ +p; p = q; + p) *(p-1) = *p; / 移动数据v - - L.length; / 长度减1v return OK;v （ i为逻辑线性表元素的下标 与该元素的逻辑地址差1）例题 顺序存储,且元素递增有序.,若不存在插入,保持原序;若存在删除.(要求省时间)void InsertSq-list (SqList & L ) low = 0; high =L.length-1; while ( low= L.length-1;+ j) L.elemj-1 = L.elemj;删除 L.length =L.length-1; else high = m-1; / 插入点在低半区 else low = m+1; while for( j =L.length-1; j= high +1;- j) L.elemj+1 = L.elemj ;/记录后移 L.elemhigh+1 = x ; / 插入 L.length =L.length+1; 设有N个大小不等的数据组,顺序存放在空间区D内,总占用空间量为m,每个数据占有一个存储单元.编写将元素X插到第i个数据组末尾且属该于数据组的算法.（15）void insert-x(sqlist &L,int i,ElemType x) If (i=1&i=L.length) for (j=0,p=L.elem j; j=q; - p) /q=L.elem i第i个数据组的首址， *(p+1) = * p; /将（p-1）位置数据移到（ p ）位置 * p = X; /插入，修改从第i +1个数据组开始到Sn数据组地址 for (q=&L.elem i, p=& L.elemL.length-1; p=q; q+)/后边位置加1 (*q)+; m+;例题 知顺序存储,且数据元素递增有序.设计算法查找值为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+1; 例：编写把从线性表（ a1 a2 a3an ）中值为X 的元素开始到an的所有元素顺序倒置的算法。从a5= e开始到a9=Ifor （ i； i i +n/2）temp=l.elementi-1；l.elementi-1= l.elementn-i+4； l.elementn-i+1= temp倒置类型题:1 编写把线性表（ a1 a2 a3an ）的顺序完全倒置的算法。并计算该算法的时间复杂性及决定时间复杂性的语句频度。与后面章中有联系的问题:二叉树的顺序存储;图的顺序存储;查找;排序第三部分 链表*基本概念与术语一、结点(node) 线性表中一个数据元素所占用的存储空间。它由数据域与指针域两部分组成，数据域用来存储用户的有用数据； 指针域用来存储直接前驱或直接后继数据元素所在结点的地址.1、含有一个直接后继数据元素指针域的结点 在C语言中可用结构指针来描述结点： typedef struct Lnode ElemType data; struct Lnode * next; Lnode, *LinkList;2、含有两个指针域的结点.一个直接前驱结点指针域,一个直接后继结点指针域.在C语言中可用结构指针来描述结点：Typedet struct DuLNode ElemType data; struct DuLNode *priou; struct DuLNode *next; DuLNode,*DuLinkList;二、单链表:如果，构成链表的每个结点都只含有一个指针域， 那么称这个表为单链表.1、不带头结点单链表;不带头结点的单链表的标准形式:不带头结点的单链表的空表标准形式: H=NULL. 2 、带头结点单链表的标准形式.L三、循环单链表:1、不带头结点的循环单链表;Lc2、 带头结点循环单链表;标准形式:四、双向链表(循环,不循环)1、不带头结点的循环双向链表;(略)2、 带头结点循环双向链表;*基本运算和例题一、单链表的插入运算1,首部插入(生成结点,插入结点)2,尾部插入(查找尾部结点, 生成结点,插入结点)3,条件插入(查找条件结点,保存前驱结点,生成结点,插入结点)Status insert-list() Status insert-list() p=h ; P=L; q=p-next; if p=null return ERROR; while (q-datax &q-nextnull ) if (p-datax &p-nextnull ) P=q; q=q-next; q=p-next; if (q-data=x) while (q-datax &q-nextnull ) s=(LinkList) malloc(sizeof(LNode)； P=q; q=q-next; s-data=y; if(q-data=x) s-next=p-next; s=(LinkList) malloc (sizeof(LNode) P-next=s; s-data=y; s-next=p-next; P-next=s;二、单链表的删除运算1,首部删除(结点, 释放结点).2,尾部删除(查找尾部结点,保存前驱结点,释放结点).3,条件删除(查找条件结点,保存前驱结点,释放结点).三、循环单链表的插入与删除:可以从表中任意已知地址查遍全表(循环)Status insert-list (L) (不循环) Status insert-list (Lc) P=L; q=p-next; P=Lc; q=p-next;while (q-data x &q- nextnull ) while (q-datax &q-next Lc)P=q; q=q-next; P=q; q=q-next; if (q-data=x) if (q-data=x) s=(LinkList) malloc(sizeof(LNode) s=(LinkList) malloc(sizeof(LNode)；s-data=y; s-data=y; s-next=p- next; s-next=p-next;P-next=s; P-next=s; P=lc-next; lc-next=av; Av=pAv为可用链表,lc为一数据无用的循环链表.要求用最少的时间把lc表与Av连接在一起.例题：Josephus问题:n个人围成圆圈,从第s个开始计数到m,便将其删除,从下一个开始,重复上述过程,直到所有人都删除.(1)建立一个含有n个结点的循环单链表jos-clist.(2)从第s个开始查找,输出和删除m由josephus-clist完成.PNode p,q;(构成循环链表)Int I;q=(PNode)malloc(sizeof(stuct Node);If(q=null) return (false);*pelist=q;Q-inf=1;q-link=q;If(n=1) return (true);For(i=2;iinf=1;p-link; q-link=p; q=p;/尾部插入 Return(true);#define false 0#define true 1Typedef int datatype;Stuct Node;Typedef stuct Node *PNode;Stuct Nodedatatype inf; PNode link;Typedef stuct Node *LinkList;Int init_clink(PLinklist pclist,int,n)voidJosephus(PLinklist pelist,int s,int m)PNode p,pre;int I;p=*pelist; if(s=1) pre=p;p=p-link; While(p!=*pelink) pre=p;p=p-link; else for(i=1;ilink; While(p!=p-link) for(i=1;ilink; prinef(“out element:p-info) if(*pelist=p) *pelist= p-link;Pre-link= p-link; Free(p);p= Pre-link; prinef(“out element:p-info);*pelist=null Free(p);主程序Mia() linklist jos-clist; int n,s m;Printf(“input”n); Scanf(&n);Printf(“input”s); Scanf(&s);Printf(“input”m); Scanf(&m);If(init-clink (&jos-clist,n)Josephus-clink(&jos-clist, s,m);Else printf(“out of space”);四、循环双向链表上的操作1、循环双向链表上的插入 SP2、循环双向链表上的删除插在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表.算法描述:(1)设定A为C表.并将其倒置.(2) qa,qb分别为两表中当前结点指针.(3)当qa,qb都存在时重复: 比较qa,qb结点数值, 若qanext; /第一个结点 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-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-data=qc-data) qb=qb-next; /修改qb while (!qa& qa-dataqc-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;/修改v 3、（12分）假设一个有向图G已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环（回路）的算法。解：对十字链表储存结构的有向图采用拓扑排序v Status toposort (OLGraph G) v findindegree (G, indegree); /对各顶点求入度v InitQueue (Q); /队列初始化v Count=0; /计数器初始化v for(i=0;iG.Vernum;i+)v if(G.Ver i .indegree=0)v Enqueue(Q,i); /入度为零的顶点入队v While(！QueueEmpty (Q) ) v Dequeue(Q,i); /队头出队v Count+;v P=G. ver i .firstout; /取邻接点v while(p) /处理邻接点的入度v j=p headvex;v G.ver j .indegree-;v if(G.ver j .indegree=0)v Enqueue (Q,j); /顶点j入队v p=ptlink;/指针后移v /whilev /whilev if (