数据结构C线性表现实

linearlist.h

#ifndef _inc_stdio_8787
#define _inc_stdio_8787
#include <stdio.h>
#include <malloc.h>
#define list_init_size 100    // 线性表存储空间的初始分配量
#define list_increment 10    // 线性表存储空间的分配增量

typedef int elemtype;        // 数据元素的类型

typedef struct {
    elemtype *elem;    // 存储空间的集地址
    int length;        // 当前线性表的长度
    int listsize;    // 当前分配的存储容量
} linearlist;

int init_list(linearlist *list);    //初始化线性表

void clear_list(linearlist *list);

void destroy_list(linearlist* list);

int list_empty(linearlist* list);

int list_length(linearlist* list);

void print_list(linearlist* list);

int locate_elem(linearlist* list, elemtype* x);

int prior_elem(linearlist* list, elemtype* cur_elem, elemtype* pre_elem);

int get_elem(linearlist* list, int index, elemtype* e);

int next_elem(linearlist* list, elemtype* cur_elem, elemtype* next_elem);

int insert_elem(linearlist* list, int index, elemtype* e);

int delete_elem(linearlist* list, int index, elemtype* e);

int append_elem(linearlist* list,elemtype* e);

int pop_elem(linearlist* list, elemtype* e);

void union_list(linearlist* list_a, linearlist* list_b, linearlist* list_c);

void intersect_list(linearlist* list_a, linearlist* list_b, linearlist* list_c);

void except_list(linearlist* list_a,linearlist* list_b, linearlist* list_c);
#endif

linearlist.c

#include "linearlist.h"

int init_list(linearlist *list)
{
    list->elem = (elemtype *)malloc(list_init_size*sizeof(elemtype));
    if (!list->elem)
    {
        return -1;
    }
    list->length = 0;
    list->listsize = list_init_size;
    return 0;
}

void clear_list(linearlist *list)
{
    list->length = 0;
}

void destroy_list(linearlist* list)
{
    free(list);
}

int list_empty(linearlist* list)
{
    return (list->length == 0);
}

int list_length(linearlist* list)
{
    return list->length;
}

int locate_elem(linearlist* list, elemtype* x)
{
    int pos = -1;
    int i;
    for (i = 0; i < list->length; i++)
    {
        if (list->elem[i] == *x)
        {
            pos = i;
        }
    }
    return pos;
}

int prior_elem(linearlist* list, elemtype* cur_elem, elemtype* pre_elem)
{
    int pos = -1;
    pos = locate_elem(list, cur_elem);
    if(pos <= 0) 
    {
        return -1;
    }
    *pre_elem = list->elem[pos-1];
    return 0;
}

int insert_elem(linearlist* list, int index, elemtype* e)
{
    elemtype *q, *p;
    if (index < 0 || index >= list->length)
    {
        return -1;
    }
    if (list->length >= list->listsize)
    {
        elemtype *newbase = (elemtype*)realloc(list->elem, (list->listsize + list_increment)*sizeof(elemtype));
        if (!newbase)
        {
            return -1;
        }
        list->elem = newbase;
        list->listsize += list_increment;
    }
    q = &(list->elem[index]);
    for (p = &(list->elem[list->length-1]); p >= q; p--)
    {
        *(p+1) = *p;
    }
    *q = *e;
    ++list->length;
    return 0;
}

int append_elem(linearlist* list,elemtype* e)
{
    if (list->length >= list->listsize)
    {
        elemtype *newbase = (elemtype*)realloc(list->elem, (list->listsize + list_increment)*sizeof(int));
        if (!newbase)
        {
            return -1;
        }
        list->elem = newbase;
        list->listsize += list_increment;
    }
    list->elem[list->length] = *e;
    ++list->length;
    return 0;
}

void print_list(linearlist* list){
    int i;
    for (i=0; i < list->length; i++){
        printf("%d \n", list->elem[i]);
    }
}

int get_elem(linearlist* list, int index, elemtype* e){
    if (index<0 || index >= list->length) return -1;
    *e = list->elem[index];
    return 0;
}

