ds.cpp

数据结构顺序表插入保持递增有序

#include <stdio.h>
#include <stdlib.h>

#define  OK 1
#define  ERROR  0
#define  LIST_INIT_SIZE 100
typedef int ElemType,Status;
typedef struct
{
    ElemType  *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList &L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)) ;
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}


int LocateElem_Sq(SqList L, ElemType e)     //寻找插入位置，使顺序表保持非递减有序
{
/* 在顺序线性表L中查找第1个值与e相等的元素的位序。若找到，则返回其在L中的位序，否则返回0。*/
     int i = 1;                 // i负责计数
     int *p = L.elem;     // 指针p从顺序表基地址开始,红箭头表示
     while (i <= L.length &&*p++ < e)
             ++i;
    return i;

}

Status ListInsert_L(SqList &L,int pos, ElemType e)
{
    ElemType *q,*p;
   if (pos<1||pos>L.length+1)  return ERROR;
   if (L.length >= L.listsize) return ERROR;

    q =&(L.elem[pos-1]);
    for (p=&(L.elem[L.length-1]); p>=q; p--)
       *(p+1) = *p;
   *q = e;
   L.length++;

  return OK;

}

void DispList_L(SqList L)
{
    int i=1;
    while(i<=L.length)
    {
      printf("%5d",L.elem[i-1]);
      i++;
    }
}

main()
{
    int e,pos,n=1;
    SqList L;
    InitList_Sq(L);
    /*判断输入值
    非负数时：根据输入的值利用LocateElem_Sq()得到插入位置之后用ListInsert_L()插入
    负数时：结束输入
    */
     while(1)
     {
        printf("请输入第%d个非负整数:   ",n++);
        scanf("%d",&e);
        if(e<0)
            break;
        else
        {
            pos=LocateElem_Sq(L,e);
           ListInsert_L(L,pos,e);
        }
     }
    printf("链表中各结点的值:\n");
    DispList_L(L);
    printf("\n");
}