//SeqList.h#ifndef __SEQLIST_H__#define __SEQLIST_H__#include#include #include typedef int DataType;typedef struct SeqList{ DataType* array; size_t size; DataType capacity; //容量}SeqList,*pSeqList;void InitSeqList(pSeqList pSeq);void PushBack(pSeqList pSeq,DataType x);void PrintSeqList(pSeqList pSeq);void PopBack(pSeqList pSeq);void PushFront(pSeqList pSeq, DataType x);void PopFront(pSeqList pSeq);void Insert(pSeqList pSeq, int pos, DataType x);void Remove(pSeqList pSeq, DataType x);void RemoveAll(pSeqList pSeq, DataType x);int Find(pSeqList pSeq,DataType x);void Erase(pSeqList pSeq,DataType pos);void ReverseList(pSeqList pSeq);void SortList(pSeqList pSeq);void SelectSortList(pSeqList pSeq);int BinarySearch(pSeqList Seq, DataType x);void CheckCapacity(pSeqList pSeq) //检查容量{ if(pSeq->size >= pSeq->capacity) { pSeq->capacity = pSeq->capacity*2+3; pSeq->array = (DataType*)realloc(pSeq->array,pSeq->capacity*sizeof(DataType)); // DataType *tmp = (DataType *)malloc(sizeof(DataType)*pSeq->capacity*2); // memcpy(tmp,pSeq->array,sizeof(DataType)*pSeq->size); // free(pSeq->array); // pSeq->array = tmp; }}void InitSeqList(pSeqList pSeq) //初始化顺序表{ assert(pSeq);// pSeq->array = (DataType*)malloc(sizeof(DataType)*3);// pSeq->size = 0;// pSeq->capacity = 3; pSeq->array = NULL; pSeq->size = 0; pSeq->capacity = 0;}void PushBack(pSeqList pSeq,DataType x) //尾插{ assert(pSeq); CheckCapacity(pSeq); pSeq->array[pSeq->size++] = x;}void PopBack(pSeqList pSeq) //尾删{ assert(pSeq); if(pSeq->size <= 0) { printf("SeqList is empty"); return; } pSeq->array[pSeq->size-1] = NULL; pSeq->size--;}void PushFront(pSeqList pSeq, DataType x) //头插{ int i = 0; assert(pSeq); CheckCapacity(pSeq); for(i = pSeq->size-1; i >= 0; i--) { pSeq->array[i+1] = pSeq->array[i]; } pSeq->array[0] = x; pSeq->size++;}void PopFront(pSeqList pSeq) //头删{ int i = 0; assert(pSeq); if(pSeq->size <= 0) { printf("SeqList is empty"); return; } for(i = 1; i < pSeq->size; i++) { pSeq->array[i-1] = pSeq->array[i]; } pSeq->size--;}void Destroy(pSeqList pSeq) //销毁{ assert(pSeq); pSeq->array = NULL; pSeq->size = 0; pSeq->capacity = 0;}void PrintSeqList(pSeqList pSeq) //打印{ int i = 0; assert(pSeq); for(i = 0; i < pSeq->size;i++) { printf("%d ",pSeq->array[i]); }}void Insert(pSeqList pSeq, int pos, DataType x) //在某个位置处插入{ int i = 0; assert(pSeq); CheckCapacity(pSeq); for(i = pSeq->size-1; i >= pos; i--) { pSeq->array[i+1] = pSeq->array[i]; } pSeq->array[pos] = x; pSeq->size++;}int Find(pSeqList pSeq,DataType x) //查找{ int i = 0; assert(pSeq); if(pSeq->size <= 0) { printf("SeqList is empty"); return -1; } for(i = 0; i < pSeq->size; i++) { if(pSeq->array[i] == x) { return i; } } return -1;}void Erase(pSeqList pSeq,DataType pos) //按位置删除{ int i = 0; assert(pSeq); if(pSeq->size <= 0) { printf("SeqList is empty"); return; } for(i = pos+1; i < pSeq->size; i++) { pSeq->array[i-1] = pSeq->array[i]; } pSeq->size--;}void Remove(pSeqList pSeq, DataType x) //删除{ int pos = Find(pSeq,x); assert(pSeq); if(pos != -1) { Erase(pSeq,pos); } else { printf("not exist"); }}void RemoveAll(pSeqList pSeq, DataType x) //删除所有的x{ int count = 0; int i = 0; assert(pSeq); if(pSeq->size <= 0) { printf("SeqList is empty"); return; } for(i = 0; i < pSeq->size; i++) { if(pSeq->array[i] == x) { count++; } else { pSeq->array[i-count] = pSeq->array[i]; } } pSeq->size-=count;}void ReverseList(pSeqList pSeq) // 逆置{ int left = 0; int right = pSeq->size-1; assert(pSeq); while(left < right) { int tmp = pSeq->array[left]; pSeq->array[left] = pSeq->array[right]; pSeq->array[right] = tmp; left++; right--; }}void SortList(pSeqList pSeq) //冒泡排序{ int i = 0, j = 0; assert(pSeq); for(i = 0; i < pSeq->size-1; i++) { int exchange = 0; for(j = 0; j < pSeq->size-i-1; j++) { if(pSeq->array[j] > pSeq->array[j+1]) { int tmp = pSeq->array[j]; pSeq->array[j] = pSeq->array[j+1]; pSeq->array[j+1] = tmp; exchange = 1; } } if(exchange == 0) { return; } }}void SelectSortList(pSeqList pSeq) //选择排序{ int i = 0, j = 0; int min = 0; int tmp; assert(pSeq); for(i = 0; i < pSeq->size-1; i++) { min = i; for(j = i+1; j < pSeq->size; j++) { if(pSeq->array[min] > pSeq->array[j]) { min = j; } tmp = pSeq->array[min]; pSeq->array[min] = pSeq->array[i]; pSeq->array[i] = tmp; } }}int BinarySearch(pSeqList pSeq, DataType x) //二分查找{ int left = 0; int right = pSeq->size-1; assert(pSeq); while(left <= right) { int mid = left - (left - right)/2; if(pSeq->array[mid] > x) { right = mid-1; } else if(pSeq->array[mid] < x) { left = mid+1; } else { return mid; } } return -1;}#endif // __SEQLIST_H__//SeqList.c#include #include"SeqList.h"void Test1(){ SeqList seq; InitSeqList(&seq); PushBack(&seq,1); PushBack(&seq,2); PushBack(&seq,3); PushBack(&seq,4); PopBack(&seq); PrintSeqList(&seq); Destroy(&seq);}void Test2(){ SeqList seq; int ret; InitSeqList(&seq); PushBack(&seq,1); PushBack(&seq,2); PushBack(&seq,3); PushBack(&seq,4); PushFront(&seq,0); PopFront(&seq); Insert(&seq,2,6); ret = Find(&seq,6); printf("%d\n",ret); PrintSeqList(&seq);}void Test3(){ SeqList seq; InitSeqList(&seq); PushBack(&seq,1); PushBack(&seq,2); PushBack(&seq,3); PushBack(&seq,4); PushBack(&seq,4); PushBack(&seq,2); PushBack(&seq,5); PushBack(&seq,6); PopBack(&seq); Erase(&seq,2); Remove(&seq,2); RemoveAll(&seq,4); PrintSeqList(&seq);}void Test4(){ SeqList seq; int pos; InitSeqList(&seq); PushBack(&seq,1); PushBack(&seq,2); PushBack(&seq,3); PushBack(&seq,4); PushBack(&seq,4); PushBack(&seq,5); ReverseList(&seq); SortList(&seq); pos = BinarySearch(&seq,2); printf("%d\n",pos); PrintSeqList(&seq);}void Test5(){ SeqList seq; int pos; InitSeqList(&seq); PushBack(&seq,1); PushBack(&seq,2); PushBack(&seq,3); PushBack(&seq,4); PushBack(&seq,4); PushBack(&seq,5); ReverseList(&seq);// SelectSortList(&seq);// Select_SortList(&seq); pos = BinarySearch(&seq,2); printf("%d\n",pos); PrintSeqList(&seq);}int main(){ //Test1(); //Test2(); //Test3(); //Test4(); Test5(); return 0;}