C語言超詳細講解數(shù)據(jù)結構中的線性表

第C語言超詳細講解數(shù)據(jù)結構中的線性表目錄前言一、分文件編寫1、分文件編寫概念2、代碼展示二、動態(tài)分布內(nèi)存malloc1、初識malloc2、使用方法三、創(chuàng)建鏈表并進行增刪操作1、初始化鏈表2、在鏈表中增加數(shù)據(jù)3、刪除鏈表中指定位置數(shù)據(jù)四、代碼展示與運行效果1、代碼展示2、運行效果總結

前言

計算機專業(yè)都逃不了數(shù)據(jù)結構這門課，而這門課無疑比較難理解，所以結合我所學知識，我準備對順序表做一個詳細的解答，為了避免代碼過長，采用分文件編寫的形式，不僅可以讓代碼干凈利落還能提高代碼可讀性，先解釋部分代碼的含義，最后放上代碼實現(xiàn)和效果圖，讓我們開始操作吧?。。?/p>

一、分文件編寫

1、分文件編寫概念

在VisualStdio編譯器中我們可以通過創(chuàng)建.h頭文件和.cpp源文件來實現(xiàn)程序運行，使代碼更美觀，可讀性高，如圖所示：

SqList.h頭文件和Sq.List.cpp源文件分別存放全局變量、結構體及函數(shù)的聲明和對應函數(shù)的完整實現(xiàn)代碼。我們需要注意的是頭文件和源文件的名稱要一致，而且源文件要引用頭文件（#includeSqList.h)，使用而不用的原因是頭文件是我們自己寫的，只能用引用。

2、代碼展示

SqList.cpp內(nèi)容如下：

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);//向順序表中插入數(shù)據(jù)

intListDelete_Sq(structSqList*L,inti,int*e);//刪除順序表中的數(shù)據(jù)

voidListShow_Sq(structSqList*L,constchar*s);//輸出順序表中的數(shù)據(jù)

voidDestroyList(SqList*L);//銷毀表

SqList.cpp部分內(nèi)容如下：

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

}

二、動態(tài)分布內(nèi)存malloc

1、初識malloc

C語言中malloc是動態(tài)內(nèi)存分配函數(shù)。

函數(shù)原型：void*malloc(unsignedintnum_bytes);

參數(shù)：num_bytes是無符號整型，用于表示分配的字節(jié)數(shù)。

返回值：如果分配成功則返回指向被分配內(nèi)存的指針(此存儲區(qū)中的初始值不確定)，否則返回空指針NULL。void*表示未確定類型的指針，void*可以指向任何類型的數(shù)據(jù)，更明確的說是指申請內(nèi)存空間時還不知道用戶是用這段空間來存儲什么類型的數(shù)據(jù)（比如是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調(diào)用int*elem屬性，因此malloc需要返回（int*）類型的指針，同時malloc右邊括號放的是內(nèi)存空間，大小就是宏定義的數(shù)值乘以整型(int)所占字節(jié)數(shù)，在這里說白了就是10*4個字節(jié)。模板可以這樣看：(分配類型*)malloc(分配元素個數(shù)*sizeof(分配類型))如果成功，則返回該空間首地址，該空間沒有初始化，如果失敗，則返回0

三、創(chuàng)建鏈表并進行增刪操作

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分配內(nèi)存空間，如果失敗返回零，成功就返回內(nèi)存空間首地址，并把鏈表長度置為零，鏈表最大長度設為LIST_INIT_SIZE（大小為10）

2、在鏈表中增加數(shù)據(jù)

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條件我們會覺得條件永遠成立，實際上下面插入數(shù)據(jù)后會進行加一操作，因此插入數(shù)據(jù)只能挨個插入;第二個if不難理解，如果鏈表長度達到最大長度，進行空間擴容，從而可以插入更多數(shù)據(jù)；后面其實是尾插法，讓*q指向鏈表的最后一個位置，把數(shù)據(jù)放到里面，然后長度加一，插入數(shù)據(jù)結束。

3、刪除鏈表中指定位置數(shù)據(jù)

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是該位置的數(shù)據(jù)，這樣我們就能知道刪除元素的值了，然后我定義*q為鏈表中最后一個元素的地址，隨后重復讓鏈表刪除位置后的元素前移，最后鏈表總長度減一，刪除結束。修改鏈表利用插入和刪除操作結合就可以完成，這里沒有單獨定義方法，具體內(nèi)容會在下面的總代碼體現(xiàn)。

四、代碼展示與運行效果

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);//向順序表中插入數(shù)據(jù)

intListDelete_Sq(structSqList*L,inti,int*e);//刪除順序表中的數(shù)據(jù)

voidListShow_Sq(structSqList*L,constchar*s);//輸出順序表中的數(shù)據(jù)

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()//界面函數(shù)

structSqListL;

InitList_Sq(

intc;

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

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

printf("|********1輸入數(shù)據(jù)***********|\n");

printf("|********2查看數(shù)據(jù)***********|\n");

printf("|********3刪除數(shù)據(jù)***********|\n");

printf("|********4改數(shù)據(jù)*********|\n");

printf("|********5插入數(shù)據(jù)***********|\n");

printf("|********0退出系統(tǒng)***********|\n");

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

printf("\n");

while(1)

printf("請選擇：");

scanf_s("%d",

switch(c)

case1:{

intn=0;

printf("輸入要插入的數(shù)據(jù)個數(shù)：");

scanf_s("%d",

for(inti=0;ii++){

intt;

scanf_s("%d",

ListInsert_Sq(L,L.len,t);

}break;

case2:{

ListShow_Sq(L,"現(xiàn)在的數(shù)據(jù)為：");

system("pause");break;

case3:{

ints,v;

printf("請輸入數(shù)據(jù)刪除的位置s：");

scanf_s("%d",

if(ListDelete_Sq(L,s,v))

printf("刪除成功.刪除的數(shù)據(jù)是：%d\n",v);

else

printf("刪除失敗.位置有誤.");

break;

case4:{

printf("請輸入想要修改的位置:");

ints,v;

scanf_s("%d",

if(s1||sL.len)

printf("數(shù)據(jù)非法");

else{