C语言超详细讲解数据结构中的线性表

第C语言超详细讲解数据结构中的线性表目录前言一、分文件编写1、分文件编写概念2、代码展示二、动态分布内存malloc1、初识malloc2、使用方法三、创建链表并进行增删操作1、初始化链表2、在链表中增加数据3、删除链表中指定位置数据四、代码展示与运行效果1、代码展示2、运行效果总结

前言

计算机专业都逃不了数据结构这门课，而这门课无疑比较难理解，所以结合我所学知识，我准备对顺序表做一个详细的解答，为了避免代码过长，采用分文件编写的形式，不仅可以让代码干净利落还能提高代码可读性，先解释部分代码的含义，最后放上代码实现和效果图，让我们开始操作吧！！！

一、分文件编写

1、分文件编写概念

在VisualStdio编译器中我们可以通过创建.h头文件和.cpp源文件来实现程序运行，使代码更美观，可读性高，如图所示：

SqList.h头文件和Sq.List.cpp源文件分别存放全局变量、结构体及函数的声明和对应函数的完整实现代码。我们需要注意的是头文件和源文件的名称要一致，而且源文件要引用头文件（#includeSqList.h)，使用而不用的原因是头文件是我们自己写的，只能用引用。

2、代码展示

SqList.cpp内容如下：

tips:#pragmaonce代码是为了避免重复引入头文件，我们稍作记忆即可

#pragmaonce

#includestdio.h

#includestdlib.h

#includemalloc.h

#defineLIST_INIT_SIZE10

#defineLISTINCREMENT10

#defineOK1

#defineERROR0

typedefstructSqList{

int*elem;

intlen;

intsize;

}SqList;

intInitList_Sq(structSqList*L);//初始化顺序表

intListInsert_Sq(structSqList*L,inti,inte);//向顺序表中插入数据

intListDelete_Sq(structSqList*L,inti,int*e);//删除顺序表中的数据

voidListShow_Sq(structSqList*L,constchar*s);//输出顺序表中的数据

voidDestroyList(SqList*L);//销毁表

SqList.cpp部分内容如下：

#include"SqList.h"

intInitList_Sq(structSqList*L)

L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L-elem)exit(0);

L-len=0;

L-size=LIST_INIT_SIZE;

returnOK;

}

二、动态分布内存malloc

1、初识malloc

C语言中malloc是动态内存分配函数。

函数原型：void*malloc(unsignedintnum_bytes);

参数：num_bytes是无符号整型，用于表示分配的字节数。

返回值：如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定)，否则返回空指针NULL。void*表示未确定类型的指针，void*可以指向任何类型的数据，更明确的说是指申请内存空间时还不知道用户是用这段空间来存储什么类型的数据（比如是char还是int等等）

2、使用方法

typedefstructSqList{

int*elem;

intlen;

intsize;

}SqList;

intInitList_Sq(structSqList*L)

L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L-elem)exit(0);

L-len=0;

L-size=LIST_INIT_SIZE;

returnOK;

}

我们可以看到此行代码L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));这里的L-elem就是形参结构体变量L调用int*elem属性，因此malloc需要返回（int*）类型的指针，同时malloc右边括号放的是内存空间，大小就是宏定义的数值乘以整型(int)所占字节数，在这里说白了就是10*4个字节。模板可以这样看：(分配类型*)malloc(分配元素个数*sizeof(分配类型))如果成功，则返回该空间首地址，该空间没有初始化，如果失败，则返回0

三、创建链表并进行增删操作

1、初始化链表

intInitList_Sq(structSqList*L)

{

L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L-elem)exit(0);

L-len=0;

L-size=LIST_INIT_SIZE;

returnOK;

}

首先为int*elem分配内存空间，如果失败返回零，成功就返回内存空间首地址，并把链表长度置为零，链表最大长度设为LIST_INIT_SIZE（大小为10）

2、在链表中增加数据

intListInsert_Sq(structSqList*L,inti,inte)

if(i0||iL-len)

returnERROR;

