數據結構入門
- 2019 年 11 月 3 日
- 筆記
定義：我們如何把現實中大量而複雜的問題以特定的數據類型和特定的存儲結構保存到主記憶體器中(記憶體)，以及在此基礎上為實現某個功能(比如查找某個元素，刪除某個元素，對所有元素進行排序)而執行的相應操作，這個相應的操作也叫演算法
數據結構 = 個體 + 個體的關係
演算法 = 對存儲結構的操作
演算法：解題的方法和步驟
衡量演算法的標準：
- 時間複雜度：大概程式執行要執行的次數，而非執行的時間
- 空間複雜度：演算法執行過程中大概所佔用的最大記憶體
- 難易程度
- 建壯性
一、指針
地址：記憶體單元的編號，從0開始的非負整數
指針：指針就是地址，指針變數是存放記憶體單元地址的變數，指針的本質是一個操作受限的非負整數
分類：
- 基本類型指針(重點看注釋)
#include <stdio.h> int main(void) { // p是一個變數名字，int * 表示p變數只能存儲int類型變數的地址 int *p; int i = 10; int j; p = &i; // p保存了i的地址，p指向i // 修改p的值不影響i的值，修改i的值不影響p的值 // *p等於i j = *p; // 等價於 j = i printf("%dn", *p); printf("%dn", j); return 0; }- 指針與函數
#include <stdio.h> // 不是定義了一個名字叫做 *p的形參，而是定義了一個形參，該形參的名字p，它的類型是int * void f(int *p) { *p = 100; } int main(void) { int i = 9; int *p = &i; f(p); printf("%dn", i ); return 0; }- 指針與數組(重點看注釋)
#include <stdio.h> void show_array(int *p , int len) { // p[0] == *p p[0] = -1; // p[i]就是主函數a[i] int i = 0; for (i = 0; i < len; i++) { printf("%dn",p[i] ); } } int main(void) { /* 一唯數組名是個指針常量，它存放的是一唯數組第一個元素的地址， 它的值不能改變，一唯數組名指向的是數組的第一個元素，也就是 a執向a[0] 下標和指針的關係 a[i] <==> *(a+i) */ int a[5] = {1,2.3,4,5,}; // a等價於&a[0] , &a[0]本身就是int * 類型 show_array(a,5); printf("%dn", a[0]); return 0; }所有的指針變數只佔4個位元組，用第一個位元組的地址表示整個變數的地址
#include <stdio.h> int main(void) { double *p; double x = 99.9; // x佔8個位元組，1位元組是8位，1位元組一個地址 ，p裡面存放了首地址 p = &x; double arr[3] = {1.1,2.2,3.3,}; double *q; double *q1; q = &arr[0]; printf("%pn", q); // %p實際就是以十六進位輸出 q1 = &arr[1]; printf("%pn", q1); // 相差了8個位元組 return 0; }二、如何通過函數修改實參的值
#include <stdio.h> void f(int **q); int main(int argc, char const *argv[]) { int i = 9; int *p = &i; // int *p , p = &i; printf("%pn",p ); f(&p); printf("%pn",p ); return 0; } void f(int **q) { *q = (int*)0XFFFFF; }這樣寫是不安全的，但是這個理是這樣的，不是修改指針的很簡單，
#include <stdio.h> void f(int *p); int main(void) { int i =10; f(&i); printf("%dn", i); return 0; } void f(int *p) { *p = 20; }三、結構體
為什麼會出現結構體
為了表示一些複雜的數據，而普通的基本類型變數無法滿足要求
什麼叫結構體
結構體是用戶根據實際需要，自己定義的複合數據類型
如何使用結構體
#include <stdio.h> #include <string.h> struct Student { int sid; char name[200]; int age; }; // 分號不能省 int main(void) { // 第一種方式，但是這樣很麻煩 struct Student st = {10 , "張三" ,20}; printf("%d %s %dn", st.sid , st.name , st.age); // 字元串不能直接賦值，必須調用相應的函數 st.sid = 20; strcpy(st.name , "李四"); st.age = 21; printf("%d %s %dn", st.sid , st.name , st.age); // 第二種方式，這個最常用 struct Student *pst; pst = &st; pst -> sid = 99; // pst->sid 等價於 (*pst).sid 等價於 st.sid return 0; }pst -> sid : pst所指向的結構體中變數中的sid這個成員
注意事項
- 結構體變數不能加減乘除，但是可以相互賦值
- 普通結構體變數和結構體指針變數作為函數傳參的問題
#include <stdio.h> #include <string.h> struct Student { int sid; char name[200]; int age; }; void f(struct Student * pst); void g(struct Student st); void g1(struct Student * pst); int main(void) { struct Student st; f(&st); //printf("%d %s %dn", st.sid , st.name , st.age); //g(st); g1(&st); return 0; } // 用於數據的輸入 void f(struct Student * pst) { (*pst).sid = 99; strcpy(pst -> name , "張三"); pst -> age = 30; } // 用於數據的輸出,但是這種方法費時間，不推薦 void g(struct Student st) { printf("%d %s %dn", st.sid , st.name , st.age); } // 用於數據的輸出，推薦使用這種方式 void g1(struct Student * pst) { printf("%d %s %dn", pst->sid , pst->name , pst->age); }四、動態記憶體的分配和釋放
重點看程式碼和注釋
#include <stdio.h> #include <stdlib.h> int main(void) { int a[5] = {3,9,5,6,2}; int len; printf("請輸入你需要的分配數組的長度：n"); scanf("%d" , &len); int * PArr = (int *)malloc(sizeof(int)*len); // *PArr = 3; //類似於a[0] = 3 // PArr[1] = 9; //類似於a[1] = 9 // printf("%d %dn", *PArr , PArr[1]); // 當然了，這個時候我們可以把pArr當作一個普通的數組來使用 int i; for (i = 0; i < len; ++i) { scanf("%d" , &PArr[i]); } int j; for (j = 0; j < len; ++j) { printf("%dn", PArr[j]); } free(PArr); // 把Parr所代表的動態分配的20個位元組記憶體釋放 return 0; }五、跨函數使用記憶體
重點看程式碼和注釋
#include <stdio.h> #include <stdlib.h> struct Student { int sid; int age; }; struct Student * CreateStudent(void); void ShowStudent(struct Student * ps); int main(void) { struct Student * ps; ps = CreateStudent(); ShowStudent(ps); return 0; } struct Student * CreateStudent(void) { // 開闢一個新空間，使用malloc函數，類型是我們想要的類型 struct Student * p = (struct Student * )malloc(sizeof(struct Student)); p->sid = 88; p->age = 99; return p; } void ShowStudent(struct Student * pst) { printf("%d %dn", pst->sid , pst->age); }
