【给学生】参考线性表.ppt

上机题目1 设计构造两个顺序映像线性表，分别用来表示一个班级学生的学号和体育成绩。成绩以递增的方式存储于线性表1中，学号则根据相应的成绩按顺序存储于线性表2中。因班里有学生转换专业离开或加入，程序能够对该表进行插入和删除的操作，插入或删除操作后的线性表仍然为有序表。 学生总数N不超过20人。 要求： 首先输入原始班级学生的总数N，然后按成绩增序手工输入学号和成绩，程序自动生成两个线性表； 程序提示是否有插入？（Y/N），如果是Y，输入新同学的学号和成绩，回车结束；否则进入下一步； 程序提示是否有删除？(Y/N)，如果是Y，输入被删除同学的学号，回车结束，程序在两个线性表中删除该同学的学号和记录；否则进入下一步； 最后显示操作后班级学生的学号和成绩，按成绩的增序排列。 上机题目2： 设计构造两个链式线性表，用来表示两个一元多项式 程序允许用户手工输入这两个线性表，每个线性表中的每个数据元素包含两个值，系数Pi和幂qi；输入方式自定； 程序对两个多项式进行相加，然后输出一个相加后的一元多项式。 双向链表的操作特点： “查询” 和单链表相同。 “插入” 和“删除”时需要同时修改两个方向上的指针。 ai-1 ai e s-next = p-next; p-next = s; s-next-prior = s; s-prior = p; p s ai-1 ai 插入 ai-1 删除 ai ai+1 p-next = p-next-next; p-next-prior = p; p ai-1 六、有序表类型 ADT Ordered_List { 数据对象: S = { xi|xi ? OrderedSet ， i=1,2,…,n, n≥0 } 集合中 任意两个 元素之间 均可以 进行比较 数据关系:R = {xi-1, xi | xi-1, xi ? S, xi-1≤ xi, i=2,3,…,n } 回顾例2-2的两个算法 LocateElem( L, e, q, int(*compare)(ElemType,ElemType) ) 初始条件：有序表L已存在。 操作结果：若有序表L中存在元素e，则 q指示L中第一个值为 e 的元素的位置，并返回函数值TRUE；否则 q 指示第一个大于 e 的元素的前驱的位置，并返回函数值FALSE。 基本操作： … … … … Compare是一个有序判定函数 ( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 ) 例如: 若 e = 45, 则 q 指向 若 e = 88, 则 q 指向 表示值为 88 的元素应插入在该指针所指结点之后。 void union(List La, List Lb) {// Lb 为线性表 InitList(La); // 构造(空的)线性表LA La_len=ListLength(La); Lb_len=ListLength(Lb); for (i = 1; i = Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第 i 个数据元素赋给 e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之 } } // union 算法时间复杂度：O(n2) void purge(List La, List Lb) { // Lb为有序表 InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); // 求线性表的长度 for (i = 1; i = Lb_len; i++) { } } // purge GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给 e if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } // La中不存在和 e 相同的数据元素，则插入之 算法时间复杂度：O(n