计算机软件技术基础 数据结构与算法（2）.

Presentation on theme: "计算机软件技术基础 数据结构与算法（2）."— Presentation transcript:

1 计算机软件技术基础 数据结构与算法（2）

2 数据结构课程的起点

3 简言之，线性结构反映结点间的逻辑关系是 的。
线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 →可表示为：（a1 , a2 , ……, an） 特点① 只有一个首结点和尾结点； 特点② 除首尾结点外，其他结点只有一个直接前驱和一 个直接后继。 一对一 (1:1) 简言之，线性结构反映结点间的逻辑关系是 的。 线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------ 线性表

4 2.2 线性表 线性表的逻辑结构 线性表的顺序表示和实现 线性表的链式表示和实现 应用举例

5 2.2.1 线性表的逻辑结构 （a1, a2, … ai-1，ai, ai＋1 ，…, an）
线性表的逻辑结构 线性表的定义：用数据元素的有限序列表示 （a1, a2, … ai-1，ai, ai＋1 ，…, an） 数据元素 线性起点 ai的直接前趋 ai的直接后继 线性终点 n为元素总个数，即表长。n≥0 下标，是元素的序号，表示元素在表中的位置 空 表 n=0时称为

6 分析：数据元素都是同类型（记录），元素间关系是线性的。 注意：同一线性表中的元素必定具有相同数据类型 ！
例1 分析26 个英文字母组成的英文表是什么结构。 （ A, B, C, D, …… , Z） 分析： 数据元素都是同类型（字母）， 元素间关系是线性的。 例2 分析学生情况登记表是什么结构。 学号 姓名 性别 年龄 班级 陈建武 男 19 2003级电信0301班 赵玉凤 女 18 2003级电信0302班 王 泽 2003级电信0303班 薛 荃 2003级电信0304班 王 春 2003级电信0305班 ： 分析：数据元素都是同类型（记录），元素间关系是线性的。 注意：同一线性表中的元素必定具有相同数据类型 ！

7 线性表的顺序表示和实现 1. 顺序表的表示 2. 顺序表的实现 3. 顺序表的运算效率分析

8 1. 顺序表的表示 线性表的顺序表示又称为顺序存储结构或顺序映像。 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
顺序存储定义： 特点： 逻辑上相邻的元素，物理上也相邻 用一组地址连续的存储单元依次存储线性表的元素。 顺序存储方法： 可以用数组类型来实现

9 LOC ( ai ) = LOC( a1 ) + L *（i -1）
线性表顺序存储特点： 逻辑上相邻的数据元素，其物理上也相邻； 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出。 设首元素a1的存放地址为LOC(a1)（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC ( ai ) = LOC( a1 ) + L *（i -1） 对上述公式的解释如图所示

10 线性表的顺序存储结构示意图 地址 内容 元素在表中的位序 b=LOC(a1) a1 a2 …… ai ai+1 an L 1 b+L 2
地址 内容 元素在表中的位序 b=LOC(a1) a1 a2 …… ai ai+1 an L 1 b+L 2 b+(i-1)L i i+1 b+(n-1)L n 空闲区 b +(max-1)L LOC ( ai ) = LOC( a1 ) + L *（i -1）

11 LOC(ai) = LOC(a1) + L *(i-1)
设有一维数组Ｍ，下标的范围是0到9，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素Ｍ[0]的第一个字节的地址是98，则Ｍ[3]的第一个字节的地址是多少？ 例1 113 解：已知地址计算通式为： LOC(ai) = LOC(a1) + L *(i-1) 但此题要注意下标起点略有不同： LOC( M[3] ) = ×(4-1) =113

12 1) 修改 通过数组的下标便可访问某个特定元素并修改之。
2 顺序表的实现（或操作） 数据结构的基本运算： 修改、插入、删除、查找、排序 1) 修改 通过数组的下标便可访问某个特定元素并修改之。 核心语句: a[i]=x; 显然，顺序表修改操作的时间效率是 O(1)

13 for (j=n; j>=i; j--) a[j+1]=a[ j ]; a[ i ]=x; n++;
2)插入 在线性表的第i个位置前插入一个元素 实现步骤： 将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满? 应当有1≤i≤n+1 或 i=[1, n+1] for (j=n; j>=i; j--) a[j+1]=a[ j ]; a[ i ]=x; n++; 核心语句 // 元素后移一个位置 // 插入x // 表长加1

14 for ( j=i+1; j<=n; j++ ) a[j-1]=a[j]; n--;
3)删除 删除线性表的第i个位置上的元素 实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当有1≤i≤n 或 i=[1, n] for ( j=i+1; j<=n; j++ ) a[j-1]=a[j]; n--; 核 心 语 句 // 元素前移一个位置 // 表长减1

