求解决
#include <string.h>#include <ctype.h>
#include <malloc.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <io.h>
#include <math.h>
#include <process.h>
//#include <iostream.h>
//函数结果状态
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;//STATUS 是函数的类型,其值是函数结果状态代码,如OK等
typedef int Boolean;//Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;
//顺序表的基本操作
//线性表的动态分配顺序存储结构
//顺序表的创建
//线性表存储空间的初始分配量
#define LIST_INIT_SIZE 10
//线性表存储空间的分配增量
#define LISTINCREMENT 2
typedef struct
{
ElemType *elem;//存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量(以sozeof(ElemType)为单位)
}SqList;
/********************************************************************************/
//顺序表的初始化
//函数要求采用地址调用,才能改变主函数中的值,动态分配内存
Status InitList(SqList *L)
{
//构造一个空的顺序线性表
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(!(*L).elem)
exit(0);//存储分配失败
(*L).length = 0; //空表长度为0
(*L).listsize = LIST_INIT_SIZE;//初始存储容量
return OK;
}
/********************************************************************************/
//顺序表重置为空表,即为清空
//前提条件为顺序表已经存在
Status ClearList(SqList *L)
{
(*L).length = 0;
return OK;
}
/********************************************************************************/
//若L为空表,则返回TRUE,否则返回FALSE
//前提条件顺序表已经存在
Status ListEmpty(SqList L)
{
if(L.length == 0)
return TRUE;
else
return FALSE;
}
/********************************************************************************/
//返回L中数据元素个数,即为顺序表长度
//前提条件顺序表已经存在
int ListLength(SqList L)
{
return L.length;
}
/********************************************************************************/
//用e返回顺序表中第i个数据元素的值
//初始条件顺序表已经存在,且i值有效。
Status GetElem(SqList L, int i, ElemType *e)
{
if(L.length == 0 || i < 1 || i > L.length)
return ERROR;
//没有将地址返回到主函数中????,而有时候又可以
*e = *(L.elem+ i -1 ); //给e重新赋地址值
return OK;
}
/********************************************************************************/
//顺序表的销毁
//注意前提条件是顺序表已经存在
Status DestroyList(SqList *L)
{
free(L->elem); //释放内存
free(L);
//L->elem = NULL;
//L->length = 0;
//L->listsize = 0;
return OK;
}
/********************************************************************************/
//在顺序表中第i个位置之前插入新的数据元素e,顺序表的长度加1
Status ListInsert(SqList *L , int i , ElemType e)
{
ElemType*q , *p;
ElemType *newbase;
if(i < 1 || i > L->length + 1)//i值不合法
exit(0);
// 如果空间不够放,调用realloc()重新分配空间
if( L->length == L->listsize)//当前存储空间已满,增加分配
{
//注意realloc函数的意思与malloc函数的区别,realloc为重新分配内存
//如果成功分配返回true,失败则是返回false
//重新将新基址分配给(*L).elem
newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase)
{
printf("内存分配错误");
exit(0);//存储分配失败
}
//调试结果,执行完上一个语句之后,开始出现问题,分配内存出现错误
L->elem = newbase; //确定新基址
L->listsize += LISTINCREMENT;//增加存储容量
//L->listsize = L->listsize + LISTINCREMENT
}
q = L->elem + i -1;//q为插入位置,采用下一个语句也是可以的
//q = &(L->elem);
//插入位置及之后右移,先从最后一个位置开始
for(p = L->elem + L->length + 1; p >= q; --p)
*(p + 1) = *p;
*q = e;//插入e
L->length ++;//表长增1
return OK;
}
/********************************************************************************/
/********************************************************************************/
//在顺序表中第i个位置之前删除新的数据元素e,顺序表的长度减1
/*
Name:
Copyright:
Author:
Date: 22/12/14 16:03
Description:顺序表的实例
*/
int main(void)
{
SqList L;//定义一个顺序表
ElemType e, e0;
Status i;
int j, k;
i = InitList(&L);//初始化顺序表
//%u表示的是地址编号
//进行初始化后,顺序表的值没有改变,说明此时采用的是值调用,我们应该采用地址调用
printf("初始化顺序表L后:\n基址L.elem = %u表长L.length = %d初始分配容量L.listsize = %d\n", L.elem, L.length, L.listsize);
for(j = 1; j <= 5; j++)
ListInsert(&L, 1, j);//在表头位置一次输入,注意顺序表表头都是第一个位置,用数组理解就是第一个a
printf("在顺序表的表头依次插入1~5后。\n表中数据依次为:");
for(j = 1; j <=5; j++)
printf("%d", *(L.elem + j -1));
printf("\n");
printf("L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
//判断顺序表是否为空,并输出是否为空表,用条件表达式来表示
printf("顺序表L%s空表。 \n", ListEmpty(L) == TRUE ? "为" : "不为");
//进行清空操作
i = ClearList(&L);
printf("进行清空操作后:L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
//判断顺序表是否为空,并输出是否为空表
printf("进行清空操作后,此时顺序表L%s空表。\n", ListEmpty(L) == 1 ? "为" : "不为");
//从表尾位置输入数据
for(j = 1; j <= 10; j++)
i = ListInsert(&L, j, j);
printf("在顺序表的表尾依次插入1~10后。\n表中数据依次为:");
for(j = 1; j <= 10; j++)
printf("%d", *(L.elem + j -1));
printf("\n");
printf("L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
printf("\n");
/*********************************************************************************/
//以上运行编译没有问题,在下面的程序编译之后出现对话框,说明出现一个问题,程序停止,
//经过综合分析之后,可能是插入函数出现问题
//在第1个位置插入0
ListInsert(&L, 1, 0);//这个函数出现问题
printf("在顺序表的插入0后。\n表中数据依次为:");
for(j = 1; j <= ListLength(L); j++)//ListLength(L)为元素个数
printf("%d", *(L.elem + j -1));
printf("\nL.elem = %u(有可能改变)L.length = %d(改变)L.listsize = %d(改变)\n", L.elem, L.length, L.listsize);
GetElem(L, 5 , &e);
printf("第5个元素的值为:%d\n",e);
DestroyList(&L);//这个函数也出现问题
printf("销毁顺序表L后:L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
system("PAUSE");
return 0;
}
出现
http://xxx.fishc.com/forum/201412/26/142338jcj0yi83riij6qik.png
发现是插入函数出问题了
1. SqList 结构体应该有一个成员指示该列表是否被初始化过, 以指导 InitList Destroy 是否初始化或销毁. 防止内存泄露或多次销毁
2.GetElem 按STL习惯(实际大多数软件习惯), 数组区间应为左闭右开区间. 即 [0,n) n为元素个数. 你以 1为首元素检索值, 长度为n, 那么区间应该是 [1,n+1)
所以if(L.length == 0 || i < 1 || i > L.length) 这个判断应该改为 if(L.length == 0 || i < 1 || i > L.length+1)
3. DestroyList 与init不对称.init只是初始化传入的指针指向的内容.DestroyList把传入指针本身给free了.
4. ListInsert 在空间不足时重新分配,但分配后没有把原来区块复制到新区块, 旧的区块也没有free. 这里泄露了.
5. for(p = L->elem + L->length + 1; p >= q; --p) 这个插入前的内存移动有问题.本来是(最后一个元素+1)这个位置取得最后一个元素的值.所以
应该 p = L->elem + L->length , 这个 *p 才是 ( 最后一个元素+1 ) 记住区间是 才是最后元素.
更甚者.*(p + 1) = *p;这个相当于(最后一个元素+2)位置取得前一个元素. 这就溢出了.
aauutthh 发表于 2015-5-24 13:32
1. SqList 结构体应该有一个成员指示该列表是否被初始化过, 以指导 InitList Destroy 是否初始化或销毁. 防 ...
你好,我在realloc函数之后加上
newbase = (ElemType *)realloc(L->elem, ((L->listsize + LISTINCREMENT) * sizeof(ElemType)));
free(L->elem );
if(!newbase)
{
printf("内存分配错误");
exit(0);//存储分配失败
}
还是出现之前那个问题,求能否详细的解答,谢谢。 newbase = (ElemType *)realloc(L->elem, ((L->listsize + LISTINCREMENT) * sizeof(ElemType)));
free(L->elem );
这个没细看.以为是alloc.realloc已经处理过旧指针,且数据保留. 不用free了.
请重点参考2,3 ,5 . 你的区间没有明确, 请试着把用户概念的首元素索引(1) 和程序概念的首元素索引(0)区分开. 如在 ListInsert 入口处,马上处理 int inx = i - 1.
另外, 这样的指示已经够详细了吧. 你的程序,自己用gdb好好调试下就知道了. 本帖最后由 x072816 于 2015-5-26 17:01 编辑
aauutthh 发表于 2015-5-25 11:25
newbase = (ElemType *)realloc(L->elem, ((L->listsize + LISTINCREMENT) * sizeof(ElemType)));
...
第二条与第三条能够理解,而且我已经改正过来了,没有再显示上面那个对话框,但是第五条我之前运行也没有问题,照着改完之后,是不对的,而且依旧在进行最后一个空间不够进行realloc函数扩展空间,插入函数之后,显示上面“那个程序出现问题”的对话框。我通过调试之后,发现就是扩建空间使用realloc函数之后,出现的问题。
x072816 发表于 2015-5-26 16:59
第二条与第三条能够理解,而且我已经改正过来了,没有再显示上面那个对话框,但是第五条我之前运行也没有 ...
附上修改后的代码呀. 本帖最后由 x072816 于 2015-5-26 19:29 编辑
aauutthh 发表于 2015-5-26 19:21
附上修改后的代码呀.
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <io.h>
#include <math.h>
#include <process.h>
//#include <iostream.h>
//函数结果状态
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;//STATUS 是函数的类型,其值是函数结果状态代码,如OK等
typedef int Boolean;//Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;
//顺序表的基本操作
//线性表的动态分配顺序存储结构
//顺序表的创建
//线性表存储空间的初始分配量
#define LIST_INIT_SIZE 10
//线性表存储空间的分配增量
#define LISTINCREMENT 2
typedef struct
{
ElemType *elem;//存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量(以sozeof(ElemType)为单位)
}SqList;
/********************************************************************************/
//顺序表的初始化
//函数要求采用地址调用,才能改变主函数中的值,动态分配内存
Status InitList(SqList *L)
{
//构造一个空的顺序线性表
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(!(*L).elem)
exit(0);//存储分配失败
(*L).length = 0; //空表长度为0
(*L).listsize = LIST_INIT_SIZE;//初始存储容量
return OK;
}
/********************************************************************************/
//顺序表重置为空表,即为清空
//前提条件为顺序表已经存在
Status ClearList(SqList *L)
{
(*L).length = 0;
return OK;
}
/********************************************************************************/
//若L为空表,则返回TRUE,否则返回FALSE
//前提条件顺序表已经存在
Status ListEmpty(SqList L)
{
if(L.length == 0)
return TRUE;
else
return FALSE;
}
/********************************************************************************/
//返回L中数据元素个数,即为顺序表长度
//前提条件顺序表已经存在
int ListLength(SqList L)
{
return L.length;
}
/********************************************************************************/
//用e返回顺序表中第i个数据元素的值
//初始条件顺序表已经存在,且i值有效。
Status GetElem(SqList L, int i, ElemType *e)
{
if(L.length == 0 || i < 1 || i > L.length +1)
return ERROR;
//没有将地址返回到主函数中????,而有时候又可以
*e = *(L.elem+ i -1 ); //给e重新赋地址值
return OK;
}
/********************************************************************************/
//顺序表的销毁
//注意前提条件是顺序表已经存在
Status DestroyList(SqList *L)
{
L->elem = NULL;
L->length = 0;
L->listsize = 0;
return OK;
}
/********************************************************************************/
//在顺序表中第i个位置之前插入新的数据元素e,顺序表的长度加1
Status ListInsert(SqList *L , int i , ElemType e)
{
ElemType*q , *p;
ElemType *newbase;
if(i < 1 || i > L->length + 1)//i值不合法
exit(0);
// 如果空间不够放,调用realloc()重新分配空间
if( L->length == L->listsize)//当前存储空间已满,增加分配
{
//注意realloc函数的意思与malloc函数的区别,realloc为重新分配内存
//如果成功分配返回true,失败则是返回false
//重新将新基址分配给(*L).elem
newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase)
{
printf("内存分配错误");
exit(0);//存储分配失败
}
//调试结果,执行完上一个语句之后,开始出现问题,分配内存出现错误
L->elem = newbase; //确定新基址
L->listsize += LISTINCREMENT;//增加存储容量
//L->listsize = L->listsize + LISTINCREMENT
}
q = L->elem + i -1;//q为插入位置,采用下一个语句也是可以的
//q = &(L->elem);
//插入位置及之后右移,先从最后一个位置开始
for(p = L->elem + L->length + 1; p >= q; --p)
*(p + 1) = *p;
*q = e;//插入e
L->length ++;//表长增1
return OK;
}
/********************************************************************************/
/********************************************************************************/
//在顺序表中第i个位置之前删除新的数据元素e,顺序表的长度减1
/*
Name:
Copyright:
Author:
Date: 22/12/14 16:03
Description:顺序表的实例
*/
int main(void)
{
SqList L;//定义一个顺序表
ElemType e, e0;
Status i;
int j, k;
i = InitList(&L);//初始化顺序表
//%u表示的是地址编号
//进行初始化后,顺序表的值没有改变,说明此时采用的是值调用,我们应该采用地址调用
printf("初始化顺序表L后:\n基址L.elem = %u表长L.length = %d初始分配容量L.listsize = %d\n", L.elem, L.length, L.listsize);
for(j = 1; j <= 5; j++)
ListInsert(&L, 1, j);//在表头位置一次输入,注意顺序表表头都是第一个位置,用数组理解就是第一个a
printf("在顺序表的表头依次插入1~5后。\n表中数据依次为:");
for(j = 1; j <=5; j++)
printf("%d", *(L.elem + j -1));
printf("\n");
printf("L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
//判断顺序表是否为空,并输出是否为空表,用条件表达式来表示
printf("顺序表L%s空表。 \n", ListEmpty(L) == TRUE ? "为" : "不为");
//进行清空操作
i = ClearList(&L);
printf("进行清空操作后:L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
//判断顺序表是否为空,并输出是否为空表
printf("进行清空操作后,此时顺序表L%s空表。\n", ListEmpty(L) == 1 ? "为" : "不为");
//从表尾位置输入数据
for(j = 1; j <= 10; j++)
i = ListInsert(&L, j, j);
printf("在顺序表的表尾依次插入1~10后。\n表中数据依次为:");
for(j = 1; j <= 10; j++)
printf("%d", *(L.elem + j -1));
printf("\n");
printf("L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
printf("\n");
/*********************************************************************************/
//以上运行编译没有问题,在下面的程序编译之后出现对话框,说明出现一个问题,程序停止,
//经过综合分析之后,可能是插入函数出现问题
//在第1个位置插入0
ListInsert(&L, 1, 0);//这个函数出现问题
printf("在顺序表的插入0后。\n表中数据依次为:");
for(j = 1; j <= ListLength(L); j++)//ListLength(L)为元素个数
printf("%d", *(L.elem + j -1));
printf("\nL.elem = %u(有可能改变)L.length = %d(改变)L.listsize = %d(改变)\n", L.elem, L.length, L.listsize);
GetElem(L, 5 , &e);
printf("第5个元素的值为:%d\n",e);
DestroyList(&L)
printf("销毁顺序表L后:L.elem = %uL.length = %dL.listsize = %d\n", L.elem, L.length, L.listsize);
system("PAUSE");
return 0;
} 1. (*L).elem 在 init时malloc 在 destroy时就要free. 这个要对称.
2. insert里面:
for(p = L->elem + L->length + 1; p >= q; --p)
*(p + 1) = *p;
*q = e;//插入e
改为:
//插入位置及之后右移,先从最后一个位置开始
if ( i <= L->length ) {
// 在队列中间插入, 需要先移动当前及后续元素.为插入元素准备位置
for(p = L->elem + L->length ; p > q; --p)
*p= *(p - 1);
}
// i == L->length+1 ||i <= L->length且已为插入元素准备好空间时
*q = e;//插入e aauutthh 发表于 2015-5-27 09:50
1. (*L).elem 在 init时malloc 在 destroy时就要free. 这个要对称.
2. insert里面:
for(p = L->elem ...
还是出现和以前相同的问题,望能告知到底问题出哪了,谢谢! 已经找到错误的地方了
插入函数中
for(p = L->elem + L->length + 1; p >= q; --p)
因改为 for(p = L->elem + L->length - 1; p >= q; --p)
*(p + 1) = *p; aauutthh 发表于 2015-5-27 09:50
1. (*L).elem 在 init时malloc 在 destroy时就要free. 这个要对称.
2. insert里面:
for(p = L->elem ...
已经找到错误的地方了
插入函数中
for(p = L->elem + L->length + 1; p >= q; --p)
因改为 for(p = L->elem + L->length - 1; p >= q; --p)
*(p + 1) = *p; :sad x072816 发表于 2015-5-28 01:31
已经找到错误的地方了
插入函数中
for(p = L->elem + L->length + 1; p >= q; --p)
你倾向于下个元素取得当前元素,这样方式的移动.
而我给的代码是当前元素取得前一元素. 两种方式都可行.不要越界存取就行.
我给的代码已调试过正常了.
加if是因为你的insert是两用的. 可以在尾部插入相当于append. 这时不用迁移数据.
也可以在区间内插入,这时需要迁移数据. 打酱油 :big 谢谢,学习了
页:
[1]