数据结构考研课程总结课件

1、数据结构 主讲 刘铁铭单位工院一系二教Tel: 319468/22/20221数据结构讲课安排：串讲全书内容典型习题分析前年、去年考题分析 8/22/20222数据结构第一章 概 论数据结构及其概念 如何评价一个算法8/22/20223数据结构第一章 概 论1.1 数据结构的概念一、术语1.数据(Data): 是信息的载体，能被计算机识别、存储、加工处理。2.数据元素(Data Element): 数据的基本单位, 即数据集合中的一个个体。也称元素、结点、顶点、记录数据项:是具有独立含义的最小标识单位关键字（key)：唯一能识别一个数据元素的数据项。数据元素由数据项(data item)组成8

2、/22/20224数据结构 3、数据类型(Data Type): 是具有相同性质的计算机数据的集合及在这个集合上的一组操作。原子数据类型(atomic data type)结构数据类型(aggregate data type)4、数据结构 数据的逻辑结构 数据的存储结构 数据的运算：既对数据施加的操作8/22/20225数据结构逻辑结构：(有时直接称为数据结构）线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继)非线性结构：树 、图、多维数组、广义表说明：1、逻辑结构与数据元素本身的形式、内容无关2、逻辑结构与数据元素的相对位置无关3、逻辑结构与所含结点个数无关8/22/202

3、26数据结构存储结构：顺序存储方法：数据元素在内存中按序连续存储， 结点间的逻辑关系由存储单元的邻接关系来体现链接存储方法：用指针指出其直接后继结点的存储位置， 结点间的逻辑关系由存储单元的邻接关系来体现索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成 分为稠密索引和稀疏索引散列存储方法：确定散列函数后，根据结点的关键字直接 计算出该结点的存储地址。8/22/20227数据结构关系：逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于计算机的。逻辑结构是从具体问题抽象出来的数学模型存储结构是逻辑结构用计算机语言的实现（亦称映象）数据的运算

4、是定义在数据的逻辑结构上的一个运算的集合运算的实现与存储结构密切相关逻辑结构与存储结构是多对多的关系8/22/20228数据结构例：一个学生成绩表：是一个数据结构每行是一个结点（或记录），由学号、姓名、各科成绩 及平均成绩等数据项组成。逻辑关系：线性结构存储结构：表的运算：8/22/20229数据结构 逻辑结构上定义的基本运算在存储结构上的实现是通过算法来描述的。一、算法定义 算法是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。第一章 概 论1.3 算法描述8/22/202210数据结构 二、算法应具有的五个特性：（1）输入 一个算法有零个或多个的输入，

5、它们是算法开始前给出的最初量（2）输出 一个算法至少有一个输出，它们是同输入 有某种关系的量（3）有穷性 每一条指令的执行次数必须是有限的（4）确定性 每一条指令必须有确切的含义，无二义性（5）可行性 每条指令的执行时间都是有限的。8/22/202211数据结构第一章 概 论一、算法评价五要素 （1）正确性（2）执行算法所耗费的时间（3）执行算法所耗费的空间（4）可读性（5）健壮性1.4 算法分析8/22/202212数据结构第一章 概 论二、算法的时间复杂度 一个算法所耗费的时间:该算法中每条语句的执行时间之和。每条语句的执行时间：该语句的执行次数乘以该语句执行一次所需时间。频度：语句重复执

