数据结构-静态链表 （C++代码）

解题思路:





注意事项:





参考代码:

麻烦的要死的题目：

#include <stdio.h>  
#include <string.h>  
  
#define MAXSIZE 11                        // 静态链表的长度  
typedef char ElemType[8];        // 元素的类型，规定姓氏不超过7个字符  
  
typedef struct  
{  
    ElemType data;                        // 节点中的数据  
    int cur;                                // 下一个节点的下标（相当于指针）  
} NodeType;                                       // 节点类型  
  
NodeType space[MAXSIZE];        // 用来存储节点的数组，相当于一般链表中的内存，  
// 只是那个内存是系统分配的，我们看不到  
  
typedef struct  
{  
    int elem;                                // 静态链表存储空间基址（起始元素的下标）  
    int length;                                // 静态链表中的元素数目  
    int listSize;                        // 静态链表当前的长度，可容纳元素数目  
} SLinkList;                                       // 静态链表类型的定义，和一般的链表类似  
  
int LocateElem_SL(SLinkList& S, ElemType e)  
{  
    // 在静态单链线性表L中查找第1个值为e的元素。  
    // 若找到，则返回它在L中的位序，否则返回0。  
    int i;  
    i = S.elem; // i指示表中第一个结点  
    while (i && strcmp(space[i].data, e))  
        i = space[i].cur; // 在表中顺链查找  
    return i;  
}  
  
void InitSpace_SL()  
{  
    // 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，  
    // "0"表示空指针  
    memset(space, 0 ,sizeof(space));  
    for (int i = 0; i < MAXSIZE - 1; ++i)  
        space[i].cur = i + 1;  
    space[MAXSIZE - 1].cur = 0;  
}  
  
int Malloc_SL()  
{  
    /* 若备用链表非空,则返回分配的结点下标(备用链表的第一个结点),否则返回0 */  
    int i = space[0].cur;  
    if (i) /* 备用链表非空 */  
        space[0].cur = space[i].cur;/* 备用链表的头结点指向原备用链表的第二个结点 */  
    return i;/* 返回新开辟结点的坐标 */  
}  
  
void Free_SL(int k)  
{/* 将下标为k的空闲结点回收到备用链表(成为备用链表的第一个结点) */  
    space[k].cur = space[0].cur;/* 回收结点的＂游标＂指向备用链表的第一个结点 */  
    space[0].cur = k; /* 备用链表的头结点指向新回收的结点 */  
}  
  
void Insert_SL(SLinkList& S, int i, ElemType e)  
{  
    // 往静态链表S中的第 i 个位置前插入e  
    int cur = S.elem;                // 指向静态链表中的第一个节点  
    int j=0;  
    int newNodeIndex;                // 存储新分配的节点下标  
    while(j < i-1)                         // 寻找第 i-1 个节点  
    {  
        cur = space[cur].cur;  
        ++j;  
    }  
    newNodeIndex = Malloc_SL();        // 分配新的节点  
    strcpy(space[newNodeIndex].data,e);        // 在新的节点中存入数据  
    space[newNodeIndex].cur = 0;                // 指针为空，这一点很重要  
    space[newNodeIndex].cur = space[cur].cur;        // 插入静态链表中  
    space[cur].cur = newNodeIndex;  
    S.length++;                        // 插入后静态链表长度加1  
}  
  
void Delete_SL(SLinkList& S, int i)  
{  
    // 删除静态链表中的第 i 个节点  
    int cur = S.elem;                // 指向静态链表中的第一个节点  
    int j=0;  
    int delCur;                                // 存储待删除节点的下标  
    while(j < i-1)                         // 寻找第 i-1 个节点  
    {  
        cur = space[cur].cur;  
        ++j;  
    }  
    delCur = space[cur].cur;                // 找到待删除节点的下标  
    space[cur].cur = space[delCur].cur;        // 删除节点  
    Free_SL(delCur);                        // 释放节点  
    S.length--;                        // 删除后静态链表长度减1  
}  
  
void CreateList_SL(SLinkList& S)         // 创建静态链表  
{  
    S.elem = Malloc_SL();                        // 分配头结点的指针  
    space[S.elem].cur = 0;  
    S.length = 0;  
    S.listSize = 9;  
}  
  
void Show_space()  
{  
    // 将静态链表中所有的节点显示出来  
    int i;  
    for(i=0; i<MAXSIZE; i++)  
    {  
        printf("%-8s%2d\n", space[i].data, space[i].cur);  
    }  
}  
  
int main()  
{  
  
    SLinkList S;                // 定义静态链表  
    char str[10];                // 用来获得指令  
    int a;                                // 存储位置  
    ElemType e;                        // 存储元素  
    InitSpace_SL();                // 初始化备用链表  
    CreateList_SL(S);        // 创建静态链表  
    while(scanf("%s", str) != EOF)  
    {  
        if(strcmp(str, "insert") == 0)                         // 插入元素  
        {  
            scanf("%d%s", &a, e);  
            Insert_SL(S, a, e);  
        }  
        else if(strcmp(str, "delete") == 0)          // 删除元素  
        {  
            scanf("%d", &a);  
            Delete_SL(S, a);  
        }  
        else if(strcmp(str, "search") == 0)          // 搜索元素  
        {  
            scanf("%s", e);  
            printf("%2d\n********************\n", LocateElem_SL(S, e));  
        }  
        else if(strcmp(str, "show") == 0)                  // 显示静态链表状态  
        {  
            Show_space();  
            puts("********************");                                                // 注意空一行  
        }  
    }  
  
    return 0;  
}