概论线性表new.ppt

《概论线性表new.ppt》由会员分享，可在线阅读，更多相关《概论线性表new.ppt（83页珍藏版）》请在三一文库上搜索。

1、数据结构,第1章 数据结构概论,本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准,1.1 数据结构研究的主要内容,当今计算机应用的特点： l 所处理的数据量大且具有一定的关系； 2 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。 应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。,表1-1,特点： l 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 2 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 3 对它的操作通常是插入某个

2、学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 应用举例2输出n个对象的全排列 输出n个对象的全排列可以使用下图1-1所示的形式描述。,图 1-1 3个对象的全排列过程,特点： l 在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构； l 对它的操作有：建立树形结构，输出最低层结点内容等等。 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示：,表1-2,课程先后关系的图形描形式：,c1,c9,c4,c2

3、,c12,c10,c11,c5,c3,c6,c7,c8,图 1-2 计算机专业必修课程开设先后关系,特点 l 课程之间的先后关系用图结构描述； 2 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。 结论 计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是数据结构这门课程研究的主要内容。,1.2 基本概念和术语,数据 是对客观事物的符号表示。在计算机科学中其含义是指所有能够

4、输入到计算机中并被计算机程序处理的符号集合。 数据元素 是数据集合中的一个实体，是计算机程序中加工处理的基本单位。 数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。,数据结构 简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、树形结构和图形结构。 逻辑结构 数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。,存储结构（物理结构） 是指数据结构在计算机存储器中的具体实现。与孤立的数据元素

5、表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。 常见的存储结构 顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构； 链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。,1.3 算法,1.3.1 算法的概念 算法是解决某个特定问题的一种方法或一个过程。 计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。,设计算法的基本过程 l 通过对问题进行详细地分析，抽象出相应的数学模型； 2 确定使用的数据结

6、构，并在此基础上设计对此数据结构实施各种操作的算法； 3 选用某种语言将算法转换成程序； 4 调试并运行这些程序。,算法应该具有下列五个特性 （1）有穷性：一个算法必须在执行有穷步之后结束。 （2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。 （3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。 （4）输入：一个算法应该有零个或多个输入。 （5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。,举例 问题：按从小到大的顺序重新排列x，y，z三个数值的内容。 算法： （1）输入x，y，z三个数值； （2）从三个数值

7、中挑选出最小者并换到x中； （3）从y，z中挑选出较小者并换到y中； （4）输出排序后的结果。,1.3.2 算法的描述 选择算法描述语言的准则 （1）该语言应该具有描述数据结构和算法的基本功能； （2）该语言应该尽可能地简捷，以便于掌握、理解； （3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。 “类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。,1. 预定义常量及类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #def

8、ine OVERFLOW -1 数据元素被约定为dateType 类型，用户需要根据具体情况，自行定义该数据类型。,2. 算法描述为以下的函数形式： 函数类型 函数名（函数参数表） 语句序列； 为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。,3. 在算法描述中可以使用的赋值语句形式有： 简单赋值 变量名 = 表达式； 串联赋值 变量名1 = 变量名2 = . = 变量名n = 表达式； 成组赋值 （变量名1，.，变量名n）=（

9、表达式1，.，表达式n）； 结构赋值 结构名1 = 结构名2； 结构名 =（值1，值2，.，值n）； 条件赋值 变量名 = 条件表达式 ? 表达式1：表达式2； 交换赋值 变量名1 变量名2；,4. 在算法描述中可以使用的选择结构语句形式有： 条件语句1 if （表达式） 语句； 条件语句2 if （表达式） 语句； else 语句； 开关语句1 switch （表达式） case 值1：语句序列1；break； case 值2：语句序列2；break； . case 值n：语句序列n；break； default：语句序列n+1； ,开关语句2 switch case 条件1：语句序列1；b

10、reak； case 条件2：语句序列2；break； . case 条件n：语句序列n；break； default：语句序列n+1； ,5. 在算法描述中可以使用的循环结构语句形式有： for循环语句 for （表达式1；循环条件表达式； 表达式2） 语句； while循环语句 while （循环条件表达式） 语句； do-while循环语句 do 语句序列； while （循环条件表达式）； 6. 在描述算法中可以使用的结束语句形式有： 函数结束语句 return 表达式； return; case或循环结束语句 break; 异常结束语句 exit（异常代码）；,7. 在算法描述中可以

