线性表

typedef struct list
{
    int *arr;//申请堆内存，存放数据
    int len;//表中元素个数
    int size;//表中大小
}LIST;
LIST mylist;

void Init(LIST *p)//初始化
{
    p->len = 0;
    p->size = 0;
    p->arr = (int *)malloc(sizeof(int)*p->size);
}

void addDate(LIST*p, int date)//插入数据
{
    if (p->len >= p->size)
    {
        //内存不够 重新申请内存 
        p->size += (p->size >> 1) > 1 ? p->size >> 1 : 1;
        if (p->arr == NULL)
            p->arr = (int*)malloc(sizeof(int)*p->size);
        else
            p->arr = (int *)realloc(p->arr, sizeof(int)*p->size);
    }
    //开始插入
    //p->arr[p->len] = date;//date插入到末尾
    //p->len++;

    //插入排序
    int i;
    for (i = p->len - 1; data < p->arr[i] && i >= 0; i--)
    {
        p->arr[i + 1] = p->arr[i];
    }
    p->arr[i + 1] = data;
    p->len++;
}

void deleDate(LIST*p, int date)
{
#if 0
    //遍历顺序表中的每一个元素，查找要删除的额元素
    for (int i = 0; i < p->len; i++)
    {
        if (p->arr[i] == date)
        {
            for (int j = i; j < p->len-1; j++)
            {
                p->arr[j] = p->arr[j + 1];
            }
            p->len--;//删除一个元素，长度减一
            i--;
        }
    }
#else
    //删除多个中的一个
    for (int i = 0; i < p->len; i++)
    {
        if (p->arr[i] == date)
        {
            printf("%d\t%d\n", i+1,p->arr[i]);
        }
    }
    printf("输入你想要删除的一个元素的序号：");
    int x;
    scanf("%d", &x);
    for (int j = x - 1; j < p->len - 1; j++)
    {
        p->arr[j] = p->arr[j + 1];
    }
    p->len--;
#endif
}

void findDate(LIST*p, int date)
{
#if FLAG    //FLAG为真代表无序插入，无序查找
    for (int i = 0; i < p->len; i++)
    {
        if (p->arr[i] == date)
        {
            printf("%d\t%d\n", i + 1, p->arr[i]);
        }
    }
#else
    //二分查找 有序
    int left = 0, right = p->len - 1;
    int mid = (left + right) / 2;
    while (left <= right)
    {
        //数据有序  从小到大
        if (p->arr[mid] > date)
        {
            right = mid - 1;
            mid = (left + right) / 2;
        }
        else if (p->arr[mid] < date)
        {
            left = mid + 1;
            mid = (left + right) / 2;
        }
        else
            break;
    }
    printf("%d\t%d\n", mid + 1, p->arr[mid]);
#endif
}

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<windows.h>
#define FLAG 1    //真：无序插入 假：有序插入

