数据结构实践——初始化顺序表怎么就内存溢出了?

  有学生调程序,是要建顺序表。
  他的程序是这样的:

#include <stdio.h>
#include <malloc.h>

#define MaxSize 50    //Maxsize将用于后面定义存储空间的大小
typedef int ElemType;  //ElemType在不同场合可以根据问题的需要确定,在此取简单的int
typedef struct
{
    ElemType data[MaxSize];  //利用了前面MaxSize和ElemType的定义
    int length;
} SqList;

//声明自定义函数
SqList InitList(SqList *L);   //初始化顺序表
void ListInsert(SqList *L,int i,int b);  //插入函数
void DispList(SqList *L);    //输出函数
bool ListEmpty(SqList *L);//判定是否为空表ListEmpty(L)

int main()
{
    SqList *sq;
    InitList(sq);
    ListInsert(sq, 1, 5);
    ListInsert(sq, 2, 3);
    ListInsert(sq, 1, 4);
    DispList(sq);
    return 0;
}

//输出线性表DispList(L)
void DispList(SqList *L)
{
    int i;
    if (ListEmpty(L))
        return;
    for (i=0; i<L->length; i++)
        printf("%d ",L->data[i]);
    printf("\n");
}

//判定是否为空表ListEmpty(L)
bool ListEmpty(SqList *L)
{
    return(L->length==0);
}

//初始化顺序表InitList(*L)
SqList InitList(SqList *L)
{
    L=(SqList *)malloc(sizeof(SqList));//这里申请了结点空间
    L->length=0;
    return *L;
}

void ListInsert(SqList *L,int i,int b)   //插入函数
{
    int j,k;

    if(i<1)
    {
        printf("插入位置非法/n");
    }
    for(j=L->length; j>i; j--)
    {
        L->data[j]=L->data[j-1];
    }
    L->data[i]=b;
    L->length++;
}

  运行结果是这样的:

  他找我帮忙。基本可以断定,内存使用不当,有溢出。
  看一下编译提示的信息,有一个警告:
  D:\CB\DS\main.cpp|21|warning: ‘sq’ is used uninitialized in this function [-Wuninitialized]|
  说在21行,sq未经初始化就使用了。通俗的说法,野指针。
  围绕着sq找。在main()函数中有:

    SqList *sq;
    InitList(sq);

  这里在调用InitList时,实际参数sq就是野指针。但这还不是出问题的关键,看InitList函数的定义是:

//初始化顺序表InitList(*L)
SqList InitList(SqList *L)
{
    L=(SqList *)malloc(sizeof(SqList));//这里申请了结点空间
    L->length=0;
    return *L;
}

  调用时,L得到的是野指针,但在函数里为其分配空间了。但调用完,这个地址并未返回到main函数中。调用完InitList,sq仍然还是野指针。这是关键!
  沿这个思路,希望能将分配的空间地址能返回给main函数。return *L就不合适了,return L是返回地址。于是,函数定义改为:

//初始化顺序表InitList(*L)
SqList *InitList(SqList *L)
{
    L=(SqList *)malloc(sizeof(SqList));//这里申请了结点空间
    L->length=0;
    return L;
}

  既然参数SqList *L调用时给的是个野指针,不要也罢。于是改选成无参函数:

//初始化顺序表InitList(*L)
SqList *InitList()
{
    SqList *L=(SqList *)malloc(sizeof(SqList));//这里申请了结点空间
    L->length=0;
    return L;
}

  在调用时,main函数定义为:

int main()
{
    SqList *sq;
    sq = InitList();
    ListInsert(sq, 1, 5);
    ListInsert(sq, 2, 3);
    ListInsert(sq, 1, 4);
    DispList(sq);
    return 0;
}

  为保证程序能够正确编译,函数声明等处的语法问题不一一列出。解决了这一环节的问题,程序能够运行了,但结果:
  
  断定问题出在ListInsert函数中。看调用,插入的位置用的是逻辑序(从1开始记数),但函数定义中,直接L->data[i]=b;没有考虑物理存储中,下标是从0开始的。
  所以,在ListInsert中加入一个 i–,完成逻辑序号向物理序号的转换,Done。
  正确的结果不贴图了,最后改过的程序是:

#include <stdio.h>
#include <malloc.h>

#define MaxSize 50    //Maxsize将用于后面定义存储空间的大小
typedef int ElemType;  //ElemType在不同场合可以根据问题的需要确定,在此取简单的int
typedef struct
{
    ElemType data[MaxSize];  //利用了前面MaxSize和ElemType的定义
    int length;
} SqList;

//声明自定义函数
SqList *InitList();   //初始化顺序表
void ListInsert(SqList *L,int i,int b);  //插入函数
void DispList(SqList *L);    //输出函数
bool ListEmpty(SqList *L);//判定是否为空表ListEmpty(L)

int main()
{
    SqList *sq;
    sq = InitList();
    ListInsert(sq, 1, 5);
    ListInsert(sq, 2, 3);
    ListInsert(sq, 1, 4);
    DispList(sq);
    return 0;
}

//输出线性表DispList(L)
void DispList(SqList *L)
{
    int i;
    if (ListEmpty(L))
        return;
    for (i=0; i<L->length; i++)
        printf("%d ",L->data[i]);
    printf("\n");
}

//判定是否为空表ListEmpty(L)
bool ListEmpty(SqList *L)
{
    return(L->length==0);
}

//初始化顺序表InitList(*L)
SqList *InitList()
{
    SqList *L=(SqList *)malloc(sizeof(SqList));//这里申请了结点空间
    L->length=0;
    return L;
}

