鏈式存儲結構中的增添與刪除

① 鏈表是採用鏈式存儲結構的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高對嗎

對
因為順序結構需要整體移動
(比如要在數組中插入一個元素不是在
最後，那麼插入點後的所有元素都要
向後移，而被刪除元素後所有元素都要
向前移）
而鏈式結構只需改寫指針
就可以了

② 建立一個鏈式存儲的線性表，並實現線性表的插入和刪除操作。

Status ListInsert_Sq(SqList &L, int i, ElemType e) {
//在順序表L中第i個位置之前插入新元素e
// i的合法值為1≦i≦ListLength_Sq(L)+1
if (i<1||i>L.length+1) return ERROR; //i值不合法
if (L.length>=L.listsize) { //當前空間已滿
newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)) ;
if (!newbase) exit (OVERFLOW);
L.elem = newbase;
L.listsize=L.listsize+INCREMENT;
}
q=&(L.elem[i-1]);//q為插入位置
for (p=&(L.elem[L.length-1]), p>=q; --p)
*(p+1)=*p; //插入位置及之後的元素右移
*q=e; //插入元素
L.length++; //表長增1
return OK;
}//ListInsert_Sq

③ 若頻繁地對一個線性表進行插入和刪除操作，該線性表宜採用何種存儲結構為什麼

採用鏈式存儲結構。

根據實際需要申請內存空間，而當不需要時又可以將不用節點空間返還給系統。在鏈式存儲結構中插入和刪除操作不需要移動元素。

1、比順序存儲結構的存儲密度大(鏈式存儲結構中每個結點都由數據域與指針域兩部分組成，相比順序存儲結構增加了存儲空間)。

2、邏輯上相鄰的節點物理上不必相鄰。

3、插入、刪除靈活 (不必移動節點，只要改變節點中的指針)。

(3)鏈式存儲結構中的增添與刪除擴展閱讀；

一般在計算機的硬碟中，文件都是鏈式存儲的。多個扇區組成一個簇，簇是計算機存儲數據的基本單位。而一個文件是存儲在多個在空間上也許並不相連的簇中的。這就是鏈式存儲。但是為了能夠讀取出這個文件，計算機會在該文件第一部分的尾部寫上第二部分所在的簇號。

第二部分的尾部又寫上第三部分，以此類推，最後一部分寫上一段代碼，表示這是該文件的最後一部分。值得一提的是，高簇號在後。（如代碼所示的1234實為簇3412）文件所佔簇可認為是隨機分配的。

④ 用C語言編寫鏈式存儲結構下實現線性表的創建,插入,刪除,按值查找

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

typedef struct LNode{
int data; //鏈表數據
struct LNode* next; //鏈表指針
}LNode,*LinkList;

/*頭插法-建立單鏈表*/
LinkList HeadCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode)); //建立頭結點
la->next=NULL;
scanf("%d",&num);
while(num!=10)
{
LNode *p=(LinkList)malloc(sizeof(LNode));
p->data=num;
p->next=la->next;
la->next=p;
scanf("%d",&num);
}
return la;
}

/*尾插法-建立單鏈表*/
LinkList TailCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode));
la->next=NULL;
LinkList s,r=la;
scanf("%d",&num);
while(num!=10)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=num;
r->next=s;
r=s;
scanf("%d",num);
}
r->next=NULL;
return la;
}

/*單鏈表遍歷*/
void TravelList(LinkList la)
{
LinkList p=la->next;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}

/*單鏈表的按位查找*/
LinkList GetElem(LinkList la,int i)
{
int j=1;
LNode* p=la->next;
if(i<1)
return NULL;
while(p && j<i)
{
p=p->next;
j++;
}
return p;
}

/*單鏈表的按值查找*/
LinkList LocalElem(LinkList la,int e)
{
LNode* p=la->next;
while(p!=NULL && p->data!=e)
p=p->next;
return p;
}

/*單鏈表插入操作*/
bool InsertList(LinkList la,int i,int e)
{
//在la鏈表中的i位置插入數值e
int j=1;
LinkList p=la,s;
while(p && j<i)
{
p=p->next;
j++;
}
if(p==NULL)
return false;
if((s=(LinkList)malloc(sizeof(LNode)))==NULL)
return false;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}

