数据结构第1讲---线性表

1、一、了解计算机的工作方式一、了解计算机的工作方式l将编好的程序和原始数据，输入并存储在计将编好的程序和原始数据，输入并存储在计算机的内存储器中（即算机的内存储器中（即“存储程序存储程序”）；）；l计算机按照程序逐条取出指令加以分析，并计算机按照程序逐条取出指令加以分析，并执行指令规定的操作（即执行指令规定的操作（即“程序控制程序控制”）。）。l这一原理称为这一原理称为存贮程序存贮程序和和程序控制程序控制,是现代计是现代计算机的基本工作方式。算机的基本工作方式。程序程序是计算机的灵魂是计算机的灵魂 什么是数据结构（什么是数据结构（data structuredata structure） 什么是

2、算法（什么是算法（algorithmalgorithm） 什么是语言？什么是语言？程序=数据结构+算法是数据在计算机中的组织方式及相应的是数据在计算机中的组织方式及相应的基本访问操作。基本访问操作。是解决问题的方法（数据处理）或者步骤是解决问题的方法（数据处理）或者步骤语言是实现数据结构和算法的载体，即编写语言是实现数据结构和算法的载体，即编写程序的工具，如程序的工具，如Pascal，C语言，语言，Qbasic，JAVA，C+，VB等等数据：数据：能够被计算机输入、存储、处理、输出的一切信能够被计算机输入、存储、处理、输出的一切信息息 ,随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字

3、符串、图像和声音等 数据元素：数据元素：是一个数据整体中相对独立的单位，是一个数据整体中相对独立的单位，也称也称元素、结点、顶点、记录。一个元素可以由若干个数元素、结点、顶点、记录。一个元素可以由若干个数据项（也称为字段、域、属性）据项（也称为字段、域、属性） 组成。组成。一、几个概念：二、数据结构的基本知识数据结构：数据结构：指相互之间存在着一种或多种关系的数据元素的集合。将数据元素之间的关系称为结构。 红色代表各类数据，蓝色框（即一行）表示一个数据元素数据元素或一个数据项、一个记录、一个结点、一个元素，而每一个数据项都包含学号、姓名、数学分析、普通物理、高等代数、平均成绩共6个字段字段或6

4、个域域，其中能通过学号字段唯一地识别一行记录，那么学号字段称为关键字段。 没有前驱的结点称为开始结点开始结点，没有后继的结点称为终端结点终端结点数据的逻辑结构数据的逻辑结构（数据元素之间的联系，（数据元素之间的联系，如哪个元素是第一个元素、哪个元素是第二个元素、如哪个元素是第一个元素、哪个元素是第二个元素、它的前驱和后继是什么）它的前驱和后继是什么） 数据的物理结构数据的物理结构（数据在计算机中的存储（数据在计算机中的存储方式，数据的存放方式有顺序、链接、索引、散列方式，数据的存放方式有顺序、链接、索引、散列等等 ） 数据的运算数据的运算（查找、插入、删除、合并、（查找、插入、删除、合并、排序

5、、统计、简单计算、输入、输出等）排序、统计、简单计算、输入、输出等） 二、数据结构的研究内容在不产生混淆的前提下，常将数据的逻辑结构简称为在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构，以下研究的数据结构，均指逻辑结构。数据结构，以下研究的数据结构，均指逻辑结构。数据的逻辑结构有两大类：线性结构和非线性结构数据的逻辑结构有两大类：线性结构和非线性结构1、数据的逻辑结构（1）线线性结构性结构线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。（2）非线非线性结

6、构性结构非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。广义表、树和图等数据结构都是非线性结构。2、通过图理解线性与非线性线性结构举例：举例：10个学生按学号排列示意图：示意图： 特点：特点：每个数据只有一个前驱、一个后继（第每个数据只有一个前驱、一个后继（第一个元素无前驱，最后一个元素无后继）一个元素无前驱，最后一个元素无后继）是是1：1的关系。的关系。树型结构举例：举例：一个领导与被领导的关系一个领导与被领导的关系(14人，单向人，单向)示意图：示意图： 特点：特点：除第一个结点除第一个结点外，都有一个前驱，外，都有一个前驱，可有多个后继可有多个后继 ；最下；最下一层只有前驱

