数据结构教学课件：第02章_线性表A

1、1第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列 第第4章章 串串第第5章章 数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 排序排序目目 录录第二章：线性表什么是什么是线性结构？线性结构？2第二章：线性表3线性结构的定义：线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。接后继。 可表示为：（可表示为：（a a1 1 , a, a2

2、 2 , , , a, an n） 简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个除首尾结点外，其他结点只有一个直接前驱和一个直接后继。直接后继。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-一对一一对一 (1:1)第二章：线性表4第二章：线性表5（a1, a2, ai-1，ai, ai1 ，, an）2.1 线性表的逻辑结构线性表的逻辑结构 用

3、数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点2.1 线性表的逻辑结构6 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级U200713569李春元李春元男男19通信工程通信工程200701班班U200713611李煜墉李煜墉男男19通信工程通信工程200701班班U200713537张祺轩张祺轩男男19通信工程通信工程2

4、00702班班： ：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。2.1 线性表的逻辑结构7“同一数据逻辑结构中的所有数据元素都具有相同的特性同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。是指数据元素所包含的数据项的个数都相

5、等。试判断下列叙述的正误：试判断下列叙述的正误：2.1 线性表的逻辑结构82.2 线性表的顺序表示和操作线性表的顺序表示和操作2.2.1 顺序表的表示顺序表的表示2.2.2 顺序表的操作顺序表的操作2.2.3 顺序表的运算效率分析顺序表的运算效率分析2.2 顺序表的顺序表示和操作92.2.1 顺序表的表示顺序表的表示用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素。存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结

6、构或顺序映像。或顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：特点：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VVn n 的有效范围是从的有效范围是从 VV0 0 VVn-1n-1 2.2.1 顺序表的表示101. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利

7、用数组利用数组VnVn的的下标下标）。）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC ( ai+1 ) = LOC( ai ) + L 对上述公式的解释如图所示对上述公式的解释如图所示线性表顺序存储特点：线性表顺序存储特点：2.2.1 顺序表的表示11a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n

8、空闲区空闲区i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L线性表的顺序存储结构示意图线性表的顺序存储结构示意图下标起下标起点是点是1 12.2.1 顺序表的表示12设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数，每个数组元素用相邻的组元素用相邻的个字节个字节存储。存储器按字节编址，存储。存储器按字节编址，设存储数组元素设存储数组元素 的第一个字节的地址是的第一个字节的地址是9898，则，则 的第一个字节的地址是多少？的第一个字节的地址是多少？答案：答案：113但此

9、题要注意下标起点是从但此题要注意下标起点是从0 0开始：开始：LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）例例1 1或用（或用（3-0）2.2.1 顺序表的表示13 char V30;void build() /字母线性表的字母线性表的生成生成，即建表操作，即建表操作 int i; V0=a; for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心语句：核心语句：例例2用数组用数组V来存放来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z）

10、，写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C语言语言程序。程序。省略了省略了includeinclude语句语句2.2.1 顺序表的表示14void main(void) /主函数，字母线性表的主函数，字母线性表的生成和输出生成和输出 n=26; / n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的实际下标的实际下标 build( ); display( );void display( ) /字母线性表的字母线性表的显示显示，即读表操作，即读表操作 int i; for( i=0; i=i; j ) aj+1=a j ; a i =x;

11、 n+;/ / 元素后移一个位置元素后移一个位置/ / 插入插入x x / / 表长加表长加1 1 核核心心语语句：句：2)2)插入插入2.2.2 顺序表的操作17在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入插入2.2.2 顺序表的操作18实现步骤：实现步骤： 将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置； 表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?应

12、当符合条件：应当符合条件：1in 或或 i=1, n删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for ( j=i+1; j=n; j+ ) aj-1=aj; n-;/ / 元素前移一个位置元素前移一个位置/ / 表长减表长减1 1 核心语句：核心语句：3)3)删除删除2.2.2 顺序表的操作19123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：顺序表插入和删除的完整程序请同学们自编，顺序表插入和删除的完整程序请同学们自编，并务必上机验证！并务必

