C 语言顺序表实现问题–快求来解答

C语言 码拜 4年前 (2016-09-18) 397次浏览
     本人模仿课本(《数据结构(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>)截图:
C 语言顺序表实现问题--快求来解答
显然中间有几个不正常的值,正确输出应该是100到129的。从0x6037d8开始连续到0x6037e0,这段地址存的值应该是106,107,108的。以及后面0x6037f8和0x6037fc也不对,这里应该是124,125的。
然后看debug时的变量情况:
C 语言顺序表实现问题--快求来解答
比较怪异的地方出现了,指针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));

#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;
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明C 语言顺序表实现问题–快求来解答
喜欢 (0)
[1034331897@qq.com]
分享 (0)