資料與結構知識點總結
資料結構概述
定義我們如何把現實中大量而複雜的問題以特定的資料型別(比如:結構體等)和特定的儲存結構(比如:陣列,鍊錶等)儲存到主儲存器(記憶體)中,以及在此基礎上為實現某個功能(比如:
查詢某個元素,刪除某個元素,對所有元素進行排序)而執行的相應操作,這個相應的操作也叫演算法。
資料結構 = 個體 + 個體的關係
演算法 = 對儲存資料的操作
理解:如果資料都無法儲存的話,如何對資料進行操作呢?這時候資料的儲存
是乙個很關鍵的問題,那麼我們就要通過特定的資料型別和特定的儲存結構儲存到記憶體中。那麼問題來了:
問題1:儲存乙個省的人事之間的關係就不能用鍊錶或陣列來實現,
因為那樣不能得知哪個是老大老二,誰是領導和屬下,所以它無法體現,那麼怎麼辦呢?
利用用樹來實現,做乙個人事管理系統
問題2:如果是個交通圖,開闢很多站點,那麼我要在各站點間修路
每個站點相同,或者說給出兩個站點,系統能給出兩站點間
最短路徑,那又該怎麼辦呢?
利用圖來實現,使各個點之間相關聯
發現:把乙個實際的問題如何儲存在計算機裡面,這是第一步要解決的問題。如
果資料都不能儲存,那還怎麼對它操作呢?
那麼該如何儲存呢?
儲存個體(特定的資料型別);
儲存個體和個體之間的關係(特定的儲存結構)。
演算法:解題的方法和步驟
衡量演算法的標準(前2條最關鍵)
1、時間複雜度:大概程式要執行的次數,而非執行的時間
2、空間複雜度:演算法執行過程中大概所占用的最大記憶體
3、難易程度
4、健壯性:不能出現當給乙個非法的數整個程式就掛了
資料結構的地位:
資料結構是軟體中最核心的課程,幾乎所有的程式語言都能找到資料結構的影子
程式 = 資料的儲存 + 資料的操作 + 可被計算機執行的語言
預備知識
指標指標的重要性:c語言的靈魂
定義位址:記憶體單元的編號
從0開始的非負整數
範圍:0—0ffffffff【0-4g-1】
指標: 指標就是位址,位址就是指標
指標變數是專門存放記憶體單元位址的變數
指標本質是乙個操作受限的非負數
分類:1、基本型別的指標
eg:#include<>
int main(void)
int *p;//p是個變數名字,int *表示p只能存放整形變數的位址
int i=10;
int j;
p=&i;//p指向i
j=*p;//等價於j=i
printf("i=%d,j=%d,*p=%d\n",i,j,*p);//10
return 0;
eg:#include<>
void f(int *p)//int *是變數p的資料型別,形參的名字是p,而不是*p
p=100;
int main(void)
int i=9;
f(&i);//實參必須為相關變數的位址
printf("i=%d\n",i);//100
return 0;
2、指標和陣列的關係
eg:#include<>
int main(void)
;//a==&a[0],它是常量值不能變
a[3]=*(a+3);//a[i]==*(a+i)
printf("%p\n",a+1);//%p是輸出位址
printf("%p\n",a+2);
printf("%p\n",a+3);
printf("%d\n",*a+3);//等價於a[0]+3
return 0;
}eg:#include<>
void show_array(int *p,int len)
int main(void)
;show_array(a,5);//a等價於&a[0]
printf("%d\n",a[0]);//-1
return 0;
}/*-1 2 3 4 5 -1*/
eg:#include<>
int main(void)
;p=&x;//x佔8個位元組(8位),乙個位元組乙個位址
q=&arr[0];
printf("%p\n",q);//%p實際就是一16進製制輸出
q=&arr[1];
printf("%p\n",q);
return 0;
相差8個位元組
無論指標變數指向誰,它本身只佔4個位元組。
結構體 為什麼會出現結構體?
為了表示一些複雜的資料,而普通的基本型別無法滿足要求。
什麼叫結構體?
是使用者根據實際需要自己定義的復合資料型別。
如何使用結構體?
eg:#include<>
#include<>
struct student
;//分號不能省
int main(void)
;printf("%d %s %d\n",
第一種方式
struct student *pst;
pst=&st;
pst->sid=99;//第二種方式 pst->sid等價於(*pst).sid又等價於
"lisi";//error
strcpy("lisi");
printf("%d %s %d\n",
printf("%d %s %d\n",st);//error
return 0;
}注意事項:
結構體變數不能相加減,但可以相互賦值;
普通結構體變數和結構體指標變數作為函式傳參的問題。
eg:#include<>
#include<>
void f(struct student *pst);
void g(struct student *pst);
struct student
;//分號不能省
int main(void)
void f(struct student *pst)
void g(struct student *pst)//第二種方式
動態記憶體的分配和釋放
eg:#include<>
#include<>
int main(void)
;int len;
printf("請輸入需要分配的陣列的長度:len=");
scanf("%d",&len);
int *parr=(int *)malloc(sizeof(int)*len);//parr等價於a
parr=4; //類似於a[0]=4;
parr[1]=10;//類似於a[1]=10;
printf("%d %d\n",*parr,parr[1]);
free(parr);//把parr所代表的如20個位元組釋放
return 0;
}假設動態構造乙個int型一維陣列
eg:#include<>
#include<>
int main(void)
//釋放掉動態分配的陣列,動態的隨時都可以釋放,而
不需要程式終止再釋放
跨函式使用記憶體問題:
#include<>
#include<>
struct student
{ int sid;
int age;
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響,一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係,便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間,減少資...
資料結構個人總結
第一章複習題 一 選擇 1 計算機演算法指的是 1 它必須具備 c 2 這三個特性 b 1 a 計算方法 b.排序方法 c.解決問題的步驟序列 d.排程方法 2 a 可執行性 可移植性 可擴充性 b.可執行性 確定性 有窮性 c.確定性 有窮性 穩定性d.易讀性 穩定性 安全性 2 下面關於演算法說...
資料結構複習總結
第二章線性表 1.線性表的邏輯結構 資料元素之間存在一對一的線性關係 線性表的儲存結構 順序和鏈式 順序表和煉表。順序錶用一維陣列實現,鍊錶有單鏈表和雙鏈表及迴圈鍊錶。每種鍊錶含有指標的個數 2.掌握順序表和煉表的查詢,插入 刪除和排序操作的演算法時間複雜度。第三章棧和佇列 1.棧和佇列邏輯結構 資...