13、上机验证！2.2.2 顺序表的操作202.2.3 顺序表的运算效率分析顺序表的运算效率分析 算法时间主要耗费在算法时间主要耗费在移动元素移动元素的操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数移动元素次数)而移动元素的个数取决于插入或删除元素的位置。而移动元素的个数取决于插入或删除元素的位置。思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应

14、当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才合理。移动次数才合理。讨论讨论1：若在长度为若在长度为 n 的线性表的第的线性表的第 i 位前位前 插入插入一个元素，一个元素，则向后移动元素的次数则向后移动元素的次数f(n)为为:f(n) = n i + 1时间效率分析时间效率分析:2.2.3 顺序表的运算效率分析21推导：推导：假定在每个元素位置上插入假定在每个元素位置上插入x x的可能性都一样（即的可能性都一样（即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：若在首结点前插入，需要移动的元素最多，后移

15、次数为若在首结点前插入，需要移动的元素最多，后移次数为n n；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1n-1; ;若在若在a an-1n-1后面插入，后移次数为后面插入，后移次数为1 1；若在尾结点若在尾结点a an n之后插入，则后移次数为之后插入，则后移次数为0 0；故插入时的故插入时的平均平均移动次数为：移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少种插入形式共有多少种插入形式? ?连头带尾有连头带尾有n+1n+1种种! !所有所有可能的元素移动次数合计可能的元素移动次数合计： 0+1+

16、0+1+n+n = n(n+1)/2 = n(n+1)/22.2.3 顺序表的运算效率分析22同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T T（n)=(n-1)/2 n)=(n-1)/2 顺序表插入、删除算法的顺序表插入、删除算法的平均平均空间空间复杂度复杂度为多少？为多少？插入效率：插入效率：删除效率：删除效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin教材教材P25算法算法2.5也是对执行效率的推导：也是对执行效率的推导：因为没有占用辅助空间！因为没有占用辅助空间！含义：对于顺序表，

17、插入、删除操含义：对于顺序表，插入、删除操作平均需要移动一半元素作平均需要移动一半元素( n / 2 )O(1)O(1)即插入、删除算法的平均即插入、删除算法的平均时间复杂度为时间复杂度为 O(n)23深入讨论深入讨论1：顺序表各种操作算法的顺序表各种操作算法的“通式通式” 该如何书写？该如何书写？采用采用抽象数据类型抽象数据类型来表示来表示24线性表的抽象数据类型定义线性表的抽象数据类型定义（见教材见教材P19）ADT List 数据数据对象对象：D=ai | aiElemSet, i=1, 2, , n, n0数据数据关系关系：R= | ai 1, ai D, i=2, n基本基本操作操作

18、： 初始化、撤销、清空、判空；初始化、撤销、清空、判空； 求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继； 读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历； 插入、删除插入、删除 ADT List25线性表的基本操作如何表示？线性表的基本操作如何表示？ （见教材（见教材P19）InitList( &L ); /建空表，初始化建空表，初始化DestoryList( &L ); /撤销表，释放内存撤销表，释放内存int LengthList( L ); /求表中元素个数，即表长求表中元素个数，即表长POSITION LocateElem (L,ElemT

19、ype e，compare() ) /查找查找ePriorElem( L, cur_e, &pre_e ); /求当前元素求当前元素e的前驱的前驱NextElem( L, cur_e, &next_e ); /求当前元素求当前元素e的后继的后继ListInsertBefore(&L, i, e ); /把把e插入到第插入到第i个元素之前个元素之前ListDelete( &L, i,&e ); /删除第删除第i个元素并个元素并“看看”此元素此元素ListTraverse( L, Visit() ); / “看看”表中全部元素（遍历）表中全部元素（遍历）l初

20、始化、撤销、清空、判空；初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；读元素、查找（含定位）、遍历；l插入、删除插入、删除26结构体 结构体结构体是一种构造数据类型用途：把不同类型的数据组合成一个整体-自定义数据类型 结构体类型定义struct 结构体名 类型标识符 成员名； 类型标识符 成员名； .；成员类型可以是基本型或构造型struct是关键字,不能省略合法标识符可省:无名结构体27例 struct student int num; char name20; char sex; int age; float s

