C语言 顺序表的实现 (动态)
程序员文章站
2022-05-16 10:15:50
给出顺序表的定义:
typedef int datatype;
typedef struct seqlistd {
datatype *array;
int size;// 记录有效元...
给出顺序表的定义:
typedef int datatype; typedef struct seqlistd { datatype *array; int size;// 记录有效元素的个数 int capacity;// 空间总大小 }seqlistd, *pseqlistd;
将函数的声明放在head.h的头文件里面:
#ifndef _head_h_ #define _head_h_ #define init_size 10 #define increment 5 typedef int datatype; typedef struct seqlistd { datatype *array; int size;// 记录有效元素的个数 int capacity;// 空间总大小 }seqlistd, *pseqlistd; void checkcapacity(pseqlistd pseqlist);//检查当前线性表的容量,不够的话申请内存 void initseqlist(pseqlistd pseqlist);//线性表初始化 void pushback(pseqlistd pseqlist, datatype data);//在线性表后面插入元素 void popback(pseqlistd pseqlist);//在线性表后面删除元素 void pushfront(pseqlistd pseqlist, datatype data);//在线性表前面插入元素 void popfront(pseqlistd pseqlist);//在线性表前面删除元素 void insert(pseqlistd pseqlist, int pos, datatype data);//在线性表指定位置插入元素 void erase(pseqlistd pseqlist, int pos);//在线性表指定位置删除元素 int find(pseqlistd pseqlist, datatype data);//在线性表查找元素,返回下标 void remove(pseqlistd pseqlist, datatype data);//在线性表删除值为data的元素 void removeall(pseqlistd pseqlist, datatype data);//在线性表删除所有值为data的元素 int empty(pseqlistd pseqlist);//判别线性表是否为空 void printseqlist(pseqlistd pseqlist);//打印线性表 void bubblesort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2));//冒泡排序,升序和降序两种版本,用了函数指针以及回调函数 void selectsort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2));//选择排序,升序和降序两种版本,用了函数指针以及回调函数 int cmpinascendingorder(const void *elem1, const void *elem2);//升序比较 int cmpindescendingorder(const void *elem1, const void *elem2);//降序比较 void swap(datatype *a, datatype *b);//交换 int binarysearch(pseqlistd pseqlist, datatype data);//二分查找 int binarysearchrecursion(pseqlistd pseqlist, int left, int right, datatype data);//二分查找的递归版本 int size(pseqlistd pseqlist);//求线性表的大小 void clear(pseqlistd pseqlist);//清空线性表 void destroyseqlist(pseqlistd pseqlist);//销毁线性表 #endif
具体的实现
test()函数为测试代码,只写出了其中的一部分
#include #include #include #include "head.h" void test0(); void test1(); void test2(); void test3(); int main() { //test0(); //test1(); //test2(); test3(); getchar(); return 0; } void test0() { seqlistd seqlist; pseqlistd p = &seqlist; initseqlist(p); pushback(p, 1); pushback(p, 2); pushback(p, 3); printseqlist(p); popback(p); popback(p); printseqlist(p); } void test1() { seqlistd seqlist; pseqlistd p = &seqlist; initseqlist(p); pushback(p, 1); pushback(p, 2); pushback(p, 3); pushback(p, 5); printseqlist(p); insert(p, 4, 4); erase(p, 1); printseqlist(p); } void test2() { seqlistd seqlist; pseqlistd p = &seqlist; initseqlist(p); pushback(p, 1); pushback(p, 6); pushback(p, 3); pushback(p, 4); pushback(p, 2); pushback(p, 5); printseqlist(p); //bubblesort(p, cmpinascendingorder); //selectsort(p, cmpinascendingorder); printseqlist(p); //bubblesort(p, cmpindescendingorder); //selectsort(p, cmpindescendingorder); //int pos = binarysearch(p, 20) + 1; //printf("%d\n", pos); } void test3() { seqlistd seqlist; pseqlistd p = &seqlist; initseqlist(p); pushback(p, 1); pushback(p, 2); pushback(p, 3); pushback(p, 5); pushback(p, 2); pushback(p, 2); pushback(p, 4); printseqlist(p); removeall(p, 2); printseqlist(p); } void checkcapacity(pseqlistd pseqlist) { assert(pseqlist); if (pseqlist->size >= pseqlist->capacity) { datatype *p = (datatype *)realloc(pseqlist->array, (init_size + increment) * sizeof(datatype)); if (!p) exit(exit_failure); pseqlist->array = p; pseqlist->capacity += increment; } } void initseqlist(pseqlistd pseqlist) { assert(pseqlist); pseqlist->array = (datatype *)malloc(init_size * sizeof(datatype)); if (!(pseqlist->array)) { exit(exit_failure); } pseqlist->size = 0; pseqlist->capacity = init_size; } void pushback(pseqlistd pseqlist, datatype data) { assert(pseqlist); checkcapacity(pseqlist); pseqlist->array[pseqlist->size++] = data; } void popback(pseqlistd pseqlist) { assert(pseqlist); pseqlist->size--; } void pushfront(pseqlistd pseqlist, datatype data) { assert(pseqlist); checkcapacity(pseqlist); for (int i = pseqlist->size; i > 0; --i) { pseqlist[i] = pseqlist[i - 1]; } pseqlist->array[0] = data; pseqlist->size++; } void popfront(pseqlistd pseqlist) { assert(pseqlist); pseqlist->size--; for (int i = 0; i < pseqlist->size; i++) { pseqlist->array[i] = pseqlist->array[i + 1]; } } void printseqlist(pseqlistd pseqlist) { assert(pseqlist); printf("the elements in the seqlist:"); for (int i = 0; i < pseqlist->size; ++i) { printf("%d ", pseqlist->array[i]); } printf("\n"); } void insert(pseqlistd pseqlist, int pos, datatype data) { assert(pseqlist); checkcapacity(pseqlist); if (1 <= pos <= pseqlist->size) { int truepos = pos - 1; for (int i = pseqlist->size; i > truepos; --i) { pseqlist->array[i] = pseqlist->array[i - 1]; } pseqlist->array[truepos] = data; pseqlist->size++; } else { printf("the pos is wrong\n"); } } void erase(pseqlistd pseqlist, int pos) { assert(pseqlist); if (1 <= pos <= pseqlist->size) { int truepos = pos - 1; pseqlist->size--; for (int i = truepos; i < pseqlist->size; ++i) { pseqlist->array[i] = pseqlist->array[i + 1]; } } else { printf("the pos is wrong\n"); } } int find(pseqlistd pseqlist, datatype data) { assert(pseqlist); for (int i = 0; i < pseqlist->size; ++i) { if (pseqlist->array[i] == data) return i + 1; } return 0; } void remove(pseqlistd pseqlist, datatype data) { assert(pseqlist); int pos = find(pseqlist, data); if (pos != 0) { erase(pseqlist, pos); } } void removeall(pseqlistd pseqlist, datatype data) { assert(pseqlist); int count = 0; for (int i = 0; i < pseqlist->size; ++i) { if (pseqlist->array[i] == data) count++; else pseqlist->array[i - count] = pseqlist->array[i]; } pseqlist->size -= count; //while (count--) { // remove(pseqlist, data); //} } int empty(pseqlistd pseqlist) { return pseqlist->size == 0; } void swap(datatype *a, datatype *b) { datatype tmp = *a; *a = *b; *b = tmp; } int cmpinascendingorder(const void *elem1, const void *elem2) { return *(int *)elem1 - *(int *)elem2; } int cmpindescendingorder(const void *elem1, const void *elem2) { return *(int *)elem2 - *(int *)elem1; } void bubblesort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2)) { assert(pseqlist); int i = 0; int j = 0; for (i = 0; i < pseqlist->size - 1; ++i) { for (j = 0; j < pseqlist->size - 1 - i; ++j) { if (cmp(&pseqlist->array[j], &pseqlist->array[j + 1]) > 0) swap(&pseqlist->array[j], &pseqlist->array[j + 1]); } } } void selectsort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2)) { assert(pseqlist); int pos = 0; int i = 0; int j = 0; for (i = 0; i < pseqlist->size - 1; ++i) { pos = i; for (j = i + 1; j < pseqlist->size; ++j) { if (cmp(&pseqlist->array[j], &pseqlist->array[pos]) > 0) { pos = j; } } if (pos != i) { swap(&pseqlist->array[i], &pseqlist->array[pos]); } } } int binarysearch(pseqlistd pseqlist, datatype data) { int left = 0; int right = pseqlist->size - 1; while (left <= right) { int mid = left + ((right - left) >> 1); if (pseqlist->array[mid] < data) left = mid + 1; else if (pseqlist->array[mid] > data) right = mid - 1; else return mid; } return -1; } int binarysearchrecursion(pseqlistd pseqlist, int left, int right, datatype data) { if (left <= right) { int mid = left + (right - left) / 2; if (data > pseqlist->array[mid]) return binarysearchrecursion(pseqlist, mid + 1, right, data); else if (data < pseqlist->array[mid]) return binarysearchrecursion(pseqlist, left, mid - 1, data); else return mid; } else return -1; } int size(pseqlistd pseqlist) { return pseqlist->size; } void clear(pseqlistd pseqlist) { for (int i = 0; i < pseqlist->size; ++i) { pseqlist->array[i] = 0; } } void destroyseqlist(pseqlistd pseqlist) { free(pseqlist->array); pseqlist->capacity = 0; pseqlist->size = 0; }