第7章-查找及应用(2020.04.27)_有序表的合并在第几章

第7章-查找及应用

1. 二分查找的实现【中等】

（二分查找的实现）请尝试用你实现的顺序存储List实现二分查找。List中的Record包含key和other部分。其中key为英文单词，other为单词的中文解释。
【输入】
第一行，查询目标target（英文单词）
第二行，若干条包含key（string）和other（string）的序列，序列按照key的升序排列；（单词数量小于2000）
【输出】查询目标所在的下标，查询目标的内容（key和other），若单词不存在则输出-1即可。
例如
【输入】
wait
computer 电脑 eye 眼睛 hello 你好 train 火车 wait 等待 zebra 斑马
【输出】
4
wait 等待
【输入】
apple
computer 电脑 eye 眼睛 hello 你好 train 火车 wait 等待 zebra 斑马
【输出】
-1 //不存在

#include <iostream>
#include <string>
using namespace std;
enum Error_code { underflow, overflow, range_Error, success, not_present };
const int max_list = 2000;

class Record
{
public:
    Record();
    Record(string x, string y);
    string the_key()const;
    string the_other()const;
private:
    string key;
    string other;
};
typedef Record List_entry;

Record::Record()
{

}

Record::Record(string x, string y)
{
    key = x;
    other = y;
}

string Record::the_key()const
{
    return key;
}

string Record::the_other()const
{
    return other;
}

class Key
{
    string key;
public:
    Key(string x);
    Key(const Record& r);
    string the_key()const;
};

Key::Key(string x)
{
    key = x;
}

Key::Key(const Record& r)
{
    key = r.the_key();
}

string Key::the_key()const
{
    return key;
}

bool operator==(const Key& x, const Key& y)
{
    return x.the_key() == y.the_key();
}

//list的顺序实现
class List
{
public:
    List();
    int size()const;
    bool full()const;
    bool empty()const;
    void clear();
    Error_code insert(int position, const List_entry& x);
    Error_code remove(int position, List_entry& x);
    Error_code retrieve(int position, List_entry& x)const;
    Error_code replace(int position, List_entry& x);
    void traverse(void(*visit)(List_entry& x));
protected:
    int count;
    List_entry entry[max_list];
};

List::List()
{
    count = 0;
}

int List::size()const
{
    return count;
}

bool List::full()const
{
    if (count == max_list) return true;
    return false;
}

bool List::empty()const
{
    if (count == 0) return true;
    return false;
}

void List::clear()
{
    count = 0;
}

Error_code List::retrieve(int position, List_entry& x)const
{
    if (position < 0 || position >= count) return range_Error;
    x = entry[position];
    return success;
}

Error_code List::insert(int position, const List_entry& x)
{
    if (full()) return overflow;
    if (position<0 || position>count) return range_Error;
    for (int i = count - 1; i >= position; i--) entry[i + 1] = entry[i];
    entry[position] = x;
    count++;
    return success;
}

Error_code List::remove(int position, List_entry& x)
{
    if (empty()) return underflow;
    if (position < 0 || position >= count) return range_Error;
    x = entry[position];
    for (int i = position; i < count - 1; i++) entry[i] = entry[i + 1];
    count--;
    return success;
}

Error_code List::replace(int position, List_entry& x)
{
    if (position < 0 || position >= count) return range_Error;
    entry[position] = x;
    return success;
}

void List::traverse(void(*visit)(List_entry& x))
{
    for (int i = 0; i < count; i++)
        (*visit)(entry[i]);
}

Error_code binary_search_1(const List& the_list, const Key& target, int& position, string& find)
{
    Record data;
    int bottom = 0, top = the_list.size() - 1;
    while (bottom < top) {
        int mid = (bottom + top) / 2;
        the_list.retrieve(mid, data);
        if (data.the_key() < target.the_key())
            bottom = mid + 1;
        else top = mid;
    }
    if (top < bottom) return not_present;
    else {
        position = bottom;
        the_list.retrieve(bottom, data);
        if (data.the_key() == target.the_key()) {
            find = data.the_other();
            return success;
        }
        else return not_present;
    }
}

int main()
{
    List a;
    string key, other, tran;
    int i = 0, position;
    cin >> key;
    Key target(key);
    while (cin >> key >> other) {
        Record temp(key, other);
        a.insert(i++, temp);
    }
    Error_code outcome = binary_search_1(a, target, position, tran);
    if (outcome == not_present) {
        cout << -1;
    }
    else{
        cout << position << endl << target.the_key() << ' ' << tran;
    }
    return 0;
}
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

