论坛 › 数据结构与算法 › 静态链表插入元素，打印结果总是只有第二个位置有数，且后面会覆盖前面

猪猪虾 发表于 2021-3-5 11:29:10

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

//用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;
       

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

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

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

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

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

int main()
{       
        struct People space;
        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;
   */
struct People
{
    int data;
    int cur;
};

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



    // 备用链表怎么结束？
    people.cur = 0;



    people.cur = 0;
}

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

int Get_first_spare_index(struct People* space)
{
    //首先需要判断备用链表是不是空，如果备用链表为空，则说明没有多余的空间可以插入元素
    //当前数组第一个元素的cur，是的备用链表的第一个元素的下标
    int i = space.cur;
    if (space.cur)//如果备用链表非空
    {
      //把第一个备用元素从备用链表中剔除，i即是被剔除的那个备用元素的下标
      space.cur = space.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.data = element;
            //找到要插入位置的前一个位置元素的游标，将游标等于position，
            //再将当前元素的游标指向原本位置的当前元素的下标
            //由于游标和下标之间没有连续的对应关系，所以不能通过i++的形式来直接索引
            for (int z = 1; z <= position - 1; z++) //对下标的索引
            {
                // 这里难道不需要判断一下吗？
                // 试想一下，当前链表只有3个元素，而插入的位置是5,那么这里将会是怎么样的一个状态呢？
                k = space.cur;
            }
            space.cur = space.cur;
            space.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.cur;//获得要删除的元素的前一个元素的下标
      }

      int f = space.cur;
      space.cur = space.cur;
      Free(space, f);

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

void Free(struct People* space, int position_index)
{
    //将指定下标的节点回收到备用链表
    space.cur = space.cur ;
    space.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.data);
    }
    printf("\n");
}

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

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


    struct People space;
    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;
}

查看完整版本: 静态链表插入元素，打印结果总是只有第二个位置有数，且后面会覆盖前面