数据结构——链表的游标实现(C语言)

上一篇博文我们用指针实现了链表,但是诸如BASIC和FORTRAN等许多语言都不支持指针。如果需要链表而又不能使用指针,这时我们可以使用游标(cursor)实现法来实现链表。

在链表的实现中有两个重要的特点:

  • 数据存储在一组结构体中。每一个结构体包含有数据以及指向下一个结构体的指针。
  • 一个新的结构体可以通过调用malloc而从系统全局内存(global memory)得到,并可以通过free而被释放。

游标法必须能够模仿实现这两条特性 。 下面给出实现代码:

#ifndef _CursorList_H

typedef int PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

void InitializeCursorSpace( void );

List MakeEmpty( List L );
int IsEmpty( const List L );
int IsLast( const Position P, const List L );
Position Find( ElementType X, const List L );
void Delete( ElementType X, List L );
Position FindPrevious( ElementType X, const List L);
void Insert( ElementType X, List L, Position P );
void DeleteList( const List L );
Position Header( const List L );
Position First( const List L);
Position Advance( const Position P );
ElementType Retrieve( const Position P );

#endif /*_CUrsor_H */

可以从上面的代码上看到,链表的游标实现跟链表的接口定义几乎是一样的。

下面放上实现代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CursorList.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define SpaceSize 10

typedef int Status;

struct Node
{
    ElementType Element;
    Position Next;
};

struct Node CursorSpace[ SpaceSize ];

/* initialize the CursorSpace */
void InitCursorSpace()
{
    int i;
    for(i = 0; i < SpaceSize; i++)
        CursorSpace[i].Next = i == SpaceSize-1 ? 0 : i+1;
}

static Position CursorAlloc(void)
{
    Position P;

    P = CursorSpace[0].Next;
    CursorSpace[0].Next = CursorSpace[P].Next;

    return P;
}

static void CursorFree(Position P)
{
    CursorSpace[P].Next = CursorSpace[0].Next;
    CursorSpace[0].Next = P;
}

/* Return true if L is empty */
Status IsEmpty(List L)
{
    if (CursorSpace[L].Next == 0)
        return TRUE;
    else
        return FALSE;
}

/* Return true if P is the last position in list L */
/* Parameter L is unused in this implementation */
Status IsLast(Position P, List L)
{
    if (CursorSpace[P].Next == 0)
        return TRUE;
    else
        return FALSE;
}

/* Return Position of X in L; 0 if not found */
/* Uses a header node */
Position Find(ElementType X, List L)
{
    Position P;

    P = CursorSpace[L].Next;
    while(P && CursorSpace[P].Element != X) {
        P = CursorSpace[P].Next;
    }
    return P;
}

/* Delete first occurrence of X from a list */
/* Assume use of a header node */
void Delete(ElementType X, List L)
{
    Position P, TmpCell;

    P = FindPrevious(X, L);
    if (!IsLast(P, L))
        TmpCell = CursorSpace[P].Next;
        CursorSpace[P].Next = CursorSpace[TmpCell].Next;
        CursorFree(TmpCell);
}

/* Find the front of the first X of The list */
/* Return 0 if not found */
Position FindPrevious(ElementType X, const List L)
{
    Position P;
    P = L;
    while(P && CursorSpace[CursorSpace[P].Next].Element != X)
    {
        P = CursorSpace[P].Next;
    }
    return P;
}

/* Insert(after legal position P) */
/* Header implementation assumed */
/* Parameter L is unused in this implemention */
void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;

    TmpCell = CursorAlloc();
    if (TmpCell == 0)
        printf("Out of space!\n");
    CursorSpace[TmpCell].Element = X;
    CursorSpace[TmpCell].Next = CursorSpace[P].Next;
    CursorSpace[P].Next = TmpCell;
}

void print_list(List L)
{
    List p = L;
    if (NULL == p)
    {
        printf("print_list: 链表为空!\n");
        return;
    }

    Position P;

    P = CursorSpace[L].Next;
    while(P != NULL) {
        printf("%d, \n", CursorSpace[P].Element);
        P = CursorSpace[P].Next;
    }
    printf("\n");
    return;
}

int main(int argc, char const *argv[])
{
    InitCursorSpace();
    List L = CursorAlloc();
    CursorSpace[L].Next = NULL;
    Insert(1, L, L);
    Insert(0, L, L);
    Insert(21, L, L);
    Insert(1201, L, L);
    Position P;
    P = Find(21, L);
    if (P)
        printf("找到元素: %d\n", CursorSpace[P].Element);
    else
        printf("未找到21元素\n");
    Delete(0, L);
    Delete(1, L);
    print_list(L);
    printf("检查链表是否为空: %d\n", IsEmpty(L));
    printf("Hello World\n");
    return 0;
}

实现过程比较简单,最后的main函数是对游标链表的测试。代码直接开箱即用,可以看到测试过程。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mukekeheart的iOS之旅

Java基础学习(学习IT企业必读的324个JAVA面试题.pdf 整理)

一、Java程序基础 javac 文件名.java    编译程序    java 类名               运行java程序 代码规范中,一下几点要注...

23590
来自专栏软件开发

JavaSE学习总结(四)——Java面向对象十分钟入门

面向对象编程(Object Oriented Programming,OOP)是一种计算机模拟人类的自然思维方式的编程架构技术,解决了传统结构化开发方法中客观...

31870
来自专栏一个会写诗的程序员的博客

JavaScript 的 async/await : async 和 await 在干什么

async 是“异步”的简写,而 await 可以认为是 async wait 的简写。 async 用于申明一个 function 是异步的,而 await...

8220
来自专栏青青天空树

C语言中把数字转换为字符串 【转】

在将各种类型的数据构造成字符串时,sprintf 的强大功能很少会让你失望。由于sprintf 跟printf 在用法上几乎一样,只是打印的目的地不同而已,前者...

5.4K60
来自专栏我和我大前端的故事

初探 TypeScript函数基本类型泛型接口类内置对象

前段时间有朋友和我推荐 TypeScript ,他说写起来特别爽,让我去试一试,那时候我还在那是啥高深莫测的东西。刚好那段时间忙,一直没有时间看。最近也很忙,还...

74220
来自专栏PHP在线

PHP Predefined Interfaces 预定义接口

SPL提供了6个迭代器接口: Traversable遍历接口(检测一个类是否可以使用 foreach 进行遍历的接口)Iterator迭代器接口(可在内部迭代自...

36650
来自专栏ShaoYL

iOS:swift :可选类型

31870
来自专栏ios 技术积累

Swif Array

使用加法赋值运算符(+=)也可以直接在数组后面添加一个或多个拥有相同类型的数据项:

11430
来自专栏技术小黑屋

Java中的字符串常量池

Java中字符串对象创建有两种形式,一种为字面量形式,如String str = "droid";,另一种就是使用new这种标准的构造对象的方法,如String...

22320
来自专栏blackheart的专栏

[C#1] 3-基元类型、引用类型和值类型、装箱拆箱

1.基元类型 编译器直接支持的数据类型成为基元类型。基元类型与FCL中的类型有直接的映射关系[int=Int32],这样我们可以简化的方式书写代码,并且编译后的...

22350

扫码关注云+社区

领取腾讯云代金券