順序表插入演算法

① 設有一個順序表,寫出在值為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時，不準再插入元素）