Question

C语言(数据结构)顺序表的初始化

以下是我写的两个顺序表的小程序，可是我有点迷糊了，顺序表的初始化，需不需要申请结点空间呀？我觉得申请了好像没什么用啊？
程序一（申请了结点空间）

#include<stdio.h>
#include"malloc.h"
#define MAX 50

typedef struct
{ int data[MAX];
int length;

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

int Listinsert(Sqlist &L,int i,int e)
{
int j;
if(i<1||i>L.length+1) return 0;
for(j=L.length-1;j>=i-1;j--)
L.data[j+1]=L.data[j];
L.data[i-1]=e;
L.length++;
return 1;
}
void main(){
Sqlist L;
L=InitSqlist();
//测试插入
printf("测试插入");
Listinsert(L,1,12);
}

程序二（未申请结点空间）：

#include<stdio.h>
#include"malloc.h"
#define MAX 50

typedef struct
{ int data[MAX];
int length;

}Sqlist;

//顺序表的初始化（这里边没有申请结点空间）

Sqlist InitSqlist()
{
Sqlist a;
a.length=0;
return a;
}

int Listinsert(Sqlist &L,int i,int e)
{
int j;
if(i<1||i>L.length+1) return 0;
for(j=L.length-1;j>=i-1;j--)
L.data[j+1]=L.data[j];
L.data[i-1]=e;
L.length++;
return 1;
}
void main(){
Sqlist L;
L=InitSqlist();
//测试插入
printf("测试插入");
Listinsert(L,1,12);

}

为何这两个程序测试都没有错误呀？顺序表到底需不需要申请结点空间呀？

Answer 1

肯定是要分配空间的，你第一个程序的initsqlist函数中声明的结构体指针（Sqlist *a;），而第二个程序的initsqlist函数中是声明的结构体（Sqlist a;），前者只是在计算机内存中声明一个指针，而不会给这个指针分配内存空间，所以你初始化的时候要给这个指针用malloc函数分配空间，而后者是实实在在的定义了一个结构体，在内存在不仅仅是一个地址，还分配了空间，就像你定义了一个数组一样，已经在内存存在空间了，不需要再分配了。
总体来说就是你定义的是指针的话就要分配空间。

你的2个程序都是对的，但是一般用第一种定义链表！！！

追问

谢谢，我在第一个中已经定义了数组，就相当于有了一些结点，那再申请结点不是多余吗？

追答

你在第一个程序中定义了结构体，结构体的成员有一个是数组，但是你没有向内存申请空间，
typedef struct
{ int data[MAX];
int length;
}Sqlist;
这段语句只是单纯的定义一个结构体，给这个结构体去取一个别名，后面的
Sqlist a;才是正式的向内存申请空间。。

Answer 2

C语言(数据结构)顺序表的初始化需要申请结点空间。

初始化顺序表

1、/**

2、 * 初始化顺序表

3、 * 返回1 表示初始化成功

4、* 返回0 表示初始化失败

5、*/

6、int initList_sq(SqList &L) { //只有在C++中才会有引用的存在

7、    L.elem = (SeqType *) malloc(sizeof(SeqType) * LIST_INIT_SIZE);

8、  if (!L.elem)

9、    return 0; //内存分配失败，存储空间不够

10、  L.length = 0; //表示顺序表为空

11、   L.listsize = LIST_INIT_SIZE; //表示顺序表里，最大存储单元个数

分配顺序表的存储单元，初始化顺序表属性的值。

定义结构

typedef int SeqType; //存储单元类型

typedef struct{

SeqType *elem; //存储空间基地址

int length; //当前长度

int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）

} SqList;

结构体内，有三个元素：存储空间基地址，类似于数组首地址；当前长度，记录顺序表中有效存储单元个数；当前分配的存储容量，顺序表中，最多容纳的存储单元个数。当顺序表中所有存储单元已经被使用，在下次插入元素之前，需要新增存储单元。这点是数组所不具有的特性。

*注：定义一个存储单元类型SeqType是为了使顺序表适和更多数据类型，使用的时候修改SeqType类型即可。

Answer 3

SeqList *Init_SeqList(){//函数返回初始化后的顺序表结构指针，没有传入参数
SeqList *L;//定义顺序表结构指针
L=(SeqList *)malloc(sizeof(SeqList));//申请头顺序表，为它在堆中分配内存
L->last = -1;//last指向顺序表中最后一个元素的位置，从0开始；这里-1表示顺序表当前没有内容
return L;//返回顺序表结构指针
}
Main(){
SeqList *L;//定义顺序表结构指针，用来保存顺序表结构
L=Init_SeqList();//调用函数得到顺序表指针
……
}

Answer 4

你的SqList结构包含的元素是一个100个int类型的数组，和一个int变量。
在初始化函数中，首先参数sqlist *L，应该改成Sqlist *L
然后你给L->Elem_array进行赋值操作是不对的，因为Elem_array是数组首地址，是个常量，不能进行赋值操作。而且本身结构里面定义的是数组元素，所以已经有空间了，根本不需要再另外申请内存。如果需要动态申请内存，就把Elem_array声明为指针类型：ElemType *pElem_array

Answer 5

分配空间的位置不当，你应该在插入节点的地方分配空间，分配空间是用在原来或者本身因为相关操作空间不足，所以需要分配空间。你写的这个程序不需要要分配空间了，因为你已经定义了data[20]这个里面已经有了20个这样的空间了，你目前的操作完全够用的。如果定义成*data,就要分配空间了。

追问

也就是说用数组存储元素的不需要申请结点空间对吗？数组就相当于结点空间了，而对于像单链表因为不是用数组存储的，所以需要申请结点空间来存储元素和指针对吗？

还有一个问题：
那我上边写的第二个程序才是正确的对吗？第一个程序没必要申请结点空间对吗？

追答

typedef struct {T data;Node *next;} Node;这种写法的时候每次增加节点的时候需要去分配空间；抱歉因为前面的回答是手机上看的回答，有点答非所问。 分配空间一般是给指针变量分配的，普通变量并不需要，上面的你的两个程序差不多是一个意思，都是使用的一个节点，然后使用里面的data数组。其实你这种写法是有问题的，你是链表初始化，什么是链表 它是条可以无限延伸的链子，每个节点里面储存着你的数据，而不是一个节点里面来个数组 ，就能长度length++；你计算的可不是节点长度，而是这个data数组中存了几个数了。 因为这台机子没有VS2008不好写程序，简单写下希望能帮到你。int Listinsert(Sqlist &L,int i,int e){for(i=0;i<num;i++){这个时候每循环一次分配一次节点空间，然后再往里面插入数据，同时链表的长度+1}}