数据结构线性表A.ppt

Recap:数据结构的定位,第二章：线性表,1,介于数学、计算机硬件和计算机软件三者之间的一门核心课程大数据时代的核心问题,Recap:什么是数据结构？,第二章：线性表,2,问题分类：数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构,Recap:什么是数据结构？,第二章：线性表,3,Data_Structure=（D,S）,元素有限集,关系有限集,相互之间存在一种或多种特定关系的数据元素的集合，表示为：,程序设计好算法好结构,Recap:基本概念,第二章：线性表,4,数据(data)：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。数据元素(data element)：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项(data item)：构成数据元素的不可分割的最小单位。,三者之间的关系：数据 数据元素 数据项,Recap:数据结构主要内容,第二章：线性表,5,Recap:逻辑结构,第二章：线性表,6,集合结构：仅同属一个集合线性结构:一对一(1:1)树结构:一对多(1:n)图结构:多对多(m:n),非线性,线 性,指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,Recap:存储结构,第二章：线性表,7,数据元素之间的关系在计算机中通常有以二种不同的表示方法，对应二种不同的存储结构顺序映象 顺序存储结构非顺序映象 链式存储结构,复数3.02.3i 的两种存储方式：,地址 内容,地址 内容,2字节,顺序存储方式,链式存储方式,2字节,Recap:抽象数据类型的定义,第二章：线性表,8,ADT=（D，S，P）数据对象 D上的关系集 D上的操作集,ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名,第二章：线性表,9,Recap:抽象数据类型定义,例：定义并实现复数抽象数据类型（定义）ADT Complex 数据对象：D=c1,c2|c1,c2 R(R为实数集）数据关系：S=（c1为实部，c2为虚部）基本操作：void Assign(*A,c1,c2）void Add(*A,B)void Minus(*A,B)void Multiply(*A,B)void Divide(*A,B).ADT Complex,Recap:抽象数据类型定义,第二章：线性表,10,例:定义并实现复数抽象数据类型（实现/类C描述）typedef ItemTypedouble;typedef structItemTyper;ItemTypev;Complex;/*复数抽象数据类型*/void Assign(Complex*A,ItemType r,ItemType v);void Add(Complex*A,Complex B);/*A+B*/void Minus(Complex*A,Complex B);/*A-B*/void Multiply(Compex*A,Complex B);/*A*B*/void Divide(Complex*A,Complex B);/*A/B*/.,Recap:算法分析,第二章：线性表,11,正确性时间代价(时间复杂度)空间代价(空间复杂度)最优性,Recap:算法效率度量,第二章：线性表,12,渐进符号“大O”的定义：当且仅当存在一个正的常数 C，使得对所有的 n n0，有 f(n)Cg(n)，则 f(n)=O(g(n),100n+6=O(n)/*100n+6101n for n6*/10n2+4n+2=O(n2)/*10n2+4n+211n2 for n5*/6*2n+n2=O(2n)/*6*2n+n2 7*2n for n4*/,面试:顺序存储还是链式存储？,第二章：线性表,13,反问：操作是什么？,14,第1章 绪论第2章 线性表第3章 栈和队列 第4章 串第5章 数组和广义表第6章 树和二叉树 第7章 图第9章 查找第10章 排序,目 录,第二章：线性表,数据结构课程的起点：,什么是线性结构？,15,第二章：线性表,16,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,an）,简言之，线性结构反映结点间的逻辑关系是 的。,特点 只有一个首结点和尾结点；特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一(1:1),第二章：线性表,17,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 应用举例,第二章：线性表,18,（a1,a2,ai-1，ai,ai1，,an）,2.1 线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,2.1 线性表的逻辑结构,19,（A,B,C,D,Z）,例2 分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析：数据元素都是同类型（字母），元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性！,例1 分析26 个英文字母组成的英文表是什么结构。,2.1 线性表的逻辑结构,20,“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,是指各元素具有相同的数据类型,试判断下列叙述的正误：,2.1 线性表的逻辑结构,21,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从 V0Vn-1,2.2.1 顺序表的表示,22,1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+L*（i-1）,对上述公式的解释如图所示,线性表顺序存储特点：,2.2.1 顺序表的表示,23,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b+L,b+(i-1)L,b+(n-1)L,b+(max-1)L,LOC(ai)=LOC(a1)+L*（i-1）,线性表的顺序存储结构示意图,下标起点是1,2.2.1 顺序表的表示,24,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是98，则的第一个字节的地址是多少？,答案：113,但此题要注意下标起点是从0开始：LOC(M3)=98+5(4-1)=113,解：已知地址计算通式为：,LOC(ai)=LOC(a1)+L*（i-1）,例1,或用（3-0）,2.2.1 顺序表的表示,25,char V30;void build()/字母线性表的生成，即建表操作 int i;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;,核心语句：法1 Vi=Vi-1+1;法2 Vi=a+i;法3 Vi=97+i;,例2,用数组V来存放26个英文字母组成的线性表（a，b，c，z），写出在顺序结构上生成和显示该表的C语言程序。,省略了include语句,2.2.1 顺序表的表示,26,void main(void)/主函数，字母线性表的生成和输出 n=26;/n是表长，是数据元素的个数，而不是V的实际下标 build();display();,void display()/字母线性表的显示，即读表操作 int i;for(i=0;i=n-1;i+)printf(%c,vi);printf(n);,执行结果：a b c d e f g h i j k l m n o p q r s t u v w x y z,2.2.1 顺序表的表示,27,2.2.2 顺序表的操作,数据结构的基本运算：修改、插入、删除、查找、排序,1)修改 通过数组的下标便可访问某个特定元素并修改之。,核心语句:Vi=x;,显然，顺序表修改操作的时间效率是 O(1),2.2.2 顺序表的操作,28,在线性表的第i个位置前插入一个元素,实现步骤：将第n至第i 位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i 是否合法?表是否已满?应当符合条件：1in+1 或 i=1,n+1,for(j=n;j=i;j-)aj+1=a j;a i=x;n+;,/元素后移一个位置,/插入x,/表长加1,核心语句：,2)插入,2.2.2 顺序表的操作,29,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,2.2.2 顺序表的操作,30,实现步骤：将第i+1 至第n 位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i 是否合法?应当符合条件：1in 或 i=1,n,删除线性表的第i个位置上的元素,for(j=i+1;j=n;j+)aj-1=aj;n-;,/元素前移一个位置,/表长减1,核心语句：,3)删除,2.2.2 顺序表的操作,31,删除顺序表中某个指定的元素的示意图如下：,顺序表插入和删除的完整程序请同学们自编，并务必上机验证！,2.2.2 顺序表的操作,32,2.2.3 顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置。,思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素，则向后移动元素的次数f(n)为:f(n)=,n i+1,时间效率分析:,2.2.3 顺序表的运算效率分析,33,推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移次数为n；若在a1后面插入，要后移n-1个元素，后移次数为n-1;若在an-1后面插入，后移次数为1；若在尾结点an之后插入，则后移次数为0；,故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n),共有多少种插入形式?连头带尾有n+1种!,所有可能的元素移动次数合计：0+1+n=n(n+1)/2,2.2.3 顺序表的运算效率分析,34,同理可证：顺序表删除一元素的时间效率为:T（n)=(n-1)/2 O(n),想一想：顺序表插入、删除算法的平均空间复杂度为多少？,插入效率：,删除效率：,教材P25算法2.5也是对执行效率的推导：,因为没有占用辅助空间！,含义：对于顺序表，插入、删除操作平均需要移动一半元素(n/2),O(1),即插入、删除算法的平均时间复杂度为 O(n),35,线性表的抽象数据类型定义（见教材P19）,ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R=|ai 1,ai D,i=2,n基本操作：,初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除,ADT List,数据结构课程的起点：,什么是线性结构？,36,第二章：线性表,Recap,37,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,2.2.1 顺序表的表示,Recap:,38,想一想：顺序表插入、删除算法的平均空间复杂度为多少？,插入效率：,删除效率：,因为没有占用辅助空间！,含义：对于顺序表，插入、删除操作平均需要移动一半元素(n/2),O(1),即插入、删除算法的平均时间复杂度为 O(n),Recap:,39,线性表的基本操作如何表示？（见教材P19）,InitList(/“看”表中全部元素（遍历）,初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除,40,结构体,结构体结构体是一种构造数据类型用途：把不同类型的数据组合成一个整体-自定义数据类型结构体类型定义,struct 结构体名 类型标识符 成员名；类型标识符 成员名；.；,成员类型可以是基本型或构造型,struct是关键字,不能省略,合法标识符可省:无名结构体,41,例 struct student int num;char name20;char sex;int age;float score;char addr30;,结构体类型定义描述结构的组织形式,不分配内存,结构体类型定义的作用域,42,例 struct student int num;char name20;char sex;int age;float score;char addr30;struct student stu1,stu2;,结构体变量的定义先定义结构体类型，再定义结构体变量一般形式：,struct 结构体名 类型标识符 成员名；类型标识符 成员名；.；struct 结构体名 变量名表列；,例#define STUDENT struct student STUDENT int num;char name20;char sex;int age;float score;char addr30;STUDENT stu1,stu2;,43,定义结构体类型的同时定义结构体变量一般形式：,struct 结构体名 类型标识符 成员名；类型标识符 成员名；.变量名表列；,例 struct student int num;char name20;char sex;int age;float score;char addr30;stu1,stu2;,44,说明结构体类型与结构体变量概念不同类型:不分配内存；变量:分配内存类型:不能赋值、存取、运算;变量:可以结构体可嵌套结构体成员名与程序中变量名可相同，不会混淆结构体类型及变量的作用域与生存期,45,结构体变量的引用引用规则 结构体变量不能整体引用,只能引用变量成员,可以将一个结构体变量赋值给另一个结构体变量结构体嵌套时逐级引用,成员(分量)运算符优先级:1结合性:从左向右,引用方式：结构体变量名.成员名,46,结构体数组结构体数组的定义三种形式：,形式一: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;,47,顺序表的C语言描述(p22),#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct ElemType*elem;int length;int listsize;SqList;SqList L;说明：elem数组指针指向线性表的基地址；length指示线性表的当前长度；listsize指示顺序表当前分配的存储空间大小。当空间不足时，再分配的存储空间增量为 LISTINCREMENT*sizeof(ElemType),48,malloc函数格式：void*malloc(unsigned int size);功能：在内存的动态存储区分配一个长度为size的连续空间，返回一个指向该区域起始地址的指针（void类型）free函数格式：void free(void*p)功能：释放由p指向的内存区 realloc的格式及功能 格式：void*realloc(void*p,unsigned size)功能：将p所指向的已分配内存区域的大小 改为size。size可以比原来分配的空间大或小,49,2)几个基本操作初始化(p23算法2.3),p23算法2.3 Status InitList_SqList(SqList,50,几个基本操作插入(p24算法2.4),Status ListInsert_sq(SqList 需将第n(即L.length)至第i个元素向后移动一个位置。注意：C语言中数组下标从0开始，则表中第i个数据元素是L.elemi-1,51,q=,几个基本操作插入,续(p24算法2.4),52,几个基本操作删除(p24p25算法2.5),Status ListDelete_sq(SqList/表长减1 return OK 需将第i+1至第L.length个元素向前移动一个位置,53,顺序表操作的典型例子,教材例2-1：求两个线性表的“并”，即：LA U LB=?,算法至少有两种：LA和LB都是无序表，则从LB中取元素逐一与LA中所有元素比较，相同则不插入LA中；若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。,54,顺序表的分析,1）优点顺序表的结构简单顺序表的存储效率高，是紧凑结构顺序表是一个随机存储结构（直接存取结构）2）缺点在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。原因：数组的静态特性造成,