15 3 顺序表的运算效率分析 时间效率分析: 算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）
3 顺序表的运算效率分析 时间效率分析: 算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置。 讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素，则向后移动元素的次数f(n)为: f(n) = n – i + 1 思考：若插入在尾结点之后，则根本无需移动（特别快）； 若插入在首结点之前，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数。

16 推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均。
若在首结点前插入，需要移动的元素最多，后移n次； 若在a1后面插入，要后移n-1个元素，后移次数为n-1; …… 若在an-1后面插入，要后移1个元素； 若在尾结点an之后插入，则后移0个元素； 所有可能的元素移动次数合计： 0+1+…+n = n(n+1)/2 共有多少种插入形式?——连头带尾有n+1种! 故插入时的平均移动次数为：n(n+1)/2÷(n+1)＝n/2≈O(n) 想一想：删除结点的平均执行时间是多少？

17 顺序表小结 链式存储结构 线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点： 1.存储密度大；
2.可以随机存取表中任一元素，方便快捷； 缺点： 1.在插入或删除某一元素时，需要移动大量元素; 2.需要一片连续的存储空间； 3.有“溢出”问题。 解决问题的思路：改用另一种线性存储方式： 链式存储结构

18 线性表的链式表示和实现 1. 链表的表示 2. 链表的实现 3. 链表的运算效率分析

19 指针域：存储直接后继或者直接前驱的存储位置
1 链表的表示 链式存储结构特点： 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。 如何实现？ 通过指针来实现！ 让每个存储结点都包含两部分：数据域和指针域 指针 数据 或 样式： 数据域：存储元素数值数据 指针域：存储直接后继或者直接前驱的存储位置

20 解：该字母表的逻辑结构为：（ a, b, … ,y, z）
链表存放示意图如下： a1 head a2 /\ an …… 例：请画出26 个英文字母表的链式存储结构。 解：该字母表的逻辑结构为：（ a, b, … ,y, z） 该字母表在内存中链式存放的样式举例如下： 讨论1 ：每个存储结点包含两部分：数据域和 。 指针域 讨论2：在单链表中，除了首结点外，任一结点的存储位置 由 指示。 其前驱结点的指针域的值

21 (2) 与链式存储有关的术语： 1）结点：数据元素的存储映像。由数据域和指针域两部分组成； 2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。 3）单链表、循环链表、双向链表： 结点只有一个指针域的链表，称为单链表； 首尾相接的链表称为循环链表； 有两个指针域，分别指向本结点的前驱结点和后继结点的链表，称为双向链表。 循环链表示意图： a1 head a2 an …… head

22 4）头指针、首结点、 表头结点 示意图如下： a1 head a2 … info an ^ 头指针 表头结点 首结点 头指针 是指向链表中第一个结点（或为表头结点、或为首结点）的指针。 首结点 是指链表中存储线性表第一个数据元素a1的结点。 表头结点 是在链表的首结点之前附设的一个结点，其数据域内只放空表标志和表长等信息，它不计入表长度。表头结点的作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首结点进行统一处理，方便编程。

23 讨论. 如何表示空表？ 答： ^ ^ 无表头结点时，当头指针的值为空（NULL）时表示空表；
有表头结点时，当表头结点的指针域为空时表示空表。 ^ 头指针 无表头结点 ^ 头指针 表头结点 有表头结点 表头结点不计入链表长度！

24 答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。
（3）举例 例1： 一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？ 存储地址 数据域 指针域 1 LI 43 7 QIAN 13 SUN 19 WANG NULL 25 WU 37 31 ZHAO ZHENG ZHOU 答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。 7 ZHAO H 31 头指针H的值是31

25 例2： 线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。 其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？ Z 47 Y 31 V 23 X 17 U 05 100 104 108 112 116 119 116 NULL(0) 100 答：X= Y= Z= , 首址= 末址= 。 108 112

26 讨论: 链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？
讨论: 链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？ 答： 因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。 以26个字母的链表为例，每个结点都有两个分量： ‘a’ ‘b’ q p 字符型 指针型 p *next data node 设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，这两个分量如何赋值？ 方式1： 直接表示为 node.data='a'; node.next=q 方式2： p指向结点首地址，然后 p->data='a'; p->next=q 方式3： p指向结点首地址，然后 (*p).data='a'; (*p).next=q

