数据结构教案第四章.doc

课程名称数据结构教学对象新华软工教 材数据结构（C语言）授课内容第四章 串课 时2教学目的与要求了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法重点、难点重点：串的顺序存储结构，堆分配存储结构,链式存储结构难点：串的模式匹配算法课 型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务一、串的基本概念前言：（用时5分钟） 计算机上的非数值处理的对象基本上是字符串数据，在较早的程序设计语言中，字符串的作为输入和输出出现的一、什么是串（用时10分钟）串是一种特殊的线性表，它是由零个或多个字符组成的有限序列，一般记作 s = “a1,a2, a3, . an” 其中 s-串名， a1,a2, a3, . an-串值 串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。下面是一些串的例子：（1）a = “This is a string”（2）b = “string”安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计(续表)（3）c = “ “（4）d = “”（5）e = “你好”说明：1) 串中包含的字符个数，称为串的长度。 长度为0的串称为空串，它不包括任何字符;2) 串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。二、串的有关术语（用时15分钟）1）子串 串中任意连续的字符组成的子序列称为该串的子串;例：c = “ DATA STRUCTURE”，f=“DATA” f是c的子串2）子串的位置 子串t 在主串S中的位置是指主串s 中第一个与T相同的子串的首字母在主串中的位置;例：s=“ababcabcac” , t=“abc” 子串T 在主串S中的位置为33）串相等 两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同；三、串的基本操作（用时35分钟）串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。1）串赋值操作assign( s, t) 功能：将串t 的值赋给串变量s ；2）串相等判断 equal(s,t) 函数3) 串的联接操作 concat( s , t ) 把串t 接在串 s 后面4) 求串长操作 lenght(s)5) 求子串操作sub ( s, start, len, t) 若 0=startlength(s) 0=len=length(s)-start 则t 中值为从串s 的第start个字符, 起长度为len 的字符序列, 并且函数返回值为1, 否则为0；6）求子串位置操作index( s, t ) 功能：如果s中存在与 t 相同的子串, 则返回s中第1个这样的子串的位置，若不存在返回07） 替换操作 replace( s, t ,v ) 功能：由串v 替换串s 中出现的所有和 t 相同的不重叠子串；教学过程设计(续表)8）复制串操作 strcopy(s, t) 功能：由串变量 s 复制得到串变量 t ；9）判空操作 empty( s ) 功能：若为空串，则返回1，否则返回010）串置空操作 ClearString( s ) 功能：将s 清为空串11) 串插入操作 StrInsert( s, start , t) 功能：将串t 插入到串s 的第start 字符之前12）串删除操作 StrDelete( s, start , len) 功能：从串s 中删除第 start 个字符起长度len 为的子串任务二、串存储和实现一、顺序存储结构（用时20分钟） 顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下： #define MAX 255 char chMAX 在数组ch中以字符0表示字符串的结束. 特点是访问容易, 但删除或插入麻烦二、链式存储结构（用时15分钟） 链式存储结构类似线性链表，由于串结构的特殊性, 要考虑每个结点是存放一个字符还是多个字符。一个字符的，插入、删除、求长度非常方便，但存储效率低。 多个字符的，改善了效率，在处理不定长的大字符串时很有效，但插入、删除不方便，可用特殊符号来填满未充分利用的结点。 复习思考题作 业上机任务案例分析：一个人的名字等等都是一个串，像这些形式如何存储？ 参考文献数据结构 （C语言版） 扬振生 中国科学技术大学出版社课后记（或归纳小结）本小节主要介绍串的概念，基本术语等，另外还有对串的两个常见的存储形式，下一节接着介绍串的另一种存储形式 课程名称数据结构教学对象新华软工教 材数据结构（C语言）授课内容第四章 串课 时2教学目的与要求了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法重点、难点重点：串的顺序存储结构，堆分配存储结构,链式存储结构难点：串的模式匹配算法课 型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务二、串存储和实现（续）三、堆分配存储（用时30分钟）堆分配存储类似于线性表的顺序存储结构，以一组地址连续的存储单元存放串值字符序列，其存储空间是在程序执行过程中动态分配的。一个串值的确定是通过串在堆中的起始位置和串的长度实现的。为此，串名与串值之间要建立一个对照表。 char storeMAX; int free ; */ 整型域：存放串长*/安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计(续表)任务三、串的基本运算实现（用时30分钟） #define MAX 100Char tMAX, sMAX;（1） 求长度 length(s) int length(char s ) int i; for (i=0, s i!=0;i+); return(i); (2) 求子串算法int sub(char s , int start, int len , char t ) int n,i; n=length(s); if (start =n )return (0); if ( lenn) return (0); /参数不合法 for (i=0;i=MAX) return(0); for(i=0;in;i+) sm+i=ti; tm+n=0; return (1); 教学过程设计(续表)(4) 判断串相等算法int equal( char s , char t ) int m, n, i; m= length(s); n=length(t); if (m!=n) return(0); for(i=0;im;i+) if (si!=ti)return(0); return (1);任务四、串的模式匹配算法（用时40分钟） 一、求子串位置的定位函数子串的定位操作index(s, t, start) 通常称作串的模式匹配（其中t 被称为模式串），是各种串处理系统中最重要的操作之一。 s=“abcdef”, t=“cde” index(s, t, 0)=2, index( s, t, 1)=2, t=“ab” index( s, t, 0)=0 t=“ad” index( s, t, 0)=-1二、BF 算法该算法的基本思想是，在主串 s 中从第 i ( i 的 初值为 start)个字符起，并且长度和 t 串相等的子串和 t 比较，若相等，则求得函数值为 i , 否则i增1 ，直至串 s 中不存在从 i 开始和 t 相等的子串为止匹配算法1int index( char s , char t , int start ) int i,eq,m,n; char subchMAX; m=strlen(s); n=strlen(t); if ( startm ) return(-1); i=start; while (ep=sub(s,i,n,subch) if(equal(t,subch) break; else i+;eq=sub(s,i,n,subch); if(eq)return(i); else return(-1); 例 s=“ababcabcac” t=“abcac” index(s,t,0)返回值为5复习思考题作 业上机任务案例分析：一个人的名字等等都是一个串，像这些形式如何存储？ 参考文献数据结构 （C语言版） 扬振生 中国科学技术大学出版社课后记（或归纳小结）本小节主要介绍串的概念，基本术语等，另外还有对串的两个常见的存储形式，下一节接着介绍串的另一种存储形式 课程名称数据结构教学对象新华软工教 材数据结构（C语言）授课内容第四章 串课 时2教学目的与要求了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法重点、难点重点：串的顺序存储结构，堆分配存储结构,链式存储结构难点：串的模式匹配算法KMP课 型电脑理论教学方法投影、讨论、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）任务四、串的模式匹配算法（续） （接上一节的序号）匹配算法2（用时40分钟）int index1(char s , char t , int start ) /返回在主串 s 第start个字符后子串t 的位置。若不存在，则函数值为-1。 int i, j, m, n; m=strlen(s); n=strlen(t); if (startm)return(-1); i=start;j=0; while (im & jn)安徽新华电脑专修学院课堂教学教案（电脑应用课使用）教学过程设计(续表)if(si=tj) i+; j+; /相等,继续比较后继字符 elsei=i-j+1; j=0; /不等,指针i后退(至当前匹配起始位置的 /下一位置）重新开始匹配 if(j=n) return(i- n);/匹配成功，返回子串T的位置 else return(-1);例 s=“ababcabcacbab” t=“abcac” start=0 index1(s,t,start)返回值为5匹配算法3（用时60分钟）一种改进算法是由D.E. Knuth, J.H.Morris, and V.R.Pratt. KMP匹配算法 int Index_KMP ( char s ,char t , int next ) int i = 0 ; j=0, m,n ; m=strlen(s); n=strlen(t); while ( i m & j =n) return ( i- n); else return(-1);void get_next ( char t , int next , int n) int j, k; j=0; k=-1; next0=-1; while(jn ) if (k=-1| t j =t k ) j+;k+; next j =k; else k=next k ; 复习思考题作 业上机任务案例分析： “abcac” 在“ababcabcacbab”中的位置，如何用算法实现？ 参考文献数据结构 （C语言版） 扬振生 中国科学技术大学出版社课后记（或归纳小结）本小节主要介绍子串在主串中的位置，如何用算法实现