一個(gè)靜態(tài)鏈表的C語(yǔ)言實(shí)現(xiàn)

2020-02-24 14:37:12

字體：大中小

供稿：網(wǎng)友

分享一段代碼，一個(gè)靜態(tài)鏈表的C語(yǔ)言實(shí)現(xiàn)，其中包含著一種簡(jiǎn)單的內(nèi)存管理策略，固定大小的鏈?zhǔn)焦芾恚枰呐笥芽梢詤⒖冀梃b，下面來(lái)一起看看吧。

在動(dòng)手之前我一直以為靜態(tài)鏈表和動(dòng)態(tài)鏈表沒(méi)有什么差別，細(xì)細(xì)一想才發(fā)現(xiàn)，原來(lái)靜態(tài)鏈表之中隱藏著一個(gè)非常值得討論的話題——內(nèi)存管理。

靜態(tài)鏈表的“靜態(tài)”二字是指內(nèi)存的來(lái)源為靜態(tài)內(nèi)存（通常用全局?jǐn)?shù)組）。與動(dòng)態(tài)鏈表不同，在靜態(tài)鏈表中節(jié)點(diǎn)內(nèi)存的申請(qǐng)與釋放都需要自行維護(hù)，由于這里是鏈表，也很容易想到將空余的節(jié)點(diǎn)鏈接起來(lái)形成一個(gè)free_list，每次需要時(shí)從free_list頭部取出一個(gè)節(jié)點(diǎn)，釋放時(shí)再將節(jié)點(diǎn)加到頭部，這樣就能夠非常容易的實(shí)現(xiàn)鏈表的其他操作。

// 靜態(tài)鏈表 的實(shí)現(xiàn)
?#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 ) { // 非空，先找到最后一個(gè)節(jié)點(diǎn)
???????? 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;? // 沒(méi)有結(jié)點(diǎn)，直接返回
???? if( ptr == idata ) { // 有一個(gè)節(jié)點(diǎn)
???????? pointer np = _alloc(val);
???????? nextof(np) = idata;
???????? idata = np;???
???????? return true;
???? }
???? else { // 其他情況，先找 ptr 的前驅(qū)，再插入
???????? 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 最前面的節(jié)點(diǎn) 移到 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 { // 找到最后一個(gè)節(jié)點(diǎn) p，以及它的前驅(qū) 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
?}

?/*
???? 測(cè)試程序：
?*/
?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;
?}

?//

測(cè)試結(jié)果如下：

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().

一個(gè)靜態(tài)鏈表的C語(yǔ)言實(shí)現(xiàn)就完成了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流。?

上一篇：C語(yǔ)言實(shí)現(xiàn)字符串?dāng)?shù)組排序的示例代碼

下一篇：C語(yǔ)言編程計(jì)算第二天日期示例代碼