順序表

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)存中開辟一段連續(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(a₁, a₂,…a_i–1, a_i,…a_n)

在第i個(gè)位置插入新元素item后，該順序表變?yōu)椋篈(a₁, a₂,…a_i–1,,item, a_i,…a_n) 而此時(shí)順序表A的長(zhǎng)度由n變?yōu)?em>n+1。

其實(shí)現(xiàn)過程如下：

（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è)元素開始向前遍歷到第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開始。非法插入
	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é)果如下：

?