C++数据结构一些菜到扣脚的个人用例

注：学习用，非常基础，用于速通

一个简单的链表实现

#include <iostream>

using namespace std;

class Node{
	public://别忘记写public
		int data;
		Node* next;
};

void PrintList(Node* head) {
	Node* temp = head;
	while (temp != NULL)
	{
		cout << temp->data << ' ';
		temp = temp->next;
	}
	cout << endl;
}

int FindElement(Node* head, int target) {
	int Index = 1;
	while (head && head->data != target)
	{
		Index++;
		head = head->next;
	}
	if (head) return Index;
	else
	{
		cout << "The element does not exist!" << endl;
		return -1;
	}
}

Node* NewNode(int value,Node* next) {
	Node* temp = new Node();
	temp->data = value;
	temp->next = next;
	return temp;
}

void InsertNode(Node** head, int index, Node* newNode) //用双指针就可以实现
{
	Node* temp = *head;

	if (index < 0) {
		return;
	}

	if (index == 0) {
		newNode->next = temp;
		*head = newNode;
		return;
	}

	for (int i = 1; i < index; i++)
	{
		temp = temp->next;
	}
	if (temp)
	{
		newNode->next = temp->next;//都接在下一个上？如果用了newNode=head，data也会覆盖吗
		temp->next = newNode;
	}

}

void DeleteNode(Node** head, int Index) 
{
	Node* temp = *head;
	Node* prevNode = *head;

	if (Index <= 0)	return;
	if (Index == 1) {
		*head = (*head)->next;
		free(temp);
		return;
	}
	for (int i = 1; i < Index; i++) {
		prevNode = temp;
		temp = temp->next;
	}
	prevNode->next = temp->next;
	free(temp);
	return;
}

int main()
{
	Node* head = new Node();//别忘记* //最重要的是！NEW！new Node()!!!
	Node* second = new Node();
	Node* third = new Node();
	head->data = 1;
	second->data = 2;
	third->data = 3;
	head->next = second;
	second->next = third;
	third->next = NULL;

	PrintList(head);

	int target;
	cout << "Please enter the element you want to find: ";
	cin >> target;
	cout << "The index of targeted element is " << FindElement(head, target) << endl;
	
	cout << "\nTo insert three 4s into different location: " << endl;
	InsertNode(&head, 3, NewNode(4, NULL));//tm的，要传head的地址进去
	PrintList(head);
	InsertNode(&head, 0, NewNode(4, NULL));
	PrintList(head);
	InsertNode(&head, 2, NewNode(4, second));
	PrintList(head);

	cout << "To delete first node with 4 and another 4 one by one: " << endl;
	DeleteNode(&head, 1);
	PrintList(head);
	DeleteNode(&head, 2);
	PrintList(head);
}

排序算法青春版（5个）

#include <iostream>

using namespace std;

// 合并两个子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 左子数组大小
    int n2 = right - mid;    // 右子数组大小

    // 动态分配普通数组
    int* L = new int[n1];
    int* R = new int[n2];

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    // 合并临时数组到原数组
    int 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;
    }

    // 释放动态分配的内存
    delete[] L;
    delete[] R;
}

// 递归实现归并排序
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 partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;       // i 指向小于基准值部分的最后一个元素

    for (int j = low; j < high; ++j) {
        if (arr[j] >= pivot) {                   //这里大于是降序小于是升序!
            ++i;
            swap(arr[i], arr[j]); // 交换当前元素和 i 指针所指元素
        }
    }
    // 将基准值放到正确位置
    swap(arr[i + 1], arr[high]);
    return i + 1; // 返回基准值的位置
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 划分数组，获得基准位置
        quickSort(arr, low, pi - 1);        // 递归排序基准左侧部分
        quickSort(arr, pi + 1, high);       // 递归排序基准右侧部分
    }
}

//选择排序
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i; // 假设当前元素是最小值

        // 找到剩余部分中最小元素的索引
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {        //这里大于是降序小于是升序!
                minIndex = j;
            }
        }

        // 交换当前元素和找到的最小元素
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

//插入排序
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i]; // 当前待插入的元素
        int j = i - 1;

        // 将大于 key 的元素右移一位
        while (j >= 0 && arr[j] > key) {       //改成小于key是降序！
            arr[j + 1] = arr[j];
            --j;
        }

        // 插入 key 到正确位置
        arr[j + 1] = key;
    }
}

// 冒泡排序
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        // 每次循环，将最大值"冒泡"到未排序部分的末尾
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {          // 升序：比较条件为 >，小于是降序
                swap(arr[j], arr[j + 1]); // 交换相邻两个元素
            }
        }
    }
}

