第2章线性表习题解答
更新时间:2024-03-22 20:50:02 阅读量: 综合文库 文档下载
- 第2章线性表自测卷答案推荐度:
- 相关推荐
第2章习题 ............................................................................................................................... 1
第2章习题
2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last,在实现各基本运算时需要做那些修改?
【解】
//用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType;
typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList;
//初始化
void initialList(seqList &S) { S.last=-1; }
//求表长度
int listLength(seqList S) { return S.last+1; }
//按序号取元素
bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>S.last+1) //i为元素编号,有效范围在1--S.last+1之间 return false; else { x=S.data[i-1]; return true; }
1
}
//查找元素x,成功:返回元素编号;失败:返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=S.last;i++) { if(S.data[i]==x) return i+1; //找到,转换为元素编号输出 } return 0; }
//插入元素
int listInsert(seqList &S,elementType x, int i) { int k; if(S.last>MAXLEN-1) return 0; //表满,返回0 else if(i<1 || i>S.last+2) return 1; //插入位置查处范围,返回1 else { for(k=S.last;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; S.last++; return 2; } }
//删除元素
int listDelete(seqList &S,int i) { int k; if(S.last==-1) return 0; //空表,返回0 else if(i<1 || i>S.last+1) return 1; //删除元素编号超出范围,返回1 else
2
{ for(k=i;k<=S.last;k++) S.data[k-1]=S.data[k]; S.last--; return 2; } }
//7. 打印表中所有元素 void printList(seqList L) { int i; for(i=0;i<=L.last;i++) cout< //8. 交互输入数据元素--特殊输入结束 void listInputC(seqList &L) { if(L.last>=0) { cout<<\顺序表已经存在,请先初始化,再输入元素。\ return; } elementType x; cout<<\请输入数据元素(整数,-9999退出):\ cout<<\ cin>>x; while(x!=-9999) { L.last++; L.data[L.last]=x; cout<<\ cin>>x; } } 3 //随机数创建顺序表 void rndCList(seqList &L) { int i; int n,m; L.last=-1; cout<<\请输入要产生的随机数个数,n=\ cin>>n; if(n>MAXLEN-1) { cout<<\您要求产生的随机数个数超出了查找表长度\,创建顺序表失败。\ return; } cout<<\请输入控制随机数大小参数,比如100以内数,请输入100,m=\ cin>>m; srand((unsigned)time(NULL)); //产生随机数种子 //srand((unsigned)GetTickCount()); //产生随机数种子 for(i=0;i L.last=n-1; //表长度为n cout< 2.2试用顺序表表示较多位数的大整数,以便于这类数据的存储。请选择合适的存放次序,并分别写出这类大数的比较、加、减、乘、除等运算,并分析算法的时间性能。 【解】顺序表0单元存放操作数的符号,区分操作数是正数还是负数;为方便处理运算时进位和借位,数据的低位存放数组低位,高位存放数组高位。 【时间性能】 加减法:O(max(m,n)) 乘除法:O(m?n) 2.3试用顺序表表示集合,并确定合适的约定,在此基础上编写算法以实现集合的交、并、差等运算,并分析各算法的时间性能。 【解】 //求C=A∩B 4 依次读取A的元素,检查次元素是否在B中,若在B中,则为交集元素,插入C中。 void interSet(seqList A, seqList B, seqList &C) { int i; for(i=0;i //求C=A∪B 现将A中元素全部插入C中。依次读取B中元素,检查是否出现在A中,若不在A中,则为并集元素,插入C中。 void mergeSet(seqList A, seqList B, seqList &C) { int i; for(i=0;i //求C=A-B 依次读取A中元素,检查是否在B中出现,若不在B中,则为差集元素,插入C中。 void differenceSet(seqList A,seqList B,seqList &C) { int i; for(i=0;i 5 【算法分析】 时间复杂度:O( |A| ? |B| ) 2.4假设顺序表L中的元素递增有序,设计算法在顺序表中插入元素x,要求插入后仍保持其递增有序特性,并要求时间尽可能少。 【解】 如果表空间满,插入失败,返回-1;否则,从L最后一个元素开始,与x比较,若大于x,元素后移,直到L中元素小于或等于x,这个元素的后面的单元即为x的插入位置,插入成功返回插入位置。 //空间满:返回值-1;正确插入:返回表中的插入位置 int incInsert(seqList &L,elementType x) { int i=L.listLen-1; if(L.listLen==MAXLEN) return -1; //表空间已满,不能插入新的元素 else { while(i>=0 && L.data[i]>x) { L.data[i+1]=L.data[i]; i--; } } L.data[i+1]=x; //插入x L.listLen++; //修改表长度 return i+2; //成功插入,返回x在顺序表中的插入位置(元素编号) } 【算法分析】 时间复杂度:O(n) 2.5假设顺序表L中的元素递增有序,设计算法在顺序表中插入元素x,并要求在插入后也没有相同的元素,即若表中存在相同的元素,则不执行插入操作。 【解】 与上题相似,只是在移动插入元素之前,检查L中是否已经存在值x,若存在,插入失败,返回-2。 //空间满:返回值-1;x已经存在返回-2;正确插入:返回表中的插入位置 int incInsert(seqList &L,elementType x) { int i; 6 if(L.listLen==MAXLEN) return -1; //表空间已满,不能插入新的元素 else { for(i=0;i return -2; //元素x已经存在,插入失败,返回-2 i=L.listLen-1; while(i>=0 && L.data[i]>x) //后移元素 { L.data[i+1]=L.data[i]; i--; } } L.data[i+1]=x; //插入x L.listLen++; //修改表长度 return i+2; //成功插入,返回x在顺序表中的插入位置(元素编号) } 2.6设计算法以删除顺序表中重复的元素,并分析算法的时间性能。 【解】 【分析】 三重循环实现。第一层循环,从左往右依次取出L元素,用i指示;第二层循环,对i元素在L中循环查重,用下标j指示;第三重循环,删除重复元素。 查重和删除从j=L.listLen-1开始,效率稍微好一点,因为这样重复元素本身不需重复移动。如果从i+1开始查重、删除,则j+1以后的重复元素会被移动。 【算法描述】 void DeleteRepeatData(seqList & L) { int i,j; if(L.listLen==0) { cout<<\当前顺序表空!\ return; } if(L.listLen==1) { cout<<\当前顺序表只有一个元素!\ 7 return; } i=0; while(i 【算法分析】时间性能:O(n3) 2.7假设顺序表L中的元素按从小到大的次序排列,设计算法以删除表中重复的元素, 并要求时间尽可能少。要求: (1)对顺序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法,并统计移动元素的次数。 (2)分析算法的时间性能。 【解】 【分析】 将元素分成两个部分:已经处理元素和待处理元素。已经处理部分返回L中,用下标i指示最后一个元素,初始化i=0。待处理部分用下标j指示第一个元素,初始化j=1. 左边下标小于i的元素已经处理好重复,等于i是当前正在处理的元素,将data[i]与data[j]进行比较,会出现下列情况: ① data[i]==data[j],说明j指示的是i的重复元素,继续处理j的下一个元素,即执行j++。 ② data[i] 循环执行上述操作,直到表尾。 修改L的长度为i+1。 【算法描述】 8 void DeleteRepeatData(seqList & L) { int i,j; //分别指向已处理部分最后元素和未处理部分第一个元素,皆为数组下标 if(L.listLen<2) return; //少于2个元素,直接退出 i=0; //初始化i指向第一个元素 j=1; //j指向第二个元素 while(j 【算法分析】时间复杂度O(n)。上例中只需移动8个元素。 2.8若递增有序顺序表A、B分别表示一个集合,设计算法求解A=A?B,并分析其时间性能。 【解】 【分析】 审题:A、B为集合,说明两个表中都没有重复元素 A=A∩B,即要求交集元素就放在A表中,而不是创建一个新表来存放。 设置两个指针ia、ib分别指向A、B表当前处理的元素; 设置一个指针i指示已经求取的交集元素在A的表中的最后元素位置; 比较A、B表当前元素,会出现以下三种情况 (1) A.data[ia]==B.data[ib],则ia或ib是交集元素,如果ia!=i+1,将ia元素复制到i+1,即:A.data[i+1]=A.data[ia];否则,若ia==i+1,说明ia就在i的后面,无需复制元素。最后,无论那种情况,修改指针:ia++,ib++,i++ (2) A.data[ia] 9 修改A表长度为i+1。 【算法描述】 void InterSet(seqList &A, seqList &B) { int i=-1; //为了最后更新交集元素表长度操作一致,初始化为-1 int ia=0, ib=0; //A、B表当前元素的数组下标 while(ia 2.9递增有序顺序表A、B分别表示一个集合,设计算法求解A=A-B,并分析其时间性能。 【解】【分析】 审题:A=A-B,即要求要利用A表的空间保存差集元素,而不是创建一个新表。 设置两个指针ia、ib分别指向A、B表当前处理的元素; 设置一个指针i指示已经求取的差集元素在A的表中的最后元素位置; 比较A、B表当前元素,会出现以下三种情况 (1) A.data[ia]==B.data[ib],则ia或ib是交集元素,不是A-B中元素,直接跳过,修改指针:ia++,ib++。 (2) A.data[ia]>B.data[ib],ia指示的元素可能在B表ib指示的元素后面,ia不动,移动ib,即ib++。 (3) A.data[ia] 重复以上过程,直至A、B中至少一个表结束。 还有一种情况:B表已结束,但A表尚未结束,说明A剩下元素不在B中,全为A-B中元素,全部迁移到目标位置。 10 最后,修改A表长度为i+1。 【算法描述】 void SetSubtraction(seqList & A, seqList & B) { int i=-1; //指示A中已经处理的最后元素 int ia=0, ib=0; //指示A、B中,当前待处理的元素,初始指向第一个元素 while( iaB.data[ib]) ib++; //此时,ia指示元素可能在B中ib指示的元素后面,移动ib。 else //此为,A.data[ia] //如果(i+1)==ia,说明ia元素不需迁移位置,直接为A-B中元素 if(i+1!=ia) //(i+1!=ia),需要将ia指示元素迁移到目标位置i+1 A.data[i+1]=A.data[ia]; i++; //A-B集合最后元素指示器后移 ia++; //A的指示器后移 } } //处理B已经,A尚未结束情况,A中剩下部分元素全部为A-B元素 while(ia 【算法分析】时间性能 O(|A| + |B|) 【思考问题】A、B两表谁先结束? 下面是本题的另一种解法,因为用到A表中交集元素的删除,所以效率较差。 【算法描述-1】 11 void SetSubtraction1(seqList & A, seqList & B) { int ia=0, ib=0; //ia、ib指示A、B表中当前元素。初始指向第一个元素。 while(iaB.data[ib]) //A元素可能在B中,移动B到下一个元素 { ib++; if(ib>=B.listLen) break; } else //A.data[ia]==B.data[ib],删除A中元素,同时移动指针 { listDelete(&A, ia+1); //ia++; 不能增加ia,因为A已经往前移动一个元素 ib++; if(ib>=B.listLen) break; } } } 【算法分析】时间性能 O(|A| + |B|) 12
正在阅读:
第2章线性表习题解答03-22
大学生毕业实习报告范文08-22
做好群众工作是领导干部的必修课——兼论毛泽东《关心群众生活r注意工作方法》的方法论意义07-23
《Autocad》课程标准模板08-14
心理健康教育心得体会(20篇汇总)04-29
廉政警示教育片《双面人生》观后感09-20
电子税务局网上领购发票操作手册 - 图文01-11
4-5级花卉园艺工理论复习资料06-22
旅游线路设计作业10-31
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 线性
- 习题
- 解答
- 2014年关于举办大连市第九届大学生结构设计竞赛的通知(1号) -
- 学生成绩管理系统
- 《防静电放电(ESD)损伤技术》研修班
- 无公害农产品产地认定与产品认证申请书
- 石林彝族自治县人民政府办公室关于加强专业应急救援队伍建设的通
- 目前我国的私营企业
- 紧急剖宫产流程图
- C语言程序设计基础教程 - 习题答案
- 超详细版王炜交通工程课后习题
- 关于印发三亚市全面打击违法建设行为工作方案的通知
- 2010年临床执业医师考试模拟试卷(1)(第二单元)-中大网校
- 六年级上册信息技术教学计划
- 在选调生培训班上的发言稿
- 多目标优化的求解方法
- 1月份高职考试模拟试卷(二)
- 宜宾市屏山镇中心2019年高中阶段学校招生考试数学模拟试卷
- 实验四参考模板
- 健康管理团队服务工作手册目录
- 最新 导游证考试到底有多难-精品
- 东财 资产评估作业答案新