概论线性表和数据结构

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课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6

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

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

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

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

7、。 1.3.2 算法的描述 选择算法描述语言的准则（1）该语言应该具有描述数据结构和算法的基本功能；（2）该语言应该尽可能地简捷，以便于掌握、理解；（3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。 “类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。 1. 预定义常量及类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 数据元素被约定为dateType 类型，用户需要根据具体情况，自行

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

9、条件赋值 变量名 = 条件表达式 ? 表达式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；break； case 条件2：语句序列2；break； . case 条件n：语句序列n；break； defa

10、ult：语句序列n+1； 5. 在算法描述中可以使用的循环结构语句形式有： for循环语句 for （表达式1；循环条件表达式； 表达式2） 语句； while循环语句 while （循环条件表达式） 语句； do-while循环语句 do 语句序列； while （循环条件表达式）；6. 在描述算法中可以使用的结束语句形式有： 函数结束语句 return 表达式； return; case或循环结束语句 break; 异常结束语句 exit（异常代码）； 7. 在算法描述中可以使用的输入输出语句形式有： 输入语句 scanf( 格式串，变量名1，.，变量名n)； 输出语句 printf( 格

11、式串，表达式1，.，表达式n); /方括号（ ）中的内容是可以省略的部分。8. 在算法描述中使用的注释格式为： 单行注释 /文字序列9. 在算法描述中可以使用的扩展函数有： 求最大值 max（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最大值。 求最小值 min（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最小值。【算法1-1】用类C描述将三个数值排序的算法。 viod Three_Sort( int *x,int *y,int *z)/将x,y,z三个指针所指示的内容按从小到大的顺序重新排列 /挑选出最小的数值并换到 x指针所指的存储单元中 i

