数据结构——线性数据结构复习

时间：2021-11-05 12:20:28
  • 顺序表（C++）：
数据结构——线性数据结构复习数据结构——线性数据结构复习
好久不用C++写程序，都忘了析构函数怎么调用的了，检测内存泄漏：

_CrtDumpMemoryLeaks();

会在析构函数之前调用，写在析构函数里，检测就没毛病了。
View Code

实现代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
class Sqlist {
public:
    Sqlist() {
        data = new int[INIT_SIZE];
        size = INIT_SIZE;
    }
    //插入
    void insert(int x,int pos) {
        if (length == size)reMalloc();
        for (int i = length - 1; i >= pos - 1; i--) 
            data[i + 1] = data[i];
        data[pos - 1] = x;
        length++;
    }
    //删除
    void remove(int x) {
        int index = find(x);
        if (index == -1) {
            cout << "the figure " << x << " is not included." << endl;
            return;
        }
        for (int i = index; i < length - 1; i++) 
            data[i] = data[i + 1];
        length--;
    }
    //查找
    int find(int x) {
        for (int i = 0; i < length; i++) 
            if(data[i] == x) 
                return i;
        return -1;
    }
    //扩容
    void reMalloc() {
        int *t = new int[size * 2];
        for (int i = 0; i < size; i++) 
            t[i] = data[i];
        size *= 2;
        delete data;
        data = t;
    }
    //遍历
    void traverse() {
        for (int i = 0; i < length; i++) 
            cout << data[i] << " ";
        cout << endl;
    }
    //归并排序
    void sort(int left,int right) {
        if (right == left) return;
        int mid = (left + right) / 2;
        sort(left, mid);
        sort(mid + 1, right);
        merger(left, right);
    }
    //获取长度
    int getLength() {
        return length;
    }
    //获取元素
    int get(int index) {
        return data[index];
    }

    ~Sqlist() {
        delete[]data;
        _CrtDumpMemoryLeaks();
    }
private:
    int size;
    ElemType *data;
    int length = 0;

    void merger(int left, int right) {
        int *t = new int[right - left + 1];
        int mid = (left + right) >> 1;
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            t[k++] = data[i] < data[j] ? data[i++] : data[j++];
        }
        while (i <= mid)t[k++] = data[i++];
        while (j <= right)t[k++] = data[j++];
        k = 0;
        while (left <= right)data[left++] = t[k++];
        delete[]t;
    }
};
View Code

测试代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
int main() {
    srand(unsigned(time(0)));
    Sqlist L;
    L.insert(16,1);
    for (int i = 0; i < 200; i++) {
        L.insert(getRandomNum(100),L.getLength());
    }
    cout << L.getLength() << endl; 
    L.traverse();
    for (int i = 0; i < 10; i++) {
        L.remove(getRandomNum(100));
    }
    cout << L.getLength() << endl;
    L.sort(0, L.getLength() - 1);
    L.traverse();
    return 0;
}
View Code
  • 单链表（带头结点）（C++）：

实现代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
typedef int ElemType;
class LNode {
private:
    static int length;
public:
    LNode *next;
    ElemType data;
    LNode() {
        next = NULL;
    }
    //插入
    void insert(int x, int pos) {
        if (pos > length + 1 || pos < 1) {
            cout << "The position you input is invalid." << endl;
            return;
        }
        int i = 1;
        LNode *p = this;
        while (p->next &&i < pos) {
            p = p->next;
            i++;
        }
        LNode *s = new LNode;
        s->data = x;
        s->next = p->next;
        p->next = s;
        length++;
    }
    //尾插
    void push_back(int x) {
        LNode *p = this->next;
        LNode *s = new LNode;
        s->data = x;
        while (p->next) {
            p = p->next;
        }
        s->next = p->next;
        p->next = s;
        length++;
    }
    //头插
    void push_front(int x) {
        LNode *p = this;
        LNode *s = new LNode;
        s->data = x;
        s->next = p->next;
        p->next = s;
        length++;
    }
    //删除第一个和x相等的元素
    void removex(int x) {
        LNode *p = this->next,*pre=this;
        while (p->next) {
            if (p->data == x)break;
            pre = p;
            p = p->next;
        }
        if (!p->next) {
            cout << "The figure is not included." << endl;
            return;
        }
        pre->next = p->next;
        delete p;
    }
    //按位置删除
    void removeIndex(int pos) {
        int i = 1;
        LNode *p = this->next, *pre = this;
        while (p->next && i < pos) {
            pre = p;
            p = p->next;
            i++;
        }
        pre->next = p->next;
        delete p;
    }
    //遍历
    void traverse() {
        LNode *p = this->next;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    void destory() {
        LNode *p = this->next;
        while (p) {
            LNode *t = p->next;
            delete p;
            p = t;
        }
    }
};
int LNode::length = 0;
typedef LNode* LinkList;
View Code

测试代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
int main() {
    LinkList L = new LNode;
    for (int i = 0; i < 10; i++) {
        L->insert(i * 10, i);
    }
    L->removeIndex(2);
    L->removeIndex(3);
    L->removex(3);
    L->removex(1);
    L->traverse();
    
    L->destory();
    delete L;
    _CrtDumpMemoryLeaks();
    return 0;
}
View Code

链表反转：

void reverse(LinkList l) {
    LNode *pre = NULL, *p = l->next;
    while (p) {
        LNode *t = p->next;
        p->next = pre;
        pre = p;
        p = t;
    }
    l->next = pre;
}
  • 双链表（C++）:

