C语言数据结构的插入问题

设长度为Max的顺序表L中包含n个整数且递增有序。写一算法，将x插入到顺序表的适当位置上，以保持表的有序性，并分析算法的时间复杂度。（急求解答，拜托众位了）

答案：#include "a.h"                             //预处理命令所包含的文件
int ListInsert_sq(SqList &L,int i,/*ElemType*/int 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){             //当前存储空间已满，增加分配
       SqList  newbase;
    newbase.elem=(/*ElemType*/ int *)realloc(L.elem,
               (L.listsize+LISTINCREMENT)*sizeof(/*ElemType*/int));
    if(!newbase.elem) exit(OVERFLOW);       //存储分配失败
 L.elem=newbase.elem;                   //新基址
 L.listsize+=LISTINCREMENT;        //增加存储容量
 }
 int *q=NULL,*p=NULL;
 q=&(L.elem[i-1]);                 //q为插入的位置
 for(p=&(L.elem[L.length-1]); p>=q;--p)
  *(p+1)=*p;                    //插入位置及之后的元素右移
 *q=e;                             //插入e
 ++L.length;                       //表长增1
 return  OK;
}//ListInser_sq
按你的描述：
直接插入排序：将一个记录插入到一个已排好序的有序表中。
void InsertSort(int *L,int n,int x) 
{
   int count=0,replace;
   if(L[n-1]<x) {L[n]=x; break;}//插入x至末尾
  for(;count<n;count++)
   { 
   if(L[count]<x && L[count+1]>=x)
    {
        replace =count +1;//插入x
        break;
    }
   }
//从replace至n-1移动到replace+1~n;并插入x到replace
  for(count =n -1;count >=replace;count --)
      L[count+1]=L[count];
  L[replace]=x;
 }
算法的时间复杂度：应该为n
程序没有调试,请自己调试是否正确。
 

上一个：c语言学生管理系统程序解释
下一个：为什么用c语言画图总蓝屏？