C语言实现顺序表-数据结构

客官°小女子只卖身不卖艺 2022-06-04 09:41 196阅读 0赞

\#include <stdio.h>  
\#include <stdlib.h>  
//需求，写一个顺序线性表，存储一个地址位置  
\#define LIST\_INIT\_SIZE    100        //线性表存储空间的初始分配量  
\#define LISTINCREMENT    10        //线性表存储空间的分配增量  
\#define TRUE 1  
\#define FALSE 0  
\#define OK    1  
\#define ERROR 0  
\#define INFEASIBLE -1  
\#define OVERFLOW -2  
typedef int Status;        //函数结果状态码  
  
typedef struct\{  
    int x;  
    int y;  
\}Point2D;  
  
typedef struct\{  
    Point2D \* element;        //存储空间基址  
    int length;                //当前长度  
    int listsize;            //当前分配的存储容量(以sizeof(elementType为单位))  
\}SqList;  
  
//初始化顺序表  
Status InitList(SqList \* L)\{  
     //分配一个listsize的空间(现在element就是一个数组)  
    L->element=(Point2D\*)malloc(LIST\_INIT\_SIZE\*sizeof(Point2D));  
    if(!L->element)\{  
        //没有申请到空间  
        exit(OVERFLOW);  
    \}  
    //申请成功之后，长度设置为0  
    L->length=0;  
    L->listsize=LIST\_INIT\_SIZE;  
    return OK;  
\}  
  
//插入元素(向顺序表中插入的第i个位置之前插入数据p)  
Status ListInsert(SqList \* L,int i,Point2D p)\{  
    int j;  
    //判断插入的位置是否合法  
    //i的合法位置为1  ListLength(L)+1  
    if(i<1||i>L->length+1)\{  
        //i的范围不合法  
        return ERROR;  
    \}  
    if(L->length>=L->listsize)\{  
        //如果大于等于最大的分配长度，则表示需要重新来分配内存  
        Point2D \* p=(Point2D\*)realloc(L->element,(L->listsize+LISTINCREMENT)\*sizeof(Point2D));  
        if(!p)\{  
            //如果为空则表示分配失败  
            return ERROR;  
        \}  
        //分配成功  
        L->element=p;  //新基址  
        L->listsize+=LISTINCREMENT;      
    \}  
    //如果都是合法的则将数据给插入进来,将第i个位置和之后的元素向后移动一个位置  
      
    for(j=L->length-1;j>=i-1;j--)\{  
        L->element\[j+1\]=L->element\[j\];  
    \}  
    //再i-1空间上写数据  
    L->element\[i-1\]=p;  
    //将长度加1  
    L->length++;  
    return OK;  
\}  
  
//合并顺序列表(将l1和l2中的元素给合并到l3中) l3必须在外面就进行分配内存空间  
void MergeList(SqList l1,SqList l2,SqList \*l3)\{  
    Point2D \*l1\_last,\*l2\_last;  
    Point2D \*l1\_start,\*l2\_start,\*l3\_start;  
    int i=l1.length+l2.length;  
    l3->length=l3->listsize=i;  
    l3\_start=l3->element=(Point2D\*)malloc(sizeof(Point2D));  
    if(!l3)\{  
        exit(OVERFLOW);  
    \}  
    l1\_start=l1.element;  
    l2\_start=l2.element;  
    l1\_last=l1.element+l1.length-1;  
    l2\_last=l2.element+l2.length-1;  
  
    while(l1\_start<=l1\_last&&l2\_start<=l2\_last)\{  
        if(l1\_start->x>l2\_start->x)\{  
            \*l3\_start=\*l1\_start;  
            l3\_start++;  
            l1\_start++;  
        \}else if(l1\_start->x<l2\_start->x)\{  
            \*l3\_start=\*l2\_start;  
            l3\_start++;  
            l2\_start++;  
        \}else\{  
            //相等  
            \*l3\_start=\*l2\_start;  
            l3\_start++;  
            l2\_start++;  
            l1\_start++;  
        \}  
    \}  
    while(l1\_start<=l1\_last)\{  
        \*l3\_start=\*l1\_start;  
        l3\_start++;  
        l1\_start++;  
    \}  
  
    while(l2\_start<=l2\_last)\{  
        \*l3\_start=\*l2\_start;  
        l3\_start++;  
        l2\_start;  
    \}  
\}  
  
  
//测试  
int main()\{  
    int i;  
    SqList \* L1=(SqList \*)malloc(sizeof(SqList));  
    Point2D p=\{1,2\};  
    //初始化一个指向结构体的指针  
    //该结构体分配一块空间用来存储数组的首地址，数组的长度，数组的最大容量  
    SqList \* L=(SqList\*)malloc(sizeof(SqList));          
    i=InitList(L);  
    if(i==OK)\{  
        printf("创建成功");  
    \}  
    i=ListInsert(L,1,p);  
    if(i==OK)\{  
        printf("插入成功");  
    \}  
    i=ListInsert(L,2,p);  
    //打印插入的数据元素  
    printf("数据x为%d,数据y为:%d,顺序表的长度为%d",L->element\[0\].x,L->element\[0\].y,L->length);  
      
    printf("hello world");  
    printf("新创建一个顺序列表的集合");  
      
    MergeList(\*L,\*L,L1);  
    printf("合并后的顺序表的长度为%d,总容量为%d\\n",L1->length,L1->listsize);  
    while(L1->element->x)\{  
        printf("数据的x值为:%d\\n",L1->element->x);  
        L1->element++;  
    \}  
    scanf("%d",&i);  
\}