C语言_顺序表的排序问题

C语言_顺序表的排序问题

21视频教程网C语言编辑部3月21日整理

学生：

“输入整型元素序列利用有序表插入算法建立一个有序表”怎样写啊？

C语言编辑部：

#include "stdio.h"
#include "process.h"   //包含exit()函数需要
#include "malloc.h"    //包含malloc(),realloc()函数

/*函数结果状态代码*/
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

typedef int Status; //Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int Boolean; //Boolean是布尔类型，其值是TRUE或FALSE

/*--------线性表的动态分配顺序存储结构--------*/
#define LIST_INIT_SIZE 10
#define LIST_INCREMENT 2
typedef int ElemType;
struct SqList
{
ElemType *elem; /*存储空间基址*/
int length;     /*当前长度*/
int listsize; /*当前分配的存储容量*/
};

//顺序表初始化
void InitList(SqList &L)
{
   L.elem=new ElemType[LIST_INIT_SIZE];
   if(!L.elem)
    exit(OVERFLOW);/*存储分配失败*/
   L.length=0; /*空表长度为0*/
   L.listsize=LIST_INIT_SIZE; /*初始存储容量*/
}

//插入数据
Status ListInsert(SqList &L,int i,ElemType e)
{
ElemType *newbase,*q,*p;
if (i<1||i>L.length+1) //i值不合法
   return ERROR;
if(L.length>=L.listsize) //当存储空间已满，增加分配
{
   if(!(newbase=(int*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(int)))) //??? realloc()
    exit(OVERFLOW);   //存储分配失败
   L.elem=newbase;      //新基址
   L.listsize+=LIST_INCREMENT; //增加存储容量
}
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;
}

//判断线性表是否为空
Status ListEmpty(SqList L)
{//初始条件：顺序表L已存在。操作结果：若L为空表，返回TRUE，否则返回FALSE
if(L.length==0)
   return TRUE;
else
   return FALSE;
}

//清空顺序表
void ClearList(SqList &L)
{//初始条件：顺序线性表已存在。操作结果：将L重置为空表
L.length=0;
}

//求顺序表中元素个数
int ListLength(SqList L)
{//初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数
   return L.length;
}

//求顺序表中第i个元素的值
Status GetElem(SqList L,int i,ElemType &e)
{//初始条件：顺序表L已存在，1<=i<=ListLength(L)。操作结果：用e返回L中的第i个元素的值
   if(i<1||i>L.length)
    return ERROR;
   e=*(L.elem+i-1);
   return OK;   
}

int LocateElem(SqList L,ElemType e,Status (*compare)(ElemType,ElemType))
{//初始条件：顺序线性表L已存在，compare()是数据元素判定元素（满足为1，否则为0）
//操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。
//若这样的元素不存在，则返回值为0。
   ElemType *p;
   int i=1; //i的初始值为第一个元素的位序
   p=L.elem;//p的值为第一个元素的存储位置
   while(i<=L.length&&!compare(*p++,e))
    ++i;
   if (i<=L.length)
    return i;
   else
    return 0;
}

Status equal(ElemType c1,ElemType c2)
{//判断是否相等
   if(c1==c2)
    return TRUE;
   else
    return FALSE;
}

Status sq(ElemType c1,ElemType c2)
{
   if(c1==c2*c2)
    return TRUE;
   else
    return FALSE;
}

//求前驱元素
Status PriorElem (SqList L,ElemType cur_e,ElemType &pre_e)
{
   //初始条件：顺序线性表L已存在
   //早错结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
   //否则操作失败，pre_e无定义
   int i=2;
   ElemType *p=L.elem+1;
   while(i<=L.length&&*p!=cur_e)
   {
    p++;
    i++;
   }
   if(i>L.length)
    return INFEASIBLE;
   else
   {
    pre_e=*--p;
    return OK;
   }
}

//求后继元素
Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{//初始条件：顺序线性表L已存在
//操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
   //否则返回失败，next_e定义无效
   int i=1;
   ElemType *p=L.elem;
   while(i<L.length&&*p!=cur_e)
   {
    i++;
    p++;
   }
   if(i==L.length)
    return INFEASIBLE;
   else
   {
    next_e=*++p;
    return OK;
   }
}
Status ListDelete(SqList &L,int i,ElemType &e)
{//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
   ElemType *p,*q;
   if(i<1||i>L.length) //i值不合法
    return ERROR;
   p=L.elem+i-1; //p为被删除元素的位置
   e=*p;// 被删除元素的值赋给e
   q=L.elem+L.length-1; //表尾元素位置
   for(++p;p<=q;++p) //被删除元素之后的元素左移
    *(p-1)=*p;
   L.length--; //表长减1
   return OK;
}

void ListTraverse(SqList L,void(*vi)(ElemType&))
{//初始条件：顺序线性表L已存在
   //操作结果：依次对L的每个数据调用函数vi()
   //vi的形参加‘&’，表明可通过调用vi()改变元素的值
   ElemType *p;
   int i;
   p=L.elem;
   for(i=1;i<=L.length;i++)
    vi(*p++);
   printf("\n");
}

void print1(ElemType &c)
{
   printf("%d",c);
}
void db1(ElemType &c)
{//ListTraverse()调用的另一函数(元素值加倍)
   c*=2;
}

void DestroyList(SqList &L)
{//初始条件：顺序线性表L已存在。操作结果：销毁线性顺序表L
   delete[]L.elem;
   L.elem=NULL;
   L.length=0;
   L.listsize=0;
}

