1、線性表--順序表
在計(jì)算機(jī)內(nèi)部存儲(chǔ)一張線性表（線性結(jié)構(gòu)的數(shù)表），最為方便簡(jiǎn)單的就是用一組連續(xù)地址的內(nèi)存單元來(lái)存儲(chǔ)整張線性表。
這種存儲(chǔ)結(jié)構(gòu)稱為順序存儲(chǔ)結(jié)構(gòu)，這種存儲(chǔ)結(jié)構(gòu)下的線性表就叫做順序表。
定義一張順序表也就是在內(nèi)存中開(kāi)辟一段連續(xù)的存儲(chǔ)空間，并給它一個(gè)名字進(jìn)行標(biāo)識(shí)。
只有定義了一個(gè)順序表，才能利用該順序表存放數(shù)據(jù)元素，也才能對(duì)該順序表進(jìn)行各種操作。
有兩種定義順序表的方法：一是靜態(tài)地定義一張順序表；二是動(dòng)態(tài)地生成一張順序表。
靜態(tài)地定義一張順序表的方法與定義一個(gè)數(shù)組的方法類似。
2）元素的插入
在長(zhǎng)度為n的順序表中的第i個(gè)位置插入新元素item。
所謂在長(zhǎng)度為n的順序表中的第i個(gè)位置插入新元素，是指在順序表第i–1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入一個(gè)新元素item。
例如順序表為：A(a1, a2,…ai–1, ai,…an)
在第i個(gè)位置插入新元素item后，該順序表變?yōu)椋篈(a1, a2,…ai–1,,item, ai,…an) 而此時(shí)順序表A的長(zhǎng)度由n變?yōu)?em>n+1。
其實(shí)現(xiàn)過(guò)程如下：
（1）判斷插入元素的位置是否合法。一個(gè)長(zhǎng)度為n的順序表的可能插入元素的位置是0～n，因此如果i<0或者i>n的插入都是非法的。
（2）將順序表的i–1以后的元素順序后移一個(gè)元素的位置，即：將順序表從第i個(gè)元素到第n個(gè)元素順序后移一個(gè)元素的位置。
（3）在表的第i個(gè)位置（下標(biāo)為i–1）上插入元素item，并將表長(zhǎng)加1。
3）元素的刪除
（1）判斷要?jiǎng)h除的元素是否合法。對(duì)于一個(gè)長(zhǎng)度為n的順序表，刪除元素的合法位置是0～n-1，因此如果i<0或者i>n-1都是不合法的。
（2）將順序表的第i位置以后的元素依次前移，這樣會(huì)將第i個(gè)元素覆蓋，也就起到刪除第i個(gè)位置元素的作用。
（3）最后將表長(zhǎng)減1。
靜態(tài)順序表的創(chuàng)建，插入和刪除的代碼如下：
#include#includeusing?namespace?std;
#define?MaxSize?20
typedef?int?Elemtype;
Elemtype?sqlist[MaxSize];
int?len?=0;//靜態(tài)順序表中的元素個(gè)數(shù)
void?InsertList(Elemtype?*sqlist,int?i,Elemtype?item)
{
if(ilen)?exit(0);
if(len==MaxSize)?exit(0);
for(int?t=len;t>i;t--)
{
sqlist[t]?=?sqlist[t-1];
}
sqlist[i]=item;
len++;
}
void?DeleteList(Elemtype?*sqlist,int?index)
{
if(index=len)?exit(0);
for(int?i=index;i<len-1;i++)
{
sqlist[i]?=?sqlist[i+1];
}
len--;
}
void?PList(Elemtype?*sqlist)
{
for(int?i=0;i<len;i++)
{
cout<<sqlist[i]<<"t";
if((i+1)%5?==?0)?cout<<endl;
}
}
int?main()
{
for(int?i=0;i<10;i++)
{
InsertList(sqlist,i,i+2);
}
printf("The?sqlist?is?as?below:n");
PList(sqlist);
DeleteList(sqlist,3);
printf("After?delete?the?sqlist?is?:n");
PList(sqlist);
system("pause");
return?0;
}輸出結(jié)果如下：
動(dòng)態(tài)順序表的創(chuàng)建，插入和刪除的代碼如下：
#include#includeusing?namespace?std;
#define?MaxSize?20
typedef?int?Elemtype;
typedef?struct
{
Elemtype?*elem;?//指向順序表首地址的指針
int?len;?//順序表的長(zhǎng)度（表中的元素個(gè)數(shù)）
int?listsize;?//順序表的容量
}SqList;
//initial?Sqlist?初始化一張空的順序表
void?InitSqList(SqList?*L)
{
L->elem?=?(Elemtype?*)malloc(MaxSize*sizeof(Elemtype));
if(!L->elem)?exit(0);
L->len?=?0;
L->listsize?=?MaxSize;
}
/*?insert?element
???向順序表中的第i個(gè)位置插入元素item
???1)?判斷插入位置是否合理；如果ilist->len,報(bào)錯(cuò)。
???2）判斷線性表的長(zhǎng)度。如果len>=listsize,拋出異?；騽?dòng)態(tài)增加容量。
???3）從最后一個(gè)元素開(kāi)始向前遍歷到第i個(gè)位置，分別將它們都向后移動(dòng)一個(gè)位置。
???4）將要插入的元素填入位置i處。
???5）表長(zhǎng)加1.
*/
void?Insert(SqList?*sqlist,int?i,Elemtype?item)
{
Elemtype?*base;
if(isqlist->len)?exit(0);//這里的位置是對(duì)應(yīng)的下標(biāo)，從0開(kāi)始。非法插入
if(sqlist->len==sqlist->listsize)?//表已滿
{
base?=?(Elemtype?*)realloc(sqlist->elem,(sqlist->listsize+10)*sizeof(Elemtype));//重新追加空間
sqlist->elem?=?base;
sqlist->listsize?+=?10;
}
for(int?t=sqlist->len-1;t>=i;t--)
{
sqlist->elem[t+1]=sqlist->elem[t];
}
sqlist->elem[i]=item;
sqlist->len++;
}
/*?delete?element
???刪除指定位置i對(duì)應(yīng)的元素
???1）判斷i的位置是否合法。如果i=list->len?報(bào)錯(cuò)。
???2)?將順序表的第i位置以后的元素依次前移，這樣會(huì)將第i個(gè)元素覆蓋，也就起到刪除第i個(gè)位置元素的作用
???3）表的長(zhǎng)度減1.
*/
void?Delete(SqList?*sqlist,int?index)
{
if(index=sqlist->len)?exit(0);
for(int?t=index;tlen-1;t++)
{
sqlist->elem[t]=sqlist->elem[t+1];
}
sqlist->len--;
}
/*?if?exit
???判斷給定的元素是否在順序表中
*/
bool?Ifexist(SqList?&list,Elemtype?item)
{
bool?flag?=?false;
for(int?i=0;i<list.len;i++)
{
if(item==list.elem[i])?
flag?=?true;
}
return?flag;
}
//printf
void?Pout(SqList?&list)
{
int?le?=?list.len;
for(int?i=0;i<le;i++)
{
cout<<list.elem[i]<<"t";
if((i+1)%5==0)?cout<<endl;
}
}
int?main()??
{
?
SqList?sqlist;
InitSqList(&sqlist);
SqList?&s=sqlist;
for(int?i=0;i<10;i++)
{
Insert(&sqlist,i,i+3);
}
printf("The?element?in?sqlist?as?below:n");
Pout(s);
if(Ifexist(s,12))?cout<<"12在順序表中。";
Delete(&sqlist,3);//刪除下標(biāo)3所對(duì)應(yīng)的元素
printf("nAfter?delete?index?3?sqlist?is:n");
Pout(s);
Delete(&sqlist,4);//刪除下標(biāo)4所對(duì)應(yīng)的元素
printf("nAfter?delete?index?4?sqlist?is:n");
Pout(s);
system("pause");??
return?0;??
}輸出結(jié)果如下：
?
下載文檔
