数据结构线性表算法的实现

98 阅读 0 评论 65 点赞

我是靠谱客的博主冷傲糖豆，最近开发中收集的这篇文章主要介绍数据结构线性表算法的实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实现了严蔚敏的那本数据结构书里线性表的有关算法，首先发给了我们宿舍C语言曾经挂了的那位妹子^_^ 很有成就感，明天再给其他室友都发过去，用她们的话说——我们宿舍专业课全靠我了。。。

#include<stdio.h>
#include<malloc.h>
/*线性表的动态分配顺序存储结构*/
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10//线性表存储空间的分配增量
typedef struct
{
    int *elem;//存储空间基址
    int length;//线性表的当前长度
    int listsize;//当前分配的存储容量（以sizeof(ElemType)为单位）
} SqList;
//算法2.3
//构造一个空的线性表L **********23
void InitList_Sq(SqList *L)
{
    L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
    //Malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。
    //void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针。
    if(!L->elem)
        exit(-1);//存储分配失败
    L->length=0;//空表长度为0
    L->listsize=LIST_INIT_SIZE;//初始存储容量
    printf("okn");
}
//为线性表赋值
void ListInput(SqList *L)
{
    int i;
    printf("请输入十个数，空格间隔n");
    for(i=0; i<10; i++)
    {
        scanf("%d",&L->elem[i]);
        (L->length)++;
        if(L->length>L->listsize)
        {
            int *newbase;
            newbase=(int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));
            if(!newbase)
                exit(-1);
            L->elem=newbase;
            L->listsize+=LISTINCREMENT;
        }
    }
}
//算法2.4
//在顺序线性表L中第i个位置之前插入新的数据元素e *************24
void ListInsert_Sq(SqList *L,int i,int e)
{
    int *newbase,*q,*p;
    if(i<1||i>L->length+1)
        exit(-1);
    if(L->length>=L->listsize)//当前存储空间已满，增加分配
    {
        newbase=(int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));
        //指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）
        //realloc先判断当前的指针是否有足够的连续空间，如果有，扩大指向的地址，并且其返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来所指内存区域，同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
        if(!newbase)
            exit(-1);
        L->elem=newbase;
        L->listsize+=LISTINCREMENT;
    }
    q=&(L->elem[i-1]);//q为插入位置
    for(p=&(L->elem[L->length-1]); p>=q; --p)//p为线性表表尾
        *(p+1)=*p;//元素右移
    *q=e;//插入e
    ++L->length;//表长加1
    printf("插入元素成功（在第2个位置插入3）n");
    for(i=0; i<=L->length-1; i++)
    {
        printf("%d ",L->elem[i]);
    }
    printf("n");
}
//算法2.5
//在顺序线性表L中删除第i个元素，并用e返回其值
void ListDelete_Sq(SqList *L,int i,int *e)
{
    int *p,*q;
    if((i<1)||(i>L->length))
        exit(-1);
    p=&(L->elem[i-1]);//p为被删除元素的位置
    *e=*p;
    q=L->elem+L->length-1;//q为表尾位置
    for(++p;p<=q;++p)
    {
        *(p-1)=*p;
    }
    --L->length;
    printf("删除成功（删除了第5个）n");
    for(i=0; i<=L->length-1; i++)
    {
        printf("%d ",L->elem[i]);
    }
    printf("n");
}
//算法2.6
//在顺序线性表L中查找第1个与e满足compare()的元素的位序。若找到，返回位序，否则返回0
int LocateElem_Sq(SqList L,int e,int (*compare)(int,int))//compare()是数据元素判定函数(满足为1,否则为0)
{
    int i=1,*p;
    p=L.elem;//的初值为第1个元素的存储位置
    while(i<=L.length&&!compare(*p++,e))
    {
        ++i;
    }
    if(i<=L.length)
        return i;
    else
        return 0;
}
int compare(int a,int b)
{
    if(a==b)
        return 1;
    else
        return 0;
}
//算法2.7
//已知顺序线性表La和Lb的元素按值非递减排序，归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排序
void MergeList_Sq(SqList La,SqList Lb,SqList *Lc)
{
    int *pa,*pb,*pc,*pa_last,*pb_last,i;
    pa=La.elem;
    pb=Lb.elem;
    Lc->listsize=Lc->length=La.length+Lb.length;
    pc=Lc->elem=(int*)malloc(Lc->listsize*sizeof(int));
    if(!Lc->elem)
        exit(-1);
    pa_last=La.elem+La.length-1;
    pb_last=Lb.elem+Lb.length-1;
    while(pa<=pa_last&&pb<=pb_last)
    {
        if(*pa<=*pb)
        {
            *pc++=*pa++;//这样就能实现指针后移了……
        }
        else
        {
            *pc++=*pb++;
        }
    }
    while(pa<=pa_last)
        *pc++=*pa++;
    while(pb<=pb_last)
        *pc++=*pb++;
    for(i=0; i<=Lc->length-1; i++)
    {
        printf("%d ",Lc->elem[i]);
    }
    printf("n");
}

int main()
{
    SqList La,Lb,Lc;
    int *e,a,i;
    InitList_Sq(&La);
    ListInput(&La);
    ListInsert_Sq(&La,2,3);
    ListDelete_Sq(&La,4,&e);
    printf("删除的数为：%dn",e);
    a=LocateElem_Sq(La,5,compare);
    printf("%dn",a);
    InitList_Sq(&Lb);
    ListInput(&Lb);
    MergeList_Sq(La,Lb,&Lc);

return 0;
}