21、core; char addr30; ; namenumsexagescoreaddr2字节2字节20字节1字节4字节30字节.结构体类型定义描述结构的组织形式,不分配内存结构体类型定义的作用域28例 struct student int num; char name20; char sex; int age; float score; char addr30; ; struct student stu1,stu2; 结构体变量的定义结构体变量的定义 先定义结构体类型，再定义结构体变量 一般形式： struct 结构体名 类型标识符 成员名； 类型标识符 成员名； .；struct 结构体名

22、变量名表列；例 #define STUDENT struct student STUDENT int num; char name20; char sex; int age; float score; char addr30; ; STUDENT stu1,stu2; 29 定义结构体类型的同时定义结构体变量一般形式：struct 结构体名 类型标识符 成员名； 类型标识符 成员名； .变量名表列；例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; 30 说

23、明 结构体类型与结构体变量概念不同类型:不分配内存； 变量:分配内存类型:不能赋值、存取、运算; 变量:可以 结构体可嵌套 结构体成员名与程序中变量名可相同，不会混淆 结构体类型及变量的作用域与生存期例 struct date int month; int day; int year; ; struct student int num; char name20; struct date birthday; stu;numnamebirthdaymonthdayyear例 struct student int num; char name20; struct date int month; in

24、t day; int year; birthday; stu;numnamebirthdaymonthdayyear31结构体变量的引用结构体变量的引用 引用规则 结构体变量不能整体引用,只能引用变量成员 可以将一个结构体变量赋值给另一个结构体变量 结构体嵌套时逐级引用成员(分量)运算符优先级: 1结合性:从左向右引用方式： 结构体变量名.成员名例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; stu1.num=10;stu1.score=85.5;stu

25、1.score+=stu2.score; stu1.age+;例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; printf(“%d,%s,%c,%d,%f,%sn”,stu1); ()stu1=101,“Wan Lin”,M,19,87.5,“DaLian”; ()例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; s

26、tu2=stu1; ( )例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu1,stu2;numnamebirthdaymonthdayyearstu1.birthday.month=12;例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; if(stu1=stu2). ()32结构体数组结构体数组 结构体数组的定义三种形

27、式：形式一: struct student int num; char name20; char sex; int age; ;struct student stu2;形式二: struct student int num; char name20; char sex; int age; stu2;形式三: struct int num; char name20; char sex; int age; stu2;numnamesexagenumnamesexagestu0stu125B33顺序表的C语言描述 (p22)#define LIST_INIT_SIZE 100#define LIST

28、INCREMENT 10typedef struct ElemType *elem; int length; int listsize; SqList;SqList L; 说明：elem数组指针指向线性表的基地址；length指示线性表的当前长度；listsize指示顺序表当前分配的存储空间大小。当空间不足时，再分配的存储空间增量为 LISTINCREMENT*sizeof(ElemType)34 malloc函数函数格式：格式：void * malloc ( unsigned int size);功能：功能：在内存的动态存储区分配一个长度为size的连续空间，返回一个指向该区域起始地址的指针

29、（void类型） free函数函数格式：格式：void free(void *p)功能：功能：释放由p指向的内存区 realloc的格式及功能的格式及功能 格式：格式： void *realloc(void *p,unsigned size) 功能：功能：将p所指向的已分配内存区域的大小 改为size。size可以比原来分配的空间大或小352) 几个基本操作初始化初始化 (p23算法算法2.3) p23算法2.3 Status InitList_SqList(SqList &L) /* 构造一个空的线性表*/ L.elem=（ElemType*）malloc( LIST_INIT_SI

30、ZE *sizeof(ElemType); if (!L.elem) exit(OVERFLOW); / 存储空间分配失败，退出 L.length = 0; / 空表初始长度为0 L.listsize = LIST_INIT_SIZE; / 初始存储容量 return OK; 36几个基本操作插入插入 (p24算法2.4) Status ListInsert_sq(SqList &L,int i,ElemType e) /* 在顺序表L中第i个位置之前插入新的元素e, 1=i=ListLength_Sq(L)+1 */ if (iL.length+1) return ERROR; if (L.length = L.listsize) newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); i