if(L-len=L-size){

int*newbase=(int*)realloc(L-elem,

(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(int));

if(!newbase)exit(0);

L-size+=LISTINCREMENT;

int*q=(L-elem[i]);

*q=e;

L-len++;

returnOK;

}

形参i对应L-len也就是初始长度,e对应插入的值,只看第一个if条件我们会觉得条件永远成立，实际上下面插入数据后会进行加一操作，因此插入数据只能挨个插入;第二个if不难理解，如果链表长度达到最大长度，进行空间扩容，从而可以插入更多数据；后面其实是尾插法，让*q指向链表的最后一个位置，把数据放到里面，然后长度加一，插入数据结束。

3、删除链表中指定位置数据

intListDelete_Sq(structSqList*L,inti,int*e){

if(i1||iL-len)returnERROR;

int*p=(L-elem[i-1]);

*e=*p;

int*q=L-elem+L-len-1;

for(++p;p++p)

*(p-1)=*p;

L-len--;

returnOK;

}

这里i代表链表中的位置，*e是该位置的数据，这样我们就能知道删除元素的值了，然后我定义*q为链表中最后一个元素的地址，随后重复让链表删除位置后的元素前移，最后链表总长度减一，删除结束。修改链表利用插入和删除操作结合就可以完成，这里没有单独定义方法，具体内容会在下面的总代码体现。

四、代码展示与运行效果

1、代码展示

//1、SqList.h:

#pragmaonce

#includestdio.h

#includestdlib.h

#includemalloc.h

#defineLIST_INIT_SIZE10

#defineLISTINCREMENT10

#defineOK1

#defineERROR0

typedefstructSqList{

int*elem;

intlen;

intsize;

}SqList;

intInitList_Sq(structSqList*L);//初始化顺序表

intListInsert_Sq(structSqList*L,inti,inte);//向顺序表中插入数据

intListDelete_Sq(structSqList*L,inti,int*e);//删除顺序表中的数据

voidListShow_Sq(structSqList*L,constchar*s);//输出顺序表中的数据

voidDestroyList(SqList*L);//销毁表

//2、SqList.cpp

#include"SqList.h"

intInitList_Sq(structSqList*L)

L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L-elem)exit(0);

L-len=0;

L-size=LIST_INIT_SIZE;

returnOK;

intListInsert_Sq(structSqList*L,inti,inte)

if(i0||iL-len)

returnERROR;

if(L-len=L-size){

int*newbase=(int*)realloc(L-elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(int));

if(!newbase)exit(0);

L-size+=LISTINCREMENT;

int*q=(L-elem[i]);

*q=e;

L-len++;

returnOK;

intListDelete_Sq(structSqList*L,inti,int*e){

if(i1||iL-len)returnERROR;

int*p=(L-elem[i-1]);

*e=*p;

int*q=L-elem+L-len-1;

for(++p;p++p)

*(p-1)=*p;

L-len--;

returnOK;

voidListShow_Sq(structSqList*L,constchar*s){

printf("%s",s);

inti;

for(i=0;iL-i++){

printf("%d",L-elem[i]);

putchar('\n');

voidDestroyList(SqList*L)

free(L-elem);

L-elem=NULL;

L-len=0;

L-size=0;

//3、链表操作.cpp

#include"SqList.h"

voidmainview_user()//界面函数

structSqListL;

InitList_Sq(

intc;

printf("------------------------------------\n");

printf("|**********线性表***************|\n");

printf("|********1输入数据***********|\n");

printf("|********2查看数据***********|\n");

printf("|********3删除数据***********|\n");

printf("|********4改数据*********|\n");

printf("|********5插入数据***********|\n");

printf("|********0退出系统***********|\n");

printf("------------------------------------\n");

printf("\n");

while(1)

printf("请选择：");

scanf_s("%d",

switch(c)

case1:{

intn=0;

printf("输入要插入的数据个数：");

scanf_s("%d",

for(inti=0;ii++){

intt;

scanf_s("%d",

ListInsert_Sq(L,L.len,t);

}break;

case2:{

ListShow_Sq(L,"现在的数据为：");

system("pause");break;

case3:{

ints,v;

printf("请输入数据删除的位置s：");

scanf_s("%d",

if(ListDelete_Sq(L,s,v))

printf("删除成功.删除的数据是：%d\n",v);

else

printf("删除失败.位置有误.");

break;

case4:{

printf("请输入想要修改的位置:");

ints,v;

scanf_s("%d",

if(s1||sL.len)

printf("数据非法");

else{