抽象数据类型线性表的定义与实现

最近刚刚上完数据结构的第一章，好久没有写线性表了，正好借着老师的作业温习一下，主程序实现的就是简单的list有序合并。不多比比，直接上代码

第一部分 de.hpp文件

//
//  main.cpp
//  test
//
//  Created by 蔡鹏 on 2018/9/4.
//  Copyright © 2018年 蔡鹏. All rights reserved.
//
#ifndef de_hpp
#define de_hpp

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 //存储空间初始分配量
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 //不可实施
#define OVERFLOW -2  //溢出elem

typedef int ElemType;//ElemType根据实际情况而定，这里假设为int
typedef int Status;
typedef struct
{
    ElemType *elem;//数组存储数据元素,最大值为MAXSIZE
    int listsize ;//当前分配的储存容量
    int length;//线性表当前长度
}SqList;

void CreateList(SqList *L, ElemType a[], int n); //利用数组初始化Sqlist
Status InitList(SqList *L);              //初始化，动态分配一块存储空间
Status DestroyList(SqList *L);        //释放这一段存储空间（撤销对应于动态）
Status ClearList(SqList *L);
Status ListEmpty(SqList L);
Status ListLength(SqList L);
Status GetElem(SqList L, int i, int *e);
Status LocateList(SqList L, int e);     //在表中查找值为e的元素
Status PriorElem(SqList L, int cur_e, int *pri_e);  //求当前元素的前驱
Status NextElem(SqList L, int cur_e, int *Nex_e); //求当前元素的后继
Status ListInsert(SqList *L, int i, int e);    //插入操作
Status ListDelete(SqList *L, int i, int *e); //删除操作
Status TravelList(SqList L);                //便历操作

#endif /* de_hpp */

第二部分 defc.hpp

//
//  main.cpp
//  test
//
//  Created by 蔡鹏 on 2018/9/4.
//  Copyright © 2018年 蔡鹏. All rights reserved.
//
#include "de.hpp"
void CreateList(SqList *L, ElemType a[5], int n){
    int i;
    for (i=0; i<n; i++){
        *(L->elem+i) = a[i];
    }
    L->length=n;

}
Status InitList(SqList *L){//创造一个空的线形表
    L->elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
    if(!L->elem) exit(OVERFLOW);//错误退出
    L->length = 0;
    L->listsize = MAXSIZE;
    return OK;
}
Status DestroyList(SqList *L){
    free(L->elem);         //释放空间
    L->elem = NULL;      //将指针置空
    L->length = 0;         //当前元素个数为0
    L->listsize = 0;        //表长为0
    return OK;
}
Status ClearList(SqList *L){
    L->length = 0;
    return OK;
}
Status ListEmpty(SqList L){
    if (L.length == 0)
        return TURE;
    else
        return FALSE;
}
Status ListLength(SqList L){
    return L.length;
}
Status GetELem(SqList L,int i,int *e){
    *e = *(L.elem + i);
    return TURE;
}
Status LocateList(SqList L,int e){
    int i;
    int * p = L.elem;
    for (i=0; i<L.length; i++, p++){
        if (*p == e)
            return i;
    }
    return FALSE;
}
Status PriorElem(SqList L ,int cur_e,int *pri_e){
    int i;
    int *p = L.elem;
    for (i=0; i<L.length; i++,p++){ //顺序表长度已知，故用for循环
        if (i==0 && *p==cur_e)
            return FALSE;
        if (*p == cur_e){  //找到了当前元素且不是第一个元素，
            *pri_e = *--p;      //将其前驱赋给引用参数
            return TURE;
        }
    }
    return FALSE;
}
Status NextElem(SqList L, int cur_e, int *Nex_e){
    int i;
    int *p = L.elem;
    for(i = 0;i<L.length;i++,p++){
        if(i==L.length-1 &&  *p  == cur_e)
            return FALSE;
        if(*p == cur_e){
            *Nex_e = *++p;
            return TURE;
        }
    }
    return FALSE;
}
Status ListInsert(SqList *L, int i, int e){
    int *p, *q;
    p = L->elem + i ;                 //p指向插入的位置
    q = L->elem + L->length - 1;    //q指向表中元素最后一个位置
    for (; q>=p; q--)    //从最后一个元素开始依次向后移动表中元素
         *(q+1) = *q;
    *(q+1) = e;              //插入元素
    L->length++;     // 表长增一
    return TURE;
}
Status ListDelete(SqList *L, int i, int *e){
    int *p, *q;
    if (i<1 || i>L->length)
            return FALSE;
    p = L->elem + i - 1;         //p指向要删除的元素的位置
    q = L->elem + L->length - 1;  //q指向表中最后一个元素位置
    *e = *p;                //将要删除的元素保存起来
    for (; p<=q; p++)   //从要删除元素的后面一个元素开始移动元素
        *p = *(p+1);
    L->length--;          //表长减一
    return TURE;
}
Status TravelList(SqList L){
    int i;
    int *p = L.elem;
    for (i=0; i<L.length; i++,p++){
    printf("第%d个元素为：%dn", i, *p);
    }
    return TURE;
}

第三部分 main 主程序

//
//  main.cpp
//  test
//
//  Created by 蔡鹏 on 2018/9/4.
//  Copyright © 2018年 蔡鹏. All rights reserved.
//
#include "defc.hpp"
void MergeList(SqList La,SqList Lb,SqList &Lc){
    int i,j,k,La_len,Lb_len,ai,bj;
    i=j=0;
    k=0;
    La_len = La.length;
    Lb_len = Lb.length;
    while(i<La_len&&j<Lb_len){
        GetELem(La, i, &ai);
        GetELem(Lb, j, &bj);
        if(ai<=bj) {ListInsert(&Lc, k++, ai);++i;}
        else{ListInsert(&Lc, k++, bj);++j;}
    }
    while (i<La_len) {
        GetELem(La, i++, &ai);
        ListInsert(&Lc, k++, ai);
    }
    while (j<Lb_len) {
        GetELem(Lb, j++, &bj);
        ListInsert(&Lc, k++, bj);
    }
}
int main(){
    int la[5] = {1,3,5,7,9};
    int lb[5] = {2,3,6,8,10};
    SqList La,Lb,Lc;
    InitList(&La);
    InitList(&Lb);
    InitList(&Lc);
    CreateList(&La, la, 5);
    CreateList(&Lb, lb, 5);
    MergeList(La, Lb, Lc);
    TravelList(Lc);

}

结果图

最后

以上就是聪明荔枝为你收集整理的抽象数据类型线性表的定义与实现的全部内容，希望文章能够帮你解决抽象数据类型线性表的定义与实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。