#ifndef __SEQLIST_H__#define __SEQLIST_H__#include<cstdio>#include<malloc.h>#include<assert.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 push_front(Seqlist *list, ElemType x);
//在顺序表的头部插入元素void show_list(Seqlist *list);
//显示顺序表中的元素void pop_back(Seqlist *list);
//删除顺序表最后一个元素void pop_front(Seqlist *list);
//删除顺序表第一个元素void insert_pos(Seqlist *list, int pos, ElemType x);
//在顺序表的选定位置上插入数据int find(Seqlist *list, ElemType key);
//在顺序表中查找元素key的下标int length(Seqlist *list);
//求顺序表的长度void delete_pos(Seqlist *list, int pos);
//删除顺序表中特定位置的数据元素void delete_val(Seqlist *list, int key);
//删除顺序表中值为key的数据元素void sort(Seqlist *list);
//冒泡排序void reverse(Seqlist *list);
//逆置顺序列表void clear(Seqlist *list);
//清除顺序表中的所有元素void destroy(Seqlist *list);
//摧毁顺序表void merge(Seqlist *lt, Seqlist *la, Seqlist *lb);
//合并两个顺序列表#endif //__SEQLIST_H__

#include"seqlist.h"bool Inc(Seqlist *list) {
ElemType *newbase = (ElemType*)realloc(list, sizeof(ElemType)*(list->capacity + INC_SIZE));
//重新分配内存空间 if (newbase == NULL) {
printf("内存空间已满，无法再分配内存空间！n");
return false;
}
list->base = newbase;
list->capacity += INC_SIZE;
return true;
}
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)) {
//Inc(list)用来判断增加顺序表容量是否成功,只有在失败的情况下才会进入if语句中 printf("顺序表容量已满，无法再在表尾继续插入新元素！n");
return;
}
list->base[list->size] = x;
list->size++;
}
void push_front(Seqlist *list, ElemType x) {
if (list->size >= list->capacity && !Inc(list)) {
printf("顺序表容量已满，无法再在表头插入新元素！n");
return;
}
for (int i = list->size;
i > 0;
i--) {
list->base[i] = list->base[i - 1];
}
list->base[0] = x;
list->size++;
}
void show_list(Seqlist *list) {
for (int i = 0;
i < list->size;
i++) {
printf("%d ", list->base[i]);
}
printf("n");
}
void pop_back(Seqlist *list) {
if (list->size == 0) {
printf("顺序表已空，无法再在表尾删除元素！n");
return;
}
list->size--;
}
void pop_front(Seqlist *list) {
if (list->size == 0) {
printf("顺序表已空，无法再在表头删除元素！n");
return;
}
for (int i = 0;
i < list->size - 1;
i++) {
list->base[i] = list->base[i + 1];
}
list->size--;
}
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("顺序表容量已满，无法在插入新的元素！n");
return;
}
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 key) {
for (int i = 0;
i < list->size;
i++) {
if (list->base[i] == key) 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, int key) {
int pos = find(list, key);
if (pos == -1) {
printf("顺序表中没有这个元素！n");
return;
}
delete_pos(list, pos);
}
void sort(Seqlist *list) {
for (int i = 0;
i < list->size - 1;
i++) {
//排序的趟数（例如5个数据需要比较4趟） for (int j = 0;
j < list->size - 1 - i;
j++) {
//每一趟比较中的比较次数（例如5个数据在第0趟需要比较4次） if (list->base[j] > list->base[j + 1]) {
ElemType temp = list->base[j];
list->base[j] = list->base[j + 1];
list->base[j + 1] = temp;
}
}
}
}
void reverse(Seqlist *list) {
if (list->size == 0 || list->size == 1) return;
int low = 0, high = list->size - 1;
while (low < high) {
ElemType temp = list->base[low];
list->base[low] = list->base[high];
list->base[high] = temp;
low++;
high--;
}
}
void clear(Seqlist *list) {
list->size = 0;
}
void destroy(Seqlist *list) {
free(list->base);
list->base = NULL;
list->capacity = 0;
list->size = 0;
}
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, ib = 0, 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++] = lb->base[ib++];
}
}
while (ia < la->size) {
lt->base[ic++] = la->base[ia++];
}
while (ib < lb->size) {
lt->base[ic++] = lb->base[ib++];
}
lt->size = la->size + lb->size;
show_list(lt);
}

#include"seqlist.h"void main() {
Seqlist list;
InitSeqlist(&list);
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] length *n");
printf("*[9] delete_pos [10] delete_value *n");
printf("*[11] sort [12] reverse *n");
printf("*[13] clear [14] merge *n");
printf("*[0] quit_system *n");
printf("*******************************************n");
printf("请选择：>>");
scanf("%d", &select);
if (select == 0) break;
switch (select) {
case 1: printf("请输入要插入的数据（-1结束）:>");
while (scanf("%d", &item), item != -1) {
//先输入item的值，只要item不等于-1就接着循环 push_back(&list, item);
}
break;
case 2: printf("请输入要插入的数据（-1结束）:>");
while (scanf("%d", &item), item != -1) {
push_front(&list, item);
}
break;
case 3: show_list(&list);
break;
case 4: pop_back(&list);
break;
case 5: pop_front(&list);
break;
case 6: printf("请输入要插入的数据:>");
scanf("%d", &item);
printf("请输入要插入的位置:>");
scanf("%d", &pos);
insert_pos(&list, pos, item);
break;
case 7: printf("请输入要查找的数据:>");
scanf("%d", &item);
pos = find(&list, item);
if (pos == -1) printf("查找的数据元素不在顺序表中！n");
else printf("查找的数据元素在顺序表中的下标位置为%dn", pos);
break;
case 8: printf("顺序表的长度为%dn", length(&list));
break;
case 9: printf("请输入要删除数据在顺序表中的下标位置:>");
scanf("%d", &pos);
delete_pos(&list, pos);
break;
case 10: printf("请输入要删除数据的值:>");
scanf("%d", &item);
delete_val(&list, item);
break;
case 11: sort(&list);
break;
case 12: reverse(&list);
break;
case 13: clear(&list);
break;
case 14: Seqlist mylist, yourlist;
ElemType item1, item2;
InitSeqlist(&mylist);
InitSeqlist(&yourlist);
printf("请输入顺序表1中的元素值（-1结束）:>");
while (scanf("%d", &item1), item1 != -1) {
push_back(&mylist, item1);
}
printf("请输入顺序表2中的元素值（-1结束）:>");
while (scanf("%d", &item2), item2 != -1) {
push_back(&yourlist, item2);
}
merge(&list, &mylist, &yourlist);
destroy(&mylist);
destroy(&yourlist);
break;
default: printf("输入的选择错误！请重新输入！n");
break;
}
}
destroy(&list);
}