随感而发

杂七杂八

统计

留言簿(13)

阅读排行榜

评论排行榜

用数组模拟指针和对象

今天学习了用没有指针和结构体的情况下用数组来实现类似的操作。他的思路和指针是一样的，只不过指针指向的是地址，他指向的是数组的下标。其他方式都一样。还有就是必须要自己实现分配和释放的函数，从数组中分配对象和释放对象。也要自己维持一张空闲数据表。
这也是书上的例子。废话少说，奉上源代码：
#include <stdio.h>
#include <stdlib.h>

int g_key[100];
int g_next[100];
int g_pre[100];
int g_free = 0;
int g_head = 0;


//初始化数据空间。
int Init()
{
    //将所有数据都添加到未分配表中
    for (int i = 0; i < 100; ++i)
    {
        g_next[i] = i + 1;
        g_pre[i] = i - 1;
    }

    g_free = 1;    //为分配的头开始指向1，0下标作为空处理。
    g_next[99] = 0;    //最后一个next指向0

    return 0;
}

//分配对象，返回对象的下标。
int AllocateObject()
{
    if (g_free == 0)    //如果没有未分配的空间，返回0
    {
        return 0;
    }

    int i = g_free;     //从未分配表中分配对象空间。
    g_free = g_next[g_free];    //把分配的空间从未分配表中分离。
    g_next[i] = 0;            //初始分配的空间
    g_pre[i] = 0;
    g_key[i] = 0xcccccccc;
    return i;    //返回空间下标。
}

//释放对象
int freeObject(int i)
{
    g_next[i]  = g_free;    //把它加入到未分配表中
    g_pre[i] = 0;
    g_free = i;
    return 1;
}

//判断链表是否为空
int IsEmpty()
{
    return g_head == 0;
}

//清空链表
int Clear()
{
    int i = g_next[g_head];
    while(g_head != 0)
    {
        i = g_next[g_head];
        freeObject(g_head);
        g_head = i;
    }
    return 1;
}

//插入数据到链表中
int Insert(int nData)
{
    int i = AllocateObject();
    g_key[i] = nData;
    g_pre[i] = 0;
    g_next[i] = g_head;
    g_head = i;
    return g_head;
}

//查找数据
bool Find(int nData)
{
    int i = g_head;
    while (i != 0)
    {
        if (g_key[i] == nData)
        {
            return true;
        }
        i = g_next[i];
    }

    return false;
}

//删除数据。
bool Delete(int nData)
{
    int i = g_head;
    while (i != 0)
    {
        if (g_key[i] == nData)
        {
            if (g_pre[i] != 0)
            {
                g_next[g_pre[i]] = g_next[i];
            }
            else
            {
                g_head = g_next[i];
            }

            if (g_next[i] != 0)
            {
                g_pre[g_next[i]] = g_pre[i];
            }

            freeObject(i);
            return true;
        }
        i = g_next[i];
    }
    return false;
}


int main()
{
    Init();
    //测试，
    for (int i = 0; i < 10; ++i)
    {
        Insert(i);    //插入数据
    }

    if (Find(5)) //查找数据
    {
        printf("Yes!\n");
    }
    if (!Find(11))
    {
        printf("No!\n");
    }

    while(!IsEmpty())    //逐一删除数据
    {
        printf("%d ", g_key[g_head]);
        Delete(g_key[g_head]);
    }
    printf("\n");
    for (int i = 0; i < 10; ++i)
    {
        Insert(i);
    }

    Clear();        //清空数据。
    if (IsEmpty())
    {
        printf("Empty!\n");
    }

    int i = g_free;
    while(i)
    {
        printf("%d ", i);
        i = g_next[i];
    }
    printf("\n");

    system("pause");
    return 0;
}

posted on 2009-05-04 18:37 shongbee2 阅读(871) 评论(2)  编辑 收藏 引用 所属分类: 数据结构和算法

评论

# re: 用数组模拟指针和对象 2009-05-04 18:41 陈梓瀚(vczh)

你可以尝试用数组去模拟一些struct……  回复  更多评论   

# re: 用数组模拟指针和对象 2009-05-04 19:37 shongbee2

@陈梓瀚(vczh)
哦。谢谢，不过书上只是提到了这些，我也觉得这个其实没有太大的意义，也就只是简单模拟了一下。您可以把它看做struct的，只不过他是三个数组合起来是一个struct,而不是传统的连续空间。呵呵。
有空去实践一下，谢谢哈。。呵呵。。
  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理