順序表的插入

需要平均移動約表長一半的元素，具體移動的元素個數(shù)與該元素在線性表中的位置有關(guān)。添加到第1個,移動N個元素；添加到第2個,移動(N-1)個元素；……添加到第N個,移動1個元素；添加到第(N+1)個,移動0個元素 平均：(0+1+2+……+N)/(N+1)=N/2刪除第1個,移動(N-1)個；刪除第2個,移動...

需向前移動n-i個元素。這個i的范圍應(yīng)當是1≤i≤n+1，是向后移動。后面的元素ai+1~an都要向上移動一個位置。如順序表的每個結(jié)點占用len個內(nèi)存單元，用location (ki)表示順序表中第i個結(jié)點ki所占內(nèi)存空間的第1個單元的地址。則有如下的關(guān)系:location (ki+1) = location (ki) +len。

這個很好理解，順序表里原本有n個元素，每個元素的位置都可以插入，這時的情況會產(chǎn)生移動；另一種情況就是直接插在末尾，這時不需要挪動元素。綜上就是N+1個位置。

我們假設(shè)順序表長度為n，由于順序表的結(jié)點之間邏輯關(guān)系為鄰接關(guān)系，所以當我們要將一個結(jié)點插入時，這個插入位置的后面的結(jié)點每一個都要移動以給新插入的結(jié)點讓出位置，同時順序表的長度加一，所以順序表插入一個結(jié)點，平均需要移動n/2個結(jié)點，由于移動了n/2個結(jié)點我們插入一個結(jié)點的移動次數(shù)就是n/2。...

最好情況：新元素插入到表尾, 則不需要移動元素 i = n+1, 循環(huán)0次; 即最好時間復(fù)雜度 = O(1)最壞情況：新元素插入到表頭, 則表中的 n 個元素需要全部移動 i =1; 循環(huán)n次, 最壞時間復(fù)雜度 = O(n)平均：新元素插入有(n+1)種選擇,即插入每個位置的概率都是 p= 1/(n+1)平均循環(huán)...

void create();//建表 void insert();//插入 ElemType delet();void display();void inverse();//逆轉(zhuǎn)函數(shù) };//創(chuàng)建空鏈表 LinkList::LinkList(){ Head=new NodeType;Head->next=NULL;Head->data=0;} LinkList::~LinkList(){ NodeType *p=Head->next;//使指針p指向鏈表的第一個節(jié)點 w...

添加到第1個,移動N個；添加到第2個,移動(N-1)個；……添加到第N個,移動1個；添加到第(N+1)個,移動0個 平均：(0+1+2+……+N)/(N+1)=N/2 刪除第1個,移動(N-1)個；刪除第2個,移動(N-2)個；……刪除第N個,移動0個 平均：[0+1+……+(N-1)]/N=(N-1)/2 ...

在一個已有n個數(shù)據(jù)的順序表中插入一個數(shù)據(jù)時，最好的情況是移動0個數(shù)據(jù)，最壞的情況是移動n個數(shù)據(jù)，而“好壞”程序則是隨機的。所以其平均移動次數(shù)為（0+n）/2=n/2次。

首先，這里的i應(yīng)該是位置，而不是下標。當i的值是[1,L->length+1]時，都是有效的插入位置。1表示用待插入元素取代第1個元素，L->length+1表示插入到最后一個元素的后面，實際上就是追加一個元素。只有當i<1 || i>L->length+1時插入位置才無效。如果改成i<1 || i>L->length，則會不...

// 將順序表第i-1個元素至最后一個元素全部向后移動一位for(j=L->last; j>=i-1; j--) L->data[j+1] = L->data[j]// 將新元素x插入到原第i-1個元素的位置L->data[i-1] = x;// 更新順序表長度L->last++;