动态顺序表
Capacity 指的是顺序表的容量，并不是实际存储的有效数据
size 当前顺序表的有效数据个数
头文件
SeqList.h
#ifndef __SEQLIST_H__ #define __SEQLIST_H__ #endif __SEQLIST_H__ #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> #pragma warning(disable:4996) #define MAX 100 #define DEFAULT_SZ 3 #define INC_SZ 2 typedef int DataType; typedef struct SeqList { size_t capacity;//容量 size_t size;//有效 DataType *array;//指向堆上的空间 }SeqLipst, *pSeqList; void InitSeqList(pSeqList p); void DestroySeqList(pSeqList p); void CheckCapacity(pSeqList p); void PushBack(pSeqList p, DataType d); void PopBack(pSeqList p); void PushFront(pSeqList p, DataType d); void PopFront(pSeqList p); void Show(pSeqList p); int Find(pSeqList p, DataType d); void Remove(pSeqList p, DataType d); void RemoveAll(pSeqList p, DataType d); int BinarySearch(pSeqList p, DataType d);//二分查找 void Sort(pSeqList p); 函数的实现SeqList.c
#include"SeqList.h" #pragma warning(disable:4996) void InitSeqList(pSeqList p) { p->array = (DataType* )malloc(DEFAULT_SZ* sizeof(DataType)*MAX); if (p->array == NULL) { perror("malloc"); return; } p->capacity = 0; p->size = 0; memset(p->array, 0, sizeof(DataType)*DEFAULT_SZ); } void DestroySeqList(pSeqList p) { assert(p != NULL); free(p->array); } void CheckCapacity(pSeqList p) { assert(p != NULL); DataType *tmp = NULL; if (p->capacity==p->size) { tmp = (DataType*)realloc(p->array, (p->capacity + INC_SZ)*sizeof(DataType)); if (tmp != NULL) { p->array = tmp; } } p->capacity += INC_SZ; } void PushBack(pSeqList p, DataType d) { CheckCapacity(p); p->array[p->size] = d; p->size++; } void PopBack(pSeqList p) { assert(p); if (p->size == 0) { printf("the seqlist is empty\n"); return; } p->size--; } void PushFront(pSeqList p, DataType d) { int i = 0; assert(p); CheckCapacity(p); if (p->size == 0) { p->array[0] = d; p->size++; } else { for (i = p->size; i > 0; i--) { p->array[i] = p->array[i - 1]; } p->array[0] = d; p->size++; } } void PopFront(pSeqList p) { size_t i = 0; assert(p); if (p->size == 0) { printf("the seqlist is empty\n"); return; } for (i = 0; i < p->size-1; i++) { p->array[i] = p->array[i + 1]; } p->size--; } int Find(pSeqList p, DataType d) { size_t i = 0; assert(p); for (i = 0; i < p->size; i++) { if (p->array[i]==d) { return i; } } return -1; } void Remove(pSeqList p, DataType d) { size_t pos = 0; size_t i = 0; assert(p); if (p->size == 0) { printf("the seqlist is empty\n"); return; } pos = Find(p, d); if (pos == -1) { printf("没有找到该数字\n"); return; } for (i = pos; i < p->size-1; i++) { p->array[i] = p->array[i + 1]; } p->size--; } void RemoveAll(pSeqList p, DataType d) { size_t i = 0; size_t pos = 0; assert(p); while (pos=Find(p,d)!=-1) { for (i = pos; i < p->size - 1; i++) { p->array[i] = p->array[i + 1]; } p->size--; } } int BinarySearch(pSeqList p, DataType d)//二分查找 { int i = 0; int left = 0; int right = p->size - 1; int mid = 0; assert(p); while (left <= right) { mid = left + (right - left) / 2; if (p->array[mid] > d) { right = mid - 1; } else if (p->array[mid] < d) { left = left + 1; } else return mid; } return -1; } void Sort(pSeqList p) { assert(p); if (p->size == 0) { printf("the seqlist is empty\n"); return; } for (size_t i = 0; i < p->size-1; i++) { for (size_t j = 0; j <p->size-1; j++) { if (p->array[j] < p->array[j + 1]) { DataType tmp = p->array[j]; p->array[j] = p->array[j + 1]; p->array[j + 1] = tmp; } } } } void Show(pSeqList p) { size_t i = 0; assert(p); if (p->size == 0) { printf("the seqlist is empty\n"); return; } for (i = 0; i < p->size; i++) { printf("%d", p->array[i]); } printf("\n"); }测试
text.c
#include"SeqList.h" #pragma warning(disable:4996) void menu() { printf("************************************\n"); printf(" 1.PushBack 2.PopBack \n"); printf(" 3.PushFront 4.PopFront\n"); printf(" 5.Show 6.Remove \n"); printf(" 7.RemoveAll 8.Sort \n"); printf(" 9.BinarySearch 10.Find \n"); printf(" 0.Exit \n"); printf("************************************\n"); } int main() { SeqLipst mylist; int input = 0; InitSeqList(&mylist); do { menu(); printf("请选择:>\n"); scanf("%d", &input); switch (input) { DataType data = 0; case 1: printf("请选择要插入的元素：>"); scanf("%d", &data); PushBack(&mylist, data); break; case 2: PopBack(&mylist); break; case 3: printf("请选择要插入的元素：>"); scanf("%d", &data); PushFront(&mylist, data); break; case 4: PopFront(&mylist); break; case 5: Show(&mylist); break; case 6: printf("请选择要删除的元素：>"); scanf("%d", &data); Remove(&mylist, data); break; case 7: printf("请选择要删除的元素：>"); scanf("%d", &data); RemoveAll(&mylist, data); break; case 8: Sort(&mylist); break; case 9: { int ret = 0; printf("请输入要查找的元素\n"); scanf("%d", &data); ret = BinarySearch(&mylist, data); if (ret = -1) { printf("查找的元素不存在\n"); } else { printf("元素的下标为%d\n", ret); } break; } case 10: { int ret2 = 0; printf("请输入要查找的元素\n"); scanf("%d", &data); ret2 = Find(&mylist, data); if (ret2 == -1) { printf("查找的元素不存在\n"); } else { printf("元素的下标为%d\n", ret2); } break; } case 0: break; default: printf("输入错误，请重新输入："); break; } }while(input); DestroySeqList(&mylist); system("puase\n"); return 0; }
