考试安排.ppt
《考试安排.ppt》由会员分享,可在线阅读,更多相关《考试安排.ppt(62页珍藏版)》请在三一文库上搜索。
1、程序设计-2005年秋,1,考试安排,时间:1月4日(星期三)下午1:00-3:00 地点:3301 后面两周安排 12月21日:复习 12月28日:答疑 其它要求 12月31日前,提交所有平时作业!,程序设计-2005年秋,2,第11讲 结构和动态数据结构基础 (Part II),周水庚 2005年12月14日,程序设计-2005年秋,3,提要,结构类型和结构变量 结构数组 结构形参和结构指针形参 链表及其应用 联合 位域 枚举 类型定义,程序设计-2005年秋,4,提要,结构类型和结构变量 结构数组 结构形参和结构指针形参 链表及其应用 联合 位域 枚举 类型定义,程序设计-2005年秋,
2、5,链表程序设计实例-1,编写按整数输入顺序建立一个单向整数链表的函数 从空链表开始,每输入一个整数,向系统申请一个表元存储空间,将输入整数存入新表元并将新表元接在链表末尾。当不再有整数输入时,函数返回生成的链表的头指针值 为使新表元能方便地接在链表的末尾,引入指向链表的末尾表元的指针变量tail。建立空链表时,头指针h和末尾表元指针tail都置值NULL。将新表元接在链表末尾的工作要分两种情况。一是原链表为空链表;二是原链表有表元。下图是在链表末尾表元之后接一个表元的示意图,图中表元的整数用于区别不同表元,h,1,p,tail,8,9,NULL,NULL,(a) 接入前,h,tail,1,p
3、,8,9,NULL,NULL,(b) 接入后,在链表末尾表元之后接一个新表元,程序设计-2005年秋,7,链表程序设计实例-1(续),设链表的表元类型为前面说明的struct intNode类型 struct intNode *createList() struct intNode *h, /* 链表的头指针 */ *tail, /* 链表未尾表元的指针 */ *p; int n; h = tail = NULL; printf(“Input data.n“); while (scanf(“%d“, ,程序设计-2005年秋,8,链表程序设计实例-1(续),上述函数createList()定义
4、表明链表新表元总接在链表末尾 在有些情况下,对新表元放在链表中的位置没有要求,最简单的办法是将新表元插在链表首表元之前,即让新表元作为更新后链表的首表元。若要对函数createList()定义作这种改写,其中变量tail就不再需要了。另外,while 控制结构内的语句“p-next = NULL;”和if结构可用以下两个赋值代替: p-next = h; h = p; 第一个赋值表示新表元的后继表元为原链表中的首表元;第二个赋值表示让链表头指针指向新表元,程序设计-2005年秋,9,链表程序设计实例-2,编写一个函数,输入整数,建立一个按值从小到大顺序链接的链表 函数以输入整数进行循环,对每个
5、输入的整数,完成生成新表元、寻找插入位置和把新表元插入的工作。插入时,也要考虑插在首表元之前的情况。 struct intNode *cSortList() struct intNode *u, *w, *p, *h = NULL; int n; printf(“Input data.n“); while (scanf(“%d“, ,程序设计-2005年秋,10,链表程序设计实例-2(续),u = h; /* 寻找插入点 */ while (u != NULL ,程序设计-2005年秋,11,链表程序设计实例-3,编制一个函数,实现将已知链表的表元链接顺序颠倒。即使链表的第一个表元变为最末一个
6、表元,第二个表元变为最后第二个表元,最后一个表元变为第一个表元 设链表为整数链表,且链表是带辅助表元的。下图表示链表颠倒前和颠倒后的情况,h,h,1,2,3,/,/,1,2,3,n,n,NULL,NULL,上(a) 颠倒前,下(b) 颠倒后,链表颠倒示意图,程序设计-2005年秋,12,链表程序设计实例-3(续),颠倒操作是一个循环过程,设从第一个表元开始颠倒,每循环一次颠倒一个表元的链接关系,直至最后一个表元颠倒完成。设某次循环前已颠倒了前(i-1)个表元, 本次循环欲颠倒第i个表元的链接关系。为实现从颠倒前状态变为颠倒后的状态,可用以下四个赋值操作实现: p = v2-next; /* 保
7、护 v2 所指表元的后继指针 */ v2-next = v1; /* 使*v2后继表元是v1所指表元 */ v1 = v2; /* 调整 v1 */ v2 = p; /* 调整 v2 */,程序设计-2005年秋,13,v1,v2,i-1,i,i+1,(a) 颠倒前,v1,v2,i-1,i,i+1,(b) 颠倒后,p = v2-next; v2-next = v1; v1 = v2; v2 = p;,第 i 个表元颠倒前、后链表状态变化图,链表程序设计实例-3(续),程序设计-2005年秋,14,链表程序设计实例-3(续),/* 带辅助表元的链表颠倒 */ void reverse (stru
8、ct intNode *h) struct intNode *p, *v1, *v2; v2 = h-next; /* v2 指向链表的首表元 */ v1 = NULL; /* 开始颠倒时,已颠倒部分为空 */ while (v2 != NULL) /* 还未颠倒完,循环 */ p = v2-next; v2-next = v1; v1 = v2; v2 = p; h-next = v1; ,程序设计-2005年秋,15,链表程序设计实例-3(续),/* 不带辅助表元链表颠倒,已知链表首指针的指针 */ void reverse (struct intNode *hpt) struct int
9、Node *p, *v1, *v2; v2 = *hpt; /* v2 指向链表的首表元 */ v1 = NULL; /* 开始颠倒时,已颠倒部分为空 */ while (v2 != NULL) /* 还未颠倒完,循环 */ p = v2-next; v2-next = v1; v1 = v2; v2 = p; *hpt = v1; ,程序设计-2005年秋,16,链表程序设计实例-3(续),/* 不带辅助表元链表颠倒,已知链表首指针,返回链表首指针 */ struct intNode * reverse (struct intNode *h) struct intNode *p, *v1,
10、*v2; v2 = h; /* v2 指向链表的首表元 */ v1 = NULL; /* 开始颠倒时,已颠倒部分为空 */ while (v2 != NULL) /* 还未颠倒完,循环 */ p = v2-next; v2-next = v1; v1 = v2; v2 = p; return v1; ,程序设计-2005年秋,17,链表程序设计实例-4,编写一个多项式相加的函数。一个多项式 pn(x)=an*xn+an-1*xn-1+ + a1*x1+a0 用一个链表来表示。如p(x)=3*x3-1*x1+5用如下图所示的带辅助表元链表来表示。其中表元是由幂次、系数和后继表元指针三个成分组成的
11、结构。现编写用这种形式表示的两个多项式相加函数addpoly(),p -1 3 1 0 / 3 -1 5 NULL,多项式的链表表示,程序设计-2005年秋,18,链表程序设计实例-4(续),设函数addpoly()实现 l(x) + k(x) = l(x) 引入两个指针变量 lpt 和 kpt,分别指向l(x)链表和k(x) 链表的当前考察项。从高次项到低次项,逐项考察它们的项的指数: 如 (*lpt)的幂次与 (*kpt) 的幂次相等, 则 (*lpt) 的系数变为它们的和。但当和为零时, 项 (*lpt) 应从链表中删去。 若 (*lpt) 的幂次大于 (*kpt) 的幂次,则 (*lp
12、t) 不变。 若 (*lpt) 的幂次小于 (*kpt) 的幂次,则在 l(x) 的链表中插入一项, 其幂次与系数均与 (*kpt) 的相同,程序设计-2005年秋,19,链表程序设计实例-4(续),#include #define EPSILON 1.0e-5 #include struct node int power; double coef; struct node *link; ; void addpoly(struct node *l, struct node *k) struct node *p, *lpt, *kpt, *q; p = l; lpt = l-link; kpt
13、= k-link;,程序设计-2005年秋,20,链表程序设计实例-4(续),while (kpt) if (lpt = NULL) q=(struct node *)malloc(sizeof(struct node); q-power = kpt-power; q-coef = kpt-coef; q-link = NULL; p-link = q; p = q; kpt = kpt-link; else if (lpt-power = kpt-power) lpt-coef+=kpt-coef; /*等幂次项系数相加*/ if (fabs(lpt-coef) link = lpt-lin
14、k; free(lpt); else p = p-link;,程序设计-2005年秋,21,链表程序设计实例-4(续),lpt = p-link; kpt = kpt-link; else if (lpt-power kpt-power) /* 跳过 (*lpt) */ p = lpt; lpt = lpt-link; else /*lpt-powerpower 复制(*kpt),插在*p之后*/ q = (struct node *)malloc(sizeof(struct node); q-power = kpt-power; q-coef = kpt-coef; p-link = q;
15、q-link = lpt; p = q; kpt = kpt-link; return ; ,程序设计-2005年秋,22,链表程序设计实例-4(续),struct node *create_list() struct node *u, *w, *p, *h; int n; /* 建立空的带哨兵链表 */ h = (struct node *)malloc(sizeof(struct node); h-link = NULL; printf(“Input data.(less zero: finish)n“); scanf(“%d“, ,程序设计-2005年秋,23,链表程序设计实例-4(续)
16、,w-link = p; p-link = u; scanf(“%d“, ,程序设计-2005年秋,24,链表程序设计实例-4(续),q = h1; while (q) p = q-link; free(q); q = p; q = h2; while (q) p = q-link; free(q); q = p; ,程序设计-2005年秋,25,提要,结构类型和结构变量 结构数组 结构形参和结构指针形参 链表及其应用 联合 位域 枚举 类型定义,程序设计-2005年秋,26,联合,在某些特殊应用中,要求某些数据对象在程序执行的不同时期能存储不同类型的值。如某高级语言解释程序,可能需要一个变量
17、表,用于存储变量的值。因变量有整型、字符型或浮点型之分,该成分应能根据需要或存储整数、或存储字符、或存储浮点数。联合就是迎合类似这种需要而引入的 联合使在同一内存区域中,几种不同类型的值选其中之一存放。如联合的成分可能是一个整数、或是一个字符,或是一个实数,它们占用同一个存储区域,由最近放入的内容决定该区域究竟是整数、还是字符、或是浮点数 存于联合变量中的只能是一种数据,联合是多种数据类型值的覆盖存储。几种不同类型的数据从同一地址开始存储,但任一时刻只存储其中一种数据,而不是同时存放多种数据。分配给联合的存储区域大小,要求至少能存储其中最大一种数据,程序设计-2005年秋,27,联合类型定义,
18、定义联合类型的一般形式为: union 联合类型名 成分说明表 ; 如下面定义的联合类型(union udata)能存储整型,或字符型,或浮点型的数据: union udata int ival; char chval; float fval; ; 定义联合类型union udata,就可用该联合类型定义变量,程序设计-2005年秋,28,联合类型定义(续),如 union udata x, y, g; 也可将联合类型定义与变量定义合在一起,如 union udata int ival; char chval; float fval; x, y, g; 如类型名不再被引用,上述union之后的
19、标识符udata还可省略。从以上解释看到,联合与结构的定义形式非常相似。但它们的含义是不相同的,程序设计-2005年秋,29,引用联合成分,引用联合成分的书写形式也类似于引用结构成分的书写形式 如 x.ival (视联合变量 x 为 int 型的) y.chval (视联合变量 y 为 char 型的) g.fval (视联合变量 g 为 float 型的) 联合是把同一存储区域当作不同类型的变量来使用 union udata联合类型可用作解释程序的变量表中表元素某个成分的类型。假设变量只有整型,字符型和浮点型。联合能存储几种类型中的任何一种类型值,不管赋的是那一种类型的值,总是占用联合的全部
20、存储空间,程序设计-2005年秋,30,引用联合成分(续),联合也可出现在结构和数组中,联合也可包含有结构和数组。引用结构中的联合,或联合中的结构的书写形式与引用嵌套结构成分的书写形式一样,struct char name30; /* 标识符 */ int class_flag; /* 标识符属性类别 */ int uflag; /* 存于联合成分中的值的类型 */ union /* 存储变量值 */ int ival; /* 当变量为整型时 */ char chval; /* 当变量为字符型时 */ float fval; /* 当变量为浮点型时 */ uval; sym_tbl1000;
21、/* 变量表 */ 定义了一个结构数组 sym_tbl,用sym_tbl50.uval.fval引用结构数组sym_tbl中的第50 个结构的联合成分uval的fval(视其中的联合为浮点型数据),程序设计-2005年秋,31,使用联合变量注意事项-1,(1)一个联合可以存放多种不同类型数据,但在每一瞬间只能存放其中一种数据,而不是同时存放多种数据。存于联合中的值是最近一次存入的值。存入新值后,原有的值就全部或部分被新值所覆盖,原有的值就不再存在 如有以下赋值: x.ival = 1; x.fval = 2.0; x.chval= ?; 完成以上三个赋值后,只有x.chval是有效的,以x.i
22、val或x.fval引用其值已经变成不确定的了,程序设计-2005年秋,32,使用联合变量注意事项-1(续),实际使用联合时,为了记住最近存于联合中的值的类型,通常另外设有一个存于联合中的数据的类型标志量。如前面变量表sym_tbl的结构成分中的uflag。下面的代码输出变量表中表元sym_tbl50的值,switch (sym_tbl50.uflag) case INT: printf(“INT VALUE = %dn“, sym_tbl50.uval.ival); break; case CHAR: printf(“CHAR VALUE = %cn“, sym_tbl50.ural.chv
23、al); break; case FLOAT: printf(“FLOAT VALUE = %fn“, sym_tbl50.uval.fval); break; default: printf(“BAD TYPE n“); ,在描述中,假定符号INT,CHAR,FLOAT是某处已定义的常量,成分uflog只能取这三个值之一,分别代表变量取整型、字符型或浮点型值,程序设计-2005年秋,33,使用联合变量注意事项-2,(2)联合变量的开始地址和其成分变量的开始地址相同。如 /* 给u赋long型值 */ 则u.s0、u.s1、u.s2、u.s3是对long型值按字节的分拆,程序设计-2005年秋
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考试 安排
链接地址:https://www.31doc.com/p-2598506.html