最近在學習排序的過程中,發現很多排序的程式中都會用到數組元素值互換的一小段代碼。然後想着直接把元素值的互換寫成函數以後直接調用即可,當時命名為`void change(int * a, int * b)。`
昨天在學習别人的排序程式時看見了swap()函數,這時候我才進一步知道了這個不是标準庫函數卻勝似标準庫函數的函數,上網搜尋`swap()`之後,又學到了不少新東西。學習就是一個積累的過程,在查漏補缺的過程中慢慢學習,寫部落格則是溫故而知新的不錯選擇,可能在寫的過程中又會出現不解的問題,正好可以及時學習,是以今天總結一下自己對`swap()`的學習。
在最初接觸C的時候,我們都知道一個簡單的整型值互換(變量`a=10,b=20`值互換)的程式:
int t = 0;
t = a;
a = b;
b = t;
這段代碼雖然簡單,但是在當時學習的過程中不禁驚呼:哇塞,好神奇。現在想想其實這段代碼雖然簡單但是說實在的,其中也是包含了變量定義、初始化、指派以及簡單的記憶體的知識,正所謂麻雀雖小五髒俱全。
swap()
常見的有以下四種形式:
void swap_1 (int * , int *);//經典型
void swap_2 (int * , int *);//取巧型
void swap_3 (int * , int *);//詭異型
void swap_4 (void * a, void *b, size_t size);//泛型
1、 void swap_1 (int * , int *);//經典型
void swap_1 (int * , int *);//經典型
而
swap()
函數的寫法最簡單的一種寫法便是我們初次接觸的這段代碼。
void swap_1 (int * a, int * b)//a,b變量接收了要比較的兩個變量的位址
{
int temp;//temp作為互換時的中間媒體,起到了一個避免資料丢失的作用
temp = * a;
* a = * b;
* b = temp;
}
比較時隻需要調用swap_1(&a,&b);發送位址即可。再看這段代碼的時候,隻是角度不同了(有了函數和指針的思想),其他也沒有什麼了,這裡我也就不啰嗦說那麼多了。以下三種是新學到的,雖然都隻是用來互換變量内容的,但是思想上有了更多的趣味性。
2、 void swap_2 (int * , int *);//取巧型
void swap_2 (int * , int *);//取巧型
void swap_2 (int * a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
我們會發現,
swap_2()
中并沒有采用像
swap_1()
中
temp
似的任何中間變量,隻是
*a,*b
之間經過了加加減減的幾步操作之後便實作了變量值的互換。這些是完全的數學運算的奧妙。但是我們不妨分析一下,也好在這枯燥的代碼中找到點樂子(←_←)。
首先假設
*a =A;*b =B;
那麼第一行:
*a=*a +*b=A+B,
此時*a的值就已經變了,變成了最初的
*a
與
*b
的和
之後第二行:
*b=*a -*b=A+B-*b=A+B-B=A,*b
的值變成了原始的
*a
的值
A
最後第三行:
*a=*a - *b=A+B-*b=A+B-A=B,*a
的值則變成了最初的
*b
的值
B
互換完成。
這種東西一般人是自己不會發現的,因為這是完全的數學的魅力。而我們要做的就是學會去欣賞這種細微的奧妙,取巧的魅力。
3、 void swap_3 (int * , int *);//詭異型
void swap_3 (int * , int *);//詭異型
void swap_3 (int * a, int *b)
{
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
//補充(time:年月日::):
//需要注意的是當:a == b即,兩個變量的位址相同時,該方法有bug:
//* a ^ *b == *a ^ *a == *b ^ *b ==
//因為a,b相同,則經一次運算:*a == *b ==
//後面無論是多少次異或結果都是:*a ^ *b =
為什麼說是詭異型呢,因為我們發現這段代碼指派等号右端始終隻有一種運算,那就是
*a ^ *b
,而就是這一種運算便解決了互換的問題,真是玄之又玄。
首先
^
是異或運算符,在邏輯運算中法則為:如果
a、b
兩個值不相同,則異或結果為1。如果
a、b
兩個值相同,異或結果為0。
0^0 = 0;
1^1 = 0;
0^1 = 1^0 = 1;
a ^ a = 0;
a ^ 0 = a;
a ^ b = b ^ a;
a ^b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
d = a ^ b ^ c 可以推出 a = d ^b ^ c;
a ^ b ^ a = b.等
那麼,讓我們來分析一下:
假設:
*a = A;*b =B;
第一行:
*a = *a ^ *b = A^B;
第二行:
*b = *a ^ *b = A^B^B = A^0 = A;
第三行:
*a = *a ^ *b = A^B^A = A^A^B = 0^B = B;
經過一系列的邏輯運算,最終實作了互換的效果。這點便展現出了邏輯運算的奧妙與魅力。也是非常的有趣而且有點繞,一眼看不出來,自己也很難想出這種代碼,那就繼續欣賞(受虐→_→)吧。
4、 void swap_4 (void * a, void *b, size_t size);//泛型
void swap_4 (void * a, void *b, size_t size);//泛型
swap_4 ()
是對于
swap_1()
的拓展,可以互換非整型變量,但是比較的兩個變量必須是同種類型。我自己現在也有些是不能夠完全了解的,因為牽扯泛型的問題以及一些對于自己來說還不常用及不常見的問題。而且在網上很難找到對該代碼的詳細解釋。代碼如下:
void swap_2 (void * a, void *b, size_t size)
{
unsigned char * p = (unsigned char *)a;//強制類型轉換
unsigned char * q = (unsigned char *)b;//強制類型轉換
unsigned char medium;
while(size--)
{
medium = *p;
*p = *q;
*q = medium;
p++;
q++;
}
}
調用時為:
swap_4(&a,&b,sizeof(char));//char類型互換
swap_4(&a,&b,sizeof(int));//int型互換
swap_4(&a,&b,sizeof(double));//double型互換
首先形參部分
(void * a, void *b, size_t size)
,以前沒有接觸過,經過查找資料之後,才有所了解:其中
void
是”無類型”,則
void *
為”無類型指針”,
void *
可以指向任何類型的資料,是以可以發送
char、int、float、double
等類型的位址。
對于
void*
的使用可以參考void與void*詳解
而
size_t
是一個變量類型,存儲的便是
sizeof()
傳回的值。對于該代碼的實作我将結合下圖來說明(畫圖前我不明白
while
循環到底是怎麼實作不同類型可以實作調換的,畫完圖後我突然自己明白了:
調換之前:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiN5UDNycjM5EDOxUDM2EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
調換之後:
為什麼要對
a,b
強制類型轉換呢?為什麼轉換為
unsigned char *
類型呢?
因為不知道要互換的
a,b
是什麼類型,是以要以最小記憶體開始互換,如圖中以int型為例,假設存儲的資料分别為:
1111 1111 1111 1111 1111 1111 1111 1111
0000 0000 0000 0000 0000 0000 0000 0000
a和b現在記憶體隻有第一個位元組,p和q分别存儲了a和b的位址,對第一個位元組的内容先進行調換。由于
size=sizeof(int)=4
(32位機),
while
循環會執行四次,每執行一次
size--,size=0
時退出循環,
p++
和
q++
使得此操作對
int
的四個位元組的内容分别進行了互換。最終實作整體的互換效果。
對于
char
型
while
循環隻實作一次,而
double
循環執行8次即可實作整體互換。