27 sizeof(x)——计算变量x的长度（字节数）； malloc(m) —申请m字节长度的地址空间，并返回这段空间的首地址；
练习： 设p为指向链表的第i个元素的指针,则第i个元素的数据域写为 ，指针域写为 。 p->data p->next ai的值 ai+1的地址 附1：介绍C的三个有用的库函数/算符（都在<stdlib.h> 中）： sizeof(x)——计算变量x的长度（字节数）； malloc(m) —申请m字节长度的地址空间，并返回这段空间的首地址； free(p) ——释放指针p所指变量的存储空间，即彻底删除一个变量。

28 typedef struct abc //abc是自定义结构类型名称 { char data; //定义数据域的变量名及其类型
① 类型定义和变量说明可以合写为： typedef struct abc //abc是自定义结构类型名称 { char data; //定义数据域的变量名及其类型 struct abc *next; //定义指针域的变量名及其类型 }node, *pointer; /*node是abc结构类型的类型替代, *pointer是指针型的abc结构类型的替代，也是数据类型*/ ② 对于指向结构类型的指针变量，可说明为： node *p, *q; //或用 struct abc *p , *q; //注：上面已经定义了node为用户自定义的abc类型。

29 2 链表的实现 （1） 单链表的建立和输出 例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z），请写出C语言程序。
2 链表的实现 （1） 单链表的建立和输出 例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z），请写出C语言程序。 实现思路：先开辟头指针，然后陆续为每个结点申请存储空间并及时赋值，后继结点的地址要提前送给前面的指针。

30 将全局变量及函数提前说明： #include<stdio.h> #include<stdlib.h> typedef struct node { char data; struct node *next; }node; node *p,*q,*head; //一般需要3个指针变量 int n ; // 数据元素的个数 int m=sizeof(node); /*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/

31 void build( ) //字母链表的生成。要一个个慢慢链入
{ int i; head=(node*)malloc(m); //m=sizeof(node) 前面已求出 p=head; for( i=1; i<26; i++) //因尾结点要特殊处理，故i≠26 { p->data=i+‘a’-1; // 第一个结点值为字符a p->next=(node*)malloc(m); //为后继结点“挖坑”！ p=p->next；} //让指针变量P指向后一个结点 p->data=i+‘a’-1; //最后一个元素要单独处理 p->next=NULL ;} //单链表尾结点的指针域要置空！

32 （2） 单链表的修改(或读取） 思路：要修改第i个数据元素，必须从头指针起一直找到该
结点的指针p，然后才能执行p->data=new_value 。 修改第i个数据元素的操作函数可写为： int GetElem_L(LinkList L, int i, ElemType &e) {p=L->next; j=1; //带头结点的链表 while(p&&j<i){p=p->next; ++j;} if( !p || j>i ) return -1; p->data =e; //若是读取则为：e=p->data; return 0;} 缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取 。

33 Step 1：s->next=p->next; Step 2：p->next=s ；
（3） 单链表的插入 在链表中插入一个元素X 的示意图如下： a b p b a p 插 入 X p->next X s s->next 链表插入的核心语句： X 结点的生成方式： s=(node*)malloc(m); s->data=X ; s->next= ? Step 1：s->next=p->next; Step 2：p->next=s ； 思考：Step1和2能互换么？

34 (p->next) -> next 删除动作的核心语句（要借助辅助指针变量q）：
（4） 单链表的删除 在链表中删除某元素b的示意图如下： c a b p × × p->next (p->next) -> next q 删除动作的核心语句（要借助辅助指针变量q）： q = p->next; //首先保存b的指针，靠它才能找到c； p->next=q->next; //将a、c两结点相连，淘汰b结点； free(q) ； //彻底释放b结点空间 思考： 省略free(q)语句行不行？

35 3 链表的运算效率分析 （1） 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 （2） 插入和删除
3 链表的运算效率分析 （1） 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 （2） 插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 但是，如果要在单链表中进行定位插入或删除操作，因为要先查找结点，算法时间复杂度将是 O(n)。

36 线性表小结 线性结构(包括表、栈、队、数组）的定义和特点：有且仅有一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。
逻辑结构：“一对一” 或 “1:1” 存储结构：顺序、链式 运 算：修改、插入、删除[查找和排序另述] 2. 线性表 特征：逻辑上相邻，物理上也相邻； 优点：随机查找修改快 O(1) 缺点：插入、删除慢 O(n) 3.顺序存储 改进方案：链表存储结构

37 作业 第一、二次上机内容 教材P132 习题3，4，5 第4周星期五交 实验一 线性表的应用 特征：逻辑上相邻，物理上未必相邻；
优点：插入、删除快 O(1) 缺点：随机查找修改慢 O(n) 4.链式存储 作业 教材P132 习题3，4，5 第4周星期五交 第一、二次上机内容 实验一 线性表的应用