《教学课件第1章线性数据结构一》由会员分享，可在线阅读，更多相关《教学课件第1章线性数据结构一（70页珍藏版）》请在金锄头文库上搜索。
1、第第1章章 线性数据结构（一）线性数据结构（一）l教材教材: 1.1 数据结构概述数据结构概述l 1.2 线性表线性表l教学目标：教学目标：l 了解数据结构的有关概念了解数据结构的有关概念l 了解线性了解线性DS的概念、特点的概念、特点l 掌握线性表的逻辑结构、物理结掌握线性表的逻辑结构、物理结构以及操作构以及操作1学习要求学习要求l1. 掌握以下掌握以下基本概念基本概念数据元素、数据元素、DS、逻辑结构、物理结构、逻辑结构、物理结构l2. DS的分类及特点、时间复杂度等的分类及特点、时间复杂度等l3. 线性线性DS的常用存储结构的常用存储结构 顺序、链表、索引、散列存储结构顺序、链表、索引、
2、散列存储结构 单向、双向、循环链表等单向、双向、循环链表等l4. 线性线性DS的有关算法的有关算法 增、删、改增、删、改21.1 数据结构概述数据结构概述l一、基本概念一、基本概念l1. 数据（数据（Data） 存储在计算机中、并被计算机处理的存储在计算机中、并被计算机处理的符号的集合符号的集合,是客观事物的符号表示。是客观事物的符号表示。l2. 数据元素（数据元素（Element） 组成数据的基本单位组成数据的基本单位 可由若干个数据项组成可由若干个数据项组成 数据集合中的个体数据集合中的个体,对应结点对应结点(节点节点)。3二二. 数据结构数据结构l1. 数据结构（数据结构（Data St
3、ructure） 1) 研究数据及数据元素之间的关系研究数据及数据元素之间的关系. 2) 组成要素：组成要素： DS=数据的逻辑结构数据的逻辑结构+ 存储结构存储结构+ 数据的运算数据的运算 42. 数据的逻辑结构数据的逻辑结构l1) 描述数据间的逻辑关系，只是抽象描述数据间的逻辑关系，只是抽象地反映数据元素的结构，而不管它们地反映数据元素的结构，而不管它们在计算机中如何存放。在计算机中如何存放。l2) 定义定义: l DS=（D，R）l 其中：其中：l D：数据元素的有限集合；：数据元素的有限集合；l R：数据元素之间关系的集合。：数据元素之间关系的集合。53.数据结构分类数据结构分类l l
4、 线性表线性表堆栈堆栈队列队列串串数组数组树树二叉树二叉树图图线性结构线性结构非线性结构非线性结构数据结构数据结构 DS64. 数据的存储结构数据的存储结构l又称物理结构又称物理结构l是指数据结构在计算机中的表示是指数据结构在计算机中的表示(又称又称映象映象),即数据在计算机中的存放方式。即数据在计算机中的存放方式。7逻辑结构和物理结构的关系逻辑结构和物理结构的关系l1. 逻辑结构逻辑结构 从逻辑关系上观察数据，独立于计算从逻辑关系上观察数据，独立于计算机；可以在理论上、形式上进行研究、机；可以在理论上、形式上进行研究、推理、运算等各种操作。推理、运算等各种操作。l2. 存储结构存储结构 逻辑
5、结构在计算机中的实现，依赖于逻辑结构在计算机中的实现，依赖于计算机。计算机。l3. 任何一个算法的设计取决于选定的任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于逻辑结构；而算法的最终实现依赖于采用的存储结构。采用的存储结构。8数据存储结构分类数据存储结构分类l顺序存储结构顺序存储结构l链式存储结构链式存储结构l索引存储结构索引存储结构l散列存储结构散列存储结构 9(1) 顺序存储结构顺序存储结构l 把数据元素按某种顺序存放在一块连续的把数据元素按某种顺序存放在一块连续的存储单元中。存储单元中。l 结点结构结点结构:l 特点特点:1) 连续存放连续存放,逻辑上相邻逻辑上相邻,物理
6、上也相邻。物理上也相邻。2) 结构简单，易实现。结构简单，易实现。3) 插入、删除操作不便（需大量移动元素）插入、删除操作不便（需大量移动元素） d1 d2 dn数据域10(2) 链式存储结构链式存储结构l 数据元素存放在任意存储单元中，可连续数据元素存放在任意存储单元中，可连续存放，也可以不连续存放，用指针实现链存放，也可以不连续存放，用指针实现链表间的联系。表间的联系。l 结点结构结点结构:l特点特点: 1) 插入、删除操作只要修改指针即可插入、删除操作只要修改指针即可2) 结构较复杂，需要额外存储空间。结构较复杂，需要额外存储空间。 d1. d2dn NULL数据域 指针域11(3) 索
7、引存储结构索引存储结构l存储两部分内容：存储两部分内容： 数据元素序列和索引表数据元素序列和索引表l索引表组成索引表组成: 数据元素的某个数据项和该数据元素的某个数据项和该元素存储地址元素存储地址l 结点结构结点结构:l 序号：序号： 1 2 3 4 5 6 7 l 数据项：数据项：l 索引号：索引号： l 特点：特点： 非连续存放非连续存放 增增 、删操作简单、删操作简单 检索速度快检索速度快 数据元素长度可不等数据元素长度可不等12 21 35 2 45 5 104 3 2 7 1 6 5 数据项数据项 索引顺序号索引顺序号12(4) 散列存储结构散列存储结构l在数据元素与存储位置之间建立
8、一种在数据元素与存储位置之间建立一种存储关系存储关系F，根据这种关系，根据这种关系F，已知元，已知元素素E，就可以得到它的存储地址，即，就可以得到它的存储地址，即D=F（E）。）。l特点：特点： （1）数据元素间无内在联系数据元素间无内在联系 （2）存储形式不定）存储形式不定l实例：哈希查找中的哈希表实例：哈希查找中的哈希表135. 数据运算数据运算l（1）数据运算）数据运算 是指对存放在物理结构上的数据是指对存放在物理结构上的数据,按定按定义的逻辑结构进行的各种操作。义的逻辑结构进行的各种操作。l（2）每个数据结构都有一个运算的集）每个数据结构都有一个运算的集合合l（3）常见操作）常见操作检
9、索、插入、删除、修改检索、插入、删除、修改14三、算法与算法分析三、算法与算法分析l 1. 算法（算法（Algorithm）是对特定问题求解步骤的一种描述；是对特定问题求解步骤的一种描述；l2. 算法和运算的关系算法和运算的关系运算依赖于逻辑结构运算依赖于逻辑结构算法依赖于存储结构算法依赖于存储结构l3. 研究算法追求的目标研究算法追求的目标 时间和空间的适当和谐时间和空间的适当和谐154. 算法的特性算法的特性l有穷性有穷性 一个算法必须总是在执行有穷步后一个算法必须总是在执行有穷步后结束，且每一步都可在有穷时间内完成；结束，且每一步都可在有穷时间内完成；l确定性确定性 算法中的每一个指令必
10、须有明确的算法中的每一个指令必须有明确的含义，不能有二义性；含义，不能有二义性；l可行性可行性 算法中描述的操作都是可通过已经算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的；实现的基本运算、执行有限次实现的；l输入输入 一个算法应有一个算法应有0个或多个输入；个或多个输入；l输出输出 一个算法应有一个算法应有1个或多个输出。个或多个输出。165. 算法的描述方式算法的描述方式l(1) 自然语言自然语言l(2) 流程图流程图 用特定图形符号进行算法描述用特定图形符号进行算法描述 l(3) 伪语言伪语言 包括程序设计语言的三大基本结构及自包括程序设计语言的三大基本结构及自然语言的一
11、种语言然语言的一种语言l(4) 类语言类语言 类似高级语言的语言，例如类类似高级语言的语言，例如类PASCAL、类类C语言。语言。176.算法的评价标准算法的评价标准l(1)时间复杂度时间复杂度 指在计算机上运行该算法所花费的时间。指在计算机上运行该算法所花费的时间。用用“O（数量级）（数量级）”来表示，称为来表示，称为“阶阶”。常见的时间复杂度：常见的时间复杂度： O(1) O(logn) O(n ) O( n2) 常数阶常数阶 对数阶对数阶 线性阶线性阶 平方阶平方阶l(2) 空间复杂度空间复杂度 指算法在计算机上运行所占用的存储指算法在计算机上运行所占用的存储空间。度量同时间复杂度。空间
12、。度量同时间复杂度。 18时间复杂度举例时间复杂度举例l（a） O(1) X：=X+1 ；l（b） O(n) FOR I：=1 TO n DO X：= X+1；l （c） O( n2) FOR I：= 1 TO n DO FOR J：= 1 TO n DO X：= X+1；191.2 线性表线性表l是指数据元素之间的关系为一一对应是指数据元素之间的关系为一一对应的线性关系的数据结构。的线性关系的数据结构。l例如，一星期七天的英文缩写表示：例如，一星期七天的英文缩写表示：l （Sun，Mon，The，wed，Thu，Fri，Sat）是一个线性表，其中的元）是一个线性表，其中的元素是字符串，表的长
13、度为素是字符串，表的长度为7。l 20（一）线性表的逻辑结构（一）线性表的逻辑结构l定义：定义： 线性表是线性表是n（n 0）个元素）个元素a1,a2,an 的有限序列的有限序列;表中每个数表中每个数据元素据元素,除了第除了第1个和最后个和最后1个外个外,有且有且仅有一个前趋元素和后继元素。仅有一个前趋元素和后继元素。21l形式定义：形式定义：l 含有含有n个数据元素的线性表是一种数据结个数据元素的线性表是一种数据结构，表示为：构，表示为： l Linear_list=( D , R )l 其中其中: D=ai | ai D0,i=1,2,3,n,n 0l R=N, N=| ai-1,ai D
14、0 ,i=1,nl D是数据元素的有限集合是数据元素的有限集合,R是是D上逻辑关上逻辑关系的有限集合。关系系的有限集合。关系N是一个有序偶对的集是一个有序偶对的集合。合。22相互关系描述相互关系描述l1）L的长度为的长度为n（n 0），），n=0时是空表；时是空表； l2）除了第）除了第1个和最后一个元素外个和最后一个元素外,每个元素每个元素有唯一的前趋和后继；有唯一的前趋和后继；l3）线性表中各元素间存在着线性关系；）线性表中各元素间存在着线性关系；l4）均匀性；各元素数据类型必须相同；）均匀性；各元素数据类型必须相同；l5）有序性；各元素是有序的，不可交换次）有序性；各元素是有序的，不可交
15、换次序。序。23线性表的基本操作线性表的基本操作lSetnull(L) 置空表置空表lLength(L) 求表长度求表长度,即表中元素个数即表中元素个数lGet(L,i) 取表中第取表中第i个元素（个元素（1 i n）lPrior(L,i) 取取i的前趋元素的前趋元素lNext(L,i) 取取i的后继元素的后继元素lLocate(L,x) 返回指定元素在表中的位置返回指定元素在表中的位置lInsert(L,i,x) 插入元素插入元素lDelete(L,x) 删除元素删除元素lEmpty(L) 判别表是否为空判别表是否为空24（二）线性表的顺序存储结构（二）线性表的顺序存储结构l1. 顺序存储结
16、构顺序存储结构表中元素顺序存入连续的存储单元中。表中元素顺序存入连续的存储单元中。l2. 顺序表顺序表采用顺序结构的线性表。采用顺序结构的线性表。l3. 顺序表的存储特点顺序表的存储特点由起始位置计算表中任一元素的地址由起始位置计算表中任一元素的地址l LOC(ai)=LOC(a1)+C*(i-1) 1 i n C: 元素占用存储单元的长度元素占用存储单元的长度25l4. C语言实现语言实现 采用一维数组采用一维数组l #define MAXLENGTH 100l int list MAXLENGTH；l int last = -1；/*表中最后一个元素的序号表中最后一个元素的序号,-1空表空
17、表*/26线性表元素存储示意图线性表元素存储示意图l a1a2.ai.元素序号元素序号 内存状态内存状态 存储地址存储地址12. i.LOC(a1)LOC(a1)+C.LOC(a1)+C*(i-1).27算法算法1-1 插入元素算法插入元素算法l算法步骤算法步骤:l step1 将第将第n至第至第i个元素后移一个存个元素后移一个存储位置储位置; l step2 将将x插入到插入到ai-1之后之后;l step3 表的长度加表的长度加1。l 28算法算法1-1 插入算法插入算法linsert（int i，int x） /* last为全局变量为全局变量*/l int k；l if（last+1=
18、MAXLENGTH）l printf（“线性表已满！线性表已满！n”); exit(-1); l if (ilast+1)l printf(“插入位置错误插入位置错误!n” ); exit(-2); l else 29 l for (k=last-1;K=i-1;k-)l listk+1=listk;l list i-1 =x;l +last;l l30算法算法1-1 插入算法主程序插入算法主程序l#define MAXLENGTH 100 /* 例例1-1主主程序程序 */lint listMAXLENGTH=5,3,1,10,7,8,-1,4;lint last=7; /* last为全局
19、变量为全局变量*/l main（）（）l int x,j,loc;l printf(“Enter x、locn”);l scanf(“%d,%d”,&x,&loc);l for (j=0;j last+1;j+)l printf(“%d “,listj); 31l printf(“n”);l insert(loc,x); /* 调用插入函数调用插入函数 */l for (j=0;j last+1,j+)l printf(“%d “,listj);l printf(“n”);l 32算法算法1-2 线性表删除元素线性表删除元素l 算法步骤算法步骤:l step1 判别指定的位置是否合法；判别指定
20、的位置是否合法；l step2 若合法，则将位置若合法，则将位置i+1至至n的的元素前移一个存储位置元素前移一个存储位置; l step3 表的长度表的长度 - 1。33算法算法1-2 线性表删除算法线性表删除算法l delete(int i) /*第第i 个元素的下标为个元素的下标为I-1 */l int k;l if( i last )l printf(“表中不存在位置为表中不存在位置为i的元素的元素 n”);l exit(-1);l l for(k= i-1;k=last-1;k+)l listk=listk+1;l last-;l 34算法算法1-2 线性表删除算法线性表删除算法l#d
21、efine MAXLENGTH 100 /* 例例1-2主主程序程序 */lint listMAXLENGTH=5,3,1,10,7,8,-1,4;lint last=7;l main（）（）l int j,loc;l printf(“Enter locn”);l scanf(“%d”,&loc);l for (j=0;j last+1;j+)l printf(“%d “,listj); 35l printf(“n”);l delete(loc); /* 删除子函数删除子函数 */l for (j=0;j next = NULLl非空表非空表: head -next = 地址地址 headNU
22、LL头结点头结点head头结点头结点41设置头结点的目的设置头结点的目的(二二)l(2) 没有头结点没有头结点l表示形式不统一表示形式不统一l空表空表: head = NULLl非空表非空表: head - next = 地址地址headheadheadheada142链表举例链表举例l由食品组成的单链表由食品组成的单链表（biscuit,butter,cheese,eggs,grapes,jam)l 不带头结点不带头结点:biscuitbuttercheesejamgrapeseggshead 头指针43单链表的存储状态单链表的存储状态l Grapes 60biscuit 61cheese
23、13eggs 1jam NULLbutter 12存储地址存储地址 数据域（数据域（data） 指针域指针域（next）1111213606111头指针头指针 head headbiscuit,butter,cheese,eggs,grapes,jam442、单链表的操作、单链表的操作指针的基本操作指针的基本操作单链表的查找单链表的查找get单链表的的插入单链表的的插入insert单链表的删除单链表的删除delete45指针的基本操作指针的基本操作l(1)定义指针变量定义指针变量p、q： NODE *p，*q；l(2) 对链表的操作就是对指针的操作。对链表的操作就是对指针的操作。l(3) 例如
24、，要删除结点例如，要删除结点ai，首先要使，首先要使指针指针p指向指向ai，即：，即：a1.headaip.an46指针的基本操作指针的基本操作p=(NODE*) malloc(sizeof(NODE) 申请一个结点空间申请一个结点空间,并将地址送入并将地址送入p中中.free(p) 释放释放p所指结点的空间所指结点的空间p=q p指向指向q所指的结点所指的结点p=q-next p指向指向q所指结点的后继所指结点的后继p=p-next p向后移动一个结点向后移动一个结点 p-next=q 将将q所指结点改接为所指结点改接为p所所指结点的后继指结点的后继p-next=NULL p所指结点与后继结
25、点所指结点与后继结点断开断开47指针操作举例指针操作举例lp=q-next p指向指向q所指结点的后继所指结点的后继aiai-1ai-1aiai-1ai+1qqpp操作前状态操作后状态48单链表的查找算法单链表的查找算法l操作步骤操作步骤:l1) 初始化初始化,指针指针p指向头指针指向头指针,计数器计数器置置0l2) p非空且计数器小于非空且计数器小于i循环循环l3) 每循环一次每循环一次, p后移一个位置后移一个位置,计计数器加数器加1l4) 循环结束循环结束,返回指向返回指向ai 的指针的指针p.49单链表查找算法程序单链表查找算法程序l NODE *get(NODE *head,int）
26、l NODE *p;l int counter = 0;l p=head-next;l while(p!=NULL)&(counternext; counter+; l if (p!=NULL)&(counter = i)l return p;l elsel return NULL; 50单链表插入算法单链表插入算法1-3l操作步骤操作步骤:l1) 找到找到ai-1的位置的位置,使指针使指针p指向指向ai-1l2) 申请并生成新结点申请并生成新结点sl3) 使使s插入到插入到ai-1和和ai之间之间l l s-next=p-nextl p-next=sl s-data=xai-1aipxs51
27、单链表的插入算法程序单链表的插入算法程序l insert(NODE *head, int i, int x)l NODE *p,*s;l if(i=1) p=head; /*若若i=1,p指向头指针指向头指针*/l else p=get(head,i-1); /*p指向指向a i-1*/l if(p=NULL) /*p为空为空,说明找不到说明找不到i位位置置*/l printf(“插入位置错插入位置错n”); exit(0); l else 52 l s=(NODE*)malloc(sizeof(NODE); l s-data=x; l s-next= p-next;l p-next=s;l
28、l 53单链表删除算法单链表删除算法1-4l操作步骤操作步骤:lstep1 找到找到ai-1的位置的位置,使指针使指针p指向指向ai-1lstep2 使指针使指针t指向指向p所指结点的后继所指结点的后继lstep3 使使t所指结点所指结点ai 脱链脱链lstep4 释放释放t t=p-nextl p-next=t-nextl free(t) pta i-1aia i+154单链表的删除算法程序单链表的删除算法程序l delete(NODE *head, int i)l NODE *p,*t;l if(i=1) p=head;l else p=get(head,i-1);l if(p=NULL)
29、l printf(“i表长表长+1, 无此结点无此结点n”); exit(0); l if(p-next=NULL) l printf(“i=表长表长+1,无此结点无此结点n”); exit(0); 55 lelse l t = p- next; l p-next = t-next; l free(t) ;l l 563、循环单链表和双向链表、循环单链表和双向链表l(1) 链表链表特点特点: 1) 检索只能从头指针开始检索只能从头指针开始,且只能沿链表方向移且只能沿链表方向移动。动。 2) 从任一结点找其前趋从任一结点找其前趋,时间复杂度是时间复杂度是O(n)l(2) 单循环链表单循环链表 链
30、表首尾相接，构成环形链表首尾相接，构成环形特点特点: 1) 从任一结点出发从任一结点出发,均可以找到表中其它结点。均可以找到表中其它结点。 2) 找其前趋结点费时找其前趋结点费时,时间复杂度是时间复杂度是O(n)。57l(3) 双向链表双向链表 链表从两个方向检索链表从两个方向检索特点特点: 1) 适合于两个方向的移动。适合于两个方向的移动。 2) 找其前趋结点的时间复杂度是找其前趋结点的时间复杂度是O(1)。l(4) 双向循环链表双向循环链表58单循环链表单循环链表l(1) 表示形式表示形式l(2)单循环链表为空单循环链表为空l条件条件: head -next=headl表示形式表示形式:
31、head.heada1a2an59双向链表双向链表结点结构结点结构lstruct dnodel int data；l struct dnode *prior，*next； ；l typedef struct dnode DNODE；60双向循环链表表示形式双向循环链表表示形式l双向循环链表表示形式：双向循环链表表示形式：l双循环链表为空的条件双循环链表为空的条件: l head-prior = head-next = headl表示形式为表示形式为: headhead.ana2a1614、链表结点及标识符、链表结点及标识符l约定：约定： 指针指针p指向结点指向结点ai ，l ai作为一个变量，
32、其标识符为作为一个变量，其标识符为*pl *p的分量：的分量： 数据域数据域:p-data 指针域指针域: 指向后继结点指向后继结点p-nextp ai pP-dataP-nextai62链表结点及各分量标识符链表结点及各分量标识符(双链表双链表)l约定：约定： 设指针设指针p指向结点指向结点ai ，数据域数据域: p-data,前趋结点前趋结点: 指针域指针域: p-prior 数据域数据域: p-prior-data后继结点后继结点: 指针域指针域 p-next 数据域数据域: p- next -datapa i+1aia i-163链表存储结构的特点链表存储结构的特点l(1) 插入、删除
33、操作极为方便插入、删除操作极为方便l(2) 数据非连续存放、顺序存取数据非连续存放、顺序存取l(3) 逻辑上相邻，物理上不一定相邻逻辑上相邻，物理上不一定相邻l(4) 存储结构较复杂、需要额外的存存储结构较复杂、需要额外的存储空间保存链结构储空间保存链结构l结论：结论：l 适合于表中元素频繁变动的线性表适合于表中元素频繁变动的线性表645、链表的动态生成、链表的动态生成l链表是一种动态存储结构。因此，建链表是一种动态存储结构。因此，建立链表的过程是动态生成的过程。立链表的过程是动态生成的过程。 l按链表结点建立的顺序、方向不同，按链表结点建立的顺序、方向不同，分为两种方法：分为两种方法： 1)
34、 从前往后的动态生成法（算法从前往后的动态生成法（算法2-6） 2) 从后往前的动态生成法（算法从后往前的动态生成法（算法2-7）65链表动态生成（方法一）从前往后链表动态生成（方法一）从前往后l操作步骤：操作步骤：lstep1 初始化；头指针置初始化；头指针置NULLlstep2 输入结点数据非输入结点数据非0循环循环l1) 使使s指向新生成的结点，指向新生成的结点，s-data =numl2) 若若 head=NULL(第第1个结点个结点) ,head=sl3) 否则否则 p-next=shead s.pa iai-1a2a166l4) 指针指针p始终指向始终指向s , p=slstep3
35、 结束循环结束循环,p-next =NULL, 返回头返回头指针指针head。67链表的动态生成（方法二）从后往前链表的动态生成（方法二）从后往前l 算法操作步骤：算法操作步骤：lstep1 初始化；初始化；头指针置头指针置NULL,线性表元素存于线性表元素存于aN中中,i=N-1lstep2 i = 0 循环循环 1) 使使s指向新生成的结点，指向新生成的结点，head . sai-1aianai-168 2) s-data = ai ,s-next = head 3) 指针指针s始终指向头指针始终指向头指针 head=sl step3 结束循环结束循环, 返回头指针返回头指针head。69作业、思考题作业、思考题l1、思考题、思考题: 第第1章习题的章习题的12题题l2. 作业题作业题: 第第1章习题的章习题的57、14题题70
