在C中将链接列表实现为光标链接列表 [英] Implementing A Linked List As A Cursor Linked Lists In C

问题描述

如何在C中将链表作为游标实现编写.任务是将链表实现转换为数组实现.其主要思想是某些语言不支持指针.因此，需要找到一种可以替代指针的解决方案，并且该解决方案是将指针写为数组的索引.但是，我无法成功完成.游标链接列表的结构和函数原型如下:

How can I write a linked list as cursor implementation in C. The task is to convert a linked list implementation to an array implementation. The main idea of this is that some languages do not support pointers. So, there need to be find a solution that can replace pointers and this solution is to write pointers as indexes of arrays. However, I could not complete it successfully. The structure of the cursor linked list and the function prototypes are below:

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


struct Node
{
    int Element;
    Position    Next;
};

struct Node CursorSpace[ SpaceSize ];


void InitializeCursorSpace( void );

List MakeEmpty( List L );
int IsEmpty( List L );
int IsLast( Position P, List L );
void Delete( int X, List L );
Position FindMin( List L );
void Insert( int X, List L, Position P );
void DeleteList( List L );
void Display( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
int Retrieve( Position P );

这是有关内存分配的函数:

And here are to functions about memory allocation :

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;
}

推荐答案

最简单的方法是将链接指针替换为int索引，然后在通常访问该指针时跟随该索引. br/>
您将一个空闲节点列表用作列表的零元素-因此您可能需要将空间增加一，否则您将只能为100个元素的数组存储99个节点.希望您的MakeEmpty函数可以设置所有可用的指针！

从链接列表代码开始，并通过用索引访问替换指针进行工作-如果正确编写了MakeEmpty，这应该是一个非常简单的转换.

The easy way is to just replace your link pointers with int indexes - and then follow the index when you would normally access the pointer.

You are using a free node list as element zero of your list - so you will probably need to increase the space by one, or you will only be able to store 99 nodes for a 100 element array. Hopefully, your MakeEmpty function sets up all the free pointers!

Start with your linked list code, and work through replacing pointers with indexed accesses - it should be a pretty easy conversion if you have written MakeEmpty correctly.

这篇关于在C中将链接列表实现为光标链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！