数据结构（复习） -------静态链表

时间：2015-12-19 16:21:58 阅读：251 评论：0 收藏：0 [点我收藏+]

技术分享

------------------------------------------------------------------------------------------------------------------------------------------------------------

静态链表相当于是用一个数组来实现线性表的链式存储结构，大概结构图如下技术分享

在静态链表中，每一个结点包含两部分内容，一部分是data（即有意义的数据），另一部分是cur（存储该元素下一个元素所在数组对应的下标）。

有几个特殊的结点：

首先是下标为0的结点中不包含有意义的数据，它的cur存储的是备用链表（即没有存储的数据的那些结点）第一个结点的下标。

其次是数组下标为1元素，它是首节点没有data, cur储存第一个有实际意义的节点数组下表；；；；

最后就是链表的最后一个元素（并不一定是数组的最后一个元素），链表最后一个元素的cur一般存放0，表示它后面的结点为空了。

-------------------------------------------------------------------------------------------------------------------------------------------------------

// 关于数据结构的总结与复习  Coding
//2.关于静态链表


#include <cstdio>
#include <cstdlib>
#define Maxsize 100
#define error 0
#define ok 1

//#define _OJ_

typedef struct Lnode
{
    int data;
    int cur;
} Lnode, Linklist[Maxsize];

void
Init_Space(Linklist Space)
//进行空间的初始化
{
    int i = 0;
    for (i = 0; i < Maxsize - 1; i++)
        Space[i].cur = i + 1;
    Space[Maxsize - 1].cur = 0;
}

int
Malloc_space(Linklist Space)
//space[0].cur  总是存储备用空间的第一个元素的数组下标
{
    int i;
    i = Space[0].cur;
    if(Space[i].cur != 0)
    Space[0].cur = Space[i].cur;
    return i;
}

void
Free_space(Linklist Space, int k)
{
    Space[k].cur = Space[0].cur;    Space[0].cur = k;
}

void
build_space(Linklist Space, int n)
//space[0].cur  总是存储备用空间的第一个元素的数组下标。
// 而space[1].cur总是存储第一个节点的数组下标       即space[1]为头节点
{
    int i, j;
    j = Malloc_space(Space);    //申请头节点    即space[1]为头节点

    for (i = 0; i < n; i++) {
        j = Malloc_space(Space);
        scanf("%d", &Space[j].data);
    }

    Space[j].cur = 0;            //最后一个节点为0    即null
}

int
List_Length(Linklist Space)
{
    int t = Space[1].cur, cnt = 0;
    while (t != 0) {
    t = Space[t].cur;
    cnt++;
   }
   printf("链表长度为：%d\n", cnt);
   return cnt;
}

int
List_insert(Linklist Space, int k, int data)
//对静态链表进行插入操作
{
    if(k < 1 && k > List_Length(Space) + 1) {
        printf("插入超限：\n");     return error;
    }

    int i, j = 0, t = Space[1].cur;
    i = Malloc_space(Space);
    Space[i].data = data;
    printf("从第%d个插入元素%d\n", k, data);

    if(k == 1) {
       Space[i].cur = Space[1].cur;    Space[1].cur = i;
     }//考虑如果插入第一个节点的情况

    for (j = 1; j < k - 1; j++)
    t = Space[t].cur;

    Space[i].cur = Space[t].cur;    Space[t].cur = i;
    //考虑到进行其他情况包括尾节点
}

int
List_Detele(Linklist Space, int k)
//对静态链表进行删除操作
{
    int t = Space[1].cur, j;
    if(k < 1 && k > List_Length(Space)) {
        printf("删除超限：\n");     return error;
    }
    printf("删除第%d个元素\n", k);

    if(k == 1) {
        // Free_space(Space, Space[1].cur);
        Space[1].cur = Space[Space[1].cur].cur;
    }                                        //考虑第一个节点

    if(k == List_Length(Space)) {
    for (j = 1; j < k - 1; j++)
    t = Space[t].cur;
    // Free_space(Space, Space[t].cur);
    Space[t].cur = 0;
    }                                       //考虑最后一个节点

    else {
    for (j = 1; j < k - 1; j++)
    t = Space[t].cur;
    // Free_space(Space, Space[t].cur);
    Space[t].cur = Space[Space[t].cur].cur;
   }
}


void
print(Linklist Space)
{
    printf("打印输出数据：\n");
    int t = Space[1].cur;
    while (t != 0) {
        printf("data == %d ", Space[t].data);
        printf("cur == %d\n", Space[t].cur);
        t = Space[t].cur;
    }
}

int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE JUDGE
       freopen("input.txt", "r", stdin);
       //freopen("output.txt", "w", stdout);
