数据结构（陈仲民）CH1-4.pptVIP

数 据 结 构 计算机系 陈仲民 联系方式E-Mail：chenzm@mail.hzau.edu.cn 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 第一章 绪 论 计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 ADT定义和实现独立，不只包括处理器已定义的数据类型，还包括设计软件系统用户自定义的长复杂数据类型，抽象层次越高，软件复用越多，使用者可利用公共界面中服务来使用它，不必关心其物理实现。 ADT体现了：分解、抽象、信息隐藏。 数学模型---------- ADT -------数据结构 非形式算法-------伪语言-------可执行程序 ADT的实现 , 面向过程、包（ada) 、OOP 小 结 在用计算机解题过程中，算法和数据结构是相辅相成、缺一不可的两个方面。数据结构是算法处理的对象也是设计算法的基础。一个具体问题的数据在计算机中往往可以采用多种不同的数据结构来表示；一个计算过程的实现又常常有多种可用的算法。因此选择什么样的算法和数据结构就成为实现程序过程中最重要的一个课题。 抽象数据类型的引入，提高了程序设计的抽象层次，也为数据结构和算法的研究提供了一种分层的模型。 重点掌握数据结构和算法的基本知识，理解它们在问题求解中的作用；了解下述概念：数据的逻辑结构、存储结构和操作，抽象数据类型，算法分析，空间代价和时间代价等。  第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 例3、学生健康情况登记表如下： 已知线性表 (4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，如图2.3所示。请注意区分元素的序号和数组的下标。 ???????? ?????????????? 图2.1 顺序表中插入元素? 算法实现： ?????? #define OK?? 1 ?????? #define ERROR? 0 int? InsList(SeqList *L,int i,ElemType e) /*在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L-last+1， i的合法取值范围是 1≤i≤L-last+2? */ { ?int k; if((i1) || (iL-last+2)) /*首先判断插入位置是否合法*/ { printf(“插入位置i值不合法”)； ???? return(ERROR); ?? } if(L-last=maxsize-1) { printf(“表已满无法插入”)； ? ?? ????return(ERROR); } for(k=L-last;k=i-1;k--)?? /*为插入元素而移动位置*/ L-elem[k+1]=L-elem[k]; L-elem[i-1]=e;?? /*在C语言数组中，第i个元素的下标为i-1*/ L-last++; Return(OK); ?? } 算法2.2? 线性表的插入运算 算法描述： ?int ?DelList(SeqList *L,int i,ElemType *e) /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1 */?? ? { ? int k; if((i1)||(iL-last+1))?? { ? printf(“删除位置不合法！”)； return(