#include<stdio.h>
#include<stdlib.h>

#define maxSize 10

// listInsert(&L,i,e)	在第i個(gè)位置插入指定元素e

typedef struct {
	int data[maxSize];
	int length;
}SqList;

void initList(SqList &L) {
	for(int i=0;i<L.length; i++) {
		L.data[i]=i;
	}
	L.length = 0;	
}

/**
* 思路：第i個(gè)元素及其之后的元素都向后移，i-1后面就空出來(lái)一個(gè)空地址 
* 那么新加元素就變成了第i個(gè)，原i就變成了i+1個(gè) 
* 在空出來(lái)的這個(gè)地址，即第i的位置，賦值data[i]=e  
*
*
* 怎么后移：data[i] = data[i-1]   那么i-1的位置不就空出來(lái)了嗎 
* 注意： i是位序，位序從1開(kāi)始，下標(biāo)從0開(kāi)始，位序和下標(biāo)是兩東西 
* data[下標(biāo)]獲取當(dāng)前位置的數(shù)據(jù)元素，
* 也就是說(shuō)，第i=1個(gè)位置的元素是data[0]，...第i=L.length個(gè)位置的元素是data[L.length-1] 
*/
bool listInsert(SqList &L, int i, int e) {
	/* i是位序，從1開(kāi)始，
	* 顯然：<1或者超過(guò)順序表長(zhǎng)度就是不合法的，
	* 因?yàn)榈?個(gè)位置前面沒(méi)有位置，
	* 第L.length個(gè)位置后面插入一個(gè)叫做在最后一個(gè)元素后面插入，即在第L.length+1個(gè)位置 
	* 如果直接跳L.length+1個(gè)位置，就是不合法
	* 還有就是，插入新元素之前，要先判斷下順序表的連續(xù)存儲(chǔ)空間是否還有空位置，如果已經(jīng)滿了，那肯定沒(méi)法插入
	*/
	// 為了代碼的健壯性，要加些判斷 
	if(i<1 || i>L.length+1)
		return false;
	
	if(L.length > maxSize)
		return false;
	/** 
	* 假設(shè)i=6，就是要在第6個(gè)位置插入新元素e
	* 那就要將原i=6位置的元素及其之后的以此向后移，為了拿到原i=6及其之后的元素，此時(shí)就要遍歷
	* 但是，i=5及其之前的元素是不應(yīng)該移動(dòng)的，所以在遍歷的時(shí)候，j<i=6的元素就不要操作，只操作j>=i的 
	*/
	for(int j=L.length;j>=i;j--) {
		L.data[j] = L.data[j-1];
	} 	
	// for循環(huán)執(zhí)行完后，此時(shí)原第i個(gè)及其之后的元素已經(jīng)后移了，目前第i個(gè)位置已經(jīng)空出來(lái)了，插入新元素e
	L.data[i-1] = e;		// 第i=6個(gè)位置，實(shí)際上它的數(shù)組下標(biāo)為5，就是L.data[i-1]，將數(shù)據(jù)項(xiàng)賦值為e
	L.length++;			// 長(zhǎng)度加1 
	
	return true;
}

int main() {
	SqList L;
	initList(L);
	for(int k=0;k<maxSize;k++){
		listInsert(L,k,k);
	}

	printf("%d\t數(shù)據(jù)長(zhǎng)度\n",L.length);
	for(int h=0;h<L.length;h++){
		printf("%d\t數(shù)組元素依次輸出\n",L.data[h]);
	}
	
	return 0;
}

分析一下當(dāng)前算法的時(shí)間復(fù)雜度，注意：順序表的元素移動(dòng)，是從最后一個(gè)元素依次移動(dòng)的
1、新元素插入到表尾，i=n+1，就不用移動(dòng)元素，不移動(dòng)就不要走for循環(huán)，for循環(huán)0次，時(shí)間復(fù)雜度為O(1)
2、新元素插入到表頭，i=1，就要移動(dòng)所有元素，有n個(gè)元素移動(dòng)n個(gè)，for循環(huán)n次，時(shí)間復(fù)雜度為O（n)
3、隨機(jī)插入除表頭和表尾的任意一個(gè)位置，它們的概率都相同，即i=1、2、3...length+1的概率都是P=1/(n+1)
i=1，循環(huán)n次，i=2，循環(huán)n-1次，...i=n+1，循環(huán)0次
平均循環(huán)次數(shù)=循環(huán)總次數(shù)*概率= (1+2+3+...+n+1)*1/(n+1)=(n+1)n/2 * 1/(n+1)=n/2
時(shí)間復(fù)雜度為O(n) 文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-726396.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】靜態(tài)分配的順序表插入元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！