《数据结构与算法分析》课程教学资源（书籍文献）数据结构与算法分析

刷除45 112336458060406. (a)时除前 1123368060406. (6)删除后 图2.3顺序表的删除操作示意图 图2.5顺序表的删除操作 涮除操作的算法实现如下： public T Delete(int i) T tmp; /判断表是否为空 if(IsEmpty()） throw new RuntimeException(("线性表为空，无法除")； /判断删除的位置是否正确 /11小于1表示删除第1个位置之前的元素， /1大于1ast+1表示删除最后一个元素后面的第1个位置的元素。 if(1<11川1>1ast+1) throw new RuntimeException("无效的下标："+i);/返回tmp tmp data[i -1]; /tmp值等于顺序表的第i个数据元素data[i-1] for (int j=i;j<=last;++j) data[j -1]data[j]; }11元素移动 -1ast;/修改表长 return tmp;/返回tmp值 算法的时间复杂度分析：顺序表上的删除操作与插入操作一样，时间主要消耗在数据的 移动上。在第i个位置删除一个元素，从ai+1到an都要向前移动一个位置，共需要移动n-i个元 2

26 图 2.5 顺序表的删除操作 删除操作的算法实现如下： public T Delete(int i) { T tmp; //判断表是否为空 if (IsEmpty()) { throw new RuntimeException("线性表为空，无法删除" ); } //判断删除的位置是否正确 // i 小于 1 表示删除第 1 个位置之前的元素， // i 大于 last+1 表示删除最后一个元素后面的第 1 个位置的元素。 if (i < 1 || i > last + 1) { throw new RuntimeException("无效的下标：" + i); //返回 tmp } tmp = data[i - 1]; // tmp 值等于顺序表的第 i 个数据元素 data[i-1] for (int j = i; j <= last; ++j) { data[j - 1] = data[j]; } //元素移动 -last; //修改表长 return tmp; //返回 tmp 值 } 算法的时间复杂度分析：顺序表上的删除操作与插入操作一样，时间主要消耗在数据的 移动上。在第i个位置删除一个元素，从ai+1到an都要向前移动一个位置，共需要移动n-i个元

素，而i的取值范围为1≤i≤n,当i等于1时，需要移动的元素个数最多，为n-l个：当i为n时 不需要移动元素。所以，删除操作的时间复杂度为O()。设在第i个位置做删除的概率为 pi=1m,则平均移动数据元素的次数为-1)2。这说明在顺序表上做删除操作平均需要移动表 中一半的数据元素。 (8)取表元取表元运算是返回顺序表中第i个数据元素，i的取值范围是1≤i≤ast+1。 步骤如下： ①判断表是否为空和位置是否正确 ②返回顺序表的第个数据元素 取表元运算的算法实现如下： public T GetElem(int i) (/判断表是否为空和位置是否正确 if (IsEmpty()) throw new RuntimeException("线性表为空，无法删除")； /1判断位置是否正确 //1小于1表示获取第1个位置之前的元素 /i大于1ast+1表示获取最后一个元素后面的第1个位置的元素。 if (i<1i>last +1) r throw new RuntimeException("无效的下标："+i);I/返回tmp return data[i-1];/返回顺序表的第i个数据元素 顺序表取表元运算的时间复杂度为0(1)。 (9)按值查找 顺序表中的按值查找是指在表中查找满足与给定值相等的数据元素。在顺序表中完成该 运算最简单的方法是：从第一个元素起依次与给定值比较，如果找到，则返回在顺序表中首 次出现与给定值相等的数据元素的序号，称为查找成功：否则，在顺序表中没有与给定值匹 配的数据元素，返回一个特殊值表示查找失败。 按值查找运算的算法实现如下： public int Locate(T value) r /顺序表为空 if (IsEmpty()) System.out.println("list is Empty"); return-1;

27 素，而i的取值范围为1≤i≤n，当i等于1时，需要移动的元素个数最多，为n-1个；当i为n时， 不需要移动元素。所以，删除操作的时间复杂度为O（n）。设在第i个位置做删除的概率为 pi=1/n，则平均移动数据元素的次数为(n-1)/2。这说明在顺序表上做删除操作平均需要移动表 中一半的数据元素。 （8）取表元 取表元运算是返回顺序表中第i个数据元素，i的取值范围是1≤i≤last+1。 步骤如下： ① 判断表是否为空和位置是否正确 ② 返回顺序表的第i个数据元素 取表元运算的算法实现如下： public T GetElem(int i) {//判断表是否为空和位置是否正确 if (IsEmpty()) { throw new RuntimeException("线性表为空，无法删除" ); } //判断位置是否正确 // i 小于 1 表示获取第 1 个位置之前的元素， // i 大于 last+1 表示获取最后一个元素后面的第 1 个位置的元素。 if (i < 1 || i > last + 1) { throw new RuntimeException("无效的下标：" + i); //返回 tmp } return data[i - 1];//返回顺序表的第 i 个数据元素 } 顺序表取表元运算的时间复杂度为O（1）。 （9）按值查找 顺序表中的按值查找是指在表中查找满足与给定值相等的数据元素。在顺序表中完成该 运算最简单的方法是：从第一个元素起依次与给定值比较，如果找到，则返回在顺序表中首 次出现与给定值相等的数据元素的序号，称为查找成功；否则，在顺序表中没有与给定值匹 配的数据元素，返回一个特殊值表示查找失败。 按值查找运算的算法实现如下： public int Locate(T value) { //顺序表为空 if (IsEmpty()) { System.out.println("list is Empty"); return -1; }

int i=0; /循环处理顺序表 for (i 0;i<=last;++i) /顺序表中存在与给定值相等的元素 if (data[i]==value) { break; /1顺序表中不存在与给定值相等的元素 if (i>last) { return -1: return i; 算法的时间复杂度分析：顺序表中的按值查找的主要运算是比较，比较的次数与给定值 在表中的位置和表长有关。当给定值与第一个数据元素相等时，比较次数为1：而当给定值与 最后一个元素相等时，比较次数为n。所以，平均比较次数为(n+1)2,时间复杂度为0(n)。 由于顺序表是用连续的空间存储数据元素，所以按值查找的方法很多。比如，如果顺序表是 有序的，则可以用折半查找法，这样效率可以提高很多。 (10)输出线性表中的元素。 public void printlist() //判断顺序表是否为空 if (IsEmpty()) System.out.println("list is Empty"); return; System.out.println("list is as follows:") int i=; /循环处理顺序表 for (i 0;i <last;++i) r System.out.println(data[i]);

28 int i = 0; //循环处理顺序表 for (i = 0; i <= last; ++i) { //顺序表中存在与给定值相等的元素 if (data[i]==value) { break; } } //顺序表中不存在与给定值相等的元素 if (i > last) { return -1; } return i; } 算法的时间复杂度分析：顺序表中的按值查找的主要运算是比较，比较的次数与给定值 在表中的位置和表长有关。当给定值与第一个数据元素相等时，比较次数为1；而当给定值与 最后一个元素相等时，比较次数为n。所以，平均比较次数为(n+1)/2，时间复杂度为O（n）。 由于顺序表是用连续的空间存储数据元素，所以按值查找的方法很多。比如，如果顺序表是 有序的，则可以用折半查找法，这样效率可以提高很多。 （10）输出线性表中的元素。 public void printlist() { //判断顺序表是否为空 if (IsEmpty()) { System.out.println("list is Empty"); return; } System.out.println("list is as follows:"); int i = 0; //循环处理顺序表 for (i = 0; i <= last; ++i) { System.out.println( data[i]); } }

2.2.4顺序表应用举例 【例1】己知顺序表L,写一算法将其倒置 (a) 1123 364580 6040 6 b 640608045362311 算法思路 把第一个元素与最后一个元素交换，把第二个元素与倒数第二个元素交换。一般地，把 第i个元素与第n-i个元素交换。i的取值范围是0到n/2(不包括n2,n为顺序表中元素的个数)。 存储整数的顺序表的倒置的算法实现如下： public static void ReversseqList(SeqList<Integer>L) {/顺序表数据类型是int int tmp =0; intn=L.Count();/n等于线性表的长度 /以下循环实现顺序表的倒置 for (int i=0;i<n/2;++i) { tmp =L.getdata(i); L.setdata(i,L.getdata(n-i-1)); L.setdata(n-i-1,tmp); 该算法只是对顺序表中的数据元素顺序扫描一遍即完成了倒置，所以时间复杂度为O)。 【例2】有数据类型为整型的顺序表La和Lb,其数据元素均按从小到大的升序排列，编 写一个算法将它们合并成一个表Lc,要求Lc中数据元素也按升序排列。 算法思路 依次扫描La和Lb的数据元素，比较La和Lb当前数据元素的值，将较小值的数据元素赋给 Lc,如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下的数据元素赋给Lc即可。 Lc的容量要能够容纳La和Lb两个表相加的长度。 按升序合并两个表的算法JAVA实现如下： public static SeqList<Integer>Merge(SeqList<Integer>La,SeqList<Integer>Lb) SeqList<Integer>Lc.new SeqListcInteger>(La.getMaxsize()+Lb.getMaxsize()); 29

29 2.2.4 顺序表应用举例 【例1】已知顺序表L，写一算法将其倒置。 (a) 11 23 36 45 80 60 40 6 (b) 6 40 60 80 45 36 23 11 算法思路: 把第一个元素与最后一个元素交换，把第二个元素与倒数第二个元素交换。一般地，把 第i个元素与第n-i个元素交换。i的取值范围是0到n/2(不包括n/2，n为顺序表中元素的个数)。 存储整数的顺序表的倒置的算法实现如下： public static void ReversSeqList(SeqList<Integer> L) { //顺序表数据类型是 int int tmp = 0; int n = L.Count();//n 等于线性表的长度 //以下循环实现顺序表的倒置 for (int i = 0; i< n/2; ++i) { tmp = L.getdata(i); L.setdata(i, L.getdata(n-i -1)); L.setdata(n-i-1,tmp); } } 该算法只是对顺序表中的数据元素顺序扫描一遍即完成了倒置，所以时间复杂度为O(n)。 【例2】有数据类型为整型的顺序表La和Lb，其数据元素均按从小到大的升序排列，编 写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。 算法思路 依次扫描La和Lb的数据元素，比较La和Lb当前数据元素的值，将较小值的数据元素赋给 Lc，如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下的数据元素赋给Lc即可。 Lc的容量要能够容纳La和Lb两个表相加的长度。 按升序合并两个表的算法JAVA实现如下： public static SeqList<Integer> Merge(SeqList<Integer> La, SeqList<Integer> Lb) { SeqList<Integer> Lc = new SeqList<Integer>(La.getMaxsize() + Lb.getMaxsize());

int i =0: int j=0; //两个表中都有数据元素 while ((i<=(La.count()-1))&&(j<=(Lb.count()-1))) if (La.getdata(i)<Lb.getdata(j)) Lc.Append(La.getdata(i++)); else { Lc.Append(Lb.getdata(j++)); 1/a表中还有数据元素 while (i<=(La.Count()-1)) Lc.Append(La.getdata(i++)): /b表中还有数据元素 while (j<=(Lb.count()-1)) Lc.Append(Lb.getdata(j++)); Lc.printlist(); return Lc; 算法的时间复杂度是O(m+n),m是La的表长，n是Lb的表长。 【例2-3】已知一个存储整数的顺序表La,试构造顺序表Lb,要求顺序表Lb中只包含顺 序表La中所有值不相同的数据元素。 算法思路： 先把顺序表La的第1个元素赋给顺序表Lb,然后从顺序表La的第2个元素起，每一个元素 与顺序表Lb中的每一个元素进行比较，如果不相同，则把该元素附加到顺序表Lb的末尾。 算法的JAVA实现如下： public static SeqList<Integer>Purge(SeqList<Integer>La) SeqList<Integer>Lb=new SeqList<Integer>(La.getMaxsize()); /将a表中的第1个数据元素赋给b表 Lb.Append(La.getdata(0));

30 int i = 0; int j = 0; //两个表中都有数据元素 while ((i <= (La.Count() - 1))&& (j <= (Lb.Count() - 1))) { if (La.getdata(i)< Lb.getdata(j)) { Lc.Append(La.getdata(i++)); } else { Lc.Append(Lb.getdata(j++)); } } //a 表中还有数据元素 while (i <= (La.Count() - 1)) { Lc.Append(La.getdata(i++)); } //b 表中还有数据元素 while (j <= (Lb.Count() - 1)) { Lc.Append(Lb.getdata(j++)); } Lc.printlist(); return Lc; } 算法的时间复杂度是O(m+n)，m是La的表长，n是Lb的表长。 【例2-3】已知一个存储整数的顺序表La，试构造顺序表Lb，要求顺序表Lb中只包含顺 序表La中所有值不相同的数据元素。 算法思路： 先把顺序表La的第1个元素赋给顺序表Lb，然后从顺序表La的第2个元素起，每一个元素 与顺序表Lb中的每一个元素进行比较，如果不相同，则把该元素附加到顺序表Lb的末尾。 算法的JAVA实现如下： public static SeqList<Integer> Purge(SeqList<Integer> La) { SeqList<Integer> Lb = new SeqList<Integer> (La.getMaxsize()); //将 a 表中的第 1 个数据元素赋给 b 表 Lb.Append(La.getdata(0));