int next_elem(linearlist* list, elemtype* cur_elem, elemtype* next_elem){
    int pos = -1;
    pos = locate_elem(list, cur_elem);
    if(pos == -1 || pos == (list->length - 1)) return -1;
    *next_elem = list->elem[pos+1];
    return 0;
}

int delete_elem(linearlist* list, int index, elemtype* e)
{
    elemtype *q, *p;
    if (index < 0 || index >= list->length)
    {
        return -1;
    }
    p = &(list->elem[index]);
    *e = *p;
    q = list->elem + list->length -1;
    for (++p; p < q; ++p)
    {
        *(p - 1) = *p;
    }
    --list->length;
    return 0;
}

int pop_elem(linearlist* list, elemtype* e){
    if (list_empty(list)) return -1;
    *e = list->elem[list->length - 1];
    --list->length;
    return 0;
}

void union_list(linearlist* list_a, linearlist* list_b, linearlist* list_c){ //并集,c=a∪b
    int i,a_length,b_length;
    elemtype elem;
    a_length = list_length(list_a);
    b_length = list_length(list_b);
    for(i=0;i<a_length;i++){
        get_elem(list_a, i, &elem);
        append_elem(list_c,&elem);
    }   
    for(i=0;i<b_length;i++){
        get_elem(list_b, i, &elem);
        if(locate_elem(list_a, &elem) == -1){
            append_elem(list_c,&elem);
        }
    }
}

void intersect_list(linearlist* list_a, linearlist* list_b, linearlist* list_c){ //交集,c=a∩b
    int i,a_length;
    elemtype elem;
    a_length = list_length(list_a);
    for(i=0;i<a_length;i++){
        get_elem(list_a, i, &elem);
        if(locate_elem(list_b, &elem) != -1){
            append_elem(list_c,&elem);
        }
    }
}

void except_list(linearlist* list_a,linearlist* list_b, linearlist* list_c){ //差集,c=a-b(属于a而不属于b)
    int i,a_length;
    elemtype elem;
    a_length = list_length(list_a);
    for(i=0;i<a_length;i++){
        get_elem(list_a, i, &elem);
        if(locate_elem(list_b, &elem) == -1){
            append_elem(list_c,&elem);
        }
    }
}

index.c

#include "linearlist.h"
void main() {
    int i;
    elemtype elem;
    linearlist *list_a = (linearlist *)malloc(sizeof(linearlist));
    linearlist *list_b = (linearlist *)malloc(sizeof(linearlist));
    linearlist *list_c = (linearlist *)malloc(sizeof(linearlist));
    init_list(list_a);
    init_list(list_b);
    init_list(list_c);
    
    for (i = 0; i < 10; i++){
        append_elem(list_a,&i);
    }
    
    for (i = 0; i < 20; i+=2){
        append_elem(list_b,&i);
    }   
    print_list(list_a);
    print_list(list_b);
    
    pop_elem(list_a, &elem);
    print_list(list_a);
    printf("pop: %d \n",elem);
    
    delete_elem(list_a, 2, &elem);
    print_list(list_a);
    printf("delete: %d \n",elem);
    
    insert_elem(list_a, 2, &elem);
    printf("insert: %d \n",elem);
    print_list(list_a);
    
    get_elem(list_a, 5, &elem);
    printf("get elem at 5: %d \n",elem);
    
    printf("locate : elem %d at %d \n",elem,locate_elem(list_a,&elem));
    
    printf("list_a length : %d \n",list_length(list_a));
    
    print_list(list_a);
    print_list(list_b);
    
    union_list(list_a,list_b,list_c);
    print_list(list_c);
    clear_list(list_c);
    
    intersect_list(list_a,list_b,list_c);
    print_list(list_c);
    clear_list(list_c);
    
    except_list(list_a,list_b,list_c);
    print_list(list_c);
    
    destroy_list(list_a);
    destroy_list(list_b);
    destroy_list(list_c);
}