 数据结构——线性数据结构复习数据结构——线性数据结构复习

实现代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
typedef int ElemType;
class LNode {
public:
    LNode *next;
    LNode *prior;
    ElemType data;
    LNode() {
        next = NULL;
        prior = NULL;
    }
};
class LinkList {
public:
    static int length;
public:
    LNode *head;
    LNode *tail;
    LinkList() {
        head = tail = NULL;
    }
    //插入
    void insert(int x, int pos) {
        LNode *p = NULL;
        LNode *s = new LNode;
        s->data = x;
        if (pos > length + 1 || pos < 1) {
            cout << "The position you input is invalid." << endl;
            return;
        }
        //如果插入位置离尾节点近
        if (pos > length / 2) {
            int i = length;
            p = tail;
            if (!p) {
                push_back(x);
                return;
            }
            while (i-- > pos) {
                p = p->prior;
            }
        }
        else {
            int i = 1;
            p = head;
            while (i++ < pos) {
                p = p->next;
            }
        }
        s->next = p;
        s->prior = p->prior;
        p->prior->next = s;
        p->prior = s;
        length++;
    }
    //尾插
    void push_back(int x) {
        LNode *p = tail;
        LNode *s = new LNode;
        s->data = x;
        if (!p) {
            tail = head = s;
            length++;
            return;
        }
        
        s->next = NULL;
        p->next = s;
        s->prior = p;
        tail = s;
        length++;
    }
    //头插
    void push_front(int x) {
        LNode *p = head;
        LNode *s = new LNode;
        s->data = x;
        if (!p) {
            tail = head = s;
            length++;
            return;
        }
        s->prior = NULL;
        s->next = head;
        head->prior = s;
        head = s;
        length++;
    }
    
    //按位置删除
    void removeIndex(int pos) {
        if (pos > length || pos < 1) {
            cout << "The position you input is invalid." << endl;
        }
        int i = 1;
        LNode *p = head;
        while (i < pos) {
            p = p->next;
            i++;
        }
        if (i == 1) {
            LNode *t = head;
            head = head->next;
            head->prior = NULL;
            length--;
            delete t;
            return;
        }
        if (i == length) {
            LNode *t = tail;
            tail = tail->prior;
            tail->next = NULL;
            length--;
            delete t;
            return;
        }
        p->next->prior = p->prior; 
        p->prior->next = p->next;
        length--;
        delete p;
        //只剩一个元素时 
    }
    //正向遍历
    void traverse() {
        LNode *p = head;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
    //反向遍历
    void reverseTraverse() {
        LNode *p = tail;
        while (p) {
            cout << p->data << " ";
            p = p->prior;
        }
        cout << endl;
    }
    //销毁
    void destory() {
        LNode *p = head;
        while (p) {
            LNode *t = p->next;
            delete p;
            p = t;
        }
    }
};
int LinkList::length = 0;
View Code

测试代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
int main() {
    LinkList *L = new LinkList;
    L->insert(7, 1);
    L->push_front(1);
    L->push_front(2);
    L->push_front(3);
    L->push_back(4);
    L->push_back(5);
    L->push_back(6);
    L->insert(10, 2);
    L->traverse();
    L->reverseTraverse();

    L->removeIndex(LinkList::length);
    L->removeIndex(1);

    L->traverse();
    L->reverseTraverse();
    L->destory();
    delete L;
    _CrtDumpMemoryLeaks();
    return 0;
}
View Code
  • 循环链表（C++）：

实现起来，和单链表几乎没有区别，把初始next设置为this，每一个 ( *! = NULL ) 终止循环条件改成 ( *! = this )

