2018-12-27
數據結構定義:
我們如(rú)何把現實中大量而複雜的(de)問題以特定的(de)數據類型和(hé)特定的(de)存儲結構保存到主存儲器(內(nèi)存)中,以及在此基礎上為(wèi)實現某個功能(如(rú)元素的(de)CURD、排序等)而執行的(de)相應操作,
這個相應的(de)操作也叫算法。
數據結構 = 元素 + 元素的(de)關系
算法 = 對數據結構的(de)操作
算法:
算法就是:解決問題的(de)方法和(hé)步驟
衡量算法有如(rú)下标準:
1.時間複雜度
程序要執行的(de)次數,并非執行時間
2.空間複雜度
算法執行過程中大概要占用的(de)最大內(nèi)存
3.難易程度(可(kě)讀性)
4.健壯性
地(dì)位:
數據結構處于軟件中核心的(de)地(dì)位。
如(rú)計算機內(nèi)存中棧和(hé)堆的(de)區别,不懂數據結構的(de)人可(kě)能會認為(wèi)內(nèi)存就是分兩大部分,一(yī)塊叫棧,一(yī)塊叫堆,顯然這是非常膚淺且不正确的(de)結論。
實際上如(rú)果一(yī)塊內(nèi)存是以壓棧出棧的(de)方式分配的(de)內(nèi)存,那麽這塊內(nèi)存就叫棧內(nèi)存,如(rú)果是以堆排序的(de)方式分配的(de)內(nèi)存,那麽這塊內(nèi)存就叫堆內(nèi)存,其最根本的(de)區别還是其內(nèi)存分配
算法的(de)不同。
例如(rú),函數的(de)調用方式也是通過壓棧出棧的(de)方式來調用的(de),或者操作系統中多線程操作有隊列的(de)概念,隊列用于保證多線程的(de)操作順序,這也是數據結構裏面的(de)內(nèi)容、或者計算機
編譯原理(lǐ)裏面有語法樹的(de)概念,這實際上就是數據結構裏面的(de)樹,比如(rú)軟件工程、數據庫之類都有數據結構的(de)影子(zǐ)。
特點:
數據結構修煉的(de)是內(nèi)功,并不能直接立竿見影的(de)可(kě)以解決現實問題,但是有了這門內(nèi)功會在其他方面的(de)學(xué)習中對你大有益處。
學(xué)習數據結構應該具備如(rú)下知識:
指針
結構體
動态內(nèi)存的(de)分配和(hé)釋放
跨函數使用內(nèi)存
本小節主要介紹學(xué)習數據結構應該有的(de)基礎,并對相關知識稍作講解。
指針
指針是 C語言 的(de)靈魂,重要性不需多言。
指針定義
地(dì)址:
地(dì)址是內(nèi)存單元的(de)編号
其編号是從 0 開始的(de)非負整數
範圍: 0 -- 0xFFFFFFFF (2^32 - 1) 注:此指x86平台,x64平台下最大內(nèi)存地(dì)址為(wèi) (2^64 - 1)
指針就是地(dì)址,地(dì)址就是指針。
指針變量是存放內(nèi)存單元地(dì)址的(de)變量,它內(nèi)部保存的(de)值是對應的(de)地(dì)址,地(dì)址就是內(nèi)存單元的(de)編号(如(rú)內(nèi)存地(dì)址值:0xffc0)。
指針的(de)本質是一(yī)個操作受限的(de)非負整數
在計算機系統中,CPU 可(kě)以直接操作內(nèi)存,關于 CPU 對內(nèi)存的(de)操作與控制原理(lǐ)可(kě)以簡單理(lǐ)解如(rú)下圖
地(dì)址線 : 确定操作哪個地(dì)址單元
控制線 : 控制該數據單元的(de)讀寫屬性
數據線 : 傳輸 CPU 和(hé)內(nèi)存之間的(de)數據
1.基本類型的(de)指針
int i = 10; // 定義一(yī)個 整形變量 i 初始值 10 int *p = i; // 定義一(yī)個 整形的(de)指針變量 p , 變量 p 指向 i 的(de)地(dì)址 int *p; // 這兩行等價于上面一(yī)行 p = &i; 1. p 存放了 i 的(de)地(dì)址,我們就可(kě)以說“ p 指向了 i” ,但 p 和(hé) i 是兩個不同的(de)變量,修改一(yī)方不會影響另一(yī)個的(de)值。 2. *p 等價于 i ,i 等價于 *p;兩者是一(yī)塊內(nèi)存空間,裏面的(de)值一(yī)變具變。
2.指針和(hé)函數
// 修改外部實參的(de)值 void func(int * p) { *p = 100; // 函數內(nèi)修改外部變量的(de)值 } // 修改外部實參的(de)值,二級指針的(de)值 void func2(int ** p) { *p = 100; // 函數內(nèi)修改外部變量的(de)值 ,這裏實際修改的(de)是指針的(de)內(nèi)部的(de)地(dì)址,這裏直接自(zì)己修改并不嚴謹也不安全,隻是為(wèi)了表達意思 } int main(void) { // 修改外部實參 int i = 10; func(&i); printf("i = %d",i); // 修改外部二級指針 int *p = i; // 等價于 int *p; p = &i; func(&p); printf("i = %d",i); return 0; } // 通過函數調用,改變函數外部變量(實參)的(de)值
3.指針和(hé)數組
【指針】 和(hé) 【一(yī)維數組】
int a[5] = {1,2,3,4,5 }; a[3] == *(a + 3) // 等價于 a[3] == *(3 + a) == 3[a]; // 3[a] 這種寫法隻是不常用,從原理(lǐ)上來說是正确的(de) a 等價于 a[0]; // a 是數組中第一(yī)個元素,每個元素占用內(nèi)存單位長(cháng)度相同, // a[i] 中的(de) i 實際代表的(de)是單位長(cháng)度的(de)倍數
一(yī)維數組名是個指針常量(它的(de)值不可(kě)變)
它存放的(de)是該一(yī)維數組的(de)第一(yī)個元素的(de)地(dì)址(一(yī)維數組名指向其第一(yī)個元素)
(1)、 a[i] 等價于 *(a + i)
(2)、假設指針變量的(de)名字為(wèi) p,
則 p + i 的(de)值為(wèi) p + i * (p 所指向的(de)變量所占字節數)
(3)、每個下标表示的(de)是第 i+1 個元素,根據元素類型分配的(de)字節長(cháng)度不同(int 類型4個字節),每個字節都有對應的(de)內(nèi)存地(dì)址編号,指針變量 p 保存的(de)是該元素首字節的(de)地(dì)址。
指針變量不能相加、相乘、相除
如(rú)果兩指針變量屬于同一(yī)數組,則可(kě)以相減
指針變量可(kě)以加減一(yī)個整數,前提是最終結果不能超過指針最大可(kě)訪問範圍
// 指針變量的(de)運算 p + i 的(de)值是 p + i*(所指向的(de)變量所占字節數) p - i 的(de)值是 p - i*(所指向的(de)變量所占字節數) p++ 等價于 p + 1 p-- 等價于 p - 1 // 下面是一(yī)個通過函數修改數組內(nèi)部元素 void my_Array(int *a , int length) { for(int i = 0; i < length; i++) { *a[i]++; // 給每個元素加 1 } } int main(void){ int a[5] = {1,2,3,4,5}; my_Array(a , 5); // 調用 }
為(wèi)什麽會出現結構體、
為(wèi)了表示一(yī)些複雜的(de)數據,而普通的(de)基本數據無法滿足要求.
什麽叫結構體
結構體是用戶根據實際需要,自(zì)己定義的(de)複合數據類型
// 如(rú)學(xué)生類型 struct Student{ int age; char * name; // name 不同,賦值方法不同 char name2[100]; // 這個隻能 strcpy(s.name2, "zhangwangdsd"); 字符串拷貝 double height; };
總結起來有兩種結構體的(de)使用方式:直接使用 && 通過指針使用
struct Student ss = {12,"xiaoyou",1.73,"xiaozhang"};
struct Student *pst = &ss;
ss.name ; 這裏直接操作結構體本身
pst -> name ; 這裏通過指針地(dì)址操作,更加節省空間
struct Student{ // 自(zì)定義結構體 int age; char * name; double height; char name2[100]; }; int main(void) { struct Student s = {12,"xiaoyou",1.73,"xiaozhang"}; // 直接使用 printf(" age = %d name = %s height = %.2f ",s.age,s.name,s.height); s.age = 21; s.name = "xiaozhu"; strcpy(s.name2, "zhangwangdsd"); // 字符串拷貝 s.height = 1.70; printf(" age = %d name = %s height = %.2f %s ",s.age,s.name,s.height,s.name2); // 以指針的(de)方式使用 struct Student *pst = &ss; pst -> name = "my new name"; printf(" name = %s ",pst->name); printf(" name = %s ",(*pst)->name); // pst -> name 等價于 (*pst).name , // 而(*pst).name 又等價于 ss.name // 所以 pst -> name 等價于 ss.name return 0; }
結構體變量的(de)類型為(wèi): struct Student
結構體變量不能加減乘除,但是能夠相互賦值
普通結構體變量和(hé)結構體指針變量作為(wèi)函數傳參的(de)問題
typedef struct Student{ // 結構體定義 int age; char * name; char name2[100]; double height; }myStudent; // 直接傳遞整個結構體數據,耗時 && 浪費內(nèi)存空間 void func(struct Student st); // 直接傳遞 隻占用 4 byte 的(de)指針,省時效率也高(gāo) <推薦用法> void func2(struct Student * pst); int main(void){ myStudent ss = {12,"xiaoyou",1.73}; func(ss); func2(&ss); return 0; } void func(struct Student st){ printf("age = %d name = %s",st.age,st.name); } void func2(struct Student * pst){ printf("age = %d name = %s",(*pst).age,(*pst).name); printf("age = %d name = %s",pst->age,pst->name); }
平時直接創建數組的(de)寫法都是靜态創建,創建完畢之後在整個程序的(de)運行過程中,會固定占用對應的(de)內(nèi)存,不僅會造成內(nèi)存空間浪費,還無法動态添加元素,所以局限性很大,而
程序中我們為(wèi)了避免這種情況,應該使用動态的(de)方式創建和(hé)銷毀數組。
// 靜态創建數組 int a[5] = {1,2,3,4,5};
動态構造一(yī)個 int 型的(de)一(yī)維數組。
int *p = (int *)malloc(int length); 1. void * malloc(size_t __size) 函數,隻有一(yī)個 int 類型的(de)形參,表示要求系統分配的(de)字節數 2. malloc 函數的(de)功能是請求系統 length 個字節的(de)內(nèi)存空間,如(rú)果請求完成則返回的(de)是第一(yī)個字節的(de)地(dì)址, 如(rú)果請求不成功,則返回NULL 3. malloc 函數能且隻能返回第一(yī)個字節的(de)地(dì)址,所以我們需要把沒有實際意義的(de)第一(yī)個字節地(dì)址(幹地(dì)址)轉化為(wèi)一(yī)個有實際意義的(de)地(dì)址, 所以 malloc 前面必須加(數據類型 *),表示把這個無意義的(de)地(dì)址轉化為(wèi)對應類型的(de)地(dì)址 實例: int *p = (int *)malloc(50); 表示将系統分配的(de) 50 個字節的(de)第一(yī)個字節的(de)地(dì)址轉化為(wèi) int 類型的(de)地(dì)址,準确的(de)說是轉化為(wèi) 4 個一(yī)組的(de)地(dì)址的(de)首地(dì)址, 這樣 p 就指向了第一(yī)個四個字節··· p+i 就指向了第 i+1 個四個字節,p[0],p[i]也就分别是第一(yī)個,第i+1個元素。 double *p = (double *)malloc(80); 表示将系統分配的(de) 80 個字節的(de)第一(yī)個字節的(de)地(dì)址轉化為(wèi) double 類型的(de)地(dì)址,準确的(de)說是轉化為(wèi) 8 個一(yī)組的(de)地(dì)址的(de)首地(dì)址, 這樣 p 就指向了第一(yī)個八個字節··· p+i 就指向了第 i+1 個八個字節,p[0],p[i]也就分别是第一(yī)個,第i+1個元素。 4. free(p); 釋放 p 所指向的(de)內(nèi)存,而不是釋放 p 本身所占用的(de)內(nèi)存
代碼示例如(rú)下:
void test2(void) { int len; printf("請輸入你要動态創建的(de)數組長(cháng)度:"); scanf("%d",&len); int *pArr = (int *)malloc(len); // 動态創建數組 *pArr = 4; // 相當于 a[0] = 4; 這裏 pArr 就等于數組首地(dì)址,等于數組名 pArr[2] = 5; // 相當于 a[2] = 5; printf("pArr[0] = %d pArr[2] = %d ",pArr[0],pArr[2]); free(pArr); // 使用完畢,釋放對應的(de)數組空間 }
在函數內(nèi)部分配的(de)局部變量,在函數調用完成之後就會被系統回收,其內(nèi)存也會消失。但是程序中常常需要定義一(yī)塊內(nèi)存,當我們用完之後再會回收。如(rú) OC 語言中對象。所以需
要保存住分配的(de)內(nèi)存,應該用動态分配內(nèi)存,當用完之後再手動釋放。這也是C語言的(de)一(yī)個不足之處:內(nèi)存需要我們手動創建和(hé)手動釋放,這也是 OC 語言在開發 iOS 程序時候,
我們所講的(de)MRC。【蘋果也發現了這個不足,于 iOS 5 的(de)時候推出了ARC 】
下面是一(yī)個跨函數使用內(nèi)存的(de)例子(zǐ):
// 這個例子(zǐ)已經非常有面向對象的(de)味道(dào)了 typedef struct Student{ // 自(zì)定義 student 結構體 int age; char * name; }myStudent; myStudent * createStudent(void); // 創建 student void showStudent(myStudent *); // 輸出 student int main(void) { myStudent *p = createStudent(); // 創建 student showStudent(p); // 輸出 student return 0; } myStudent * createStudent(void) { myStudent *p = (myStudent *)malloc(sizeof(myStudent)); p->age = 20; p->name = "xiaoyou"; return p; } void showStudent(myStudent *p) { printf("student.age = %d student.name = %s ",p->age,p->name); }
本文主要講解了數據結構的(de)定義和(hé)簡介。
回顧了學(xué)習數據結構應該具備的(de)一(yī)些 C語言 的(de)基礎知識,如(rú)指針、結構體、和(hé)內(nèi)存等。
後面會繼續開始對數據結構的(de)講解。
上一(yī)篇:Linux 文件系統結構介紹
*請認真填寫需求,我們會在24小時內(nèi)與您取得聯系。