C++ 线性表实现

 

list.h 

#pragma once
#include "targetver.h"

#include <stdio.h>
#include <tchar.h>

#define list_init_size 100
#define maxsize 100

typedef int elemtype;

typedef struct sqlist {
    elemtype * elem;
    int length;
    int listsize;
}sqlist, *listptr;

typedef enum status {
    success, fail, fatal, rangeerror,overflow
}status;

status list_init(listptr l);

void list_destroy(listptr l);

void list_clear(listptr l);

bool list_empty(listptr l);

int list_size(listptr l);

status list_retrieve(listptr l, int pos, elemtype * elem);

status list_locate(listptr l, elemtype elem, int *pos);

status list_insert(listptr l, int pos, elemtype elem);

status list_remove(listptr l, int pos);

status list_prior(listptr l, int pos, elemtype * elem);

 

线性表.cpp

#include "stdafx.h"
#include<iostream>
#include "list.h"
using namespace std;

status list_retrieve(listptr l, int pos, elemtype * elem) {
    status status = rangeerror;
    int len = l->length;
    if (1 <= pos&&pos <= len) {
        *elem = l->elem[pos];
        status = success;
    }
    return status;
}

status list_locate(listptr l, elemtype elem, int * pos) {
    status status = rangeerror;
    int len = l->length;
    int i = 1;
    while (i <= len && l->elem[i]==elem) {
        i++;
    }
    if (i <= len) {
        *pos = i;
        status = success;
    }
    return status;
}

status list_insert(listptr l, int pos, elemtype elem) {
    status status = rangeerror;
    int len = l->length,i;
    if (len > maxsize)status = overflow;
    else if (1 <= pos && pos <= len + 1) {
        for (i = len; i >= pos; i--)
            l->elem[i + 1] = elem;
        l->elem[pos] = elem;
        l->length++;
        status = success;
    }
    return status;
}

status list_init(listptr l) {
    status status = fatal;
    l->elem = (elemtype*)malloc((maxsize + 1) * sizeof(elemtype));
    if (l->elem) {
        l->length = 0;
        status = success;
    }
    return status;
}

void list_destroy(listptr l) {
    if (l->elem) {
        free(l->elem);
        l->elem = null;
    }
    l->length = 0;
}

void list_clear(listptr l) {
    l->length = 0;
}

bool list_empty(listptr l) {
    return l->length == 0;
}

status list_prior(listptr l, int pos, elemtype * elem) {
    status status = fail;
    int len = l->length;
    if (2 <= pos && pos <= len) {
        *elem = l->elem[pos - 1];
        status = success;
    }
    return status;
}

status list_next(listptr l, int pos, elemtype * elem) {
    status status;
    int len = l->length;
    if (1 <= pos && pos <= len - 1) {
        *elem = l->elem[pos+1];
        status = success;
    }
    return status;
}

int list_size(listptr l) {
    return l->length;
}

status list_remove(listptr l, int pos) {
    status status = rangeerror;
    int len = l->length, i;
    if (1 <= pos && pos <= len) {
        for (i = pos; i < len; i++) 
            l->elem[i] = l->elem[i + 1];
        l->length--;
        status = success;
    }
    return status;
}


status list_union(listptr la, listptr lb) {
    elemtype elem;
    status status= fail;
    int i, len = list_size(lb);
    for (i = 1; i <= len; i++) {
        list_retrieve(lb, i, &elem);
        if (status != success) {
            status = list_insert(la, 1, elem);
            if (status != success)break;
        }
    }
    return status;
}



status list_merge(listptr la, listptr lb, listptr lc) {
    elemtype elem1, elem2;
    status status=fail;
    status = list_init(lc);
    if(status != success)return status;
    int i = 1, j = 1, k = 1;
    int n = list_size(la), m = list_size(lb);
    while (i <= n && j <= m) {
        list_retrieve(la, i, &elem1), list_retrieve(lb, j, &elem2);
        if (elem1 < elem2) {
            status = list_insert(lc, k, elem1);
            i++;
        }
        else {
            status = list_insert(lc, k, elem2);
            j++;
        }
        if (status != success) return status;
        k++;
    }
    while (i <= n) {
        list_retrieve(la, i, &elem1);
        status = list_insert(lc, k, elem1);
        if (status != success) return status;
        i++, k++;
    }
    while (j <= m) {
        list_retrieve(lb, j, &elem2);
        status = list_insert(lc, k, elem2);
        if (status != success) return status;
        j++, k++;
    }
    return status;
}


int main() {
    listptr la = new sqlist, lb = new sqlist, lc = new sqlist;;
    list_init(la);
    list_init(lb);
    list_init(lc);
    int arra[5] = { 2,4,6,7,8 };
    for (int i = 1; i <= 5; i++)
        list_insert(la, i, arra[i-1]);
    
    for(int i=1;i<=5;i++)
        cout << la->elem[i] << " ";
    cout << endl;

    int arrb[5] = { 1,5,9,10,11 };
    for (int i = 1; i <= 5; i++)
        list_insert(lb, i, arrb[i - 1]);

    for (int i = 1; i <= 5; i++)
        cout << lb->elem[i] << " ";
    cout<< endl;

    status status = list_merge(la, lb, lc);
    cout << status << endl;
    if (status != success)return exit_failure;

    for (int i = 1; i <= 10; i++)
        cout << lc->elem[i] << " ";
    cout << endl;


    system("pause");
    return exit_success;
}

 

参考《数据结构与算法》 林劼