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++
#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=0i<ni++)
scanf("%d",L.elem+i)
L.length=n
return 1
}
/*输出表中元素和长度*/
void Print(SqList &L)
{
int i
for(i=0i<L.lengthi++)
printf("%d ",*(L.elem+i))
printf("\n长度为:%d\n\n",L.length)
}
/*删除值为X的元素*/
status ListDelete1(SqList &L,int x)
{
int i
for(i=0i<L.lengthi++)
if(*(L.elem+i)==x)
break
if(i==L.length)
return 0
for(i++i<L.lengthi++)
*(L.elem+i-1)=*(L.elem+i)
L.length--
return 1
}
/*逆置函数*/
void Inverse(SqList &L)
{
int i,t
for(i=0i<L.length/2i++)
{
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=1i<L.lengthi++)
for(j=0j<L.length-ij++)
{
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=0i<L.lengthi++)
if(x<*(L.elem+i))
break
k=i
for(i=L.lengthi>ki--)
*(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
}
） *** 作步骤。
①判断插入数据元素的位置是否合法，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）。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）