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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//
//  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 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//
//  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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//
//  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);

}