一維陣列
陣列 - 使用C語言為範例
一維陣列
一維陣列宣告語法如下：
說明
資料型態
陣列名稱
行數 n ：ｎ為整數。代表此陣列維度１有ｎ個元素。
一維陣列，只有一個［］
註標或索引的範圍介於0與n-1之間
初始化
一維陣列 - 範例
輸入一星期每天花費的費用，印出總花費(請用陣列)。
#include <stdio.h>
int main(int argc, char const *argv[])
{
int m[7], total=0;
for(int i = 0 ; i< 7 ; i ++){
printf("輸入星期 %d 的花費",i+1);
scanf("%d",&m[i]);
total+=m[i];
}
printf("一星期花費:%d\n",total);
return 0;
}
字串
字串是由多個字組成的資料，必以'\0'(空字元)作為結束字串資料的結束。因此字串可用一維字元陣列的形式表示。
字串陣列宣告方式
若是用字串存8bytes 的內容
char id[9];
// 0-8 共有9個 設定初始設定語法有下列方法
char arrayname[長度 +1] = "字串內容";
char arrayname [長度+1] ={'字元1','字元2'...}排序法
氣泡排序法(Bubble Sort )-範例
這個是將相鄰兩個資料逐一比較，資料是否需要互相交換位置。將 26、12、6 、 10、 58 用氣泡排序法從小排到大。
void SelSort(int A[], int n) //選擇排序法之副程式
{
int i, j, Temp, Min = 0;
for (i = 1; i <= n - 1; i++)
{
Min = i;
for (j = i + 1; j <= n; j++)
if (A[j] < A[Min])
Min = j;
{//相鄰兩個的資料交換位置
Temp = A[i];
A[i] = A[Min];
A[Min] = Temp;
}
}
}插入排序法(Insertion Sort)
依序由未排序的資料中選一筆資料
一一掃瞄已排序資料，將選取的資料插入正確位置
void InSort(int A[], int n)
{
int i, j, Temp;
for (i = 1; i <= n; i++)
{
Temp=A[i];
j=i-1;
while (Temp<A[j])
{
A[j+1]=A[j];
j--;
if(j==-1)
break;
}
A[j+1]=Temp;
}
}選擇排序法(Selection Sort)
void SelSort(int A[], int n) //選擇排序法之副程式
{
int i, j, Temp, Min = 0;
for (i = 1; i <= n - 1; i++)
{
Min = i;
for (j = i + 1; j <= n; j++)
if (A[j] < A[Min])
Min = j;
{//相鄰兩個的資料交換位置
Temp = A[i];
A[i] = A[Min];
A[Min] = Temp;
}
}
}資料搜尋
線性搜尋法 - Sequential Search
1.無崗哨(衛兵)線性搜尋(Non-Sentinel Linear Search)
直接對數列由右至左，或由左至右一一比對是否有與鍵值相同的元素
需比對陣列值是否與鍵值相同、陣列是否結束
2.崗哨(衛兵)線性搜尋(Sentinel Linear Search)
直接對數列由右至左，或由左至右一一比對
將鍵值放在陣列的第一個或最後一個元素，並把這個元素當成崗哨(衛兵)
一定可以找到與鍵值相同的元素 ⇒ 避免檢查陣列是否結束
因為省下一次比較的時間，當資料很大時，時間約為無崗哨線性搜尋的一半(時間複雜度仍為Ο(n))
特性：
資料不需事先排序
支援隨機存取(Random Access)與循序存取(Sequential Access)機制
時間複雜度為Ο(n) ⇒ 線性
時間複雜度(Time Complexity)
(1+2+3+...+n)/n = (n+1)/2 ⇒ Ο(n)
#include<stdio.h>
#include<stdlib.h>
void main (){
int search_Ctr[] = {6,1,7,2,8,3,8,4,9,5,10};//初始內容
int Ctr_Max = sizeof(search_Ctr)/sizeof(search_Ctr[0]); //陣列的長度
int key = 0;int index = 0; // key =需要搜尋的值
scanf("%d",&key);
while (index < Ctr_Max)
{
if(search_Ctr[index] == key){ printf("key is %d ",index); break;}
index++;
if(index>= Ctr_Max) {printf("Not key");}
}
}二分搜尋法 - Binary Search
是一種在有序陣列中搜尋某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
二分搜尋演算法在最壞情況下是對數時間複雜度的，需要進行{O(\log n)}次比較操作
在此處是陣列的元素數量，
是大O記號，
是對數）。二分搜尋演算法使用常數空間，對於任何大小的輸入資料，演算法使用的空間都是一樣的。除非輸入資料數量很少，否則二分搜尋演算法比線性搜尋更快，但陣列必須事先被排序。儘管一些特定的、為了快速搜尋而設計的資料結構更有效（比如雜湊表），二分搜尋演算法應用面更廣。
#include<stdio.h>
#include<stdlib.h>
void search(int *search_Ctr, int target, int key);
void main (){
int search_Ctr[] = {1,2,3,4,5,6,7,8,9,10};//初始內容
int Ctr_Max = sizeof(search_Ctr)/sizeof(search_Ctr[0]); //陣列的長度
int key = 0;int index = 0; // key =需要搜尋的值
scanf("%d",&key);
search(search_Ctr, Ctr_Max , key);
}
void search(int *search_Ctr, int target ,int key){
int index = 0 ,low= 0, height = target-1 ;
while (index < target)
{
int mid = (height + low) / 2 ;
if(search_Ctr[mid]< key){
low = mid+1;
}
else if(search_Ctr[mid] > key){
height = mid-1;
}
else {
printf("%d ",mid);
break;
}
index++;
}
}
亂數種子 - rand()及srand()
time()函數
使用srand()來設定亂數種子，其來源可以是CPU、記憶體、時間等，最常用時間來當亂數種子，必須使用time()函數時須include<time.h>。
srand((unsigned) time(NULL)); 只要放在程式一開始的地方，千萬別放在跑亂數的迴圈中，因為CPU執行指令極快速，取的時間種子相差很小，而你取出來的每個數字都會很相近。
不過用取時間種子還有個缺點，當使用者在一秒執行程式數次，因為取時間是以秒為單位，所以會出現很相近的亂數，改善的方式就是將時間再跟其他來源作運算。例如用PID：
srand((unsigned) time(NULL) + getpid());整數亂數
rand()這個函數會隨機產生0~RAND_MAX的數字，而RAND_MAX為編譯器設定的數字，可以用Printf("%d",RAND_MAX)來查看。要產生特定範圍的亂數只要先產生0~1的隨機數就可以完成，產生down~up的亂數公式如下：
#[down, up] 含上界
rand_num = <up-down> * rand() / RAND_MAX + <down>;
#[down, up) 不含上界
rand_num = <up-down> * rand() / (RAND_MAX + 1) + <down>; 很多人會用取mod來算亂數，但這樣會有些數字機率較小，相較而言用上述方法就比較好。 例如我要產生15~30之間的數字 ，也就是[15, 30]：
rand_num = (30-15) * rand() / (RAND_MAX) + 15範例程式是產生10個1到100的亂數：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
int n = 10;
srand((unsigned) time(NULL) + getpid());
while(n-- > 0)
printf("%d\n", 99 * rand() / RAND_MAX + 1);
return 0;
}小數亂數
將整數亂數的公式改一下就可以實現小數亂數了，如下：
#[down, up] 含上界
rand_num = <up-down> * rand() / RAND_MAX + <down>;
#[down, up) 不含上界
rand_num = <up-down> * rand() / (RAND_MAX + 1.0) + <down>;例如我要產生-3.0~3.0 之間的數字，也就是[-3.0, 3.0]：
rand_num = (3.0 - (-3.0)) * rand() / RAND_MAX + (-3.0);下面這個範例程式是產生10個-5.0到5.0的亂數：
#include <stdlib.h>
#include <time.h>
int main() {
int n = 10;
srand((unsigned) time(NULL) + getpid());
while(n-- > 0)
printf("%lf\n", 10.0 * rand() / RAND_MAX - 5.0);
return 0;
}不重複亂數
要產生不重複的亂數有很多方法，最簡單的就是暴力產生，比對過去產生的數字有相同就重新取，但如果數字一多效率就很差，所以建議要去量大的不重複亂數，可以使用洗牌法來取。所謂洗牌法就像玩撲克牌一樣，將欲取的亂數放入陣列，再進行洗牌的動作將數字打亂，之後再取出。
下面這個程式是產生30個1到100不重複亂數：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Size 100
#define Num 30
int main() {
int i, poker[Size], temp, pos;
srand((unsigned) time(NULL) + getpid());
//放入數字
poker[0] = 100;
for(i = 1; i < Size; ++i)
poker[i] = i;
//洗牌
for(i = 0; i < Size; ++i){
pos = 99 * rand() / RAND_MAX;
temp = poker[i];
poker[i] = poker[pos];
poker[pos] = temp;
}
//印出前30個字
for(i = 0; i < Num; ++i)
printf("%d ", poker[i]);
return 0;
}不均勻機率亂數
如果是要機率不同的亂數，可以使用陣列來模擬，數量多了話則可以用IF來判斷。
例如有一個抽獎系統，獎品分為特獎、頭獎、二獎、三獎、四獎、五獎、安慰獎，機率分別為0.00001、0.00005、0.0001、0.001、0.01、0.1、0.88884且和為1，把它們都乘上100000後分別為1、5、10、100、1000、10000、88884，這樣就可以藉由亂數產生1~100000來模擬不均勻機率抽獎，下面為範例程式：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define A1 1
#define A2 5
#define A3 10
#define A4 100
#define A5 1000
#define A6 10000
#define A7 88884
#define Total 100000
int main() {
int r;
srand((unsigned) time(NULL) + getpid());
printf("歡迎來到「不均勻機率抽獎系統」\n");
system("PAUSE");
while(1){
r = (Total - 1) * rand() / RAND_MAX + 1;
if(r == A1)
printf("# 恭喜獲得「特獎」\n");
else if(r > A1 && r <= A2 + A1)
printf("# 恭喜獲得「頭獎」\n");
else if(r > A2 + A1 && r <= A3 + A2 + A1)
printf("# 恭喜獲得「二獎」\n");
else if(r > A3 + A2 + A1 && r <= A4 + A3 + A2 + A1)
printf("# 恭喜獲得「三獎」\n");
else if(r > A4 + A3 + A2 + A1 && r <= A5 + A4 + A3 + A2 + A1)
printf("# 恭喜獲得「四獎」\n");
else if(r > A5 + A4 + A3 + A2 + A1 && r <= A6 + A5 + A4 + A3 + A2 + A1)
printf("# 恭喜獲得「五獎」\n");
else
printf("# 恭喜獲得「安慰獎」\n");
system("PAUSE");
}
return 0;
}
最后更新于
这有帮助吗？