/*單鏈表刪除操作*/
bool DeleteList(LinkList la,int i)
{
int j=1;
LinkList p=la,q;
while(p && j<i) //p指向第i-1個元素
{
p=p->next;
j++;
}
if(p==NULL || p->next==NULL) //表示不存在第i-1個和第i的元素
return false;
q=p->next;
p->next=q->next;
free(q);
return true;
}

/*單鏈表的表長*/
int LengthList(LinkList la)
{
int nLen=0;
LinkList p=la->next;
while(p)
{
p=p->next;
nLen++;
}
return nLen;
}

/*單鏈表逆置*/
LinkList Reserve(LinkList la)
{
if(la==NULL || la->next==NULL)
return la;
LinkList p=la->next,q=p->next,r=q->next;
la->next=NULL;
p->next=NULL;
while(r!=NULL)
{
q->next=p;
p=q;
q=r;
r=r->next;
}
q->next=p;
la->next=q;
return la;
}

int main()
{
LNode la;
LinkList p;
p=HeadCreate(&la); //頭插法創建單鏈表
TravelList(p);
printf("%p\n",GetElem(p,1)); //獲得第1個結點地址
InsertList(p,2,10); //在鏈表的第2個位置插入元素10
TravelList(p);
DeleteList(p,3); //刪除鏈表的第3個元素
TravelList(p);
printf("%d\n",LengthList(p)); //獲得鏈表長度
p=Reserve(p);
TravelList(p);
return 0;
}

//運行結果
//5 6 12 7 8 14 9 3 2 5 14 10 頭插法創建鏈表
//14->5->2->3->9->14->8->7->12->6->5-> 顯示鏈表
//00382490 第一個結點的地址
//14->10->5->2->3->9->14->8->7->12->6->5-> 插入元素值為10的結點
//14->10->2->3->9->14->8->7->12->6->5-> 刪除第三個結點
//11 獲得鏈表長度
//5->6->12->7->8->14->9->3->2->10->14-> 鏈表逆置
//Press any key to continue

這是我寫的一個線性表鏈式存儲的綜合程序，包含了你所要的創建、刪除、插入、按值查找的功能，還有一些額外的功能。下面加註釋的是程序運行結果，你可以參考試著改改程序，讓程序更加完美。希望對你有幫助，呵呵！

⑤ 鏈式存儲結構的線性表中插入、刪除一個元素的時間復雜度 答案是不是O（n）

是,因為插入刪除最多是遍歷整個鏈表，循環n次，所以復雜度為O(n)

⑥ 線性表的基本操作:插入、刪除、查找等運算在鏈式存儲結構上的運算。

萬惡的數據結構 你是幾班的啊～～～我電信071～～～～

⑦ 存儲的數據總數不能確定,並經常需要進行數據的添加和刪除操作,此時應選用哪種存儲結構為什麼

選用鏈式存儲結構
因為在刪除和插入操作時只需移動指針，不需要新的存儲空間，更方便

⑧ 這個題是線性表的鏈式存儲結構中的插入和刪除操作。。。。。求改正。。謝謝 。。。急急急！！！！！

我的編譯結果：test.cpp:38:16: fatal error: C1.H: No such file or directory compilation terminated.你把代碼搞全。有個頭文件沒給出。另外：scanf("%d",&(p->next));這里p的下一個應該是結構體。應該加.date

⑨ 線性表鏈式存儲結構的優點和缺點有什麼

（1）鏈式存儲的優點。
①插入和刪除操作不需要移動大量元素，只需要修改指針即可。
②不需預先分配空間，由系統應需求即時生成。
（2）鏈式存儲的缺點。
①增設指示結點之間關系的指針域，增加了內存負擔。
②不可以隨機存取數據元素。

⑩ 鏈式存儲插入和刪除的時間復雜度

計算機的線性表中有兩種基本的存儲方式： 順序存儲 和 鏈式存儲 。順序存儲指的是用一段地址連續的存儲單元依次存儲數據；而鏈式存儲中數據元素可以散亂的存儲到存儲單元中，每一個數據元素中包含數據項和下一個元素的存儲地址。

通過二者的定義不難看出，順序存儲在查找時的時間復雜度為 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) .