《线性表扩展与应用》PPT课件.ppt

线性表（扩展与应用）,2009/03/2,2,关于这门课,关于这门课，我希望随便了，不过还是轻一点题量较好，因为我们这学期每人至少有3个实验课（至多4个），其中两个要写比较长的实验报告，再加上这学期有好几门重要的理论专业课，所以实际上以前几个大二下您也应该有所体会了 关于这门课我希望不会太惨，但是真的是很难，因为大部分有一点点弱的（貌似计概后百分之五六十）都退了或没选。所以我貌似只能垫底了给分要厚道啊，这个班整体水平不正常啊，我们正常人还是想正常的过啊,3,关于这门课,关于这门课我希望练习能够多一些，因为我的基础比较差 训练的少了感觉学不明白 上课的知识不能在课堂上理解。 关于这门课我希望好好学，事实上，我希望不惜一切代价学好它。 当然，希望结束这门课的时候，能有较好的编程能力。有很好的分数就更好了。而且，我希望可以参加大作业。希望老师和助教们可以多多帮忙，谢谢。,4,问题：,周二晚上上机时间和我的专业课有冲突，故不能到机房上机，那么关于必须上机时间内提交的选作题怎么处理呢？ 刚开始对于算法课程的内容我很茫然，觉得书上说的很抽象，不知道怎么解决具体问题，不过经过上次的上机，现在慢慢开始了解了。 希望进度不要太快。希望老师在课件上有一些程序的注释。 请问能否在上机时间之外再另设一段答疑时间？,5,意见：,对于您的课程，我唯一的一点点意见就是，希望您上课时声音可以大一点或者用麦克风，有的时候不太听得清楚所以会很容易犯困=_= 关于这门课我希望老师在上课之前就能把课件放在网站上。还有一个建议：希望老师以后上课能用话筒 （-),6,安排：,上机 = 学习 + 自我测试 + 现场答疑 + 深入学习 在大环境中多做小题。选作题深入讲解。 Gmail + Google talk + google = bbs 加分是硬道理,7,上机中的一些问题（彭跃辉 ）,注意指针的初始化 初始化为0或NULL。 在.h文件中函数的声明必须与.cpp文件中函数的定义相匹配 包括函数名 返回值类型 参数类型和参数数量！ 同一工程中不能有两个main函数，否则会build错误！ cannot open Debug/XXX.exe 这个是因为有一个XXX.exe正在运行！ 标识符使用之前一定要定义 尽量使用有意义的标识符！ 注意C或C+中数组下标是从0开始，最后一个元素的下标是length-1 把自己修改过的地方加上注释，最好有一个大概思路。 在叫助教之前请先按Ctrl+a ALT+F8 格式化代码 大家可以学学基本的VC调试的方法 掌握调试的几个基本功能：设置/取消断点 运行到下一个断点 单步执行 和 递归的进入函数。,8,作业提交的一些问题,邮件的主题请包括学号和姓名 建议申请一个Gmail邮箱用于学习和交流。 使用rar压缩格式 附件最好改下名字，建议学号+题号，如：00700012-1-2 编译通过后再提交。或者先把不能通过编译的问题仔细观察总结后直接提交问题。 在对同一个功能采用不同方式实现时，建议使用多个相近名称的操作函数，如：deleteAll_1(); deleteAll_2();并加以简单的注释。在主函数里也可以分别调用以演示功能。 鼓励相互讨论，反对相互copy，与其抄袭不如不交。,9,上机作业讲解,第一题,10,11,12,13,14,顺序表空间的扩展,发生在插入元素操作过程中 n = MAX 申请二倍空间；复制数据；释放原空间,element,15,16,上机作业讲解,第二题： 指针 指针的空间 指针指向元素的空间 结构体的空间问题,17,在链表尾部插入节点,18,在链表尾部插入节点,19,在链表尾部插入节点,20,删除从i开始k个节点,21,无头节点链表中删除从i开始k个节点,/p,q移动到i-1,/delete k nodes,/q移动k次,/删除中间节点,/？,22,删除从i开始k个节点,23,24,25,26,/by 骆文珊,27,几个相关的话题,有头、无头链表的优缺点 链表组成的线性表中 MAX, n有无意义？ 顺序表与链表的优缺点 常用的数据结构形式是什么？,28,用数组来实现链表结构,struct Node DataType num; int next ; struct Slinklist Node listMAXNUM; int elementNum; ,29,设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此反复直到所有的人全部出列为止。 Josephus问题是： 对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。,应用举例 Josephus问题,30,应用举例 Josephus问题,以n=8，s=1，m=4为例,31,应用举例 Josephus问题,求解Josephus问题的一般步骤为： （1）首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表； （2）从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程，直到Josephus表中的所有元素都删除。,32,应用举例 Josephus问题,main( ) /*主函数*/ PSeqList jos_alist; int i，k; int n,s,m; printf(“n please input the values(element); free(jos_alist); ,33,应用举例 Josephus问题,void josephus_seq( PSeqList palist, int s, int m) int s1, i, w; s1 = s - 1; for( i = palist-n; i0; i-) /* 找出列的元素 */ s1 = ( s1 + m - 1 ) % i ; /*下一个出列的元素*/ w = palist-elements1; /* 求下标为s1的元素的值 */ printf(“Out element %d n”,w); /* 元素出列 */ delete_seq(palist,s1); /* 删除出列的元素 */ ,34,算法复杂度分析 （顺序结构）,步骤： 1: 建立顺序表 2: 出列 时间复杂度分析：出列元素的删除（移动实现）为基本运算（每次最多i-1个元素移动，需要n-1次） (n-1)+(n-2)+1 = n(n-1)/2 = O(n2),35,算法复杂度分析 （链表结构）,步骤： (1)建立循环链表； (2)找循环单链表中的第s个结点放在指针变量p中 (3)从p所指结点开始计数寻找第m个结点，输出该结点的元素值； (4)删除该结点，并将该结点的下一个结点放在指针变量p中，转去执行(2)，直到所有结点被删除为止； 时间复杂度分析： 三部分时间（创建链表：O(n)+ 求第s个结点：O(s)+ 求n个第m个应出列的元素：O(m*n),36,一元多项式表示和运算-1,一元多项式：Pn(x) = p0+p1x+p2x2+pn xn 线性表表示：P=(p0, p1, p2, , pn) 顺序表表示：只存系数（第i个元素存xi的系数） 特殊问题：p(x) = 1+ 2x10000 + 4x40000 链表表示： 每个结点结构,系数,指数,0,-1,1,0,2,10000,4,40000,37,一元多项式的求和运算-2,数据： f(x)=6x3+12x2+10x+11 f(x)=3x2+5x+9; 运算：f(x)+g(x) f(x)-g(x) f(x)*g(x) f(x)/g(x) 用线性表表示多项式；用节点表示项；用节点之间的关系表示项之间的降幂关系。,38,一元多项式表示和运算-3,数据定义： typedef struct float c; /系数 int e; /指数 struct item *next Item ;,加法: 相同指数对应结点的系数项相加， 如和为0，删除结点，否则必定为 和链表的一个结点。 （实质上就是两个单链表的合并问题）,39,两个一元多项式的乘法,可以利用两个一元多项式相加的算法来实现 M(x) = A(x) B(x) = A(x) b1xe1+b2xe2+.+bnxen =,40,广义表,广义表也是零个或多个元素组成的序列。但是，广义表中的元素允许以不同形式出现:它可以是一个原子（逻辑上不能再分解的元素），也可以又是一个广义表。 作为广义表元素的广义表称作广义表的子（广义）表。一个广义表还允许直接或间接地作为它自身的子（广义）表。,41,广义表的书写约定：,用大写字母表示广义表，用小写字母表示原子。例如： （） （，） （，）（，（，） （，）（，（，），） （，）（，（，），（，（，），） （，）（，（，（）,42,广义表,广义表也是零个或多个元素组成的序列。 广义表中的元素可以是一个原子，也可以是一个广义表。 一个广义表本身允许直接或间接地作为它自身的子（广义）表。,43,广义表的书写约定：,用大写字母表示广义表，用小写字母表示原子。例如： （） （，） （，）（，（，） （，）（，（，），） （，）（，（，），（，（，），） （，）（，（，（）,44,广义表的分类,如果广义表中的元素全部都是原子（例如广义表），这种广义表就是线性表； 如果广义表中的元素允许有子广义表，但所有各层子广义表均无共享（例如广义表、），这种广义表，称为纯表； 在各层子广义表中允许共享的广义表（例如广义表的子表B中共享了A），称为再入表； 允许（子）广义表直接（或间接）地把作为自己的子广义表时，这样的广义表（例如广义表），称为递归表。,45,本章小结,ADT的基本概念及基本实现方法。 线性表的逻辑结构 线性表的顺序存储结构，要求能够灵活应用 顺序表上的插入、删除操作及其平均时间性能分析。 利用顺序表设计算法解决简单的应用问题。 线性表的链式存储结构的单链表，要求能够灵活应用。 单链表如何表示线性表中元素之间的逻辑关系。 单链表中头指针和头结点的使用。 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 利用单链表设计算法解决简单的应用问题。 线性表的链式存储结构的循环链表和双链表，要求熟悉基本操作，能够简单应用。,46,字符串基本概念,字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。 一个串可以记作s=“s0s1sn-1“（n 0），其中s是串的名字，双引号括起来的字符序列s0s1sn-是串的值。 例如： A = “123“ B = “ABBABBC“ C = “BB“ D = “BB “ E = “,47,C语言中定义的字符串,存储结构： 字符指针 0 操作： char *strcpy(char *dst, char *sorc) int strcmp(char *str1, char *str2); char* strcat(char *dest, const char* sorc,size); char* strstr(char *str, const char *strSearch); size_t strlen(const char* str); gets(char *); puts(char*);,48,由字符串构成的线性表,49,自定义字符串ADT,String createNullStr (void) 创建一个空串。 int IsNullStr ( String s ) 判断串s是否为空串，若为空串，则返回1，否则返回0。 int length ( String s ) 返回串s的长度。 String concat (String s1, Sting s2 ) 返回将串s1和s2拼接在一起构成的一个新串。 String subStr (String s, int i, int j ) 在串s中，求从串的第i个字符开始连续j个字符所构成的子串。 int index (String s1, String s2 ) 如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置。,50,顺序结构字符串ADT的定义,struct SeqString /* 顺序串的类型 */ int MAXNUM; /* 串允许的最大字符个数 */ int n; /* 串的长度，nMAXNUM */ char *c; ; typedef struct SeqString *PSeqString;,51,顺序串示例,s = “abcdefg”,a,b,c,d,e,f,g,s.n = 7 s.c,0 1 2 3 4 5 6 MAXNUM-1,52,自定义字符串ADT 创建顺序结构空串,PSeqString createNullStr_seq( int m ) PSeqString pstr = (PSeqString)malloc(sizeof(struct SeqString); if (pstr != NULL) pstr-c = (char* )malloc(sizeof (char)*m); if (pstr-c ！= NULL) pstr-n = 0; pstr-MAXNUM = m; return (pstr) else free (pstr); printf(“Out of space!n“); return NULL; ,struct SeqString int MAXNUM; int n; char *c; ;,53,自定义字符串ADT 初始化字符串,54,自定义字符串ADT 取指定子串,55,链接结构字符串ADT的定义,struct StrNode; /* 链串的结点 */ typedef struct StrNode *PStrNode; /* 结点指针类型 */ struct StrNode /* 链串的结点结构 */ char c; PStrNode link; ; typedef struct StrNode *LinkString; /* 链串的类型 */,字符串结尾？长度？,56,字符串的链接存储示例,s,a,b,c,d,s,a,b,c,d,不带头结点,带头结点,a,b,c,d,s,带尾指针的循环链表,57,链接存储字符串的基本运算,创建空链串 联结两个串 取单链串的子串 删除子串 追加方式插入子串 子串定位 模式匹配 求串长,58,创建带头结点的空链串,LinkString createNullStr_link( void ) LinkString pst; pst = (LinkString)malloc( sizeof(struct StrNode) ); if (pst!=NULL) pst-link = NULL; else printf(“Out of space! n“); /*创建失败*/ return (pst); ,59,取单链串的子串,60,作业：（上机完成）,P68 12， P68 13,16 提交：3月6号前 提交方式： 邮件名 学号#0305 打包rar后。 ftp提交（上机通知） 上机座位建议：4-5号机房尽量抱团分开坐。,61,Files,File: collection of data that is stored together under a common name, usually on a disk, magnetic tape, or CD-ROM Each file has a unique filename, referred to as the files external name For example, prices.dat and info.txt,62,File folder/path,data structure that can holds a group of files and can be hold in another high level folder. Disk name is the highest level of folder. Path: location of a folder e:mydocuments Absolute path; Relative path,63,Type of files,There are two basic types of files Text files (also known as character-based files): store each individual character, such as a letter, digit, dollar sign, decimal point, and so on, using an individual character code Binary files: use the same code as your computer processor uses internally for Cs primitive data types,64,File Streams,File stream: one-way transmission path used to connect a file stored on a physical device to a program Input file stream: receives data from a file into a program Output file stream: sends data to a file,65,File Streams (continued),Disk file,Output buffer,Input buffer,Program data,a,File streams,OS,66,Declaring a File Stream,For each file that your program uses, a file stream must be named (declared) and created (opened) Naming a file stream is accomplished by declaring a variable name to be of type FILE FILE *inFile; Asterisk is necessary Name is selected by programmer and internal to the program The FILE data structure is declared in stdio.h,67,Opening a file in a program:,file stream,File* fp;,Disk file,fp = fopen(“File Name”, ”r”);,program,OS,68,Opening a files stream:,Step1: Declare file pointer: (file stream) FILE *fp; Step2: Decided filename(path ) and opening mode: inFile.dat read Step3: Open the file (connect fp with a file stream) fp = fopen(“inFile.dat”, ”r”) ; Step4: Closing file: fclose (fp);,String constant,69,Closing a File Stream,A file stream is closed using fclose() fclose() breaks the link between the files external and internal names, releasing the internal file pointer name, which can then be used for another file fclose(inFile); Open files existing at the end of normal program execution are closed by the operating system,70,Opening and Closing a File Stream (exp.),fclose(inFile);,71,Opening a File Stream (mode indictors),72,Reading from and Writing to Text Files,fscanf() and fprintf(): Functions fscanf() and fprintf() are exactly like scanf() and printf() which read and write formatted data, except take an extra argument indicating which stream the input and output should be sent to. int fscanf(FILE *stream, const char *format .) ; int fprintf(FILE *stream, const char *format .) ;,73,Writing to a Text File,74,Reading from Text Files EOF,C appends the low-value hexadecimal byte 0x00 as the end-of-file (EOF) sentinel when the file is closed EOF sentinel is never counted as part of the file,75,Reading from a Text File (exp.),76,Reading from Text Files EOF,C appends the low-value hexadecimal byte 0x00 as the end-of-file (EOF) sentinel when the file is closed EOF sentinel is never counted as part of the file,77,Reading from a Text File (exp.),78,Standard Device Files,stdin data stream (read) from keyboard stdout data stream (write) from monitor stderr data stream (write) for error message,79,Get a line from stream,There are two line-oriented I/O functions, i.e. fgets() and fputs(), which allow us read and write lines instead of chracters. The function prototypes are: char *fgets(char *s, int n, FILE *stream) ; int *fputs(const char *s, FILE *stream); The second argument, n, of fgets() specifies the size of the array in which the string is stored.,80,Prog11.4,81,char * strstr(char *s1, const char *s2);,strstr returns a pointer to the beginning of the sub-string or NULL if not found. Exp: char string1 = “paper tiger“;