#endif
    

    int n, Len;

    Linklist Space;

    scanf("%d", &n);    //printf("n == %d\n", n);

    Init_Space(Space);

    build_space(Space, n);

    print(Space);

    List_Length(Space);

    // List_insert(Space, 2, 10);
    // List_insert(Space, 1, 11);    //进行边界值的检测
    // List_insert(Space, 3, 12);    //进行边界值的检测
    // List_insert(Space, 4, 13);

    print(Space);

    // List_Detele(Space, 2);
    // List_Detele(Space, 1);       //进行边界值的检测
    // List_Detele(Space, 3);       //进行边界值的检测

    print(Space);

    
    return 0;
}

----------------------------------------------------------------------------------------------------------------------------------------------------------

// 关于数据结构的总结与复习  Coding
//2.关于静态链表


#include <cstdio>
#include <cstdlib>
#define Maxsize 100
#define error 0
#define ok 1

//#define _OJ_

typedef struct Lnode
{
    int data;
    int cur;
} Lnode, Linklist[Maxsize];

void
Init_Space(Linklist Space)
//进行空间的初始化
{
    int i = 0;
    for (i = 0; i < Maxsize - 1; i++)
        Space[i].cur = i + 1;
    Space[Maxsize - 1].cur = 0;
}

int
Malloc_space(Linklist Space)
//space[0].cur  总是存储备用空间的第一个元素的数组下标
{
    int i;
    i = Space[0].cur;
    if(Space[i].cur != 0)
    Space[0].cur = Space[i].cur;
    return i;
}

void
Free_space(Linklist Space, int k)
{
    Space[k].cur = Space[0].cur;    Space[0].cur = k;
}

void
build_space(Linklist Space, int n)
//space[0].cur  总是存储备用空间的第一个元素的数组下标。
// 而space[1].cur总是存储第一个节点的数组下标       即space[1]为头节点
{
    int i, j;
    j = Malloc_space(Space);    //申请头节点    即space[1]为头节点

    for (i = 0; i < n; i++) {
        j = Malloc_space(Space);
        scanf("%d", &Space[j].data);
    }

    Space[j].cur = 0;            //最后一个节点为0    即null
}

int
List_Length(Linklist Space)
{
    int t = Space[1].cur, cnt = 0;
    while (t != 0) {
    t = Space[t].cur;
    cnt++;
   }
   printf("链表长度为：%d\n", cnt);
   return cnt;
}

int
List_insert(Linklist Space, int k, int data)
//对静态链表进行插入操作
{
    if(k < 1 && k > List_Length(Space) + 1) {
        printf("插入超限：\n");     return error;
    }

    int i, j = 0, t = Space[1].cur;
    i = Malloc_space(Space);
    Space[i].data = data;
    printf("从第%d个插入元素%d\n", k, data);

    if(k == 1) {
       Space[i].cur = Space[1].cur;    Space[1].cur = i;
     }//考虑如果插入第一个节点的情况

    for (j = 1; j < k - 1; j++)
    t = Space[t].cur;

    Space[i].cur = Space[t].cur;    Space[t].cur = i;
    //考虑到进行其他情况包括尾节点
}

int
List_Detele(Linklist Space, int k)
//对静态链表进行删除操作
{
    int t = Space[1].cur, j;
    if(k < 1 && k > List_Length(Space)) {
        printf("删除超限：\n");     return error;
    }
    printf("删除第%d个元素\n", k);

    if(k == 1) {
        // Free_space(Space, Space[1].cur);
        Space[1].cur = Space[Space[1].cur].cur;
    }                                        //考虑第一个节点

    if(k == List_Length(Space)) {
    for (j = 1; j < k - 1; j++)
    t = Space[t].cur;
    // Free_space(Space, Space[t].cur);
    Space[t].cur = 0;
    }                                       //考虑最后一个节点

    else {
    for (j = 1; j < k - 1; j++)
    t = Space[t].cur;
    // Free_space(Space, Space[t].cur);
    Space[t].cur = Space[Space[t].cur].cur;
   }
}


void
print(Linklist Space)
{
    printf("打印输出数据：\n");
    int t = Space[1].cur;
    while (t != 0) {
        printf("data == %d ", Space[t].data);
        printf("cur == %d\n", Space[t].cur);
        t = Space[t].cur;
    }
}

int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE JUDGE
       freopen("input.txt", "r", stdin);
       //freopen("output.txt", "w", stdout);
#endif
    

    int n, Len;

    Linklist Space;

    scanf("%d", &n);    //printf("n == %d\n", n);

    Init_Space(Space);

    build_space(Space, n);

    print(Space);

    List_Length(Space);

    // List_insert(Space, 2, 10);
    // List_insert(Space, 1, 11);    //进行边界值的检测
    // List_insert(Space, 3, 12);    //进行边界值的检测
    // List_insert(Space, 4, 13);

    print(Space);

    // List_Detele(Space, 2);
    // List_Detele(Space, 1);       //进行边界值的检测
    // List_Detele(Space, 3);       //进行边界值的检测

    print(Space);

    
    return 0;
}

数据结构（复习） -------静态链表

原文：http://www.cnblogs.com/airfand/p/5059225.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)