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)文章
visual?studio?2022一個不易發(fā)現(xiàn)的問題
本文主要介紹了visual?studio?2022一個不易發(fā)現(xiàn)的問題，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
本文主要介紹了C語言楊氏矩陣中查找元素的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
C語言的最大特點是：功能強、使用方便靈活。C編譯的程序?qū)φZ法檢查并不象其它高級語言那么嚴格，這就給編程人員留下“靈活的余地”，但還是由于這個靈活給程序的調(diào)試帶來了許多不便，尤其對初學(xué)C語言的人來說，經(jīng)常會出一些連自己都不知道錯在哪里的錯誤2013-07-07
今天小編就為大家分享一篇關(guān)于Lua和C/C++互相調(diào)用實例分析，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
C++實現(xiàn)LeetCode(171.求Excel表列序號)
這篇文章主要介紹了C++實現(xiàn)LeetCode(171.求Excel表列序號),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
使用Objective-C獲取IPHONE手機IMSI序列號
這篇文章主要介紹了使用Objective-C獲取IPHONE手機IMSI序列號的方法以及通過IMSI序列號獲取運營商、手機號的方法，非常的實用，有需要的小伙伴可以參考下。2015-04-04
這篇文章主要介紹了C++雙向循環(huán)列表,實例分析了C++雙向循環(huán)列表的創(chuàng)建、輸出、添加、刪除、移動的相關(guān)操作技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細介紹了C語言實現(xiàn)通訊錄小功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
這篇文章主要介紹了C++ bitset的簡單使用示例，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2020-11-11
C語言實現(xiàn)宿舍管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細介紹了C語言實現(xiàn)宿舍管理系統(tǒng)課程設(shè)計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03