void ListInsert(SqList *L,int i,int b)   //插入函数
{
    int j;

    if(i<1)
    {
        printf("插入位置非法/n");
    }
    i--;
    for(j=L->length; j>i; j--)
    {
        L->data[j]=L->data[j-1];
    }
    L->data[i]=b;
    L->length++;
}
时间: 2024-11-05 21:57:04

数据结构实践——初始化顺序表怎么就内存溢出了?的相关文章

归并排序-数据结构C语言顺序表的排序和删除问题

问题描述 数据结构C语言顺序表的排序和删除问题 顺序表定义的长度为10000,此时程序可以正常运行:把顺序表长度改成500000,程序出错,不能运行.求问大神是哪里出了错误,还是要提高存储上限?如何改正?#include #include #include typedef int ElemType; #define MAX 10000 typedef struct{ ElemType *elem; int length; }SqList; void InitList(SqList &L){ L.

C++数据结构分别用顺序表和单链表的存储形式

问题描述 C++数据结构分别用顺序表和单链表的存储形式 分别用顺序表和单链表的存储形式实现将输入的两个大整数(超过20位)相加并打印和值:自行设计基本操作,要求两种存储结构中操作接口相同 解决方案 数据结构-----顺序表与单链表的实现 解决方案二: 存储结构的引入是为了将大数字分解成若干个小数字么? 解决方案三: 大数相加必须,分解成若单个小数字呀,采用哪个储存结构只是题目要求而已,用数组也可以实现代码如下#include #include int main() { char str1[100

【数据结构1】顺序表

顺序表的基本概念 1 静态存储 2 动态存储 顺序表的基本操作 1 插入操作 2 删除操作 3 查找操作 4 顺序表并集 5 顺序表合并 1 顺序表的基本概念 顺序存储的线性表称为顺序表.表中元素的逻辑顺序与物理顺序相同. 假设顺序表L存储的起始位置是b,每个数据元素所占用存储空间大小是l,则表L所对应的顺序存储如下图.(本文规定:顺序表元素位序从1开始,而数组元素下标从0开始) 顺序表中元素的一维数组可以是静态分配,也可以是动态分配. 1.1 静态存储 在静态分配时,由于数组的大小和空间已经固

数据结构 c++语言-顺序表上的基本操作实现

问题描述 顺序表上的基本操作实现 求大神补充一下逆置操作,顺便将注释补上.求问此处return -1:是什么意思?顺序表上的基本操作实现 时 限: 1000 ms 内存限制: 10000 K 总时限: 3000 ms 描述: 在顺序存储结构实现基本操作:初始化.创建.插入.删除.查找.遍历.逆置.合并运算. 输入: 请输入线性表La的长度:na1 a2 a3 ...an(数值有序,为降序)请输入要插入到线性表La中的数字x和插入的位置i:x i请输入要删除数字的位置:i请输入要查找的数字:x请输

数据结构 语言-关于顺序表操作的问题

问题描述 关于顺序表操作的问题 输入一组整形元素序列,建立顺序表.要求:(1)实现顺序表的遍历.查找.插入.删除:(2)实现将顺序表中所有奇数排在偶数之前,表的前面为奇数,后面为偶数: 解决方案 java实现: 这个顺序表可以封装两个TreeSet,一个放奇数,一个放偶数.遍历: 返回两个set的集合,先返回骑术的,再返回偶数的.查找: 先判断奇偶,然后直接到set里查,so easy.插入: 先判断奇偶,然后add到对应的set.删除: 同理. 解决方案二: http://blog.csdn.

数据结构(C#):顺序表

线性表是有限个数据元素的序列.线性表的存储有顺序存储和链式存储两种. 为使线性表支持相同的API,定义了以下接口,分别用顺表和链表实现. /* * File : ILinerList.cs * Author : Zhenxing Zhou * Date : 2008-12-06 * Blog : http://www.xianfen.net/ */ using System.Collections.Generic; namespace Xianfen.Net.DataStructure { in

C/C++常用算法【C语言顺序查找(顺序表)】【2】

顺序表结构的存储方式非常容易理解,操作也十分方便.但是顺序表结构有如下一些缺点: 1.在插入或者删除结点时,往往需要移动大量的数据. 2.如果表比较大,有时难以分配足够的连续存储空间,往往导致内存分配失败,而无法存储. 后面会有链表结构的章节. 直接上代码,代码中有详细注释,请自己领悟 #include <stdio.h> #include <stdlib.h> #define MAXLEN 100 //定义顺序表的最大长度 typedef struct { char key[10

如何在C++中建立一个顺序表_C 语言

准备数据 复制代码 代码如下: #define MAXLEN 100 //定义顺序表的最大长度struct DATA{ char key[10]; //结点的关键字  char name[20]; int age;};struct SLType //定义顺序表结构 { DATA ListData[MAXLEN+1];//保存顺序表的结构数组 int ListLen;   //顺序表已存结点的数量 }; 定义了顺序表的最大长度MAXLEN.顺序表数据元素的类型DATA以及顺序表的数据结构SLTyp

C++实现顺序表的常用操作(插入删出查找输出)_C 语言

实现顺序表的插入,删除,查找,输出操作在C语言中经常用到.下面小编给大家整理实现代码,一起看下吧 代码如下所示: #include<iostream> using namespace std; #define MAXSIZE 15 typedef int DataType; typedef struct { DataType data[MAXSIZE]; //通常用一位数组来描述顺序表的数据存储 int SeqLength; /*线性表长度*/ } SeqList; SeqList *Init