 实现代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
typedef int ElemType;
class LNode {
private:
    static int length;
public:
    LNode *next;
    ElemType data;
    LNode() {
        next = this;
    }
    //插入
    void insert(int x, int pos) {
        if (pos > length + 1 || pos < 1) {
            cout << "The position you input is invalid." << endl;
            return;
        }
        int i = 1;
        LNode *p = this;
        while (p->next != this &&i < pos) {
            p = p->next;
            i++;
        }
        LNode *s = new LNode;
        s->data = x;
        s->next = p->next;
        p->next = s;
        length++;
    }
    //尾插
    void push_back(int x) {
        LNode *p = this->next;
        LNode *s = new LNode;
        s->data = x;
        while (p->next!=this) {
            p = p->next;
        }
        s->next = p->next;
        p->next = s;
        length++;
    }
    //头插
    void push_front(int x) {
        LNode *p = this;
        LNode *s = new LNode;
        s->data = x;
        s->next = p->next;
        p->next = s;
        length++;
    }
    //删除第一个和x相等的元素
    void removex(int x) {
        LNode *p = this->next, *pre = this;
        while (p->next!=this) {
            if (p->data == x)break;
            pre = p;
            p = p->next;
        }
        if (!p->next) {
            cout << "The figure is not included." << endl;
            return;
        }
        pre->next = p->next;
        delete p;
    }
    //按位置删除
    void removeIndex(int pos) {
        int i = 1;
        LNode *p = this->next, *pre = this;
        while (p->next!=this && i < pos) {
            pre = p;
            p = p->next;
            i++;
        }
        pre->next = p->next;
        delete p;
    }
    //遍历
    void traverse() {
        LNode *p = this->next;
        while (p!=this) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    void destory() {
        LNode *p = this->next;
        while (p!=this) {
            LNode *t = p->next;
            delete p;
            p = t;
        }
    }
};
int LNode::length = 0;
typedef LNode* LinkList;
View Code

测试代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
int main() {

    LinkList L = new LNode;
    for (int i = 0; i < 3; i++) {
        L->push_back(i);
        L->push_front(i);
    }
    L->traverse();
    L->removeIndex(2);
    L->removex(1);
    L->traverse();
    _CrtDumpMemoryLeaks();
    return 0;
}
View Code
  •  循环队列（C语言）：

数组实现：

 

初始时，front,rear指针（下标）都是0。插入元素后，rear指针始终指向队尾元素的后一个位置。

所以，当(rear+1)%size==front时，队满，而队空时，是front==rear。

 

数据结构——线性数据结构复习

实现+测试代码：

数据结构——线性数据结构复习数据结构——线性数据结构复习
#define MAX_SIZE 100

typedef struct{
    int *data;
    int front, rear;
    int size;
}Queue;

void InitQueue(Queue *q) {
    q->data = (int *)malloc(sizeof(int)*MAX_SIZE);
    q->size = MAX_SIZE;
    q->rear = q->front = 0;
}
void EnQueue(Queue *q,int x) {
    
    if ((q->rear + 1) % q->size == q->front) {
        cout << "Queue is full." << endl;
    }
    q->data[q->rear++] = x;
    q->rear %= q->size;
}
int DeQueue(Queue *q) {
    if (q->front == q->rear) {
        cout << "Queue is empty." << endl;
    }
    return q->data[q->front++];
    q->front %= q->size;
}
void destory(Queue *q) {
    free(q->data);
}
int main() {
    Queue *q=(Queue *)malloc(sizeof(Queue));
    InitQueue(q);
    for (int i = 0; i < 10; i++) {
        EnQueue(q,i);
    }
    cout << DeQueue(q) << endl;
    destory(q);
    free(q);
    _CrtDumpMemoryLeaks();
    return 0;
}
View Code

 

堆栈：

本来觉得这句数据结构——线性数据结构复习话是没有必要的，用这段代码测试了一下。

realloc：如果当前 基址后面的空闲内存 能够满足新容量，指针s的不会变，不能满足，新找一片内存空间。

简单点说，就是当realloc时扩容时，一般（扩容特别小的可能不会）是会给开一片新的内存空间。

    int *s = (int *)malloc(sizeof(int) * 10);
    cout << s << endl;
    s = (int *)realloc(s,sizeof(int) * 100);
    cout << s <<endl;