7、无后继一层只有前驱无后继 ，是是1：N的关系。的关系。图型结构举例：举例：人与人之间互相认识的关系人与人之间互相认识的关系(双向的双向的) 示意图：示意图：特点：特点：每个结点都可有多个前驱和多个后每个结点都可有多个前驱和多个后继继 ，M：N的关系。的关系。 顺序存储把逻辑上相邻的结点存储在物理上相邻的存储单元,通常借助于程序设计语言中的数组来实现链式存储逻辑上相邻元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示,每个结点的存储单元由数据域和指针域两部分组成2、数据的存储结构有时，为了查找的方便，还采用索引存储方法和散列存储方法。索引存储用结点的索引号来确定结点的存储地址散列

8、存储根据结点的值来确定结点的存储地址查找、插入、删除、合并、排序、统计、简单计算、输入、输出等。算法算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上所施加的一种运算。如何设计数据的逻辑结构如何选择数据的物理结构如何优化设计思想和技巧学习数据结构的目的优化算法3、数据的运算3、小结三种基本数据结构、小结三种基本数据结构考虑数据之间前驱与后继的对应关系考虑数据之间前驱与后继的对应关系:l线性结构线性结构 数据元素之间存在一对一的线性关系数据元素之间存在一对一的线性关系(1:1)l树形结构树形结构 数据元素之间存在一对多的层次关系数据元素之间存在一对多的层次关系(1:N)l图状结

9、构图状结构 数据元素之间存在多对多的网状关系数据元素之间存在多对多的网状关系(M:N) 数据的逻辑结构数据的逻辑结构 001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02线性表图书馆书目表数据元素数据元素树图用圆圈代表一个数据元素用圆圈代表一个数据元素在逻辑上相邻的数据在存储时仍然相邻吗？在逻辑上相邻的数据在存储时仍然相邻吗？为什么？为什么？顺序存储（如数组，相邻）顺序存储（如数组，相邻）链式存储（如指针，不相邻）链式存储（如指针，不相邻） 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据结构的基本运算数据结构的基本运算 线性

10、结构线性结构 顺序存储顺序存储 链式存储链式存储 树形结构树形结构图形结构图形结构小结：数据结构的三个方面：小结：数据结构的三个方面： 数数据据结结构构 :查找、插入、删除等查找、插入、删除等 线性表的长度：线性表的长度：所含元素的个数所含元素的个数, ,用用n n表示，表示，n=n=。当当n=0n=0时时, ,表示线性表是一个空表，即表中不包含任何元表示线性表是一个空表，即表中不包含任何元素。素。线性表线性表是由是由n n（n0n0）个）个具有相同特性具有相同特性数据元素数据元素( (结点结点) ) a a1 1，a a2 2，a an n组成的有限序列。组成的有限序列。1、线性表的概念、线

11、性表的概念a1a2aiai+1an线性表的逻辑结构表示：线性表的逻辑结构表示：三、线性结构三、线性结构线性表线性表2、线性表的特点、线性表的特点对于非空的线性表：对于非空的线性表：有且仅有一个开始结点有且仅有一个开始结点a a1 1，没有直接前趋，有且，没有直接前趋，有且仅有一个直接后继仅有一个直接后继a a2 2；有且仅有一个终结结点有且仅有一个终结结点a an n，没有直接后继，有且，没有直接后继，有且仅有一个直接前趋仅有一个直接前趋a an-1n-1；其余的内部结点其余的内部结点a ai i（2in-12in-1）都有且仅有一个）都有且仅有一个直接前趋直接前趋a ai-1i-1和一个和一

