嵌入式學習筆記：數據結構知識點大集合
時間：2018-09-10 來源：未知
數據結構學習很容易，想要容易學，那你就需要掌握好下面這些基礎知識，都是學霸總結的
數據結構的定義 ：數據元素間的相互關系
(DS)
數據(Data)定義 ：即信息的載體(可以輸入計算器且能被計算機識別，存儲 和處理的符號總稱)
數據元素定義 ：數據的基本元素(即記錄)(若干基本項組(字段、數據結構)成)
數據類型定義 ：對元素取值范圍與運算的限定
數據存儲結構 ：
順序存儲 --將數據結構中的各元素按照其邏輯順序存放在存儲器 的一片連續(xù)的存儲空間中
鏈式存儲 --將數據結構中的各元素分布在存儲器不同點，用地址或 鏈指針把他們聯(lián)系起來的存儲結構
索引存儲 --在數據存儲的同時建立一個附加索引表，：索引存儲結構=數據文件+索引表
散列存儲 --根據數據元素的關鍵字key計算存儲地址然后數據元素按地址存放，的這種存儲結構
p126頁
數據結構類型
數據結構關系：
物理關系：順序關系、鏈式關系
運算關系：增(加)，刪(除)，改(修改)，查(詢)，排(序)
邏輯關系：
(結構)
集合 ： 數據元素間除同屬一集合無其他關系
線性： 線性(關系) ：一對一(如線性表、棧、隊列)
非線性： 層次關系(樹狀結構) ：一對多
網狀關系(圖狀結構) ：多對多
算法特性： (1)有窮性---算法執(zhí)行的步驟或規(guī)則是有限的
(2)確定性---每個計算步驟無二義性
(3)可行性---每個計算步驟都能在有限時間內完成
(4)輸入---算法有一個或多個輸入
(5)輸出---算法有一個或多個輸出 p128頁
評判算法好(壞)： 消耗時間少 、存儲空間少，
易(理解 編程 調試 和維護)的程度，
問題規(guī)模(小)：(輸入數據量的大小，用n表示)
算法消耗的時間復雜度 T(N)：(算法消耗的時間)
算法消耗的空間復雜度 D(N)：(算法消耗的空間)
語句頻度： 可執(zhí)行語句在算法(或程序)中重復執(zhí)行的次數
(一條語句的時間復雜度=語句平度 *消耗時間) p129頁
算法與程序的聯(lián)系與區(qū)別：
共同點：二者皆為完成某個任務，或解決某個問題而編制的規(guī)則(或語句)的 有序集合
區(qū)別 ： 一，算法與計算機無關，但程序依賴于具體的計算機語言
二，算法必須有窮而程序可能無窮
三，算法可忽略一些語法細節(jié)問題，重點放在解決問題的思路上， 但程序必須嚴格按相應的語言工具的語法算法換成程序后才能在計算機上運行。
線性表： 是信息表的一種形式，數據元素間滿足線性關系(或線性結構)
非空線性表的特征：
a0是表頭無前驅
a(n-1)是表尾無后繼
其他每個元素有且僅一個直接前驅a(i-1)和直接后繼a(i+1)
(當關系表長n<=1時，關系集R為空)
創(chuàng)建Makefile 文件
test:main.c seqlist.c
gcc main.c seqlist.c -o test
創(chuàng)建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
創(chuàng)建.c主程序文件
#include "seqlist.h"
#include
#include
#include
seqlist *create_list() //創(chuàng)建空表
{
seqlist *l; //創(chuàng)建鏈表指針
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");
}
創(chuàng)建主函數調用
#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);
}
