[已解决]静态链表插入元素，打印结果总是只有第二个位置有数，且后面会覆盖前面

猪猪虾

//用C++新建一个类，实现静态表的初始化, 获取元素的值，插入，删除操作
//要求：
//1.数据类型可以存储字符串
//2.插入数据，是插入数据后，链表的数据顺序如下：
//"ZHAO"
//"QIAN"
//"SUN"
//"LI"
//"ZHOU"
//"WU"
//"ZHENG"
//"WANG"

#include<winuser.inl>
#include<stdio.h>
#include <cstdlib>
#include<string.h>

#define MAXSIZE 10
#define True 1
void InitialList(struct People* people);
int Getlength(struct People* space);
void InsertElement(struct People* space, int position, int element);
void DeleteElement(struct People* space, int position);
void Free(struct People* space, int position_index);
void printfInfo(struct People* space);


struct People 
{
        int data;
        int cur;
}people[MAXSIZE];
        

void InitialList(struct People *people)
{
        int i;
        for(i = 0; i < MAXSIZE - 1 ; i++)
        {
                people[i].cur = i + 1;
        }
        people[MAXSIZE - 1].cur = 0; 
}

int Getlength(struct People* space)
{
        int count = 0;
        //最后一个元素的游标是第一个存有元素的位置下标
        int i = space[MAXSIZE - 1].cur;
        while (i)
        {
                count++;
                i = space[i].cur;
        }
        return count;
}

int Get_first_spare_index(struct People* space)
{
        //首先需要判断备用链表是不是空，如果备用链表为空，则说明没有多余的空间可以插入元素
        //当前数组第一个元素的cur，是的备用链表的第一个元素的下标
        int i = space[0].cur;
        if (space[0].cur)  //如果备用链表非空
        {
                //把第一个备用元素从备用链表中剔除，i即是被剔除的那个备用元素的下标
                space[0].cur = space[i].cur;
        }
        return i;
}
//插入元素
void InsertElement(struct People* space, int position, int element)
{
        int spare_of_first_e, k ;
        k = MAXSIZE - 1;  //当前k是最后一个元素的下标
        if (position < 1 || position > MAXSIZE)
        {
                printf("out index\n");
        }
        else
        {
                spare_of_first_e = Get_first_spare_index(space);
                if (spare_of_first_e)
                {
                        space[spare_of_first_e].data = element;
                        //找到要插入位置的前一个位置元素的游标，将游标等于position，
                        //再将当前元素的游标指向原本位置的当前元素的下标
                        //由于游标和下标之间没有连续的对应关系，所以不能通过i++的形式来直接索引
                        for (int z = 1; z <= position - 1; z++) //对下标的索引
                        {
                                k = space[k].cur;
                        }
                        space[spare_of_first_e].cur = space[k].cur;
                        space[k].cur = spare_of_first_e;
                }
        }
}
        


//删除元素
void DeleteElement(struct People* space, int position)
{
        if (position < 1 || position > Getlength(space) + 1)
        {
                printf("out index\n");
        }
        else
        {
                int k ;
                k = MAXSIZE - 1;
                for (int z = 1; z <= position - 1; z++) //对下标的索引
                {
                        k = space[k].cur;  //获得要删除的元素的前一个元素的下标
                }
                space[k].cur = space[position].cur;
                Free(space, position);
        }
}

void Free(struct People* space, int position_index)
{
        //将指定下标的节点回收到备用链表
        space[position_index].cur = space[0].cur ;
        space[0].cur = position_index;
}

void printfInfo(struct People *space)
{
        printf("all element: \n");
        for (int i = 0; i < MAXSIZE; i++)
        {
                printf("%d ", space[i].data);
        }
        printf("\n");
}

int main()
{        
        struct People space[MAXSIZE];
        InitialList(space);
        InsertElement(space, 2, 1);
        InsertElement(space, 4, 10);
        printfInfo(space);

}

最佳答案

月排行榜 / 总排行榜

人造人

2021-3-6 20:57:43

好多的错误，我认为你这部分没有学好，建议重新学习一下这部分内容

//用C++新建一个类，实现静态表的初始化, 获取元素的值，插入，删除操作
//要求：
//1.数据类型可以存储字符串
//2.插入数据，是插入数据后，链表的数据顺序如下：
//"ZHAO"
//"QIAN"
//"SUN"
//"LI"
//"ZHOU"
//"WU"
//"ZHENG"
//"WANG"

//#include<winuser.inl>
#include<stdio.h>
#include <cstdlib>
#include<string.h>

#define MAXSIZE 10
#define True 1
void InitialList(struct People* people);
int Getlength(struct People* space);
void InsertElement(struct People* space, int position, int element);
void DeleteElement(struct People* space, int position);
void Free(struct People* space, int position_index);
void printfInfo(struct People* space);

/*
   struct People 
   {
   int data;
   int cur;
   }people[MAXSIZE];
   */
