【数据结构】24种常见算法题
- 补全下面顺序表的插入操作算法代码：
| public void insert(int i, Object x) { //0.1 满校验：存放实际长度 和 数组长度 一样 if(curLen == listEle.length) { throw new Exception("已满"); } //0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素 if(i < 0 || 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 ++; } |
- 补全顺序表的删除算法代码
| public void remove(int i ) throws Exception { // 0.1 校验非法数据 if(i < 0 || i > curLen – 1 ) { throw new Exception("位置非法"); } // 1 将i之后向前移动 for(int j = i ; j < curLen - 1 ; j ++ ) { listEle[j] = listEle[j+1]; } // 2 长度减一 curLen--; } |
- 补全顺序表的查找算法1代码
循环遍历已有数据，进行判断，如果有返回第一个索引号，如果没有返回-1
| public int indexOf(Object x) { for(int i = 0; i < curLen ; i ++) { if( listEle[i].equals(x) ) { return i; } } return -1; } |
- 补全顺序表的查找算法2代码：
使用变量记录没有匹配到索引
| 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 } } |
- 补全单链表长度算法：
| public class Node{ public Object data; //数据域 public Node next; //指针域 } public int length() { Node p = head.next; // 获得第一个结点 int length = 0; // 定义一个变量记录长度 while(p != null) { length ++; //计数 p = p.next; //p指向下一个结点 } return length; } |
- 补全单链表按索引号(位序号)查找算法代码：
| public class Node{ public Object data; //数据域 public Node next; //指针域 } public Object get(int i) { Node p = head.next; //获得头结点 int j = 0; //已经处理的结点数 while(p != null && j <i ) { //链表没有下一个 && 处理有效部分 p = p.next; j++; } if(i < 0 || p == null) { throw new Exception("元素不存在"); } return p.data; //返回数据 } |
- 补全按值查找索引算法代码：
| public class Node{ public Object data; //数据域 public Node next; //指针域 } //查询给定值的索引号，如果没有返回-1 public int indexOf(Object x) { Node p = head.next; // 获得头结点 int j = 0; // 不匹配元素的个数 while(p != null && !p.data.equals(x) ) { // 循环依次找【不匹配】元素 p = p.next; j++; } // 返回匹配索引，如果没有返回-1 if(p != null ) { return j; } else { return -1; } } |
- 补全入栈算法代码
| public class SqStack { private Object[] stackElem; //栈对象数组 private int top; //长度、下一个存储位置 等 } public void push(Object x) { if(top == stackElem.length ) { //栈满 throw new RuntimeException("栈满"); } else { stackElem[top] = x; top++; } } |
- 1~n求和算法代码补全(n=10)
| public class TestSum { public static void main(String[] args) { System.out.println(sum(10)); } private static int sum(int n) { if(n == 1) { return 1; } return n + sum(n-1); } } |
- n!算法代码补全(n=10)
| public class TestFactorial { public static void main(String[] args) { System.out.println(factorial(4)); } private static int factorial(int n) { if(n == 1 ) { return 1; } return n * factorial(n-1); } } |
- 斐波那契数列算法代码补全(n=10)
| public class TestFibonacci { public static void main(String[] args) { for(int i = 0 ; i <= 10 ; i ++) { System.out.print(fibonacci(i) + "、"); } } private static int fibonacci(int n) { if(n == 0) return 0; if(n == 1) return 1; return fibonacci(n-1) + fibonacci(n-2); }} |
- 串的扩容算法代码补全
| public void allocate(int newCapacity) { char[] temp = strvalue; // 存放原来的数据 ab数组 strvalue = new char[newCapacity]; // 给strValue重新赋一个更大数组的值 for(int i = 0; i < temp.length; i++) { // 拷贝数据 strvalue[i] = temp[i]; } } |
- 串的求子串算法代码补全
| public IString substring(int begin , int end) { // 1 两个参数校验 if(begin < 0 || end > curlen || begin > end) { throw new StringIndexOutOfBoundsException("条件不合法"); } // 2 优化：当前串直接返回 if(begin == 0 && end == curlen) return this;
// 3 核心算法 char[] buffer = new char[end - begin]; // 构建新数组 for(int i = 0 ; i < buffer.length ; i ++) { // 依次循环遍历新数组，一个一个赋值 buffer[i] = strvalue[i + begin]; } return new SeqString(buffer); // 使用字符数组构建一个新字符串 } |
- 串删除算法代码补全
| public IString delete(int begin , int end) { // 1 参数校验 if(begin < 0 || end > curlen || begin > end) { throw new StringIndexOutOfBoundsException("条件不合法"); }
// 2 核心：将后面内容移动到签名 // 2.1 移动 for(int i = 0 ; i < curlen - end ; i ++) { strvalue[i + begin] = strvalue[i + end]; } // 2.2 重新统计长度 (end-begin 需要删除串的长度) curlen = curlen - (end-begin) return this; } |
- n!算法代码补全(n=10)：
| public class TestFactorial { public static void main(String[] args) { System.out.println(factorial(4)); } private static int factorial(int n) { if(n == 1 ) { 【代码1】 return 1; } return n * factorial(n-1); 【代码2】 } } |
- 不带监视哨的插入排序算法
| public void insertSort() { RecordNode temp; int i, j; for (i = 1; i < this.curlen; i++) { temp = r[i]; for (j = i - 1; j >= 0 && temp.key.compareTo(r[j].key) < 0; j--) { r[j + 1] = r[j]; } r[j + 1] = temp; display(); } } |
- 带监视哨的插入排序算法
| public void insertSortWithGuard() { int i, j; for (i = 1; i <this.curlen; i++) { r[0] = r[i]; for (j = i - 1; r[0].key.compareTo(r[j].key) < 0; j--) { r[j + 1] = r[j]; } r[j + 1] = r[0]; System.out.print("第" + i + "趟: "); display(9); } } |
- 优化版冒泡排序算法
| public void bubbleSort() { RecordNode temp; boolean flag = true; for (int i = 1; i < this.curlen && flag; i++) { flag = false; for (int j = 0; j < this.curlen - i; j++) { if (r[j].key.compareTo(r[j + 1].key) > 0) { temp = r[j]; r[j] = r[j + 1]; r[j + 1] = temp; flag = true; } } System.out.print("第" + i + "趟: "); display(); } } |
- 直接选择排序算法
| public void selectSort() { RecordNode temp; for (int i = 0; i < this.curlen - 1; i++) { int min = i; for (int j = i + 1; j < this.curlen; j++) { if (r[j].key.compareTo(r[min].key) < 0) { min = j; } } if (min != i) { temp = r[i]; r[i] = r[min]; r[min] = temp; } } } |
- 二路归并算法
| public void mergepass(RecordNode[] r, RecordNode[] order, int s, int n) {……}//一趟归并算法 public void mergeSort() { int s = 1; int n = this.curlen; RecordNode[] temp = new RecordNode[n]; while (s < n) { mergepass(r, temp, s, n); s *= 2; mergepass(temp, r, s, n); s *= 2; } } |
- 补全带监视哨的顺序查找算法代码
| public int seqSearchWithGuard(Comparable key) { int i = length() - 1; r[0].key = key; while(r[i].key.compareTo(key) != 0) { i--; } return i>0 ? i : -1; } |
- 补全顺序查找代码
| public int seqSearch(Comparable key) { int i = 0 , n = length(); while(i < n && r[i].key.compareTo(key) != 0) { i++; } return i < n ? i : -1 } |
- 补全二分查找算法代码
| public int binarySearch(Comparable key) { if(length() > 0) { int low = 0, high = length() - 1; while (low <= high) { int mid = (low + high) / 2; if(r[mid].key.compareTo(key) == 0) { return mid; } else if (r[mid].key.compareTo(key) > 0) { // 中间值比给定值大 high = mid - 1; } else { low = mid + 1; } } } return -1; } |
- 补全二叉排序树的递归算法代码
| private Object searchBST(BiTreeNode p, Comparable key) { if (p != null) { if (key.compareTo(((RecordNode) p.data).key) == 0) { return p.data; } if (key.compareTo(((RecordNode) p.data).key) < 0) { return searchBST(p.lchild, key); } else { return searchBST(p.rchild, key); } } return null; } |
文章来源: blog.csdn.net，作者：陶然同学，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/weixin_45481821/article/details/126163017
- 点赞
- 收藏
- 关注作者
评论（0）