顺序表插入算法

① 设有一个顺序表,写出在值为x的元素后插入m个元素的算法。

struct list *p, *q, *s, *head;
p = head;
while(p != NULL)
{
if(x > p->data)
{
q = p;
p = p->next;
}
else
{
s = (struct list*)malloc(sizeof(struct list));
s->data = x;
q->next = s;
s->next = p;
}
}

② 顺序表中元素插入算法详细解释

//将顺序表第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++;

③ 为什么顺序表的插入算法的平均移动次数约为n/2其比较和移动的次数为n-i+1（i=1,2,...,n+1）

在一个已有n个数据的顺序表中插入一个数据时，最好的情况是移动0个数据，最坏的情况是移动n个数据，而“好坏”程序则是随机的。所以其平均移动次数为（0+n）/2=n/2次。

④ 新手求助顺序表插入算法，为什么数据插不进去

1. 问题在于这行：
int Insert(Sqlist L,int a,Elemtype b) //插入数据
这里 L传的是值，而不是引用，改变L并不会改变调用函数（这里是main函数）中的L。
应改为：
int Insert(Sqlist &L,int a,Elemtype b) //插入数据

2. 建议输入放在main函数中，Insert函数单纯进行操作。
Insert函数的返回值可用来判断出错。
if (Insert(L,i,x) == 1)
Output(L);

⑤ 在顺序表L中插入数据元素e的步骤是什么

）操作步骤。

①判断插入数据元素的位置是否合法，i的合法值为1≤i≤L.Length＋1②若当前存储空间已满，增加分量，即L.length≥L.listsize表示存储空间已满③将顺序表L中的第n个至第i个数据元素依次后移一个位置。

④将数据元素e插入到第i个位置之前。

⑤顺序表长度增1。

（2）在顺序表L中第i个位置之前插入数据元素e的算法。（4）顺序表插入算法的时间复杂度分析。

假设线性表中含有n个数据元素，在进行插入操作时，算法2.2的时间主要花费在for循环语句中的数据元素后移语句上，该语句的执行次数（即移动元素的次数）是n－i＋1。由此可看出，所需移动的数据元素次数不仅依赖于表的长度n，而且还与插入位置i有关。当i＝n＋1时，元素后移语句将不执行，这是最好的情况，其时间复杂度为O（1）；当i＝1时，元素后移语句将循环执行n次，需移动表中所有元素，这是最坏的情况，其时间复杂度为O（n）。

⑥ 顺序表的插入算法的实现

#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int status ;
typedef int ElemType ;

typedef struct{
ElemType *elem;
int length,listsize;
}SqList;

status InitList(SqList &L)//初始化
{
L.elem=(int *)malloc(100*sizeof(int));
if(!L.elem) exit(-2);
L.listsize=100;
L.length=0;
return 1;
}

/*先建立新表*/
status Build(SqList &L)
{
int i,n;
printf("请输入元素个数n和n个元素\n");
scanf("%d",&n);
//if(n>LIST_INIT_SIZE)

for(i=0;i<n;i++)
scanf("%d",L.elem+i);
L.length=n;
return 1;
}
/*输出表中元素和长度*/
void Print(SqList &L)
{
int i;
for(i=0;i<L.length;i++)
printf("%d ",*(L.elem+i));
printf("\n长度为:%d\n\n",L.length);
}
/*删除值为X的元素*/
status ListDelete1(SqList &L,int x)
{
int i;
for(i=0;i<L.length;i++)
if(*(L.elem+i)==x)
break;
if(i==L.length)
return 0;
for(i++;i<L.length;i++)
*(L.elem+i-1)=*(L.elem+i);
L.length--;
return 1;
}

/*逆置函数*/
void Inverse(SqList &L)
{
int i,t;
for(i=0;i<L.length/2;i++)
{
t=*(L.elem+i);
*(L.elem+i)=*(L.elem+L.length-i-1);
*(L.elem+L.length-i-1)=t;
}
printf("表逆置成功!!!\n");
}

/*（升序）*/
void Sort(SqList &L)
{
int i,j,t;
for(i=1;i<L.length;i++)
for(j=0;j<L.length-i;j++)
{
if(*(L.elem+j)>*(L.elem+j+1))
{
t=*(L.elem+j);
*(L.elem+j)=*(L.elem+j+1);
*(L.elem+j+1)=t;
}
}
printf("已升序\n");

}

/*合并两个线性表*/
status Merger(SqList &L,SqList &Lb)
{
int i,j,k;
SqList Lc;
InitList(Lc);
if(Lc.listsize<L.length+Lb.length)
{
Lc.elem=(ElemType *)realloc(Lc.elem,(L.length+Lb.length+LISTINCREMENT)*sizeof(ElemType));
if(!L.elem) exit(-2);
Lc.listsize=L.length+Lb.length+LISTINCREMENT;
}
i=j=k=0;
while(i<L.length && j<Lb.length)
{
if(*(L.elem+i) < *(Lb.elem+j))
{
*(Lc.elem+k)=*(L.elem+i);
k++;i++;
}
else
{
*(Lc.elem+k)=*(Lb.elem+j);
k++;j++;
}
}
while(i<L.length)
{
*(Lc.elem+k)=*(L.elem+i);
k++;i++;
}
while(j<Lb.length)
{
*(Lc.elem+k)=*(Lb.elem+j);
k++;j++;
}
Lc.length=L.length+Lb.length;
L=Lc;
return 1;
}