12、f (*y*x&*y*z) *x*y; else if (*z*x&*z*y) *x*z; /在y和z所指示的存储单元中挑选出较小者换到y中 if(*zlength=-1； /将当前线性表长度置0 return L； 2. 销毁线性表Lvoid Destroy_List(SQ_LIST *L) if (L) free(L); /释放线性表占据的所有存储空间3. 清空线性表Lvoid Clear_List(SQ_LIST *L) L-length=-1; /将线性表的长度置为04. 求线性表L的长度int Length_List(SQ_LIST L) return (L.length+1); 5

13、. 判断线性表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; /判断i值是否合理，若不合理，返回ERROR *e=L .datai-1; /数组中第i-1的单元存储着线性表中第i个数据元素的内容 return OK;7. 在线性表L中检索值为e的数据元素int Locate _List(SQ_LIST

14、 *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-1) return ERROR; /检查是否有剩余空间 if (iL-length+2) return ERROR; /检查i值是否合理 for (j=L-length;j=i-1; j- -) /将线性表第i个元素之后的所有元素向后移动 L-d

15、ataj+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; /检测线性表是否为空 if (iL-length+1) return ERROR; /检查i值是否合理 *e=L-datai-1; /将欲删除的数据元素内容保留在e所指示的存储单元中 for (j=i;jlength;j+) /将线性表第i+1个元素之后的所有元素向前移

16、动 L-dataj-1=L-dataj; L-length- -; return OK; 插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为： 删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为： 分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。2.3 线性表的链式存储结构 线性表顺序存储结构的特点： 它是一种简单、方便的存储方式。它要求线性表的数据元素依次

17、存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题： l 在做插入或删除元素的操作时，会产生大量的数据元素移动； 2 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； 3 线性表的容量难以扩充。线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图2-2所示的形式存储：

18、图2-2 线性表链式存储结构示意图 术语： 表示每个数据元素的两部分信息组合在一起被称为结点；其中表示数据元素内容的部分被称为数据域（data）； 表示直接后继元素存储地址的部分被称为指针或指针域（next）。 单链表简化的图2-3描述形式headd cba图 2-3 单链表结构示意图 其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（ ）符号表示。 带头结点的单链表： 为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第

19、一个结点的特殊处理。如下图2-4所示：d headcba图 2-4 带头结点的单链表结构示意图链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等。在C语言中，实现线性表的链式存储结构的类型定义 typedef struct node /结点类型及表头类型 datatype data; struct node *next; LNODE,* LINK_LIST;2.3.2 典型操作的算法实现1初始化链表L(在单链表的

20、头部插入结点)LINK_LIST Init_List1() LINK_LIST L=NULL； LNODE *s; int x; scanf(“%d”,&x); while(x!=-1) s=malloc(sizeof(LNODE); s-data=x; s-next=L; L=s; scanf(“%d”,&x); return L ; 2 初始化链表L(在单链表的尾部插入结点)LINK_LIST Init_List2() LINK_LIST L=NULL； LNODE *s，*R=NULL; int x; scanf(“%d”,&x); while(x!=-1) s=malloc(sizeo

21、f(LNODE)； s-data=x； if (L= =NULL) L=s； else R-next=s； R=s； scanf(“%d”,&x)； if (R!=NULL) R-next=NULL； return L ; 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

22、-next!=NULL；len+,p=p-next); return(len)；4. 判链表L空否 int IsEmpty(LINK_LIST L) if (L-next=NULL) return TRUE; else 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个结

23、点的内容赋给e return p; /返回指针p6. 在链表L中检索值为e的数据元素LNODE *LocateELem(LINK_LIST L,dataType e) LNODE *p; for (p=L-next;p!=NULL&p-data!=e;p=p-next); /寻找满足条件的结点 return(p);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 & p-ne

24、xt-data!=e;p=p-next); if (p-next-data=e) return p; else return NULL; 8. 返回链表L中结点e的直接后继结点LNODE *NextElem(LINK_LIST L,LNODE *e) LNODE *p; for(p=L-next;p&p!=e;p=p-next); if (p) p=p-next; return p;9. 在链表L中第i个数据元素之前插入数据元素e int Insert_List (LINK_LIST L,int i,dataType e) LNODE *p,*s; p=Get_List(L,i-1); if(

25、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= =NULL) printf(“第i-1个结点不存在！”);return -1; else if(p

26、-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域指向头结点 实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。head 图2-7 带头结点的循环链表示意图1. 初始化链表CLLINK_LIST InitList() LINK_LIST

27、CL; LNODE *s，*R=NULL; CL=(LNODE *)malloc(sizeof(LNODE)； CL-next=CL； int x; scanf(“%d”,&x); while(x!=-1) s=(LNODE *)malloc(sizeof(LNODE)； s-data=x； if (CL-next= =CL) s-next=CL;CL-next=s； else s-next=CL;R-next=s； R=s； scanf(“%d”,&x)； return CL ; 2. 在循环链表CL中检索值为e的数据元素LNODE *Locatedata(LINK_LIST CL,data

28、Type e) LNODE *p; for (p=CL-next;(p!=CL)&(p-data!=e);p=p-next); if (p!=CL) return p; else return NULL ; 2.3.4 双向循环链表 在循环链表中，访问结点的特点：访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。 结论：循环链表并不适用于经常访问前驱结点的情况。 解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。 双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。图 2-8headprioritemnext(a)(b)用C语言实现

29、双向循环链表的类型定义typedef strcut du_node /双向链表的结点类型 dataType item; struct du_node *prior,*next;LNODE,* LINK_LIST;（1）初始化双向循环链表DLLINK_LIST InitDuList() LINK_LIST DL; LNODE *s，*R=NULL; DL=(LNODE *)malloc(sizeof(LNODE)； DL-next=CL；DL-prior=DL; int x; scanf(“%d”,&x); while(x!=-1) s=(LNODE *)malloc(sizeof(LNODE)

30、； s-data=x； if (DL-next= =DL) s-next=DL;DL-next=s； s-prior=DL;DL-prior=s； else s-next=DL;R-next=s； s-prior=R;DL-prior=s； R=s； scanf(“%d”,&x)； return DL ; （2）在双向循环链表DL中，第i个数据元素之前插入数据元素e 在一个结点之前插入一个新结点的过程。 在双向循环链表中的p结点之前插入s结点应使用下列语句序列： s-next=p; s-prior=p-prior; p-prior-next=s; p-prior=s;图 2-9ps2.4 线性表的应用举例 约瑟夫（Joseph）问题：编号为1，2，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值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个人，每