12、个a ai+1i+1。3、线性表的基本操作、线性表的基本操作u初始化：设置一个空的线性表u求长度：求线性表中数据元素的个数u获取元素：取出线性表中的某个数据元素u查找：搜索线性表里满足某一条件的元素u插入：把给定元素插入到线性表中u删除：删除线性表中的元素u判断线性表是否满: :若满,返回True，否则返回Falseu判断线性表是否空: :若空,返回True，否则返回False数据结构教材数据结构教材P22P22在我们生活中有哪些属于线性表的例子在我们生活中有哪些属于线性表的例子,列举几个。列举几个。1 1、英文字母表（、英文字母表（A A，B B，Z Z）是线性表，）是线性表，表中每个字母是

13、一个数据元素（结点）表中每个字母是一个数据元素（结点）2 2、学生成绩表中，每个学生及其成绩是一、学生成绩表中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。各科成绩及平均成绩等数据项组成。 顺序存储是线性表的一种最顺序存储是线性表的一种最简单的存储结构，存储方式是：简单的存储结构，存储方式是：在内存中为线性表开辟一块连在内存中为线性表开辟一块连续的存储空间续的存储空间。用数组来存放用数组来存放每一个节点。每一个节点。s+n-1s+i-1s+1sanaia3a2a1内 存单 元编 号 (1)设和存放在设和存放在S

14、中中, 确定第一个数和最后确定第一个数和最后 一个数的位置。假设圆盘上一个数的位置。假设圆盘上5为第一个数，为第一个数，12为为最后一个数。则可将这最后一个数。则可将这20个数放在个数放在a数组中。数组的下数组中。数组的下标取标取0-19。0imax then begin max:=s;smax:=i;end; if sm*fzk do k:=k+1; if z*fmkm*fzk then begin 插入表中插入表中 end; end;(2)初始化，将两个线性表中分别存储最初的两个值初始化，将两个线性表中分别存储最初的两个值fz1:=0;fm1:=1;fz2:=1;fm2:=1;total:

15、=2; 下标下标12分子分子01分母分母11K to total?关于数组的复习 排序 查找 方阵 高精度5 5、线性表的链式存储、线性表的链式存储指针是以存储单元的地址作为其值的一种数据类型，是一种可指针是以存储单元的地址作为其值的一种数据类型，是一种可以根据需要动态申请内存单元的一种数据类型。以根据需要动态申请内存单元的一种数据类型。 100 p1p134F234F234F234F2定义方式：定义方式：Type Type 指针类型标识符指针类型标识符=类型标识符类型标识符； varvar 指针变量名：指针类型标识符；指针变量名：指针类型标识符；newnew（p1p1） 向计算机申请内存地址

16、向计算机申请内存地址 链式结构链式结构如何申请、释放存储单元如何申请、释放存储单元 p1p134F234F234F234F2typetype p=integer; p=integer;varvar p1:p; p1:p;p1:=200p1:=200 给给p1p1指向的单元赋值指向的单元赋值dispose(p1) 释放存储单元释放存储单元20020034F2 地址被释放，变量P与地址34F2没有关系 p1:integer;arrp = array1.10 of real；Type p=integer; arr=array1.4 of char; arrp = arr; Var p1:p; p2:

17、arrp;指针变量所指向的类型不同，指针变量所指向的类型不同，计算机所给予的存储单元的多计算机所给予的存储单元的多少也不相同。少也不相同。指针类型定义中的基类型只能指针类型定义中的基类型只能是类型标识符，不能是具体的是类型标识符，不能是具体的类型定义。类型定义。 p1p1 p2p2i链式结构链式结构什么是指针什么是指针 beginbegin new(p1);p1:=100; new(p1);p1:=100; new(p2);p2:=200; new(p2);p2:=200; p1:=p2; p1:=p2; end. end.30103011402040214022402340243011p14

