一個靜態鏈表的C語言實現

2020-02-24 14:37:12

字體：大中小

來源：轉載

供稿：網友

分享一段代碼，一個靜態鏈表的C語言實現，其中包含著一種簡單的內存管理策略，固定大小的鏈式管理，需要的朋友可以參考借鑒，下面來一起看看吧。

在動手之前我一直以為靜態鏈表和動態鏈表沒有什么差別，細細一想才發現，原來靜態鏈表之中隱藏著一個非常值得討論的話題——內存管理。

靜態鏈表的“靜態”二字是指內存的來源為靜態內存（通常用全局數組）。與動態鏈表不同，在靜態鏈表中節點內存的申請與釋放都需要自行維護，由于這里是鏈表，也很容易想到將空余的節點鏈接起來形成一個free_list，每次需要時從free_list頭部取出一個節點，釋放時再將節點加到頭部，這樣就能夠非常容易的實現鏈表的其他操作。

// 靜態鏈表 的實現
?#include 

?#define MAXN 16 // capacity of list.
?typedef int element; // element type.

?// define boolean type:
?typedef int bool;
?#define true -1
?#define false 0

?#define NPTR -1 // null pointer definition. can not between 0 to MAXN-1.
?typedef int pointer;

?#define DEBUGVAL(x) printf("%s: %d/n", #x, (x)); // a macro for debug.

?struct __node
?{
???? element data;
???? pointer next;
?}SLList[MAXN];
?pointer ifree, idata;

?#define nextof(p) SLList[p].next
?#define dataof(p) SLList[p].data

?#define _alloc(d) ifree; dataof(ifree)=(d); ifree != NPTR ? ifree=nextof(ifree) : NPTR
?#define _free(p)? nextof(p)=ifree; ifree = p