struct People 
{
    int data;
    int cur;
};

void InitialList(struct People *people)
{
    int i;
    for(i = 0; i < MAXSIZE - 1 ; i++)
    {
        people[i].cur = i + 1;
    }



    // 备用链表怎么结束？
    people[MAXSIZE - 2].cur = 0;



    people[MAXSIZE - 1].cur = 0; 
}

int Getlength(struct People* space)
{
    int count = 0;
    //最后一个元素的游标是第一个存有元素的位置下标
    int i = space[MAXSIZE - 1].cur;
    while (i)
    {
        count++;
        i = space[i].cur;
    }
    return count;
}

int Get_first_spare_index(struct People* space)
{
    //首先需要判断备用链表是不是空，如果备用链表为空，则说明没有多余的空间可以插入元素
    //当前数组第一个元素的cur，是的备用链表的第一个元素的下标
    int i = space[0].cur;
    if (space[0].cur)  //如果备用链表非空
    {
        //把第一个备用元素从备用链表中剔除，i即是被剔除的那个备用元素的下标
        space[0].cur = space[i].cur;
    }
    return i;
}
//插入元素
void InsertElement(struct People* space, int position, int element)
{
    int spare_of_first_e, k ;
    k = MAXSIZE - 1;  //当前k是最后一个元素的下标



    // position 等于 MAXSIZE 也不行吧？
    //if (position < 1 || position > MAXSIZE)
    if (position < 1 || position >= MAXSIZE)
    {
        printf("out index\n");
    }
    else
    {
        spare_of_first_e = Get_first_spare_index(space);
        if (spare_of_first_e)
        {
            space[spare_of_first_e].data = element;
            //找到要插入位置的前一个位置元素的游标，将游标等于position，
            //再将当前元素的游标指向原本位置的当前元素的下标
            //由于游标和下标之间没有连续的对应关系，所以不能通过i++的形式来直接索引
            for (int z = 1; z <= position - 1; z++) //对下标的索引
            {
                // 这里难道不需要判断一下吗？
                // 试想一下，当前链表只有3个元素，而插入的位置是5,那么这里将会是怎么样的一个状态呢？
                k = space[k].cur;
            }
            space[spare_of_first_e].cur = space[k].cur;
            space[k].cur = spare_of_first_e;
        }
    }
}



//删除元素
void DeleteElement(struct People* space, int position)
{
    // 这里为什么要加1呢？
    // 如果链表只有一个元素我要删除位置2呢？
    //if (position < 1 || position > Getlength(space) + 1)
    if (position < 1 || position > Getlength(space))
    {
        printf("out index\n");
    }
    else
    {
        int k ;
        k = MAXSIZE - 1;
        for (int z = 1; z <= position - 1; z++) //对下标的索引
        {
            k = space[k].cur;  //获得要删除的元素的前一个元素的下标
        }

        int f = space[k].cur;
        space[k].cur = space[f].cur;
        Free(space, f);

        // 下面这波操作是在做什么啊？
        //space[k].cur = space[position].cur;
        //Free(space, position);
    }
}

void Free(struct People* space, int position_index)
{
    //将指定下标的节点回收到备用链表
    space[position_index].cur = space[0].cur ;
    space[0].cur = position_index;
}

// 这个函数是要做什么？输出数组内容？不应该是输出链表内容吗？
//void printfInfo(struct People *space)
void printArray(struct People *space)
{
    printf("all element: \n");
    for (int i = 0; i < MAXSIZE; i++)
    {
        printf("%d ", space[i].data);
    }
    printf("\n");
}

void printElement(struct People *space)
{
    printf("all element: \n");
    int i = space[MAXSIZE - 1].cur;
    while(i)
    {
        printf("%d ", space[i].data);
        i = space[i].cur;
    }
    printf("\n");
}

int main()
{
    /*
    struct People space[MAXSIZE];
    InitialList(space);
    InsertElement(space, 2, 1);     // 在2的位置插入1？位置1怎么办？
    InsertElement(space, 4, 10);    // 位置3怎么办？
    printInfo(space);
    */


    struct People space[MAXSIZE];
    InitialList(space);
    InsertElement(space, 1, 5);
    InsertElement(space, 2, 9);
    InsertElement(space, 3, 7);
    InsertElement(space, 4, 8);
    printElement(space);
    DeleteElement(space, 3);
    DeleteElement(space, 2);
    printElement(space);
    return 0;
}

跳转到最佳答案楼层

人造人

好多的错误，我认为你这部分没有学好，建议重新学习一下这部分内容

//用C++新建一个类，实现静态表的初始化, 获取元素的值，插入，删除操作
//要求：
//1.数据类型可以存储字符串
//2.插入数据，是插入数据后，链表的数据顺序如下：
//"ZHAO"
//"QIAN"
//"SUN"
//"LI"
//"ZHOU"
//"WU"
//"ZHENG"
//"WANG"

