c/c++ 线性表之顺序表
程序员文章站
2022-06-18 16:28:54
线性表之顺序表 存储在连续的内存空间,和数组一样。 下面的代码,最开始定义了一个能存8个元素的顺序表,当超过8个元素的时候,会再追加开辟空间(函数:reInit)。 实现了以下功能: | 函数 | 功能描述 | | | | | push_back | 从最后插入 | | push_front | 从 ......
线性表之顺序表
存储在连续的内存空间,和数组一样。
下面的代码,最开始定义了一个能存8个元素的顺序表,当超过8个元素的时候,会再追加开辟空间(函数:reInit)。
实现了以下功能:
函数 | 功能描述 |
---|---|
push_back | 从最后插入 |
push_front | 从最前插入 |
show_list | 打印出顺序表里的元素 |
pop_back | 从最后删除 |
pop_front | 从最前删除 |
insert_pos | 从指定位置插入 |
find | 查找指定的元素,返回其在顺序表中的下标 |
length | 返回顺序表的长度 |
delete_pos | 从指定位置删除 |
delete_val | 删除指定的值的元素 |
sort1 | 按升序排序 |
sort2 | 按降序排序 |
resver | 反转顺序表中的元素 |
clear | 清除顺序表中的元素 |
destroy | 释放顺序表所占用的内存空间 |
SeqList.h
#ifndef __SEQLIST__ #define __SEQLIST__ #include <stdio.h> #include <malloc.h> #include <assert.h> #include <memory.h> #include <stdbool.h> #define SEQLIST_INIT_SIZE 8 typedef int ElemType; typedef struct SeqList{ int cap;//顺序表所能容纳的最大元素数量 int size;//当前顺序表中元素的数量 ElemType *base;//指向顺序表开始位置的指针 }SeqList; void init(SeqList*); void push_back(SeqList*, ElemType); void show_list(SeqList*); void push_front(SeqList*, ElemType); void pop_back(SeqList*); void pop_front(SeqList*); void insert_pos(SeqList*, ElemType, int); int find(SeqList*, ElemType); int length(SeqList*); void delete_pos(SeqList*, int); void delete_val(SeqList*, int); void sort1(SeqList*); void sort2(SeqList*); void resver(SeqList*); void clear(SeqList*); void destroy(SeqList*); #endif
SeqList.c
#include "SeqList.h" bool reInit(SeqList* seq){ //容量已满,所以重新开辟空间 ElemType* newp = (ElemType*)realloc(seq->base,(seq->size+1)*sizeof(ElemType)); if(NULL == newp){ return true; } //如果重新开辟的空间的地址和原来空间的地址不相同 //就需要把原来内存空间里的值,复制到新的内存空间中。 if(seq->base != newp){ memmove(seq->base, newp, sizeof(ElemType)*seq->size); seq->base = newp; } seq->cap++; return false; } void init(SeqList* seq){ //开辟能容纳8个元素的内存空间 seq->base = (ElemType*)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE); assert(NULL != seq->base); seq->cap = SEQLIST_INIT_SIZE; seq->size = 0; } void push_back(SeqList* seq, ElemType x){ if(seq->size >= seq->cap && reInit(seq)){ printf("线性表已满\n"); return; } seq->base[seq->size] = x; seq->size++; } void push_front(SeqList* seq, ElemType x){ if(seq->size >= seq->cap && reInit(seq)){ printf("线性表已满\n"); return; } //往后移动一个元素的距离 memmove(seq->base+1, seq->base,seq->size * sizeof(ElemType)); seq->base[0] = x; seq->size++; } void pop_back(SeqList* seq){ if(seq->size <= 0){ printf("线性表以空\n"); return; } seq->size--; } void pop_front(SeqList* seq){ if(seq->size <= 0){ printf("线性表以空\n"); return; } //往前移动一个元素的距离 memmove(seq->base, seq->base+1,seq->size * sizeof(ElemType)); seq->size--; } void insert_pos(SeqList* seq, ElemType x, int index){ if(seq->size >= seq->cap && reInit(seq)){ printf("线性表已满\n"); return; } if(index < 0 || index > seq->size){ printf("given index is error\n"); return; } //在指定的位置往后移动一个元素的距离 memmove(seq->base+index+1,seq->base+index,(seq->size-index)*sizeof(ElemType)); seq->base[index] = x; seq->size++; } int find(SeqList* seq, ElemType x){ for(int i = 0; i < seq->size; ++i){ if(x == seq->base[i]){ return i; } } return -1; } int length(SeqList* seq){ return seq->size; } void delete_pos(SeqList* seq, int index){ if(seq->size <= 0){ printf("线性表以空\n"); return; } if(index < 0 || index > seq->size - 1){ printf("given index is error\n"); return; } //在指定的位置往前移动一个元素的距离 memmove(seq->base+index,seq->base+index+1,(seq->size-index-1)*sizeof(ElemType)); seq->size--; } void delete_val(SeqList* seq, int value){ int pos = find(seq, value); if(pos == -1){ printf("The enter value is not exist"); return; } delete_pos(seq, pos); } void sort1(SeqList* seq){ for(int i = 0; i < seq->size-1; ++i){ for(int j = 0; j < seq->size-i-1; ++j){ if(seq->base[j] > seq->base[j+1]){ ElemType tmp = seq->base[j]; seq->base[j] = seq->base[j+1]; seq->base[j+1] = tmp; } } } } void sort2(SeqList* seq){ for(int i = 0; i < seq->size-1; ++i){ for(int j = 0; j < seq->size-1-i; ++j){ if(seq->base[j] < seq->base[j+1]){ seq->base[j] = seq->base[j] + seq->base[j+1]; seq->base[j+1] = seq->base[j] - seq->base[j+1]; seq->base[j] = seq->base[j] - seq->base[j+1]; } } } } void resver(SeqList* seq){ //如果seq->size是偶数就会被整除,如果是奇数就会舍掉小数位,不进1 for(int i = 0; i < seq->size / 2; ++i){ ElemType tmp = seq->base[i]; seq->base[i] = seq->base[seq->size-i-1]; seq->base[seq->size-i-1] = tmp; } } void clear(SeqList* seq){ seq->size = 0; } void destroy(SeqList* seq){ free(seq->base); seq->base = NULL; seq->cap = 0; seq->size = 0; } void show_list(SeqList* seq){ for(int i = 0; i < seq->size; ++i){ printf("%d ", seq->base[i]); } printf("\n"); }
SeqListMain.c
#include "SeqList.h" int main(){ SeqList list; init(&list); int select = 1; ElemType item; int index; 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] length ***\n"); printf("*** [9] delete_pos [10] delete_val ***\n"); printf("*** [11] sort1 [12] resver ***\n"); printf("*** [13] clear [14*] destroy ***\n"); printf("*** [0] quit [15] sort2 ***\n"); printf("*****************************************\n"); printf("请选择:>"); scanf("%d", &select); if(0 == select) break; switch(select){ case 1: printf("请输入要插入的数据,以-1结束>\n"); while(scanf("%d",&item),item != -1){ push_back(&list, item); } show_list(&list); break; case 2: printf("请输入要插入的数据,以-1结束>\n"); while(scanf("%d",&item),item != -1){ push_front(&list, item); } show_list(&list); break; case 3: show_list(&list); break; case 4: pop_back(&list); show_list(&list); break; case 5: pop_front(&list); show_list(&list); break; case 6: printf("请输入要插入的数据>\n"); scanf("%d",&item); printf("请输入要插入的index>\n"); scanf("%d",&index); insert_pos(&list, item, index); show_list(&list); break; case 7: printf("please enter what you shoule find out>\n"); scanf("%d",&item); index = find(&list, item); if(index == -1){ printf("can not find %d \n", item); }else{ printf("find %d at position %d\n", item, index); } show_list(&list); break; case 8: printf("length is %d\n", length(&list)); show_list(&list); break; case 9: printf("please enter the index that you shoule delete>\n"); scanf("%d", &index); delete_pos(&list, index); show_list(&list); break; case 10: printf("please enter the value what you shoule delete >\n"); scanf("%d", &item); delete_val(&list, item); show_list(&list); break; case 11: sort1(&list); show_list(&list); break; case 12: resver(&list); show_list(&list); break; case 13: clear(&list); show_list(&list); break; case 15: sort2(&list); show_list(&list); break; default: printf("输入的选择错误,请重新选择\n"); break; } } destroy(&list); }