6、行的次数算法的时间耗费T(n)=每条语句的执行的时间=（语句频度语句执行一次所需时间） =语句频度算法的时间复杂度：就是算法的时间耗费T(n)8/22/202213数据结构第一章 概 论三、（渐进）时间复杂度(O(f(n)当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度，简称时间复杂度四、最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度。五、平均时间复杂度在假设数据集的分布是等概率的条件下，估算出的时间复杂度称为平均时间复杂度。例：顺序查找8/22/202214数据结构五、空间复杂度S(n)： 算法所耗费的存储空间，仍是问题规

7、模n的函数。第一章 概 论8/22/202215数据结构第一章 概 论本章要求:1、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。3、学会算法分析的基本方法。8/22/202216数据结构第二章 线性表本章要学习的主要内容1、线性表的逻辑结构及基本运算2、线性表的顺序存储结构3、线性表的链式存储结构：单链表、循环链表、双链表、静态链表4、顺序表和链表的比较8/22/202217数据结构2.1 线性表的概念及运算1.描述: 线性表是由n (n=0)个数据元素(点)a1,a2,.,ai,.,an组成的有限序列。其中，数据元素的个数n定义为表长。当n=0时称为空表，非

8、空的线性表(n0)记为： (a1,a2,.,ai,.,an)一、逻辑结构 注意: 1.数据元素ai是一个抽象的符号 2. ai可取各种数据类型 3. 一般情况下,同一线性表中的元素具有相同的数据类型 4. i是元素的序号 (1=i=n) 2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继8/22/202218数据结构线性表的常见基本运算包括： （1）置空表SETNULL(L) （2）建表CREATLIST(L)二、线性表的运算 （4）取结点GET(L,i) （5）定位LOCATE(L,x) （6）插入INSERT(L,x,i) （7）删除DELETE

9、(L,i) （3）求表长LENGTH(L)复杂的运算可以由这些基本运算组合来实现8/22/202219数据结构2.2 线性表的顺序存储1、顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。 3、存储地址的计算： LOC(ai)=LOC(a1)+(i-1)*c 1=idata=ch; s-next=head; head=s; ch=getchar( );return head;8/22/202228数据结构2.3.2 单链表上的基本运算（实现）尾插法建表：将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr不带头结点的尾插法：插入时，第一个结点的处理与其它结点的处理

10、有区别。 结束时，空表和非空表的处理有区别。8/22/202229数据结构Linklist *CREATLISTR( ) char ch; linklist *head,*s,*r; head=NULL; r=NULL; ch=getchar( ); while (ch!=$) s=malloc(sizeof(linklist) ; s-data=ch; if(head=NULL) head=s else r-next=s; r=s; ch=getchar( ); if (r!=NULL) r-next=NULL; return head;8/22/202230数据结构2.3.2 单链表上的基

11、本运算（实现）尾插法建表：将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr不带头结点的尾插法：插入时，第一个结点的处理与其它结点的处理有区别。结束时，空表和非空表的处理有区别。带头结点的尾插法：1）链表第一个位置上的操作与其它位置上的操作相一致。2）空表和非空表的处理相一致。8/22/202231数据结构2.3.2 单链表上的基本运算（实现）Linklist *CREATLISTR1() char ch; linklist *head,*s,*r; head=malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=“$”)

12、 s=malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; return head; dsrcHeadr8/22/202232数据结构2.3.2 单链表上的基本运算（实现） 二、查找运算（1）按序号查找 GET（L，i） 给定一个序号，在单链表中查找该序号对应的结点， 若结点存在，则返回该结点的指针，否则返回空指针。方法：非随机存储结构的链表，决定了上述查找运算只能通过扫描单链表来完成。设置一个计数器j一个p，初始指向头结点P向后每移动一个位置j+当j=i时返回8/22/202233数据结构按

13、值查找即在链表中查找是否有值等于给定值key的结点。若有则返回首次找到的其值为key的结点的指针，否则返回NULL。算法描述如下： linklist *locate(head,key) linklist *head; datatye key; linklist *p; p=head next;在等概率的情况下，该算法的平均时间复杂度亦为O(n)（2）按值查找 LOCATE（head，key）2.3.2 单链表上的基本运算（实现）while (p!=NULL) if (p data!=key) p=p next; else break ; return p; 8/22/202234数据结构 3.

14、插入运算 （1）后插操作: 在指针p所指结点之后插入xs （2）前插操作: 在指针p所指结点之前插入Headp时间复杂度度O(1)xs平均时间复杂度 O(n)先从头指针起, 顺链找到*p的前趋结点*q.Headpq8/22/202235数据结构Headpax 3.插入运算:将前插操作转变为后插操作xsxsaINSERTBEFORE(p,x)linklist *p;datatype x;linklist *s;s=malloc(sizeof(linklist);s-data=p-data;s-next=p-next;p-data=x;p-next=s;时间复杂度 O(1)应尽量将单链表上的插入操

15、作转化为后插操作！8/22/202236数据结构 4.删除运算时间复杂度 O(1)删除指定结点的直接后继Headprr=p-next;p-next=r-next;free(r);删除指定结点时间复杂度O(n)链表的优点:在链表上实现插入、删除运算无须移动结点，仅须修改指针改进?8/22/202237数据结构2.单循环链表的特点：链表尾结点的next域不为空，而是指向头结点或开始结点。（优点：从任一结点开始，均可找到其前趋和后继结点。）3、引入单循环链表的目的在于方便一些运算的实现。实用中常采用尾指针单循环链表,而不是头指针单循环链表。4、单循环链表上的操作与单链表基本一致 差别仅在于：循环控制

16、条件不是判空，而是判断是否等于头指针或尾指针。2.3.3 单循环链表1.循环链表:是一种首尾相接的链表单循环链表双循环链表8/22/202238数据结构 1. 双链表的特点：每个结点有两个指针域，分别指向其直接 前趋和后继。2.双链表存储结构描述如下： typedef struct dnode datatype data; struct dnode *prior,*next; dlinklist; dlinklist *head; 对于双向链表，当将头、尾结点链起来时，便成了双向循环链表。2.3.4 双链表 priornextdata为了指示双链表，也须引入一个头指针head，指向其开始结点。

17、8/22/202239数据结构3.双向链表基本运算的实现：（1）删除运算（2）插入运算插入和删除都非常方便p-prior-next=p=p-next-prior删除运算DELETENODE（p） /*删除双链表结点*p */dlinklist *p; p-prior-next=p-next; p-next-prior= p -prior; free(p);Headp8/22/202240数据结构插入运算DINSERTBEFORE(p,x)dlinklist *p;datatype x;dlinklist *s;Pxss=malloc(sizeof(dlinklist);s-data=x;s-p

18、rior=p -prior;s-next=p;p -prior -next=s;p -prior=s;8/22/202241数据结构2.3.5 静态链表 实现方法 存储空间 分配和释放 静态链表 游 标 预分配的一个连续空间 用户定义 动态链表 指 针 内存所有可用空间 系统提供 静态链表与动态链表的区别8/22/202242数据结构 2、静态链表存储结构描述如下：define maxsize 1024typedef int datatype;typedef int cursor ; typedef struct datatype data; 数据域 cursor next; 游标 node;

19、 node nodepoolmaxsize; 存储池 cursor av; 游标变量 2.3.5 静态链表1、用数组和“游标”实现链式存储的方法是： 事先定义一个规模较大的结构数组作为备用结点空间（即存储池），当申请结点空间时，从存储池中取出结点，当释放结点空间时，将其归还于存储池内。采用这种方法实现的链表称为静态链表。12Maxsize-13NULL012Maxsize-1av0nodepoolmaxsize8/22/202243数据结构说明:静态链表也可以用头指针L唯一指示 ,L为cursor类型 3、可用空间表:将存储池中所有空闲结点链成一个头指针为av的单链表,构成一个可用空间表8/2

20、2/202244数据结构2.3.5 静态链表12Maxsize-13NULL012Maxsize-1av1nodepoolmaxsize初始化：INITALIZE() int i; for (i=0;idata=x; p-next=top; return p;8/22/202256数据结构Linkstack *POPLSTACK(top,datap)linkstack *top;datatype *datap; linkstack *p; if(top=NULL) printf(“underflow”); return NULL; else *datap=top-data; p=top; to

21、p=top-next; free(p); return top; 2） 退栈 *POPLSTACK(top,datap)8/22/202257数据结构3.2 栈的应用举例1. 文字编辑器2. 函数的递归调用（p47)8/22/202258数据结构3.3 队 列1定义：队列(queue) 是一端进行删除另一端进行插入的线性表。允许插入的一端称为队尾(rear) ，允许删除的一端称为队头(front)。2特点： 先入队(即插入队尾）的元素必将被先删除(即出队）。因此，队列是一种先进先出(First In First Out)的线性表。3.3.1 队列的概念及运算出队入队队头队尾a1 a2 an8/

22、22/202259数据结构 3队列的基本运算： （1）SETNULL（Q）置队空 （2）EMPTY（Q）判队空 （3）FRONT（Q）取队头元素,队中元素保持不变 （4）ENQUEUE（Q,x) 将元素x入队 （5）DEQUEUE（Q）出队,函数返回原队头元素8/22/202260数据结构3.3.2 顺 序 队 列1 定义：采用顺序存储结构的队列称为顺序队列。 规定：front总是指向当前队头元素的前一个位置 rear指向当前队尾元素的位置2 顺序队列存储结构描述如下： typedef struct datatype datamaxsize; int front,rear; sequeue;

23、sequeue *sq;8/22/202261数据结构4 3 2 1 0sq-rearsq-front sq-rear4 3 2 1 0DCBA4 3 2 1 0DC 空队列 ABCD入队 AB出栈sq-front sq-front sq-rear3 顺序队列指针图示4 顺序队列基本运算初始时，sqrear=sq front=-1,在不考虑溢出的情况下，入队和出队的运算如下： 入队： sq rear+; sq datasq rear=x;出队： sq front+;8/22/202262数据结构队空： sq rear=sq front队满： sq rear sq front=maxsize下溢

24、： 队空时，若要进行出队操作时发生上溢： 队满时，进行入队操作时出现。“假上溢”：当 sq-rear=maxsize-1但队列并不满时进行入队操作.sqrear=4sqfront=143210edcba这种情况（即sq-rear=maxsize-1)下若要进行入队运算,sqrear的值将超出下标范围，故不能进行这种运算，但此时整个队列空间并没用完。 4 几种特殊情况8/22/202263数据结构解决“假上溢”的方法有两种： （1）当元素出队或出现假上溢时，移动队列元素。 sqrear=4sqfront=143210edcbaedc43210sqrear=2sqfront= -1移动元素后（2）

25、采用循环队列：即sq-data0 接在sq-datamaxsize-1之后循环队列的示意图054321sqrear=0sqfront=48/22/202264数据结构采用循环队列后，进行入队和出队运算时，头、尾指针加1操作应如下进行： 出队： sq front=(sq front+1)% maxsize; 入队： sq rear=(sq rear+1)% maxsize;循环队列如何判断队空和队满? 方法一：引入标志flag 若 (sq front=sq rear)&(flag=0),则队空,不能出栈。 若 (sq front=sq rear)&(flag=1),则队满,不能入栈。054321

26、sqrear=5sqfront=5054321sqfront=5sqrear=48/22/202265数据结构 方法二：牺牲一个元素的空间（sq-datasq-front)，避免队满时头、尾指针指向同一位置。 若 sq front=sq rear，则队空。 若 (sq rear+1)%maxsize= sq front，则队满。054321sqrear=1sqfront=1054321sqfront=5sqrear=48/22/202266数据结构3.3.3 链 队 列1 、定义：采用链式存储结构的队列称为链队列。（是限制在表头删除在表尾插入的单链表）2 、链队列存储结构描述 typedef

27、struct linklist *front,*rear; linkqueue; linkqueue *q; 为了运算实现的方便，在队头结点前引入一个头结点。初始时（即队空）链队的头、尾指针均指向头结点。 front rear q头结点qrearfront rear q头结点 qfront队头结点q-front=q-rear8/22/202267数据结构1）入队ENQUEUE（q,x)类似于单链表的尾插法8/22/202268数据结构2）出队qrearfront rear q头结点 qfront队头结点*sfront rear q头结点a1*s front rear q头结点S=q-front

28、-next; q-front-next=s-next; free(s);队列长度等于1时，不但修改头结点的指针域，还需尾指针。队列长度大于1时，只需修改头结点的指针域，尾指针不变。8/22/202269数据结构解决方法：出队时只修改头指针，删除头结点，使链队列上的队头结点成为新的链表的头结点，队列上的第2个结点成为队头结点。即物理上删除头结点，逻辑上删除对头结点。即使当前队列长度为1，也不用修改尾指针。qrearfront rear q头结点 队头结点*s8/22/202270数据结构串(即字符串）是一种特殊的线性表，其每个结点仅由一个字符组成。4.1 串及其运算4.1.1 串的基本概念 1.

29、串(string):是由零个或多个字符组成的有限序列。 一般记为S=“a1a2.an”, 其中：S为串名，a1a2an为串值；ai(1=i=n)可 以是字母、数字和其它字符； 注意：仅含一个空格的串（“”）和空串（“ ”）是不同的两个串。2.串长度：串中所含的字符个数 空串：长度为零的串（不含任何字符，和空格串严格区分）第四章 串8/22/202271数据结构4.子串在主串中的序号：子串在主串中第一次出现时其第一个字符在主串中的序号。S1=“Iamastudent.”S2=“student”S2在S1中的序号为83.子串： 串中任意个连续的字符组成的子序列,该串相应称为主串。空串为任意串的子串

30、，任意串为其自身的子串。两串相等当且仅当两串长度相等且对应位置上的字符相同。5. 在程序中使用的串可分为串常量和串变量S2=“student”将串常量命名为S2char object=“datastructure”第四章 串8/22/202272数据结构4.1.2 串的基本运算 串的基本运算有九种，具体如下（p61）（1）赋值：=（2）联接： strcat(ST1,ST2) （3）求串长：strlen(S) （4）求子串：substr(S,i,j) （5）比较串的大小：strcmp(S,T) （6）插入：insert(S1,i,S2) （7）删除：delete(S,i,j) （9）置换：rep

31、lace(S1,i,j,S2)， repl(S,T,V) 8/22/202273数据结构4.2 串的存储结构 串可以分别采用顺序、链式和索引存储结构实现存储。1）用字符数组描述1、顺序存储 串中的字符被顺序地存储在内存中相邻的存储单元中。采用顺序存储结构的串称为顺序串。 H o w a r e y o u ? . 串S的顺序存储示意图S=“How are you?”#define maxsize 32char smaxsize;8/22/202274数据结构 ） 顺序串存储结构描述： #define maxsize 128;typedef struct char chmaxsize; int

32、curlen; seqstring;串字符存储空间串长度 缺点： 顺序串上插入、删除运算不方便。8/22/202275数据结构 2. 链式存储 采用链式存储结构的串称为链串，链串中结点的数据域既可存储单个字符，也可存储多个字符，结点数据域存储字符的个数称为结点的大小。 显然，结点大小大于1的链串，其结点的存储密度提高了，但同时也带来了问题： (1) 如何处理链串的最后一个结点，因为串所含字符数不一定是结点大小的整数倍。 (2) 插入、删除运算实现起来不方便。(p64)8/22/202276数据结构 typedef struct linknode char data; struct linkno

33、de *next; linkstring; linkstring *s;如果结点大小不为1，则此处应说明一个字符数组。 链串存储结构描述如下： 8/22/202277数据结构 1）带长度的名字表 2）带末指针的名字表 3）带特征位的名字表 4）带位移量的名字表 3. 索引存储特点：将串的串名作为关键字组织名字表(即索引表)，名字表中的每一项记录了串名和串值存放单元的起址及确定串长的有关数据。 名字表一般采用顺序存储方式存储。其组织形式主要有如下几种：(p65)8/22/202278数据结构 本节讨论子串定位运算(也称模式匹配)在顺序串上的实现,及在链串上的实现子串定位运算的含意：4.3 串运算

34、的实现设有两个顺序串S和T，且： S=“s0s1s2.sn-1” 目标 T=“t0t1t2.tm-1” 模式 匹配有两种结果：若在S中找到了模式为T的子串（若有多个模式为T的子串，只需找出第一个）时，则返回该子串在S中的位置，这种情况称为匹配成功；否则称为匹配失败。8/22/202279数据结构 1. 朴素的匹配算法基本思想：初始时，从S的第一个字符开始将T的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在S中的位置，否则，将T向右移动一个字符位置，从T的第一个字符开始与S中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二趟匹配，成功则返回子串在S

35、中的位置，否则，T再向右移动一个字符位置，进行第三趟匹配，如此反复，或匹配成功，或当T右移到无法与S继续进行比较时，匹配失败。 a b a b c a b c a c b a b a b c a c8/22/202280数据结构 1. 朴素的匹配算法基本思想：初始时，从S的第一个字符开始将T的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在S中的位置，否则，将T向右移动一个字符位置，从T的第一个字符开始与S中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二趟匹配，成功则返回子串在S中的位置，否则，T再向右移动一个字符位置，进行第三趟匹配，如此反复，

36、或匹配成功，或当T右移到无法与S继续进行比较时，匹配失败。 a b a b c a b c a c b a b a b c a c8/22/202281数据结构 a b a b c a b c a c b a b 设S=“ababcabcacbab” T=“abcac” a b c a ci=0j=0i=1j=1i=2j=2i指针回溯的位置为：i=i-j+1（i的值为1） 1. 朴素的匹配算法8/22/202282数据结构 a b a b c a b c a c b a b 设S=“ababcabcacbab” T=“abcac” a b c a ci=1j=0i指针回溯的位置为：i=i-j+

37、1（i的值为2）8/22/202283数据结构设S=“ababcabcacbab” T=“abcac” a b a b c a b c a c b a b a b c a ci=2j=0i=3j=1i=4j=2i=5j=3i=6j=4i指针回溯的位置为：i=i-j+1（i的值为3）8/22/202284数据结构 a b a b c a b c a c b a b 设S=“ababcabcacbab” T=“abcac” a b c a ci=3j=0i指针回溯的位置为：i=i-j+1（i的值为4）8/22/202285数据结构 a b a b c a b c a c b a b 设S=“aba

38、bcabcacbab” T=“abcac” a b c a ci=4j=0i指针回溯的位置为：i=i-j+1（i的值为5）8/22/202286数据结构 a b a b c a b c a c b a b 设S=“ababcabcacbab” T=“abcac” a b c a ci=5j=0i=6j=1i=7j=2i=8j=3i=9j=4i=10j=5返回子串的位置为：i-j+1=6（串的起始位置从1开始算起）8/22/202287数据结构 int index(s,t) seqstring *s,*t; int i=0,j=0;while (iscurlen)&(jt curlen) if

39、(s chi=t chj i+;j+; else i=i-j+1;j=0; if (j=t curlen) return (i-j+1) else return (-1); 朴素的模式匹配算法描述如下：8/22/202288数据结构5.1 多 维 数 组一、多维数组的概念多维数组可以看成是向量（一维数组）的扩展1、二维数组： 可以看成是m个行向量和n个列向量组成的向量逻辑特征： 除边界外，每个元素aij恰好有两个直接前趋和两个直接后继。ai-1,jai,jai+1,jai,j-1ai,j+1Amn=a11 a12 a1na21 a22 a2n am1 am2 amn8/22/202289数据结

40、构2.三维及多维数组三维数组Amnp: 可看成有p个二维数组（m*n)所组成的向量每个元素aijk同属于三个向量（二维数组）最多有3个直接前趋和直接后继（除角、边、面上的结点）推广：多维数组An1n2nm可看成nm个（m-1）维数组所构成的向量任一元素ai1i2im都属于m个向量，最多有m个直接前趋和m个直接后继8/22/202290数据结构对于数组，通常只有两种操作： (1)取值：给定一组下标，存取相应的数据元素； (2)修改：给定一组下标，修改相应数据元素中的某一个或几个数据项的值。二、多维数组的运算说明：对于数组，通常只进行读、写操作，不进行元素的插入和删除操作。因此，一般采用顺序存储结

41、构表示数组。8/22/202291数据结构1、两种顺序存储方法： (1) 行优先顺序(row major order) (c,pascal语言采用） 特点：将数组元素按行向量排列 (以二维数组为例）(2) 列优先顺序(column major order) (fortran语言采用） 特点：将数组元素按列向量排列 (以二维数组为例）a11 a12 . a1n a21 a22 a2n am1 am2 amn 第1行 第2行 第m行a11 a21 . am1 a12 a22 am2 a1n a2n amn 第1列 第2列 第n列三、顺序存储方法8/22/202292数据结构2、特点 顺序存储的数组

42、是一个随机存取结构，即只要知道开始元素的存储起址、维数和每一维的上、下界及单个元素所占单元数，便可将数组元素的存储地址表示为其下标的线性函数。 (以二维数组为例,且数组采用行优先顺序） LOC(aij)=LOC(a11)+(i-1)*n+j-1*dd为单个元素所占单元数开始元素的存储起址n为列数c语言中因数组下标从0开始，因此上面的式子应改为： LOC(aij)=LOC(a00)+(i*n+j)*d8/22/202293数据结构5.2 矩阵的压缩存储压缩存储: 前提：非零元素呈某种规律分布或矩阵中有大量零元素 定义：多个值相同的元素只分配一个存储空间，值为0的 元素不分配空间采用压缩存储的矩阵

43、分为两类：特殊矩阵和稀疏矩阵。 5.2.1 特 殊 矩 阵特殊矩阵：指的是非零元素或零元素的分布有一定规律的矩阵。对特殊矩阵常采用一维数组存储。需解决的问题：如何将二维数组元素下标转换成一维数组元素下标。8/22/202294数据结构 1.对称矩阵 1）定义: 已知n阶方阵A，若其元素满足如下性质： aij=aji 0=i,j=j 则 k=i*(i+1)/2+j b: 若 ij 则 k=j*(j+1)/2+i(这是由对称性质决定的） 注意：进行压缩存储后，没有改变原采用二维数组存储时能进行随机访问的特性。综合a、b，令I=max(i,j), J=min(i,j)，则k=I*(I+1)/2+Jl

44、oc(aij)=loc(sak)=loc(sa0)+k*d =loc(sa0)+(I*(I+1)/2+J)*da00a10 a11a20 a21 a22 aij a n-1,0 a n-1,1 an-1,2 a n-1,n-18/22/202296数据结构2.三角矩阵（方阵） 1）分类：三角矩阵以主对角线划分，可分为上三角矩阵和下三角矩阵。a00 c c ca10 a11 c a20 a21 c a n-1,0 a n-1,1 an-1,2 a n-1,n-18/22/202297数据结构2.三角矩阵（方阵） 2）存储方法： 只需存储非常数三角中的所有元素，另外再加一个存储单元存储常数C。 非

45、常数三角中的所有元素个数为n(n+1)/2,外加一个常数,总共有n(n+1)/2+1个元素，可用一维数组sn*(n+1)/2+1存储，常数存于最后一个存储单元。 1）分类：三角矩阵以主对角线划分，可分为上三角矩阵和下三角矩阵。8/22/202298数据结构上三角矩阵中aij与sk的对应关系：下三角矩阵中aij与sk的对应关系： i*(2n-i+1)/2+j-i ij i*(i+1)/2+j i=j k= n*(n+1)/2 ija00 a01 a0,n-1 c a11 a1,n-1 aii aij c c an-1,n-13)存储地址的计算i*n-(i-1) *i /28/22/202299数

46、据结构3.对角矩阵特点：所有的非零元素都集中在以对角线为中心的带状区域中。带状区域外的所有元素均为零。以三对角矩阵为例（p75)三对角矩阵中所有非零元素为3*n-2,可用一维数组s3*n-2存储.再次强调：特殊矩阵的压缩存储没有改变原采用二维数组存储时所具有的随机存取特性。 8/22/2022100数据结构5.2.2 稀 疏 矩 阵稀疏矩阵的压缩存储通常有两种方式：三元组表和十字链表。稀疏矩阵：非零元素的个数远远少于矩阵元素的总数的矩阵（sm=3; a-n=5; a-t=4; a- data16 8/22/2022105数据结构传统转置方法介绍基本思想：由于A的列是B的行，因此按a-data的

47、列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先顺序存放的。为了找到A的每一列中的所有非零元素，需要对三元组表a-data从第一行起扫描一遍，由于a-data是按A的行优先顺序存放的，因此得到的恰是b-data应有的顺序。时间复杂度：O(n*t)O(m*n) 0 1 2 1 3 1 2 0 -3 2 3 2 i j vA的三元组表 i j v 0 2 -3 1 0 2 3 1 1 3 2 2 B 的三元组表转置后8/22/2022106数据结构 3、十字链表1) 十字链表中结点的结构： i j v/next cptr rptr存储行号存储列号存储元素值或指向下一个表头结点列指针

48、域，指向本列下一个非零元素行指针域，指向本行下一个非零元素4)三元组表的优点：结构简单，易于实现，存储密度高。 缺点：不具有随机存储特性；矩阵中非零元素发生变化时，将会引起三元组表中大量元素的移动。8/22/2022107数据结构十字链表h0 0 0 0 0 0 0 0 0 0 1 2 2 2 4 1 3 1 -3 3 4 2 0 0 0 0 0 0 3 5 H1H1H4H2H3H2H5H3 A= 0 2 0 0 0 0 0 0 1 0 -3 0 0 2 0 i j v/next cptr rptr8/22/2022108数据结构2) 十字链表存储结构描述： typedef struct ln

49、ode int i,j; struct lnode *cptr,*rptr; union struct lnode *next; datatype v ; uval; link; 3)建立十字链表 i j v/next cptr rptr8/22/2022109数据结构建立十字链表的算法分为两步： 1.建立表头结点的循环链表 2.依次读入非零元素的三元组，每读入一个三元组，生成一个表结点，并将其插入相应行、列链表中的正确位置上。8/22/2022110数据结构5.3 广义表的概念广义表(Lists)是n（n=0)个元素a1,a2,an的有限序列，其中ai或者是原子或者是一个广义表，通常记为LS

50、=(a1,a2,an)1、定义：8/22/2022111数据结构补充说明：对于LS=(a1,a2,an)LS:广义表的名字n: 广义表的长度。E=(a,E )如果ai是广义表， 则称它为LS的子表书写时，用大写字母表示广义表，小写字母表示原子若LS非空(n=1)，则a1是LS的表头，（a2,a3,an)构成的表称为LS的表尾表是递归定义的，一个表的深度定义为表展开后所含括号的层数.D=(A,B,C )如果规定任何表都是有名字的，为了即表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名称。 D (A( ),B ( b,c,d), C (a, B(b,c,d) ) )； 8/22/

51、2022112数据结构2、广义表的表示方法图示法：用分支结点表示广义表，非分支结点表示原子。特殊的，空表对应的也是非分支结点。A=( )AB=( b,c,d)BbcdC=(a,(b,c,d) )bcdBCaD=(A,B,C )DABbcdCaE=(a,E )Ea纯表：树对应的广义表，限制了成分的共享与递归 A,B,C再入表：允许结点间共享的表 D 递归表：允许递归的表 E 8/22/2022113数据结构3、广义表的两个特殊的运算取表头head(LS): 任何一个非空广义表的表头是表中第一个元素。取表尾tail(LS)：据表尾定义，必定是子表。例: head(B)=btail(B)=(c,d)

52、head(D)=Atail(D)=（B,C)head( )=( )tail( )=( )线性表纯表 再入表 递归表所以，广义表不仅是线性表的推广，还是树的推广8/22/2022114数据结构5.3 广义表的存储p831、单链表示法（模仿单链表结构）2、双链表示法（类似于第六章的二叉链表）8/22/2022115数据结构第六章 树 树形结构是一种重要的非线性结构，在我们的客观世界和现实生活中大量存在。 树形结构：结点之间有分支，并且具有层次关系的结构8/22/2022116数据结构6.1 树的概念1、树的定义：树(Tree)是n(n0)个结点的有限集合T，它满足如下条件： (1) 有且仅有一个称