18、024p24024p1(1) (1) 同一基类型的指针变量可以互相赋值。同一基类型的指针变量可以互相赋值。链式结构链式结构指针变量的基本操作指针变量的基本操作p1:=p2; ?(2)(2)对指针变量可以进行关系运算对指针变量可以进行关系运算 如如:if P1P2 then :if P1P2 then 语句语句1 else 1 else 语句语句2; 2; while P3 NIL do while P3 NIL do . . . . end; end; 关系运算的结果关系运算的结果, ,仍是仍是 FALSE , TRUE FALSE , TRUE 。链式结构链式结构指针变量的基本操作指针变量的

19、基本操作由于指针变量代表的是存储单元地址，它不能用输出语句进行打印，故在调试程序时要多加小心1、下面的自定义函数完成对一个单链表的查询操作，则方框中应填入（ ）。function find(var head:pointer;var x:integer):pointer;var p:pointer;begin p:=head; while ( ) do p:=p.next; find := p;end;A(p.datax) B(pnil)C(p.datax) OR (pnil) D(p.datax) AND (pnil)2、下列关于线性表的叙述正确的是（）A、线性表采用顺序存储，必须占用一片连续

20、的存储单元B、线性表采用顺序存储，便于进行插入和删除操作C、线性表采用链接存储，不必占用一片连续的存储单元D、线性表采用链接存储，便于插入和删除操作Type p= node ; node= record data : integer ; next:p； end; var p1, p2 : p1 1、查找链表的第、查找链表的第n n个元素个元素(1)(1)设临时工作变量设临时工作变量p p指针指向链表的指针指向链表的头结点头结点( (头结点的地址不能丢失和改变，头结点的地址不能丢失和改变，否则会丢失整个链表否则会丢失整个链表);); p:=head; p:=head;(2)x:=0;(2)x:=

21、0; while xn do while xn do begin begin inc(x);pinc(x);p:=:=p.nextp.next; ; end; end; 2 2、链表元素的删除（、链表元素的删除（删除删除r r结点，结点，p p是是r r的前驱的前驱）（1 1）表头删除）表头删除p:=head;r:=p.next;p.next:=r.next; dispose(r);rheadnilpr:=p.next;p.next:=nil; dispose(r);（2 2）表尾删除）表尾删除headnilrpnilheadnilrpr:=p.next;p.next:=r.next; dis

22、pose(r);（3 3）表中节点删除）表中节点删除3 3、链表元素的插入、链表元素的插入 new(s);readln(x);s.datanew(s);readln(x);s.data:=x;:=x; s.nexts.next:=nil; :=nil; p.nextp.next:=s:=s表尾插入headpsxnilnew(s);readln(x);s.datanew(s);readln(x);s.data:=x; :=x; s.nexts.next:=head; head:=s:=head; head:=s；表头插入headpsnilxnew(s);readln(x);s.datanew(s

23、);readln(x);s.data:=x;:=x;s.nexts.next:= :=p.nextp.next; ; p.nextp.next:=s:=spheadsnilx表中插入线性链表应用的三种模式：线性链表应用的三种模式： （1）数据元素的查找数据元素的查找 （2）数据元素的插入数据元素的插入 （3）数据元素的删除。数据元素的删除。线性链表的访问基本方法是：线性链表的访问基本方法是：（1 1）从头结点开始沿线性链表方向进行探求，一从头结点开始沿线性链表方向进行探求，一般用于指向刚查过的结点地址，另一个用于指向下般用于指向刚查过的结点地址，另一个用于指向下一个待查的结点地址。一个待查的结

24、点地址。（2 2）结束访问的条件有两个：一个是结点地址为结束访问的条件有两个：一个是结点地址为Nil,Nil,另一个是找到了相应的结点。另一个是找到了相应的结点。 容易出错的是：当容易出错的是：当p p为为nilnil时，取时，取p.datap.data时出错，时出错，因为因为p p是是nilnil，p.datap.data的值无意义。的值无意义。例例5.15.1：输入一个正整数序列：输入一个正整数序列, ,遇遇0 0时停止，按输入时停止，按输入数据的顺序建立如下链表数据的顺序建立如下链表: :（从表头插入结点）（从表头插入结点） （1 1）初始化）初始化（2 2）申请一个结点并赋值，然后将结