int main() {
    int arr1[] = { 38, 27, 43, 3, 9, 82, 10 };//给归并
    int arr2[] = { 38, 27, 43, 3, 9, 82, 10 };//给快排
    int arr3[] = { 38, 27, 43, 3, 9, 82, 10 };//给选择
    int arr4[] = { 38, 27, 43, 3, 9, 82, 10 };//给插入
    int arr5[] = { 38, 27, 43, 3, 9, 82, 10 };//给冒泡
    int n = sizeof(arr1) / sizeof(arr1[0]);

    //归并
    cout << "排序前数组: ";
    for (int i = 0; i < n; ++i)
        cout << arr1[i] << " ";
    cout << endl;

    mergeSort(arr1, 0, n - 1);

    cout << "归并排序后数组: ";
    for (int i = 0; i < n; ++i)
        cout << arr1[i] << " ";
    cout << endl;

    //快排
    quickSort(arr2, 0, n - 1);

    cout << "快速排序后数组: ";
    for (int i = 0; i < n; ++i)
        cout << arr2[i] << " ";
    cout << endl;

    //选择
    selectionSort(arr3, n);

    cout << "选择排序后数组: ";
    for (int i = 0; i < n; ++i)
        cout << arr3[i] << " ";
    cout << endl;

    //插入
    insertionSort(arr4, n);

    cout << "选择排序后数组: ";
    for (int i = 0; i < n; ++i)
        cout << arr4[i] << " ";
    cout << endl;

    //冒泡
    bubbleSort(arr5, n);

    cout << "选择排序后数组: ";
    for (int i = 0; i < n; ++i)
        cout << arr5[i] << " ";
    cout << endl;

    return 0;
}

Simon给的链表实现

#include <iostream>
using namespace std;

class Node{
    public:
        double data;
        Node * next;
};

class List{
    public:
        List()//构造函数
        {
            head = NULL;
        }
        bool IsEmpty()
        {
            return head == NULL;
        }
        Node * InsertNode(int index, double x);
        int FindNode(double x);
        int DeleteNode(double x);
        void DisplayList(void);
    private:
        Node * head;
};

//类外定义成员函数
//插入节点
Node * List::InsertNode(int index, double x)
{
    if(index < 0)
        return NULL;
    int currIndex = 1;
    Node * currNode = head;
    while(currNode && index > currIndex)
    {
        currNode = currNode->next;
        currIndex++;
    }
    if(index > 0 && currNode == NULL)
        return NULL;
    Node * newNode = new Node;
    newNode->data = x;
    if(index = 0)
    {
        newNode ->next = head;
        head = newNode;
    }
    else{
        newNode ->next = currNode->next;
        currNode->next = newNode;
    }
    return newNode;
}

//寻找节点
int List::FindNode(double x)
{
    Node * temp = head;
    int currIndex = 1;
    while(temp && temp->data != x)
    {
        temp = temp->next;
        currIndex++;
    }
    if(temp)
        return currIndex;
    return 0;
}

Simon的排序

#include <iostream>
using namespace std;

//选择排序
//从i之后选最小的放在前面
void selectionSort(int ass[],int size)
{
    for(int i = 0; i< size;i++)
    {
        int index = i;
        for(int j = i+1; j< size;j++)
        {
            if(ass[j] < ass[index])
                index = j;
        }
        swap(ass[index],ass[i]);
    }
}

//插入排序
//将下一位放到已排序列的正确位置
void insertSort(int arr[], int size)
{
    for(int i = 1; i< size;i++)
    {
        int key = arr[i];
        int j = i-1;
        while(j > 0 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

//冒泡排序
void bubbleSort(int arr[],int size)
{
    for(int i = 0; i < size-1; i++)
    {
        for(int j = 0; j < size -i-1; j++)
        {
            if(arr[j+1] < arr[j])
                swap(arr[j],arr[j+1]);
        }
    }
}

//归并排序
void merge(int arr[],int left,int right,int mid)
{
    int tempArr[100];
    int  left1 = left;
    int right1 = mid;
    int left2 = mid +1;
    int right2 = right;
    int index = left;

    for(;left1 < right1 && left2<right2;index++)
    {
        if(arr[left1] < arr[left2])
        {
            tempArr[index] = arr[left2];
            left1++;
        }
        else
        {
            tempArr[index] = arr[left2];
            left2++;
        }
    }   
    while(left1 <= right1)
    {
        tempArr[index] = arr[left1];
        left1++;
        index++;
    }
    while(left2 <=right2)
    {
        tempArr[index] = arr[left2];
        left2++;
        index++;
    }
    for(int i = left;i<right;i++)
        arr[i] = tempArr[i];
}

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

//快速排序
int partition(int arr[],int left,int right)
{
    int pivot = right;
    int i = left;
    for(int j =left; j<right;j++)
    {
        if(arr[j] < arr[pivot])
        {
            swap(arr[i],arr[j]);
            i++;
        }
    }
    swap(arr[i],arr[pivot]);
    return i;
}

void quickSort(int arr[],int left,int right)
{
    if(left < right)
    {
        int pi = partition(arr,left,right);
        quickSort(arr,left,pi-1);
        quickSort(arr,pi+1,right);
    }
}

网站统计信息

菜单

发送评论编辑评论

发送评论 编辑评论

推荐文章

发送评论编辑评论