// 静态链表 的实现
#include <stdio.h>
#define DEBUGVAL(x) printf("%s: %d\n", #x, (x));
// define boolean type:
typedef int bool;
#define true -1
#define false 0
#define MAXN 16
#define NPTR -1
typedef int Type;
typedef int pointer;
struct __node
{
Type data;
int next;
}SLList[MAXN];
#define nextof(p) SLList[p].next
#define dataof(p) SLList[p].data
#define _alloc(d) ifree; dataof(ifree)=(d); ifree=nextof(ifree)
#define _free(p) nextof(p)=ifree; ifree = p
int ifree, idata;
void init()
{
int i;
ifree = 0;
idata = NPTR;
for( i=0; i < MAXN-1; i++)
SLList[i].next = i+1;
SLList[i].next = NPTR;
}
bool push_front(Type val)
{
pointer tmp, np;
if( ifree != NPTR ) {
#if 0
SLList[ifree].data = val; // 保存新值
// free list 最前面的节点移到 data list上
tmp = idata;
idata = ifree;
ifree = SLList[ifree].next; // 更新 ifree
SLList[idata].next = tmp;
#else
np = _alloc(val);
nextof(np) = idata;
idata = np;
#endif
return true;
}
return false;
}
bool push_back(Type val)
{
if( idata == NPTR ) { // 顺序不能错！
dataof(ifree) = val;
idata = ifree;
ifree = nextof(ifree);
nextof(idata) = NPTR;
return true;
}
if( ifree != NPTR ) {
pointer last = idata, newn = ifree;
dataof(ifree) = val;
while( nextof(last) != NPTR ) last = nextof(last);
SLList[last].next = ifree;
ifree = SLList[ifree].next;
SLList[newn].next = NPTR;
return true;
}
return false;
}
bool insert_after(pointer p, Type val)
{
if( ifree != NPTR && p != NPTR ) {
pointer pn = ifree; // point to new node.
#if 1
dataof(ifree) = val; // write data.
ifree = nextof(ifree); // move ifree, update free list.
#else
SLList[ifree].data = val; // write data.
ifree = SLList[ifree].next; // move ifree, update free list.
#endif
nextof(pn) = nextof(p);
nextof(p) = pn;
return true;
}
return false;
}
// insert to the position in front of p.
bool insert(pointer ptr, Type val)
{
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;
}
pointer find_prev(Type val)
{
pointer p = idata;
while( p != NPTR ) {
if( dataof( nextof(p) ) == val )
return p;
p = nextof(p);
}
return NPTR;
}
pointer find(Type val)
{
pointer p = idata;
while( p != NPTR ) {
if( dataof(p) == val ) return p;
p = nextof(p);
}
return NPTR;
}
void pop_front()
{
if( idata != NPTR ) { // 将 data list 最前面的节点 移到 free list 上
#if 0
pointer p = idata;
idata = nextof(idata); // idata = SLList[idata].next;
nextof(p) = ifree; // SLList[p].next = ifree;
ifree = p;
#else
pointer p = idata;
idata = nextof(idata);
_free(p);
#endif
}
}
void pop_back()
{
if( idata == NPTR ) return;
if( nextof(idata) == NPTR ) { // only 1 node.
nextof(idata) = ifree;
ifree = idata;
idata = NPTR;
}
else { // 找到最后一个节点 p，以及它的前驱 q.
// TODO: find the lase nod 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 = SLList[p].next) {
printf(" %3d ", SLList[p].data );
}
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
puts("push_front test:");
for(i=0; i<MAXN+2; i++) {
push_front(2*i+1);
show();
}
info();
puts("pop_front test：");
for(i=0; i<MAXN+2; i++)
{
pop_front();
show();
}
info();
#endif
#if 1
puts("push_back test:");
for(i=0; i<MAXN/2+4; i++) {
push_back((i+1)*10);
show();
}
info();
puts("pop_back test:");
for(i=0; i<MAXN+1; i++)
{
pop_back();
show();
}
info();
#endif
#define POPTC 5
#if 0
puts("push_back test:");
for(i=0; i<POPTC; i++)
{
push_back(88+i);
show();
}
#endif
#if 1
push_back(100);
puts("insert_after test:");
for(i=0; i<POPTC; i++)
{
insert_after(idata, -(i+1));
show();
}
#endif
puts("end of main.");
return 0;
}
//
