【数据结构与算法分析(c语言)】 链表的游标实现 .h文件方法全实现

　　最近在学习<<数据结构与算法分析>>，实现了书上的链表的游标实现的代码，在这记录一下.

一、注意

　　使用前要因为代码使用ifndef 这个函数这个是为了防止头文件重返加载，他的标识是头文件名，命名规则为头文件名字首字母大写（我查资料也有说头文件名全大写），

前面加上"_"符号，在结尾处把“.”也要变成“_”，最后h大写。如我取的文件名是"cursor.h"，写在ifndef后就要改成"_Cursor_H".

二、代码

　　代码都有注释。

.h文件

#ifndef _Cursor_H

#define SpaceSize 11

typedef int PtrToNode;
typedef PtrToNode List;//表示表头的下标号 
typedef PtrToNode Position;



typedef char ElementType;

 void InitializeCursorSpace();
 
 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(List L);
 Position Header(const List L);
 Position First(const List L);
 Position Advance(const Position P);
 ElementType Retrieve(const Position P); 
 

#endif

struct Node
{
    ElementType Element;
    Position Next;
};

struct Node CursorSpace[SpaceSize];

.c文件

#include <stdio.h>
#include <stdlib.h>
#include "cursor.h"

int main(int argc, char *argv[]) {
    int i;
    InitializeCursorSpace();
    //创建列表L1 
    //为L1分配一个节点当头节点
    List L1=CursorAlloc();
    CursorSpace[L1].Element='h';
    CursorSpace[L1].Next=0;
    //为L1在头节点后面插入一个节点
    Insert('a',L1,L1);
    // 创建列表L2
    //为列表L2分配一个节点当头节点
    List L2=CursorAlloc();
    CursorSpace[L2].Element='h';
    CursorSpace[L2].Next=0;
    //为列表L1再插入一个节点
    Insert('b',L1,2);
    //为列表L2头节点后插入一个节点 
    Insert('1',L2,L2);
    //删除列表L1中值为'a'的节点
    Delete('a',L1); 
    //为列表L2插入一个节点
    Insert('2',L2,5); 
    //循环输出整个列表 
    for(i=0;i<SpaceSize;i++){
        printf("%d %c %d 
",i,CursorSpace[i].Element,CursorSpace[i].Next);
    }
    
    
    //通过列表L1和L2第一个节点的数值
    ElementType X1= Retrieve(First(L1));
    ElementType X2= Retrieve(First(L2));
    printf("列表L1第一个节点的数值：%c
列表L2第一个节点的数值：%c

",X1,X2);
    //删除列表L2
    DeleteList(L2);
    //使列表L1赋值为零 
    MakeEmpty(L1); 
    //循环输出整个列表 
    for(i=0;i<SpaceSize;i++){
        printf("%d %c %d 
",i,CursorSpace[i].Element,CursorSpace[i].Next);
    }
    return 0;
}
/*
初始化把节点全部加入freelist表 
*/
void InitializeCursorSpace(){
     int i;
     for(i=0;i<SpaceSize;i++){
         if(i<SpaceSize-1){
             CursorSpace[i].Next=i+1;
        }else{
            CursorSpace[i].Next=0;    
        }
        CursorSpace[i].Element='-';
     } 
 }
void FatalError(char * text){
    printf("%s
",text);
} 
/*
类似malloc函数分配内存资源
*/
Position CursorAlloc(){ 
    Position P;
    
    P=CursorSpace[0].Next;
    CursorSpace[0].Next=CursorSpace[P].Next;//把freelist的第一个下标为P的元素移除，表示被分配出使用中 
    
    return P;
}
/*
类似free函数回收内存资源
*/
void CursorFree(Position P){
    CursorSpace[P].Element='-';
    CursorSpace[P].Next = CursorSpace[0].Next;
    CursorSpace[0].Next=P;//把下标为P的元素插入freelist标表第一个元素中，表示空闲未被分配 
} 
/*
如果列表L为空返回true 
*/
int IsEmpty(List L){
    return CursorSpace[L].Next ==0;
 } 
/*
如果位置P是列表L最后一位元素则返回true 
*/ 
int IsLast(Position P,List L){
    return CursorSpace[P].Next == 0;
}
/*
返回值X在列表L中的位置，如果返回0则是没有找到 
*/
Position Find(ElementType X,List L){
    Position P;
    
    P=CursorSpace[L].Next;
    while(P&&CursorSpace[P].Element!=X){
        P=CursorSpace[P].Next;
    }
    
    return P;
} 
/*
从列表中返回值为X的节点前一个节点的位置,如果没有找到返回0 
*/
 Position FindPrevious(ElementType X,const List L)
 {
     Position P,TmpCell;
    P=Header(L);
    while(P&&CursorSpace[P].Element!=X){
        TmpCell=P;
        P=CursorSpace[P].Next;
    
    }
//    printf("
P=%d,TmpCell=%d
",P,TmpCell);
    if(P==0){//如果没有找则P=0 
        return P;
    }else{//如果找到了返回p的前一位 
        return TmpCell;
    }
 } 

/*
在列表L中删除第一次碰到的值为X的元素(可能存在多个) 
*/
void Delete(ElementType X ,List L){
    Position P,TmpCell;
    
    P = FindPrevious(X,L);
    if(!IsLast(P,L))//位置不在最后 AND 能找到 
    {
        TmpCell=CursorSpace[P].Next;
        CursorSpace[P].Next=CursorSpace[TmpCell].Next;
        CursorFree(TmpCell);
    } 
} 
/*
插入(位置P后面存在且合法) 
位置P是已经存在列表L中合法位置 ，向位置P后插入节点 
*/ 
void Insert(ElementType X,List L,Position P){
    Position TmpCell;
    TmpCell=CursorAlloc();
    if(TmpCell==0){
        FatalError("Out of space!!!");
    } 
    CursorSpace[TmpCell].Element=X;
    CursorSpace[TmpCell].Next=CursorSpace[P].Next;
    CursorSpace[P].Next=TmpCell;
} 
/*
删除整个列表L 
*/ 
void DeleteList(List L){
    Position P,TmpCell;
    P=Header(L);//找到头节点 
    while(P){//位置循环到最后 （P=0） 
        TmpCell=P;
        CursorSpace[P].Element='-'; 
        P=CursorSpace[P].Next;
        
        CursorFree(TmpCell);
    }    
}
/*
初始化一个列表的值，使其全部变成空 
*/
List MakeEmpty(List L){
    Position P;
    P=First(L);
    while(P){
        CursorSpace[P].Element='0';
        P=CursorSpace[P].Next;
    }
    return L;
}
/*
输入列表L,返回头节点的位置 
*/ 
Position Header(const List L){
    return L;//列表L就代表了头节点的位置 
}
/*
输入列表返回第一节点的位置 
*/ 
Position First(const List L){
    Position P=Header(L);
    return CursorSpace[P].Next;
} 
/*
通过输入位置P返回值X 
*/
ElementType Retrieve(const Position P){
     return CursorSpace[P].Element;
 }