C語言實現(xiàn)靜態(tài)鏈表的方法
在動手之前我一直以為靜態(tài)鏈表和動態(tài)鏈表沒有什么差別，細細一想才發(fā)現(xiàn)，原來靜態(tài)鏈表之中隱藏著一個非常值得討論的話題——內(nèi)存管理。
靜態(tài)鏈表的“靜態(tài)”二字是指內(nèi)存的來源為靜態(tài)內(nèi)存（通常用全局數(shù)組）。與動態(tài)鏈表不同，在靜態(tài)鏈表中節(jié)點內(nèi)存的申請與釋放都需要自行維護，由于這里是鏈表，也很容易想到將空余的節(jié)點鏈接起來形成一個free_list，每次需要時從free_list頭部取出一個節(jié)點，釋放時再將節(jié)點加到頭部，這樣就能夠非常容易的實現(xiàn)鏈表的其他操作。
// 靜態(tài)鏈表 的實現(xiàn)
#include <stdio.h>
#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 < MAXN-1; 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 ) { // 非空，先找到最后一個節(jié)點
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; // 沒有結(jié)點，直接返回
if( ptr == idata ) { // 有一個節(jié)點
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é)點 移到 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 { // 找到最后一個節(jié)點 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<MAXN; 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<MAXN+2; i++) {
push_front(2*i+1);
show();
}
puts("pop_front test:");
for(i=0; i<MAXN+2; i++) {
pop_front();
show();
}
#endif
#if 1 // push_back test:
puts("push_back test:");
for(i=0; i<MAXN+2; i++) {
push_back((i+1)*10);
show();
}
puts("pop_back test:");
for(i=0; i<MAXN+1; i++)
{
pop_back();
show();
}
#endif
#if 1 // insert test:
puts("insert test:");
for(i=0; i<MAXN+2; 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<MAXN+1; i++) {
insert_after(idata, i+1);
show();
}
puts("clear...\n");
clear();
#endif
#if 1 // find test:
puts("find test:");
for(i=0; i<MAXN/2; i++) {
push_front(MAXN-i);
push_back(MAXN/2-i);
//show();
}
show();
info();
for(i=0; i<MAXN; 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<MAXN; 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<MAXN/2; i++) {
push_front(MAXN/2-i);
}
show();
for(i=0; i<MAXN/2; 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<MAXN/2; i++) {
push_front(MAXN/2-i);
}
show();
for(i=0; i<MAXN/2; 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;
}
//
測試結(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().
相關(guān)文章
這篇文章主要介紹了c++ 預(yù)處理之正整型實現(xiàn)方法,需要的朋友可以參考下2017-07-07
這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)手寫Map(全功能)，文中的示例代碼講解詳細，對我們學(xué)習(xí)C語言有一定幫助，需要的可以參考一下2022-08-08
c++ 如何在libuv中實現(xiàn)tcp服務(wù)器
這篇文章主要介紹了c++ 如何在libuv中實現(xiàn)tcp服務(wù)器，幫助大家更好的理解和使用libuv，感興趣的朋友可以了解下2021-02-02
C++分析如何用虛析構(gòu)與純虛析構(gòu)處理內(nèi)存泄漏
虛析構(gòu)和純虛析構(gòu)共性：可以解決父類指針釋放子類對象，都需要有具體的函數(shù)實現(xiàn)；虛析構(gòu)和純虛析構(gòu)區(qū)別：如果是純虛析構(gòu)，該類屬于抽象類，無法實例化對象2022-08-08
C語言數(shù)據(jù)結(jié)構(gòu)之棧和隊列的實現(xiàn)及應(yīng)用
棧和隊列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實現(xiàn)方式。本文將以順序結(jié)構(gòu)實現(xiàn)棧，鏈表方式實現(xiàn)隊列，感興趣的小伙伴快跟隨小編一起學(xué)習(xí)一下吧2022-08-08
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱2022-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)一個簡易通訊錄，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要介紹了C++之list容器介紹及使用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要為大家詳細介紹了基于MFC和OpenCV實現(xiàn)角點檢測，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
這篇文章主要介紹了VC MFC非模態(tài)對話框的實現(xiàn)方法,有助于讀者加深對于模態(tài)對話框與非模態(tài)對話框的理解與運用,需要的朋友可以參考下2014-07-07