25、点插入表头）申请一个结点并赋值，然后将结点插入表头（3 3）重复（）重复（2 2），直到输入的值为等于），直到输入的值为等于0 0结束。结束。分析：分析：实战演练实战演练 readln(n) ; head:=nil; while n 0 do插入表头插入表头,形成链表形成链表 begin new ( p ) ; p.data:=n; p.next:=head; head:= p ; read ( n ) ; end ; 参考程序：参考程序： head:=nil; read(x); while x0 do begin if head=nil then begin new(p); p.data:=

26、x;p.next:=nil; q:=p; head:=p end else begin 结点插入结点插入 end; read(x); end; headnew(p); p.data:=x;pnext:=nil;q.next:=p; q:=p; 空间空间分配分配静态分配。程序执行前静态分配。程序执行前须确定存储规模。估计须确定存储规模。估计过大造成空间浪费，估过大造成空间浪费，估计太小使空间溢出机会计太小使空间溢出机会增多。增多。 动态分配动态分配, ,只要内存空间尚有空只要内存空间尚有空闲，就不会产生溢出。当线性表闲，就不会产生溢出。当线性表的长度变化较大，难以估计存储的长度变化较大，难以估计

27、存储规模时，宜采用动态链表作存储规模时，宜采用动态链表作存储结构为好结构为好。 时间时间存取存取随机存取结构，查找方随机存取结构，查找方便，但插入和删除操作便，但插入和删除操作很费时。很费时。顺序存取结构，链表中的结点，顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取需从头指针起顺着链扫描才能取得。得。 插入插入删除删除操作操作在顺序表中进行插入和在顺序表中进行插入和删除，平均要移动表中删除，平均要移动表中近一半的结点，尤其是近一半的结点，尤其是当每个结点的信息量较当每个结点的信息量较大时，移动结点的时间大时，移动结点的时间开销就相当可观。开销就相当可观。 在链表进行插入和删除，只需要

28、在链表进行插入和删除，只需要修改指针。对于频繁进行插入和修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存删除的线性表，宜采用链表做存储结构。若表的插入和删除主要储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。指针表示的单循环链表为宜。 实战演练：例实战演练：例5.25.2线性链表的归并运算：线性链表的归并运算：将下列两个有序线性表进行归并。将下列两个有序线性表进行归并。线性表（线性表（1 1）是：）是：33，5 5，8 8，1111，1313线性表（线性表（2 2）是：）是：11，4 4，5 5，9 9，1515归并后的线性

29、表为：归并后的线性表为：11，3 3，4 4，5 5，8 8，9 9，1111，1313，1515（1 1）线性链表中的结点是按数据域由小到大进行排）线性链表中的结点是按数据域由小到大进行排列的，根据两个线性列的，根据两个线性链链表中结点数据域的大小进行表中结点数据域的大小进行归并运算；哪个表中的数据小就归并哪一个；归并运算；哪个表中的数据小就归并哪一个；1 1、建立链表、建立链表2 2、归并、归并问题分析：问题分析：（2 2）当两个线性）当两个线性链链表中有一个已归并完毕，则另一个线表中有一个已归并完毕，则另一个线性性链链表的剩余部分全部复制到所建立的新线性表的剩余部分全部复制到所建立的新线

30、性链链表中。表中。（3 3）如果出现同值时，则选一个值。）如果出现同值时，则选一个值。p1:=head1;p2:=head2;p1:=head1;p2:=head2;while (p1nil) and (p2nil) dowhile (p1nil) and (p2nil) do begin begin if p1.data=p2.data if p1.data=p2.data then then 将链表将链表(1)(1)当前结点加到新链表中当前结点加到新链表中,p1,p1指针后移指针后移; ; else else 将链表将链表(2)(2)当前结点加到新链表中当前结点加到新链表中,p2,p2指针

