仿照教材代码，使用顺序表实现折半插入排序算法，并在主函数中输入元素，再输出排序结果（需要用到顺序表的各种基本运算）

折半插入排序算法利用了顺序表的插入操作，其步骤如下：

#include <iostream>
using namespace std;

// 定义顺序表结构体
struct ListNode {
    int data;
    ListNode* next;
};

// 创建顺序表的头部节点
ListNode* createList() {
    return nullptr;
}

// 插入元素到顺序表
void insertToList(ListNode** head, int value) {
    ListNode* newNode = new ListNode{value, nullptr};
    
    if (*head == nullptr) {
        *head = newNode;
    } else {
        ListNode* current = *head;
        while (current->next != nullptr && current->next->data < value) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

// 折半插入排序
void binaryInsertionSort(int arr[], int size) {
    ListNode* listHead = createList();
    for (int i = 0; i < size; ++i) {
        insertToList(&listHead, arr[i]);
    }

    // 将顺序表内容复制回数组并打印排序后的结果
    cout << "Sorted array: ";
    ListNode* temp = listHead;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

// 主函数
int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    
    int arr[n];
    cout << "Enter elements: ";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    binaryInsertionSort(arr, n);
    
    return 0;
}

在这个程序中，首先我们创建了一个顺序列表的头部节点，然后通过循环读取用户输入的元素，依次插入到顺序表中。最后，从顺序表中取出所有元素并按照顺序输出，即得到了排序的结果。