第3章 线性表

《第3章 线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章习题参考答案一、简答题1．【参考答案】：（1）线性表是将多个具有相同类型的数据元素放在一起构成一组有限序列的结构。还可以理解为第一个元素无前驱，最后一个元素无后继，而其他元素都有惟一直接前驱和直接后继的表结构。（2）顺序表是指线性表在顺序存储形式下构成的表。线性表逻辑上相邻的数据元素（直接前驱和直接后继）在存储位置（或物理位置）上也相邻。（3）链表也是一种有顺序的表，其内容可以存储在一组任意的存储单元中，所谓任意的存储单元，即这组存储单元可以连续的，也可以不连续的，这就需要在存储元素本身信息的同时，还要存储下一个元素的位置，由此构成一个链状结构，称其

2、为链表。（4）线性表的逻辑结构，即相临元素之间所满足的前驱和后继的逻辑关系。（5）一种逻辑结构可对应多种存储结构，而每种存储又有自己的存储特点和操作方式。2．【参考答案】：顺序表的基本操作包括：建立、插入、删除、查找等（下面以插入和删除过程为例，讲解实现过程）。插入操作具体过程为：首先确定插入位置i，按照an～ai的顺序由后至前依次将各元素向后移动，为新元素让出位置，将新元素x插入已经让出的第i个位置，结束插入操作。在规定位置删除某元素，删除操作的具体过程为：首先确定删除位置i，按照ai+1～an的顺序依次将各元素向前移动，将元素ai删除，结束删除操作。3

3、．【参考答案】：语法错误：node*L改为nodeL其功能：在线性表中查找与给定值x相等的数据元素4．【参考答案】：publicintdeleteAll(intT){//顺序表删除所有值为T的节点int[]data=L.data;intilen=data.length;intk=0;for(inti=0;i

4、//链式删除intcount=0;while(root!=null){if(root.getData()==T){root=root.getNext();}elsebreak;}LinkNodetmp=root.getNext();LinkNodetmp1=root;while(tmp!=null){if(tmp.getData()==T){tmp=tmp.getNext();count++;}else{tmp1.setNext(tmp);tmp1=tmp1.getNext();tmp=tmp.getNext();}}returncount;}5．【参考答

5、案】：对链表操作时，操作顺序对操作结果有影响。因为链表有两个区域，数据域、指针域，指针域指向下一个元素的地址或位置，若操作顺序不正确，可能使链表断裂。如，进行链表插入操作时，操作顺序是绝对不能调换的。二、简答题1．【参考答案】：publicMultiItemadd(MultiItemm){MultiItemrm=newMultiItem();SingleItemsroot=null;SingleItemsr=null;SingleItemsi1=this.getFirst();SingleItemsi2=m.getFirst();inti=0;while(

6、si1!=null){if(i==0){sroot=new43SingleItem(si1.getZhishu(),si1.getXishu()+si2.getXishu());sr=sroot;}else{SingleItemsi=newSingleItem(si1.getZhishu(),si1.getXishu()+si2.getXishu());sr.setNext(si);sr=sr.getNext();}si1=si1.getNext();si2=si2.getNext();i++;}rm.setFirst(sroot);returnrm;}}

7、2．【参考答案】：classNode{int[]data;intlength;publicNode(){}publicvoidsetLength(int[]data){this.length=data.length;}publicintgetLength(){returnlength;}publicstaticvoidset(int[]data,intk){intsum=0;for(inti=0;i

8、}}publicclassD{publicstaticvoidma