資料結構介紹
本章介紹為什麼需要學習資料結構
一個小問題
請同學寫一個小程式來產生1~6數字的任意排列，例如: 152346, 243561, 每次產生不同的數字排列
這是一個很小的問題，我們要寫出這個程式(program), 需要用到演算法(algorithm)和資料結構(data structure)的搭配。
我們需要使用序列(List)的資料結構抽象定義，並且設計以下演算法：
定義一個序列的6個籃子(bin)，每個籃子分別放入1~6的數字
從1~6執行以下:
選取一個亂數(小於或等於籃子數)，取出該籃子，印出該藍子的數字。
將該藍子從序列中移除。
C程式解答
我們可以將這個演算法寫成C的程式(ex1.c)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
//generate 1~6 random numbers
int num, i, j;
int bin[6];
int ans[6];
int bin_length = 6;
int select;
for (i=0; i<6; i++){
bin[i] = i+1;
}
/* Seed the random-number generator with */
srand( (unsigned) time( NULL ) );
for (i=0; i<6; i++)
{
select = rand()%bin_length;
ans[i] = bin[select];
//remove the selected item
for (j=select; j<bin_length; j++ ){
bin[j]=bin[j+1];
}
bin_length--;
}
for (i=0; i<6; i++){
printf("%d ", ans[i]);
}
return 0;
}
將這個演算法寫成用linked list的C的程式(ex2.c)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node
{
int value;
struct node *next;
};
struct node * RemoveAt(struct node *head, int pos){
struct node *curr = NULL;
struct node *prev = NULL;
struct node *next = NULL;
int i;
if (head == NULL)
return NULL;
if (pos==0){
next = head->next;
free (head);
return next;
}
curr = head;
for ( i=0; i< pos; i++){
if (curr == NULL)
return NULL;
prev = curr;
curr = curr->next;
}
//link prev->next
next = curr->next;
free(curr);
prev->next = next;
return head;
}
int main(){
//generate 1~6 random numbers
int num, i, j;
int bin[6];
int ans[6];
int bin_length = 6;
int select;
struct node *head = NULL;
struct node *curr = NULL;
head = (struct node *) malloc( sizeof(struct node) );
head->next = NULL;
curr = head;
for (i=0; i<6; i++){
//bin[i] = i+1;
curr->value = i+1;
if (curr->next==NULL){
curr->next = (struct node *) malloc( sizeof(struct node) );
curr = curr->next;
curr->next=NULL;
}
}
/* Seed the random-number generator with */
srand( (unsigned) time( NULL ) );
for (i=0; i<6; i++)
{
select = rand()%bin_length;
//remove the selected item
curr = head;
for (j=0; j<select; j++ ){
curr = curr->next;
}
ans[i] = curr->value;
head = RemoveAt(head, select);
bin_length--;
}
for (i=0; i<6; i++){
printf("%d ", ans[i]);
}
return 0;
}
Java程式解答
我們可以將這個演算法寫成Java的程式(Ex1Class.java)
import java.io.*;
import java.util.*;
public class Ex1Class {
public static void main(String[] args) {
//generate 1~6 random numbers
int num, i, j;
int[] bin = new int[6];
int[] ans = new int[6];
int bin_length = 6;
int select;
for (i=0; i<6; i++){
bin[i] = i+1;
}
/* New a random-number generator object */
Random random = new Random();
for (i=0; i<6; i++){
select = random.nextInt()%bin_length;
if (select < 0)
select =-select;
ans[i] = bin[select];
//remove the selected item
for (j=select; j<bin_length-1; j++ )
{
bin[j]=bin[j+1];
}
bin_length--;
}
for (i=0; i<6; i++){
System.out.printf("%d ", ans[i]);
}
}
}
進一步使用我們可以將這個演算法改成使用Java的ArrayList類別的程式(Ex2Class.java)
import java.io.*;
import java.util.*;
public class Ex2Class {
public static void main(String[] args) {
//generate 1~6 random numbers
int num, i;
//int[] bin = new int[6];
ArrayList <Integer> bin = new ArrayList<Integer>();
int[] ans = new int[6];
int bin_length = 6;
int select;
for (i=0; i<6; i++){
//bin[i] = i+1;
bin.add(i+1);
}
/* New a random-number generator object */
Random random = new Random();
for (i=0; i<6; i++){
select = (random.nextInt()& Integer.MAX_VALUE)%bin_length;
//ans[i] = bin[select];
ans[i] = bin.get(select);
//remove the selected item
bin.remove(select);
bin_length--;
}
for (i=0; i<6; i++){
System.out.printf("%d ", ans[i]);
}
}
}
也可以將這個演算法改成使用Java的LinkedList類別的程式(Ex3Class.java)
import java.io.*;
import java.util.*;
public class Ex1Class {
public static void main(String[] args) {
//generate 1~6 random numbers
int num, i;
//int[] bin = new int[6];
LinkedList<Integer> bin = new LinkedList<Integer>();
int[] ans = new int[6];
int bin_length = 6;
int select;
for (i=0; i<6; i++){
//bin[i] = i+1;
bin.add(i+1);
}
/* New a random-number generator object */
Random random = new Random();
for (i=0; i<6; i++){
select = (random.nextInt()& Integer.MAX_VALUE)%bin_length;
//ans[i] = bin[select];
ans[i] = bin.get(select);
//remove the selected item
bin.remove(select);
bin_length--;
}
for (i=0; i<6; i++){
System.out.printf("%d ", ans[i]);
}
}
}
Go程式解答
我們可以將這個演算法寫成Go的程式(ex1.go)
package main
import "time"
import "fmt"
import "math/rand"
func main() {
//generate 1~6 random numbers
var i, j int
var bin [6]int
var ans [6]int
var curselect int
bin_length := 6
for i=0; i<6; i++{
bin[i] = i+1
}
// The default number generator is deterministic, so it'll
// produce the same sequence of numbers each time by default.
// To produce varying sequences, give it a seed that changes.
// Note that this is not safe to use for random numbers you
// intend to be secret, use `crypto/rand` for those.
s1 := rand.NewSource(time.Now().UnixNano())
rand1 := rand.New(s1)
for i=0; i<6; i++{
curselect = rand1.Intn(bin_length);
ans[i] = bin[curselect];
//remove the selected item
for j=curselect; j<bin_length-1; j++ {
bin[j]=bin[j+1]
}
bin_length--;
}
for i=0; i<6; i++ {
fmt.Printf("%d ", ans[i]);
}
}
進一步使用我們可以將這個演算法改成使用Go的Slice的程式(ex2.go)
package main
import "time"
import "fmt"
import "math/rand"
func main() {
//generate 1~6 random numbers
var i int
var bin = make([]int, 6)
var ans [6]int
var curselect int
bin_length := 6
for i=0; i<6; i++{
bin[i] = i+1
}
// The default number generator is deterministic, so it'll
// produce the same sequence of numbers each time by default.
// To produce varying sequences, give it a seed that changes.
// Note that this is not safe to use for random numbers you
// intend to be secret, use `crypto/rand` for those.
s1 := rand.NewSource(time.Now().UnixNano())
rand1 := rand.New(s1)
for i=0; i<6; i++{
curselect = rand1.Intn(bin_length);
ans[i] = bin[curselect];
//remove the selected item
/*for j=curselect; j<bin_length-1; j++ {
bin[j]=bin[j+1]
}*/
bin = append(bin[:curselect], bin[curselect+1:]...)
bin_length--;
}
for i=0; i<6; i++ {
fmt.Printf("%d ", ans[i]);
}
}
說明
- slice是一個陣列(array)的參考，可以用make動態產生。make([]int, 6)是產生一個長度為6的陣列
- append(bin[:j], bin[j+1:]...)是刪掉slice的第i個元素。https://github.com/golang/go/wiki/SliceTricks
也可以將這個演算法改成使用Go的List package的程式(ex3.go)
package main
import "time"
import "fmt"
import "math/rand"
import "container/list"
func main() {
//generate 1~6 random numbers
var i, j int
//var bin [6]int
bin := list.New() //創建一个新的list
var ans [6]int
//var select int 因為select是Go語言關鍵字，所以我們不用了，改用cursel
//bin_length := 6
for i=0; i<6; i++{
bin.PushBack(i+1)
}
s1 := rand.NewSource(time.Now().UnixNano())
rand1 := rand.New(s1)
for i=0; i<6; i++{
cursel := rand1.Intn(bin.Len());
e := bin.Front()
//remove the selected item
for j=0; j<cursel; j++ {
e = e.Next()
}
//ans[i] = bin[curselect];
ans[i] = e.Value.(int)
bin.Remove(e)
}
for i=0; i<6; i++ {
fmt.Printf("%d ", ans[i]);
}
}