데이터 구조 - 링크 의 커서 구현 (C 언어)
링크 의 실현 에 있어 두 가지 중요 한 특징 이 있다.
4. 567917. 데 이 터 는 구조 체 에 저장 된다.모든 구조 체 패 키 지 는 데이터 와 다음 구조 체 를 가리 키 는 지침 을 포함 하고 있다
4. 567917. 새로운 구조 체 는 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
#include
#include
#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!
");
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: !
");
return;
}
Position P;
P = CursorSpace[L].Next;
while(P != NULL) {
printf("%d,
", CursorSpace[P].Element);
P = CursorSpace[P].Next;
}
printf("
");
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
", CursorSpace[P].Element);
else
printf(" 21
");
Delete(0, L);
Delete(1, L);
print_list(L);
printf(" : %d
", IsEmpty(L));
printf("Hello World
");
return 0;
}
실현 과정 이 비교적 간단 하고 마지막 main 함 수 는 커서 링크 에 대한 테스트 입 니 다.코드 는 직접 상 자 를 열 면 바로 사용 할 수 있 고 테스트 과정 을 볼 수 있다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.