1.二級指針的使用
二級指針：
1. 在被調函數中，想要修改主調函數中的指針變量，需要傳遞該指針變量的地址，形參用二級指針接收。
2.指針數組的數組名是一個二級指針，指針數組的數組名作為參數傳遞時，可用二級指針接收。指針數組：保存多個指針的數組。
數組名：數組首元素地址。
2.內核鏈表
內核鏈表：雙向循環鏈表
不再將數據存儲在鏈表節點中，而是將結點嵌入到存儲的數據中。
包含的宏：
offset_of : 獲取內核鏈表中鏈表結點到結構體起始位置的偏移量。
container_of:通過偏移量，獲取結構體的首地址（結點首地址-偏移量）。
3.棧
（1）基本概念
①系統棧
特點：先進后出: FILO
②數據結構的棧
棧：只允許從一端進行數據的插入和刪除的線性存儲結構，稱之為棧結構
特點：先進后出: FILO
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
a.順序棧
?滿增棧、滿減棧、空增棧、空減棧
滿棧、空棧：棧頂所在位置是否存在數據
增棧、減棧：按照棧的生長方向區分
b.鏈式棧
（2）基本操作
①創建一個棧
Stack_t *create_stack()
{Stack_t *pstack = malloc(sizeof(Stack_t));if(NULL == pstack){return NULL;}pstack->clen = 0;pstack->ptop = NULL;return pstack;
}②判斷一個棧是否為空
int is_empty_stack(Stack_t *pstack)
{return NULL == pstack->ptop;
}③遍歷
int stack_for_each(Stack_t *pstack)
{STNode_t *ptmp = pstack->ptop;if(NULL == pstack){return -1;}else{while(ptmp != NULL){printf("%d ", ptmp->data);ptmp = ptmp->pnext;}puts("");}
}④插入
int push_stack(Stack_t *pstack, Data_t data)
{STNode_t *ptmp = malloc(sizeof(STNode_t));if(NULL == ptmp){return -1;}ptmp->data = data;ptmp->pnext = NULL;ptmp->pnext = pstack->ptop;pstack->ptop = ptmp;pstack->clen++;return 1;
}⑤刪除
int pop_stack(Stack_t *pstack,Data_t *pdata)
{if(NULL == pstack){return -1;}STNode_t *ptmp = pstack->ptop;pstack->ptop = ptmp->pnext;if(pdata != NULL){*pdata = ptmp->data;}free(ptmp);pstack->clen--;return 0;}⑥獲取棧頂元素
int get_pop_stack(Stack_t *pstack, Data_t *pdata)
{if(NULL == pstack){return -1;}if(NULL == pdata){return -1;}*pdata = pstack->ptop->data;return 0;}
⑦銷毀棧
void destroy_stack(Stack_t *pstack)
{if(is_empty_stack(pstack)){free(pstack);return ;}else{STNode_t *ptmp = pstack->ptop;STNode_t *p = NULL;while(ptmp->pnext != NULL){p =ptmp->pnext;free(ptmp);ptmp = p;} free(ptmp);}free(pstack);
}
void stack_destory(Stack_t **pstack)
{while(!is_empty_stack(*pstack)){pop_stack(*pstack, NULL);}free(*pstack);*pstack = NULL;
}4.隊列
（1）基本概念
隊列：允許從一端進行數據的插入，另一端進行數據刪除的線性存儲結構，稱為隊列結構
插入操作，叫入隊操作，插入的這端稱為隊列的隊尾；
刪除操作，叫出隊操作，刪除的這端稱為隊列的隊頭。特點：先進先出（FIFO）
應用：數據緩存
①鏈式隊列
②順序隊列
循環隊列
[head， tail)
循環隊列為了區分隊空和隊滿，將來少存儲一個數據。
循環隊列如何判空？--》隊頭和隊尾處于同一位置，此時認為隊列為空
循環隊列如何判滿？--》當隊尾+1跟上隊頭時，任務認為隊列為滿
（2）基本操作
①鏈式隊列
a.創建隊列
LQueue_t *create_linkque()
{LQueue_t *plq = malloc(sizeof(LQueue_t));if(NULL == plq){return NULL;} plq->clen = 0;plq->phead = NULL;plq->ptail = NULL;return plq;
}b.判空
int is_empty_linkque(LQueue_t *plq)
{return NULL == plq->phead;
}c.遍歷
void linkque_for_each(LQueue_t *plq)
{LQNode_t *ptmp = plq->phead;while(ptmp != NULL){printf("%d ", ptmp->data);ptmp = ptmp->pnext;}puts("");
}
d.插入
int insert_linkque_tail(LQueue_t *plq, Data_type_t data)
{LQNode_t * ptmp = malloc(sizeof(LQNode_t));if(NULL == ptmp){return -1;}ptmp->data = data;ptmp->pnext = NULL;if(is_empty_linkque(plq)){plq->phead = ptmp;plq->ptail = ptmp;}else{plq->ptail->pnext = ptmp;plq->ptail = ptmp;} plq->clen++;return 1;
}e.刪除
int delete_linkque_head(LQueue_t *plq, Data_type_t *pdata)
{if(is_empty_linkque(plq)){return -1;}LQNode_t *ptmp = plq->phead;plq->phead = ptmp->pnext;if(pdata != NULL){*pdata = ptmp->data;}free(ptmp);if (NULL == plq->phead){plq->ptail = NULL;}plq->clen--;return 1;}f.獲取隊頭元素
int get_linkque_head(LQueue_t *plq)
{if(is_empty_linkque(plq)){return -1;}return plq->phead->data;
}
g.銷毀隊列
void destroy_linkque(LQueue_t **plq)
{while(!is_empty_linkque(*plq)){delete_linkque_head(*plq);}free(*plq);*plq = NULL;
}
②順序隊列---》循環隊列
a.創建
Seqque_t *create_seqque()
{Seqque_t *psq = malloc(sizeof(Seqque_t));if (NULL == psq){printf("malloc error\n");return NULL;}psq->head = 0;psq->tail = 0;psq->pbase = malloc(sizeof(Data_type_t) * SEQQUE_MAX_LEN);if (NULL == psq->pbase){printf("malloc error\n");return NULL;}return psq;
}b.判滿
int is_full_seqque(Seqque_t *psq)
{if ((psq->tail+1)%SEQQUE_MAX_LEN == psq->head){return 1;}return 0;c.判空
int is_empty_seqque(Seqque_t *psq)
{if (psq->head == psq->tail){return 1;}return 0;
}d.入隊
int push_seqque(Seqque_t *psq, Data_type_t data)
{if (is_full_seqque(psq)){printf("seqque is full\n");return -1;}psq->pbase[psq->tail] = data;psq->tail = (psq->tail+1) % SEQQUE_MAX_LEN;return 0;
}e.遍歷
void seqque_for_each(Seqque_t *psq)
{for (int i = psq->head; i < psq->tail; i = (i+1)%SEQQUE_MAX_LEN){printf("%d ", psq->pbase[i]);}printf("\n");
}
f.出隊
int pop_seqque(Seqque_t *psq, Data_type_t *pdata)
{if(is_empty_seqque(psq) || NULL == pdata){return -1;}if(pdata != NULL){*pdata = psq->pbase[psq->head];psq->head = (psq->head + 1) % SEQQUE_MAX_LEN;}return 0;
}g.獲取隊頭元素
int top_seqque(Seqque_t *psq)
{if(is_empty_seqque(psq)){return -1;}return psq->pbase[psq->head];}h.銷毀隊列
void destroy_seqque(Seqque_t *psq)
{free(psq->pbase);free(psq);
}5.棧和隊列的不同
1.?存取規則不同
隊列：先進先出（FIFO, First In First Out）
先進入隊列的元素先被取出（類似排隊）。棧：后進先出（LIFO, Last In First Out）
最后入棧的元素最先被取出（類似疊盤子）。2.?操作接口不同
隊列：
enqueue（入隊）：在隊尾添加元素。
dequeue（出隊）：從隊頭移除元素。棧：
push（入棧）：在棧頂添加元素。
pop（出棧）：從棧頂移除元素。
注：上述函數代碼均沒有主函數