31、后移指针后移; ; end; end;if p1nil then if p1nil then 将链表将链表(1)(1)剩余的结点连接到新表的后面剩余的结点连接到新表的后面; ;if p2nil then if p2nil then 将链表将链表(2)(2)剩余结点连到新表的后面剩余结点连到新表的后面; ;归并算法：归并算法：procedure procedure combine(varcombine(var head3:point;head1,head2:point); head3:point;head1,head2:point); varvar p1,p2,q,r:point; p1,p2,

32、q,r:point; begin begin new(head3);r:=head3; new(head3);r:=head3; p1:=head1;p2:=head2; p1:=head1;p2:=head2; while (p1nil) and (p2nil) do while (p1nil) and (p2nil) do if p1.data=p2.data if p1.data=p2.data then begin then begin new(q);r.nextnew(q);r.next:=:=q;q.dataq;q.data:=p1.data; :=p1.data; r:=q; p

33、1:=p1.next; r:=q; p1:=p1.next; if if p1.data=p2.data then p2:=p2.next; end end else begin else begin new(q);r.nextnew(q);r.next:=:=q;q.dataq;q.data:=p2.data;r:=q;:=p2.data;r:=q; p2:=p2.next; p2:=p2.next; end; end; if p1nil then if p1nil then r.nextr.next:=p1;:=p1; if p2nil then if p2nil then r.nextr

34、.next:=p2;:=p2; end; end;本算法在构建链表本算法在构建链表3 3时申请了新结点，能否时申请了新结点，能否不申请新结点来实现线性链表的归并？不申请新结点来实现线性链表的归并？想一想：想一想：不带附加不带附加头结点的头结点的链表链表heada1 a2 a3 a4a1 a2 a3 a4带附加头结带附加头结点的链表点的链表线性链表的几种形式：线性链表的几种形式： 其特点如下：其特点如下：单向链表单向链表双向链表双向链表双向链表双向链表双链表的操作与单链表基本一致：双链表的操作与单链表基本一致：123412type type point=node; point=node; nod

35、e=record node=record data:datatypedata:datatype; ; pre,next:pointpre,next:point; ; end; end;(1)每个结点有两个指针域，每个结点有两个指针域，一个指向其前驱结点，一一个指向其前驱结点，一个指向其后继结点。个指向其后继结点。(2)从任一结点出发可以访从任一结点出发可以访问其他结点。问其他结点。便于访问、插入和删除。便于访问、插入和删除。单循环链表单循环链表双循环链表双循环链表循环链表循环链表（1 1）尾结点指向第一个结点）尾结点指向第一个结点（2 2）从表中任一个结点出发可以找到链表中的其他结点。）从表中

36、任一个结点出发可以找到链表中的其他结点。（3 3）遍历操作的结束条件是：）遍历操作的结束条件是：（4 4）其他操作与单链表一样。）其他操作与单链表一样。循环链表循环链表注意：注意：带附加头结点带附加头结点 p=p=head.nexthead.next不带附加头结点不带附加头结点p=headp=head双向循环链表：最后一个结点的指针指向头结点，双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图：且头结点的前趋指向最后一个结点。如下图： 问题描述：设有问题描述：设有n n个人围成一圈，并按顺个人围成一圈，并按顺时针方向从时针方向从1 1到到n n编号；从第编号；从第s s个人开始进个人开始进行行1 1到到m m报数，数到报数，数到m m的人出圈；接着再从的人出圈；接着再从他后面一个人重新开始他后面一个人重新开始1 1到到m m报数，直到报数，直到所有人出圈为止。输出出圈人的次序。所有人出圈为止。输出出圈人的次序。例例2