//#include<winuser.inl>
#include<stdio.h>
#include <cstdlib>
#include<string.h>

#define MAXSIZE 10
#define True 1
void InitialList(struct People* people);
int Getlength(struct People* space);
void InsertElement(struct People* space, int position, int element);
void DeleteElement(struct People* space, int position);
void Free(struct People* space, int position_index);
void printfInfo(struct People* space);

/*
   struct People 
   {
   int data;
   int cur;
   }people[MAXSIZE];
   */
struct People 
{
    int data;
    int cur;
};

void InitialList(struct People *people)
{
    int i;
    for(i = 0; i < MAXSIZE - 1 ; i++)
    {
        people[i].cur = i + 1;
    }



    // 备用链表怎么结束？
    people[MAXSIZE - 2].cur = 0;



    people[MAXSIZE - 1].cur = 0; 
}

int Getlength(struct People* space)
{
    int count = 0;
    //最后一个元素的游标是第一个存有元素的位置下标
    int i = space[MAXSIZE - 1].cur;
    while (i)
    {
        count++;
        i = space[i].cur;
    }
    return count;
}

int Get_first_spare_index(struct People* space)
{
    //首先需要判断备用链表是不是空，如果备用链表为空，则说明没有多余的空间可以插入元素
    //当前数组第一个元素的cur，是的备用链表的第一个元素的下标
    int i = space[0].cur;
    if (space[0].cur)  //如果备用链表非空
    {
        //把第一个备用元素从备用链表中剔除，i即是被剔除的那个备用元素的下标
        space[0].cur = space[i].cur;
    }
    return i;
}
//插入元素
void InsertElement(struct People* space, int position, int element)
{
    int spare_of_first_e, k ;
    k = MAXSIZE - 1;  //当前k是最后一个元素的下标



    // position 等于 MAXSIZE 也不行吧？
    //if (position < 1 || position > MAXSIZE)
    if (position < 1 || position >= MAXSIZE)
    {
        printf("out index\n");
    }
    else
    {
        spare_of_first_e = Get_first_spare_index(space);
        if (spare_of_first_e)
        {
            space[spare_of_first_e].data = element;
            //找到要插入位置的前一个位置元素的游标，将游标等于position，
            //再将当前元素的游标指向原本位置的当前元素的下标
            //由于游标和下标之间没有连续的对应关系，所以不能通过i++的形式来直接索引
            for (int z = 1; z <= position - 1; z++) //对下标的索引
            {
                // 这里难道不需要判断一下吗？
                // 试想一下，当前链表只有3个元素，而插入的位置是5,那么这里将会是怎么样的一个状态呢？
                k = space[k].cur;
            }
            space[spare_of_first_e].cur = space[k].cur;
            space[k].cur = spare_of_first_e;
        }
    }
}



//删除元素
void DeleteElement(struct People* space, int position)
{
    // 这里为什么要加1呢？
    // 如果链表只有一个元素我要删除位置2呢？
    //if (position < 1 || position > Getlength(space) + 1)
    if (position < 1 || position > Getlength(space))
    {
        printf("out index\n");
    }
    else
    {
        int k ;
        k = MAXSIZE - 1;
        for (int z = 1; z <= position - 1; z++) //对下标的索引
        {
            k = space[k].cur;  //获得要删除的元素的前一个元素的下标
        }

        int f = space[k].cur;
        space[k].cur = space[f].cur;
        Free(space, f);

        // 下面这波操作是在做什么啊？
        //space[k].cur = space[position].cur;
        //Free(space, position);
    }
}

void Free(struct People* space, int position_index)
{
    //将指定下标的节点回收到备用链表
    space[position_index].cur = space[0].cur ;
    space[0].cur = position_index;
}

// 这个函数是要做什么？输出数组内容？不应该是输出链表内容吗？
//void printfInfo(struct People *space)
void printArray(struct People *space)
{
    printf("all element: \n");
    for (int i = 0; i < MAXSIZE; i++)
    {
        printf("%d ", space[i].data);
    }
    printf("\n");
}

void printElement(struct People *space)
{
    printf("all element: \n");
    int i = space[MAXSIZE - 1].cur;
    while(i)
    {
        printf("%d ", space[i].data);
        i = space[i].cur;
    }
    printf("\n");
}

int main()
{
    /*
    struct People space[MAXSIZE];
    InitialList(space);
    InsertElement(space, 2, 1);     // 在2的位置插入1？位置1怎么办？
    InsertElement(space, 4, 10);    // 位置3怎么办？
    printInfo(space);
    */


    struct People space[MAXSIZE];
    InitialList(space);
    InsertElement(space, 1, 5);
    InsertElement(space, 2, 9);
    InsertElement(space, 3, 7);
    InsertElement(space, 4, 8);
    printElement(space);
    DeleteElement(space, 3);
    DeleteElement(space, 2);
    printElement(space);
    return 0;
}