补全下面顺序表的插入操作算法代码：
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;
}
