C语言实现的顺序表功能完整实例

本文实例讲述了C语言实现的顺序表功能。分享给大家供大家参考,具体如下:

seqlist.h

#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__

seqlist.cpp

#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);

}

main.cpp

#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("查找的数据元素在顺序表中的下标位置为%d\n", pos);

break;

case 8:

printf("顺序表的长度为%d\n", 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);

}

希望本文所述对大家C语言程序设计有所帮助。

以上是 C语言实现的顺序表功能完整实例 的全部内容, 来源链接: utcz.com/z/346484.html

回到顶部