【数据结构】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;

}