//主函数
void main()
{
   Status i;
   int e,e0;
         int j,k;
   //顺序表初始化
   SqList L;
   InitList(L);
   printf("初始化L后：L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize);

   for (j=1;j<=5;j++)
    //在表头插入数据
    i=ListInsert(L,1,j);
   printf("在L的表头依次插入1~5后：*L.elem=");
   for(j=1;j<=5;j++)
    printf("%d",*(L.elem+j-1));
   printf("\n");
   printf("L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize);
  
   //判断顺序表是否为空
   i=ListEmpty(L);
   printf("L是否为空：i=%d（1：是 0：否）\n",i);
   //清空顺序表
   ClearList(L);
   printf("清空L后：L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize);
   //查看是否清空顺序表
   i=ListEmpty(L);
   printf("L是否为空：i=%d（1：是 0：否）\n",i);

   for (j=1;j<=10;j++)
    //在表尾插入数据
    i=ListInsert(L,j,j);
   printf("在L的表尾依次插入1~10后：*L.elem=");
   for(j=1;j<=10;j++)
    printf("%d",*(L.elem+j-1));
   printf("\n");
   printf("L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize);
   ListInsert(L,1,0);
   printf("在L的表头插入0后：*L.elem=");
    for(j=1;j<=ListLength(L);j++) //ListLength(L)为元素个数
     printf("%d",*(L.elem+j-1));
   printf("\n");
   printf("L.elem=%u(有可能改变) L.length=%d(改变) L.listsize=%d(改变) \n",L.elem,L.length,L.listsize);

   GetElem(L,5,e);
   printf("第5个元素的值为： %d \n",e);

   for(j=10;j<=11;j++)
   {
    k=LocateElem(L,j,equal);
    if(k) //k不为0，表明有符合条件的元素，且其位序为k
     printf("第%d个元素的值为%d \n",k,j);
    else
     printf("没有值为%d的元素 \n",j);
   }
   for(j=3;j<=4;j++)
   {
    k=LocateElem(L,j,sq);
    if(k)
     printf("第%d个元素的值为%d的平方 \n",k,j);
    else
     printf("没有值为%d的平方的元素 \n",j);
   }
   for(j=1;j<=2;j++)
   {//测试头两个数据
    GetElem(L,j,e0); //把第j个数据赋给e0
    i=PriorElem(L,e0,e); //求e0的前驱
    if(i==INFEASIBLE)
     printf("元素%d无前驱元素 \n",e0);
    else
     printf("元素%d的前驱为：%d \n",e0,e);
   }
   for(j=ListLength(L)-1;j<=ListLength(L);j++)
   {//测试最后两个数据
    GetElem(L,j,e0); //把第j个数据赋给e0
    i=NextElem(L,e0,e); //求e0的后继
    if(i==INFEASIBLE)
     printf("元素%d无后继 \n",e0);
    else
     printf("元素%d的后继为：%d \n",e0,e);
   }
   k=ListLength(L); //k为表长
   for(j=k+1;j>=k;j--)
   {
    i=ListDelete(L,j,e); //删除第j个数据
    if(i==ERROR)
     printf("删除第%d个元素失败\n",j,e);
    else
     printf("删除第%d个元素成功,其值为：%d \n",j,e);
   }
   printf("依次输出L的元素：");
   ListTraverse(L,print1); //依次对元素调用print1()，输出元素的值
   printf("L的元素值加倍后：");
   ListTraverse(L,db1); //依次对元素调用db1(),元素值乘2
   ListTraverse(L,print1);
   DestroyList(L);
   printf("销毁L后：L.elem=%u L.length=%d L.listsize=%d",L.elem,L.length,L.listsize);
}
天下程序一大抄！ 还好曾经保存过

学生：

“那输入整型元素序列利用有序表插入算法建立一个有序表”       这个具体怎么写啊？

C语言编辑部：

#include<stdio.h>
#define MAXLEN 100       /*此处的宏定义常量表示线性表可能达到的最大长度*/
typedef int elementtype;      /*根据需要，elementtype也可以定义为其它任何类型*/
typedef struct               /*定义线性表*/
{
    elementtype s[MAXLEN];  /*定义线性表中元素，MAXLEN为线性表的最大容量*/
    int len;                  /*定义线性表的表长*/
}SqList;

int insertsqlist(SqList *sql,elementtype x)
{
    int j;
   
    if(sql->len>=MAXLEN-1)
    {
        printf("表已满无法插入");
        return(0);
    }
    for(j=sql->len;sql->s[j]>x;j--)
      sql->s[j+1]=sql->s[j];   /*向后移动数据，腾出要插入的空位*/
    sql->s[j+1]=x;             /*修正插入位置为j+1，将新元素插入到s[j+1]位置*/
    (sql->len)++;              /*表长加1*/
    return(1);                 /*插入成功，返回值为1*/
}

void main()
{
    SqList seq;
    int p,q,r;
    int i;
    printf("请输入线性表的长度:");
    scanf("%d",&r);
    seq.len =r;
    printf("请输入线性表的各元素值:\n");
    for(i=1; i<=seq.len; i++)
     /*赋线性表各元素初值，为与前概念描述一致，seq.s[0]闲置不用*/
    {
        scanf("%d",&seq.s[i]);
    }
   
    printf("请输入要插入的元素值:");
    scanf("%d",&q);   
    insertsqlist(&seq,q);
    printf("插入元素后的线性表:\n");
    for(i=1; i<=seq.len; i++)
    {
        printf("%d  ",seq.s[i]);
    }
}

学生：

谢谢！

C语言编辑部结