《 靜態鏈表的創建、插入、刪除、銷毀代碼實現》
序言：表的學習也沒學習多久，對于我而言大部分都是研究別人的代碼，取其精華取其糟粕。鏈表在學習計算機課程的時候，數據結構是一門基礎課程，基礎不代表不重要，相反是特別重要，就好比你想學習騎自行車，但是你連走路都不會，怎么會騎自行車呢？哈哈，學習數據結構的基本思路是:
順序表，鏈表，靜態鏈表、雙鏈表，循環量表等 .
要求：c語言要懂一點。
接下來我們就一起分析下面一段代碼吧！
#include<stdlib.h>
#include <stdio.h> //頭函數就好比一個倉庫,存儲我們需要的基礎函數,如printf 等
#include<malloc.h>
#define AVAILABLE -1
typedef void StaticList;
typedef void StaticListNode;
/**************頭函數定義其實也可以不需要只是為了實現結構化***************/
//下面通過英語提示大家都應該知道函數的實現功能了吧
StaticList* StaticList_Create(int capacity); //創建
void StaticList_Destroy(StaticList* list); //銷毀鏈表
void StaticList_Clear(StaticList* list); //清除鏈表
int StaticList_Length(StaticList* list); //獲取長度
int StaticList_Capacity(StaticList* list); //獲取容量
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos); //插入數據
StaticListNode* StaticList_Get(StaticList* list, int pos); //獲取元素
StaticListNode* StaticList_Delete(StaticList* list, int pos); //刪除元素
//對于這個結構體的定義相信大家都應該很熟悉了吧，關鍵在這里typedef的應用
typedef struct _tag_StaticListNode
{
unsigned int data; //存放和數據的地方
int next; //指向下一個數組坐標的值
} TStaticListNode; //結構體變量相當于別名
typedef struct _tag_StaticList //定義一個數據域結構體
{
int capacity;
TStaticListNode header; //數組頭
TStaticListNode node[]; //相當于指針地址
} TStaticList;
/************************創建鏈表*****************************/
StaticList* StaticList_Create(int capacity) // O(n)
{
TStaticList* ret = NULL;
int i = 0;
if( capacity >= 0 )
{ /*申請內存大小capacity加一是因為頭數據要算一個*/
ret = (TStaticList*)malloc(sizeof(TStaticList) + sizeof(TStaticListNode) * (capacity + 1));
}
if( ret != NULL )
{
ret->capacity = capacity;
ret->header.data = 0;
ret->header.next = 0;
for(i=1; i<=capacity; i++) /*用來找出數組空閑的數據位置*/
{
ret->node[i].next = AVAILABLE;
}
}
return ret;
}
/*銷毀鏈表內存申請相當于調用了一個free函數*/
void StaticList_Destroy(StaticList* list) // O(1)
{
free(list);
}
/*清除鏈表元素*/
void StaticList_Clear(StaticList* list) // O(n)
{
TStaticList* sList = (TStaticList*)list;//ba void turn point
int i = 0;
if( sList != NULL )
{
sList->header.data = 0;
sList->header.next = 0;
for(i=1; i<=slist->capacity; i++)/*清除后要定義為可用*/
{
sList->node[i].next = AVAILABLE;
}
}
}
/*獲取數組元素個數*/
int StaticList_Length(StaticList* list) // O(1)
{
TStaticList* sList = (TStaticList*)list;
int ret = -1;
if( sList != NULL )
{
ret = sList->header.data;
}
return ret;
}
/****獲取內存容量***/
int StaticList_Capacity(StaticList* list) // O(1)
{
TStaticList* sList = (TStaticList*)list;
int ret = -1;
if( sList != NULL )
{
ret = sList->capacity;
}
return ret;
}
/****插入數據元素***/
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos) // O(n)
{ /***參數1 鏈表頭指針 參數2 具體數據地址 參數3 位置****/
TStaticList* sList = (TStaticList*)list;
int ret = (sList != NULL);
int current = 0;
int index = 0;
int i = 0;
/****判斷位置是否有效***/
ret = ret && (sList->header.data + 1 <= slist-="">capacity);
ret = ret && (pos >=0) && (node != NULL);
if( ret )
{
for(i=1; i<=slist->capacity; i++)
{
if( sList->node[i].next == AVAILABLE )
{
index = i;
break; /****判斷是否為可用位置***/
}
}
sList->node[index].data = (unsigned int)node;
sList->node[0] = sList->header;
for(i=0; (inode[current].next != 0); i++)
{
current = sList->node[current].next;
}
/****下面兩行代碼是說明具體插入位置的算法實現***/
sList->node[index].next = sList->node[current].next;
sList->node[current].next = index;
sList->node[0].data++; /****之后要data加以***/
sList->header = sList->node[0]; /***節點游標要回到初始位置****/
}
return ret;
}
/****獲取元素值***/
StaticListNode* StaticList_Get(StaticList* list, int pos) // O(n)
{
TStaticList* sList = (TStaticList*)list;
StaticListNode* ret = NULL;
int current = 0;
int object = 0;
int i = 0;
if( (sList != NULL) && (0 <= pos) && (pos < sList->header.data) )
{
sList->node[0] = sList->header;
for(i=0; i<pos; i++)
{
current = sList->node[current].next;
}
object = sList->node[current].next; /***獲取的是元素位置****/
ret = (StaticListNode*)(sList->node[object].data); /***賦值結構體求出該位置的數據****/
}
return ret;
}
/****刪除元素具體實現和插入相仿***/
StaticListNode* StaticList_Delete(StaticList* list, int pos) // O(n)
{
TStaticList* sList = (TStaticList*)list;
StaticListNode* ret = NULL;
int current = 0;
int object = 0;
int i = 0;
if( (sList != NULL) && (0 <= pos) && (pos < sList->header.data) )
{
sList->node[0] = sList->header;
for(i=0; i<pos; i++)
{
current = sList->node[current].next;
}
object = sList->node[current].next;
sList->node[current].next = sList->node[object].next;
/****主要區別還是上面兩行代碼進行插入實現***/
sList->node[0].data--;
sList->header = sList->node[0];
sList->node[object].next = AVAILABLE;
ret = (StaticListNode*)(sList->node[object].data);
}
return ret;
}
/***主函數具體實現創建鏈表，插入、刪除、銷毀、獲取元素、等操作****/
int main(int argc, char *argv[])
{
StaticList* list = StaticList_Create(10);
int index = 0;
int i = 0;
int j = 1;
int k = 2;
int x = 3;
int y = 4;
int z = 5;
StaticList_Insert(list, &i, 1);
StaticList_Insert(list, &j, 3);
StaticList_Insert(list, &k, 2);
StaticList_Insert(list, &x, 5);
StaticList_Insert(list, &y, 4); /****剛開始對于這個賦值沒有理解后來明白了***/
StaticList_Insert(list, &z, 6); /****&i 也就是插入的元素的地址，這個地址是指向下一個元素的地址***/
for(index=0; index<StaticList_Length(list); index++)
{
int* p = (int*)StaticList_Get(list, index); /*****獲取元素**/
printf("%d\\n", *p);
}
printf("\\n");
while( StaticList_Length(list) > 0 )
{
int* p = (int*)StaticList_Delete(list, 0); /**刪除數據
**/
printf("%d\\n", *p);
}
printf("\\n");
StaticList_Insert(list, &x, 0);
StaticList_Insert(list, &y, 0); /***插入元素****/
StaticList_Insert(list, &z, 0);
printf("Capacity: %d Length: %d\\n", StaticList_Capacity(list),
StaticList_Length(list));
for(index=0; index<StaticList_Length(list); index++)
{
int* p = (int*)StaticList_Get(list, index);
printf("%d\\n", *p);
}
StaticList_Destroy(list); /**銷毀鏈表，不用的時候必須要進行操作不然會有內
泄露*****/
return 0;
}
好啦結束了，希望對于你會有一點幫助，我也是自己理解的難免會有都錯誤，請諒解 ！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
