c 语言 动态顺序表

来源:转载

#ifndef __SEQLIST_D__//头文件#define __SEQLIST_D__#define CAPICITY 4 typedef int DataType; typedef struct SeqList_D{ DataType* _Array; size_t _size; size_t _capicity;}SeqL,*pSeqL; void InitSeqList(pSeqL seq);void PrintfSeqList(pSeqL seq);void PushBack(pSeqL seq,DataType x);void PopBack(pSeqL seq);void BubbleSort(pSeqL seq);void SelectSort(pSeqL seq);int BinarySearch(pSeqL seq, DataType x);void AddCapicity(pSeqL* seq); #endif #include<stdio.h>//函数文件#include<assert.h>#include"SeqList_D.h"#include<malloc.h> void InitSeqList(pSeqL seq){ assert(seq); seq->_Array = (DataType*)malloc(sizeof(DataType)*CAPICITY); seq->_size = 0; seq->_capicity = CAPICITY;} void PrintfSeqList(pSeqL seq){ size_t index = 0; assert(seq); if (seq->_size == 0) printf("顺序表已空!/n"); for (; index < seq->_size; ++index) { printf("%d ",seq->_Array[index]); } printf("/n");}//尾插void PushBack(pSeqL seq, DataType x){ assert(seq); AddCapicity(&seq); seq->_Array[(seq->_size)++] = x;}//尾删void PopBack(pSeqL seq){ assert(seq); if (seq->_size == 0) printf("顺序表为空!/n"); else --seq->_size;}//冒泡排序__升序void BubbleSort(pSeqL seq){ size_t i=0,j=0;//循环变量 assert(seq); for (; i < seq->_size; ++i) { int count = 0;//计数器 for (j=0; j < seq->_size - 1 - i; ++j) { if (seq->_Array[j]>seq->_Array[j + 1]) { DataType tmp = seq->_Array[j]; seq->_Array[j] = seq->_Array[j + 1]; seq->_Array[j + 1] = tmp; ++count; } } if (count <= 1) return; }} //选择排序__降序void SelectSort(pSeqL seq){ size_t i = 0, j = 0,min=0,max=seq->_size-1;//循环变量 for (; i < seq->_size - 1; ++i) { for (j = i + 1; j < seq->_size-i; ++j) { if (seq->_Array[min] < seq->_Array[max])//交换头 尾 { DataType tmp = seq->_Array[min]; seq->_Array[min] = seq->_Array[max]; seq->_Array[max] = tmp; } if (seq->_Array[min] < seq->_Array[j])//交换头 中 { DataType tmp = seq->_Array[min]; seq->_Array[min] = seq->_Array[j]; seq->_Array[j] = tmp; } if (seq->_Array[j] < seq->_Array[max])//交换中 尾 { DataType tmp = seq->_Array[max]; seq->_Array[max] = seq->_Array[j]; seq->_Array[j] = tmp; } PrintfSeqList(seq); } max--; min++; if (max <= min) break; }} //二分查找int BinarySearch(pSeqL seq, DataType x){ size_t lift = 0, right = seq->_size - 1; while (lift < right) { if (seq->_Array[(lift + right) / 2] > x) lift= (lift + right) / 2+1; if (seq->_Array[(lift + right) / 2] < x) right = (lift + right) / 2; if (seq->_Array[(lift + right) / 2] == x) return (lift + right) / 2; } return -1;} //增容void AddCapicity(pSeqL* seq){ assert(seq); assert(*seq); if ((*seq)->_capicity == (*seq)->_size) { (*seq)->_Array =realloc((*seq)->_Array,sizeof(DataType)*((*seq)->_capicity)*2);//用realloc函数增加容量 (*seq)->_capicity *= 2; size_t index = 0; }} #include<stdio.h>//主函数 测试函数#include"SeqList_D.h" void test1(){ SeqL seq ; InitSeqList(&seq); PushBack(&seq, 1); PushBack( &seq, 4); PushBack( &seq, 3); PushBack( &seq, 2); PrintfSeqList(&seq); PushBack( &seq, 5); PrintfSeqList(&seq); PopBack( &seq); PopBack( &seq); PopBack( &seq); PopBack( &seq); PopBack(&seq); PopBack( &seq); PrintfSeqList(&seq); } void test2(){ SeqL seq; InitSeqList(&seq); PushBack(&seq, 1); PushBack(&seq, 4); PushBack(&seq, 3); PushBack(&seq, 2); PushBack(&seq, 9); PushBack(&seq, 6); PushBack(&seq, 7); PushBack(&seq, 5); PrintfSeqList(&seq); PrintfSeqList(&seq); BubbleSort(&seq); PrintfSeqList(&seq); SelectSort(&seq); PrintfSeqList(&seq); printf("%d/n",BinarySearch(&seq, 2));} int main(){ test2(); return 0;}

 


分享给朋友:
您可能感兴趣的文章:
随机阅读: