阅读《数据结构—Java语言描述》一书：打卡第五天
- 💂 个人网站: 路遥叶子
- 🤟 版权: 本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主
- 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
- 💅 想寻找共同成长的小伙伴，请点击【Java全栈开发社区】
目录
一、习题篇
(一) 概念题
(二) 算法设计题
（三）填空题
（四）简答题
1.什么是数据？
2.算法的五种性质
3.算法设计的目标
4.算法的描述方式
5.多项式时间算法的时间复杂度有哪些形式？
6.按照数据元素之间逻辑关系的特性可分为哪几类(作简要说明)？
7.顺序表的插入操作
8.顺序表的查找操作
9.列举几个常见的链表？
10.顺序表与链表的比较
11.算法的时间复杂度分析
12.影响一个程序的执行时间的主要因素有如下几个方面
(五) 线性表的应用举例
学生成绩管理系统
线性表接口
线性表接口实现类
学生成绩类
主函数，功能调试；测试类
测试结果
章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！
如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟
一、习题篇
(一) 概念题
1. 试述数据结构研究的3个方面的内容。
解析：数据结构研究的3个方面分布是：
数据的逻辑结构
数据的存储结构
数据的运算(操作)
----------------------------------------------------------------------------
2. 试述集合、线性结构、树形结构和图形结构4种常见的数据结构的特性。
集合结构
集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其他关系，它们之间的关系称为是松散性的
线性结构
线性结构中数据元素之间存在“一对一”的关系。
若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前驱但有一个后继。终端结点没有后继但有一个前驱。其余结点有其仅有一个前驱和后继。
树形结构
树形结构中数据元素之间存在“一对多”的关系。
若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可能有多个后继。
图形结构
图形结构中数据元素之间存在“多对多”的关系。
若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。
----------------------------------------------------------------------------
3. 设有数据的逻辑结构的二元组定义形式为B=(D,R), 其中D = {a1,a2,a3,......an} , R={ | i = 1,2,3.......n -1},请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。
顺序存储结构示意图:
链式结构示意图：
----------------------------------------------------------------------------
4. 设一个数据结构的逻辑结构如下图，请写成它的二元组定义形式。
解析：由于二元组的定义形式为B= (D,R) ; 如图可知：
D = {k1,k2,k3,k4,k5,k6,k7,k8,k9} ；
则R = {ROW,COL} 【{行,列}】。故：R = { , , , , , , , , , , }
----------------------------------------------------------------------------
5. 试确定下列程序段中有标记符号 ‘ # ’ 的语句行的语句频度(其中n为正整数)
i = 1 ; k = 0 ;while ( i <= n -1 ) { k += 10*i ; // # i++ ;}
i = 1 ; k = 0 ;do { k += 10 * i ; //# i++ ;}while (i <= n-1 )；
i = 1 ; k = 0 ;while ( i <= n -1 ) { i++ ; k += 10*i ; // #}
k = 0 ;for(int i = 1 ; i <= n ; i++ ) { for( int j = 1; j <= i ; j++ ) { k++ ; // # }}
i = 1 ; j = 0 ;while (i + j j ) { j ++ ; //# }else { i ++ ; }}
x = n ; y = 0 ; //n 是不小于1 的整数while (x >= (y+1) * (y+1) ) { y ++ ; //#}
x = 91 ; y = 100 ;while( y > 0 ) { if(x > 100 ) { x -= 10 ; y -- ; //# }else { x++ ; }}
a = 1 ; m = 1 ;while(a < n) { m += a ; a *= 3 ; //# }
----------------------------------------------------------------------------
(二) 算法设计题
1. 有一个包括100个数据元素的数组，每个数据元素的值都是实数，试编写一个求最大数据元素的值及其下标的算法；并分析算法的时间复杂度。
public void max(double[] list) { //初始化最大值为数组的第一个元素 double max = list[0] ; int index = 0 ; //记录索引 for (int i = 0; i < list.length; i++) { if (max < list[i]) { max = list[i] ; index = i ; } } System.out.println("最大的实数为:"+max+"\n其在数组中的小标为："+ index); //此算法的时间复杂度为O(n), 其中n为数组的长度。 }----------------------------------------------------------------------------
2. 编写一个实现将整数数组中的数据元素按值递增的顺序进行排序的java程序。
package data.linear_table.csdn;public class Demo02_desc { public static void main(String[] args) { int[] value = {49,38,65,97,76,13,27,49} ; System.out.print("排序前的数组中的数据元素： "); for (int i = 0; i < value.length; i++) { System.out.print(value[i]+"\t"); } System.out.println(); System.out.print("降序排序后的数组中的数据元素:"); int[] arr = bubbleSort(value); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+"\t"); } } public static int[] bubbleSort(int[] arr) { //arr为待排序的整数数组 int length = arr.length ; //数组的长度 boolean isExchange = true ; //判断是否交换位置的标志 //如果i 小于最大索引，并且交换标志为true 。 for (int i = 0 ; i < length - 1 && isExchange ; i++) { //最多可遍历的索引为数组长度-1 //将其交换标志设为false isExchange = false ; //如果j 小于当前元素索引位置 for (int j = 0 ; j arr[j+1]) { //如果前一个数，比后一个数大；交换数据元素 //满足交换条件，进行交换，定义一个变量视为中间变量。记录要交换的值 int temp = arr[j] ; arr[j] = arr[j+1] ; arr[j+1] = temp ; isExchange = true ; } } if (!isExchange) { break; } } return arr ; }}----------------------------------------------------------------------------
（三）填空题
- 线性表是一种最常用、最简单，也是最基本的____数据结构________
- 线性表由n个数据元素所构成的___有限序列_________，且数据类型相同
- 线性表可以用`顺序存储`和`___链式存储_________`两种存储结构来表示
- 链表可分为单链表、双向链表、____循环链表________、双向循环链表等
- 顺序表就是___顺序存储_________的线性表
- 顺序存储是用一组____地址连续________的存储单元依次存放线性表中各个数据元素的存储结构
- 线性表地址公式：__Loc(Ai) = Loc(A0) + i * c (第i的地址 = 第一个地址 + 第几个 * 存储单位)__________
- 在线性表中逻辑上相邻的数据元素，在__物理存储位置__上也是相邻的
- 算法__时间复杂度 _的高低直接反应算法执行时间的长短
- _数据元素__是数据结构中讨论的基本单位，不同场合也叫结点、顶点、记录
- __算法______是对特定问题求解步骤的一种描述，是指令的有限序列。其中每条指令表示一个或多个操作
- 对数据的操作包括：1.初始化：___创建、销毁____；2.数据操作：__增删改_____，3.数据使用：__查找、遍历__
- 采用链式存储方式存储的线性表称为___链表_________
- 若一个结点中只包含一个指针域，则称此链表为_____单链表_______
- 链表中每个结点包含存放元素值的___数据域_________和存放指向逻辑上相邻结点的____指针域________ 。
----------------------------------------------------------------------------
（四）简答题
1.什么是数据？
-----------------------------------------------------------------------------
2.算法的五种性质
-----------------------------------------------------------------------------
3.算法设计的目标
-----------------------------------------------------------------------------
4.算法的描述方式：
-----------------------------------------------------------------------------
5.多项式时间算法的时间复杂度有哪些形式？
-----------------------------------------------------------------------------
6.按照数据元素之间逻辑关系的特性可分为哪几类(作简要说明)？
集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其他关系，它们之间的关系称为是松散性的
线性结构中数据元素之间存在“一对一”的关系
树形结构中数据元素之间存在“一对多”的关系
图形结构中数据元素之间存在“多对多”的关系
-----------------------------------------------------------------------------
7.顺序表的插入操作：
public void insert(int i, Object x) { //0.1 满校验：存放实际长度 和 数组长度 一样 if(curLen == listEle.length) { throw new Exception("已满"); } //0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素 if(i curLen) { throw new Exception("位置非法"); } //1 将i及其之后后移 for(int j = curLen ; j > i; j --) { listEle[j] = listEle[j-1]; } //2 插入i处 listEle[i] = x; //3 记录长度 curLen ++;}-----------------------------------------------------------------------------
8.顺序表的查找操作
public int indexOf(Object x) { for(int i = 0; i < curLen ; i ++) { if(listEle[i].equals(x)) { return i; } } return -1;}
public int indexOf(Object x) { int j = 0; //用于记录索引信息 while(j < curLen && !listElem[j].equals(x)) { j++; } // j记录索引小于数量 if(j < curLen ) { return j; } else { return -1 }}-----------------------------------------------------------------------------
9.列举几个常见的链表？
-----------------------------------------------------------------------------
10.顺序表与链表的比较
-----------------------------------------------------------------------------
11.算法的时间复杂度分析
-----------------------------------------------------------------------------12.影响一个程序的执行时间的主要因素有如下几个方面
----------------------------------------------------------------------------
(五) 线性表的应用举例
学生成绩管理系统
编程实现学生成绩管理系统。此系统具有查询、修改、删除、增加和求全班各门课平均分的功能。要求采用顺序存储结构。
分析：由学生成绩表可知数据元素是由学号、姓名、性别、大学英语、高等数学5个数据项所构成。故可将数据元素描述为学生成绩类如下：
程序代码：
线性表接口
package data.linear_table;//线性表接口public interface IList { public void clear() ; //清空 public boolean isEmpty(); //判断是否为空 public int length(); // 表的长度 public Object get(int i) throws Exception; //获取元素的值 public void insert(int i , Object x) throws Exception; //在指定位置，插入指定元素 public void remove(int i ) throws Exception; //删除指定元素 public int indexOf(Object x) ; //查找指定元素第一次出现的位置 public void display() ; //输出元素的值} 线性表接口实现类
package data.linear_table;//线性表接口实现类public class SqList implements IList { private Object[] listElem ; //线性表的存储空间 private int curLen ; //线性表的当前长度 //顺序表类的构造函数，构造一个存储空间容量为maxSize的线性表 public SqList(int maxSize) { curLen = 0 ; //置顺序表的当前长度为0 listElem = new Object[maxSize]; //为顺序表分配maxSize个存储单元 } //将一个一存在的线性表置为空表 @Override public void clear() { curLen = 0 ; //置顺序表的当前长度为0 } //判断线性表的数据元素的个数是否为0 ，若为0则返回true,反之返回false @Override public boolean isEmpty() { return curLen == 0; } //求线性表中的数据元素的个数并返回值 @Override public int length() { return curLen; } //读取到线性表中的第i个数据元素并有函数返回其值。其中i的取值范围为：0 <= i <= length()-1 //若i 值不在此范围则抛出异常 @Override public Object get(int i) throws Exception { if (i curLen -1 ) { //i 小于或者大于表长-1 throw new Exception("第"+i+"个元素不存在"); //抛出异常 }else { return listElem[i] ; //返回顺序表中的第i个元素 } } //在线性表的第i个数据元素之前插入一个值为x的数据元素 @Override public void insert(int i, Object x) throws Exception { //0.1 满校验：存放实际长度 和 数组长度 一样 if(curLen == listElem.length) { throw new Exception("已满"); } //0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素 if(i curLen) { throw new Exception("位置非法"); } //1 将i及其之后后移 for(int j = curLen ; j > i; j --) { listElem[j] = listElem[j-1]; } //2 插入i处 listElem[i] = x; //3 记录长度 curLen ++; } //删除并返回线性表中的第i个数据 @Override public void remove(int i) throws Exception { // 0.1 校验非法数据 if(i curLen - 1 ) { throw new Exception("位置非法"); } // 1 将i之后向前移动 for(int j = i ; j < curLen - 1 ; j ++ ) { listElem[j] = listElem[j+1]; } // 2 长度减一 curLen--; } //返回线性表在首次出现指定的数据元素的位序号，若线性表在不包括此元素，则返回-1 @Override public int indexOf(Object x) { for(int i = 0; i < curLen ; i ++) { if(listElem[i].equals(x)) { return i; } } return -1; } /** * 使用变量记录没有匹配到索引 * @param x 要查找的数据 * @return */ public int indexOf2(Object x){ int j = 0 ; //用于记录索引信息 //while循环，循环条件是：j 小于线性表的长度， // 并且第j个数不等于要查找的数据，都满足才可进行循环。 while (j < curLen && !listElem[j].equals(x)){ //进行循环对其j进行++ j ++ ; } // j 记录索引的数量 if (j < curLen) { return j ; }else { return -1 ; } } //输出线性表中的数据元素 @Override public void display() { for (int i = 0; i < curLen; i++) { //输出 System.out.println(listElem[i]+" "); } }} 学生成绩类
package data.linear_table.test;import java.util.Scanner;//学生成绩表的系统中的数据，作为顺序表的数据元素listElem[i]//学生成绩类public class StudentNode { public int number ; //编号 public String name ; //姓名 public String sex ; //性别 public double english ; //大学英语 public double math ; //高等数学 //无参时的构造函数 public StudentNode() { this(0,null,null,0.0,0.0); } //有参数时的构造函数 public StudentNode(int number, String name, String sex, double english, double math) { this.number = number; this.name = name; this.sex = sex; this.english = english; this.math = math; } //用于手动输入学生对应信息 public StudentNode(Scanner sc) { this(sc.nextInt(),sc.next(),sc.next(),sc.nextDouble(),sc.nextDouble()); }} 主函数，功能调试；测试类
package data.linear_table.test;import data.linear_table.SqList;import java.util.Scanner;public class Student extends SqList { //主函数，用于功能调试 public static void main(String[] args) throws Exception { int maxSize = 1000 ; //设定最大存储空间 Scanner sc = new Scanner(System.in); System.out.println("------------- 建立学生成绩顺序表--------------------"); System.out.println("请输入学生的总数："); int n = sc.nextInt(); //表示线性表的长度 System.out.println("请按照学号、姓名、性别、大学英语、高等数学的顺序输入学生信息："); Student student = new Student(maxSize, n); //建立顺序表 while (true) { System.out.println("------------- 学生成绩管理系统--------------------"); System.out.println("现有学生列表信息："); student.display(); //输出学生信息 System.out.println("[1]查询\t[2]添加\t[3]删除\t[4]求平均分"); int temp = sc.nextInt(); switch (temp){ case 1 : System.out.println("请输入要查询的学生的学号："); student.displayNode(student.get(sc.nextInt())); //取出成功，则输出该学生的信息 break; case 2: System.out.println("请输入需要增加的学生信息："); student.insert(new StudentNode(sc)); //在顺序表插入指定的信息 break; case 3: System.out.println("请输入要删除的学生的学号："); student.remove(sc.nextInt()); //删除指定学生的学号 break; case 4: System.out.println("请输入你要查询全部平均分的科目名称："); String s = sc.next(); double avg = student.avg(s); System.out.println(s+"的全班平均分为："+avg); } } } //按照顺序构造顺序表，其中参数maxSize指的是顺序表的最大存储容量 public Student(int maxSize, int n) throws Exception { super(maxSize); Scanner sc = new Scanner(System.in); //创建含有n个数据元素的顺序表 for (int i = 1; i <= n; i++) { StudentNode node = new StudentNode(sc); if (node != null) { //将录入的学生数据元素插入顺序表的表尾 insert(node); } else { //若不成功就不计数 i--; } } } //覆盖父类的get方法; 从顺序表中取出指定学号的学生信息 public StudentNode get(int number) throws Exception { //遍历顺序表 for (int i = 0; i < length(); i++) { //强转数据类型 StudentNode node = (StudentNode) super.get(i); //调用父类的get方法 if (node.number == number) { return node; //包含指定的学号，返回该学生的信息 } } //否则抛出异常 throw new Exception("学号" + number + "不存在"); } //重载父类的insert方法，在顺序表的表尾插入一个学生信息 public void insert(StudentNode node) throws Exception { //调用父类的insert方法。在顺序表尾部插入 try { super.insert(this.length(), node); System.out.println("添加成功"); } catch (Exception e) { e.printStackTrace(); } } //覆盖了父类的remove方法 public void remove(int number) throws Exception { //遍历顺序表 for (int i = 0; i < length(); i++) { //取出第i项 //强转数据类型 StudentNode node = (StudentNode) super.get(i); if (node.number == number) { //找到了:进行删除 super.remove(i); System.out.println("删除成功"); return; } } //抛出异常 throw new Exception("学号" + number + "不存在"); } //重载父类的display()方法，输出顺序表中所有数据元素 public void display() { //遍历顺序表 for (int i = 0; i < length(); i++) { //强转数据类型 try { StudentNode node = (StudentNode) super.get(i); displayNode(node); } catch (Exception e) { e.printStackTrace(); } } } //输出一个数据元素信息 public void displayNode(StudentNode node) { System.out.println( "编号 =" + node.number + ", 姓名 = " + node.name + ", 性别 = " + node.sex + ", 大学英语 = " + node.english + ", 高等数学 = " + node.math + '}'); } //求各门科的平均分 public double avg(String name) throws Exception { //记录分数 double sum = 0 ; //记录个数 int num = 0 ; //判断是计算英语还是数学的全班平均分 if (name.equals("大学英语")){ //记录英语的平均分 for (int i = 0; i < length(); i++) { //调用get方法取出指定学号的学生信息 StudentNode node = (StudentNode) super.get(i); sum += node.english ; num++ ; } }else if (name.equals("高等数学")){ for (int i = 0; i < length(); i++) { //调用get方法取出指定学号的学生信息 StudentNode node = (StudentNode) super.get(i); //加全班的数学成绩 sum += node.math ; num++ ; } } return sum/num ; }} 测试结果
----------------------------------------------------------------------------
章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！
如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟
