風景圖
作者個人博客 https://www.you3xuan.top/ 查看原文。
本文為線性表第二篇慨亲，如果讀者想了解第一篇人弓，請點擊這里稍途。
源碼地址: https://github.com/ThinkingXuan/DataStructure </br>
如果對您有幫助，隨手一個Star吧倘潜。
1绷柒、線性表的鏈式存儲
??在鏈式存儲中，結(jié)點之間的內(nèi)存單元地址是不連續(xù)的涮因。它的每一個結(jié)點包括數(shù)據(jù)域和下一個結(jié)點的地址废睦。頭結(jié)點的數(shù)據(jù)域只存放結(jié)點的長度，并指向第一個元素养泡。尾結(jié)點指向NULL嗜湃。如圖所示：
鏈表
??因為內(nèi)存單元不連續(xù)，所以哪里空閑的內(nèi)存澜掩，都可以分配一個結(jié)點购披，提高了內(nèi)存的利用率。又因為結(jié)點之間只通過地址連接肩榕，所以刪除和插入結(jié)點效率高刚陡。又因為沒有索引與結(jié)點對應，查找一個結(jié)點的時候株汉，必須找到上一個結(jié)點筐乳，所以查詢效率不高。
2乔妈、鏈式存儲的實現(xiàn)
2.1 創(chuàng)建單鏈表
??分為三部分哥童，創(chuàng)建頭結(jié)點，創(chuàng)建普通結(jié)點褒翰，創(chuàng)建單鏈表贮懈。
- 創(chuàng)建頭結(jié)點
//創(chuàng)建頭結(jié)點匀泊，length存儲鏈表的長度 next指向下一個結(jié)點
typedef struct Header{
int length;
struct Header * next;
}Head;
- 創(chuàng)建普通結(jié)點
//創(chuàng)建一個結(jié)點，data存放數(shù)據(jù)朵你，next指向下一個結(jié)點
typedef struct Node{
int data;
struct Node *next;
}ListNode;
- 創(chuàng)建鏈表
//創(chuàng)建一個鏈表各聘，返回頭結(jié)點
Head * createList(){
Head *phead = (Head*)malloc(sizeof(Head));
phead->length = 0;
phead->next = NULL;
return phead;
}
2.2 獲取鏈表長度
// 獲取鏈表長度
int getLength(Head * phead){
if(phead==NULL){
printf("not init headnode!\n");
return -1;
}
return phead->length;
}
2.3 添加結(jié)點
// 添加數(shù)據(jù)，,默認添加在末尾
int addData(Head * phead, int data){
if(phead==NULL){
printf("not init head node!\n");
return -1;
}
//創(chuàng)建當前結(jié)點抡医，并指向鏈表最后一個結(jié)點
ListNode * curNode = phead;
while(curNode->next!=NULL){
curNode = curNode->next;
}
//創(chuàng)建新結(jié)點
ListNode * newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = data;
newNode->next = NULL;
//連接結(jié)點
curNode->next = newNode;
phead->length++;
return 1;
}
??如圖所示躲因，添加結(jié)點需要兩個結(jié)點，一個當前結(jié)點忌傻，指向尾結(jié)點大脉，另一個是要添加的新結(jié)點，指向NULL,使用當前結(jié)點的next指向新結(jié)點水孩，就完成了添加結(jié)點的操作镰矿。因為當前結(jié)點是指向尾結(jié)點的，當前結(jié)點的next就相當于尾結(jié)點的next俘种，所有就相當于尾結(jié)點的next指向了新結(jié)點秤标。最后別忘把頭結(jié)點的length加1。
結(jié)點
2.4 插入結(jié)點
// 插入數(shù)據(jù)
int insertData(Head * pHead, int data, int pos){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pos < 0||pos > pHead->length){
printf("insert postion error!\n");
return -2;
}
//創(chuàng)建新結(jié)點
ListNode * newNode = (ListNode *)malloc(sizeof(ListNode));
newNode->data = data;
//創(chuàng)建當前結(jié)點
ListNode * curNode = pHead;
int i;
for(i=0;i<pos;i++){
curNode = curNode->next;
}
newNode->next = curNode->next;
curNode->next = newNode;
pHead->length++;
return 1;
}
插入
??同樣宙刘，插入也需要兩個結(jié)點苍姜，一個結(jié)點指向要插入的位置的前一個結(jié)點，起名為當前結(jié)點悬包。另一個為新結(jié)點衙猪。主要就是兩行代碼：
newNode->next = curNode->next;
curNode->next = newNode;
??當前結(jié)點指向待插入位置的前一個結(jié)點，起名為前結(jié)點(lastNode)布近。以上代碼相當于：
newNode->next = lastNode->next;
lastNode->next = newNode;
??因為lastNode->next指向下一個結(jié)點∏停現(xiàn)在使用newNode->next指向下一個結(jié)點。然后使用lastNode->next指向newNode吊输。就完成了插入操作饶号。
??兩行代碼不可顛倒位置，因為先執(zhí)行第二行代碼的話季蚂，會導致后面結(jié)點全部丟失茫船。
2.5 刪除結(jié)點
// 刪除數(shù)據(jù)
int deleteData(Head * pHead,int pos){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pos < 0||pos >= pHead->length){
printf("delete postion error!\n");
return -2;
}
//創(chuàng)建當前結(jié)點
ListNode * curNode = pHead;
int i;
for(i=0;i<pos;i++){
curNode = curNode->next;
}
curNode->next = curNode->next->next;
pHead->length--;
return 1;
}
刪除
??當前結(jié)點指定要刪除位置的上一個結(jié)點(前結(jié)點)，把前結(jié)點的next指向下一個結(jié)點的
next,curNode->next = curNode->next->next,就完成了刪除操作扭屁。
2.6 獲取指定位置的結(jié)點
//獲取數(shù)據(jù)
int getData(Head * pHead,int pos){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pos < 0||pos >= pHead->length){
printf("postion error!\n");
return -2;
}
//創(chuàng)建當前結(jié)點
ListNode * curNode = pHead;
int i;
for(i=0;i<=pos;i++){
curNode = curNode->next;
}
return curNode->data;
}
2.7 打印所有結(jié)點
//打印
void print(Head * phead){
if(phead==NULL){
printf("not init headnode!\n");
return 0;
}
ListNode * node = phead->next;
while(node->next!=NULL){
printf("%d->",node->data);
node = node->next;
}
printf("%d length=%d\n",node->data,phead->length);
}
??為了讓打印效果更好算谈，想法去掉了最后一個->，并且輸出鏈表的長度料滥。
2.8 測試
#include<stdio.h>
#include<stdlib.h>
int main(){
int i;
printf("create ListNode:\n");
Head* pHead = createList();
printf("length=%d\n\n",pHead->length);
printf("add data:\n");
for(i=0;i<10;i++){
addData(pHead,i);
}
print(pHead) ;
printf("\n");
printf("insert data:\n");
insertData(pHead,100,3);
print(pHead);
printf("\n");
printf("delete data:\n");
deleteData(pHead,3);
print(pHead);
printf("\n");
printf("get data:\n");
printf("%d\n",getData(pHead,5));
printf("\n");
return 0;
}
輸出結(jié)果：
輸出結(jié)果
3然眼、雙鏈表實現(xiàn)鏈式存儲
定義
??前面使用單鏈表實現(xiàn)了線性表的鏈式存儲。但是單鏈表有個缺點葵腹，無法訪問前驅(qū)結(jié)點高每。當查找到一個元素結(jié)點時屿岂，如果想要找到前面的元素結(jié)點，需要從頭開始遍歷鲸匿，比較麻煩爷怀。所有雙鏈表有開辟了一個空間,存儲結(jié)點前驅(qū)結(jié)點的地址。如圖所示：
雙鏈表
??雙鏈表的實現(xiàn)和單鏈表類似带欢，當我們插入一個新結(jié)點時运授，如果這個結(jié)點有后驅(qū)結(jié)點時，要是后驅(qū)結(jié)點的pre 指向新結(jié)點乔煞，新結(jié)點的pre也要指向它的前驅(qū)結(jié)點吁朦。其他操作類似，這里只貼出代碼渡贾，就不詳細解釋了逗宜。
3.1 創(chuàng)建雙鏈表
typedef struct Header{
int length;
struct Header * pre; //為了方便，在頭結(jié)點添加一個pre 剥啤，不然無法指向 Node,在Head后面添加結(jié)點時就需要單獨判斷锦溪。
struct Header * next;
}Head;
typedef struct Node{
int data;
struct Node * pre;
struct Node * next;
}NodeList;
//創(chuàng)建
Head * createDouNodeList(){
Head * pHead = (Head*)malloc(sizeof(Head));
if(pHead == NULL){
printf("create failure!\n");
}
pHead->length = 0;
pHead->next = NULL;
return pHead;
}
3.2 獲取鏈表長度
// 獲取鏈表長度
int getLength(Head * pHead){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
return pHead->length;
}
3.3 判斷是否為空
//判斷是否為空
int isEmpty(Head *pHead){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pHead->length==0){
return 1;
}else{
return 0;
}
}
3.4 添加結(jié)點
// 添加結(jié)點不脯，,默認添加在末尾
int addDataDou(Head * pHead, int data){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
//創(chuàng)建當前結(jié)點府怯，并指向鏈表最后一個結(jié)點
NodeList * curNode = pHead;
while(curNode->next != NULL){
curNode = curNode->next;
}
//創(chuàng)建新結(jié)點
NodeList * newNode = (NodeList*)malloc(sizeof(NodeList));
newNode->data = data;
newNode->next = NULL;
curNode->next = newNode;
newNode->pre = curNode;
pHead->length++;
return 1;
}
3.5 插入結(jié)點
//插入
int insertDou(Head *pHead,int data,int pos){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pos<=0||pos>=pHead->length){
printf("insert positon error!\n");
return -2;
}
//創(chuàng)建新結(jié)點
NodeList * newNode = (NodeList*)malloc(sizeof(NodeList));
newNode->data = data;
//創(chuàng)建當前結(jié)點,并指向 指定位置之前的那個結(jié)點
NodeList * curNode = pHead;
int i;
for(i=0;i<pos;i++){
curNode = curNode->next;
}
//連接
newNode->next = curNode->next;
curNode->next->pre = newNode;
newNode->pre = curNode;
curNode->next = newNode;
pHead->length++;
return 1;
}
3.6 刪除結(jié)點
//刪除
int deleteDataDou(Head * pHead,int pos){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pos < 0||pos >= pHead->length){
printf("delete postion error!\n");
return -2;
}
//創(chuàng)建當前結(jié)點
NodeList * curNode = pHead;
int i;
for(i=0;i<pos;i++){
curNode = curNode->next;
}
curNode->next = curNode->next->next;
//要刪除最后一個結(jié)點時判斷
if(curNode->next!=NULL){
curNode->next->pre = curNode;
}
pHead->length--;
return 1;
}
3.7 獲取指定元素的結(jié)點
//查找某個元素，返回它的結(jié)點
NodeList * findNodeDou(Head *pHead,int val){
if(pHead==NULL){
printf("not init head node!\n");
return 0;
}
NodeList *curNode = pHead->next;
do{
if(curNode->data == val){
return curNode;
}
curNode = curNode->next;
}while(curNode->next!=NULL);
return NULL;
}
3.8 打印所有結(jié)點
//打印
void print(Head * pHead){
if(pHead==NULL){
printf("not init head node!\n");
return 0;
}
NodeList * node = pHead->next;
while(node->next!=NULL){
printf("%d<->",node->data);
node = node->next;
}
printf("%d length=%d\n",node->data,pHead->length);
}
3.9 測試
//雙鏈表實現(xiàn)鏈式存儲
#include <stdio.h>
#include <stdlib.h>
int main(){
int i;
printf("Create Double Node List: \n");
Head *pHead = createDouNodeList();
printf("length = %d\n",pHead->length);
printf("\n");
printf("Add Data: \n");
for(i=0;i<10;i++){
addDataDou(pHead,i);
}
print(pHead);
printf("\n");
printf("Insert Data: \n");
insertDou(pHead,100,3);
print(pHead);
printf("\n");
printf("delete Data: \n");
deleteDataDou(pHead,3);
print(pHead);
printf("\n");
printf("find Node: \n");
NodeList * node = findNodeDou(pHead,3);
printf("node is %d\n",node);
printf("\n");
return 0;
}
輸出結(jié)果：
輸出結(jié)果
4防楷、循環(huán)鏈表
??鏈表還有一種常用的形式牺丙，那就是循環(huán)鏈表。循環(huán)鏈表首尾相接复局，形成一個環(huán)冲簿，從鏈表任何一個結(jié)點出發(fā)，都能夠找到其他所有結(jié)點亿昏。
??循環(huán)鏈表分為單向循環(huán)鏈表峦剔，雙循環(huán)鏈表，多重循環(huán)鏈表角钩。如圖所示：
單向循環(huán)鏈表
??上圖是單向循環(huán)鏈表吝沫，形成一個閉合環(huán)，有一個方向递礼。
雙循環(huán)鏈表
??上圖是雙向循環(huán)鏈表惨险，形成一個閉合環(huán)，有兩個方向脊髓。
多重循環(huán)鏈表
??上圖是多重循環(huán)鏈表辫愉，形成了兩個閉合環(huán)。
??本教程只講解單向循環(huán)鏈表将硝，其他兩種比較復雜恭朗，如需要的話屏镊，自行搜索。 循環(huán)鏈表的創(chuàng)建和查找基本和單鏈表一樣冀墨，這里就不過多講解了闸衫，只講解插入和刪除。如果您還不太清楚诽嘉，請認真閱讀前面的知識蔚出。
4.1 插入結(jié)點
int insertCircleList(Head * pHead,int data,int pos){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pos < 0||pos > pHead->length){
printf("insert postion error!\n");
return -2;
}
//創(chuàng)建新結(jié)點
NodeList * newNode = (NodeList*)malloc(sizeof(NodeList));
newNode->data = data;
//如果是空
if(isEmpty(pHead)){
pHead->next = newNode; //直接插入到頭結(jié)點后面
newNode->next = newNode; //自己指向自己
}else{
NodeList *curNode = pHead->next;
//因為pos ==0為涉及到頭結(jié)點，單獨處理
if(pos==0){
//curNode指向尾結(jié)點
while(curNode->next!=pHead->next){
curNode = curNode->next;
}
newNode->next =pHead->next;
pHead->next = newNode;
curNode->next = newNode;
}else{
//使curNode指向插入位置的前一個結(jié)點
int i;
for(i=1;i<pos;i++){
curNode = curNode->next;
}
newNode->next = curNode->next;
curNode->next = newNode;
}
}
pHead->length++;
return 1;
}
4.2 刪除結(jié)點
int deleteCircleNode(Head *pHead,int pos){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pos < 0||pos > pHead->length){
printf("insert postion error!\n");
return -2;
}
NodeList *curNode = pHead->next;
if(isEmpty(pHead)){
return -3;
}else{
if(pos==0){
while(curNode->next!=pHead->next){
curNode = curNode->next;
}
curNode->next = curNode ->next->next;
pHead->next = curNode ->next;
}else{
int i;
for(i=1;i<pos;i++){
curNode = curNode->next;
}
curNode ->next = curNode->next->next;
}
}
pHead->length--;
return 1;
}
4.3 其他代碼
//創(chuàng)建頭結(jié)點虫腋，length存儲鏈表的長度 next指向下一個結(jié)點
typedef struct Header{
int length;
struct Header * next;
}Head;
//創(chuàng)建一個結(jié)點骄酗，data存放數(shù)據(jù)，next指向下一個結(jié)點
typedef struct Node{
int data;
struct Node *next;
}NodeList;
//創(chuàng)建一個鏈表悦冀，返回頭結(jié)點
Head * createList(){
Head *phead = (Head*)malloc(sizeof(Head));
phead->length = 0;
phead->next = NULL;
return phead;
}
//判斷是否為空
int isEmpty(Head *pHead){
if(pHead==NULL){
printf("not init head node!\n");
return -1;
}
if(pHead->length==0){
return 1;
}else{
return 0;
}
}
//打印
void print(Head *pHead){
if(pHead==NULL){
printf("not init headnode!\n");
return 0;
}
NodeList * node = pHead->next;
do{
printf("%d->",node->data);
node = node->next;
}while(node!=pHead->next);
printf(" length=%d\n",pHead->length);
}
4.4 測試
//循環(huán)鏈表
#include<stdio.h>
#include<stdlib.h>
int main(){
int i;
printf("Create Circle Node List: \n");
Head * pHead = createList();
printf("length = %d\n",pHead->length);
printf("\n");
printf("Insert Node: \n");
for(i=0;i<11;i++){
insertCircleList(pHead,i,i);
}
print(pHead);
printf("\n");
printf("Delete Node: \n");
deleteCircleNode(pHead,0);
print(pHead);
return 0;
}
輸出結(jié)果：
輸出結(jié)果
