链式存储结构中的增添与删除

① 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高对吗

对
因为顺序结构需要整体移动
(比如要在数组中插入一个元素不是在
最后，那么插入点后的所有元素都要
向后移，而被删除元素后所有元素都要
向前移）
而链式结构只需改写指针
就可以了

② 建立一个链式存储的线性表，并实现线性表的插入和删除操作。

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) .