526互联

线性表之顺序表实现

发布时间 2023-03-26 16:28:22作者: 才下眉头3

头文件

#ifndef LINER_LIST_SEQLIST_H
#define LINER_LIST_SEQLIST_H

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <stdbool.h>

#define SEQLIST_INIT_SIZE 8

#define     INC_SIZE 3
typedef int ElemType;

typedef struct SeqList {
    ElemType *base;
    int capacity;
    int size;
} SeqList;

bool Inc(SeqList *list);

void InitSeqList(SeqList *list);

void push_back(SeqList *list, ElemType x);

void show_list(SeqList *list);

void push_front(SeqList *list, ElemType x);

void pop_back(SeqList *list);

void pop_front(SeqList *list);

void insert_pos(SeqList *list, int pos, ElemType item);

int find(SeqList *list, ElemType x);

int length(SeqList *list);

void delete_pos(SeqList *list, int pos);

void delete_val(SeqList *list, ElemType x);

void sort(SeqList *list);

void resver(SeqList *list);

void clear(SeqList *list);

void destory(SeqList *list);

void merge(SeqList *lt, SeqList *la, SeqList *lb);

#endif //LINER_LIST_SEQLIST_H

主函数

#include "SeqList.h"

void main(){
    SeqList  mylist,youlist,list;
    InitSeqList(&mylist);
    InitSeqList(&youlist);
    push_back(&mylist,1);
    push_back(&mylist,3);
    push_back(&mylist,5);
    push_back(&mylist,7);

    push_back(&youlist,2);
    push_back(&youlist,3);
    push_back(&youlist,6);
    push_back(&youlist,9);
    merge(&list,&mylist,&youlist);
    show_list(&list);

}
/*void main() {
    SeqList mylist;
    InitSeqList(&mylist);
    ElemType item;
    int pos;
    int select = 1;
    while (select) {
        printf("*********************************\n");
        printf("* [1] push_back  [2] push_front *\n");
        printf("* [3] show_list  [4] pop_back   *\n");
        printf("* [5] pop_front  [6] insert_pos *\n");
        printf("* [7] find       [8] lenght     *\n");
        printf("* [9] delete_pos [10] delete_val \n");
        printf("* [11] sort      [12] resver    *\n");
        printf("* [13] clear     [14] destory  *\n");
        printf("* [0] exit_system");
        printf("*********************************\n");
        printf("请选择:>");
        scanf("%d", &select);
        if (select == 0)
            break;
        switch (select) {
            case 1:
                printf("请输入要插入的数据:(-1结束)>");
                while (scanf("%d", &item), item != -1) {
                    push_back(&mylist, item);
                }
                break;
            case 2:
                printf("请输入要插入的数据:(-1结束)>");
                while (scanf("%d", &item), item != -1) {
                    push_front(&mylist, item);
                }
                break;
            case 3:
                show_list(&mylist);
                break;
            case 4:
                pop_back(&mylist);
                break;
            case 5:
                pop_front(&mylist);
                break;
            case 6:
                printf("请输入要插入的数据:>");
                scanf("%d", &item);
                printf("请输入要插入的位置:>");
                scanf("%d", &pos);
                insert_pos(&mylist, pos, item);
                break;
            case 7:
                printf("请输入要查找的数据");
                scanf("%d", &item);
                pos = find(&mylist, item);
                if (pos == -1) {
                    printf("元素不在表内");
                } else {
                    printf("元素找到了，位置索引为%d\n", pos);
                }
                break;
            case 8:
                printf("顺序表的长度为:> %d\n",length(&mylist));
                break;
            case 9:
                printf("请输入要删除数据的位置:>");
                scanf("%d",&pos);
                delete_pos(&mylist,pos);
                break;
            case 10:
                printf("请输入要删除的数据:>");
                scanf("%d",&item);
                delete_val(&mylist,item);
                break;
            case 11:
                printf("sorted :>");
                sort(&mylist);
                break;
            case 12:
                printf("resver:>");
                resver(&mylist);
                break;
            case 13:
                printf("清除");
                clear(&mylist);
                break;
            case 14:
                destory(&mylist);
                break;
            default:
                printf("输入的选择错误，请重新输入:>");
                break;
        }

    }
}
*/

其他函数

#include "SeqList.h"

void InitSeqList(SeqList *list) {
    list->base = (ElemType *) malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);
    assert(list->base != NULL);
    list->capacity = SEQLIST_INIT_SIZE;//初始存储容量
    list->size = 0;//空表长度
}

//尾插
void push_back(SeqList *list, ElemType x) {
    if (list->size >= list->capacity && !Inc(list)) {
        printf("顺序表的空间已满，%d不能尾部插入数据\n", x);
        return;
    }
    list->base[list->size] = x;
    list->size++;
}

