09.14 嵌入式學習筆記：數據結構知識點大集合

數據結構學習很容易，想要容易學，那你就需要掌握好下面這些基礎知識，都是學霸總結的

數據結構的定義 ：數據元素間的相互關係

(DS)

數據(Data)定義 ：即信息的載體(可以輸入計算器且能被計算機識別，存儲 和處理的符號總稱)

數據元素定義 ：數據的基本元素(即記錄)(若干基本項組(字段、數據結構)成)

數據類型定義 ：對元素取值範圍與運算的限定

數據存儲結構 ：

順序存儲 --將數據結構中的各元素按照其邏輯順序存放在存儲器 的一片連續的存儲空間中

鏈式存儲 --將數據結構中的各元素分佈在存儲器不同點，用地址或 鏈指針把他們聯繫起來的存儲結構

索引存儲 --在數據存儲的同時建立一個附加索引表，：索引存儲結構=數據文件+索引表

散列存儲 --根據數據元素的關鍵字key計算存儲地址然後數據元素按地址存放，的這種存儲結構

p126頁

數據結構類型

數據結構關係：

物理關係：順序關係、鏈式關係

運算關係：增(加)，刪(除)，改(修改)，查(詢)，排(序)

邏輯關係：

(結構)

集合 ： 數據元素間除同屬一集合無其他關係

線性： 線性(關係) ：一對一(如線性表、棧、隊列)

非線性： 層次關係(樹狀結構) ：一對多

網狀關係(圖狀結構) ：多對多

算法特性： (1)有窮性---算法執行的步驟或規則是有限的

(2)確定性---每個計算步驟無二義性

(3)可行性---每個計算步驟都能在有限時間內完成

(4)輸入---算法有一個或多個輸入

(5)輸出---算法有一個或多個輸出 p128頁

評判算法好(壞)： 消耗時間少 、存儲空間少，

易(理解 編程 調試 和維護)的程度，

問題規模(小)：(輸入數據量的大小，用n表示)

算法消耗的時間複雜度 T(N)：(算法消耗的時間)

算法消耗的空間複雜度 D(N)：(算法消耗的空間)

語句頻度： 可執行語句在算法(或程序)中重複執行的次數

(一條語句的時間複雜度=語句平度 *消耗時間) p129頁

算法與程序的聯繫與區別：

共同點：二者皆為完成某個任務，或解決某個問題而編制的規則(或語句)的 有序集合

區別 ： 一，算法與計算機無關，但程序依賴於具體的計算機語言

二，算法必須有窮而程序可能無窮

三，算法可忽略一些語法細節問題，重點放在解決問題的思路上， 但程序必須嚴格按相應的語言工具的語法算法換成程序後才能在計算機上運行。

線性表： 是信息表的一種形式，數據元素間滿足線性關係(或線性結構)

非空線性表的特徵：

a0是表頭無前驅

a(n-1)是表尾無後繼

其他每個元素有且僅一個直接前驅a(i-1)和直接後繼a(i+1)

(當關系表長n<=1時，關係集R為空)

創建Makefile 文件

test:main.c seqlist.c

gcc main.c seqlist.c -o test

創建shell 文件

#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; //創建鏈表指針

l = (seqlist *)malloc(sizeof(seqlist)); //開闢malloc空間並強轉

if (l == NULL){ //判斷是否為空，

return NULL;

}

memset(l->data, 0, 4*size); //把所有空間初始化為0，memset初始化的意思

l->last = -1;

return l;

}

int insert_list(seqlist *l, int pos, data_t value)//插入數據

{

if (l == NULL) //首先判斷是否為空

return -1;

if (pos < 0 || pos > l->last + 1 || (l->last + 1 == size)) //判斷插入位置是否有效，無效返回-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)//刪除某一地址下的數據

{

if(l==NULL || l->last == -1 )//同樣判斷刪除位置是否有效

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");

}

創建主函數調用

#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);

}