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;
}