?void init()
?{
???? int i;
???? ifree = 0;
???? idata = NPTR;
???? for( i=0; i ???????? nextof(i) = i+1;
???? nextof(i) = NPTR;
?}

?// clear all nodes.
?void clear() { init(); }

?// push val to front.
?bool push_front(element val)
?{
???? pointer tmp, np;
???? if( ifree != NPTR ) {
???????? np = _alloc(val);
???????? nextof(np) = idata;
???????? idata = np;
???????? return true;
???? }
???? return false;
?}

?// push val to end of list.
?bool push_back(element val)
?{
???? if( idata == NPTR ) { // 空表，直接寫入
???????? idata = _alloc(val);
???????? nextof(idata) = NPTR;
???????? return true;
???? }
???? if( ifree != NPTR ) { // 非空，先找到最后一個節點
???????? pointer last = idata, np;
???????? while( nextof(last) != NPTR ) last = nextof(last);???????
???????? np = _alloc(val);
???????? nextof(np) = NPTR;
???????? nextof(last) = np;
???????? return true;
???? }
???? return false;
?}

?// insert val to after p pointed node.
?bool insert_after(pointer p, element val)
?{
???? if( ifree != NPTR && p != NPTR ) {
???????? pointer pn = _alloc(val);
???????? nextof(pn) = nextof(p);
???????? nextof(p)? = pn;???????
???????? return true;
???? }
???? return false;
?}

?// insert to the position in front of p.
?bool insert(pointer ptr, element val)
?{
???? if( ifree == NPTR ) return false;? // 沒有結點，直接返回
???? if( ptr == idata ) { // 有一個節點
???????? pointer np = _alloc(val);
???????? nextof(np) = idata;
???????? idata = np;???
???????? return true;
???? }
???? else { // 其他情況，先找 ptr 的前驅，再插入
???????? pointer p = idata;
???????? while(? p != NPTR ) {
???????????? if( nextof(p) == ptr ) { // find p -- the prev node of ptr.
???????????????? return insert_after(p, val); // insert val after p.???????????
???????????? }
??????????? p = nextof(p);
???????? }
???? }
???? return false;
?}

?// find element, return the prev node pointer.
?pointer find_prev(element val)
?{
???? pointer p = idata;
???? while(? p != NPTR ) {
???????? if( dataof( nextof(p) ) == val )
???????????? return p;
???????? p = nextof(p);
???? }
???? return NPTR;
?}

?// find element, return the node? pointer.
?pointer find(element val)
?{
???? pointer p = idata;
???? while(? p != NPTR ) {
???????? if( dataof(p) == val ) return p;
???????? p = nextof(p);
???? }
???? return NPTR;
?}

?// pop front element.
?void pop_front()
?{
???? if( idata != NPTR ) { // 將 data list 最前面的節點 移到 free list 上
?#if 0
???????? pointer p = idata;???????
???????? idata = nextof(idata); // idata = nextof(idata);
???????? nextof(p) = ifree;? // SLList[p].next = ifree;
???????? ifree = p;
?#else
???????? pointer p = idata;
???????? idata = nextof(idata);
???????? _free(p);
?#endif
???? }
?}

?// pop back element.
?void pop_back()
?{
???? if( idata == NPTR ) return;
???? if( nextof(idata) == NPTR ) { // only 1 node.
???????? nextof(idata) = ifree;
???????? ifree = idata;
???????? idata = NPTR;
???? }
???? else { // 找到最后一個節點 p，以及它的前驅 q.
???????? // TODO: find the last node p, and it's perv node q.
???????? pointer p = idata, q;
???????? while( nextof(p) != NPTR ) {
???????????? q = p;
???????????? p = nextof( p );
???????? }
???????? // remove *p to free list, update nextof(q) to NPTR.
???????? nextof(p) = ifree;
???????? ifree = p;
???????? nextof(q) = NPTR;
???? }
?}

?void show()
?{
???? pointer p = idata;
???? for( ; p != NPTR; p = nextof(p) ) {
???????? printf(" %3d ", dataof(p) );
???? }
???? printf("/n");
?}

?#define INFOSHOW
?void info()
?{
?#ifdef INFOSHOW
???? int i;???
???? DEBUGVAL(ifree);
???? DEBUGVAL(idata);
???? puts("====================/n"
???????? "index/tdata/tnext/n"
???????? "--------------------");
???? for(i=0; i???????? printf("%d/t%d/t%d/n", i, SLList[i].data, SLList[i].next);
???? }
???? puts("====================/n");
?#endif
?}

?/*
???? 測試程序：
?*/
?int main()
?{
???? int i;
???? init();

?#if 1? // push_front test:
???? puts("push_front test:");
???? for(i=0; i???????? push_front(2*i+1);
???????? show();???
???? }

???? puts("pop_front test:");
???? for(i=0; i???????? pop_front();
???????? show();
???? }
?#endif

?#if 1 // push_back test:
???? puts("push_back test:");
???? for(i=0; i???????? push_back((i+1)*10);
???????? show();???
???? }

???? puts("pop_back test:");
???? for(i=0; i???? {
???????? pop_back();
???????? show();
???? }
?#endif

?#if 1 // insert test:
???? puts("insert test:");
???? for(i=0; i???? {
???????? insert(idata, (i+1)*10);
???????? show();
???? }
???? puts("clear.../n");
???? clear();
?#endif

?#if 1 // insert_after test:
???? puts("insert_after test:");
???? push_back(-99);
???? for(i=0; i???????? insert_after(idata, i+1);
???????? show();
???? }
???? puts("clear.../n");
???? clear();
?#endif

?#if 1 // find test:
???? puts("find test:");
???? for(i=0; i???????? push_front(MAXN-i);
???????? push_back(MAXN/2-i);
???????? //show();
???? }
???? show();
???? info();
???? for(i=0; i???????? int val = rand()%(2*MAXN);
???????? pointer p = find(val);
???????? if( p != NPTR )
???????????? printf("%3d %3d found at %d/n", val, dataof(p), p);
???????? else
???????????? printf("%3d not found/n", val);
???? }
?#endif

?#if 1
???? puts("/nfind_prev test:");
???? for(i=0; i???????? int val = rand()%(2*MAXN);
???????? pointer p = find_prev(val);
???????? if( p != NPTR )
???????????? printf("%3d %3d found at %d's next./n", val, dataof(nextof(p)), p);
???????? else
???????????? printf("%3d not found/n", val);
???? }
?#endif

?#if 1 // find_prev and insert_after test:
???? clear();
???? puts("/nfind_prev and insert_after test:");
???? for(i=0; i???????? push_front(MAXN/2-i);
???? }
???? show();
???? for(i=0; i???????? int val = rand()%(2*MAXN), n=-(i+1);
???????? pointer p = find_prev(val);
???????? if( p != NPTR ) {
???????????? printf("insert %d to front of %d:", n, val);
???????????? insert_after(p, n);
???????????? show();
???????? }
???? }???
?#endif???

?#if 1 // find and insert test:
???? clear();
???? puts("/nfind and insert test:");
???? for(i=0; i???????? push_front(MAXN/2-i);
???? }
???? show();
???????? for(i=0; i???????? int val = rand()%MAXN, n=-(i+1);
???????? pointer p = find(val);
???????? if( p != NPTR ) {
???????????? printf("insert %d to after of %d:", n, val);
???????????? insert_after(p, n);
???????????? show();
???????? }
???? }
?#endif

???? puts("end of main().");???
???? return 0;
?}

?//

測試結果如下：

push_front test:
??? 1
??? 3??? 1
??? 5??? 3??? 1
??? 7??? 5??? 3??? 1
??? 9??? 7??? 5??? 3??? 1
?? 11??? 9??? 7??? 5??? 3??? 1
?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 25?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 27?? 25?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 29?? 27?? 25?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 29?? 27?? 25?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 29?? 27?? 25?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
pop_front test:
?? 27?? 25?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 25?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 23?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 21?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 19?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 17?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 15?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 13?? 11??? 9??? 7??? 5??? 3??? 1
?? 11??? 9??? 7??? 5??? 3??? 1
??? 9??? 7??? 5??? 3??? 1
??? 7??? 5??? 3??? 1
??? 5??? 3??? 1
??? 3??? 1
??? 1
?

push_back test:

?? 20
?? 20?? 30
?? 20?? 30?? 40
?? 20?? 30?? 40?? 50
?? 20?? 30?? 40?? 50?? 60
?? 20?? 30?? 40?? 50?? 60?? 70
?? 20?? 30?? 40?? 50?? 60?? 70?? 80
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130? 140
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130? 140? 150
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130? 140? 150? 160
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130? 140? 150? 160
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130? 140? 150? 160
pop_back test:
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130? 140? 150
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130? 140
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120? 130
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110? 120
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100? 110
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90? 100
?? 20?? 30?? 40?? 50?? 60?? 70?? 80?? 90
?? 20?? 30?? 40?? 50?? 60?? 70?? 80
?? 20?? 30?? 40?? 50?? 60?? 70
?? 20?? 30?? 40?? 50?? 60
?? 20?? 30?? 40?? 50
?? 20?? 30?? 40
?? 20?? 30
?? 20
?

insert test:

?? 10
?? 20?? 10
?? 30?? 20?? 10
?? 40?? 30?? 20?? 10
?? 50?? 40?? 30?? 20?? 10
?? 60?? 50?? 40?? 30?? 20?? 10
?? 70?? 60?? 50?? 40?? 30?? 20?? 10
?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 110? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 120? 110? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 130? 120? 110? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 140? 130? 120? 110? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 150? 140? 130? 120? 110? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 150? 140? 130? 120? 110? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
? 150? 140? 130? 120? 110? 100?? 90?? 80?? 70?? 60?? 50?? 40?? 30?? 20?? 10
clear...

insert_after test:
?-99??? 1
?-99??? 2??? 1
?-99??? 3??? 2??? 1
?-99??? 4??? 3??? 2??? 1
?-99??? 5??? 4??? 3??? 2??? 1
?-99??? 6??? 5??? 4??? 3??? 2??? 1
?-99??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 11?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 12?? 11?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 13?? 12?? 11?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 14?? 13?? 12?? 11?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 15?? 14?? 13?? 12?? 11?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 15?? 14?? 13?? 12?? 11?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
?-99?? 15?? 14?? 13?? 12?? 11?? 10??? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
clear...

find test:
?? 10?? 11?? 12?? 13?? 14?? 15?? 16??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1
ifree: -1
idata: 14
====================
index??? data??? next
--------------------
??? 16??? 1
??? 8??? 3
??? 15??? 0
??? 7??? 5
??? 14??? 2
??? 6??? 7
??? 13??? 4
??? 5??? 9
??? 12??? 6
??? 4??? 11
??? 11??? 8
??? 3??? 13
??? 10??? 10
??? 2??? 15
??? 9??? 12
??? 1??? -1
====================
?? 9 found at 14
?? 3 found at 11
?not found
?? 4 found at 9
?? 1 found at 15
? 12 found at 8
?not found
? 14 found at 4
?not found
? 16 found at 0
?? 9 found at 14
?not found
?not found
?not found
?? 9 found at 14
? 11 found at 10

find_prev test:
?not found
?? 6 found at 3's next.
?not found
?not found
?? 7 found at 1's next.
? 12 found at 10's next.
?not found
?not found
?? 4 found at 7's next.
?not found
? 13 found at 8's next.
?not found
?? 6 found at 3's next.
?not found
?? 7 found at 1's next.
?not found

find_prev and insert_after test:
??? 2??? 3??? 4??? 5??? 6??? 7??? 8
insert -4 to front of 8:?? 1??? 2??? 3??? 4??? 5??? 6??? 7?? -4??? 8
insert -5 to front of 3:?? 1??? 2?? -5??? 3??? 4??? 5??? 6??? 7?? -4??? 8
insert -8 to front of 6:?? 1??? 2?? -5??? 3??? 4??? 5?? -8??? 6??? 7?? -4??? 8

find and insert test:
??? 2??? 3??? 4??? 5??? 6??? 7??? 8
insert -2 to after of 3:?? 1??? 2??? 3?? -2??? 4??? 5??? 6??? 7??? 8
insert -6 to after of 8:?? 1??? 2??? 3?? -2??? 4??? 5??? 6??? 7??? 8?? -6
insert -7 to after of 5:?? 1??? 2??? 3?? -2??? 4??? 5?? -7??? 6??? 7??? 8?? -6
end of main().

一個靜態鏈表的C語言實現就完成了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。?

上一篇：C語言實現字符串數組排序的示例代碼

下一篇：C語言編程計算第二天日期示例代碼