《《线性表扩展与应用》ppt课件》由会员分享，可在线阅读，更多相关《《线性表扩展与应用》ppt课件（90页珍藏版）》请在金锄头文库上搜索。
1、线性表（扩展与应用）,2009/03/2,2,关于这门课,关于这门课，我希望随便了，不过还是轻一点题量较好，因为我们这学期每人至少有3个实验课（至多4个），其中两个要写比较长的实验报告，再加上这学期有好几门重要的理论专业课，所以实际上以前几个大二下您也应该有所体会了 关于这门课我希望不会太惨，但是真的是很难，因为大部分有一点点弱的（貌似计概后百分之五六十）都退了或没选。所以我貌似只能垫底了给分要厚道啊，这个班整体水平不正常啊，我们正常人还是想正常的过啊,3,关于这门课,关于这门课我希望练习能够多一些，因为我的基础比较差 训练的少了感觉学不明白 上课的知识不能在课堂上理解。 关于这门课我希望好好
2、学，事实上，我希望不惜一切代价学好它。 当然，希望结束这门课的时候，能有较好的编程能力。有很好的分数就更好了。而且，我希望可以参加大作业。希望老师和助教们可以多多帮忙，谢谢。,4,问题：,周二晚上上机时间和我的专业课有冲突，故不能到机房上机，那么关于必须上机时间内提交的选作题怎么处理呢？ 刚开始对于算法课程的内容我很茫然，觉得书上说的很抽象，不知道怎么解决具体问题，不过经过上次的上机，现在慢慢开始了解了。 希望进度不要太快。希望老师在课件上有一些程序的注释。 请问能否在上机时间之外再另设一段答疑时间？,5,意见：,对于您的课程，我唯一的一点点意见就是，希望您上课时声音可以大一点或者用麦克风，有
3、的时候不太听得清楚所以会很容易犯困=_= 关于这门课我希望老师在上课之前就能把课件放在网站上。还有一个建议：希望老师以后上课能用话筒 （-),6,安排：,上机 = 学习 + 自我测试 + 现场答疑 + 深入学习 在大环境中多做小题。选作题深入讲解。 Gmail + Google talk + google = bbs 加分是硬道理,7,上机中的一些问题（彭跃辉 ）,注意指针的初始化 初始化为0或NULL。 在.h文件中函数的声明必须与.cpp文件中函数的定义相匹配 包括函数名 返回值类型 参数类型和参数数量！ 同一工程中不能有两个main函数，否则会build错误！ cannot open D
4、ebug/XXX.exe 这个是因为有一个XXX.exe正在运行！ 标识符使用之前一定要定义 尽量使用有意义的标识符！ 注意C或C+中数组下标是从0开始，最后一个元素的下标是length-1 把自己修改过的地方加上注释，最好有一个大概思路。 在叫助教之前请先按Ctrl+a ALT+F8 格式化代码 大家可以学学基本的VC调试的方法 掌握调试的几个基本功能：设置/取消断点 运行到下一个断点 单步执行 和 递归的进入函数。,8,作业提交的一些问题,邮件的主题请包括学号和姓名 建议申请一个Gmail邮箱用于学习和交流。 使用rar压缩格式 附件最好改下名字，建议学号+题号，如：00700012-1-
5、2 编译通过后再提交。或者先把不能通过编译的问题仔细观察总结后直接提交问题。 在对同一个功能采用不同方式实现时，建议使用多个相近名称的操作函数，如：deleteAll_1(); deleteAll_2();并加以简单的注释。在主函数里也可以分别调用以演示功能。 鼓励相互讨论，反对相互copy，与其抄袭不如不交。,9,上机作业讲解,第一题,10,11,12,13,14,顺序表空间的扩展,发生在插入元素操作过程中 n = MAX 申请二倍空间；复制数据；释放原空间,element,15,16,上机作业讲解,第二题： 指针 指针的空间 指针指向元素的空间 结构体的空间问题,17,在链表尾部插入节点,
6、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 e
7、lementNum; ,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个结点开始寻找、输出和删除
8、表中的第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;
9、 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 =
10、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) 顺序表表示：只存系
11、数（第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
12、 *next Item ;,加法: 相同指数对应结点的系数项相加， 如和为0，删除结点，否则必定为 和链表的一个结点。 （实质上就是两个单链表的合并问题）,39,两个一元多项式的乘法,可以利用两个一元多项式相加的算法来实现 M(x) = A(x) B(x) = A(x) b1xe1+b2xe2+.+bnxen =,40,广义表,广义表也是零个或多个元素组成的序列。但是，广义表中的元素允许以不同形式出现:它可以是一个原子（逻辑上不能再分解的元素），也可以又是一个广义表。 作为广义表元素的广义表称作广义表的子（广义）表。一个广义表还允许直接或间接地作为它自身的子（广义）表。,41,广义表的书写约定
13、：,用大写字母表示广义表，用小写字母表示原子。例如： （） （，） （，）（，（，） （，）（，（，），） （，）（，（，），（，（，），） （，）（，（，（）,42,广义表,广义表也是零个或多个元素组成的序列。 广义表中的元素可以是一个原子，也可以是一个广义表。 一个广义表本身允许直接或间接地作为它自身的子（广义）表。,43,广义表的书写约定：,用大写字母表示广义表，用小写字母表示原子。例如： （） （，） （，）（，（，） （，）（，（，），） （，）（，（，），（，（，），） （，）（，（，（）,44,广义表的分类,如果广义表中的元素全部都是原子（例如广义表），这种广义表就是线性表； 如
14、果广义表中的元素允许有子广义表，但所有各层子广义表均无共享（例如广义表、），这种广义表，称为纯表； 在各层子广义表中允许共享的广义表（例如广义表的子表B中共享了A），称为再入表； 允许（子）广义表直接（或间接）地把作为自己的子广义表时，这样的广义表（例如广义表），称为递归表。,45,本章小结,ADT的基本概念及基本实现方法。 线性表的逻辑结构 线性表的顺序存储结构，要求能够灵活应用 顺序表上的插入、删除操作及其平均时间性能分析。 利用顺序表设计算法解决简单的应用问题。 线性表的链式存储结构的单链表，要求能够灵活应用。 单链表如何表示线性表中元素之间的逻辑关系。 单链表中头指针和头结点的使用。
15、单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 利用单链表设计算法解决简单的应用问题。 线性表的链式存储结构的循环链表和双链表，要求熟悉基本操作，能够简单应用。,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
