第3章 线性表.doc

第三章习题参考答案一、简答题1【参考答案】 ：（1）线性表是将多个具有相同类型的数据元素放在一起构成一组有限序列的结构。还可以理解为第一个元素无前驱，最后一个元素无后继，而其他元素都有惟一直接前驱和直接后继的表结构。（2）顺序表是指线性表在顺序存储形式下构成的表。线性表逻辑上相邻的数据元素（直接前驱和直接后继）在存储位置（或物理位置）上也相邻。 （3）链表也是一种有顺序的表，其内容可以存储在一组任意的存储单元中，所谓任意的存储单元，即这组存储单元可以连续的，也可以不连续的，这就需要在存储元素本身信息的同时，还要存储下一个元素的位置，由此构成一个链状结构，称其为链表。（4）线性表的逻辑结构，即相临元素之间所满足的前驱和后继的逻辑关系。（5）一种逻辑结构可对应多种存储结构，而每种存储又有自己的存储特点和操作方式。2【参考答案】 ：顺序表的基本操作包括：建立、插入、删除、查找等（下面以插入和删除过程为例，讲解实现过程）。插入操作具体过程为：首先确定插入位置 i ，按照anai 的顺序由后至前依次将各元素向后移动，为新元素让出位置，将新元素 x 插入已经让出的第i 个位置，结束插入操作。在规定位置删除某元素，删除操作的具体过程为：首先确定删除位置 i ，按照ai+1an 的顺序依次将各元素向前移动，将元素 ai 删除，结束删除操作。 3【参考答案】 ：语法错误：node * L 改为 node L其功能：在线性表中查找与给定值x相等的数据元素4【参考答案】 ：public int deleteAll(int T)/顺序表删除所有值为T的节点int data = L.data;int ilen = data.length;int k = 0;for(int i = 0; i ilen; i +)if(T=datai) for(int j = i; j ilen-1; j +) L.dataj = L.dataj+1; ilen-; i-;k +;return k;public int deleteAll(int T)/链式删除int count = 0;while(root!=null)if(root.getData()=T)root = root.getNext();elsebreak;LinkNode tmp = root.getNext();LinkNode tmp1 = root;while(tmp!=null)if(tmp.getData()=T)tmp = tmp.getNext();count +;elsetmp1.setNext(tmp);tmp1 = tmp1.getNext();tmp = tmp.getNext();return count;5【参考答案】 ： 对链表操作时，操作顺序对操作结果有影响。因为链表有两个区域，数据域、指针域，指针域指向下一个元素的地址或位置，若操作顺序不正确，可能使链表断裂。如，进行链表插入操作时，操作顺序是绝对不能调换的。二、简答题1【参考答案】 ：public MultiItem add(MultiItem m)MultiItem rm = new MultiItem();SingleItem sroot = null;SingleItem sr = null;SingleItem si1 = this.getFirst();SingleItem si2 = m.getFirst();int i = 0;while(si1!=null)if(i = 0)sroot = new SingleItem(si1.getZhishu(),si1.getXishu()+si2.getXishu();sr = sroot;elseSingleItem si = new SingleItem(si1.getZhishu(),si1.getXishu()+si2.getXishu();sr.setNext(si);sr = sr.getNext();si1 = si1.getNext();si2 = si2.getNext();i+;rm.setFirst(sroot);return rm;2【参考答案】 ：class Node int data; int length; public Node() public void setLength(int data) this.length=data.length; public int getLength() return length; public static void set(int data,int k) int sum=0; for(int i=0;idata.length;i+) if(datai=k) sum+; System.out.println(k+在该数组中出现的次数为：+sum); public class D public static void main(String args) Node L=new Node(); int data=26,35,45,57,3,4,5,26,89,26; L.set(data,26); 3 【参考答案】 ：public class H public static int sort(int a) int b;int ilen = a.length;int k = 0;if(ilen%2=0)b = new intilen/2;elseb = new intilen/2+1;for (int i = 0; i b.length; i+)bi = ak;k = k+2;return b;public static void main(String args) int a = 12, 23, 34, 45, 56, 67 ;int n = a.length;System.out.println(数组a的数为:);for (int i = 0; i a.length; i+) System.out.print(ai + ,);System.out.println();int b = sort(a);System.out.println(数组b的数为:);for (int i = 0; i b.length; i+) System.out.print(bi + ,);4【参考答案】 ：略三、思考题1【参考答案】 ：线性表的顺序存储结构实现比较简单，容易实现；在算法实现过程中要移动大量元素，同时在存储过程中，对于数据长度控制不是很容易。链式存储结构节省存储空间，但是实现算法中不需要大量移动元素，但是算法实现不是很容易。2【参考答案】 ：对双向链表、循环链表以及单链表存储结构都是属于链表的特点，即由数据域和指针区域构成，操作时都需要使用指针去定位相邻结点的位置，在进行插入、删除等操作时都需要进行链表的连接和删除操作，需要改变指针的位置以达到操作的目的；其不同点为单链表从头指针或者从某个固定位置开始，按顺序向后移动，双向链表可以从某个位置开始向两个方向进行操作，循环链表从某个位置开始，可以查找到该链表当中的任何结点。3【参考答案】 ：链表的头指针是一个和结点指针