Java数据结构与经典算法——高手必会
1.大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的
算法大O表示法表示的运行时间
线性查找 O(N)
二分查找 O(logN)
无序数组的插入 O(1)
有序数组的插入 O(N)
无序数组的删除 O(N)
有序数组的删除 O(N)
O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)
2.排序
public class JWzw {
//插入排序
public void insertArray(Integer []in){
int tem = 0;
int num = 0;
int upnum = 0;
for (int i = 0; i < in.length; i++) {
for (int j = i - 1; j >= 0; j--) {
num++;
if (in[j+1] < in[j]) {
tem = in[j+1];
in[j+1] = in[j];
in[j] = tem;
upnum++;
}
else
{
break;
}
}
}
for (int i = 0; i < in.length; i++) {
System.out.print(in[i]);
if(i < in.length - 1)
{
System.out.print(",");
}
}
System.out.println();
System.out.println("插入排序循环次数:" + num);
System.out.println("移动次数：" + upnum);
System.out.print("\n\n\n");
}
//选择排序
public void chooseArray(Integer []in){
int tem = 0;
int num = 0;
int upnum = 0;
for(int i = 0;i < in.length;i++)
{
for(int j = i;j < in.length - 1;j++){
num++;
if(in[j+1] < in[j]){
tem = in[j+1];
in[j + 1] = in[j];
in[j] = tem;
upnum++;
}
}
}
for (int i = 0; i < in.length; i++) {
System.out.print(in[i]);
if(i < in.length - 1)
{
System.out.print(",");
}
}
System.out.println();
System.out.println("选择排序循环次数:" + num);
System.out.println("移动次数：" + upnum);
System.out.print("\n\n\n");
}
//冒泡排序
public void efferArray(Integer []in){
int tem = 0;
int num = 0;
int upnum = 0;
for(int i = 0;i < in.length;i++){
for(int j = i;j < in.length - 1;j++)
{
num++;
if(in[j+1] < in[i]){
tem = in[j+1];
in[j+1] = in[i];
in[i] = tem;
upnum++;
}
}
}
for (int i = 0; i < in.length; i++) {
System.out.print(in[i]);
if(i < in.length - 1)
{
System.out.print(",");
}
}
System.out.println();
System.out.println("冒泡排序循环次数:" + num);
System.out.println("移动次数：" + upnum);
System.out.print("\n\n\n");
}
//打印乘法口诀
public void printMulti(){
for (int j = 1; j < 10; j++) {
for (int i = 1; i <= j; i++) {
System.out.print(i + " * " + j + " = " + j * i + "\t");
}
System.out.print("\t\n");
}
System.out.print("\n\n\n");
}
//打印N * 1 + N * 2 + N * 3 =num的所有组合
public void printNumAssemble(int num){
for (int i = 0; i < num + 1; i++) {
for (int j = 0; j < num / 2 +1; j++) {
for (int in = 0; in < num / 3 + 1; in++) {
if (i * 1 + j * 2 + in * 3 == num) {
System.out.println("小马" + i + ",\t中马" + j + ",\t大马" + in);
}
}
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
JWzw jwzw = new JWzw();
int num = 3;
jwzw.printMulti();//打印乘法口诀
jwzw.printNumAssemble(100);//打印N * 1 + N * 2 + N * 3 =num的所有组合
Integer in[] = {8,89,5,84,3,45,12,33,77,98,456,878,654,213,897};
jwzw.efferArray(in);//冒泡排序
Integer in1[] = {8,89,5,84,3,45,12,33,77,98,456,878,654,213,897};
jwzw.insertArray(in1);//插入排序
Integer in2[] = {8,89,5,84,3,45,12,33,77,98,456,878,654,213,897};
jwzw.chooseArray(in2);//选择排序
//int i = num++;
//System.out.println(i);
System.out.println(1000>>2);
}
}
3.优先级队列
class PriorityQueue {
private long[] a = null;
private int nItems = 0;
private int maxSize = 0;
public PriorityQueue(int maxSize) {
a = new long[maxSize];
this.maxSize = maxSize;
nItems = 0;
}
public void insert(long l) {
//优先级队列的插入不是队尾,而是选择一个合适的按照某种顺序插入的
//当队列长度为0时，如下
//不为0时,将所有比要插入的数小的数据后移,这样大的数就在队列的头部了int i = 0;
if(nItems == 0) {
a[0] = l;
} else {
for(i=nItems-1; i>=0; i--) {
if(l < a[i])
a[i+1] = a[i];
else
break;
}
a[i+1] = l;
}
nItems++;
}
public long remove() {
//移出的是数组最上端的数，这样减少数组元素的移动
return a[--nItems];
}
public boolean isEmpty() {
return (nItems == 0);
}
public boolean isFull() {
return (nItems == maxSize);
}
public int size() {
return nItems;
}
}
public class duilie {// 队列体类
private duilie s;
private String data;
duilie(String data) {
this.data = data;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public duilie getS() {
return s;
}
public void setS(duilie s) {
this.s = s;
}
}
public class duiliecz {// 队列操作类
/**
* @param args
*/
private int i = 0;// 队列长
private duilie top = new duilie("");// 队列头private duilie end = new duilie("");// 队列尾public void add(String s) {// 添加队列
duilie m = new duilie(s);
if (i != 0) {
m.setS(top.getS());
top.setS(m);
} else {
top.setS(m);
end.setS(m);
}
i++;
}
4.队列
public void del() {// 删除队尾
if (i == 0) {
return;
} else if (i == 1) {
top.setS(null);
end.setS(null);
} else {
duilie top1 = new duilie("");// 队列底查找用缓存 top1.setS(top.getS());
while (!top1.getS().getS().equals(end.getS())) { top1.setS(top1.getS().getS());
}
end.setS(top1.getS());
}
i--;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
duiliecz m = new duiliecz();
m.add("1");
m.add("2");
m.add("3");
m.add("4");
for (int n = 0; n < 4; n++) {
m.del();
}
}
public int getI() {
return i;
}
public duilie getEnd() {
return end;
}
public duilie getTop() {
return top;
}
}
5.栈
public class Stack {
int[] arr;
int len = 0;
public Stack() {
arr = new int[100];
}
public Stack(int n) {
arr = new int[n];
}
public int size() {
return len + 1;
}
// 扩大数组
public void resize() {
int[] b = new int[arr.length * 2];
System.arraycopy(arr, 0, b, 0, arr.length);
arr = b;
}
public void show() {
for (int i = 0; i < len; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 进栈
public void push(int a) {
if (len >= arr.length)
resize();
arr[len] = a;
len++;
}
// 出栈
public int pop() {
if (len == 0) {
System.out.println();
System.out.println("stack is empty!");
return -1;
}
int a = arr[len - 1];
arr[len - 1] = 0;
len--;
return a;
}
}
6.链表
class Node {
Object data;
Node next;
public Node(Object data) {
setData(data);
}
public void setData(Object data) {
this.data = data;
}
public Object getData() {
return data;
}
}
class Link {
Node head;
int size = 0;
public void add(Object data) {
Node n = new Node(data);
if (head == null) {
head = n;
} else {
Node current = head;
while (true) {
if (current.next == null) {
break;
}
current = current.next;
}
current.next = n;
}
size++;
}
public void show() {
Node current = head;
if (current != null) {
while (true) {
System.out.println(current);
if (current == null) {
break;
}
current = current.next;
}
} else {
System.out.println("link is empty");
}
}
public Object get(int index) {
// ....
}
public int size() {
return size;
}
}
7.单链表
class Node // 节点类，单链表上的节点
{
String data; // 数据域，存放String类的数据
Node next; // 指向下一个节点
Node(String data) {
this.data = data; // 构造函数
}
String get() {
return data; // 返回数据
}
}
class MyLinkList // 链表类
{
Node first; // 头节点
int size; // 链表长度
MyLinkList(String arg[]) {
// Node first = new Node("head");//生成头节点
first = new Node("head"); // J.F. 这里不需要定义局部变量 first
// 如果定义了局部变量，那成员变量 first 就一直没有用上
// 所以，它一直为空
size = 0;
Node p = first;
for (int i = 0; i < arg.length; i++) // 将arg数组中的元素分别放入链表中{
Node q = new Node(arg[i]);
q.next = p.next; // 每一个节点存放一个arg数组中的元素
p.next = q;
p = p.next;
size++;
}
}
MyLinkList() // 无参数构造函数
{
// Node first = new Node("head");
first = new Node("head"); // J.F. 这里犯了和上一个构造方法同样的错误size = 0;
}
int size() // 返回链表长度
{
return size;
}
void insert(Node a, int index) // 将节点a 插入链表中的第index个位置
{
Node temp = first;
for (int i = 0; i < index; i++) {
temp = temp.next;// 找到插入节点的前一节点
}
a.next = temp.next; // 插入节点
temp.next = a;
size++;
}
Node del(int index) // 删除第index个节点，并返回该值
{
Node temp = first;
for (int i = 0; i < index; i++) {
temp = temp.next;// 找到被删除节点的前一节点
}
Node node = temp.next;
temp.next = node.next;
size--; // 删除该节点，链表长度减一
return node;
}
void print() // 在屏幕上输出该链表（这段程序总是出错，不知道错在哪里）{
Node temp = first;
for (int i = 1; i < size; i++) // 将各个节点分别在屏幕上输出
{
temp = temp.next;
System.out.print(temp.get() + "->");
}
}
void reverse() // 倒置该链表
{
for (int i = 0; i < size; i++) {
insert(del(size - 1), 0); // 将最后一个节点插入到最前
// J.F. 最后一个节点的 index 应该是 size - 1
// 因为第一个节点的 index 是 0
}
}
String get(int index) // 查找第index个节点，返回其值
{
if (index >= size) {
return null;
}
Node temp = first;
for (int i = 0; i < index; i++) {
temp = temp.next;// 找到被查找节点的前一节点
}
return temp.next.get();
}
}
class MyStack // 堆栈类，用单链表实现
{
MyLinkList tmp;
Node temp;
MyStack() {
// MyLinkList tmp = new MyLinkList();
tmp = new MyLinkList(); // J.F. 和 MyLinkList 构造方法同样的错误}
void push(String a) // 压栈，即往链表首部插入一个节点
{
Node temp = new Node(a);
tmp.insert(temp, 0);
}
String pop() // 出栈，将链表第一个节点删除
{
Node a = tmp.del(0);
return a.get();
}
int size() {
return tmp.size();
}
boolean empty() // 判断堆栈是否为空
{
if (tmp.size() == 0)
return false;
else
return true;
}
}
public class MyLinkListTest // 测试程序部分
{
public static void main(String arg[]) // 程序入口
{
if ((arg.length == 0) || (arg.length > 10))
System.out.println("长度超过限制或者缺少参数");
else {
MyLinkList ll = new MyLinkList(arg); // 创建一个链表
ll.print(); // 先输出该链表（运行到这一步抛出异常）
ll.reverse(); // 倒置该链表
ll.print(); // 再输出倒置后的链表
String data[] = new String[10];
int i;
for (i = 0; i < ll.size(); i++) {
data[i] = ll.get(i); // 将链表中的数据放入数组
}
// sort(data);// 按升序排列data中的数据（有没有现成的排序函数？）
for (i = 0; i < ll.size(); i++) {
System.out.print(data[i] + ";"); // 输出数组中元素
}
System.out.println();
MyStack s = new MyStack(); // 创建堆栈实例s
for (i = 0; i < ll.size(); i++) {
s.push(data[i]); // 将数组元素压栈
}
while (!s.empty()) {
System.out.print(s.pop() + ";"); // 再将堆栈里的元素弹出}
}
}
}
8.双端链表
class Link {
public int iData = 0;
public Link next = null;
public Link(int iData) {
this.iData = iData;
}
public void display() {
System.out.print(iData + " ");
}
}
class FirstLastList {
private Link first = null;
private Link last = null;
public FirstLastList() {
first = null;
last = null;
}
public void insertFirst(int key) {
Link newLink = new Link(key);
if (this.isEmpty())
last = newLink;
newLink.next = first;
first = newLink;
}
public void insertLast(int key) {
Link newLink = new Link(key);
if (this.isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}
public Link deleteFirst() {
Link temp = first;
if (first.next == null)
last = null;
first = first.next;
return temp;
}
public boolean isEmpty() {
return (first == null);
}
public void displayList() {
System.out.print("List (first-->last): ");
Link current = first;
while (current != null) {
current.display();
current = current.next;
}
System.out.println("");
}
}
class FirstLastListApp {
public static void main(String[] args) {
// TODO Auto-generated method stub
FirstLastList theList = new FirstLastList();
theList.insertFirst(22); // insert at front
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11); // insert at rear
theList.insertLast(33);
theList.insertLast(55);
theList.displayList(); // display the list
theList.deleteFirst(); // delete first two items
theList.deleteFirst();
theList.displayList(); // display again }
}
9.有序链表
package arithmetic;
class Link {
public int iData = 0;
public Link next = null;
public Link(int iData) {
this.iData = iData;
}
public void display() {
System.out.print(iData + " ");
}
}
class SortedList {
private Link first = null;
public SortedList() {
first = null;
}
public void insert(int key) {
Link newLink = new Link(key);
Link previous = null;
Link current = first;
// while的第一个条件是没有到达链表的尾端,第二个是按顺序找到一个合适的位置while (current != null && key > current.iData) {
previous = current;
current = current.next;
}
// 如果是空表或者要插入的元素最小,则在表头插入key
if (current == first)
first = newLink;
else
previous.next = newLink;
newLink.next = current;
}
/**
* 删除表头的节点
*
* @return要删除的节点
*/
public Link remove() {
Link temp = first;
first = first.next;
return temp;
}
public boolean isEmpty() {
return (first == null);
}
public void displayList() {
System.out.print("List (first-->last): ");
Link current = first; // start at beginning of list
while (current != null) // until end of list,
{
current.display(); // print data
current = current.next; // move to next link
}
System.out.println("");
}
}
class SortedListApp {
public static void main(String[] args) { // create new list
SortedList theSortedList = new SortedList();
theSortedList.insert(20); // insert 2 items
theSortedList.insert(40);
theSortedList.displayList(); // display list
theSortedList.insert(10); // insert 3 more items
theSortedList.insert(30);
theSortedList.insert(50);
theSortedList.displayList(); // display list
theSortedList.remove(); // remove an item
theSortedList.displayList(); // display list }
}
10.双向链表
class Link {
// 双向链表,有两个指针,一个向前,一个向后
public int iData = 0;
public Link previous = null;
public Link next = null;
public Link(int iData) {
this.iData = iData;
}
public void display() {
System.out.print(iData + " ");
}
}
class DoublyLinked {
// 分别指向链表的表头和表尾
private Link first = null;
private Link last = null;
public boolean isEmpty() {
return first == null;
}
/**
* 在表头插入数据
*
* @param要插入的节点的数据
*/
public void insertFirst(int key) {
Link newLink = new Link(key);
// 如果开始链表为空,则插入第一个数据后,last也指向第一个数据if (this.isEmpty())
last = newLink;
else {// 表不为空的情况
first.previous = newLink;
newLink.next = first;
}
// 无论怎样,插入后都的让first重新指向第一个节点
first = newLink;
}
public void insertLast(int key) {// 在尾端插入数据,同上Link newLink = new Link(key);
if (this.isEmpty())
first = newLink;
else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
/**
* 在指定的节点后插入数据
*
* @param key
* 指定的节点的值
* @param iData
* 要插入的数据
* @return是否插入成功
*/
public boolean insertAfter(int key, int iData) {
Link newLink = new Link(key);
Link current = first;
// 从first开始遍历,看能否找到以key为关键字的节点
while (current.iData != key) {
current = current.next;
// 若能找到就跳出循环,否则返回false,插入失败
if (current == null)
return false;
}
// 如果插入点在last的位置
if (current == last) {
last = newLink;
} else {// 非last位置,交换各个next和previous的指针
newLink.next = current.next;
current.next.previous = newLink;
}
current.next = newLink;
newLink.previous = current;
return true;
}
/**
* 删除表头的节点
*
* @return
*/
public Link deleteFirst() {
Link temp = first;
// 如果表中只有一个元素,删除后则为空表,所以last=null
if (first.next == null)
last = null;
else
// 否则,让第二个元素的previous=null
first.next.previous = null;
// 删除头指针,则first指向原来的second
first = first.next;
return temp;
}
public Link deleteLast() {// 同上
Link temp = last;
if (last.previous == null)
first = null;
else
last.previous.next = null;
last = last.previous;
return temp;
}
public Link deleteKey(int key) {
Link current = first;
// 遍历整个链表查找对应的key,如果查到跳出循环,否则...
while (current.iData != key) {
current = current.next;
// ...否则遍历到表尾,说明不存在此key,返回null,删除失败
JAVA经典算法案例
JA V A经典算法40例 【程序1】题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... public class exp2{ public static void main(String args[]){ int i=0; for(i=1;i<=20;i++) System.out.println(f(i)); } public static int f(int x) { if(x==1 || x==2) return 1; else return f(x-1)+f(x-2); } } 或 public class exp2{ public static void main(String args[]){ int i=0; math mymath = new math(); for(i=1;i<=20;i++) System.out.println(mymath.f(i)); } } class math { public int f(int x) { if(x==1 || x==2) return 1; else return f(x-1)+f(x-2); } } 【程序2】题目：判断101-200之间有多少个素数，并输出所有素数。 1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除， 则表明此数不是素数，反之是素数。 public class exp2{ public static void main(String args[]){ int i=0; math mymath = new math(); for(i=2;i<=200;i++) if(mymath.iszhishu(i)==true) System.out.println(i); } } class math { public boolean iszhishu(int x) { for(int i=2;i<=x/2;i++) if (x % i==0 ) return false; return true; } } 【程序3】题目：打印出所有的"水仙花数"，所谓"水仙花数 "是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个"水
数据结构与算法基础知识总结
数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满
力 扣 数 据 结 构 与 算 法
前端如何搞定数据结构与算法(先导篇) 「观感度：?」 「口味：锅包肉」 「烹饪时间：20min」 本文已收录在Github? 为什么要学习数据结构与算法？ 在0202年的今天，由于每天被无数的信息轰炸，大多数人已经变得越来越浮躁了，并且丧失了独立思考的能力。 你可能会经常听到这样的感慨： 技术人究竟能走多远？我遇到了天花板 35岁的程序员要如何面对中年危机？ 技术更新太快，好累，学不动了 然后，你也变得焦虑起来。那你有没有静下心来想过，如何才能抵御年龄增长并且使自己增值呢？ 无非是终身学习，持续修炼自己的内功。内功也就是基础知识和核心概念，这些轰轰烈烈发展的技术本质，其实都是基础知识，也就是我们在大学里学过的基础课-程。 操作系统 计算机组成原理 计算机网络 编译原理
设计模式 数据结构与算法 这也就是为什么越靠谱的面试官越注重你基础知识的掌握程度，为什么越牛的的企业越重视你的算法能力。因为当你拥有了这些，你已经比大多数人优秀了。你的天花板由你自己来决定，大家口中的中年危机可能并不会成为你的危机。新技术来临时，你对它的本质会看得更加透彻，学起来会一通百通。这样的人才，公司培养你也会花费更少的成本。 (不过，一辈子做个开开心心的 CRUD Boy 也是一种选择。) 数据结构与算法之间的关系 Rob Pikes 5 Rules of Programming中的第五条是这样说的： Data dominates. If youve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming. 数据占主导。如果您选择了正确的数据结构并组织得当，那么这些算法几乎总是不言而喻的。数据结构而非算法是编程的核心。 瑞士计算机科学家，Algol W，Modula，Oberon 和 Pascal 语言的设计师 Niklaus Emil Wirth 写过一本非常经典的书《Algorithms + Data Structures = Programs》，即算法 + 数据结构 = 程序。 我们可以得出结论，数据结构与算法之间是相辅相成的关系。数据结构服务于算法，算法作用于特定的数据结构之上。 数据结构与算法好难，怎么学？
Java经典算法大全
Java经典问题算法大全 /*【程序1】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... */ package https://www.wendangku.net/doc/4b7634908.html,.flywater.FiftyAlgorthm; public class FirstRabbit { public static final int MONTH = 15; public static vo id main(String[] args) { long f1 = 1L, f2 = 1L; long f; for(int i=3; i 算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点？（A） A．存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600 (10)，A[3][3]存放位置在678 (10) ， 每个元素占一个空间，问A[2][3] (10)存放在什么位置？(脚注 (10) 表示用10进制表示,m>3)C A．658 B．648 C．633 D．653 下列关于二叉树遍历的叙述中，正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找，其前提条件是( C). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储，并且按关键码值排好序 D. 线性表以链接方式存储，并且按关键码值的检索频率排好序 对n个记录进行堆排序，所需要的辅助存储空间为（C） A. O（1og2n） B. O（n） C. O（1） D.O（n2） 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（D）个， A．1 B．2 C．3 D．4 下列关于数据结构的叙述中，正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时，一般不考虑（ A ）。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。A．单链表B．静态链表C．线性链表D．顺序存储结构 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。 A．q=p->next；p->data=q->data；p->next=q->next；free(q)； B．q=p->next；q->data=p->data；p->next=q->next；free(q)； C．q=p->next；p->next=q->next；free(q)； 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 JA V A经典算法40题 【程序1】题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... public class exp2{ public static void main(String args[]){ int i=0; for(i=1;i<=20;i++) System.out.println(f(i)); } public static int f(int x) { if(x==1 || x==2) return 1; else return f(x-1)+f(x-2); } } 或 public class exp2{ public static void main(String args[]){ int i=0; math mymath = new math(); for(i=1;i<=20;i++) System.out.println(mymath.f(i)); } } class math { public int f(int x) { if(x==1 || x==2) return 1; else return f(x-1)+f(x-2); } } 【程序2】题目：判断101-200之间有多少个素数，并输出所有素数。 1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除， 则表明此数不是素数，反之是素数。 public class exp2{ public static void main(String args[]){ int i=0; math mymath = new math(); for(i=2;i<=200;i++) if(mymath.iszhishu(i)==true) System.out.println(i); } } class math { public int f(int x) { if(x==1 || x==2) return 1; else return f(x-1)+f(x-2); } public boolean iszhishu(int x) { for(int i=2;i<=x/2;i++) if (x % 2==0 ) return false; return true; 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i 数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列, 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 协同过滤推荐算法(java原生JDK实现-附源 码地址) 一、项目需求 1.需求链接 https://https://www.wendangku.net/doc/4b7634908.html,/getStart/information.htm?raceId=231522 2.需求内容 训练数据包含了抽样出来的一定量用户在一个月时间（11.18~12.18）之内的移动端行为数据（D），评分数据是这些用户在这个一个月之后的一天（12.19） 对商品子集（P）的购买数据。参赛者要使用训练数据建立推荐模型，并输出用户在接下来一天对商品子集购买行为的预测结果。 评分数据格式 具体计算公式如下：参赛者完成用户对商品子集的购买预测之后，需要将结果放入指定格式的数据表（非分区表）中，要求结果表名为：tianchi_mobile_recommendation_predict.csv，且以utf-8格式编码；包含user_id 和item_id两列（均为string类型）,要求去除重复。例如： 评估指标 比赛采用经典的精确度(precision)、召回率(recall)和F1值作为评估指标。具体计算公式如下： 其中PredictionSet为算法预测的购买数据集合，ReferenceSet为真实的答案购买数据集合。我们以F1值作为最终的唯一评测标准。 二、协同过滤推荐算法原理及实现流程 1.基于用户的协同过滤推荐算法 基于用户的协同过滤推荐算法通过寻找与目标用户具有相似评分的邻居用户，通过查找邻居用户喜欢的项目，推测目标用户也具有相同的喜好。基于用户的协同过滤推荐算法基本思想是：根据用户-项目评分矩阵查找当前用户的最近邻居，利用最近邻居的评分来预测当前用户对项目的预测值，将评分最高的N 个项目推荐给用户，其中的项目可理解为系统处理的商品。其算法流程图如下图1所示。 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 1.最短路的笛杰斯特拉算法 /** * * @author Administrator */ //这个算法用来解决无向图中任意两点的最短路径，同时输出路径(起点到所有点的) public class MinPath { public static String dijkstra(int[][] W1, int start, int end) { System.out.println("起点:" + start + "终点:" + end); boolean[] isLabel = new boolean[W1[0].length];// 是否标号 int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合，以标号的先后顺序进行存储，实际上是一个以数组表示的栈 int i_count = -1;// 栈的顶点 int[] distance = W1[start].clone();// v0到各点的最短距离的初始值 int index = start;// 从初始点开始 int presentShortest = 0;// 当前临时最短距离 indexs[++i_count] = index;// 把已经标号的下标存入下标集中 isLabel[index] = true; while (i_count < W1[0].length) { // 第一步：得到与原点最近的某个点 int min = Integer.MAX_V ALUE; for (int i = 0; i < distance.length; i++) { if (!isLabel[i] && distance[i] != -1 && i != index) { // 如果到这个点有边,并且没有被标号 if (distance[i] < min) { min = distance[i]; index = i;// 把下标改为当前下标 } } } i_count = i_count + 1; if (i_count == W1[0].length) { break; } isLabel[index] = true;// 对点进行标号 indexs[i_count] = index;// 把已经标号的下标存入下标集中 if (W1[indexs[i_count - 1]][index] == -1 || presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) { // 如果两个点没有直接相连，或者两个点的路径大于最短路径 presentShortest = distance[index]; } else { presentShortest += W1[indexs[i_count - 1]][index]; //插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; i //堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j 数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 答案： 1．错误 2．正确 3．正确 4．错误 5．正确 6．正确 7．错误 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 答案： Ａ：ｃＢ；ｄＣ：ａＤ：ｂＥ：ｆ 三．从供选择的答案中选取正确的答案填在下面叙述中的横线上： 1． A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构 河内塔问题（Towers of Hanoi） 问题说明： 河內之塔(Towers of Hanoi)是法国人M.Claus(Lucas)於1883年从泰国带至法国的，河內为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及這个故事，据说创世紀时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），並命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将损毁，而也就是世界末日來临之时。 算法代码（Java）： 复制内容到剪贴板 import java.io.*; public class Hanoi { public static void main(String args[]) throws IOException { int n; BufferedReader buf; buf = new BufferedReader(new InputStreamReader(System.in)); System.out.print("请输入盘子个数"); n = Integer.parseInt(buf.readLine()); Hanoi hanoi = new Hanoi(); hanoi.move(n, 'A', 'B', 'C'); } public void move(int n, char a, char b, char c) { if(n == 1) System.out.println("盘 " + n + " 由 " + a + " 移至 " + c); else { move(n - 1, a, c, b); System.out.println("盘 " + n + " 由 " + a + " 移至 " + c); move(n - 1, b, a, c); 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data算法与数据结构复习资料
数据结构经典例题
JAVA算法100例_全源码
数据结构与算法复习题及参考答案
数据结构(C语言)【经典题库】含标准答案
数据结构与算法知识点必备
数据结构经典例题
协同过滤推荐算法(java原生JDK实现-附源码地址)
数据结构与算法设计知识点
java实现图论中的经典算法
数据结构经典算法 C语言版
数据结构与算法基础
JAVA经典算法
数据结构经典算法试题