typedef struct list
{
    int *arr;   //申请堆内存，存放数据
    int len;    //表中元素个数
    int size;   //表中大小
}LIST;
LIST mylist;
void Init(LIST *p)//初始化
{
    p->len = 0;
    p->size = 0;
    p->arr = (int *)malloc(sizeof(int)*p->size);
}
void menu()
{
    printf("1.添加数据.\n");
    printf("2.删除数据.\n");
    printf("3.查找数据.\n");
    printf("4.插入数据.\n");
    printf("5.显示数据.\n");
}
void addDate(LIST*p, int data)//插入数据
{
    if (p->len >= p->size)
    {
        //内存不够 重新申请内存 
        p->size += (p->size >> 1) > 1 ? p->size >> 1 : 1;
        if (p->arr == NULL)
            p->arr = (int*)malloc(sizeof(int)*p->size);
        else
            p->arr = (int *)realloc(p->arr, sizeof(int)*p->size);
    }
    //开始插入
#if FLAG
    p->arr[p->len] = data;//date插入到末尾
    p->len++;
#else
    //插入排序   1 3 5 7  4
    int i;
    for (i = p->len - 1; data < p->arr[i] && i >= 0; i--)
    {
        p->arr[i + 1] = p->arr[i];
    }
    p->arr[i + 1] = data;
    p->len++;
#endif
}
void deleDate(LIST*p, int date)
{
#if 0
    for (int i = 0; i < p->len; i++)
    {
        if (p->arr[i] == date)
        {
            for (int j = i; j < p->len - 1; j++)
            {
                p->arr[j] = p->arr[j + 1];
            }
            p->len--;//删除一个元素，长度减一
            i--;
        }
    }
    //删除多个中的一个
#else
    //删除多个中的一个
    for (int i = 0; i < p->len; i++)
    {
        if (p->arr[i] == date)
        {
            printf("%d\t%d\n", i + 1, p->arr[i]);
        }
    }
    printf("输入你想要删除的一个元素的序号：");
    int x;
    scanf("%d", &x);
    for (int j = x - 1; j < p->len - 1; j++)
    {
        p->arr[j] = p->arr[j + 1];
    }
    p->len--;
#endif
}
void findDate(LIST*p, int date)
{
#if FLAG
    for (int i = 0; i < p->len; i++)
    {
        if (p->arr[i] == date)
        {
            printf("%d\t%d\n", i + 1, p->arr[i]);
        }
    }
#else
    //二分查找 有序
    int left = 0, right = p->len - 1;
    int mid = (left + right) / 2;
    while (left <= right)
    {
        //数据有序  从小到大
        if (p->arr[mid] > date)
        {
            right = mid - 1;
            mid = (left + right) / 2;
        }
        else if (p->arr[mid] < date)
        {
            left = mid + 1;
            mid = (left + right) / 2;
        }
        else
            break;
    }
    printf("%d\t%d\n", mid + 1, p->arr[mid]);
#endif
}
int FindData(LIST*p, int left, int right, int data)
{
    //递归查找
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (p->arr[mid] > data) return FindData(p, left, mid - 1, data);
    else if (p->arr[mid] > data) return FindData(p, mid + 1, right, data);
    else return mid;
}
void show(LIST*p)
{
    printf("顺序表:\n");
    for (int i = 0; i < p->len; i++)
    {
        printf("%d\t%d", i + 1, p->arr[i]);
    }
    printf("\n");
}
void insertDate(LIST*p, int date)
{
    int x;
    show(p);
    printf("请输入插入位置：");
    scanf("%d", &x);

    if (p->len >= p->size)
    {
        //内存不够 重新申请内存 
        p->size += (p->size >> 1) > 1 ? p->size >> 1 : 1;   //分配比原先大1/2的空间
        if (p->arr == NULL)
            p->arr = (int*)malloc(sizeof(int)*p->size);
        else
            p->arr = (int *)realloc(p->arr, sizeof(int)*p->size);
    }

    int j;
    for (j = p->len - 1; j >= x - 1; j--)
    {
        p->arr[j + 1] = p->arr[j];
    }
    p->arr[j + 1] = date;
    p->len++;

}
void FreeList(LIST *p)
{
    if (p->arr != NULL)
    {
        free(p->arr);
        p->arr = NULL;
    }
}
int main()
{
    int x;
    char ch;
    Init(&mylist);
    while (1)
    {
        menu();
        ch = getch();
        if (ch == '0')break;
        switch (ch)
        {
        case'1':
            printf("请输入要添加的数字：");
            scanf("%d", &x);
            addDate(&mylist, x);
            printf("按任意键继续.\n");
            ch = getch();
            system("cls");
            break;
        case'2':
            printf("请输入要删除的数字：");
            scanf("%d", &x);
            deleDate(&mylist, x);
            printf("按任意键继续.\n");
            ch = getch();
            system("cls");
            break;
        case'3':
            printf("请输入要查找的数字：");
            scanf("%d", &x);
            //普通查找数据
            findDate(&mylist, x);
            //递归查找数据
            //int index = FindData(&mylist, 0, mylist.len, x);
            //printf("第%d个数字\t%d\n", index + 1, mylist.arr[index]);
            printf("按任意键继续.\n");
            ch = getch();
            system("cls");
            break;
        case'4':
            printf("请输入要插入的数字：");
            scanf("%d", &x);
            insertDate(&mylist, x);
            ch = getch();
            system("cls");
            break;
        case'5':
            show(&mylist);
            printf("按任意键继续.\n");
            ch = getch();
            system("cls");
            break;
        default:continue;
        }
    }
    return 0;
}

p->size += (p->size >> 1) > 1 ? p->size >> 1 : 1;
初始化Init之后size=0 ,代入上式 size = size + (size/2)>1?size/2:1;
等同：size = 0 + 0>1?0:1;    所以size = 1;
size = 1 再代入size = size + (size/2)>1?size/2:1;
等同：size = 1 + 0>1?0:1;  所以size = 2;
size = 2 再代入size = size + (size/2)>1?size/2:1;
等同：size = 2 + 1>1?1:1;  所以size = 3;
size = 3 再代入size = size + (size/2)>1?size/2:1;
等同：size = 3 + 1>1?1:1;  所以size = 4;
size = 4 再代入size = size + (size/2)>1?size/2:1;
等同：size = 4 + 2>1?2:1;  所以size = 6;
此后size每次都加上原先1/2的容量