cpp数据结构

结构

线性表

方法
初始化init()
头插insertAtHead(int vale)
尾插insertAtTail(int vale)
删除指定元素deletenode(int vale)
遍历输出printList()
析构LinkedList()

线性表

数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;

const int N = 10;    //最大容量为10
int res[N + 1];    //存储元素,下标从1开始
int cnt = 0;    //数组指针，也表示当前元素数量

//插入元素
void push_key(int key)
{
    if (cnt == N)
    {
        cout << "容器已满！" << endl;
        return;
    }
    res[++cnt] = key;    
}

//在指定位置前插入元素
void insert_key(int idx, int key)
{
    if (cnt == N)
    {
        cout << "容器已满！" << endl;
        return;
    }
    //判断指定的位置下标是否超出范围或数组越界
    if (idx<1 || idx>N)
    {
        cout << "下标不满足要求!" << endl;
        return;
    }
    for (int i = cnt; i >= idx; i--)
        res[i + 1] = res[i];    //将插入位置的后面所有元素都后移一位
    res[idx] = key;
    cnt++;
}

//找到指定元素
int find(int key)
{
    for (int i = 1; i <= cnt; i++)
        if (res[i] == key)
            return i;
    return -1;
}

//删除指定元素
void delete_key(int key)
{
    if (cnt == 0)
    {
        cout << "容器为空！" << endl;
        return;
    }
    int idx = find(key);    //找到该元素的位置
    if (idx == -1)
    {
        cout << "不存在该元素！" << endl;
        return;
    }
    for (int i = idx; i <= cnt; i++)
        res[i] = res[i + 1];    //让删除元素后面的所有元素向前移一位就可以覆盖掉删除元素
    cnt--;
}

//展示容器中元素
void show()
{
    if (cnt == 0)
    {
        cout << "容器为空！" << endl;
        return;
    }
    for (int i = 1; i <= cnt; i++)
        cout << res[i] << " ";
    cout << endl;
}

int main()
{
    //初始化数组
    for (int i = 1; i <= 5; i++)
        push_key(i);
    show();
    insert_key(3, 9);
    insert_key(5, 7);
    show();
    delete_key(3);
    delete_key(10);
    show();
}

单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;

struct node
{
    int data;        //数据
    node* next;        //指向下一个结点的指针
};

node* head = NULL;    //将头指针设为全局变量，方便使用
void init_node();         //初始化结点
void head_insert(int);    //头插法
void end_insert(int);     //尾插法
void delete_node(int);    //删除结点
void show();              //遍历链表

int main()
{
    init_node();
    head_insert(4);
    head_insert(9);
    end_insert(7);
    show();
    delete_node(4);
    show();
}

void show()
{
    node* temp = head->next;
    if (temp == NULL)
    {
        cout << "当前还没有创建结点" << endl;
        return;
    }
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

void init_node()
{
    node* new_node = new node;
    new_node->data = -1;
    new_node->next = NULL;
    head = new_node;
}

void head_insert(int key)
{
    node* new_node = new node;
    new_node->data = key;
    new_node->next = head->next;    //将新结点的next指向head的ne
    head->next = new_node;          //将head的next指向新结点
}

void end_insert(int key)
{
    node* new_node = new node;
    node* temp = head;                //创建一个临时指针
    while (temp->next != NULL)        //将临时指针指向最后一个结点
        temp = temp->next;
    new_node->data = key;            //给新结点赋值
    new_node->next = temp->next;    //将新结点的next指向temp的next
    temp->next = new_node;            //将temp的next指向新结点
}

void delete_node(int key)
{
    node* temp = head->next;
    node* prev = head;
    while (temp->data != key && temp != NULL)
    {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL)
    {
        cout << "没有此结点" << endl;
        return;
    }
    prev->next = temp->next;
    temp->next = NULL;
    delete[]temp;
    temp = NULL;
}