main.c文件
#define _CRT_SECURE_NO_WARNINGS #include"SeqList.h" int main() { SeqListTest(); system("pause"); return 0; }SeqList.h文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //动态顺序表 typedef int SLDataType; typedef struct SeqList { SLDataType * _a;//数组 size_t _size;//有多少数据 size_t capacity;//容量 }SeqList; void CheckCapacity(SeqList *psl); void SeqListInit(SeqList *psl,size_t capacity); void SeqListDestory(SeqList *psl); void SeqListPushBack(SeqList *psl, SLDataType x); void SeqListPopBack(SeqList *psl); void SeqListPushFront(SeqList *psl, SLDataType x); void SeqListPopFront(SeqList *psl); int SeqListFind(SeqList *psl, SLDataType x); void SeqListInsert(SeqList *psl, size_t pos, SLDataType x); void SeqListErase(SeqList *psl, size_t pos); void SeqListRemove(SeqList *psl, SLDataType x); void SeqListModify(SeqList *psl, size_t pos, SLDataType x); void SeqListPrint(SeqList *psl); void SeqListTest(); //面试题 void SeqListBubbleSort(SeqList *psl); int SeqListBinary(SeqList *psl, SLDataType x); void SeqListRemoverAll(SeqList *psl, SLDataType x);SeqList.c文件
#include"SeqList.h" void SeqListInit(SeqList *psl,size_t capacity) { assert(psl); if (capacity == 0) { psl->_a = NULL; psl->capacity = 0; psl->_size = 0; } else { psl->capacity = capacity; psl->_size = 0; psl->_a = (SLDataType *)malloc(sizeof(SLDataType)*capacity); assert(psl->_a); } } void SeqListDestory(SeqList *psl) { assert(psl); free(psl->_a); psl->capacity = 0; psl->_size = 0; psl->_a = NULL; } void CheckCapacity(SeqList *psl) { assert(psl); if (psl->_size == psl->capacity) { SLDataType *tmp; if (psl->capacity == 0) { psl->capacity = 2; } tmp = realloc(psl->_a, psl->capacity * 2 * sizeof(SLDataType)); assert(tmp); psl->_a = tmp; psl->capacity *= 2; } } void SeqListPushBack(SeqList *psl, SLDataType x) { assert(psl); /*CheckCapacity(psl); psl->_a[psl->_size] = x; psl->_size++;*/ SeqListInsert(psl, psl->_size, x); } void SeqListPopBack(SeqList *psl) { assert(psl); /*if (psl->_size > 0) { psl->_size--; }*/ SeqListErase(psl, psl->_size - 1); } void SeqListPushFront(SeqList *psl,SLDataType x) { assert(psl); /*CheckCapacity(psl); size_t i = psl->_size; for (i ; i > 0; i--) { psl->_a[i] = psl->_a[i - 1]; } psl->_a[0] = x; psl->_size++;*/ SeqListInsert(psl, 0, x); } void SeqListPopFront(SeqList *psl) { assert(psl); /*if (psl->_size > 0) { size_t i; for (i = 0; i < psl->_size - 1; i++) { psl->_a[i] = psl->_a[i + 1]; } psl->_size--; }*/ SeqListErase(psl, 0); } int SeqListFind(SeqList *psl, SLDataType x) { assert(psl); size_t i; for (i = 0; i < psl->_size; i++) { if (psl->_a[i] == x) { return i; } } return -1; } void SeqListInsert(SeqList *psl, size_t pos, SLDataType x) { assert(psl && pos<=psl->_size); CheckCapacity(psl); int i = psl->_size-1; while (i >= (int)pos) { psl->_a[i+1] = psl->_a[i]; --i; } psl->_a[pos] = x; psl->_size++; } void SeqListErase(SeqList *psl, size_t pos) { assert(psl && pos<psl->_size); int i = pos; while (i < (int)psl->_size-1) { psl->_a[i] = psl->_a[i + 1]; i++; } psl->_size--; } void SeqListRemove(SeqList *psl, SLDataType x) { assert(psl); int pos=SeqListFind(psl, x); if (pos != -1) { SeqListErase(psl, pos); } } void SeqListModify(SeqList *psl, size_t pos, SLDataType x) { assert(psl && pos<psl->_size); psl->_a[pos] = x; } void SeqListPrint(SeqList *psl) { assert(psl); size_t i; for (i = 0; i < psl->_size; i++) { printf("%d ", psl->_a[i]); } printf("\n"); } //void SeqListBubbleSort(SeqList *psl) //{ // assert(psl); // // int begin, end; // end = psl->_size; // while (end > 0) // { // int exchange = -1; // begin = 1; // while (begin<end) // { // if (psl->_a[begin-1] > psl->_a[begin]) // { // SLDataType tmp = psl->_a[begin-1]; // psl->_a[begin-1] = psl->_a[begin]; // psl->_a[begin] = tmp; // exchange = 1; // } // begin++; // } // if (exchange == -1) // { // break; // } // end--; // } //} void SeqListBubbleSort(SeqList *psl) { assert(psl); int i = 0; int j = 0; for (i = 0; i < (int)psl->_size-1; i++) { int exchange = 0; for (j = 0; j < (int)psl->_size - 1 - i; j++) { if (psl->_a[j]>psl->_a[j + 1]) { SLDataType tmp = psl->_a[j]; psl->_a[j] = psl->_a[j + 1]; psl->_a[j + 1] = tmp; exchange = 1; } } if (exchange == 0) break; } } //int SeqListBinary(SeqList *psl, SLDataType x) //{ // assert(psl); // // int left = psl->_size - 1; // int right = 0; // while (right <= left) // { // int mid = left + (right-left) / 2; // if (psl->_a[mid] > x) // { // left = mid - 1; // } // else if (psl->_a[mid] < x) // { // right = mid + 1; // } // else // { // return mid; // } // } // return -1; //} int SeqListBinary(SeqList *psl, SLDataType x) { assert(psl); int left = psl->_size; int right = 0; while (right <= left) { int mid = left + (right - left) / 2; if (psl->_a[mid] > x) { left = mid; } else if (psl->_a[mid] < x) { right = mid + 1; } else { return mid; } } return -1; } void SeqListRemoverAll(SeqList *psl, SLDataType x) { assert(psl); int start = 0; int index = 0; while (start < (int)psl->_size) { if (psl->_a[start] != x) { psl->_a[index]=psl->_a[start]; index++; start++; } else { start++; } } psl->_size = index; } void SeqListTest() { SeqList sl; SeqListInit(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 4); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPrint(&sl); SeqListRemoverAll(&sl, 2); SeqListPrint(&sl); }