11、使用的输入输出语句形式有： 输入语句 scanf( 格式串，变量名1，.，变量名n)； 输出语句 printf( 格式串，表达式1，.，表达式n); /方括号（ ）中的内容是可以省略的部分。 8. 在算法描述中使用的注释格式为： 单行注释 /文字序列 9. 在算法描述中可以使用的扩展函数有： 求最大值 max（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最大值。 求最小值 min（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最小值。,【算法1-1】用类C描述将三个数值排序的算法。 viod Three_Sort( int *x,int *y,in

12、t *z) /将x,y,z三个指针所指示的内容按从小到大的顺序重新排列 /挑选出最小的数值并换到 x指针所指的存储单元中 if (*y*x ,1.3.3 算法的评价 算法的评价标准 (1) 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。 (4) 高效性：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。,算法的时间效

13、率 算法的时间效率主要由两个因素决定： 1 所需处理问题的数据量大小，数据量大，所花费的时间就多； 2 在解决问题的过程中，基本操作的执行次数 时间特性的分析： 如果我们将一个算法所花费的时间设计成一个以数据量n为自变量的函数T(n)，这个函数在正整数定义域范围内一定是单调递增的。好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。,空间效率的分析 一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想

14、的情况。在设计算法时，应该注意空间效率。,第2章 线性表,线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例,2.1 线性表的定义和基本操作,2.1.1 线性表的定义 线性表是由n（n0）个类型相同的数据元素组成的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。,举例 La=（34，89，765，12，90，-34，22） 数据元素类型为int。

15、 Ls=(Hello,World, China, Welcome) 数据元素类型为string。 Lb=(book1,book2,.,book100) 数据元素类型为下列所示的结构类型： struct bookinfo int No; /图书编号 char *name; /图书名称 char *auther; /作者名称 .; ,2.1.2 线性表的基本操作 1. 初始化线性表L Init_List(L) 2. 销毁线性表L Destory_List(L) 3. 清空线性表L Clear_List(L) 4. 求线性表L的长度 Length_List (L) 5. 判断线性表L是否为空 IsE

16、mpty(L) 6. 获取线性表L中元素内容 Get _List (L,i,e) 7. 检索值为e的数据元素 Locate _List(L,x) 8. 在线性表L中插入一个数据元素 Insert_List (L,i,x) 9. 删除线性表L中第i个数据元素 Delete_List (L,i,e),2.2 线性表的顺序存储结构,2.2.1 线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：,图2-1 线性表顺序存储结构示意图,其中，L为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LO

17、C(ai)+L 线性表中任意一个数据元素的存储位置的计算公式为： LOC(ai+1)=LOC(a1)+(i-1)*L 顺序存储结构的特点 （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致。,（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。 在C语言中，实现线性表的顺序存储结构的类型定义 #define LIST_MAX_LENGTH 100 /线性表

18、的最大长度 typedef struct dataType 100; /数组名 int length; /线性表的当前最大下标 SQ_LIST；,2.2.2 典型操作的算法实现 SQ_LIST *L； /定义指针变量 1. 初始化线性表L SQ_LIST * InitList() SQ_LIST *L； L =malloc(sizeof(SQ_LIST ); L-length=-1； /将当前线性表长度置0 return L； ,2. 销毁线性表L void Destroy_List(SQ_LIST *L) if (L) free(L); /释放线性表占据的所有存储空间 3. 清空线性表L v

19、oid Clear_List(SQ_LIST *L) L-length=-1; /将线性表的长度置为0 ,4. 求线性表L的长度 int Length_List(SQ_LIST L) return (L.length+1); 5. 判断线性表L是否为空 int IsEmpty(SQ_LIST L) if (L.length= =-1) return TRUE; else return FALSE; ,6. 获取线性表L中的某个数据元素的内容 int Get _List(SQ_LIST L,int i,dataType *e) if (iL .length+1) return ERROR; /判

20、断i值是否合理，若不合理，返回ERROR *e=L .datai-1; /数组中第i-1的单元存储着线性表中第i个数据元素的内容 return OK; ,7. 在线性表L中检索值为e的数据元素 int Locate _List(SQ_LIST *L,dataType e) for (i=0;ilength;i+) if (L-datai= =e) return i+1; return 0; ,8. 在线性表L中第i个数据元素之前插入数据元素e int Insert_List (SQ_LIST *L,int i, dataType e) if (L-length=LIST_MAX_LENGTH-

21、1) return ERROR; /检查是否有剩余空间 if (iL-length+2) return ERROR; /检查i值是否合理 for (j=L-length;j=i-1; j- -) /将线性表第i个元素之后的所有元素向后移动 L-dataj+1=L-dataj; L-datai-1=e; /将新元素的内容放入线性表的第i个位置 L-length+; return OK; ,9. 将线性表L中第i个数据元素删除 int Delete_List (SQ_LIST *L,int i,dataType *e) if (IsEmpty(*L) return ERROR; /检测线性表是否为

22、空 if (iL-length+1) return ERROR; /检查i值是否合理 *e=L-datai-1; /将欲删除的数据元素内容保留在e所指示的存储单元中 for (j=i;jlength;j+) /将线性表第i+1个元素之后的所有元素向前移动 L-dataj-1=L-dataj; L-length- -; return OK; ,插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为： 分析结论 顺序存储结构表示的线

23、性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,2.3 线性表的链式存储结构,线性表顺序存储结构的特点： 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题： l 在做插入或删除元素的操作时，会产生大量的数据元素移动； 2 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； 3 线性表的容量难以扩充。,线性表的链式存储结构 线性表的链式存储结构是

24、指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图2-2所示的形式存储：,图2-2 线性表链式存储结构示意图,术语： 表示每个数据元素的两部分信息组合在一起被称为结点；其中表示数据元素内容的部分被称为数据域（data）； 表示直接后继元素存储地址的部分被称为指针或指针域（next）。 单链表简化的图2-3描述形式,图 2-3 单链表结构示意图,其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的

25、入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（ ）符号表示。 带头结点的单链表： 为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图2-4所示：,图 2-4 带头结点的单链表结构示意图,链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等。,在C语言中，实现线性表的链式存储结

26、构的类型定义 typedef struct node /结点类型及表头类型 datatype data; struct node *next; LNODE,* LINK_LIST;,2.3.2 典型操作的算法实现 1初始化链表L(在单链表的头部插入结点) LINK_LIST Init_List1() LINK_LIST L=NULL； LNODE *s; int x; scanf(“%d”, ,2 初始化链表L(在单链表的尾部插入结点) LINK_LIST Init_List2() LINK_LIST L=NULL； LNODE *s，*R=NULL; int x; scanf(“%d”, ,

27、2. 清空链表L void Destory_List(LINK_LIST L) LNODE *p; while (L-next) /依次删除链表中的所有结点 p=L-next; L-next=p-next; free(p); ,3. 求链表L的长度 int Length_List (LINK_LIST L) LNODE *p； int len； for(p=L, len=0；p-next!=NULL；len+,p=p-next); return(len)； ,4. 判链表L空否 int IsEmpty(LINK_LIST L) if (L-next=NULL) return TRUE; els

28、e return FALSE; ,5. 在链表L中查找到第i个元素，并把元素内容放到元素e中 LNODE *Get_List(LINK_LIST L,int i, dataType *e) LNODE *p=L; int j; /检测i值的合理性 if (iLength_List(L) return NULL; for (j=0;jnext,j+); *e=p-data; /将第i个结点的内容赋给e return p; /返回指针p ,6. 在链表L中检索值为e的数据元素 LNODE *LocateELem(LINK_LIST L,dataType e) LNODE *p; for (p=L-

29、next;p!=NULL ,7. 返回链表L中结点e的直接前驱结点 LNODE *PriorElem(LINK_LIST L,LNODE* e) LNODE *p; if (L-next-data=e) return NULL; /检测第一个结点 for (p=L-next;p-next!=NULL ,8. 返回链表L中结点e的直接后继结点 LNODE *NextElem(LINK_LIST L,LNODE *e) LNODE *p; for(p=L-next;p ,9. 在链表L中第i个数据元素之前插入数据元素e int Insert_List (LINK_LIST L,int i,data

30、Type e) LNODE *p,*s; p=Get_List(L,i-1); if(p= =NULL) printf(“参数错误！”);return 0; else s=malloc(sizeof(LNODE); if (s=NULL) return ERROR; s-data=e; s-next=p-next; p-next=s; return OK; ,10. 将链表L中第i个数据元素删除，并将其内容保存在e中 int Delete_List (LINK_LIST L,int i,dataType *e) LNODE *p，*s; p=Get_List(L,i-1); if(p= =NU

31、LL) printf(“第i-1个结点不存在！”);return -1; else if(p-next= =NULL) printf(“第i个结点不存在！”);return 0; else s=p-next; /用s指向将要删除的结点 *e=s-data; p-next=s-next; /删除s指针所指向的结点 free(s); return OK; ,2.3.3 循环链表 若将链表中最后一个结点的next域指向头结点 实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。,图2-7 带头结点的循环链表示

32、意图,1. 初始化链表CL LINK_LIST InitList() LINK_LIST CL; LNODE *s，*R=NULL; CL=(LNODE *)malloc(sizeof(LNODE)； CL-next=CL； int x; scanf(“%d”, ,2. 在循环链表CL中检索值为e的数据元素 LNODE *Locatedata(LINK_LIST CL,dataType e) LNODE *p; for (p=CL-next;(p!=CL) ,2.3.4 双向循环链表 在循环链表中，访问结点的特点：访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。 结论：循环链表并

33、不适用于经常访问前驱结点的情况。 解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。 双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。,图 2-8,head,(a),(b),用C语言实现双向循环链表的类型定义 typedef strcut du_node /双向链表的结点类型 dataType item; struct du_node *prior,*next; LNODE,* LINK_LIST;,（1）初始化双向循环链表DL LINK_LIST InitDuList() LINK_LIST DL; LNODE *s，*R=NULL; D

34、L=(LNODE *)malloc(sizeof(LNODE)； DL-next=CL；DL-prior=DL; int x; scanf(“%d”, ,（2）在双向循环链表DL中，第i个数据元素之前插入数据元素e 在一个结点之前插入一个新结点的过程。 在双向循环链表中的p结点之前插入s结点应使用下列语句序列： s-next=p; s-prior=p-prior; p-prior-next=s; p-prior=s;,图 2-9,p,s,2.4 线性表的应用举例,约瑟夫（Joseph）问题：编号为1，2，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整

35、数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。,假设有7个人，编号从1到7，他们手中的密码分别是3，1，7，2，4，8，4，最初的m=2，通过报数，这7个人离开桌旁的顺序应该是：2，3，5，4，7，6，1。 数据结构的分析 这个问题的主角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。,顺序存储结构算法描述 让n个人围坐在一张圆桌旁； for (i=1;i=n;i+)

36、从1开始报数，报到m停止；报到m的人离开桌子； 最终的算法实现 #define LIST_MAX_LENGTH 7 #define n LIST_MAX_LENGTH typedef int EntryType; /将EntryType定义为int类型,void Joseph(int code ,int n) /通过一维数组code带入n个人手中的密码，n是开始就坐在桌旁的人数 SQ_LIST people; int temp,m; /m是报数的上限值 scanf(“%d”, /将密码变为负值 ,链式存储结构 使用一个不带头结点的循环单链表结构。结点结构为：,图 2-10,用C语言定义 typ

37、edef struct /循环链表中每个结点的数据域部分的类型 int No; /编号 int code; /密码 INFO; typedef INFO EntryType;,算法 void Joseph(int code,int n) LINK_LIST people; LNODE *position,*pre; /position指向当前报数的结点 if (InitList(,position=people.head; /让position指向最后一个结点，以便报数从第一个开始 while (position-next!=people.head) position= NextElem(people,position); scanf(“%d”,printf(“%d”,position-item.No); /离开桌子处理 m=position-item.code; pre=PriorElem(people,position); pre-next=position-next; free(position); position= pre; printf(“%d”,position-item.No); /处理最后一个人 free(position); ,