一、資料結構概述
1.定義：
我們如何把現實中大量而復雜的問題，以特定的資料型別和特定的存盤結構保存到主存盤器（記憶體）中，以及在此基礎上為實作某個功能（比如查找某個元素，洗掉某個元素，對所有元素進行排序）而執行的相應操作，這個相應的操作也叫演算法，
資料結構 =個體的存盤 + 個體的關系存盤
演算法（狹義） = 對存盤資料的操作
2.演算法：解題的方法和步驟
2.1.衡量演算法好壞的標準：
2.1.1.時間復雜度：程式大概執行的次數，而非執行的時間
2.1.2.空間復雜度：演算法執行程序中大概所占用的最大記憶體
2.1.3.難易程度（編演算法最重要的）
2.1.4.健壯性
3.資料結構的地位：資料結構是軟體中最核心的課程
程式 = 資料的存盤 + 資料的操作 + 可以被計算機執行的語言
二、預備知識
1.指標
1.1.指標的重要性：指標是c語言的靈魂
1.2.有關指標概念的定義：
指標就是地址 地址就是指標，指標和地址是一個概念
指標變數 是存放記憶體單元地址的變數，所謂記憶體單元地址 即為記憶體單元編號，兩者是一個概念
指標的本質 是一個操作受限的非負整數/從0開始的非負整數
范圍：0 -- FFFFFFFF【4G-1】
1.2.1.關于記憶體和cpu的關系:
CPU能夠直接訪問的只有記憶體，記憶體是CPU唯一能夠訪問的大容量儲存器，記憶體的基本劃分單位是位元組，每個位元組有8位，每一位存放1個0或1個1，CPU和記憶體打交道的方式：地址線、控制線、資料線
記憶體可以看做很多小格子，如果是32位，編號從0到4G-1；
1.2.1.1.地址線 可以確定對哪一個單元編號進行操作,地址沒有編號，地址就是編號；重點是地址線，因為地址線是32位的，所以最大只能0到32-1；記憶體的編號不能重復，但是內容可以重復；
定義：地址就是記憶體單元的編號，單元編號是死的，不能改變，但是里面的內容是可以改變的；當一個程式運行完成，記憶體會被回收(回收和銷毀不是一個概念，作業系統會分配記憶體給程式，程式告訴操作系統，作業系統會把記憶體中的空間釋放出來，原始的資料(遺留的垃圾數字)不會銷毀，只是不能使用而已(c存在這個問題，但是java不會，java會自動釋放)，其中的變數會被清空，但是記憶體、單元編號依然存在;
1.2.1.2.控制線 用來確定是：讀、寫、只讀、只寫；
1.2.1.3.資料線 可以進行資料傳輸
2.指標的分類：
2.1.基本型別的指標
2.1.1基本概念
1 #include <stdio.h> 2 3 int main(void) 4 { 5 int * p; //該p變數只能存盤int型別的地址，不能存放一個整數 6 int i = 10; 7 int j; 8 9 // char ch = 'A'; 10 // p = &ch; //p只能存放int型別，不能存放char型別的'A',型別不一致，會報錯 11 // p = 10; //error p是個變數名字，表示只能存放int型變數地址，10是個整數，不是個地址； 12 // *p = i; //可以存放i,一定要如下理解才可以 13 // 1）將i的地址發送給p，意味著p是指向i的； 14 // 2）修改p、i的值，不會影響另外一個值，相互不會影響； 15 // 3）*p即為i變數本身，i跟*p可以在任何地方進行互換，i的值改了，*p的值也改了，i原來等于100，*p也就等于100，但是p不是i，i不是p； 16 p = &i; // 如果這一行被省略掉，會報錯； 17 // 第一步int * p;只是說p可以保存整型變數地址了，但p中并沒有保存真正的整型變數地址，所以我們不知道*p真正指向的是誰了 18 // 雖然p中沒有保存真正有效整型數字地址，但是p中還是可以有垃圾數字的，垃圾數字也有可能是某一個變數的地址，所以*p最終指向的是一個不確定的單元，*p不知道指向了哪里，造成了混亂，c語言中不允許這樣去寫 19 // 不能將一個不確定單元的值，賦給另外一個變數，這樣不合適，所以會報錯 20 *p = i; // 等價于i=i，不會出錯，但是沒有什么實際意義 21 j = *p; // 等價于j = i； 若注釋掉這一行，則j沒有賦值，c會自動賦予一個垃圾數字-2341343; 22 printf("i = %d, j= %d, *p = %d\n",i, j, *p); 23 24 //printf(); 25 return 0; 26 }View Code
小結：
1、如果一個指標變數（假定為p）存放了某個普通變數，那我們就可以說：“p指向了i”，但p與i是兩個變數；修改p的值不影響i的值，修改i的值不影響p的值
2、*p等價于I 或者說*p可以與i在任何地方互換
3、如果一個指標變數指向了某個普通變數，則*指標變數就完全等價于該普通變數
注意：
指標變數也是變數，只不過它存放的不能是記憶體單元的內容，只能存放記憶體單元的地址
普通變數前不能加*
常量和運算式前不能加&
如何通過被調函式，修改主調函式中普通變數的值
1.實參為相關變數的地址：&i
2.形參為以該變數的型別為型別的指標變數：*p
3.在被呼叫函式中通過*形參變數名的方式修改主函式:*p=100
2.2.指標和陣列的關系(一維陣列)
//Array_point_1.cpp # include <stdio.h> int main(void) { int a[5] = {1,2,3,4,5}; // 1)a中存放的不是1~5這5個數字,這5個數字是在a0到a4中存放的， // 2)陣列名a存放的是陣列的第一個元素的地址 // 3)它的值不能被改變 // 4)字母a即為一維陣列名，指向的是陣列的第一個元素,即a指向的是a0 // 5)a[3]和*(a+3)的關系:a[i] <<==>> *(a+i) 即陣列a[i]的寫法，等價于*(a+i) a[3] == *(3+a), 3[a] == *(a+3), 因a指向第一個元素a[0]，故a+3指向第四個元素a[3],則*(a+3)==a[3]; // 理論上指標比下標的速度快，但是可以忽略不計 //a[3] == *(3+a); printf("%p\n", a+1); printf("%p\n", a+2); printf("%p\n", a+3); //[Out]: //0019FF30 //0019FF34 //0019FF38 printf("%d\n", *a+3); // *a+3等價于 a[0]+3 = 4 //[Out]: // 4 return 0; }View Code
2.2.1.陣列名:a[*]中的a
一維陣列名 是個指標常量，它存放的是一維陣列第一個元素的地址a[0]，它的值不能被改變
一維陣列名指向的是 陣列的第一個元素
2.2.2.下標和指標的關系:a[i]等價于*(a+i)
a[i] <<==>> *(a+i)
假設指標變數的名字為p,則p+i的值是p+i*(p所指向的變數所占的位元組數)
2.2.3.指標變數的運算:
指標變數不能相加，不能相乘， 不能相除，如果兩指標變數屬于同一陣列，則可以相減
指標變數可以加減一整數，前提是最終結果不能超過指標
p+i 的值是p+i*(p所指向的變數所占的位元組數)
p- i 的值是p-i*(p所指向的變數所占的位元組數)
p++ <==> p+1 // 如果是int型，就是4位元組，double型，就是8位元組，但是都是指向的后一個元素
p-- <==> p-1
2.2.4.舉例:
如何通過被調函式修改主調函式中一維陣列的內容[如何界定]
兩個引數:1)存放陣列首元素的指標變數；2)存放陣列元素長度的整型變數
//Array_point_2.cpp # include <stdio.h> void Show_Array(int * p, int len) // a發送給了*p { // p[0] = -1; //p[0] == *p // p[2] = -1; //p[2] == *(p+2) == *(a+2) p[i]就是主函式的a[i] int i = 0; for (i=0; i<len; ++i) printf("%d\n", p[i]); } int main(void) { int a[5] = {1,2,3,4,5}; Show_Array(a, 5); // a等價于&a[0], &a[0]本身就是i // 通過寫一個陣列名，陣列長度，就可以確定一個陣列, // 要想通過一個函式，訪問另一個函式中的一個陣列，只需要知道這個陣列的首地址(陣列第一個元素地址)和長度， // 在另一個函式中就可以任意訪問、修改主函式a[5]的值 //[Out]:1 2 3 4 5 // printf("%d\n", a[2]); //[Out]: -1 // printf("%d\n", a[0]); //[Out]: -1 return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137165.html
標籤：其他
上一篇：淺談K-means聚類演算法
下一篇：圖論篇4——拓撲排序