順序表的動(dòng)態(tài)分配
元素為int類(lèi)型
與靜態(tài)分配的區(qū)別,主要體現(xiàn)在定義,初始化,銷(xiāo)毀,自動(dòng)增長(zhǎng)
查找,賦值操作是差不多的
重載的方式來(lái)實(shí)現(xiàn)動(dòng)態(tài)分配的
定義
image-20210329111015697
typedef struct{
int *data;
int length; //當(dāng)前長(zhǎng)度
int maxsize; //最大容量
}Dynamiclist;
初始化
void initDynamicList(Dynamiclist & l){
l.data=(int *)malloc(sizeof(int) * MAXSIZE);
if(!l.data){! cout <<"分配失敗" <<endl;
}
for(int i=0;i<MAXSIZE;i++){
l.data[i]=0;
}
l.length=0;
l.maxsize=MAXSIZE;
}
銷(xiāo)毀
為了健壯性,最后再令其為空指針
bool destroyList(Dynamiclist &l){
free(l.data);
l.length=0;
l.maxsize=0;
l.data=nullptr;
if(!l.data){
return true;
}
return false;
}
增長(zhǎng)
void increaseList(Dynamiclist &l,int n){
int * p =l.data;
l.data=(int *)malloc(sizeof(int)*(l.maxsize+n));
for(int i=0;i<l.length;i++){ //改變的是data length還沒(méi)變
l.data[i]=p[i];
}
l.maxsize+=n;
free(p);
}
插入元素
當(dāng)長(zhǎng)度滿(mǎn)了的時(shí)候,自動(dòng)擴(kuò)增指定長(zhǎng)度的
bool insertList(Dynamiclist & l,int n,int number){
if(n<0||n>l.length+1){
cout <<"下標(biāo)有誤" <<endl;
return false;
}
if(l.length>=l.maxsize){
//自動(dòng)增長(zhǎng)長(zhǎng)度 MAXSIZE
increaseList(l,MAXSIZE);
}
for(int i=l.length;i>=n;i++){
l.data[i]=l.data[i-1];
}
l.data[n-1]=number;
l.length++;
return true;
}
刪除
bool deleteListByOrder(Dynamiclist & l,int n,int &number){
if(n<0||n>l.length){
cout <<"下標(biāo)有誤" <<endl;
return false;
}
number=l.data[n-1];
for(int i=n;i<l.length;i++){
l.data[i-1]=l.data[i];
}
l.length--;
return false;
}
查找
注意這里的數(shù)組形式,因?yàn)榉峙涞臅r(shí)候,malloc(int)長(zhǎng)度為單位的,用數(shù)組[]內(nèi)部會(huì)自動(dòng)轉(zhuǎn)換成地址加長(zhǎng)度,即下一個(gè)
int findElementByOrder(Dynamiclist l,int n){
return l.data[n-1];
}
int findElementByValue(Dynamiclist l,int num){
for(int i=0;i<l.length;i++){
if(l.data[i]==num){
return i+1;
}
}
return -1;
}
其他
void printList(Dynamiclist l){
for(int i=0;i<l.length;i++){
cout << "第" << i+1 << "個(gè)元素是" <<l.data[i] <<endl;
}
}
int lengthOfList(Dynamiclist l){
return l.length;
}
bool isEmpty(Dynamiclist l){
if(!l.length){
return true;
}
return false;
}
結(jié)果
==代碼測(cè)試==
void test_dy(){
Dynamiclist l;
initDynamicList(l);
//表空
if(isEmpty(l)){
cout <<"表空" <<endl;
}
if(insertList(l,1,0)){
cout <<"插入成功" <<endl;
}
//循環(huán)插入9個(gè)數(shù)
for(int i=1;i<10;i++){
insertList(l,i+1,i);
}
printList(l);
//插入十個(gè)數(shù)后自動(dòng)增長(zhǎng),不會(huì)報(bào)錯(cuò)
insertList(l,11,11);
cout <<"表長(zhǎng)為" <<lengthOfList(l) <<endl;
//查找5
cout <<"5的位序是" <<findElementByValue(l,5) <<endl;
//查找位置6
cout <<"位置6的是" <<findElementByOrder(l,6) <<endl;
//刪除位置6
int num;
deleteListByOrder(l,6,num);
cout <<"刪除的是" <<num<<endl;
printList(l);
//銷(xiāo)毀
destroyList(l);
cout <<"表空?"<<isEmpty(l)<<endl;
==結(jié)果==
表空
插入成功
第1個(gè)元素是0
第2個(gè)元素是1
第3個(gè)元素是2
第4個(gè)元素是3
第5個(gè)元素是4
第6個(gè)元素是5
第7個(gè)元素是6
第8個(gè)元素是7
第9個(gè)元素是8
第10個(gè)元素是9
表長(zhǎng)為11
5的位序是6
位置6的是5
刪除的是5
第1個(gè)元素是0
第2個(gè)元素是1
第3個(gè)元素是2
第4個(gè)元素是3
第5個(gè)元素是4
第6個(gè)元素是6
第7個(gè)元素是7
第8個(gè)元素是8
第9個(gè)元素是9
第10個(gè)元素是11
表空?1
