• 日期: 2026-09-15 05:13:19
  • 标签: 常规

C/C++ 顺序表、排序和查找算法实现及应用

1. 顺序表结构和相关基本操作

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int length;
} SeqList;

void InitList(SeqList *list) {
    list->length = 0;
}

void Unique(SeqList *list) {
    int i, j, k;
    for (i = 0; i < list->length; i++) {
        for (j = i + 1; j < list->length; j++) {
            if (list->data[i] == list->data[j]) {
                for (k = j; k < list->length - 1; k++) {
                    list->data[k] = list->data[k + 1];
                }
                list->length--;
                j--;
            }
        }
    }
}

void PrintList(SeqList *list) {
    int i;
    for (i = 0; i < list->length; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

int GetSize(SeqList *list) {
    return list->length;
}

int FindElement(SeqList *list, int target) {
    int i;
    for (i = 0; i < list->length; i++) {
        if (list->data[i] == target) {
            return i;
        }
    }
    return -1;
}

void InsertElement(SeqList *list, int position, int element) {
    int i;
    if (position < 0 || position > list->length) {
        printf("Invalid position!\n");
        return;
    }
    for (i = list->length; i > position; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[position] = element;
    list->length++;
}

void DeleteRange(SeqList *list, int start, int end) {
    int i;
    if (start < 0 || end >= list->length || start > end) {
        printf("Invalid range!\n");
        return;
    }
    for (i = end + 1; i < list->length; i++) {
        list->data[i - end + start - 1] = list->data[i];
    }
    list->length -= (end - start + 1);
}

int main() {
    SeqList list;
    InitList(&list);
    list.data[0] = 1;
    list.data[1] = 2;
    list.data[2] = 2;
    list.data[3] = 3;
    list.data[4] = 4;
    list.length = 5;
    
    Unique(&list);
    PrintList(&list);
    
    printf("Size of list: %d\n", GetSize(&list));
    
    int target = 3;
    int index = FindElement(&list, target);
    if (index != -1) {
        printf("Element %d found at index %d\n", target, index);
    } else {
        printf("Element %d not found\n", target);
    }
    
    int position = 2;
    int element = 5;
    InsertElement(&list, position, element);
    PrintList(&list);
    
    int start = 1;
    int end = 3;
    DeleteRange(&list, start, end);
    PrintList(&list);
    
    return 0;
}

2. 冒泡排序、归并排序和折半查找算法

2.1 冒泡排序

#include <stdio.h>

void BubbleSort(int arr[], int size) {
    int i, j, temp;
    for (i = 0; i < size - 1; i++) {
        for (j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    BubbleSort(arr, size);
    
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

2.2 归并排序

#include <stdio.h>

void Merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int L[n1], R[n2];
    
    for (i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    
    i = 0;
    j = 0;
    k = left;
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void MergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        
        Merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    MergeSort(arr, 0, size - 1);
    
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

2.3 折半查找

#include <stdio.h>

int BinarySearch(int arr[], int left, int right, int target) {
    if (right >= left) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] > target) {
            return BinarySearch(arr, left, mid - 1, target);
        }
        
        return BinarySearch(arr, mid + 1, right, target);
    }
    
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 5, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    int target = 5;
    int index = BinarySearch(arr, 0, size - 1, target);
    
    if (index != -1) {
        printf("Element %d found at index %d\n", target, index);
    } else {
        printf("Element %d not found\n", target);
    }
    
    return 0;
}

3. 合并序列并查找元素

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int length;
} SeqList;

void InitList(SeqList *list) {
    list->length = 0;
}

void Merge(SeqList *list1, SeqList *list2, SeqList *mergedList) {
    int i, j;
    mergedList->length = list1->length + list2->length;
    
    for (i = 0; i < list1->length; i++) {
        mergedList->data[i] = list1->data[i];
    }
    for (j = 0; j < list2->length; j++) {
        mergedList->data[i + j] = list2->data[j];
    }
}

int BinarySearch(SeqList *list, int target) {
    int left = 0;
    int right = list->length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (list->data[mid] == target) {
            return mid;
        }
        
        if (list->data[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

int main() {
    SeqList list1, list2, mergedList;
    InitList(&list1);
    InitList(&list2);
    
    list1.data[0] = 1;
    list1.data[1] = 3;
    list1.data[2] = 5;
    list1.length = 3;
    
    list2.data[0] = 2;
    list2.data[1] = 4;
    list2.length = 2;
    
    Merge(&list1, &list2, &mergedList);
    
    int i;
    for (i = 0; i < mergedList.length; i++) {
        printf("%d ", mergedList.data[i]);
    }
    printf("\n");
    
    int target = 3;
    int index = BinarySearch(&mergedList, target);
    
    if (index != -1) {
        printf("Element %d found at index %d\n", target, index);
    } else {
        printf("Element %d not found\n", target);
    }
    
    return 0;
}

注意:

  • 代码中使用 #define MAX_SIZE 100 定义了顺序表的最大容量，可以根据需要调整。
  • 以上代码仅供参考，可以根据具体需求进行修改和扩展。
  • 合并序列时，代码中使用了 BinarySearch 函数来查找元素，也可以使用其他查找算法。
  • 在实际应用中，应根据具体情况选择合适的排序算法和查找算法。
C/C++ 顺序表、排序和查找算法实现及应用

原文地址: https://www.cveoy.top/t/topic/RP5 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录