数据结构教案第二章.doc

课程名称数据结构教学对象新华软工专业教 材数据结构（C语言）授课内容第二章 线性表课 时2教学目的与要求本章主要介绍线性表的定义、运算和线性表的几种存储结构等内容重点、难点重点：线性表的定义、线性表的基本操作，线性表的存储结构难点：线性表的基本操作，线性表的存储结构课 型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务一、 线性表的定义和运算前言：（用时10分钟）线性表是最简单常用的数据结构，顺序存储结构和链式结构也是应用中最常用的存储方法，这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈、队列和串等特殊的线性表，数组和广义表是线性表的扩展，有助于理解和掌握树和图等复杂的数据结构一、线性表的定义和运算：（用时40分钟） 1、线性结构的特点是：在数据元素的非空有限集合中，、存在唯一的一个被称做“第一”的数据元素；、存在唯一的一个被称做“最后一个”的数据元素；、除第一个之外，集合中的每个数据元素均只有一个前驱；、除最后一个之外，集合中每个数据元素均只有一个后继。线性表是一个相当灵活的数据元素，它的长度可根据需要增长或缩短，简言之，一个线性表是个数据元素的有限序列安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计(续表)2、线性表的定义：线性表是由个元素（n=0）a1,a2,an组成的有限序列，记作（a1,a2,an）,其中称为表长度n=0时，称为空表补充说明：）对于某个元素ai:ai是第i个数据元素，称i为数据元素ai在线性表中的位序ai-1 , ai , ai+1 直接前驱直接后继 前驱后继）元素ai的定义：不同的场合，ai有不同的含义，但同一表中所有元素必须类型相同二、线性表的运算（六个基本运算）（用时50分钟）1、建空表：Initlist (&L)；2、求表长度：Listlength(L):返回中数据元素个数3、按序号取值：GetElem(L,i,&e):用e返回中第数据元素的值4、按值查找：LocateElem(L,e,compare() 初始条件：线性表L已存在，compare()是数据元素判定函数操作结果：返回L中第个与e满足关系compare()的数据元素的次序，若这样的数据元素不存在，则返回值为5、插入：ListInsert(&l,i,e) 初始条件：线性表已存在，= i = list 操作结果：在中第个位置之前插入新的数据元素，的长度加6、删除：istDelete(&L,i,&e) 初始条件：线性表已存在且非空1=i=listlength(&L) 操作结果：删除的第i数据元素，并用返回其值，的长度减 理论上（逻辑上）对线性表的所有操作只需这六个运算（称为完备的），但在实际应用中，考滤到速度等实际情况，可根据具体情况加以变化复习思考题作 业上机任务案例分析：学生的成绩表分析，每个学生的信息包含参考文献数据结构（C语言版） 扬振生 编著 中国科学技术大学出版社课后记（或归纳小结）总结一下本次课程所上的内容，通过这一章的了解学生知识什么是线性表；然后要求学生对此内容课后好好加深一下，并预习下一次的内容课程名称数据结构教学对象新华软工专业教 材数据结构（C语言）授课内容第二章 线性表课 时2教学目的与要求本章主要介绍线性表的定义、运算和线性表的几种存储结构等内容重点、难点重点：线性表的定义、线性表的基本操作，线性表的存储结构难点：线性表的基本操作，线性表的存储结构课 型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务二、顺序表: （存储结构，物理上要求相邻）（用时50分钟）复习： 复习上一次所上的内容，让今天所上的内容和这一次的内容要求连续性，并要求学生回签线性表的四个特点顺序表：指的是用一组地址连续的存储单元存储线性表的数据元素 （a1,a2,a3,a4,an) 假设有一个足够大的连续存储空间，将线性表中元素按照其逻辑次序依次存储顺序表Typedef struct ElemType *elem;/基地址 int length;/当前表长 int listsize;/最大分配量 sqlist; 安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计(续表)说明：）typedef 定义新的数据类型）计算每个数据元素的存储位置Loc(ai)=Loc(a1)+(i-1)*l,其中a1为起始地址或基地址，为每个数据元素占用的存储单元，即线性表的顺序存储结构是一种随机存取的存储结构，由此可得，只要确定了存储线性表的起始位置，线性表中的任一数据元素都可随机存取。插入：判定：1=i= L.listsize) printf(“The list is overflow n”); else if ( iL.length+1) ) printf(“ The insertion postion is not correct !n”); else if (i!=L.length+1) for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; L.length=L.length+1; L.elemi-1=b; 删除：Status ListDelete (sqlist &L,int I,Elemtype &b) int j ; if (iL.listsize) ) printf(“ The delete position is not correct !n”); else b=L.elemi-1; for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj; L.lenght=L.length-1; 教学过程设计(续表)算法分析：（用时50分钟）最占份量的语句是移动元素的for循环）在不同的位置上，移动元素个数不同=0,1 ,2,3,n次）假设在每一个位置上插入的概率相同的活，每次执行要移动的元素次数为： （0+1+2+3+4+n) n(n+1)/2 n n+1 n+1 2 注：b) 一般情况下，在第(1=i=n) 个元素之前插入一个元素时，需将第至第（共n-i+1)个元素向后移动一个位置a) 一般情况下，删除第+1（1=inext=p-next 2 p-next=s删除： 1 p-next=p-next-next一个动态函数的介绍：malloc( int size ) 功能：在系统内中分配size个存储单元，并返回该空间的基址使用方法：p=( Linklist )malloc( sizeof(LNode);为申请一个结点此函数以后我们会经常用到，这在语言也提过2、关于链表结构的讨论：（关于带头结点的单链表）教学过程设计(续表)要讨论的问题：不论插入、删除等对单链表的操作，因为首元素结点没有前驱，所以它的操作与其它位置不同，这将造成同一数据结构上操作的不一致性，不科学因此，在表头前一个结点头结点，使单链表成为带头结点的单链表，既可解决操作一致性的问题以后，我们将在该结构上讨论操作说明：在单链表中，每一个元素的存储位置都包含在其直接前驱结点的信息之中有：指向ai元素p-next指向ai+1元素3、线性链表基本操作的算法：（用时40分钟） 如何在线性链表的实现基本操作？如何建表？如何插入？删除？M约定带头结点的线性链表存储线性表）初始化操作：功能：建空线性表参数：head为线性链表的头指针主要步聚：调用malloc()分配一结点的空间，并将其地址赋值给head算法：LNode *create-head( ) LNode *head; head=(Linklist )malloc(sizeof(LNode); head-next=NULL; Return (head);）建立有个结点的线性单链表的算法：LNode *create-link ( n) LNode *head,*p,*q; int i; p=( Linklist )malloc (sizeof (LNode); head=p; for(i=1;idata=i; q-next=NULL; p-next=q; p=q; return (head); 教学过程设计(续表)）插入操作：Insert-Link(LNode *head,int x,int i) 功能：在线性链表的第i元素结点之前插入一个新元素结点插入操作步聚：a) 查找链表的系i-1个元素结点b) 为新元素建立结点c) 修改系i-1个元素结点的指针和新元素结点指针完成插入Int Insert_link ( Linklist &head,ElemType x,int i ) LNode *p,*s; int j ; p=head; j=0; while (p!=NULL)&(jnext; j+; if (p=NULL) return (0); s=( Linklist )malloc(sizeof(LNode); s-data=x; s-next=p-next; p-next=s; return (1);复习思考题作 业上机任务案例分析： 主要是对线性链表基本算法的实现参考文献数据结构（C语言版） 扬振生 编著 中国科学技术大学出版社课后记（或归纳小结）总结一下本次课程所上的内容，本章主要介绍的是线性表的链式存储，然后如何建立一个空的线性表，建立有n个结点的单链表的算法，如何对线性链表实现插入等等，最后要求学生对此内容课后好好加深一下，并预习下一次的内容课程名称数据结构教学对象新华软工专业教 材数据结构（C语言）授课内容第二章 线性表课 时2教学目的与要求本章主要介绍线性表的定义、运算和线性表的几种存储结构等内容重点、难点重点：线性表的定义、线性表的基本操作，线性表的存储结构难点：线性表的基本操作，线性表的存储结构课 型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务三、线性链表（非顺序映象或链式映象，原因是物理上不要求紧领）（续）复习：（用时10分钟） 复习上一次所上的内容，让今天所上的内容和这一次的内容要求连续性，另求两次的内容的完整性（接上一次课内容的序号）删除数据元数：删除操作主要步聚：a) 查找链表的第i-1个元素结点，使指针p指向它，将指针q指向第i个结点b) 修改第i-1个元素结点指针，使其指向第i个元素结点的后继安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计(续表)c) 回收q指针所指的第i个结点空间算法实现： （用时30分钟） int delete_link ( Linklist &head , int i) LNode *p,*q; p=head; j=0; while (p!=NULL)&(jnext;j+; if ( p=NULL ) return (0); q=p-next; p-next=q-next; free(q); return( ok ); 线性链表的小结：（用时10分钟）1)通过保存直接扣继元素的存储位置来表示数据元素之间的逻辑关系2)插入删除操作通过修改结点的指针实现3)不能随机存取元素线性表上机测试题：#define NULL 0 struct node int data; struct node *next;typedef struct node NODE; NODE *create_link ( int n ) NODE *head,*p,*q; int i; p= ( NODE *)malloc(sizeof(NODE); head=p; for( i=1;idata=i; q-next=NULL; p-next=q; p=q;return(head);教学过程设计(续表)int Insert_Link( NODE *head, int x,int i) NODE *p,*s; int j; p=head; j=0; while (p!=NULL)&(jnext; j+; if (p=NULL) return (0); s= ( NODE *) malloc(sizeof (NODE); s-data=x; s-next=p-next; p-next=s; return (1); main ( ) int j; NODE *t; t= create_link ( 10 ); for( j=1;jnext; printf(“%3d”,t-data); Insert_link( t,99,6); for (j=1;jnext; printf( “%3d”,t-next); 任务四、其他链表结构形式一、关于链表的一些概念：（用时10分钟）头指针：用于存放线性表中第一个结点的存储地址空指针：不指向任何结点，线性链表是最后一个结点的指针通常是空指针头结点：线性链表的第一个元素，结点前面的一个附加结点，称为头结点带头结点的线性链表：第一个元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表二、单向链表的概念：（用时40分钟）1、循环链表的概念：循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点2、循环链表图示：教学过程设计(续表)说明：）在解决某些实际问题时循环链表可能要比线性链表方便些，如将一个链表链在另一个链表的后面。）循环链表与线性链表操作的主要差别是算法中循环结束的条件，不是p或p-next是否为NULL,而是它们是否等于首指针。）对循环链表，有时不给出头指针，而是给出尾指针3、单向循环链表：带头结点且带尾指针的单循环链表见图所示 p=a-next; q=b-next; a-next=q-next; b-next=p; a=b; free(q);复习思考题作 业上机任务案例分析： 线性表的上机实现参考文献数据结构（C语言版） 扬振生 编著 中国科学技术大学出版社课后记（或归纳小结）总结一下本次课程所上的内容，本章主要介绍的是线性表的链式存储改进，单向循环链表等等，最后要求学生对此内容课后好好加深一下，并预习下一次的内容课程名称数据结构教学对象新华软工专业教 材数据结构（C语言）授课内容第二章 线性表课 时1教学目的与要求本章主要介绍线性表的定义、运算和线性表的几种存储结构等内容重点、难点重点：线性表的定义、线性表的基本操作，线性表的存储结构难点：线性表的基本操作，线性表的存储结构课 型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务四、其他链表结构形式（续）复习：（用时5分钟） 复习上一次所上的内容，让今天所上的内容和这一次的内容要求连续性，另求两次的内容的完整性（接上一次课内容的序号）三、双向链表：（用时10分钟）以上的链表中，可以从任何一个结点直接得到后继结点，但不能直接找出它的前驱结点1、双向链表的概念：双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点结点：安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计(续表)2、双向链表图示： 结构类型说明：typedef struct DuNode ElemType data; struct DuNode *prior; struct DuNode *next; DuNode,*Dulinklist;3、双向链表的基本操作算法：在双向链表中插入一个结点时指针的变化情况在P结点之前插入S结点：s=( Dulinklist ) malloc (sizeof (DuNode); s-next=p; s-prior=p-prior; p-prior=s; s-prior-next=s;在双向链表中删除某个结点：删除结点P教学过程设计(续表) 1) P-prior-next=p-next; 2) P-next-prior=p-prior; free(p);补充说明：链表：用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的任务五、一元多项式的表示及相加（用时35分钟）目的：为用计算机实现多项式运算，如何表示一元多项式？一、一元多项式的表示及相加：数学上：p(x)=p0+p1x+p2x2+pnxn; Q(x)=q0+q1x+q2x2+qnxn;不失一般性，设mindex index:p所指结点应为和多项式中的结点p-index = q-index: 将p所指结点的系数