2. Start and End Position【中等】

（Start and end position）Given an array of integers numbers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].
【输入】
第一行，要查找的目标值
第二行，值按升序排列的整数数组，数组以-1结束（数组长度小于2000）
【输出】 目标值在数组里，第一次以及最后一次出现的下标
例如：
【输入】
8
5 7 7 8 8 10 -1
【输出】
[3,4]
【输入】
6
5 7 7 8 8 10 -1
【输出】
[-1,-1]

#include <iostream>
using namespace std;

void find_first(int arr[], int target, int len)
{
    int left = 0;
    int right = len - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] >= target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    //不要加&& right > -1
    //因为出循环的时候如果找到的是第一个数那么right一定为-1
    if (left < len && arr[left] == target)
        cout << '[' << left << ',';
    else cout << '[' << -1 << ',';
}

void find_last(int arr[], int target, int len)
{
    int left = 0;
    int right = len - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    //不要加left < len &&
    //同理如果找到的是最后一个数那么出循环的时候left一定为len
    if (right > -1 && arr[right] == target)
        cout << right << ']' << endl;
    else cout << -1 << ']' << endl;
}

int main()
{  
    int target, num, i = 0;
    int arr[2001];
    cin >> target >> num;
    while (num != -1) {
        arr[i++] = num;
        cin >> num;
    }
    find_first(arr, target, i);
    find_last(arr, target, i);
}
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

3. 求开方值【中等】

（Sqrt function）Implement int sqrt(int x).Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
【输入】x的值，x为整数
【输出】x的平方根（整数）
例如：
【输入】 4
【输出】 2
【输入】 8
【输出】 2 //8的开方为2.82842，结果只需要输出整数，故输出2即可。

#include <iostream>
using namespace std;

long long sqrt(int x) {
    long long left = 0;
    long long right = x;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (mid * mid < x)
            left = mid + 1;
        else if (mid * mid > x)
            right = mid - 1;
        else
            return mid;
    }
    return right;
}

int main()
{  
    long long num;
    cin >> num;
    cout << sqrt(num);
    return 0;
}
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

4. 有序表合并 【中等】

（有序表合并）给定有序的单链表La和Lb（元素类型为整型），请编写程序将La和Lb合并成为一个新的有序表。（注意：你的程序使用的辅助空间为常数，即若La中有m个节点，Lb中有n个节点，程序需要的节点空间为m+n+常数）
【输入】
单链表La的值（升序）（-1结束）
单链表Lb的值（升序）（-1结束）
【输出】
La和Lb排序的后的结果
例如：
【输入】
1 6 12 19 -1
3 7 16 29 45 99 -1
【输出】
1 3 6 7 12 16 19 29 45 99
（这题就是把链表串起来）

#include <iostream>
using namespace std;
typedef int Node_entry;

struct Node
{
    Node_entry entry;
    Node* next;
    Node();
    Node(Node_entry item, Node* add_on = NULL);
}*LinkList;

Node::Node()
{
    next = NULL;
}

Node::Node(Node_entry item, Node* add_on)
{
    entry = item;
    next = add_on;
}

Node* creat()
{
    Node* head = new Node();
    Node* cur = head;
    int num;
    cin >> num;
    while (num != -1) {
        Node* newptr = new Node(num);
        cur->next = newptr;
        cur = newptr;
        cin >> num;
    }
    return head;
}

Node* hebin(Node* La, Node* Lb)
{
    //原链表中的游走指针
    Node* pa = La->next;
    Node* pb = Lb->next;
    //新的链表中的游走指针
    Node* cur = La;
    cur->next = NULL;
    while (pa && pb) {
        if (pa->entry < pb->entry) {
            cur->next = pa;
            cur = pa;
            pa = pa->next;
        }
        else {
            cur->next = pb;
            cur = pb;
            pb = pb->next;
        }
    }
    if (pa) {
        cur->next = pa;
    }
    if (pb) {
        cur->next = pb;
    }
    return La;
}

void print(Node* L)
{
    Node* cur = L->next;
    while (cur != NULL) {
        cout << cur->entry << ' ';
        cur = cur->next;
    }
}

int main()
{
    Node* La, * Lb, * Lc;
    La = creat();
    Lb = creat();
    Lc = hebin(La, Lb);
    print(Lc);
    //删除Lb头节点
    delete Lb;
    //删除Lc(一串全删啦！)
    while (Lc != NULL) {
        Node* temp = Lc;
        Lc = Lc->next;
        delete temp;
    }
    return 0;
}
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
93