线性表之顺序表
存储在连续的内存空间,和数组一样。
下面的代码,最开始定义了一个能存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;
}
vo