嵌入式學(xue)習筆(bi)記(ji)：數據(ju)結構知識點大集合
時間：2018-09-10 來(lai)源：未知(zhi)
數據結(jie)構學(xue)習很容(rong)易，想要容(rong)易學(xue)，那(nei)你就(jiu)需要掌握(wo)好下面(mian)這些基礎知識，都是學(xue)霸總結(jie)的
數(shu)據結構的定義 ：數(shu)據元素(su)間的相互關系
(DS)
數(shu)據(ju)(Data)定義(yi) ：即(ji)信(xin)息的(de)載體(可以(yi)輸入計算(suan)器且能被計算(suan)機(ji)識(shi)別，存儲 和處理的(de)符號總稱)
數(shu)據(ju)元素定義 ：數(shu)據(ju)的基(ji)本(ben)元素(即記錄)(若干基(ji)本(ben)項組(字(zi)段、數(shu)據(ju)結構)成)
數據類型定義 ：對(dui)元素取值(zhi)范圍與運算的限定
數(shu)據存儲結構 ：
順序存儲 --將數據結構中的(de)各元素(su)按照其邏輯(ji)順序存放(fang)在存儲器(qi) 的(de)一片連(lian)續(xu)的(de)存儲空間中
鏈式(shi)存(cun)儲 --將數據結(jie)構(gou)中的各元素分布在存(cun)儲器不同點，用地(di)址或(huo) 鏈指針(zhen)把他們聯系起來的存(cun)儲結(jie)構(gou)
索(suo)引存(cun)儲(chu)(chu) --在數(shu)據存(cun)儲(chu)(chu)的同時(shi)建立一個(ge)附加索(suo)引表，：索(suo)引存(cun)儲(chu)(chu)結構=數(shu)據文件(jian)+索(suo)引表
散(san)列存(cun)儲 --根據數(shu)據元素的關鍵字key計算存(cun)儲地(di)址(zhi)(zhi)然后數(shu)據元素按地(di)址(zhi)(zhi)存(cun)放(fang)，的這種存(cun)儲結構(gou)
p126頁
數據結構(gou)類型(xing)
數據(ju)結構關系：
物理關系(xi)：順序關系(xi)、鏈式關系(xi)
運算關系(xi)：增(加(jia))，刪(除)，改(gai)(修改(gai))，查(詢(xun))，排(序)
邏輯關系：
(結構)
集合 ： 數據元素間除(chu)同屬一(yi)集合無其他關系
線性(xing)： 線性(xing)(關系) ：一(yi)(yi)對一(yi)(yi)(如線性(xing)表(biao)、棧、隊(dui)列)
非線性(xing)： 層次關系(樹狀結(jie)構) ：一對多(duo)
網狀關系(圖狀結(jie)構) ：多對多
算(suan)法(fa)特(te)性(xing)： (1)有窮性(xing)---算(suan)法(fa)執行的(de)步驟或(huo)規則是(shi)有限的(de)
(2)確定性(xing)---每個計(ji)算步(bu)驟(zou)無二義性(xing)
(3)可(ke)行性(xing)---每(mei)個計(ji)算步驟都能在有限(xian)時(shi)間內完成
(4)輸入---算法有一個或多個輸入
(5)輸出(chu)---算法有一(yi)個(ge)或多(duo)個(ge)輸出(chu) p128頁
評判(pan)算(suan)法好(壞)： 消耗時間少(shao) 、存(cun)儲空(kong)間少(shao)，
易(理解(jie) 編(bian)程 調試 和(he)維護)的程度(du)，
問題規模(小(xiao))：(輸入(ru)數據量的大小(xiao)，用n表示)
算(suan)(suan)法(fa)消(xiao)耗的時間(jian)復雜度 T(N)：(算(suan)(suan)法(fa)消(xiao)耗的時間(jian))
算法(fa)消(xiao)耗的(de)空間復雜度 D(N)：(算法(fa)消(xiao)耗的(de)空間)
語(yu)句頻度： 可執行語(yu)句在算法(或程序(xu))中重復執行的次數
(一條語句(ju)的(de)時(shi)間(jian)復雜度(du)=語句(ju)平(ping)度(du) *消(xiao)耗時(shi)間(jian)) p129頁
算法與程序的聯系與區別：
共同點：二(er)者皆為(wei)完成某個任(ren)務，或(huo)解決某個問題而(er)編(bian)制的(de)規則(或(huo)語句(ju))的(de) 有序(xu)集(ji)合
區(qu)別 ： 一，算(suan)法與(yu)計(ji)算(suan)機無(wu)關，但程序依賴于具體的計(ji)算(suan)機語言
二，算法必須(xu)有窮(qiong)而程序(xu)可能無(wu)窮(qiong)
三，算法可忽略一些(xie)語(yu)法細節問(wen)題(ti)，重點放在解(jie)決問(wen)題(ti)的思(si)路上(shang)， 但(dan)程序必須嚴(yan)格按相應的語(yu)言(yan)工具的語(yu)法算法換(huan)成程序后才能(neng)在計算機上(shang)運行。
線性(xing)表(biao)： 是信息表(biao)的(de)一(yi)種形式，數據(ju)元素間滿足線性(xing)關系(xi)(或線性(xing)結構)
非空線性表的特征(zheng)：
a0是表頭無前(qian)驅
a(n-1)是(shi)表尾無后(hou)繼
其他(ta)每個(ge)元素有(you)且僅(jin)一個(ge)直(zhi)接前(qian)驅a(i-1)和直(zhi)接后繼(ji)a(i+1)
(當關系表(biao)長n<=1時(shi)，關系集R為空)
創(chuang)建Makefile 文件
test:main.c seqlist.c
gcc main.c seqlist.c -o test
創建shell 文件(jian)
#ifndef SEQLIST_H
#define SEQLIST_H
#include
#include
#include
typedef int data_t;
#define size 15
typedef struct node{
data_t data[size];
int last;
}seqlist;
//增,刪,改,查,排序等
seqlist *create_list();
int insert_list(seqlist *l, int pos, data_t value);
int delte_list(seqlist *l, int pos);
int change_list(seqlist *l, int pos, data_t value);
data_t select_list(seqlist *l, int pos);
void printf_list(seqlist *l);
#endif
創建.c主程序文件
#include "seqlist.h"
#include
#include
#include
seqlist *create_list() //創建空表
{
seqlist *l; //創建(jian)鏈表(biao)指(zhi)針(zhen)
l = (seqlist *)malloc(sizeof(seqlist)); //開(kai)辟(pi)malloc空間并強轉
if (l == NULL){ //判(pan)斷是否為(wei)空，
return NULL;
}
memset(l->data, 0, 4*size); //把所有(you)空(kong)間(jian)初始化為0，memset初始化的意思
l->last = -1;
return l;
}
int insert_list(seqlist *l, int pos, data_t value)//插入數據(ju)
{
if (l == NULL) //首先判斷是否為(wei)空(kong)
return -1;
if (pos < 0 || pos > l->last + 1 || (l->last + 1 == size)) //判斷插入(ru)位(wei)置是否有效，無效返回-1
return -1;
int i;
for(i = l->last; i >= pos; i--)
l->data[i+1] = l->data[i];
l->data[pos] = value;
l->last = l->last + 1;
return 0;
}
int delte_list(seqlist *l, int pos)//刪除(chu)某一地址下(xia)的數據
{
if(l==NULL || l->last == -1 )//同樣(yang)判斷(duan)刪除位置(zhi)是否(fou)有效(xiao)
return -1;
if(pos < 0 || pos>l->last+1)
return -1;
int i;
for(i=pos; ilast; i++)
l->data[i] = l->data[i+1];
l->last--;
return 0;}
int change_list(seqlist *l, int pos, data_t value)//更改
{if (l == NULL)
return -1;
if (pos < 0 || pos > l->last + 1 )
return -1;
int i;
for(i = pos; i < l->last; i++)
l->data[pos] = value;
return 0;
}
data_t select_list(seqlist *l, int pos)//查詢
{if (l == NULL)
return -1;
else
return l->data[pos];
}
void printf_list(seqlist *l)//輸出函數
{
int i = 0;
printf("seqlist : l->last = %d\n", l->last);
while(i <= l->last){
printf("----%d ", l->data[i]);
i++;
}
printf("\n");
}
創建主函數(shu)調用
#include "seqlist.h"
#include
#include
#include
void main()
{
seqlist *l = create_list();
if (l == NULL)
printf("create list failed\n");
insert_list(l, 0, 2);
insert_list(l, 1, 3);
insert_list(l, 2, 5);
insert_list(l, 3, 7);
insert_list(l, 4, 9);
printf_list(l);
insert_list(l, 2, 13);
printf_list(l);
delte_list(l,2);
printf_list(l);
change_list(l,3,666);
printf_list(l);
select_list(l,3);
printf_list(l);
}
