ID：技術讓夢想更偉大
作者:李肖遙
說真的，任何說起嵌入式軟件怎么入門啊？需要學些什么東西啊，我差不多一致的回答都是：軟件方面C語言和數(shù)據(jù)結構加上一些簡單常用的算法，這些需要學好。
借著自己的回顧學習，我也寫一些基礎的數(shù)據(jù)結構知識，多畫圖，少BB，與大家一起學習數(shù)據(jù)結構
數(shù)組作為一個順序儲存方式的數(shù)據(jù)結構，可是有大作為的，它的靈活使用為我們的程序設計帶來了大量的便利；
但是，但是，數(shù)組最大的缺點就是我們的插入和刪除時需要移動大量的元素，所以呢，大量的消耗時間，以及冗余度難以接受了。
以C語言數(shù)組插入一個元素為例，當我們需要在一個數(shù)組{1,2,3,4}的第1個元素后的位置插入一個’A’時，我們需要做的有：
將第1個元素后的整體元素后移，形成新的數(shù)組{1,2,2,3,4}
再將第2個元素位置的元素替換為我們所需要的元素’A’
最終形成我們的預期，這需要很多的操作喔。
上圖可以看出，使用數(shù)組都有這兩大缺點：
插入刪除操作所需要移動的元素很多，浪費算力。
必須為數(shù)組開足夠的空間，否則有溢出風險。
由于數(shù)組的這些缺點，自然而然的就產生鏈表的思想了。
鏈表通過不連續(xù)的儲存方式，自適應內存大小，以及指針的靈活使用，巧妙的簡化了上述的內容。
鏈表的基本思維是，利用結構體的設置，額外開辟出一份內存空間去作指針，它總是指向下一個結點，一個個結點通過NEXT指針相互串聯(lián)，就形成了鏈表。
其中DATA為自定義的數(shù)據(jù)類型，NEXT為指向下一個鏈表結點的指針，通過訪問NEXT，可以引導我們去訪問鏈表的下一個結點。
對于一連串的結點而言，就形成了鏈表如下圖：
上文所說的插入刪除操作只需要修改指針所指向的區(qū)域就可以了，不需要進行大量的數(shù)據(jù)移動操作。如下圖：
相比起數(shù)組，鏈表解決了數(shù)組不方便移動，插入，刪除元素的弊端，但相應的，鏈表付出了更加大的內存犧牲換來的這些功能的實現(xiàn)。
包含單鏈表，雙鏈表，循環(huán)單鏈表，實際應用中的功能不同，但實現(xiàn)方式都差不多。
單鏈表就像是美國男籃，一代一代往下傳；
雙鏈表像是中國男足，你傳球給我，我傳球給你，最終傳給了守門員；
循環(huán)鏈表就像是中國男籃，火炬從姚明傳給王治郅，王治郅傳給易建聯(lián)，現(xiàn)在易建聯(lián)傷了，又傳給了姚明
單鏈表是一種鏈式存取的數(shù)據(jù)結構，鏈表中的數(shù)據(jù)是以結點來表示的，每個結點由元素和指針構成。
元素表示數(shù)據(jù)元素的映象，就是存儲數(shù)據(jù)的存儲單元；指針指示出后繼元素存儲位置，就是連接每個結點的地址數(shù)據(jù)。
以結點的序列表示的線性表稱作線性鏈表，也就是單鏈表，單鏈表是鏈式存取的結構。
對于鏈表的每一個結點，我們使用結構體進行設計，其主要內容有：
其中，DATA數(shù)據(jù)元素，可以為你想要儲存的任何數(shù)據(jù)格式，可以是數(shù)組，可以是int，甚至可以是結構體（這就是傳說中的結構體套結構體）
NEXT為一個指針，其代表了一個可以指向的區(qū)域，通常是用來指向下一個結點，鏈表的尾部NEXT指向NULL（空），因為尾部沒有任何可以指向的空間了
故，對于一個單鏈表的結點定義，可以代碼描述成：
//定義結點類型
typedef struct Node {
int data; //數(shù)據(jù)類型，你可以把int型的data換成任意數(shù)據(jù)類型，包括結構體struct等復合類型
struct Node *next; //單鏈表的指針域
} Node,*LinkedList;
//Node表示結點的類型，LinkedList表示指向Node結點類型的指針類型
初始化主要完成以下工作：創(chuàng)建一個單鏈表的前置節(jié)點并向后逐步添加節(jié)點，一般指的是申請結點的空間，同時對一個結點賦空值(NULL)，其代碼可以表示為：
LinkedList listinit(){
Node *L;
L=(Node*)malloc(sizeof(Node)); //開辟空間
if(L==NULL){ //判斷是否開辟空間失敗，這一步很有必要
printf("申請空間失敗");
//exit(0); //開辟空間失敗可以考慮直接結束程序
}
L->next=NULL; //指針指向空
}
注意：一定要判斷是否開辟空間失敗，否則生產中由于未知的情況造成空間開辟失敗，仍然在繼續(xù)執(zhí)行代碼，后果將不堪設想啦，因此養(yǎng)成這樣的判斷是很有必要的。
利用指針指向下一個結點元素的方式進行逐個創(chuàng)建，使用頭插入法最終得到的結果是逆序的。如圖所示：
從一個空表開始，生成新結點，并將讀取到的數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭，即頭結點之后。
//頭插法建立單鏈表
LinkedList LinkedListCreatH() {
Node *L;
L = (Node *)malloc(sizeof(Node)); //申請頭結點空間
L->next = NULL; //初始化一個空鏈表
int x; //x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
while(scanf("%d",&x) != EOF) {
Node *p;
p = (Node *)malloc(sizeof(Node)); //申請新的結點
p->data = x; //結點數(shù)據(jù)域賦值
p->next = L->next; //將結點插入到表頭L-->|2|-->|1|-->NULL
L->next = p;
}
return L;
}
如圖所示為尾插入法的創(chuàng)建過程。
頭插法生成的鏈表中，結點的次序和輸入數(shù)據(jù)的順序不一致。若希望兩者次序一致，則需要尾插法。
該方法是將新結點逐個插入到當前鏈表的表尾上，為此必須增加一個尾指針r, 使其始終指向當前鏈表的尾結點，代碼如下：
//尾插法建立單鏈表
LinkedList LinkedListCreatT() {
Node *L;
L = (Node *)malloc(sizeof(Node)); //申請頭結點空間
L->next = NULL; //初始化一個空鏈表
Node *r;
r = L; //r始終指向終端結點，開始時指向頭結點
int x; //x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
while(scanf("%d",&x) != EOF) {
Node *p;
p = (Node *)malloc(sizeof(Node)); //申請新的結點
p->data = x; //結點數(shù)據(jù)域賦值
r->next = p; //將結點插入到表頭L-->|1|-->|2|-->NULL
r = p;
}
r->next = NULL;
return L;
}
從鏈表的頭開始，逐步向后進行每一個元素的訪問，稱為遍歷。
對于遍歷操作，我們可以衍生出很多常用的數(shù)據(jù)操作，比如查詢元素，修改元素，獲取元素個數(shù)，打印整個鏈表數(shù)據(jù)等等。
進行遍歷的思路極其簡單，只需要建立一個指向鏈表L的結點，然后沿著鏈表L逐個向后搜索即可，代碼如下：
//便利輸出單鏈表
void printList(LinkedList L){
Node *p=L->next;
int i=0;
while(p){
printf("第%d個元素的值為:%d\n",++i,p->data);
p=p->next;
}
}
對于元素修改操作，以下是代碼實現(xiàn)：
//鏈表內容的修改，在鏈表中修改值為x的元素變?yōu)闉閗。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
Node *p=L->next;
int i=0;
while(p){
if(p->data==x){
p->data=k;
}
p=p->next;
}
return L;
}
簡單的遍歷設計的函數(shù)只需要void無參即可，而當涉及到元素操作時，可以設計一個LinkedList類型的函數(shù)，使其返回一個操作后的新鏈表。
鏈表的插入操作主要分為查找到第i個位置，將該位置的next指針修改為指向我們新插入的結點，而新插入的結點next指針指向我們i+1個位置的結點。
其操作方式可以設置一個前驅結點，利用循環(huán)找到第i個位置，再進行插入。
如圖，在DATA1和DATA2數(shù)據(jù)結點之中插入一個NEW_DATA數(shù)據(jù)結點：
從原來的鏈表狀態(tài)
到新的鏈表狀態(tài)：
代碼實現(xiàn)如下：
//單鏈表的插入，在鏈表的第i個位置插入x的元素
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
Node *pre; //pre為前驅結點
pre = L;
int tempi = 0;
for (tempi = 1; tempi < i; tempi++) {
pre = pre->next; //查找第i個位置的前驅結點
}
Node *p; //插入的結點為p
p = (Node *)malloc(sizeof(Node));
p->data = x;
p->next = pre->next;
pre->next = p;
return L;
}
刪除元素要建立一個前驅結點和一個當前結點，當找到了我們需要刪除的數(shù)據(jù)時，直接使用前驅結點跳過要刪除的結點指向要刪除結點的后一個結點，再將原有的結點通過free函數(shù)釋放掉。如圖所示：
代碼如下：
//單鏈表的刪除，在鏈表中刪除值為x的元素
LinkedList LinkedListDelete(LinkedList L,int x) {
Node *p,*pre; //pre為前驅結點，p為查找的結點。
p = L->next;
while(p->data != x) { //查找值為x的元素
pre = p;
p = p->next;
}
pre->next = p->next; //刪除操作，將其前驅next指向其后繼。
free(p);
return L;
}
單鏈表是指結點中只有一個指向其后繼的指針，具有單向性，但是有時需要搜索大量數(shù)據(jù)的時候，就需要多次進行從頭開始的遍歷，這樣的搜索就不是很高效了。
在單鏈表的基礎上，對于每一個結點設計一個前驅結點，前驅結點與前一個結點相互連接，構成一個鏈表，就產生了雙向鏈表的概念了。
雙向鏈表可以簡稱為雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。
一個完整的雙向鏈表應該是頭結點的pre指針指為空，尾結點的next指針指向空，其余結點前后相鏈。
對于每一個結點而言，有：
其中，DATA表示數(shù)據(jù)，其可以是簡單的類型也可以是復雜的結構體；
pre代表的是前驅指針，它總是指向當前結點的前一個結點，如果當前結點是頭結點，則pre指針為空；
next代表的是后繼指針，它總是指向當前結點的下一個結點，如果當前結點是尾結點，則next指針為空
其代碼設計如下：
typedef struct line{
int data; //data
struct line *pre; //pre node
struct line *next; //next node
}line,*a;
//分別表示該結點的前驅(pre)，后繼(next)，以及當前數(shù)據(jù)(data)
創(chuàng)建雙向鏈表需要先創(chuàng)建頭結點，然后逐步的進行添加雙向鏈表的頭結點是有數(shù)據(jù)元素的，也就是頭結點的data域中是存有數(shù)據(jù)的，這與一般的單鏈表是不同的。
對于逐步添加數(shù)據(jù)，先開辟一段新的內存空間作為新的結點，為這個結點進行的data進行賦值，然后將已成鏈表的上一個結點的next指針指向自身，自身的pre指針指向上一個結點。
其代碼可以設計為：
//創(chuàng)建雙鏈表
line* initLine(line * head){
int number,pos=1,input_data;
//三個變量分別代表結點數(shù)量，當前位置，輸入的數(shù)據(jù)
printf("請輸入創(chuàng)建結點的大小\n");
scanf("%d",&number);
if(number<1){return NULL;} //輸入非法直接結束
//////頭結點創(chuàng)建///////
head=(line*)malloc(sizeof(line));
head->pre=NULL;
head->next=NULL;
printf("輸入第%d個數(shù)據(jù)\n",pos++);
scanf("%d",&input_data);
head->data=input_data;
line * list=head;
while (pos<=number) {
line * body=(line*)malloc(sizeof(line));
body->pre=NULL;
body->next=NULL;
printf("輸入第%d個數(shù)據(jù)\n",pos++);
scanf("%d",&input_data);
body->data=input_data;
list->next=body;
body->pre=list;
list=list->next;
}
return head;
}
雙向鏈表創(chuàng)建的過程可以分為：創(chuàng)建頭結點->創(chuàng)建一個新的結點->將頭結點和新結點相互鏈接->再度創(chuàng)建新結點，這樣會有助于理解。
如圖所示：
對于每一次的雙向鏈表的插入操作，首先需要創(chuàng)建一個獨立的結點，并通過malloc操作開辟相應的空間；
其次我們選中這個新創(chuàng)建的獨立節(jié)點，將其的pre指針指向所需插入位置的前一個結點；
同時，其所需插入的前一個結點的next指針修改指向為該新的結點，該新的結點的next指針將會指向一個原本的下一個結點，而修改下一個結點的pre指針為指向新結點自身，這樣的一個操作我們稱之為雙向鏈表的插入操作。
其代碼可以表示為：
//插入數(shù)據(jù)
line * insertLine(line * head,int data,int add){
//三個參數(shù)分別為：進行此操作的雙鏈表，插入的數(shù)據(jù)，插入的位置
//新建數(shù)據(jù)域為data的結點
line * temp=(line*)malloc(sizeof(line));
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
//插入到鏈表頭，要特殊考慮
if (add==1) {
temp->next=head;
head->pre=temp;
head=temp;
}else{
line * body=head;
//找到要插入位置的前一個結點
for (int i=1; i<add-1; i++) {
body=body->next;
}
//判斷條件為真，說明插入位置為鏈表尾
if (body->next==NULL) {
body->next=temp;
temp->pre=body;
}else{
body->next->pre=temp;
temp->next=body->next;
body->next=temp;
temp->pre=body;
}
}
return head;
}
如圖：
刪除操作的過程是：選擇需要刪除的結點->選中這個結點的前一個結點->將前一個結點的next指針指向自己的下一個結點->選中該節(jié)點的下一個結點->將下一個結點的pre指針修改指向為自己的上一個結點。
在進行遍歷的時候直接將這一個結點給跳過了，之后，我們釋放刪除結點，歸還空間給內存，這樣的操作我們稱之為雙鏈表的刪除操作。
其代碼可以表示為：
//刪除元素
line * deleteLine(line * head,int data){
//輸入的參數(shù)分別為進行此操作的雙鏈表，需要刪除的數(shù)據(jù)
line * list=head;
//遍歷鏈表
while (list) {
//判斷是否與此元素相等
//刪除該點方法為將該結點前一結點的next指向該節(jié)點后一結點
//同時將該結點的后一結點的pre指向該節(jié)點的前一結點
if (list->data==data) {
list->pre->next=list->next;
list->next->pre=list->pre;
free(list);
printf("--刪除成功--\n");
return head;
}
list=list->next;
}
printf("Error:沒有找到該元素，沒有產生刪除\n");
return head;
}
雙向鏈表的遍歷利用next指針逐步向后進行索引即可。
注意，在判斷這里，我們既可以用while(list)的操作直接判斷是否鏈表為空，也可以使用while(list->next)的操作判斷該鏈表是否為空，其下一節(jié)點為空和本結點是否為空的判斷條件是一樣的效果。
其簡單的代碼可以表示為：
//遍歷雙鏈表,同時打印元素數(shù)據(jù)
void printLine(line *head){
line *list = head;
int pos=1;
while(list){
printf("第%d個數(shù)據(jù)是:%d\n",pos++,list->data);
list=list->next;
}
}
對于單鏈表以及雙向鏈表，就像一個小巷，無論怎么走最終都能從一端走到另一端，顧名思義，循環(huán)鏈表則像一個有傳送門的小巷，當你以為你走到結尾的時候，其實這就是開頭。
循環(huán)鏈表和非循環(huán)鏈表其實創(chuàng)建的過程唯一不同的是，非循環(huán)鏈表的尾結點指向空（NULL），而循環(huán)鏈表的尾指針指向的是鏈表的開頭。
通過將單鏈表的尾結點指向頭結點的鏈表稱之為循環(huán)單鏈表（Circular linkedlist）
一個完整的循環(huán)單鏈表如圖：
對于循環(huán)單鏈表的結點，可以完全參照于單鏈表的結點設計，如圖：
data表示數(shù)據(jù)；
next表示指針，它總是指向自身的下一個結點，對于只有一個結點的存在，這個next指針則永遠指向自身，對于一個鏈表的尾部結點，next永遠指向開頭。
其代碼如下：
typedef struct list{
int data;
struct list *next;
}list;
//data為存儲的數(shù)據(jù)，next指針為指向下一個結點
先創(chuàng)建一個頭結點并且給其開辟內存空間，在開辟內存空間成功之后，將頭結點的next指向head自身，創(chuàng)建一個init函數(shù)來完成；
為了重復創(chuàng)建和插入，我們可以在init函數(shù)重新創(chuàng)建的結點next指向空，而在主函數(shù)調用創(chuàng)建之后，將head頭結點的next指針指向自身。
這樣的操作方式可以方便過后的創(chuàng)建單鏈表，直接利用多次調用的插入函數(shù)即可完成整體創(chuàng)建。
其代碼如下：
//初始結點
list *initlist(){
list *head=(list*)malloc(sizeof(list));
if(head==NULL){
printf("創(chuàng)建失敗，退出程序");
exit(0);
}else{
head->next=NULL;
return head;
}
}
在主函數(shù)重調用可以是這樣
//////////初始化頭結點//////////////
list *head=initlist();
head->next=head;
如圖所示：
通過逐步的插入操作，創(chuàng)建一個新的節(jié)點，將原有鏈表尾結點的next指針修改指向到新的結點，新的結點的next指針再重新指向頭部結點，然后逐步進行這樣的插入操作，最終完成整個單項循環(huán)鏈表的創(chuàng)建。
其代碼如下：
//創(chuàng)建——插入數(shù)據(jù)
int insert_list(list *head){
int data; //插入的數(shù)據(jù)類型
printf("請輸入要插入的元素：");
scanf("%d",&data);
list *node=initlist();
node->data=data;
//初始化一個新的結點，準備進行鏈接
if(head!=NULL){
list *p=head;
//找到最后一個數(shù)據(jù)
while(p->next!=head){
p=p->next;
}
p->next=node;
node->next=head;
return 1;
}else{
printf("頭結點已無元素\n");
return 0;
}
}
如圖，對于插入數(shù)據(jù)的操作，可以創(chuàng)建一個獨立的結點，通過將需要插入的結點的上一個結點的next指針指向該節(jié)點，再由需要插入的結點的next指針指向下一個結點的方式完成插入操作。
其代碼如下：
//插入元素
list *insert_list(list *head,int pos,int data){
//三個參數(shù)分別是鏈表，位置，參數(shù)
list *node=initlist(); //新建結點
list *p=head; //p表示新的鏈表
list *t;
t=p;
node->data=data;
if(head!=NULL){
for(int i=1;i<pos;i++){
t=t->next; //走到需要插入的位置處
}
node->next=t->next;
t->next=node;
return p;
}
return p;
}
如下圖所示，循環(huán)單鏈表的刪除操作是先找到需要刪除的結點，將其前一個結點的next指針直接指向刪除結點的下一個結點即可。
需要注意的是尾結點，因為刪除尾節(jié)點后，尾節(jié)點前一個結點就成了新的尾節(jié)點，這個新的尾節(jié)點需要指向的是頭結點而不是空。
其代碼如下：
//刪除元素
int delete_list(list *head) {
if(head == NULL) {
printf("鏈表為空！\n");
return 0;
}
//建立臨時結點存儲頭結點信息（目的為了找到退出點）
//如果不這么建立的化需要使用一個數(shù)據(jù)進行計數(shù)標記，計數(shù)達到鏈表長度時自動退出
//循環(huán)鏈表當找到最后一個元素的時候會自動指向頭元素，這是我們不想讓他發(fā)生的
list *temp = head;
list *ptr = head->next;
int del;
printf("請輸入你要刪除的元素：");
scanf("%d",&del);
while(ptr != head) {
if(ptr->data == del) {
if(ptr->next == head) {
temp->next = head;
free(ptr);
return 1;
}
temp->next = ptr->next; //核心刪除操作代碼
free(ptr);
//printf("元素刪除成功！\n");
return 1;
}
temp = temp->next;
ptr = ptr->next;
}
printf("沒有找到要刪除的元素\n");
return 0;
}
與普通的單鏈表和雙向鏈表的遍歷不同，循環(huán)鏈表需要進行結點的特殊判斷。
先找到尾節(jié)點的位置，由于尾節(jié)點的next指針是指向頭結點的，所以不能使用鏈表本身是否為空（NULL）的方法進行簡單的循環(huán)判斷，我們需要通過判斷結點的next指針是否等于頭結點的方式進行是否完成循環(huán)的判斷。
此外還有一種計數(shù)的方法，即建立一個計數(shù)器count=0，每一次next指針指向下一個結點時計數(shù)器+1，當count數(shù)字與鏈表的節(jié)點數(shù)相同的時候即完成循環(huán)；
但是這樣做會有一個問題，就是獲取到鏈表的節(jié)點數(shù)同時，也需要完成一次遍歷才可以達成目標。
其代碼如下：
//遍歷元素
int display(list *head) {
if(head != NULL) {
list *p = head;
//遍歷頭節(jié)點到，最后一個數(shù)據(jù)
while(p->next != head ) {
printf("%d ",p->next->data);
p = p->next;
}
printf("\n"); //換行
//把最后一個節(jié)點賦新的節(jié)點過去
return 1;
} else {
printf("頭結點為空!\n");
return 0;
}
}
循環(huán)單鏈表也有一個孿生兄弟——雙向循環(huán)鏈表，其設計思路與單鏈表和雙向鏈表的設計思路一樣，就是在原有的雙向鏈表的基礎上，將尾部結點和頭部結點進行互相連接。交給大家了。
在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低。并且需要預先分配足夠大的存儲空間，而鏈表恰恰是其中運用的精華。
基于存儲，運算，環(huán)境這幾方面考慮，可以讓我們更好的在項目中使用鏈表。
今天鏈表基礎就講到這里，下一期，我們再見！
從0學ARM專輯
1. 0. 到底什么是Cortex、ARMv8、arm架構、ARM指令集、soc？一文幫你梳理基礎概念【科普】
2. 1. 從0開始學ARM-安裝Keil MDK uVision集成開發(fā)環(huán)境
推薦閱讀
點擊“閱讀原文”查看更多分享，歡迎點分享、收藏、點贊、在看。
