ITvsET

smiley

2.2顺序表的算法

#include <stdio.h>
#include <iostream>

#define MaxSize 50

typedef int ElemType;

typedef struct
{
    ElemType data[MaxSize];
    int length;
}SqList;

void InitList(SqList& L)
{
    L.length=0;
}

//求指定位置元素值的算法
int GetElem(SqList L,int i,ElemType &e)
{
    if(i<1 || i>L.length)                 //逻辑位序
        return 0;
    e=L.data[i-1];
    return 1;
}

//按元素值查找的算法
int LocateElem(SqList L,ElemType e)
{
    int i=0;
    while(i<L.length && L.data[i]!=e)i++;
    if(i>=L.length)
        return 0;
    else
        return (i+1);
}

//插入数据元素的算法
int ListInsert(SqList &L,int i,ElemType e)
{
    int j;
    if(i<1 || i>L.length+1)             //逻辑位序
        return 0;
    i--;
    for(j=L.length;j>i;j--)
        L.data[j]=L.data[j-1];
    L.data[i]=e;
    L.length++;
    return 1;
}

//删除数据元素的算法
int ListDelete(SqList &L,int i,ElemType &e)
{
    int j;
    if(i<1 || i>L.length)
        return 0;
    i--;
    e=L.data[i];
    for(j=i;j<L.length-1;j++)
        L.data[j]=L.data[j+1];
    L.length--;
    return 1;
}

//有序表的归并算法
void Merge_SortedList(SqList L1,SqList L2,SqList& L3)
{
    int i=0,j=0,k=0;
    while(i<L1.length && j<L2.length)
    {
        if(L1.data[i]<L2.data[j])
        {
            L3.data[k]=L1.data[i];
            i++;k++;
        }
        else if(L1.data[i]>L2.data[j])
        {
            L3.data[k]=L2.data[j];
            j++;k++;
        }
        else
        {
            L3.data[k]=L1.data[i];
            i++;j++;k++;
        }
    }

    while(i<L1.length)
    {
        L3.data[k]=L1.data[i];
        i++;k++;
    }
    while(j<L2.length)
    {
        L3.data[k]=L2.data[j];
        j++;k++;
    }
    L3.length=k;
}

//遍历顺序表
void Traverse(SqList L)
{
    printf("Traversing: ");
    for(int i=0;i<L.length;i++)
    {
        printf("%d ",L.data[i]);
    }
    printf("\n");
}

//2-2-10已知一个递增有序表(incrementing orderly table)
//，现插入x使其仍然递增
void insert_iot(SqList &L,ElemType x)
{
    int i=0,j;
    while(i<L.length && x>=L.data[i])
        i++;
    for(j=L.length-1;j>=i;j--)
        L.data[j+1]=L.data[j];
    L.data[i]=x;
    L.length++;
}

