顺序表的应用

雨点打透心脏的1/2处 2022-07-16 13:29 72阅读 0赞

2016年7月13日12:03:58
        编程需求:编写一个算法,把一个顺序表拆分成两部分,使顺序表中小于0的元素位于左边,
        大于0的元素位于右边,例如(-12,3,-6,-10,20,-7,9,-20)顺序表,经过分拆后
        变成(-12,-20,-6,-10,-7,20,9,3);
        1.使用顺序表来存贮这些数据,首先建立一个空的顺序表;
        2.将保存在数组中的数据保存到顺序表中,即创建顺序表;
        3.将创建好的顺序表遍历输出,
        4.将顺序表进行分拆,
        5.将创建好的顺序表遍历输出;

#include<stdio.h>
    #include<stdlib.h>
    #define listSize 100
    typedef int DataType;
    
    //顺序表的结构体类型
    typedef  struct
    {
        DataType list[listSize];
        int length;
    }LIST;
    
    //函数前置声明
    void  initList(LIST * L);
    void  createList(LIST * L,LIST * pArr,int len);
    void  traverseList(LIST * L);
    int   insertList(LIST * L,int pos,DataType e);
    void  splitList(LIST * L);
    void  swap(DataType * p,DataType * q);
    
    //初始化顺序表
    void  initList(LIST * L)
    {
        L->length = 0;
    }
    
    //向顺序表中插入元素
    int insertList(LIST * L, int pos, DataType e)
    {
        int i;
        if(L->length==listSize)//首先检查顺序表是否为满,若满则返回-1;
        {
            printf("顺序表已满,不能插入元素!\n");
            return -1;
        }
        else if(pos<1||pos>L->length+1)//其次检查插入元素的位置是否正确,若非法,则返回0;
        {
            printf("插入元素的位置不合适!");
            return 0;
        }
        else//在合法的前提下,将下标为pos-1及其以后的元素都向后移动,使得pos-1处被"空"出来,最后插入元素至空处;
        {
            for(i = L->length;i>=pos;i--)
            {
                L->list[i] = L->list[i-1];
            }
            L->list[pos-1] = e;
            L->length++;
            return 1;
        }
    
    }
    
    //创建顺序表
    void  createList(LIST * L,DataType * pArr,int len)
    {
        int i;
        for(i = 0; i<len ;i++)
        {
            if(0==insertList(L,i+1,pArr[i]))
            {
                printf("插入元素的位置不合适!\n");
            }
        }
        return ;
    }
    
    //交换两个整数
    void  swap(DataType * p,DataType * q)
    {
        DataType temp;
        temp = *q;
        *q = *p;
        *p = temp;
        return ;
    }
    
    //将顺序表分拆成两部分:前一部分<=0,后一部分＞0
    void splitList(LIST * L)
    {
        int i,j;
        i = 0;
        j = L->length-1;
        while(i<j)
        {
            while(L->list[i]<=0)
            {
                i++;
            }
            while(L->list[j]>0)
            {
                j--;
            }
            if(i<j)
            {
                swap(&L->list[i],&L->list[j]);
            }
        }
        return ;
    }
    
    //遍历顺序表
    void  traverseList(LIST * L)
    {
        int i;
        for( i = 0;i<L->length;i++)
        {
            printf("%d ",L->list[i]);
        }
        printf("\n");
        return ;
    }
    
    //主函数
    int main(void)
    {
        int a[] = {-12,3,-6,-10,20,-7,9,-20};
        LIST L;
        initList(&L);
        createList(&L,a,sizeof(a)/sizeof(a[0]));
        printf("顺序表L中的元素为:\n");
        traverseList(&L);
        splitList(&L);
        printf("分拆后顺序表L中的元素为:\n");
        traverseList(&L);
        return 0;
    }