C语言实现静态链表的方法_C 语言

在动手之前我一直以为静态链表和动态链表没有什么差别，细细一想才发现，原来静态链表之中隐藏着一个非常值得讨论的话题——内存管理。

静态链表的“静态”二字是指内存的来源为静态内存（通常用全局数组）。与动态链表不同，在静态链表中节点内存的申请与释放都需要自行维护，由于这里是链表，也很容易想到将空余的节点链接起来形成一个free_list，每次需要时从free_list头部取出一个节点，释放时再将节点加到头部，这样就能够非常容易的实现链表的其他操作。

复制代码 代码如下:

// 静态链表 的实现
 #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 ) { // 非空，先找到最后一个节点
         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 ) { // 有一个节点
         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 最前面的节点 移到 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 { // 找到最后一个节点 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<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;
 }

 //

测试结果如下：

复制代码 代码如下:

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().

时间： 2024-10-02 05:08:44

C语言实现静态链表的方法_C 语言的相关文章

C语言实现颠倒栈的方法_C 语言

本文实例讲述了C语言实现颠倒栈的方法,很实用的技巧.分享给大家供大家参考之用. 具体实现方法如下: #include <iostream> #include <iterator> #include <algorithm> #include <vector> #include <stack> using namespace std; void initializeStack(stack<int> &st) { for(int i

C语言字符串原地压缩实现方法_C 语言

本文实例讲述了C语言字符串原地压缩的实现方法,对于学习字符串操作的算法设计有不错的借鉴价值.分享给大家供大家参考.具体方法如下: 字符串原地压缩示例: "eeeeeaaaff"压缩为"e5a3f2" 具体功能代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <iterator> #include <

C语言实现求定积分的方法_C 语言

本文实例讲述了C语言实现求定积分的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: #include <cmath>  #include <cstdio> #define ACC 1000 float solve(float (*p)(float),float up,float down,int acc); float fun_exp(float x); float fun_qua(float x); void main(){ char selection; f

深入分析C语言分解质因数的实现方法_C 语言

首先来看一个最简单的C语言实现质因数分解的列子: #include <stdio.h> void main( ) { int data, i = 2; scanf("%d", &data); while(data > 1) { if(data % i == 0) { printf("%d ", i); data /= i; } else i++; } } 原理&&方法把一个合数分解为若干个质因数的乘积的形式,即求质因数的过程

使用C语言实现CRC校验的方法_C 语言

CRC(Cyclic Redundancy Check)校验应用较为广泛,以前为了处理简单,在程序中大多数采用LRC(Longitudinal Redundancy Check)校验,LRC校验很好理解,编程实现简单.用了一天时间研究了CRC的C语言实现,理解和掌握了基本原理和C语言编程.结合自己的理解简单写下来. 1.CRC简介 CRC检验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个检验码r位(就是CRC码),附在信息后面,构成一个新的二进制码序列数

c语言打开文件函数使用方法_C 语言

ANSI C规定文件打开用函数fopen,关闭为fclose. 1.调用方式通常为: 复制代码 代码如下: FILE *fp;fp=fopen(文件名, 打开方式); 2.参数说明: 文件名: 形如"myfile.dat"."F:\data\myfile.dat"等等; 打开方式:"r"(只读) 为输入打开一个文本文件"w"(只写) 为输出打开一个文本文件"a"(追加) 向文件文件尾添加数据"rb

排列和组合算法的实现方法_C语言经典案例_C 语言

排列和组合算法是考查递归的常见算法,这两种算法能用递归简洁地实现. 本人在经过多次摸索和思考之后,总结如下,以供参考. 程序代码如下: #include <stdio.h> #include <stdlib.h> char array[] = "abcd"; #define N 4 #define M 3 int queue[N] = {0}; int top = 0; int flag[N] = {0}; void perm(int s, int n) { i

详解C++的JSON静态链接库JsonCpp的使用方法_C 语言

JsonCpp部署方法:在http://sourceforge.net/projects/jsoncpp/中下载最新版本的jsoncpp库源码. 之后将jsoncpp-src-版本号-tar.gz解压出来,打开makefiles中的jsoncpp.sln进行编译,之后build文件夹下的vs71\debug\lib_json中会有一个.lib静态链接库. JsonCpp主要包含三种类型的class:Value Reader Writer. jsoncpp中所有对象.类名都在namespace j

C++链表倒序实现方法_C 语言

本文通过一个实例展示了C++实现链表倒序的方法,对于C++数据结构的学习有很好的参考借鉴价值.具体方法如下: 首先,C++链表倒序的难点在于如何一个个地修改.虽然不是数组,但是大概思想是一样的,所以可以用一个for循序,一个游标对应for循环里面的 i,只不过要记得前一个节点和后一个节点,尤其是后一个,因为修改之后就访问不到后面的,所以要记录.for每一个循环只改变所指向的那个节点的指针,这样既不会乱套了. 用一个for循环就非常好理解了,实例代码如下所示: #include <iostream