//2-2-11设计一算法，将顺序表的所有元素逆置，要求
//算法复杂度为O(1)
void reverse(SqList &L)
{
    int i;
    ElemType x;
    for(i=0;i<L.length/2;i++)
    {
        x=L.data[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=x;
    }
}

//2-2-12设计一算法，删除所有值的x,
//要求空间复杂度O(1)
void delall(SqList& L,ElemType x)
{
    int i=0,j;
    //找到第一个
    while(i<L.length && L.data[i]!=x)
        i++;
    for(j=i+1;j<L.length;j++)
        if(L.data[j]!=x)
        {
            L.data[i]=L.data[j];
            i++;
        }
    L.length=i;
}

//2-2-12方法二
//算法复杂度为O(n)
void delall2(SqList &L,ElemType x)
{
    int i=0,k=0;
    while(i<L.length)
    {
        if(L.data[i]==x)
            k++;
        else
            L.data[i-k]=L.data[i];
        i++;
    }
    L.length-=k;
}

//2-2-12 自己的方法
//算法不太好，另外将找到的结果先标记，
//再按照交换排序的方法前后交换
void delall_self(SqList &L,ElemType x)
{
    int i=0,j=0;
    while(i<L.length)
    {
        if(L.data[i]==x)
        {
            for(j=i;j<L.length-1;j++)
                L.data[j]=L.data[j+1];
            L.length--;
        }
        else
            i++;
    }
}

//2-2-13设计一算法，从给定的顺序表L中删除元素
//值在x到y(x<=y)的所有元素值，空间复杂度为O(1)
void delallxy(SqList &L,ElemType x,ElemType y)
{
    int i=0,k=0;
    while(i<L.length)
    {
        if(L.data[i]>=x && L.data[i]<=y)
            k++;
        else
            L.data[i-k]=L.data[i];
        i++;
    }
    L.length-=k;
}

//2-2-14有一顺序表L,其元素为整型数据,设计一算法
//将所有小于0的整数放在前半部分，大于等于0的整数
//放在后半部分
void move(SqList &L)
{
    ElemType temp;
    int i=0,j=L.length-1;
    while(i<j)
    {
        while(i<j && L.data[i]<0)
            i++;
        while(i<j && L.data[j]>=0)
            j--;
        if(i<j)
        {
            temp=L.data[i];
            L.data[i]=L.data[j];
            L.data[j]=temp;
        }
    }
}

//2-2-15设计一算法从顺序表中删除重复的元素
//并使剩余的元素间的相对次序保持不变
void delsame(SqList &L)
{
    //j记录合格的元素，
    //i为指示标
    //k辅助变量
    int i,j,k;
    if(L.length>0)
    {
        j=0;
        for(i=1;i<L.length;i++)
        {
            k=0;
            while(k<=j && L.data[k]!=L.data[i])
                k++;
            if(k>j)
            {
                j++;
                L.data[j]=L.data[i];
            }
        }
        L.length=j+1;
    }
}

//2-2-16用顺序表表示集合，(如果有相同元素就不成立)
//设计一算法实现集合的求交集运算
void Intersection(SqList A,SqList B,SqList &C)
{
    int i,j,k=0;
    for(i=0;i<A.length;i++)
    {
        j=0;
        while(j<B.length && B.data[j]!=A.data[i])
            j++;
        if(j<B.length)
            C.data[k++]=A.data[i];
    }
    C.length=k;
}

//2-2-16自己的算法(主要是处理重复元素的情况)
void Intersection_self(SqList A,SqList B,SqList &C)
{
    int i=0,j=0,k=0,m=0;
    for(;i<A.length;i++)
    {
        m=0;
        while(m<i)
        {
            if(A.data[m]==A.data[i])break;
            m++;
        }
        if(m<i)continue;

        j=0;
        while(j<B.length && A.data[i]!=B.data[j])
            j++;
        if(A.data[i]==B.data[j])
        {
            C.data[k++]=A.data[i];
        }
    }
    C.length=k;
}

//2-2-17顺序表表示集合，设计一算法实现
//集合的求并集运算
void Union(SqList A,SqList B,SqList &C)
{
    int i,j,k=0;
    for(i=0;i<A.length;i++)
        C.data[i]=A.data[i];
    C.length=A.length;
    for(i=0;i<B.length;i++)
    {
        j=0;
        while(j<A.length && B.data[i]!=A.data[j])
            j++;
        if(j==A.length)
            C.data[C.length+k++]=B.data[i];
    }
    C.length+=k;
}

//2-2-17自己的算法(处理元素重复的情况)
void Union_self(SqList A,SqList B,SqList &C)
{
    int i=0,k=0;
    ElemType temp;
    for(i=0;i<A.length+B.length-1;i++)
    {
        if(i<A.length)temp=A.data[i];
        else temp=B.data[i-A.length+1];
        for(k=0;k<C.length;k++)
        {
            if(temp==C.data[k])
                break;
        }

        if(k>=C.length)
        {
            C.data[k]=temp;
            C.length++;
        }
    }
}

//2-2-18顺序表表示集合,设计一合适
//的求差集运算
void Difference(SqList A,SqList B,SqList &C)
{
    int i,j,k=0;
    for(i=0;i<A.length;i++)
    {
        j=0;
        while(j<B.length && B.data[j]!=A.data[i])
            j++;
        if(j==B.length)
            C.data[k++]=A.data[i];
    }
    C.length=k;
}

//2-2-18自己的算法
void Difference_self(SqList A,SqList B,SqList &C)
{
    int i=0,j=0,k=0,m=0;
    while(i<A.length)
    {
        j=0;
        while(j<i)
        {
            if(A.data[i]==A.data[j])break;
            j++;
        }
        if(j>=i)
        {
            k=0;
            while(k<B.length && B.data[k]!=A.data[i])
                k++;
            if(k>=B.length)
            {
                C.data[m++]=A.data[i];
            }
        }
        i++;
    }
    C.length=m;
}

//2-2-19已知顺序表A、B,其中元素的个数
//分别为m,n,若表中的数据均是递增的，且
//这(m+n)个数据中没有重复的
//(1)将两表归并，存于新表C中
//时间复杂度为O(m+n)
void merge1(SqList A,SqList B,SqList &C)
{
    int i=0,j=0,k=0;
    while(i<A.length && j<B.length)
    {
        if(A.data[i]<B.data[j])
        {
            C.data[k]=A.data[i];
            i++;k++;
        }
        else
        {
            C.data[k]=B.data[j];
            j++;k++;
        }
    }
    while(i<A.length)
    {
        C.data[k]=A.data[i];
        i++;k++;
    }
    while(j<B.length)
    {
        C.data[k]=B.data[j];
        j++;k++;
    }
    C.length=k;
}

//(2)如果B的大小为(m+n)个单元，是否可不利用顺序表C
//而将合成的线性表存于顺序表B中,设计此算法
//算法时间复杂度为O(m*n)
void merge2(SqList A,SqList &B)
{
    int i=0,j=0,k;
    while(i<A.length)
    {
        if(A.data[i]>B.data[B.length-1])
        {
            B.data[B.length]=A.data[i];
            B.length++;i++;
        }
        else if(A.data[i]<B.data[j])
        {
            for(k=B.length-1;k>=j;k--)
                B.data[k+1]=B.data[k];
            B.data[j]=A.data[i];
            B.length++;
            i++;j++;
        }
        else j++;
    }
}

//(2)self
void merge2_2(SqList A,SqList &B)
{
    int i=0,j=0,k=0;
    while(i<A.length)
    {
        while(j<B.length && A.data[i]>=B.data[j])
            j++;
        if(j<B.length)
        {
            for(k=B.length;k>j;k--)
                B.data[k]=B.data[k-1];
            B.data[j]=A.data[i];
            B.length++;
            j++;
        }
        i++;
    }
}

//(3)设顺序表A有m+n个元素，且前m个有序
//,后n个有序,设计一个算法使整个有序
//时间复杂度为O(m*n)
void merge3(SqList &A,int m,int n)
{
    int i=0,j=m,k;
    ElemType tmp;
    while(j<A.length && i<j)
    {
        if(A.data[j]>A.data[j-1])
            break;
        else if(A.data[j]<A.data[i])
        {
            tmp=A.data[j];
            for(k=j-1;k>=i;k--)
                A.data[k+1]=A.data[k];
            A.data[i]=tmp;
            i++;j++;
        }
        else//找合适的位置插入
            i++;
    }
}

//(3)self 想用交换排序，其实和插入
//排序差不多，有序的情况还是插入排
//较好

int main()
{
    //std::cout<<1+1<<std::endl;
    SqList l,s,total;

    //初始化
    InitList(l);
    InitList(s);
    InitList(total);


    //插入
    ListInsert(l,1,1);
    ListInsert(l,2,1);
    ListInsert(l,3,2);
    ListInsert(l,4,4);

    //2-2-10测试
    //insert_iot(l,3);
    Traverse(l);

    //2-2-11测试
    //reverse(l);
    //printf("After reversing,the result is :\n");
    
    //2-2-12测试
    //delall(l,9);
    //delall2(l,9);
    //delall_self(l,9);
    //printf("After deleting,the result is :\n");

    //2-2-13测试
    //delallxy(l,7,9);
    //printf("After deleting,the result is :\n");

    //2-2-14测试
    //move(l);
    //printf("After moving,the result is :\n");

    //2-2-15测试
    //delsame(l);
    //printf("After deleting same elment,the result is :\n");

    //2-2-16测试
    //2-2-17测试
    //2-2-18测试
    //2-2-19测试
    ListInsert(s,1,2);
    ListInsert(s,2,3);
    ListInsert(s,3,4);

    printf("Traversing s: ");
    Traverse(s);

    //Intersection(l,s,total);
    //Intersection_self(l,s,total);
    //Union(l,s,total);
    //Union_self(l,s,total);
    //Difference(l,s,total);
    //Difference_self(l,s,total);
    //merge1(l,s,total);
    //merge2(l,s);
    merge2_2(l,s);
    //merge3(l,2,2);

    printf("Traversing total: ");
    Traverse(s);

    /*
    //有序表的归并
    ListInsert(s,1,2);
    ListInsert(s,2,6);
    ListInsert(s,3,6);
    ListInsert(s,4,10);

    Merge_SortedList(l,s,total);
    printf("SqList l: ");
    for(int i=0; i<l.length;i++)
        printf("%d ",l.data[i]);
    
    printf("\nSqList s: ");
    for(i=0;i<s.length;i++)
        printf("%d ",s.data[i]);

    printf("\nSqList total: ");
    for(i=0;i<total.length;i++)
        printf("%d ",total.data[i]);

    printf("\n");

    //取元素
    int get,e;
    get=GetElem(l,1,e);
    if(get)
        printf("get first elment: %d\n",e);
    else
        printf("Error Get!");

    //删除元素
    int del;
    del=ListDelete(l,2,e);
    if(del)
        printf("delete second elment: %d\n",e);
    else
        printf("Error Delete!");

    //查找元素
    int loc;
    loc=LocateElem(l,4);
    if(loc)
        printf("elment 4 locates at :%d\n",loc);
    else
        printf("Can't Find!\n");
    */

    return 0;
}

posted on 2011-04-22 20:34 天一程 阅读(547) 评论(0)  编辑 收藏 引用 所属分类: 数据结构算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理