本人模仿课本(《数据结构(C语言版)》,严蔚敏,清华大学出版社,第2版)在数据结构线性表的顺序实现部分代码如下:
#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASABLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType; //元素类型设置为int型
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList; //顺序表定义
Status initList_Sq(SqList *L) //初始化线性表
{
L->elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
if(!L->elem)
exit(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}
Status ListInsert_Sq(SqList *L,int i,ElemType e) //在线性表的第i个位置插入元素e
{
if(i<1||i>L->length+1)
return ERROR;
if(L->listsize<L->length+1)
{
ElemType *newbase=(ElemType*)(realloc(L->elem,sizeof(ElemType)*(LIST_INIT_SIZE)));
if(!newbase)
exit(OVERFLOW);
L->elem=newbase;
L->listsize=L->length+LIST_INIT_SIZE;
}
ElemType *p=L->elem+i-1,*q=L->elem+L->length-1;
for(;q>=p;q--)
*(q+1)=*q;
*p=e;
++L->length;
return OK;
}
int ListLength(SqList *L)
{
if(!L)
exit(ERROR);
else return L->length;
}
Status GetElem(SqList *L,int i,ElemType *e) //获取线性表中的第i个元素
{
if(!L->elem) exit(ERROR);
if(i<1||i>L->length) return ERROR;
*e=*(L->elem+i-1);
printf("%p: ",L->elem+i-1);
return OK;
}
Status MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc)//合并两个线性表A和B到C中
{
Lc->listsize=La->length+Lb->length;
Lc->elem=(ElemType*)malloc(sizeof(Lc->listsize));
ElemType *pa=La->elem,*pb=Lb->elem,*pc=Lc->elem;
if(!pc)
exit(OVERFLOW);
while(pa<La->elem+La->length&&pb<Lb->elem+Lb->length)
{
if(*pa<*pb)
{
*pc++=*pa++;
//printf("%3d ",*(pc-1));
}
else
{
*pc++=*pb++;
// printf("%3d ",*(pc-1));
}
}
while(pa<La->elem+La->length)
{
*pc++=*pa++;
// printf("%3d ",*(pc-1));
}
while(pb<Lb->elem+Lb->length)
{
*pc++=*pb++;
// printf("%3d ",*(pc-1));
}
Lc->length=Lc->listsize;
return OK;
}
int main()
{
SqList *listA=(SqList*)(malloc(sizeof(SqList)));
SqList *listB=(SqList*)(malloc(sizeof(SqList)));
printf("%d\n",initList_Sq(listA));
printf("%d\n",initList_Sq(listB));
int i=100;
for(i=100;i<110;i++)
{
ListInsert_Sq(listA,i-99,i); /*将100-109插入A中,*/
ListInsert_Sq(listB,i-99,i+20); /*将120-129插入B中,*/
}
SqList *listC=(SqList*)(malloc(sizeof(SqList)));
MergeList_Sq(listA,listB,listC); /*合并A,B到C中*/
ElemType *e=(ElemType*)(malloc(sizeof(ElemType))); //就是这里的malloc出问题了,结果中会看到。
if(!e)
exit(OVERFLOW);
ElemType *p=listC->elem;
for(i=1;i<=listC->length;i++)
{
GetElem(listC,i,e); /* 将第i个元素赋予e,
printf("%3d\n ",*e); 并将C中的元素打印出来*/
}
free(listA->elem);
free(listB->elem);
free(listC->elem);
free(listA);
free(listB);
free(listC);
//free(e);
return 0;
}
下面是debug的结果(运行环境是64位 linux<ubuntu16.04>)截图:
显然中间有几个不正常的值,正确输出应该是100到129的。从0x6037d8开始连续到0x6037e0,这段地址存的值应该是106,107,108的。以及后面0x6037f8和0x6037fc也不对,这里应该是124,125的。
然后看debug时的变量情况:
比较怪异的地方出现了,指针e是用malloc分配的,e指向了0x6037e0, 而这个地址竟然在malloc之前就已经被listC使用了(108因该存放在这个地址的,而上面该打印108的地方打印了0出来),这当然不合常理,于是这就耐人寻味了,所以,请高手来解答啦,已经被困惑一周了……
解决方案
80
你malloc那句错了,所以导致有的内存空间被覆盖重写,所以打印出了这样的信息
Lc->elem = (ElemType*)malloc(sizeof(Lc->listsize));应该是:
Lc->elem = (ElemType*)malloc(Lc->listsize * sizeof(ElemType));
Lc->elem = (ElemType*)malloc(sizeof(Lc->listsize));应该是:
Lc->elem = (ElemType*)malloc(Lc->listsize * sizeof(ElemType));
#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASABLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType; //元素类型设置为int型
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList; //顺序表定义
Status initList_Sq(SqList *L) //初始化线性表
{
L->elem = (ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
if (!L->elem)
exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
Status ListInsert_Sq(SqList *L, int i, ElemType e) //在线性表的第i个位置插入元素e
{
if (i<1 || i>L->length + 1)
return ERROR;
if (L->listsize<L->length + 1)
{
ElemType *newbase = (ElemType*)(realloc(L->elem, sizeof(ElemType)*(LIST_INIT_SIZE)));
if (!newbase)
exit(OVERFLOW);
L->elem = newbase;
L->listsize = L->length + LIST_INIT_SIZE;
}
ElemType *p = L->elem + i - 1, *q = L->elem + L->length - 1;
for (; q >= p; q--)
*(q + 1) = *q;
*p = e;
++L->length;
return OK;
}
int ListLength(SqList *L)
{
if (!L)
exit(ERROR);
else return L->length;
}
Status GetElem(SqList *L, int i, ElemType *e) //获取线性表中的第i个元素
{
if (!L->elem) exit(ERROR);
if (i<1 || i>L->length) return ERROR;
*e = *(L->elem + i - 1);
printf("%p: ", L->elem + i - 1);
return OK;
}
Status MergeList_Sq(SqList *La, SqList *Lb, SqList *Lc)//合并两个线性表A和B到C中
{
Lc->listsize = La->length + Lb->length;
Lc->elem = (ElemType*)malloc(Lc->listsize * sizeof(ElemType));
ElemType *pa = La->elem, *pb = Lb->elem, *pc = Lc->elem;
if (!pc)
exit(OVERFLOW);
while (pa < La->elem + La->length&&pb < Lb->elem + Lb->length)
{
if (*pa < *pb)
{
*pc++ = *pa++;
//printf("%3d ",*(pc-1));
}
else
{
*pc++ = *pb++;
// printf("%3d ",*(pc-1));
}
}
while (pa < La->elem + La->length)
{
*pc++ = *pa++;
// printf("%3d ",*(pc-1));
}
while (pb < Lb->elem + Lb->length)
{
*pc++ = *pb++;
// printf("%3d ",*(pc-1));
}
Lc->length = Lc->listsize;
return OK;
}
int main()
{
SqList *listA = (SqList*)(malloc(sizeof(SqList)));
SqList *listB = (SqList*)(malloc(sizeof(SqList)));
printf("%d\n", initList_Sq(listA));
printf("%d\n", initList_Sq(listB));
int i = 100;
for (i = 100; i<110; i++)
{
ListInsert_Sq(listA, i - 99, i); /*将100-109插入A中,*/
ListInsert_Sq(listB, i - 99, i + 20); /*将120-129插入B中,*/
}
SqList *listC = (SqList*)(malloc(sizeof(SqList)));
MergeList_Sq(listA, listB, listC); /*合并A,B到C中*/
ElemType *e = (ElemType*)(malloc(sizeof(ElemType))); //就是这里的malloc出问题了,结果中会看到。
if (!e)
exit(OVERFLOW);
ElemType *p = listC->elem;
for (i = 1; i <= listC->length; i++)
{
GetElem(listC, i, e); /* 将第i个元素赋予e,并将C中的元素打印出来*/
printf("%3d\n ",*e);
}
free(listA->elem);
free(listB->elem);
free(listC->elem);
free(listA);
free(listB);
free(listC);
//free(e);
return 0;
}