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