2020/2/15
数据结构
17
2.1 线性表的概念及运算
一、逻辑结构 1.描述: 线性表是由n (n>=0)个数据元素(点)a1,a2,….,ai,….,an
组成的有限序列。其中，数据元素的个数n定义为表长。 当n=0时称为空表，非空的线性表(n>0)记为： (a1,a2,….,ai,…..,an)
2020/2/15
数据结构
11
第一章 概 论
1.4 算法分析
一、算法评价五要素 （1）正确性 （2）执行算法所耗费的时间 （3）执行算法所耗费的空间 （4）可读性 （5）健壮性
2020/2/15
数据结构
12
第一章 概 论
二、算法的时间复杂度
•一个算法所耗费的时间:该算法中每条语句的执行时间之和。 •每条语句的执行时间：该语句的执行次数乘以该语句执行一次 所需时间。 •频度：语句重复执行的次数 •算法的时间耗费T(n)=每条语句的执行的时间
2020/2/15
数据结构
23
一、链表
2.3 线性表的链式存储
1、 链式存储：用一组任意的存储单元存储线性表, 逻辑上 相邻的结点在物理位置上不一定相邻，结点间 的逻辑关系由存储结点时附加的指针字段表示
2、链表：采用链式存储方法的线性表称为链表。
2020/2/15
数据结构
24
2.3.1 单链表
1、单链表的特点：每个结点只有一个链域，指向其直接后继 （尾结点除外）。
依据数据集中可能出现的最坏情况估算出的时间复杂度 称为最坏时间复杂度。
五、平均时间复杂度
在假设数据集的分布是等概率的条件下，估算出的时间 复杂度称为平均时间复杂度。
例：顺序查找
2020/2/15
数据结构
14
第一章 概 论
五、空间复杂度S(n)： 算法所耗费的存储空间，仍是问题规模n的函数。
2020/2/15
申请一个结点 p=(linklist *)malloc(sizeof(linklist)); 释放一个结点 free(p);
2020/2/15
数据结构
26
2.3.2 单链表上的基本运算（实现）
1.建立单链表
方法:从一个空表开始,重复读入数据,生成新结点,将读入数 据存放在新结点的数据域,然后将新结点插入当前链表 中,直到结束。
Head a
r
b
c^
sr d ^
•不带头结点的尾插法：插入时，第一个结点的处理与其 它结点的处理有区别。
结束时，空表和非空表的处理有区别。
2020/2/15
数据结构
29
Linklist *CREATLISTR( )
{ char ch;
linklist *head,*s,*r;
head=NULL; r=NULL; ch=getchar( );
注意: 1.数据元素ai是一个抽象的符号 2. ai可取各种数据类型 3. 一般情况下,同一线性表中的元素具有相同的数据类型 4. i是元素的序号 (1<=i<=n)
2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结 点都最多只有一个直接前趋和一个直接后继
2020/2/15
数据结构
18
二、线性表的运算
2020/2/15
数据结构
8
例：一个学生成绩表： •是一个数据结构 •每行是一个结点（或记录），由学号、姓名、各科成绩 及平均成绩等数据项组成。 •逻辑关系：线性结构 •存储结构： •表的运算：
2020/2/15
数据结构
9
第一章 概 论
1.3 算法描述
逻辑结构上定义的基本运算在存储结构上的 实现是通过算法来描述的。
数据结构
2020/2/15
数据结构
1
讲课安排：
•串讲全书内容 •典型习题分析 •前年、去年考题分析
2020/2/15
数据结构
2
第一章 概 论
•数据结构及其概念 • 如何评价一个算法
2020/2/15
数据结构
3
第一章 概 论
一、术语
1.1 数据结构的概念
1.数据(Data): 是信息的载体，能被计算机识别、存储、加工处理。
它位置上的操作相一致。
2）空表和非空表的处理相一致。
2020/2/15
数据结构
31
2.3.2 单链表上的基本运算（实现）
Linklist *CREATLISTR1()
{ char ch;
linklist *head,*s,*r;
head=malloc(sizeof(linklist));
2020/2/15
数据结构
19
2.2 线性表的顺序存储
一、顺序表
1、顺序存储：将线性表的结点按逻辑次序依次存放在一组地 址连续的存储单元里。
2、顺序表：采用顺序存储方法存储的线性表称顺序表。
3、存储地址的计算：
LOC(ai)=LOC(a1)+(i-1)*c
1<=i<=n
这里：LOC(a1)为结点a1的存储起址(基地址），c为 每个结点所占存储单元数。
=（语句频度×语句执行一次所需时间） =语句频度 •算法的时间复杂度：就是算法的时间耗费T(n)
2020/2/15
数据结构
13
第一章 概 论
三、（渐进）时间复杂度(O(f(n))
当问题的规模n趋向无穷大时，时间复杂度T(n)的数量 级（阶）称为算法的渐近时间复杂度，简称时间复杂度
四、最坏时间复杂度
INSERT(L,x,i)
DELETE(L,i)
2020/2/15
数据结构
22
顺序表的特点： 用物理位置上的邻接关系表示结点间的逻辑关系
顺序表的优点： （1）无须增加额外的存储空间表示结点间的逻辑关系。
（2）可以方便地随机存取表中任一结点。
顺序表的缺点： （1）插入和删除运算不方便，通常须移动大量结点，效率 较低。 （2）难以进行连续的存储空间的预分配，尤其是当表变化 较大时。
2020/2/15
数据结构
25
typedef int datatype; typedef struct node {datatype data; struct node *next; } linklist; linklist *head, *p;
说明：•区分指针变量和结点变量 :p ,*p •结点的动态分配和释放
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;
集合上的一组操作。
4、数据结构
原子数据类型(atomic data type) 结构数据类型(aggregate data type)
• 数据的逻辑结构
• 数据的存储结构
• 数据的运算：既对数据施加的操作
2020/2/15
数据结构
5
逻辑结构：(有时直接称为数据结构） •线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继) •非线性结构：树 、图、多维数组、广义表 说明： 1、逻辑结构与数据元素本身的形式、内容无关 2、逻辑结构与数据元素的相对位置无关 3、逻辑结构与所含结点个数无关
（1）头插法建表 （2）尾插法建表
头插法建表：将新结点插入到当前链表的表头
Head c
b
a^
2
sd
1
优点：算法简单
缺点： 链表中结点次序和输入次序相反
2020/2/15
数据结构
27
Linklist *CREATLIST( )
Head c
b
a^
{ char ch;
2
sd
1
linklist *head,*s; head=NULL; ch=getchar( );
while (ch!=‘$’) {s=malloc(sizeof(linklist));
s->data=ch;
s->next=head;
head=s;
ch=getchar( );
}
return head;
}
2020/2/15
数据结构
28
பைடு நூலகம்
2.3.2 单链表上的基本运算（实现）
尾插法建表：将新结点插入到当前链表的表尾（需引入r）
} sequenlist;
Maxsize-1
last
说明: (1).datatype是表中的数据类型,依具体情况而定 (2).向量下标可以看作表中结点的相对地址
(3). 顺序表的长度为last+1
(4).结点的引用:定义一个顺序表：sequenlist *L;
(*L).data[0] a1
(*L).data[1] a2
线性表的常见基本运算包括：
（1）置空表SETNULL(L) （2）建表CREATLIST(L) （3）求表长LENGTH(L) （4）取结点GET(L,i) （5）定位LOCATE(L,x) （6）插入INSERT(L,x,i) （7）删除DELETE(L,i)
复杂的运算可以由这些基本运算组合来实现
2、结点结构：
data
3、图示法表示单链表
head a1
a2
next .....
an ^
4、单链表的存储结构描述如下： typedef int dataype;
typedef struct node {datatype data; 因为单链表由头指针唯一决定 struct node *next; } linklist; linklist *head, *p;