java數據結構和演算法源碼
『壹』 求程序代碼（java版的數據結構）
3個燃罩class，運行UI.java。
******
public class CircuitException extends Exception {public CircuitException(){}}
*****
import java.util.LinkedList;
public class GPS {
public static final int MAX = 65535;
public GPS(int maxSize){
graph = new Graph(maxSize);
}
public GPS(){
graph = new Graph();
}
public Graph graph;
public static void main(String args[]){
GPS gps = new GPS();
try {
gps.graph.addEdge("a", "b", 1);
gps.graph.addEdge("a", "c", 1);
gps.graph.addEdge("b","d" , 1);
gps.graph.addEdge("c","d"皮跡鬧 , 1);
gps.graph.addEdge("d","e" , 1);
gps.graph.addEdge("d","f" , 1);
gps.graph.addEdge("e","t" , 2);
gps.graph.addEdge("f","t" , 1);
LinkedList list = gps.graph.getPath("a", "d");
for(int i = 0 ; i < list.size() ; i++){
System.out.print(list.get(i));
}System.out.println();
} catch (CircuitException e) {
System.out.println("出現了自環！"州首);
}
gps.graph.showGraph();
System.out.println(gps.graph.gap);
}
public class Graph{
public int Zuida = 50;
public int chang = 0;
public Jiao[] vertex;
public double gap;
public Graph(){
vertex = new Jiao[Zuida];
}
public Graph(int maxSize){
this.Zuida = maxSize;
vertex = new Jiao[maxSize];
}
public void addVertex(String name){
vertex[chang++] = new Jiao(name);
}
public void addEdge(String v1, String v2,double edge) throws CircuitException{
//先找到v1；
if(v1.equals(v2))
throw new CircuitException();
Jiao from = null;
Jiao to = null;
for(int i = 0 ; i < chang ; i++){
if(vertex[i].name.equals(v1)){
from = vertex[i];
}else if(vertex[i].name.equals(v2)){
to = vertex[i];
}
}
if(from == null){
this.addVertex(v1);
from = this.vertex[chang-1];
}
if(to == null){
this.addVertex(v2);
to = this.vertex[chang-1];
}//已經找到v1和v2；
//沒有檢測是否v1 v2邊已經存在！
//加入邊。
Jiao v1adj = new Jiao(v2);
v1adj.edge = edge;
Jiao v2adj = new Jiao(v1);
v2adj.edge = edge;
//添加聯系
//檢查聯系是否已經存在
Jiao temp = from;
while(temp.next!=null){
Jiao temppar = temp;
temp = temp.next;
if(temp.name.equals(v1adj.name)){
temppar.next = temp.next;
}
}
v1adj.next = from.next;
from.next = v1adj;
//v2adj.next = to.next;
//to.next = v2adj;
}
//假設要找的必然存在，不用想是否不在
public LinkedList getPath(String v1 ,String v2){
int count = 0;
//System.out.println(count++);
boolean found[] = new boolean[chang];
double distance[] = new double[chang];
int to = 0;
Jiao from = null;
for(int i = 0 ; i < chang ; i++){
found[i] = false;
distance[i] = MAX;
}
for(int i = 0 ; i < chang ; i++){
if(vertex[i].name.equals(v1)){//找到始發地
from = vertex[i];
distance[i] = 0;
found[i] = true;
//System.out.println(count++);
}
if(vertex[i].name.equals(v2)){//找到目的地
to = i;
//System.out.println(count++);
}
}
//必須先准備好路徑！
Jiao forCount = from;
int degree = 0;
while(forCount!=null){
degree++;
forCount=forCount.next;
}
LinkedList[] list = new LinkedList[degree];
int [] mark = new int[degree];
for(int i = 0 ; i < degree ; i++){
list[i]=new LinkedList();
mark[i]=MAX;
}
int test=0;
int count2 = 0;
int count3 = 0;
//System.out.println(count+++"xx");
while(!found[to]&&test++<100){
//System.out.println(count+++"FIRST");
//開始時from到所有都是最大值。
//找到標記了的節點
//找標記了的節點鄰接的未標記的節點。
//得到最短的邊，並標記。
//更新現有路徑
double min = MAX;
int address = -1;
int father = -1;
for(int i = 0 ; i < chang ; i++){//對於已經找到的頂點尋找最小的往後的距離。
if(found[i]){//找到了的。
Jiao temp = vertex[i];
while(temp!=null){//vertex的鄰接頂點~~
//先看temp的號碼~
int tempNumber = -1;
for(int j = 0 ; j < chang ; j++){
if(vertex[j].name.equals(temp.name)){
tempNumber = j;
break;
}
}
if(!found[tempNumber]){//如果是還沒有找到的~
double dist = distance[i]+temp.edge;
if(dist < min){
min = dist;
father = i;
//System.out.println(" "+min);
address = tempNumber;
}
}
temp = temp.next;
}
}
}found[address] = true;
distance[address] = min;
//添加到已有路徑中去！
//知道father
for(int i = 0 ; i < degree ; i++){
if(list[i].isEmpty()||list[i].getLast().equals(vertex[father].name)){
list[i].addLast(vertex[address].name);
break;
}
}
}
for(int i = 0 ; i < degree ; i++){
if(list[i].isEmpty())
continue;
else{
if(list[i].getLast().equals(v2)){
gap=0;
//先求出gap
Jiao pre = from;
Jiao nex = null;
for(int j = 0 ; j < list[i].size() ; j++){
for(int k = 0 ; k < chang ; k++){
if(vertex[k].name.equals(list[i].get(j))){
nex = vertex[k];break;
}
}
while(pre.next!=null){//找到下一個的長度
pre = pre.next;
//System.out.println(nex.name +"nex.name");
if(pre.name.equals(nex.name)){
gap+=pre.edge;
//System.out.println(" gap2 "+gap);
}
}
pre = nex;
}
//System.out.println(gap+"gap");
return list[i];
}
}
}
return null;
}
public void showGraph(){
Jiao temp;
for(int i = 0 ; i < chang ; i++){
temp = vertex[i];
while(temp!=null){
System.out.print(temp.name+temp.edge+" ");
temp = temp.next;
}System.out.println();
}System.out.println("Show Over!");
}
}
public class Jiao{
public String name;
public Jiao next = null;
public double edge;
public Jiao(String name){
this.name = name;
}
}
}
******
import java.awt.EventQueue;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.LinkedList;
import javax.swing.JButton;
import javax.swing.DefaultListModel;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JList;
import javax.swing.JOptionPane;
import javax.swing.JScrollPane;
import javax.swing.JSeparator;
import javax.swing.JTextField;
import javax.swing.SwingConstants;
public class UI extends JFrame implements ActionListener{
private JTextField textField_5;
private JTextField textField_4;
private JList list_1;
private JList list;
private JTextField textField_1;
private JTextField textField_3;
private JTextField textField_2;
private JTextField textField;
private DefaultListModel model = new DefaultListModel();
private DefaultListModel model_1 = new DefaultListModel();
/**
* Launch the application
* @param args
*/
public static void main(String args[]) {
EventQueue.invokeLater(new Runnable() {
public void run() {
try {
UI frame = new UI();
frame.setVisible(true);
} catch (Exception e) {
e.printStackTrace();
}
}
});
}
/**
* Create the frame
*/
public UI() {
super();
setTitle("GPS尋路");
getContentPane().setLayout(null);
setBounds(100, 100, 500, 375);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
final JScrollPane scrollPane = new JScrollPane();
scrollPane.setBounds(11, 36, 221, 193);
getContentPane().add(scrollPane);
list = new JList(model);
scrollPane.setViewportView(list);
final JScrollPane scrollPane_1 = new JScrollPane();
scrollPane_1.setBounds(253, 36, 218, 193);
getContentPane().add(scrollPane_1);
list_1 = new JList(model_1);
scrollPane_1.setViewportView(list_1);
final JLabel label = new JLabel();
label.setText("從");
label.setBounds(10, 249, 24, 18);
getContentPane().add(label);
final JLabel label_1 = new JLabel();
label_1.setText("到");
label_1.setBounds(11, 273, 24, 18);
getContentPane().add(label_1);
textField = new JTextField();
textField.setBounds(50, 247, 103, 22);
getContentPane().add(textField);
textField_2 = new JTextField();
textField_2.setBounds(50, 271, 103, 22);
getContentPane().add(textField_2);
final JLabel label_2 = new JLabel();
label_2.setText("距離");
label_2.setBounds(11, 297, 37, 18);
getContentPane().add(label_2);
textField_3 = new JTextField();
textField_3.setBounds(50, 295, 103, 22);
getContentPane().add(textField_3);
final JButton button = new JButton();
button.setText("添加");
button.setBounds(155, 250, 73, 28);
getContentPane().add(button);
final JButton button_1 = new JButton();
button_1.setText("刪除");
button_1.setBounds(155, 285, 73, 28);
getContentPane().add(button_1);
final JLabel label_3 = new JLabel();
label_3.setText("距離：");
label_3.setBounds(253, 297, 39, 18);
getContentPane().add(label_3);
textField_1 = new JTextField();
textField_1.setBounds(293, 295, 86, 22);
getContentPane().add(textField_1);
final JButton button_2 = new JButton();
button_2.setText("顯示路徑");
button_2.setBounds(385, 249, 86, 68);
getContentPane().add(button_2);
final JLabel label_4 = new JLabel();
label_4.setText("路徑表示");
label_4.setBounds(11, 10, 66, 18);
getContentPane().add(label_4);
final JLabel label_5 = new JLabel();
label_5.setText("最佳路徑");
label_5.setBounds(253, 12, 66, 18);
getContentPane().add(label_5);
//
button.addActionListener(this);
button_1.addActionListener(this);
button_2.addActionListener(this);
final JLabel label_6 = new JLabel();
label_6.setText("從");
label_6.setBounds(253, 249, 24, 18);
getContentPane().add(label_6);
textField_4 = new JTextField();
textField_4.setBounds(293, 247, 86, 22);
getContentPane().add(textField_4);
final JLabel label_7 = new JLabel();
label_7.setText("到");
label_7.setBounds(253, 273, 24, 18);
getContentPane().add(label_7);
textField_5 = new JTextField();
textField_5.setBounds(293, 271, 86, 22);
getContentPane().add(textField_5);
final JSeparator separator = new JSeparator();
separator.setOrientation(SwingConstants.VERTICAL);
separator.setBounds(239, 10, 8, 317);
getContentPane().add(separator);
}
@Override
public void actionPerformed(ActionEvent e) {
// TODO Auto-generated method stub
if(e.getActionCommand().equals("添加")){
try{String from = textField.getText();
String to = textField_2.getText();
if(from.equals(to)){
JOptionPane.showMessageDialog(null, "始點與終點不能相同");
return;
}
if(from.equals("")||to.equals("")){
JOptionPane.showMessageDialog(null, "添加不能為空");
return;
}for(int i = 0 ; i < model.size() ; i ++){
if(model.get(i).toString().substring(0, model.get(i).toString().indexOf(":")).equals(
from+"->"+to))
model.remove(i);
}
double length = Double.parseDouble(textField_3.getText());
model.addElement(from+"->"+to+": "+length);
}catch(Exception e1){
JOptionPane.showMessageDialog(null, "距離為數字值");
}
}
if(e.getActionCommand().equals("刪除")){
for(int i = 0 ; i < model.size() ; i++){
if(list.isSelectedIndex(i))
model.remove(i);
}
}
if(e.getActionCommand().equals("顯示路徑")){
try{
model_1.removeAllElements();
GPS gps = new GPS();
String full,from,to;
double length;
for(int i = 0 ; i < model.size() ; i++){
full = model.get(i).toString();
from = full.substring(0,full.indexOf("-"));
to = full.substring(full.indexOf("-")+2,full.lastIndexOf(":"));
length = Double.parseDouble(full.substring(full.indexOf(":")+1, full.length()-1));
//System.out.println(from);
//System.out.println(to);
try {
gps.graph.addEdge(from, to, length);
System.out.println(from +" "+ to);
} catch (CircuitException e1) {
System.out.println("有環存在");
}
}LinkedList list = gps.graph.getPath(textField_4.getText(), textField_5.getText());
model_1.addElement(textField_4.getText());
for(int i = 0 ; i < list.size() ; i++){
model_1.addElement(list.get(i));
}//計算路徑長度
textField_1.setText(""+gps.graph.gap);
}catch(Exception e1){
JOptionPane.showMessageDialog(null, "沒有找到有關節點");
}
}
}
}
『貳』 java（演算法與數據結構）tree
代碼實現[一]部分
package ChapterEight;
class Tree {
class Node {
public long value;
public Node leftChild;
public Node rightChild;
public Node(long value) {
this.value = value;
leftChild = null;
rightChild = null;
}
}
public Node root;
public Tree() {
root = null;
}
// 向樹中插入一個節點
public void insert(long value) {
Node newNode = new Node(value);
// 樹是空的
if (root == null)
root = newNode;
else {
Node current = root;
Node parentNode;
while (true) {
parentNode = current;
if (value < current.value) {
current = current.leftChild;
// 要插入的節點為左孩子節點
if (current == null) {
parentNode.leftChild = newNode;
return;
}
} else {
// 要插入的節點為右孩子節點
current = current.rightChild;
if (current == null) {
parentNode.rightChild = newNode;
return;
}
}
}
}
}
// 先續遍歷樹中的所有節點
public void preOrder(Node currentRoot) {
if (currentRoot != null) {
System.out.print(currentRoot.value + " ");
preOrder(currentRoot.leftChild);
preOrder(currentRoot.rightChild);
}
}
// 中續遍歷樹中的所有節點
public void inOrder(Node currentNode) {
if (currentNode != null) {
inOrder(currentNode.leftChild);
System.out.print(currentNode.value + " ");
inOrder(currentNode.rightChild);
}
}
// 後續遍歷樹中的所有節點
public void postOrder(Node currentNode) {
if (currentNode != null) {
postOrder(currentNode.leftChild);
postOrder(currentNode.rightChild);
System.out.print(currentNode.value + " ");
}
}
public void traverse(int traverseType) {
switch (traverseType) {
case 1:
preOrder(root);
break;
case 2:
inOrder(root);
break;
case 3:
postOrder(root);
break;
default:
break;
}
// 依據樹節點的值刪除樹中的一個節點
public boolean delete(int value) {
// 遍歷樹過程中的當前節點
Node current = root;
// 要刪除節點的父節點
Node parent = root;
// 記錄樹的節點為左孩子節點或右孩子節點
boolean isLeftChild = true;
while (current.value != value) {
parent = current;
// 要刪除的節點在當前節點的左子樹里
if (value < current.value) {
isLeftChild = true;
current = current.leftChild;
}
// 要刪除的節點在當前節點的右子樹里
else {
isLeftChild = false;
current = current.rightChild;
}
// 在樹中沒有找到要刪除的節點
if (current == null)
return false;
}
// 要刪除的節點為葉子節點
if (current.leftChild == null && current.rightChild == null) {
// 要刪除的節點為根節點
if (current == root)
root = null;
// 要刪除的節點為左孩子節點
else if (isLeftChild)
parent.leftChild = null;
// 要刪除的節點為右孩子節點
else
parent.rightChild = null;
}
// 要刪除的節點有左孩子節點，沒有右孩子節點
else if (current.rightChild == null) {
// 要刪除的節點為根節點
if (current == null)
root = current.leftChild;
// 要刪除的節點為左孩子節點
else if (isLeftChild)
parent.leftChild = current.leftChild;
// 要刪除的節點為右孩子節點
else
parent.rightChild = current.leftChild;
}
// 要刪除的節點沒有左孩子節點，有右孩子節點
else if (current.leftChild == null) {
// 要刪除的節點為根節點
if (current == root)
root = root.rightChild;
// 要刪除的節點為左孩子節點
else if (isLeftChild)
parent.leftChild = current.rightChild;
// 要刪除的節點為右孩子節點
else
parent.rightChild = current.rightChild;
}
// 要刪除的接節點既有左孩子節點又有右孩子節點
else {
Node successor = getSuccessor(current);
// 要刪除的節點為根節點
if (current == root)
root = successor;
// 要刪除的節點為左孩子節點
else if (isLeftChild)
parent.leftChild = successor;
// 要刪除的節點為右孩子節點
else
parent.rightChild = successor;
}
return true;
}
// 找到要刪除節點的替補節點
private Node getSuccessor(Node delNode) {
// 替補節點的父節點
Node successorParent = delNode;
// 刪除節點的替補節點
Node successor = delNode;
Node current = delNode.rightChild;
while (current != null) {
// successorParent指向當前節點的上一個節點
successorParent = successor;
// successor變為當前節點
successor = current;
current = current.leftChild;
}
// 替補節點的右孩子節點不為空
if (successor != delNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
}
public class TreeApp {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(8);
tree.insert(50);
tree.insert(45);
tree.insert(21);
tree.insert(32);
tree.insert(18);
tree.insert(37);
tree.insert(64);
tree.insert(88);
tree.insert(5);
tree.insert(4);
tree.insert(7);
System.out.print("PreOrder : ");
tree.traverse(1);
System.out.println();
System.out.print("InOrder : ");
tree.traverse(2);
System.out.println();
System.out.print("PostOrder : ");
tree.traverse(3);
System.out.println();
System.out.println(tree.delete(7));
System.out.print("PreOrder : ");
tree.traverse(1);
System.out.println();
System.out.print("InOrder : ");
tree.traverse(2);
System.out.println();
System.out.print("PostOrder : ");
tree.traverse(3);
System.out.println();
}
}
『叄』 Java數據結構與演算法有哪些
《Java數據結構和演算法》（第2版）介紹了計算機編程中使用的數據結構和演算法，對於在計算機應用中如何操作和管理數據以取得最優性能提供了深入淺出的講解。全書共分為15章，分別講述了基本概念、數組、簡單排序、堆和隊列、鏈表、遞歸、進階排序、二叉樹、紅黑樹、哈希表及圖形等知識。附錄中則提供了運行專題Applet和常式、相關書籍和問題解答。《Java數據結構和演算法》（第2版）提供了學完一門編程語言後進一步需要知道的知識。本書所涵蓋的內容通常作為大學或學院中計算機系二年級的課程，在學生掌握了編程的基礎後才開始本書的學習。
『肆』 JAVA數據結構與演算法
給你寫了答案如下，有問題再追問。
B
A
C
確切性
3
infexOf
隊頭指針指向隊尾
對
對
順序表：查找方便，但插入困難；
鏈表：查找困難，但插入方便。
//最大值
publicstaticintgetMax(intn,int[]arr){//n是數組最後一個元素的index
if(n==0)
returnarr[0];
if(arr[n]>getMax(n-1,arr))
returnarr[n];
returngetMax(n-1,arr);
}//平均值
publicstaticintgetAverage(intn,int[]arr){//n是數組最後一個元素的index
if(n==1)
returnarr[0];
return(arr[n]+getAverage(n-1,arr)*(n-1))/n;
}//刪除節點
publicstaticNodermNode(Nodehead,Nodenode){
Nodetemp=head;
while(temp.next!=null){
if(temp.next==node){
temp.next=node.next;
break;
}
else
temp=temp.next;
}
returnhead;
}//數組元素逆置
publicstaticint[]inverseArray(int[]arr){
intstart=0;
intend=arr.length-1;
for(;start<arr.length/2;start++,end--){
inttemp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
returnarr;
『伍』 java數據結構和演算法
首先看存儲方式, 這個list, 只保存一個link的引用, 作為鏈表的頭, 然後通過這個頭.next, 得到第二個, 第二個.next得到第三個, 一次類推, 知道.next == null 的時候, 說明list結束.
那麼現在分兩種情況看:
1. 當當前鏈表裡面沒有元素的時候, 那麼就添加一個, 然後讓它的next = first, 也就是為null, 那麼鏈表在遍歷的時候, 訪問了第一個, 然後第一個.next == null, 鏈表就到頭了.
2.當當前鏈表裡面有元素的時候, 那麼因為方法叫做firstinsert, 也就是添加頭元素, 所以先聲明一個link = newlink, 然後讓newlink, 的next 指向之前list.first素, 那麼現在newlink就變成了第一個, 而之前那個變成了第二個, 然後再把newlink的引用賦給first, 這樣, 鏈表的頭就變成了newlink, 達到了first insert的目的.
first的引用就是我上面分析的兩種情況, 一種是沒有元素就是null, 另一種情況是有, 變成了第二個, 因為這個list要有結束的位置, 否則就無限長了, 結束的條件就是遍歷list的時候, 最後一個元素.next == null, 這樣list就停住了我大體畫個圖吧, 你看看:
第一種情況: 當隊列中沒有元素的時候
列表中什麼都沒有 : [ (head)null ]
有一個newlink {nl}
執行完newlink.next=first; {nl} -> null
執行完first=newlink; [ (head){nl} -> null ];
這樣list的頭就是newlist, 只有它一個元素.
第二中情況: 當隊列中有元素的時候:
假設當前頭元素為{oldhead}
[ (head){oldhead} -> {obj1} -> {obj2} ... {objn} -> null]
有一個newlink {nl}
執行完newlink.next=first; {nl} -> {oldhead}
執行完first=newlink; [ (head){nl} -> {oldhead} -> {obj1} -> {obj2} ... {objn} -> null]
這樣list的頭就是newlist, 而oldhead就變成了第二個元素, 後面的元素以此類推.
『陸』 用Java實現一個地鐵票價計算程序，希望給出主要演算法與數據結構
根據某市地鐵線路圖寫一個地鐵票價計算程序
需求描述：
1.計費規則：最低2元，超過5站以上每站加收0.5元，換乘重新起算，例如L1先坐4站，換乘L2再坐6站，結果就是2+2.5=5.5元
2.程序啟動以後讀取輸入文件（in.txt），內容格式如：
L2-8,L2-2
X3,L3-8
....
每行表示一次行程，起點站和終點站之間用逗號分隔，行數不限
4.系統按最短路徑方案（盡量少換乘且站數少，假設乘 客換乘一次用的時間相當於坐4個站）規劃路線，計算票價，並把路線和票價輸出到文件(out.txt)，內容格式如：
L2-8,L2-2=2.5:L2-8,L2-7,L2-6,L2-5,L2-4,L2-3,L2-2
X3,L3-8=4:X3,X4,L3-8
....
等號後面的表示票價和路徑
地鐵線路圖如下：共有5條線路，X開頭的站點表示 換乘車站
『柒』 用java實現一個數據結構！
import java.io.IOException;
import java.util.Scanner;
public class LinkList {
private static Scanner san = new Scanner(System.in);
public static void main(String[] args) throws IOException {
List list = new List();
for (int i = 1; i <= 10; i++) {
System.out.print("請輸入第" + i + "個數: ");
list.add(san.nextInt());
list.print();
}
System.out.println("輸入的數據如下: ");
list.print();
}
}
class node {
int data;
node next = this; // 指向自己
}
class List {
private node header = new node();
// 循環鏈表的尾部添加數據
public node add(int data) {
node current = new node();
node temp = header;
while (temp.next != header)
temp = temp.next;
current.data = data;
current.next = temp.next;
temp.next = current;
return current;
}
// 查詢某個數字的位置 如果不在 返回-1；
public int search(int data) {
node temp = header;
int n = 0;
while (temp.next != header) {
temp = temp.next;
n++;
if (temp.data == data)
break;
}
if (temp.data == data)
return n;
else
return -1;
}
// 列印出整個鏈表
public void print() {
node temp = header;
while (temp.next != header) {
temp = temp.next;
System.out.print(temp.data + " ");
}
System.out.println();
}
// 插入數據
public node Insert(int pos, int data) {
node temp = header;
node current = new node();
for (int i = 0; i < pos - 1; i++) {
if (temp.next != header) {
temp = temp.next;
} else
return null;
}
current.data = data;
if (temp.next != header) {
current.next = temp.next;
}
temp.next = current;
return current;
}
// 刪除某個數據
public node del(int data) {
node temp = header;
node oldtemp = null;
node current = null;
while (temp.next != header) {
oldtemp = temp;
temp = temp.next;
if (temp.data == data) {
current = temp;
break;
}
}
if (current == header)
return null;
oldtemp.next = current.next;
return current;
}
}
『捌』 數據結構JAVA編程求教
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
#define N 9 /* 數據元素個數 */
typedef char KeyType; /* 設關鍵字域為字元型 */
typedef struct /* 數據元素類型 */
{
KeyType key;
int weight;
}ElemType;
ElemType r[N]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3},
{'F',4},{'G',4},{'H',3},{'I',5}}; /* 數據元素(以教科書例9-1為例),全局變數 */
int sw[N+1]; /* 累計權值，全局變數 */
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef struct
{
ElemType *elem; /* 數據元素存儲空間基址，建表時按實際長度分配，0號單元留空 */
int length; /* 表長度 */
}SSTable;
Status Creat_Seq(SSTable *ST,int n)
{ /* 操作結果: 構造一個含n個數據元素的靜態順序查找表ST(數據來自全局數組r) */
int i;
(*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType)); /* 動態生成n個數據元升缺素空間(0號單元不用) */
if(!(*ST).elem)
return ERROR;
for(i=1;i<=n;i++)
*((*ST).elem+i)=r[i-1]; /* 將全局數組r的值依次賦給ST */
(*ST).length=n;
return OK;
}
void Ascend(SSTable *ST)
{ /* 重建靜態查找表為按關鍵字非降序排序 */
int i,j,k;
for(i=1;i<(*ST).length;i++)
{
k=i;
(*ST).elem[0]=(*ST).elem[i]; /* 待比較值存[0]單元 */
for(j=i+1;j<=(*ST).length;j++)
if LT((*ST).elem[j].key,(*ST).elem[0].key)
{
k=j;
(*ST).elem[0]=(*ST).elem[j];
}
if(k!=i) /* 有更小的值則交換 */
{
(*ST).elem[k]=(*ST).elem[i];
(*ST).elem[i]=(*ST).elem[0];
}
}
}
Status Creat_Ord(SSTable *ST,int n)
{ /* 操作結果: 構造一個含n個數據元素的靜態按關鍵字非降序查找表ST */
/* 數據來自全局數組r */
Status f;
f=Creat_Seq(ST,n);
if(f)
Ascend(ST);
return f;
}
Status Traverse(SSTable ST,void(*Visit)(ElemType))
{ /* 初始條件: 靜態查找表ST存在，Visit()是對元素操作的應用函數 */
/* 操作結果: 按順序對ST的每個元素調用函數Visit()一次且僅一次。 */
/* 一旦Visit()失敗，則槐逗操作失敗 */
ElemType *p;
int i;
p=++ST.elem; /* p指向第一個元素鉛笑賣 */
for(i=1;i<=ST.length;i++)
Visit(*p++);
return OK;
}
typedef ElemType TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode,*BiTree;
Status SecondOptimal(BiTree *T, ElemType R[],int sw[],int low,int high)
{ /* 由有序表R[low..high]及其累計權值表sw(其中sw[0]==0)遞歸構造 */
/* 次優查找樹T。*/
int i,j;
double min,dw;
i=low;
min=fabs(sw[high]-sw[low]);
dw=sw[high]+sw[low-1];
for(j=low+1;j<=high;++j) /* 選擇最小的△Pi值 */
if(fabs(dw-sw[j]-sw[j-1])<min)
{
i=j;
min=fabs(dw-sw[j]-sw[j-1]);
}
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
return ERROR;
(*T)->data=R[i]; /* 生成結點 */
if(i==low)
(*T)->lchild=NULL; /* 左子樹空 */
else
SecondOptimal(&(*T)->lchild,R,sw,low,i-1); /* 構造左子樹 */
if(i==high)
(*T)->rchild=NULL; /* 右子樹空 */
else
SecondOptimal(&(*T)->rchild,R,sw,i+1,high); /* 構造右子樹 */
return OK;
}
void FindSW(int sw[],SSTable ST)
{ /* 按照有序表ST中各數據元素的Weight域求累計權值表sw */
int i;
sw[0]=0;
for(i=1;i<=ST.length;i++)
sw[i]=sw[i-1]+ST.elem[i].weight;
}
typedef BiTree SOSTree; /* 次優查找樹採用二叉鏈表的存儲結構 */
Status CreateSOSTree(SOSTree *T,SSTable ST)
{ /* 由有序表ST構造一棵次優查找樹T。ST的數據元素含有權域weight。*/
if(ST.length==0)
*T=NULL;
else
{
FindSW(sw,ST); /* 按照有序表ST中各數據元素的Weight域求累計權值表sw */
SecondOptimal(T,ST.elem,sw,1,ST.length);
}
return OK;
}
Status Search_SOSTree(SOSTree *T,KeyType key)
{ /* 在次優查找樹T中查找關鍵字等於key的元素。找到則返回OK，否則返回FALSE */
while(*T) /* T非空 */
if((*T)->data.key==key)
return OK;
else if((*T)->data.key>key)
*T=(*T)->lchild;
else
*T=(*T)->rchild;
return FALSE; /* 順序表中不存在待查元素 */
}
void print(ElemType c) /* Traverse()調用的函數 */
{
printf("(%c %d) ",c.key,c.weight);
}
void main()
{
SSTable st;
SOSTree t;
Status i;
KeyType s;
Creat_Ord(&st,N); /* 由全局數組產生非降序靜態查找表st */
Traverse(st,print);
CreateSOSTree(&t,st); /* 由有序表構造一棵次優查找樹 */
printf(" 請輸入待查找的字元: ");
scanf("%c",&s);
i=Search_SOSTree(&t,s);
if(i)
printf("%c的權值是%d ",s,t->data.weight);
else
printf("表中不存在此字元 ");
}
運行結果：
這個是數據結構上的一個源碼，你用這個自己改一改試試吧
『玖』 java數據結構與演算法分析
於之前面試android的時候考到了很多關於java的知識，所以這次重溫數據結構知識就打算用java來學習，畢竟android是以java為基礎的，而且我現在學習的j2ee架構也是以java為基礎的。
java中的類就是對現實世界的對象的一種抽象，例如人就是一個類別，人有名字，聯系電話，住址等成員屬性，人擁有說話，吃飯，走路等成員方法。類就是這樣，定義了一種對象，它有什麼，會做什麼。
繼承——子類就是父類的一種特定類別。例如學生就是人的子類，學生屬於人，是特定的一類人。所以我們讓學生繼承人，這樣學生可以擁有人的屬性和方法，也就是說，學生也有了名字，聯系電話，住址等成員屬性，擁有說話，吃飯，走路等成員方法。但是學生還有特定的一些方法（讀書，上課），或者特定的一些屬性（學號，年級），這些可以添加在子類中。
因為每個子類都屬於父類，例如每個學生都屬於人，所以可以用父類來引用子類的對象:People p = new Student();反過來不行。
java中一個類只能繼承一個父類，也就是單繼承。
但一個類可以實現多個介面，間接地實現了多繼承。介面就是一系列方法的聲明，沒有實現。於之前面試android的時候考到了很多關於java的知識，所以這次重溫數據結構知識就打算用java來學習，畢竟android是以java為基礎的，而且我現在學習的j2ee架構也是以java為基礎的。
java中的類就是對現實世界的對象的一種抽象，例如人就是一個類別，人有名字，聯系電話，住址等成員屬性，人擁有說話，吃飯，走路等成員方法。類就是這樣，定義了一種對象，它有什麼，會做什麼。
繼承——子類就是父類的一種特定類別。例如學生就是人的子類，學生屬於人，是特定的一類人。所以我們讓學生繼承人，這樣學生可以擁有人的屬性和方法，也就是說，學生也有了名字，聯系電話，住址等成員屬性，擁有說話，吃飯，走路等成員方法。但是學生還有特定的一些方法（讀書，上課），或者特定的一些屬性（學號，年級），這些可以添加在子類中。
因為每個子類都屬於父類，例如每個學生都屬於人，所以可以用父類來引用子類的對象:People p = new Student();反過來不行。
java中一個類只能繼承一個父類，也就是單繼承。
但一個類可以實現多個介面，間接地實現了多繼承。介面就是一系列方
『拾』 工作一到五年的Java程序員遇到瓶頸應該如何提升
工作了5年的Java程序員，該如何提升,做了3~5年Java開發，你已經積累了不少項目經驗，擴寬了技術廣度，也許已發力成為團隊管理者。到了這個階段，大家卻常有這種感受：感覺自己卡在瓶頸進步緩慢，技術水平很難像早期一樣實現大幅突破？
其實大家往往忽略了這一點——提升自己的架構認知（工作5年左右程序員必須重視架構認知的提升，這會很大程度上推動你今後的成長）。架構的本質在於面對業務場景給出優雅的解決方案，使得業務能夠快速迭代和持續交付，從而達到降本增效的目標。提升架構認知高度，就像達克效應所描述的一樣，要敢於從愚昧之巔跳到絕望之谷，通過爬升開悟之坡，從而達到架構認知的巔峰時刻。到達巔峰時刻也就掌握了架構背後設計的哲學，面對具體業務場景在架構層面你便能夠輕松應對，以無招勝有招。
提升架構認知，要緊抓3個關鍵點：業務洞察力、技術視野、原創力（執行力）。
1.業務洞察力是技術戰略層面的問題，在當下能夠做出合理的判斷，清楚公司做什麼事情收益最大；
2. 技術視野即技術選型能力，是技術戰術層面的問題，在清楚做什麼事情後，需要進一步解決怎麼做的問題，也就是能夠給出合理的技術選型方案：是完全基於開源的方案，還是基於開源二次開發的方案，還是完全自研的方案；
3. 原創力（執行力）是技術落地執行層面的問題，一旦技術設計方案確定後，需要能夠快速Rush完成。
這3點層層遞進，最重要的是先把技術戰略問題思考清楚，然後再進一步解決技術戰術問題，最後是快速落地執行的問題。
工作5年左右的程序員，在原創力（執行力）層面比較有競爭力，往往欠缺技術視野以及業務洞察力。後面2點更加重要，這2點解決的是架構設計哲學問題，是架構師能夠持續擁有競爭力和影響力的立身之道。
舉個場景的例子來詳細說明：一提到分布式鎖問題，大多數人想到的方案是基於Redis的Master-Slave模式來實現。這個實現方案行不行？分布式鎖本質是一個CP需求，基於Redis的實現是一個AP需求，乍一看基於Redis的實現是無法滿足的。脫離業務場景來談架構都是耍流氓。
從技術戰略的需求層面來看，如果分布式鎖在極端情況下獲取鎖的不一致，社交業務場景能夠接受，那麼基於Redis的實現是完全可行的。如果業務是交易場景，分布式鎖在極端情況下獲取鎖的不一致性無法接受，那麼基於Redis的實現方案是不可行的。在鎖強一致性的場景下，需要採取基於CP模型的etcd等方案來實現。