/*将X插入，使仍然有序*/
status ListInsert(SqList &L,int x)
{
int i,k;
if(L.length>=L.listsize)
{
L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!L.elem) exit(-2);
L.listsize+=LISTINCREMENT;
}
for(i=0;i<L.length;i++)
if(x<*(L.elem+i))
break;
k=i;
for(i=L.length;i>k;i--)
*(L.elem+i)=*(L.elem+i-1);
*(L.elem+k)=x;
L.length++;
return 1;
}

/*提示函数*/
void Tips()
{
printf("请选择你的想要的操作：\n");
printf("<1> 输出顺序表及顺序表的长度\n");

printf("<2> 删除值为x的结点\n");

printf("<3> 将顺序表逆置\n");
printf("<4> 将顺序表按升序排序\n");
printf("<5> 将x插入到顺序表的适当位置上\n");
printf("<6> 将两个有序表合并\n");
printf("<0> 退出\n\n");
}

int main()
{

SqList L,Lb;
InitList(L);
Build(L);
int a,x,flag;
//SqList L,Lb;
Tips();
scanf("%d",&a);
while(a)
{
switch(a)
{

case 1:
{ Print(L);
break;}
case 2:
{ printf("请输入要删除的数据X:\n");
scanf("%d",&x);
flag=ListDelete1(L,x);
if(flag)
printf("删除成功!!\n\n");
else
printf("元素不存在,删除失败!!\n\n");
break;}

case 3:
Inverse(L);
break;
case 4:
Sort(L);
break;
case 5:
printf("请输入要插入的数据X:\n");
scanf("%d",&x);
flag=ListInsert(L,x);

if(flag)
printf("插入成功!!\n\n");
else
printf("插入失败!!\n\n");
break;

case 6:
printf("请输入Lb的内容:\n");
InitList(Lb);
Build(Lb);
flag=Merger(L,Lb);
if(flag)
printf("合并成功!!\n\n");
break;
//default;

Tips();
scanf("%d",&a);

}
}
return 0;
}

⑦ 关于顺序表插入的c程序只要算法

Node *Insert(Node *Head){ int x; Node *p=Head->next,*q,*temp; scanf("%d",&x); temp=(Node *)malloc(Node); temp->n=x; //申请内存我忘记是不是这么写了…… //VC++6.0支持temp=new Node; while(p!=NULL) { q=p->next; if(q==NULL)//表尾插入 { p->next=temp; temp->next=NULL; break; } else if(q->n>x)//升序,降序 就 < { p->next=temp; temp->next=q; break; } p=p->next; } if(Head->next==NULL)//空链表 { Head->next=temp; temp->next=NULL; } return Head;}

⑧ 用java写个顺序表插入算法的实现

int insert( struct student *head, int i )
{
struct student *p，*q;
q = locate( head, i );
/*调用链表定位函数，获取序号i结点的指针*/
if(q == NULL) return 0;
/*找不到序号i对应的位置，返回0，表示插入失败*/
p=(struct student*) malloc(sizeof(struct student));
/*申请新结点*/
printf ( "Input No：" );
scanf ( "%d", &p-> no );
printf ( "Input Name：" );
scanf ( "%s", p-> name );
p-> next = q-> next; /*新结点的next指针的处理*/
q-> next = p; /*定位结点的next指针处理*/
return 1; /*返回1，表示插入成功*/

int delete ( struct student *head，int i )
{
struct student *p, *q;
/*调用链表定位函数，获取序号i结点的指针*/
q = locate ( head, i– 1 );
if ( q == NULL ) return 0;
/*找不到序号i－1对应的位置，返回0，表示删除失败*/
/*找序号i对应的位置*/
p = q -> next;
if(p == NULL) return 0;
/*找不到序号i对应的位置，返回0，表示删除失败*/
q-> next = p-> next;
free(p); /*释放结点内存*/
return 1; /*返回1，表示删除成功*/

⑨ 数据结构 顺序表中插入和删除元素的算法、顺序栈中入栈和出栈的算法

//顺序表的插入
void Insert(int i, int item)
{
if (length >= MaxSize)
{
cerr << "上溢";
exit(1);
}
if (i<1 || i>length + 1)
{
cerr << "插入位置非法";
exit(1);
}
for (int j = length; j >= i - 1; j--)
data[j + 1] = data[j];
data[i - 1] = item;
length++;
}
//顺序表的删除
int Delete(int i)
{
if (length == 0)
{
cerr << "下溢";
exit(1);
}
if (i<1 || i>length)
{
cerr << "删除位置非法";
exit(1);
}
int x = data[i - 1];
for (int j = i; j < length; j++)
data[j - 1] = data[j];
length--;
return x;
}
//入栈操作
void Push(T x)
{
if (top == MaxSize - 1)
{
cerr << "上溢";
exit(1);
}
top++;
data[top] = x;
}
//出栈操作
int Pop()
{
if (top == -1)
{
cerr << "下溢";
exit(1);
}
int x = data[top--];
return x;
}

⑩ 【C语言·数据结构】关于线性表里的顺序表的插入算法

你这里的线性表是特指链表吧？要不然是不会需要把长度加1的。

链表理论上是没有长度限制的(但实际上你不能无限地增长它，因为计算机的内存是有限的)

在插入一个元素后再把长度加1是没有任何问题的，反而这是一个较为妥当的做法，因为如果你一开始就把长度加一，但元素插入失败的话，那就会出现问题。

另外，你要明确一个观点，“后移元素”并不是真的把它在内存中的位置后移了，只是把它挂在了当前插入的这个结点后面，对任何的其他元素的地址都不会有影响的。

表长其实是一个方便你管理链表的东西，它可以记录当前链表的长度，让你较为容易地判断链表是否为空，也可以让你限定链表的长度（通过设置一个max值，当length达到max时，不准再插入元素）