数据结构之线性表（C语言）

浅浅的花香味﹌ 2022-04-08 14:55 168阅读 0赞

线性表的两种存储方式

1，顺序存储

利用数组

/*
        数据结构之线性表复习--顺序存储
        构建了以下函数：
        初始化，查找，插入，删除，合并，输出
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define LIST_INIT_SIZE 100
    #define LISTINCREATE 10
    #define OVERFLOW -2
    #define OK 1
    #define ERROR 0
    typedef int Status;
    typedef int ElemType;
    typedef struct LNode{
        ElemType *data;
        int length;
        int size;
    }List,*SqList;
    
    Status InitList_Sq(List &L){
        L.data = (ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
        if(!L.data)
        {
            exit(OVERFLOW);
        }
        L.size = LIST_INIT_SIZE;
        L.length = 0;
        return OK;
    }
    int ListLocate_Sq(List &L,ElemType x){
        int a = -1;
        for(int i = 0; i < L.length; i++){
            if(L.data[i] == x)
            {
                a = i;
                break;
            }
        }
        if(-1 == a)
            return ERROR;
        else
            return a+1;
    }
    
    Status Insert_Sq(int i,ElemType x,List &L){
        if(i < 1 || i > L.length + 1) return ERROR;
        if(L.length >= L.size){
            ElemType *newbase = (ElemType *)realloc(L.data,(L.size+LISTINCREATE)*sizeof(ElemType));
            if(!newbase) exit(OVERFLOW);
            L.size += LISTINCREATE;
            L.data = newbase;
        }
        ElemType *p,*q;
        p = &(L.data[i-1]);
        for(q = &(L.data[L.length - 1]);q >= p; q--){
            *(q+1) = *q;
        }
        *p = x;
        ++L.length;
        return OK;
    }
    Status Delete_Sq(int pos,List &L){
        if(pos < 1 || pos > L.length) return ERROR;
        ElemType *p = &(L.data[pos-1]);
        int elem = *p;
        ElemType *q = L.data +L.length + 1;
        for(++p;p <= q; p++){
            *(p-1) = *p;
        }
        --L.length;
        return OK;
    }
    
    void Merge_Sq(List &L1,List &L2,List &L3){
        ElemType *pa = L1.data;
        ElemType *pb = L2.data;
        L3.length = L3.size = L1.length + L2.length;
        ElemType *pc = L3.data = (ElemType *)malloc(sizeof(ElemType)*L3.size);
        if(!L3.data)
            exit(OVERFLOW);
        ElemType *pa_last = L1.data + L1.length - 1;
        ElemType *pb_last = L2.data + L2.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++;
    }
    void putList(List &L){
        int i;
        for(i = 0; i < L.length; i++){
            if(i == 0)
                printf("%d",L.data[i]);
            else
                printf(" %d",L.data[i]);
        }
        printf("\n");
    }
    int main(){
        int num,i,tmp;
        List L;
        int a = InitList_Sq(L);
        printf("请输入线性表的长度：(100以内)\n");
        scanf("%d",&num);
        L.length = num;
        printf("请输入元素：\n");
        for(i = 0; i < num; i++){
            scanf("%d",&tmp);
            L.data[i] = tmp;
        }
        putList(L);
    
        //测试用例可以自行设置
        //以下为测试
        List L2;
        List L1 = L;
        printf("合并：\n");
        Merge_Sq(L,L1,L2);
        putList(L2);
        printf("插入：\n");
        Insert_Sq(5,5,L);
        putList(L);
        printf("删除：\n:");
        Delete_Sq(4,L);
        putList(L);
    
        return 0;
    }

2，链式存储

/*
        数据结构之线性表--链式存储
        实现函数有：
        初始化（头插法和尾插法），查找，插入，
        删除，长度，输出，逆置，合并
    
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int ElemType;
    typedef int Status;
    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    /*
    //第一种初始化方法：头插法
    Status LinkCreate(LinkList &L,int len){
        LinkList p;
        int i;
        L = (LinkList)malloc(sizeof(LNode));
        L->next = NULL;
        printf("请输入元素：\n");
        for(i = 0; i < len; i++){
            p = (LinkList)malloc(sizeof(LNode));
            scanf("%d",&p->data);
            p->next = L->next;
            L->next = p;//插入到表头
        }
    }
    */
    //第二种初始化方法：尾插法
    Status LinkCreate(LinkList &L,int len){
        LinkList tail,p;
        L = (LinkList)malloc(sizeof(LNode));
        if(!L) exit(OVERFLOW);
        L->next = NULL;
        tail = L;
        printf("请输入元素：\n");
        for(int i = 0; i  < len; i++){
            p = (LinkList)malloc(sizeof(LNode));
            scanf("%d",&p->data);
            p->next = NULL;
            tail->next = p;
            tail = p;
        }
        return OK;
    }
    
    //获取第i个元素，返回给e
    Status GetElem(int pos,LinkList& L,ElemType &e){
        LinkList p = L->next;
        int j = 1;//计数器
        while(p && j < pos){
            j++;
            p = p->next;
        }
        if(j > pos || !p)
            return ERROR;
        e = p->data;
        return OK;
    }
    Status LinkInsert(LinkList &L,int pos,ElemType e){
        LinkList p = L->next,s;
        int j = 1;
        while(p && j < pos-1){
            p = p->next;
            j++;
        }
        if(!p || j > pos){
            return ERROR;
        }
        s = (LinkList)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;//这两步是核心
        p->next = s;
    }
    Status LinkDelete(LinkList &L,int pos,ElemType &e){
        LinkList p = L->next;
        int j = 1;
        while(p && j < pos-1){
            p = p->next;
            j++;
        }
        if(!p || j > pos-1)
            return ERROR;
        LinkList q = p->next;//这两步是核心
        p->next = q->next;
        e = q->data;
        free(q);
        return OK;
    }
    int LinkLength(LinkList &L){
        LinkList p = L->next;
        int len = 0;
        while(p){
            p = p->next;
            len++;
        }
        return len;
    }
    void LinkPut(LinkList &L){
        int i = 0;
        LinkList p = L->next;
        while(p){
            if(i == 0)
                printf("%d",p->data);
            else
                printf(" %d",p->data);
            p = p->next;
            i++;
        }
        printf("\n");
    }
    //单链表的就地逆置
    void LinkReverse(LinkList &L){
        LinkList p = L->next,q;
        L->next = NULL;
        while(p){
            q = p;
            p = p->next;
            q->next = L->next;
            L->next = q;
        }
    }
    //链表的合并
    void LinkMerge(LinkList &La,LinkList &Lb,LinkList &Lc){
        LinkList pa,pb,pc;
        pa = La->next;
        pb = Lb->next;
        pc = Lc = La;
        while(pa && pb){
            if(pa->data <= pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            }
            else{
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
        }
        pc->next = pa?pa:pb;
        free(Lb);
    }
    //测试用例
    int main()
    {
        LinkList L1,L2,L3;
        int num,s;
        printf("请输入元素个数：\n");
        scanf("%d",&num);
        LinkCreate(L1,num);
        //LinkCreate(L2,num);
        //LinkCreate(L3,num);
        LinkPut(L1);
        printf("长度：%d\n",LinkLength(L1));
    //    LinkInsert(L1,2,5);
    //    LinkPut(L1);
    //    LinkDelete(L1,4,s);
    //    LinkPut(L1);
        //LinkPut(L2);
        //LinkMerge(L1,L2,L3);
        //LinkPut(L3);
        LinkReverse(L1);
        LinkPut(L1);
        return 0;
    }