//头插
void push_front(SeqList *list, ElemType x) {
    if (list->size >= list->capacity && !Inc(list)) {
        printf("顺序表的空间已满，%d不能尾部插入数据\n", x);
        return;
    }
    for (int i = list->size; i > 0; i--) {
        list->base[i] = list->base[i - 1];
    }
    list->base[0] = x;
    list->size++;
}

//删除pop_back
void pop_back(SeqList *list) {
    if (list->size == 0) {
        printf("表长为0，无法进行删除");
        return;
    }
    list->size--;
}

//删除 pop_front
void pop_front(SeqList *list) {
    if (list->size == 0) {
        printf("表长为0，无法进行删除");
        return;
    }
    for (int i = 0; i < list->size - 1; ++i) {
        list->base[i] = list->base[i + 1];
    }
    list->size--;
}

//插入insert_pos
void insert_pos(SeqList *list, int pos, ElemType x) {
    if (pos < 0 || pos > list->size) {
        printf("插入数据的位置非法，不能插入数据：\n");
        return;
    }
    if (list->size >= list->capacity && !Inc(list)) {
        printf("顺序表的空间已满，%d不能按位置插入数据\n", x);
        return;
    }
//    if (pos == 0) {
//        push_front(list, x);
//    } else if (pos == list->size) {
//        push_back(list, x);
//    } else {
    for (int i = list->size; i > pos; --i) {
        list->base[i] = list->base[i - 1];
    }
    list->base[pos] = x;
    list->size++;
}

//查找
int find(SeqList *list, ElemType x) {
    for (int i = 0; i < list->size; ++i) {
        if (list->base[i] == x) {
            return i;
        }
    }
    return -1;
}

//长度
int length(SeqList *list) {
    return list->size;
}

//删除位置元素
void delete_pos(SeqList *list, int pos) {
    if (pos < 0 || pos >= list->size) {
        printf("删除数据的位置非法，不能删除数据：\n");
        return;
    }
    for (int i = pos; i < list->size - 1; i++) {
        list->base[i] = list->base[i + 1];
    }
    list->size--;
}

//删除指定内容的数据
void delete_val(SeqList *list, ElemType x) {
//    for (int i = 0; i < list->size; ++i) {
//        if(list->base[i] == x){
//            for (int j = i; j < list->size-1; ++j) {
//                list->base[i] = list->base[i+1];
//            }
//            list->size--;
//        }
//        else{
//            printf("输入删除的数据有误");
//        }
//    }
// 利用前面写完的函数
    int pos = find(list, x);
    if (pos == -1) {
        printf("要删除的数据不存在\n");
        return;
    }
    delete_pos(list, pos);
}

//顺序表排序(冒泡)
void sort(SeqList *list) {
    for (int i = 0; i < list->size - 1; ++i) {
        for (int j = 0; j < list->size - 1 - i; ++j) {
            if (list->base[j] > list->base[j + 1]) {
                list->base[j] ^= list->base[j + 1];
                list->base[j + 1] ^= list->base[j];
                list->base[j] ^= list->base[j + 1];
            }
        }

    }
}

//逆置
void resver(SeqList *list) {
    if (list->size == 0 || list->size == 1) {
        return;
    }
    int low;
    int hight;
    for (low = 0, hight = list->size - 1; low < hight; low++, hight--) {
        list->base[low] ^= list->base[hight];
        list->base[hight] ^= list->base[low];
        list->base[low] ^= list->base[hight];
    }
}

//清除
void clear(SeqList *list) {
    list->size = 0;
}

//摧毁
void destory(SeqList *list) {
    free(list->base);
    list->base = NULL;
    list->capacity = 0;
    list->size = 0;
}

//
bool Inc(SeqList *list) {
    ElemType *newbase = (ElemType *) realloc(list->base, sizeof(ElemType) * (list->capacity + INC_SIZE));
    if (newbase == NULL) {
        printf("增配空间失败,内存不足\n");
        return false;
    }
    list->base = newbase;
    list->capacity += INC_SIZE;
    return true;
}

//合并顺序表
void merge(SeqList *lt, SeqList *la, SeqList *lb) {
    lt->capacity = la->size + lb->size;
    lt->base = (ElemType *) malloc(sizeof(ElemType) * lt->capacity);
    assert(lt->base != NULL);
    int ia = 0;
    int ib = 0;
    int ic = 0;
    while (ia < la->size && ib < lb->size) {
        if (la->base[ia] < lb->base[ib])
            lt->base[ic++] = la->base[ia++];
        else
            lt->base[ic++] = la->base[ib++];
    }
    while (ia < la->size) {
        lt->base[ic++] = la->base[ia++];
    }
    while (ib < lb->size) {
        lt->base[ic++] = la->base[ib++];
    }
    lt->size = la->size + lb->size;

}

//打印顺序表内容
void show_list(SeqList *list) {
    printf("顺序表如下: ");
    for (int i = 0; i < list->size; ++i) {
        printf("%2d", list->base[i]);
    }
    putchar(10);
}