Question

已知顺序表L递增有序，编写一个算法，将X插入到线性表的适当位置上，以保证线性表的有序性。

#include<stdio.h>typedef int ElemType;#define MAXSIZE 100#define OK 1#define ERROR 0//定义线性表typedef struct{ ElemType elem[MAXSIZE]; int last;}SeqList;//创建空表 void Initlist(SeqList *L){ L->last=-1;}//输入递增有序顺序表void putseqList(SeqList *L,int n){ int i; for(i=0;i<n;i++) scanf("%d",&(L->elem[i])); L->last=L->last+n; }//求表长int LenList(SeqList *L){ int Len; Len=L->last+1; return Len;}//判断插入位置int PositionList(SeqList *L,int X){ int j; for(j=0;j<=L->last;j++) if(X<L->elem[j]) //如果找到位置就返回地址，否则知道循环结束再返回最后一个地址 return j+1; //注意这里要加1，下标j表示第j+1个元素，所以返回j+1 return (L->last+1); //这里不能用else，否则就属于for循环里面的了 }//插入元素int InsList(SeqList *L,int i,int e) { int k; if((i<1)||(i>L->last+2)) { printf("插入位置不合理"); return(ERROR); } if(L->last>=MAXSIZE-1) { printf("表已满无法插入"); return(ERROR); } for(k=L->last;k>=i-1;k--) L->elem[k+1]=L->elem[k]; L->elem[i-1]=e; L->last++; return(OK);}//输出元素int OutputSeqList(SeqList *L){ int i; for(i=0;i<=L->last;i++) printf("%d,",L->elem[i]); return(L->elem[i]);}//主程序void main(){ int s,c; SeqList L; Initlist(&L); printf("请输入顺序表长度: "); scanf("%d",&s); printf("请输入递增顺序表: "); putseqList(&L,s); LenList(&L); printf("表长为%d\n",LenList(&L)); printf("请输入要插入的元素: "); scanf("%d",&c); InsList(&L,PositionList(&L,c),c); OutputSeqList(&L); printf("\n"); }

这是程序 我想知道：
解决问题的基本方法说明，包括主要算法思想，算法的流程图，程序中主要函数或过程的功能说明。
http://zhidao.baidu.com/question/325017200.html 程序看不清 原址在这里

Answer 1

基本方法说明：

在一个有序线性表中插入一个元素，使其依然有序，那递增有序线性表来说

for example：

x插入a  b之间时  应满足x<=b&&x>=a；

根据这个原理我们在搜索一个链表适合插入x节的位置时应该至少知道两个值，

即链表的a节的值和b节的值（只有一个节点的链表另当别论。。。。）

那么 就有这样的算法：

已知头结点h

设 同类型节点  p和q

p=h->next;
q=p;
while(p!=NULL)
{
    if(x>=q->data&&x<=p->data)//q->data是数据。。。。x是要插入的数值
    {
        node *t=(node*)malloc(sizeof(node));//新建一个节点t
        t->data=x;
        t->next=q->next;
        q->next=t;
    }
    else
    {
        q=p;
        p=p->next;
    }
}

追问

这是链表吗？？？我想知道顺序表

追答

。。。。看错了  以为 是链表。。。狂汗。。是数组那样的 顺序表吗。。

这样原理相似 不过 需要在插入前判断顺序表是否满，这个 你有函数。。

在插入后将插入元素后的所有元素后移。。。

 int a[500];
int t,x,a,b,i,j,o,tt;
int len;//已有元素数量，你用函数判断吧。。。。
    if(表不满)
    for(i=0;i<max-1;i++)//#define max 表的容量
    {
        if(x>=a[i]&&x<=a[i+1])
        {
            t=x;
            tt=a[i+1];
            for(j=i+1;j<len;j++)//len是此时已有元素数量
            {
                a[j]=t;               
                t=tt;
                tt=a[j+1];
            }
        }
    }
    else
    {
        printf("表满了。。。\n")
    }

这样行么

Answer 2

你代码排版风格和我差不多嘛，很清晰。我调试了一下你的代码，有点小错误，正确代码如下，你自己看后面的注释就知道你错在哪里了
#include
typedef int ElemType;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
//定义线性表
typedef struct
{
ElemType elem[MAXSIZE];
int last;
}SeqList;
//创建空表
void Initlist(SeqList *L)
{
L->last=-1;
}

//输入递增有序顺序表
void putseqList(SeqList *L,int n)
{
int i;
for(i=0;i<n;i++)
scanf("%d",&(L->elem[i]));
L->last=L->last+n;
}
//求表长
int LenList(SeqList *L)
{
int Len;
Len=L->last+1;
return Len;
}
//判断插入位置
int PositionList(SeqList *L,int X)
{
int j;
for(j=0;jlast;j++)
if(Xelem[j]) //如果找到位置就返回地址，否则知道循环结束再返回最后一个地址
return j+1; //注意这里要加1，下标j表示第j+1个元素，所以返回j+1
return (L->last+1); //这里不能用else，否则就属于for循环里面的了

}
//插入元素
int InsList(SeqList *L,int i,int e)
{
int k;
if((iL->last+2))
{
printf("插入位置不合理");
return(ERROR);
}
if(L->last>=MAXSIZE-1)
{
printf("表已满无法插入");
return(ERROR);
}
for(k=L->last;k>=i-1;k--)
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e;
L->last++;
return(OK);
}
//输出元素
int OutputSeqList(SeqList *L)
{
int i;
for(i=0;ilast;i++)
printf("%d,",L->elem[i]);
return(L->elem[i]);
}
//主程序
void main()
{
int s,c;

SeqList L;
Initlist(&L);
printf("请输入顺序表长度: ");
scanf("%d",&s);
printf("请输入递增顺序表: ");
putseqList(&L,s);
LenList(&L);
printf("表长为%d\n",LenList(&L));
printf("请输入要插入的元素: ");
scanf("%d",&c);
InsList(&L,PositionList(&L,c),c);
OutputSeqList(&L);
printf("\n");

}