53、为根(Root)的结点。 (2) 其余结点可分为m(m=0)个互不相交的有限集合,T1,T2,Tm,其中每个集合又是一棵树，并称其为根的子树（Subtree） 。这是一个递归定义。 有时n=0也称为空树。ABCDEFG集合1集合2集合3一、树的基本概念8/22/2022117数据结构2、树的表示方法1）树形图法2）嵌套集合法3）广义表形式4）凹入表示法(A(B),C(E,F),D(G)ABCDEFGABCEFDGABDGEFC8/22/2022118数据结构1）结点的度(Degree)：为该结点的子树的个数。2）树的度：为该树中结点的最大度数。3）终端结点(叶子)：度为零的结点。4）非终端结点

54、(分支结点)：度不为零的结点。5）内部结点：除根结点之外的分支结点。ACDEFGB3、 树结构的基本术语8/22/2022119数据结构6）孩子(child)：结点的子树之根 双亲（parent):该结点称为孩子的双亲 兄弟(sibling):同一双亲的孩子 堂兄弟（cousin):双亲不同但其双亲处于同一层的结点7）路径(Path)：若树中存在一个结点序列k1,k2,kj,使得ki是ki+1的双亲(1=i=0)棵互不相交的树的集合称为森林。关系：树森林删去一个树根加上一个树根ACDEFGB8/22/2022122数据结构6.2 二 叉 树6.2.1 二叉树的概念一、二叉树的定义： 二叉树(B

55、inary Tree)是n(n=0)个结点的有限集，它或者是空集(n=0)或者由一个根结点和两棵互不相交的，分别称为根的左子树和右子树的二叉树组成。 可以看出，二叉树的定义和树的定义一样，均为递归定义。8/22/2022123数据结构二、二叉树的五种基本形态：空二叉树只有一个根结点的二叉树右子树为空的二叉树左子树为空的二叉树左、右子树均非空的二叉树注意：二叉树中子树是有左右之分的，即使只有一棵子树，或为左子树，或为右子树，这一点与度为2的有序树不同。这不是二叉树这是二叉树8/22/2022124数据结构6.2.2 二叉树的性质性质1：二叉树第i层上的结点数目最多为2i-1 (i=1)性质2：深

