歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C語言之數組

1,數組簡介:
所謂數組,就是相同數據類型的元素按一定順序排列的集合,就是把有限個類型相同的變量用一個名字命名,然後用編號區分他們的變量的集合,這個名字稱為數組名,編號稱為下標。組成數組的各個變量稱為數組的分量,也稱為數組的元素,有時也稱為下標變量。數組是在程序設計中,為了處理方便, 把具有相同類型的若干變量按有序的形式組織起來的一種形式。這些按序排列的同類數據元素的集合稱為數組。

2,例子要求:
針對數組這個最基礎的數據結構,列舉這個數據結構可以支持的操作,並以大O的方式分析各個操作的時間復雜度

3,實現過程:

#include <QCoreApplication>
//數組的基本操作,排序,取最大值,模糊查詢某個值

// 【1】數組排序 算法
// 1.1, 冒泡排序 O(n2)
最好的是數組有序情況下為:O(2N),

平均是正常隨機亂序為:O(2N),

最差的是數據完全亂序O(n2)。

void BubbleSort(int A[], int N)

{

 int tmp;
 for (i = 0; i < N - 1; ++i)
 {
 for (j = 1; j < N - i; ++j)
 {
 if (A[j] > A[j - 1]) //從大到小排序,把較小的交換到後面來
 {
 tmp = A[j - 1];
 A[j - 1] = A[j];
 A[j] = tmp;
 }
 }
 }
}

 


// 1.2 快速排序,它的平均時間復雜度為O(Nlog2N)
最好的是數組有序情況下時間復雜度為:O(nlogn),
平均是正常隨機亂序時平均時間復雜度為:O(nlogn)。 ,
最差的是數據完全亂序O(n^2)。
int Partition(int *arr, int low, int high)
{
 int pivot = arr[low];
 while(low < high)
 {
 while(low < high && arr[high] <= pivot) high--;
 arr[low] = arr[high];
 while(low < high && arr[low] >= pivot) low++;
 arr[high] = arr[low];
 }
 arr[low] = pivot;
 return low;
}


void Qsort(int *arr, int low, int high)
{
 if (low < high)
 {
 int mid = Partition(arr, low, high);
 Qsort(arr, low, mid - 1);
 Qsort(arr, mid + 1, high);
 }
}


// 【2】 數組取最大值 算法
最好情況下,最大值在第一個,時間復雜度為:O(n^2)
平均是,最大值在中間位置,時間復雜度:O(n).
最差是,最大值在末尾,時間復雜度:O(2^n)
int max(int array[],int n);
void main( )
{
 int num[N],count,i,val;
? scanf("%d",&count);
 for (i=0;i<count;i++)
 {
 scanf("%d",&num[i]);
 }
 val=max(num,count);
 printf("%dn",val);
 }

int max(int array[ ],int n)
{
 if (n<=1)
 return(array[0]); // 就一個數,最大值就是自已
 int t=max(array+1,n-1); // 求後面 n-1個數的最大值
 if (t>array[0]) // t 比第一個大,返回最大 t
 return(t);
 else
 return(array[0]); // t小,返回array[0];
}

// 【3】 數組查詢是否包含某個值
最好情況下,就是第一個,時間復雜度為O(1);
平均情況下,值在中間,時間復雜度為0(N/2);
最壞情況下,值在末尾或者不存在,時間復雜度為O(N);
int main()
{
 int n,m,i,a[20];
 int find;
 scanf("%d",&n);
 for(i=0;i<n;i++){
 scanf("%d",&a[i]);
 }
 scanf("%d",&m);
 find = -1;
 for(i=0;i<n;i++){
 if(a[i] == m){
 find = i;
 break;
 }
 }

 if(find < 0) {
 printf("Non");
 }
 else {
 printf("%dn", find);
 }
 return 0;
}


// 【4】數組輸入輸出,一時沒有想到用什麼算法,順序遍歷?

C++ 隱式類類型轉化 Implicit Class-Type Conversions http://www.linuxidc.com/Linux/2013-01/78071.htm

C語言變長數組之剖析 http://www.linuxidc.com/Linux/2013-07/86997.htm

C語言需要注意的問題 http://www.linuxidc.com/Linux/2013-05/84301.htm

C語言位域的使用及其注意點 http://www.linuxidc.com/Linux/2013-07/87027.htm

C語言中簡單的for循環和浮點型變量 http://www.linuxidc.com/Linux/2013-08/88514.htm

Copyright © Linux教程網 All Rights Reserved