数据结构授课教案-第2章.doc

山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学 分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花 山东轻工业学院教务处制授课时间年 月 日 星期 第 节年 月 日 星期 第 节年 月 日 星期 第 节授课内容概要第二章 线性表第一节 线性表的类型定义线性表的逻辑结构定义和抽象数据类型定义。第二节 线性表的顺序表示和实现顺序表的类型定义、查找、插入和删除。第三节 线性表的链式表示和实现线性链表（单链表）的结构、类型定义、查找、插入和删除；带头结点的单链表；循环链表的结构，循环链表与单链表操作的区别；双向链表的结构、类型定义、插入和删除。 目的要求目的：理解线性表的定义和实现。基本要求：了解线性表的逻辑结构和基本操作；理解循环链表和双向链表的概念和基本算法；掌握线性表的顺序存储结构及基本操作的实现、线性表的链式存储结构及基本操作的实现。重 点顺序表的定义、查找、插入和删除；单链表的定义、查找、插入和删除，头结点的作用；循环链表的定义，循环链表的操作和单链表操作的区别；双向链表的定义、插入和删除。难点单链表的定义、插入和删除；带头结点和不带头结点的单链表的基本操作的区别。作业布置习题2参考书1. 数据结构题集(C语言版), 严蔚敏，清华大学出版社，2002。3. 数据结构、算法与应用C+语言描述，(美)Sartaj Sahni著，汪诗林等译，机械工业出版社，2002。课 型理论课学时分配复 习 分钟主要教具投影、黑板讲 授 分钟教学方法讲解、提问、示例指 导 分钟教学手段板书、课件总 结 分钟备注共8学时，包括2学时的习题课。注：课型一栏填写理论课、实验课、习题课等授 课 内 容备 注第二章 线性表线性结构的特点：在数据元素的非空有限集中1. 存在唯一的一个被称做“第一个”的数据元素；2. 存在唯一的一个被称做“最后一个”的数据元素；3. 除第一个之外，每个元素都只有一个前驱；4. 除最后一个之外，每个元素都只有一个后继。2.1 线性表的逻辑结构 线性表是一种最简单的数据结构，它是一种线性结构。 线性表是n(n=0)个数据元素的有限序列，通常记为：(a1，a2， ai-1，ai，ai+1，an)其中:1) 同一线性表中的数据元素必须具有相同数据类型，2) ai是线性表的第i个元素，称i为数据元素ai的序号3) 相邻数据元素间存在序偶关系：将ai-1称为ai 的直接前趋，ai+1称为ai 的直接后继。a1 是表中第一个元素，它没有前趋；an 是最后一个元素无后继；其余有且仅有一个直接前趋 ，有且仅有一个直接后继 4) n为表长， n0 时称为空表（）。5) 线性表的数据元素，或者叫结点，或者叫记录，是独立的信息。它可以是一个数：例某校从1978年到1983年各种型号的计算机拥有量的变化情况可以用线性表表示为：（6，17，28，50，92，188）或一个符号，如英文字母表（A，B，Z）；也可以由若干个数据项组成：如：学生健康情况登记表如下： 线性表的其他表示方式:1) 二元组表示L= ， 其中:D= a1,a2, a3, . an; S= R R=, , 2)图示表示 线性表的基本操作：n 表的初始化n 存取操作：存、取线性表中第i个数据元素n 查找操作：在线性表中查找满足条件元素n 插入操作：在线性表的第i个元素之前插入n 删除操作：删除线性表的第i个元素n 遍历n 求表长 说明：1)上面列出的操作，只是线性表的一些常用的基本操作；2)线性表的复杂操作可通过基本操作实现；2.2 线性表的顺序存储和实现 线性表的顺序存储结构:指的是用一组地址连续的存储单元依次存储线性表的数据元素，用物理上的相邻表示逻辑上的相邻。 说明：l 在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来；l 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai+1 ) = Loc( ai )+ tLoc(ai ) = Loc(a1 )+ ( i 1) t 顺序表特点：可随机存取一、顺序表的类型定义：几种方法：1)# define ListSize 100 typedef int ElemType; ElemType ListListSize; int length;2)# define ListSize 100 typedef int ElemType; ElemType ListListSize; int length;3)# define ListSize 100 typedef int ElemType; typedef struct ElemType dataListSize; int length;SqList;4)#define LIST_INIT_SIZE 100#define LISTINCREAMENT 10typedef structElemType *elem;int length;int listsize;SqList二、顺序表上的基本操作1. 插入 功能：在顺序表v 中的第 i ( 1=i=ListSize)return -1; /*溢出*/ if (iL.length+1) return (0); /* i 值不合法*/for ( j=L.length-1 ; j= i-1; j-)L.dataj+1= L.data j;/* 结点移动 */ L.datai-1=e ; /* 插入e */ L.length+; /* 表长增1 */ return 1;/*插入成功，返回*/ /*第二种写法*/# define ListSize 100 typedef int ElemType; ElemType VectorListSize; int length;int insert_listSq (int i,ElemType e)if(length=ListSize)return -1; /*溢出*/ if (ilength+1) return (0); /* i 值不合法*/for ( j=length-1 ; j= i-1; j-)Vectorj+1= Vector j;/* 结点移动 */ Vectori-1=e ; /* 插入e */ length+; /* 表长增1 */ return 1;/*插入成功，返回*/ 顺序表插入算法分析：平均移动数据元素的次数：这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度T(n)(n)。 2. 删除 功能：在顺序表 删除第 i ( 1=i=n+1)个数据元素，将被删除元素值存入e, 删除前线性表为(a1, a2, a3, ai-1 ,ai, an )；删除后,线性表长度为n1, 线性表为(a1, a2, a3, ai-1 , ai+1, an )。 注意两点：1 第i+1至第n个元素（共ni个）依次前移2 表长减1 算法：# define ListSize 100 typedef int ElemType; typedef struct ElemType dataListSize; int length;SqList;int delete_listSq (SqList &L , int i,ElemType &e)if (iL.length) return (0); /* 检查空表及删除位置的合法性 */ e =L.datai-1 ; /* 取出第i个元素存入e */ for ( j=i-1; j=L.length-2; j+)L.dataj= L.data j+1;/* 结点移动 */ L.length-; /* 表长减1 */ return 1;/*删除成功，返回*/ 顺序表删除算法分析设删除第i个元素的概率为Pi，当Pi=1/ n，即为等概率情况，则平均移动数据元素的次数：这说明：在顺序表上做删除操作需移动表中一半的数据元素。显然时间复杂度T(n)(n)。 3. 初始化空表# define ListSize 100 typedef int ElemType; typedef struct ElemType dataListSize; int length;SqList;void init_listSq (SqList &L)L.length 0; return; 思考：采用其它的定义如何初始化空表？三 顺序表应用举例 设有两个按元素值递增有序排列的顺序表A和B，请编写算法将A和B归并成一个按元素值递增有序排列的线性表C。 void merge(SeqList A,SeqList B,SeqList &C)i=0;j=0;k=0; while ( iA.length & jB.length ) if (A.dataidatak+=A.datai+; else C-datak+=B.dataj+; while (idatak+= A.datai+; while (jdatak+=B.dataj+; C-length=k; 小结顺序表是线性表最简单的一种存储结构顺序表的特点：1 通过元素的存储顺序反映 线性表中 数据元素之间的逻辑关系；2 可随机存取顺序表的元素；3 顺序表的插入、删除操作要通过移动元素实现；2.3 线性表的链式表示和实现 由于顺序表的存贮特点是用物理上的相邻实现了逻辑上的相邻，优点是可以随机存取，但插入和删除操作会移动大量的结点。 本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。 2.3.1 线性链表 一 线性链表的概念 二 线性链表的基本操作算法 三 线性链表的其它操作 2.3.2 循环链表 2.3.3 双向链表 一 双向链表的概念 二 双向链表的基本操作算法2. 3. 1 线性链表一 线性链表（单链表）的概念1 线性链表 用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。 线性链表有关术语1)结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；1)结点的数据域：结点中用于保存数据元素的部分;2)结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;3)头指针：用于存放线性链表中第一个结点的存储地址;4)头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；5)带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为 带头结点的线性链表；通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中。 线性链表的类型定义typedef int elemtypetypedef struct node elemtype data;struct node *next; LNode，*LinkList；例：定义头指针变量：LinkList H；相当于定义了一个单链表H 两个C 函数1) malloc(int size) 功能：在系统内存中分配size个的存储单元，并返回该空间的基址。使用方法： p = (LinkList) malloc(sizeof(LNode ); 为p申请一个结点2) free ( p )功能：将指针变量p所指示的存储空间，回收到系统内存空间中去。使用方法：free(p)二 线性链表基本操作的算法1.建立单链表1）初始化空表 算法：初始化带头结点的线性链表LinkList init_List ( ) head = (LinkList)malloc(sizeof(LNode); head-next = null; return (head); 2）头插法建表 LinkList Creat_LinkList( ) 不带头节点 LinkList L=NULL；/*空表*/ scanf(%d,&x); while (x!=flag) s=malloc(sizeof(LNode); s-data=x; s-next=L; L=s; scanf (%d,&x); return L;例：线性表（25,45,18,76,29）之链表的建立过程。 2）尾插法建表 LinkList Creat_LinkList( )LinkList L=NULL; r=NULL; scanf(%d,&x); while (x!=flag) s=malloc(sizeof(LNode); s-data=x; if (L=NULL) L=s; /*第一个结点的处理*/ else r-next=s; /*其它结点的处理*/ r=s; /*r 指向新的尾结点*/ scanf(%d,&x); if ( r!=NULL) r-next=NULL; /*对于非空表，最后结点的指针域放空指针*/ return L;2. 查找(1)按序号查找Linklist Get_LinkList(LinkList L, int i)/*在带头结点的单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/ p=L;j=0;while (p-next !=NULL & jnext; j+; if (j=i) return p; else return NULL; (2)按值查找 Locate_LinkList(L,x)Linklist Locate_LinkList( LinkList L, elemtype x)/*在带头结点的单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/ p=L-next; while ( p!=NULL & p-data != x) p=p-next; return p; 3.插入(1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。操作如下：s-next=p-next;p-next=s;注意：两个指针的操作顺序不能交换。(2)前插结点：设指向链表中某结点，指向待插入的值为x的新结点，将*s插入到*p的前面。首先要找到*p的前驱*q;然后再完成在*q之后插入*s：s-next=q-next; q-next=s;(3)插入运算 Insert_LinkList(L,i,x)int Insert_LinkList( LinkList L, int i, datatype x) /*在单链表L的第i个位置上插入值为x的元素*/ Lnode * p,*s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p=NULL) printf(参数i错);return 0; /*第i-1个不存在不能插入*/ else s=malloc(sizeof(LNode); /*申请、填装结点*/ s-data=x; s-next=p-next; /*新结点插入在第i-1个结点的后面*/ p-next=s return 1; 4. 删除 (1)删除结点：设p指向单链表中某结点，删除*p。首先要找到*p的前驱结点*q，然后完成指针的操作即可：q-next=p-next;free(p);(2)删除运算：Del_LinkList(L,i)int Del_LinkList(LinkList L，int i) /*删除单链表L上的第i个数据结点*/ LinkList p,s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p=NULL) printf(第i-1个结点不存在);return -1; else if (p-next=NULL)