56、度为k的二叉树至多有2k-1个结点(k=1)性质3：任意二叉树中，若叶结点的个数为n0,度为2的结点数为n2，则n0=n2+1。8/22/2022125数据结构两种特殊形态的二叉树：满二叉树和完全二叉树 深度为k且有2 k-1个结点的二叉树称为满二叉树。 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。满二叉树1234567非完全二叉树123456完全二叉树234518/22/2022126数据结构两种特殊形态的二叉树：满二叉树和完全二叉树 深度为k且有2 k-1个结点的二叉树称为满二叉树。 对满二叉树的结点

57、进行编号，约定编号从根结点起，自上而下，自左至 右。 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称之为完全二叉树。满二叉树1234567非完全二叉树123456完全二叉树234518/22/2022127数据结构根据定义:(1)满二叉树是完全二叉树,反之不成立; (2)对于完全二叉树,若某结点无左孩子,则必无右孩子,该结点为叶结点;性质4：具有n个结点的完全二叉树的深度为 log2n +1( log2(n+1) )8/22/2022128数据结构性质5：如果对一棵有n个结点的完全二叉树的结点按层次编号(即自上而下，自左至右)，则对

58、任一结点i(1=i1,则其双亲是编号为 i/2 的结点。 (2) 如果2*in,则结点i无左孩子；否则其左孩子是编号为2*i的结点。 (3) 如果2*i+1n,则结点i无右孩子；否则其右孩子是编号为2*i+1的结点。 (4)若i为奇数且不为1,则结点i的左兄弟的编号是i-1;否则,结点i无左兄弟。 (5)若 i为偶数且小于n,则结点i的右兄弟的编号是i+1;否则,结点i无右兄弟。234518/22/2022129数据结构6.2.3 二叉树的存储1. 顺序存储结构1）对于完全二叉树可以采用顺序存储结构(即一维数组)进行存储，编号为i的结点存放在第i个数组元素所分配的存储单元中，完全二叉树结点之间

59、的逻辑关系通过数组元素的下标体现。完全二叉树abcde非完全二叉树abcdef 0 1 2 3 4 5 a b c d e 下标元素 0 1 2 3 4 5 6 7 a b c * d e f 下标元素“虚结点”占据的空间补设的“虚结点”8/22/2022130数据结构2）对于非完全二叉树，通过补设一些“虚结点”，使得二叉树的结点的编号与完全二叉树相同，再进行顺序存储。每个“虚结点”都将占据一个数组元素存储单元。结论：非完全二叉树采用顺序存储结构会造成存储空间的浪费。8/22/2022131数据结构二叉树除了可以采用顺序存储结构实现存储外,还可以采用链式存储结构进行存储,与采用顺序存储结构相比

60、,采用链式存储结构实现二叉树的存储显得更自然.1）链式存储结构中结点的结构: lchild data rchild指向左孩子的指针域指向右孩子的指针域存放数据 2、链式存储结构8/22/2022132数据结构2）结点的存储描述:typedef struct nodedatatype data; struct node *lchild,*rchild; bitree;bitree *root;所有类型为node的结点，再加上一个指向根结点的头指针root，就构成了二叉树的存储结构，称为二叉链表。 lchild data rchild指向左孩子的指针域指向右孩子的指针域存放数据8/22/20221