 实现+测试代码:

数据结构——线性数据结构复习数据结构——线性数据结构复习
#define INIT_SIZE 100

typedef struct{
    int *base;
    int *top;
    int size;
}Stack;

Stack* init() {
    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->size = INIT_SIZE;
    s->base = (int *)malloc(sizeof(int) * s->size);
    s->top = s->base;
    return s;
}

void push(Stack *s,int x) {
    if (s->top - s->base == s->size) {
        s->base = (int *)realloc(s->base, sizeof(int)*s->size * 2);
        s->top = s->base + s->size;
        s->size *= 2;
    }
    *(s->top++) = x;
}

int top(Stack *s) {
    if (s->top == s->base) {
        cout << "The Stack is empty." << endl;
    }
    return *(s->top - 1);
}
int pop(Stack *s) {
    if (s->top == s->base) {
        cout << "The Stack is empty." << endl;
    }
    return *(--s->top);
}
void traverse(Stack *s){
    int *t = s->base;
    while (t!=s->top) {
        cout << *(t++) << endl;
    }
}

void destory(Stack *s) {
    free(s->base);
}
int main() {
    Stack *s = init();
    for (int i = 0; i < 1001; i++) {
        push(s, i);
    }
    for (int i = 0; i < 1000; i++) {
        pop(s);
    }
    traverse(s);
    destory(s);
    free(s);
    _CrtDumpMemoryLeaks();
    return 0;
}
View Code

 数据结构——线性数据结构复习

 

 

top.h/tools.h:

数据结构——线性数据结构复习数据结构——线性数据结构复习
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

int* getRandomArray(int size, int value) {
    
    int *a = new int[size];
    for (int i = 0; i < size; i++) {
        a[i] = (rand() % value) - (rand() % value);
    }
    return a;
}

int* getNoRepateRandomArray(int size, int value) {
    //srand(time(NULL));
    int *a = new int[size];
    for (int i = 0; i < size; i++) {
        a[i] = (rand() % value);
        for (int j = 0; j < i; j++) {
            if (a[i] == a[j]) {
                i--; 
                break;
            }
        }
    }
    return a;
}
int getRandomNum(int limit) {
    //srand(unsigned(time(0)));
    return rand() % limit;
}

void meger(int *a, int left, int mid, int right) {
    int *b = new int[right - left + 1];
    int t = 0, i = left, j = mid + 1;

    while (i <= mid && j <= right) {
        b[t++] = a[i] < a[j] ? a[i++] : a[j++];
    }

    while (i <= mid) b[t++] = a[i++];
    while (j <= right) b[t++] = a[j++];

    i = left; t = 0;
    while (i <= right) a[i++] = b[t++];
    delete[]b;
}
void megerSort(int *a, int left, int right) {
    if (left == right) return;
    int mid = (right + left) >> 1;
    megerSort(a, left, mid);
    megerSort(a, mid + 1, right);
    meger(a, left, mid, right);
}

void quickSort(int *a, int left, int right) {
    if (left >= right) return;
    int sign = a[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j&&a[j] >= sign)j--;
        while (i < j&&a[i] <= sign)i++;
        swap(a[i], a[j]);
    }
    swap(a[left], a[i]);
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);

}

void insertSort(int *a, int length) {
    for (int i = 1; i < length; i++) {
        int j, temp = a[i];
        for (j = i; temp < a[j - 1] && j>0; j--) {
            a[j] = a[j - 1];
        }
        a[j] = temp;
    }
}

void bubbleSort(int *a, int length) {
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length - i; j++) {
            if (a[j - 1] > a[j])
                swap(a[j - 1], a[j]);
        }
    }
}
void selectSort(int *a, int length) {
    for (int i = 0; i < length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < length; j++) {
            minIndex = a[j] < a[minIndex] ? j : minIndex;
        }
        swap(a[i], a[minIndex]);
    }
}
void shellSort(int*a, int len)
{
    for (int div = len / 2; div > 0; div /= 2) {
        for (int i = 0; i < div; ++i) {
            for (int j = i + div; j < len; j += div) {
                int k, temp = a[j];
                for (k = j - div; k >= 0 && temp < a[k]; k -= div) {
                    a[k + div] = a[k];
                }
                a[k + div] = temp;
                /*for (k = j; k >= div && temp < a[k - div]; k -= div) {
                    a[k] = a[k - div];
                }
                a[k] = temp;*/
            }
        }
    }
}
View Code

2019年1月26日10:44:17

标签：

相关文章