// 靜態(tài)鏈表 的實現
?#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 ) { // 非空，先找到最后一個節(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;? // 沒有結點，直接返回
???? if( ptr == idata ) { // 有一個節(jié)點
???????? 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 最前面的節(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.
???????? // 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().