① 順序存儲結構與鏈式存儲結構
概念官方一點來說可以使用 網路 的介紹：順序存儲結構是存儲結構類型中的一種，該結構是把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中，結點之間的邏輯關系由存儲單元的鄰接關系來體現。
簡單來說就是： 用一段連續的地址存放數據元素，數據間的邏輯關系和物理關系相同。
優點1：存儲密度大，空間利用度高，比鏈式存儲節約空間
優點2：存儲操作上方便操作，順序支持隨機存取，查找會比較容易
缺點1：插入或者刪除元素時不方便，花費的時間更多
概念：鏈式存儲結構，又叫鏈接存儲結構。在計算機中用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續的,也可以是不連續的).它不要求邏輯上相鄰的元素在物理位置上也相鄰.因此它沒有順序存儲結構所具有的弱點,但也同時失去了順序表可隨機存取的優點
優點1：插入或刪除時方便些，空間使用靈活
缺點1：存儲密度小，空間利用度低
缺點2：查找會相較順序存儲方式復雜一些，花費的時間會更多
這里我們先看圖，其實就是將想要插入的元素往鏈表的尾部插入，然後更新一下為節點tail的位置即可。
今天我們的老師將這個內容的時候提到怎麼一句話「誰想進來，誰就去找組織」看這個圖我想你應該可以理解這句話，首先第一步需要我們的「C」去找組織中的A，第二步是頭結點接到新元素C上。
要想移除單向鏈表中的一個元素，首先我們得找到被移除結點的前驅的位置，比如是pre「A」。當前移除的元素是remove「B」，讓pre->next = remove->next, 然後再執行remove->next = nil。經過上面這些步驟，B就與鏈表脫離關系了。
但是在網路上面看到怎麼一句話
鏈式的要比順序的方便（這句話是不能這么說的，因為插入的話順序表也很方便，問題是順序表的插入要執行更大的空間復雜度，包括一個從表頭索引以及索引後的元素後移，而鏈表是索引後，插入就完成了）
② 順序表的插入與刪除的時間主要花在什麼操作上
順序表的插入和刪除操作的時間主要耗費在移動元素上，而移動元素的個數取決於插入和刪除元素的位置。
最好情況：查找的元素就在表頭，僅需比較一次，時間復雜度為O(1)。
最壞情況：查找的元素在表尾（或不存在）時，需要比較n次，時間復雜度為O(n)。
順序表是在計算機內存中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中。
即通過數據元素物理存儲的相鄰關系來反映數據元素之間邏輯上的相鄰關系，採用順序存儲結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續的存儲單元中。
順序表簡介：
將表中元素一個接一個的存入一組連續的存儲單元中，這種存儲結構是順序結構。
採用順序存儲結構的線性表簡稱為「 順序表」。順序表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素佔用存儲單元的長度。
③ 順序存儲結構線性表的插入與刪除
順序表的插入與刪除，其實都是一個查找和移動的過程。插入與刪除分為 按位置和按值插入和刪除。1）按位置比較簡單，插入時，從表尾開始到要插入的位置，每個元素向後面移動一個位置，最後將要插入的值放入即可。刪除的話，直接從要刪除的後一個開始，所有元素向前移動一個位置即可。
2）按值刪除，先需要查找，可以選擇順序查找，二分查找（有序表）等。找到後，記錄位置，後面的操作與第一種情況一樣。
插入演算法：
void inert(int i,int data,List L)//要插入的位置,插入的數據,
{
int start=i;
int end=L.length-1;
for(int i=end;i--;i>start)
L.data[i+1]=L.data[i]
L.data[i]=data;
L.length++;
}
④ 順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好
該說法錯誤。在順序存儲方式中如果元素的插入或者刪除不牽扯到元素的移動的話，鏈式的優勢體現不出來。另外，在鏈式存儲中，元素的存取機制是順序；順序存儲中，元素的存取機制是隨機的。從元素訪問方面來講，要想訪問某個位置的元素時，在順序存儲要比鏈式存儲好很多，在順序存儲可以直接訪問，鏈式存儲則需要從鏈頭開始訪問，一直到目標點。
⑤ 順序存儲結構線性表的插入與刪除
順序表的插入與刪除，其實都是一個查找和移動的過程。插入與刪除分為
按位置和按值插入和刪除。1)按位置比較簡單，插入時，從表尾開始到要插入的位置，每個元素向後面移動一個位置，最後將要插入的值放入即可。刪除的話，直接從要刪除的後一個開始，所有元素向前移動一個位置即可。
2)按值刪除，先需要查找，可以選擇順序查找，二分查找(有序表)等。找到後，記錄位置，後面的操作與第一種情況一樣。
插入演算法:
void
inert(int
i,int
data,List
L)//要插入的位置,插入的數據,
{
int
start=i;
int
end=L.length-1;
for(int
i=end;i--;i>start)
L.data[i+1]=L.data[i]
L.data[i]=data;
L.length++;
}
⑥ 假設線性表採用順序表為存儲結構，其插入與刪除在什麼位置最快
都是在末尾插入和刪除最快
如果插入在中間甚至在表頭，那樣要後移插入位置後面的所有結點一個單位，而如果是在表尾插入的話，只需要直接添加一個結點即可。
刪除同理，如果我們是在中間刪除，要將刪除位置後面的結點都前移一個單位，而如果是在表尾刪除的話，只需要將最後一個刪除點即可。
順序存儲結構最耗時的是移動結點的操作。
⑦ 如何建立一個順序存儲的線性表，實現線性表的插入、刪除操作
順序存儲結構線性表基本操作 C語言實現
#include<stdio.h>
//以下為函數運行結果狀態代碼
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
#defineLIST_INIT_SIZE100//線性表存儲空間的初始分配量
#defineLISTINCREMENT10//線性表存儲空間分配增量
typedefintStatus;//函數類型，其值為為函數結果狀態代碼
typedefintElemType;//假設數據元素為整型
typedefstruct
{
ElemType*elem;//存儲空間基址
intlength;//當前長度
intlistsize;//當前分配的存儲容量
}SqList;
//實現線性表的順序存儲結構的類型定義
//函數聲明開始
StatusInitList_Sq(SqList&L);
voidDestroyList_Sq(SqList&L);
voidClearList_Sq(SqList&L);
voidListEmpty_Sq(SqListL);
StatusGetElem_Sq(SqListL,i,&e);
intLocateElem_Sq(SqListL,e,compare());
StatusPriorElem_Sq(SqListL,cur_e,&pre_e);
StatusNextElem_Sq(SqListL,cur_e,&next_e);
StatusListInsert_Sq(SqList&L,i,e);
StatusListDelete_Sq(SqList&L,i,&e);
ListTravel_Sq(SqListL,visit());
//函數聲明結束
intmain(void)
{
return0;
}
//函數定義開始
///////////////////////////////////////
//函數名：InitList_Sq()
//參數：SqList*L
//初始條件：無
//功能：構造一個空線性表
//返回值：存儲分配失敗：OVERFLOW
//存儲分配成功：OK
///////////////////////////////////////
StatusInitList_Sq(SqList*L)
{
L.elem=(ElemType*)malloc((LIST_INIT_SIZE*sizeof(ElemType));//分配空間
if(!L.elem)
exit(OVERFLOW);//若存儲分配失敗，返回OVERFLOW
L.length=0;//空表，長度為0
L.listsize=LIST_INIT_SIZE;//初始存儲容量
returnOK;
}
///////////////////////////////////////
//函數名：DestroyList_Sq()
//參數：SqList*L
//初始條件：線性表L已存在
//功能：銷毀線性表
//返回值：無
///////////////////////////////////////
voidDestroyList_Sq(SqList*L)
{
if(L->elem)
free(L->elem);//釋放線性表占據的所有存儲空間
}
///////////////////////////////////////
//函數名：ClearList_Sq()
//參數：SqList*L
//初始條件：線性表L已存在
//功能：清空線性表
//返回值：無
///////////////////////////////////////
voidClearList_Sq(SqList*L)
{
L->length=0;//將線性表的長度置為0
}
///////////////////////////////////////
//函數名：ListEmpty_Sq()
//參數：SqListL
//初始條件：線性表L已存在
//功能：判斷線性表是否為空
//返回值：空：TRUE
//非空：FALSE
///////////////////////////////////////
StatusListEmpty_Sq(SqListL)
{
if(L.length==0)
returnTRUE;
else
returnFALSE;
}
///////////////////////////////////////
//函數名：ListLength_Sq()
//參數：SqListL
//初始條件：線性表L已存在
//功能：返回線性表長度
//返回值：線性表長度(L.length)
///////////////////////////////////////
StatusListLength_Sq(SqListL)
{
return(L.length);
}
///////////////////////////////////////
//函數名：GetElem_Sq()
//參數：SqListL,inti,ElemType*e
//初始條件：線性表L已存在，1<=i<=ListLength(L)
//功能：用e返回線性表中第i個元素的值
//返回值：(i<1)||(i>ListLength(L))：ERROR
//1<=i<=ListLength(L)：OK
///////////////////////////////////////
StatusGetElem_Sq(SqListL,inti,ElemType*e)
{
if(i<1||i>L.length)
returnERROR;//判斷i值是否合理，若不合理，返回ERROR
*e=L.elem[i-1];//數組中第i-1的單元存儲著線性表中第i個數據元素的內容
returnOK;
}
///////////////////////////////////////
//函數名：LocateElem_Sq()
//參數：L,e,compare(ElemType1,ElemType2)
//初始條件：線性表L已存在，compare()為數據元素判定函數
//功能：返回順序表L中第1個與e滿足關系compare()的數據元素的位序
//返回值：若在L中存在於e滿足關系compare()的元素：其位序
//若在L中不存在於e滿足關系compare()的元素：0
///////////////////////////////////////
intLocateElem_Sq(SqListL,e,compare(ElemType1,ElemType2))
{
inti=1;//i的初值為第1元素的位序
intp=L.elem;//p的初值為第1元素的存儲位置
while(i<=L.length&&!(*compare)(*p++,e))
++i;//依次進行判定
if(i<=L.length)
returni;//找到滿足判定條件的數據元素為第i個元素
else
return0;//該線性表中不存在滿足判定的數據元素
}
StatusPriorElem_Sq(SqListL,cur_e,&pre_e);
//見StatusNextElem_Sq(SqListL,cur_e,&next_e);
StatusNextElem_Sq(SqListL,cur_e,&next_e);
//我的思路是先用LocateElem_Sq()搜索cur_e的位序，
//再看是否大於等於length，
//若是，則返回OVERFLOW；否則返回後繼
//這樣也許有點麻煩？所以希望大家能夠補充方案
//bywangweinoo1
///////////////////////////////////////
//函數名：ListInsert_Sq()
//參數：SqList*L,inti,ElemTypee
//初始條件：線性表L已存在，1<=i<=ListLength(L)+1
//功能：在線性表中第i個數據元素之前插入數據元素e
//返回值：失敗：ERROR
//成功：OK
///////////////////////////////////////
StatusListInsert_Sq(SqList*L,inti,ElemTypee)
{
ElemType*j;
if(L->length==LIST_MAX_LENGTH)
returnERROR;//檢查是否有剩餘空間
if(i<1||i>L->length+1)
returnERROR;//檢查i值是否合理
//將線性表第i個元素之後的所有元素向後移動
for(j=L->length-1;j>=i-1;i++)
L->elem[j+1]=L->elem[j];
L->elem[i-1]=e;//將新元素的內容放入線性表的第i個位置，
L->length++;
returnOK;
}
///////////////////////////////////////
//函數名：ListDelete_Sq()
//參數：SqList*L,inti,Elemtype*e
//初始條件：線性表L已存在，1<=i<=ListLength(L)
//功能：將線性表L中第i個數據元素刪除
//返回值：失敗：ERROR
//成功：OK
///////////////////////////////////////
intListDelete_Sq(SqList*L,inti,Elemtype*e)
{
if(IsEmpty(L))
returnERROR;//檢測線性表是否為空
if(i<1||i>L->length)
returnERROR;//檢查i值是否合理
*e=L->elem[i-1];//將欲刪除的數據元素內容保留在e所指示的存儲單元中
//將線性表第i+1個元素之後的所有元素向前移動
for(j=i;j<=L->length-1;j++)L->elem[j-1]=L->elem[j];
L->length--;
returnOK;
}
//函數定義結束
⑧ 為什麼在順序存儲結構下，棧的插入和刪除運算都不需要移動表中其他數據元素，如果在鏈式存儲結構下會怎樣
棧也被叫做"先進後出表",正是由於這種性質,讓它可以不需要移動元素實現插入和刪除.
棧的插入,其實就是壓棧,它是被嚴格限制在棧頂進行的.由於棧頂也是表中最後一個元素,所以壓棧也就相當於是在順序表的最後追加一個元素,這顯然不影響前面的元素,也就無需移動其他元素了.
刪除也是同樣的道理,彈棧(刪除操作)也是被嚴格限制在棧頂進行,這時候刪除一個元素只需要在順序表中去除最後一個元素,自然也不影響之前的元素.
鏈式結構對於棧來說,同樣不需要作任何其他元素的移動.事實上,鏈式結構的刪除和插入操作本身就不需要移動其他元素,無論是對於棧來說還是對於一般的鏈表.
⑨ 為什麼說在順序存儲結構下，棧的插入和刪除運算不需移動表中其他數據元素
棧的插入(入棧)和刪除（出棧）運算，都是在棧的同一端進行。所以在順序存儲結構下，棧的入棧與出棧只需移動棧頂指針即可。
如用數組表示棧時，設a[]表示棧，top表示棧頂，x表示欲入（出）棧的元素，則入棧只需：a[top]=x;；top++，出棧只需：top--；x=a[top]。
如用鏈表表示棧，對於不使用頭結點的情形，入棧和出棧時也不需要移動表中其他數據元素；對於使用頭結點的情形，入棧和出棧時需要修改頭結點的指針。
⑩ 鏈式存儲插入和刪除的時間復雜度
計算機的線性表中有兩種基本的存儲方式： 順序存儲 和 鏈式存儲 。順序存儲指的是用一段地址連續的存儲單元依次存儲數據；而鏈式存儲中數據元素可以散亂的存儲到存儲單元中，每一個數據元素中包含數據項和下一個元素的存儲地址。
通過二者的定義不難看出，順序存儲在查找時的時間復雜度為 O(1) ，因為它的地址是連續的，只要知道首元素的地址，根據下標可以很快找到指定位置的元素，而對與插入和刪除操作由於可能要在插入前或刪除後對元素進行移動，所以順序存儲的時間復雜度為 O(n) 。鏈式存儲的特性則正好相反，在查找時需要從頭元素逐個尋找，因此查找的時間復雜度為 O(n) ,而對於插入和刪除操作，由於只需要變更數據元素中下一元素的存儲地址即可，因此時間復雜度為 O(1) 。
表面上看上面的說法沒有什麼問題，但其實在日常的使用中，比如要在數據集合的第i個位置插入或刪除一個元素，要完成這樣一個動作，使用順序存儲需要查找到元素然後執行插入或刪除，時間復雜度為 O(1)+O(n)=O(n) ;而鏈式存儲同樣需要先查找到元素然後在插入或刪除，時間復雜度為 O(n)+O(1)=O(n) 。
所以說鏈式存儲插入和刪除的時間復雜度為O(1)的前提應該是已知元素當前的位置，否則實現在第i個位置插入或刪除一個元素，順序存儲和鏈式存儲的時間復雜度是一樣的， 都是O(n) .