1.回文字符串
判断一个非空字符串是否是回文。
#include <iostream>
#include <string>
using namespace std;
bool judge(string str) {
int len = 0;
for (int i = 0; i < 100; i++) {
if (str[i] < 65 || str[i]>122) {
break;
}
len++;//计算字符串的大小
}
for (int i = 0; i < len; i++) {
if (str[i] != str[len - i - 1]) {
return false;
}//回文数
/*
此处将反面作为判断，因为正面必须所有字符都满足才可以，稍微麻烦
*/
}
return true;
}
int main()
{
string s;
getline(cin, s);
bool res = judge(s);
if (res)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}2.奇偶数排序
已知数组A[n]中的元素是整型，设计算法将其调整为左右两部分，其中左边是奇数，右边是偶数。并要求算法的时间复杂度是O（n），空间复杂度是O（1）。
#include <iostream>
using namespace std;
void split(int A[], int n) {
int temp;
int i=0, j=n-1;
while (i < j) {
while (i < j && A[i] % 2 != 0) i++;
while (i < j && A[j] % 2 == 0) j--;
if (i<j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
void show(int A[], int n) {
for (int i = 0; i < n; ++i)
cout << A[i] << " ";
cout << endl;
}
int main()
{
int n;
cin >> n;
int a[100];
for (int i = 0; i < n; ++i)
cin >> a[i];
split(a, n);
show(a, n);
return 0;
}
3.循环左移
将一个具有 n 个元素的数组A[n]向左循环移动k个位置，要求时间复杂度为O(n)，空间复杂度为O(1)。
#include <iostream>
using namespace std;
void reverseArr(int A[], int start, int rear) {//倒置算法
int temp;
int len = rear - start + 1;
for (int i = 0; i < len / 2; i++)
{
temp = A[start + i];
A[start + i] = A[rear - i];
A[rear - i] = temp;
}
}
void leftCir(int A[], int n, int k) {
if (k <= 0 || k >= n)
cout << "ERROR" << endl;
else {
/*将这个问题看作是把数组AB转换成数组BA
（A代表数组的前 i 个元素，B代表数组中余下的 n – i 个元素），
先将A置逆得到A'，再将B置逆得到B'，
最后将整个A'B'置逆得到(A'B')' = BA*/
reverseArr(A, 0, k - 1);
reverseArr(A, k, n - 1);
reverseArr(A, 0, n - 1);
}
}
void show(int A[], int n) {
for (int i = 0; i < n; ++i)
cout << A[i] << " ";
cout << endl;
}
int main()
{
int n, p;
cin >> n >> p;
int a[100];
for (int i = 0; i < n; ++i)
cin >> a[i];
leftCir(a, n, p);
show(a, n);
return 0;
}4.求最大值与次最大值
找出整型数组A[n]中的最大值和次最大值
#include <iostream>
using namespace std;
void getMax(int A[],int n,int &fMax,int &sMax){
int temp;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1; j++)
{
if (A[j] < A[j + 1]) {
temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
}
}
}
fMax = A[0];
sMax = A[1];
}
int main()
{
int n,maxV,nMax;
cin>>n;
int a[n];
for(int i=0;i<n;++i)
cin>>a[i];
getMax(a,n,maxV,nMax);
cout<<maxV<<" "<<nMax<<endl;
return 0;
}
5.顺序表插入并且递增有序
已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保持表L仍递增有序。
#include <iostream>
using namespace std;
const int MaxSize = 100;
typedef int DataType;
DataType data[MaxSize];
int length = 0;
void insertList(DataType elem)
{
DataType data[MaxSize];
int i;
for (i = 0; i < length; i++)
{
if (data[i] > elem)
break;
}
for (int j = length - 1; j >= i; j--) {
data[j + 1] = data[j];
}
data[i] = elem;
length++;
}
void show()
{
DataType data[MaxSize];
for (int i = 0; i < length; ++i)
cout << data[i] << " ";
cout << endl;
}
int main()
{
DataType data[MaxSize];
cin >> length;
for (int i = 0; i < length; ++i)
cin >> data[i];
DataType x;
cin >> x;
insertList(x);
show();
return 0;
}6.删除顺序表元素
在顺序表中删除所有元素值为x的元素，要求空间复杂度为O(1)。
#include <iostream>
using namespace std;
const int MaxSize = 100;
typedef int DataType;
DataType data[MaxSize];
int length;
void deleteList(DataType elem)
{
DataType data[MaxSize];
int acount = 0;
int i, j;
for (i = 0; i < length; i++) {
if (data[i] == elem) {
for (j = i; j < length; j++) {
data[j] = data[j + 1];
}
acount++;
i--;
}
}
length = length - acount;
}
void show()
{
DataType data[MaxSize];
for (int i = 0; i < length; ++i)
cout << data[i] << " ";
cout << endl;
}
int main()
{
DataType data[MaxSize];
cin >> length;
for (int i = 0; i < length; ++i)
cin >> data[i];
DataType x;
cin >> x;
deleteList(x);
show();
return 0;
}7.顺序表逆置
以顺序表存储非空线性表，编写一个实现线性表就地逆置的算法。空间复杂度均是O(1)。
#include <iostream>
using namespace std;
const int MaxSize = 100;
typedef int DataType;
DataType data[MaxSize];
int length;
void reverseList()
{
DataType data[MaxSize];
int temp;
for (int i = 0; i < length / 2; i++) {
temp = data[i];
data[i] = data[length - 1 - i];
data[length - 1 - i] = temp;
}
}
void show()
{
DataType data[MaxSize];
for (int i = 0; i < length; ++i)
cout << data[i] << " ";
cout << endl;
}
int main()
{
DataType data[MaxSize];
cin >> length;
for (int i = 0; i < length; ++i)
cin >> data[i];
reverseList();
show();
return 0;
}8.单链表逆置
以单链表作存储结构存储非空线性表，编写一个实现线性表就地逆置的算法。空间复杂度均是O(1)。
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct node {
DataType data;
node* next;
}node;
node* first;
int length;
void init()
{
first = new node;
first->next = NULL;
node* rear = first;
cin >> length;
for (int i = 0; i < length; ++i) {
DataType elem;
cin >> elem;
node* s = new node;
s->data = elem;
s->next = NULL;
rear->next = s;
rear = s;
}
}
void reverseList()
{
node* q = new node();
node* p = first->next;
first->next = NULL;
while (p != NULL)
{
q = p->next;
p->next = first->next;
first->next = p;
p = q;
}
}
void show()
{
node* p = first->next;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main()
{
init();
reverseList();
show();
return 0;
}9.单链表删除重复数值
有一个递增非空单链表，设计一个算法删除值域重复的结点。例如{1,1,2,3,3,3,4,4,7,7,7,9,9,9,}，经过删除后变成{1,2,3,4,7,9}。
#include <iostream>
using namespace std;
template <class DataType>
struct node {
DataType data;
node<DataType>* next;
};
template <class DataType>
class linkList {
public:
linkList();
~linkList();
void Delete();
void show();
private:
node<DataType>* first;
};
template <class DataType>
linkList<DataType>::linkList()
{
first = new node<DataType>;
first->next = NULL;
node<DataType>* rear = first;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
DataType elem;
cin >> elem;
node<DataType>* s = new node<DataType>;
s->data = elem;
s->next = NULL;
rear->next = s;
rear = s;
}
}
template <class DataType>
linkList<DataType>::~linkList()
{
node<DataType>* p;
while (first != NULL) {
p = first;
first = first->next;
delete p;
}
}
template <class DataType>
void linkList<DataType>::Delete()
{
node<DataType>* p = first->next;
while (p != NULL && p->next != NULL)//遍历链表，查看是否有与p值域相同的结点
{
if (p->data == p->next->data)//有,删除s
{
node<DataType>* s = p->next;//生成新结点s，指向重复结点
p->next = s->next;//修改指针，此时q->next是s的下一个结点，下一轮继续判断
delete s;
}
else//不同，判断下一个结点
p = p->next;
}
}
template <class DataType>
void linkList<DataType>::show()
{
node<DataType>* p = first->next;
if (p == NULL) cout << "Empty";
else {
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
}
int main()
{
linkList<int> L;
L.Delete();
L.show();
L.~linkList();
return 0;
}10.查找单链表倒数第k个结点
【问题描述】输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。
【输入形式】第一行是数据的个数，第二行是空格分割的整型值，第三行是K值。
【输出形式】输出为倒数第K个结点的值，若无，则输出Not Found。
【样例输入】
8
13 45 54 32 1 4 98 2
3
【样例输出】4
【样例说明】K值为3，则输出链表倒数第3个结点的值，为4；数据输入间以空格隔开
#include <iostream>
using namespace std;
template <class DataType>
struct node {
DataType data;
node<DataType>* next;
};
template <class DataType>
class linkList {
public:
linkList();
~linkList();
node<DataType>* reverseFindK(int k);
private:
node<DataType>* first;
};
template <class DataType>
linkList<DataType>::linkList()
{
first = new node<DataType>;
first->next = NULL;
node<DataType>* rear = first;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
DataType elem;
cin >> elem;
node<DataType>* s = new node<DataType>;
s->data = elem;
s->next = NULL;
rear->next = s;
rear = s;
}
}
template <class DataType>
linkList<DataType>::~linkList()
{
node<DataType>* p;
while (first != NULL) {
p = first;
first = first->next;
delete p;
}
}
template <class DataType>
node<DataType>* linkList<DataType>::reverseFindK(int k)
{
node<DataType>* p = NULL;
node<DataType>* q = NULL;
p = first->next;
q = first->next;
int count = 1;
int length = 1;
while (q != NULL) {
q = q->next;
length++;
}
while (p != NULL) {
if (length < k) return NULL;
if (count == length - k) {
return p;
}
p = p->next;
count++;
}
}
int main()
{
linkList<int> L;
int k;
cin >> k;
node<int>* p = L.reverseFindK(k);
if (p == NULL)
cout << "Not Found" << endl;
else
cout << p->data << endl;
L.~linkList();
return 0;
}11.逆序打印单链表
写一个函数，逆序打印单链表中的数据（单链表是带有头结点的单链表）。
#include <iostream>
using namespace std;
template <class DataType>
struct node {
DataType data;
node<DataType>* next;
};
template <class DataType>
class linkList {
public:
linkList();
~linkList();
node<DataType>* getFirst();
void reversePrint(node<DataType>* p);
private:
node<DataType>* first;
};
template <class DataType>
linkList<DataType>::linkList()
{
first = new node<DataType>;
first->next = NULL;
node<DataType>* rear = first;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
DataType elem;
cin >> elem;
node<DataType>* s = new node<DataType>;
s->data = elem;
s->next = NULL;
rear->next = s;
rear = s;
}
}
template <class DataType>
linkList<DataType>::~linkList()
{
node<DataType>* p;
while (first != NULL) {
p = first;
first = first->next;
delete p;
}
}
template <class DataType>
node<DataType>* linkList<DataType>::getFirst()
{
return first;
}
template <class DataType>
void linkList<DataType>::reversePrint(node<DataType>* p)
{
if (p != NULL) {
reversePrint(p->next);
cout << p->data << " ";
}
}
int main()
{
linkList<int> L;
node<int>* p = L.getFirst()->next;
if (p == NULL)
cout << "Empty" << endl;
else
L.reversePrint(p);
L.~linkList();
return 0;
}
12.删除单链表中大于minK且小于maxK的元素
已知单链表中各结点的元素值为整型且自增有序，设计算法删除单链表中大于minK且小于maxK的所有元素，并释放被删结点的存储空间。
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct node {
DataType data;
node* next;
}node;
node* first;
void init()
{
first = new node;
first->next = NULL;
node* rear = first;
int length;
cin >> length;
for (int i = 0; i < length; ++i) {
DataType elem;
cin >> elem;
node* s = new node;
s->data = elem;
s->next = NULL;
rear->next = s;
rear = s;
}
}
void deleteList(DataType minK, DataType maxk)
{
node* p = first;
node* q = first->next;
while (q != NULL)
{
if (q->data > minK && q->data < maxk){
p->next = q->next;
delete q;
q = p->next;
}
else{
p = p->next;
q = p->next;
}
}
}
void show()
{
node* p = first->next;
if (p == NULL) cout << "Empty";
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main()
{
init();
DataType minK, maxK;
cin >> minK >> maxK;
deleteList(minK, maxK);
show();
return 0;
}13.双循环链表是否对称
判断带头结点的双循环链表是否对称。
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct node{
DataType data;
node* next,*prior;
}node;
node* first;
void init( )
{
first = new node;
first->next = NULL;
first->prior = NULL;
node* rear = first;
DataType elem;
while(cin>>elem){
node* s = new node;
s->data = elem;
s->next = NULL;
s->prior = rear;
rear->next = s;
rear = s;
}
rear->next = first;
first->prior = rear;
}
bool equalDulList()
{
node* p = first->next;
node* q = first->prior;
while (p != q && p->prior != q)
{
if (p->data == q->data)
{
p = p->next;
q = q->prior;
return true;
}
else
{
return false;
}
}
return true;
}
void show()
{
node* p = first->next;
while(p != first){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
int main()
{
init();
//show();
bool res = equalDulList();
if(res) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
14.单链表应用：八进制求和
假设用不带头结点的单链表表示八进制数，例如八进制数536表示成如图所示单链表。要求写一个函数Add，该函数有两个参数A和B，分别指向表示八进制的单链表，执行函数调用Add(A,B)后，得到表示八进制A加八进制B所得结果的单链表，结果保留在单链表A中。
【输入说明】A表的长度和A表中八进制的数码；（中间用空格隔开）
B表的长度和B表中八进制的数码；（中间用空格隔开）
【输出说明】八进制A加八进制B所得结果
3
5 3 6
2
5 4
【输出样例】
612
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct node {
DataType data;
node* next;
}node;
//尾插法构造单链表
void init(node*& first, int len)
{
first = NULL;
node* rear;
for (int i = 0; i < len; ++i) {
DataType elem;
cin >> elem;
node* s = new node;
s->data = elem;
s->next = NULL;
if (first == NULL) {
first = s;
rear = first;
}
else {
rear->next = s;
rear = s;
}
}
}
//八进制A加八进制B，结果存在链表A中
void add(node* A, node* B)
{
node* p = A, * q = B;
int flag = 0;//
int sum = 0;
while (p->next != NULL && q->next != NULL) {
sum = p->data + q->data + flag;
p->data = sum % 8;
flag = sum / 8;
p = p->next;
q = q->next;
}
//A、B等长
if (p->next == NULL && q->next == NULL) {
sum = p->data + q->data + flag;
p->data = sum % 8;
flag = sum / 8;
if (flag == 1) {
node* s = new node;
s->data = flag;
s->next = NULL;
p->next = s;
}
}
//A比B短
if (p->next == NULL && q->next != NULL) {
sum = p->data + q->data + flag;
//将A中的最后一个结点元素和B中同位置的元素相加后对8取余，并将余数放入A中的最后一个结点的数据域。
p->data = sum % 8;
//记录好此时p、q所分别指向的结点元素相加后是否有进位。
flag = sum / 8;
while (q->next != NULL) {
node* s = new node;
sum = q->next->data + flag;
s->data = sum % 8;
flag = sum / 8;
s->next = NULL;
p->next = s;
p = p->next;
q = q->next;
}
if (flag == 1 && q->next == NULL) {
node* s = new node;
s->data = flag;
s->next = NULL;
p->next = s;
}
}
//A比B长
if (q->next == NULL && p->next != NULL) {
sum = p->data + q->data + flag;
p->data = sum % 8;
flag = sum / 8;
while (p->next != NULL) {
if (flag == 1) {
sum = p->next->data + flag;
p->next->data = sum % 8;
flag = sum / 8;
p = p->next;
}
else
break;
}
if (flag == 1 && p->next == NULL) {
node* s = new node;
s->data = flag;
s->next = NULL;
p->next = s;
}
}
}
void reverseList(node*& first)
{
node* q = first, * p = first;
if (first == NULL) {
return;
}
else {
while (p->next != NULL) {
p = p->next;
}
first = p;
p = q->next;
while (q != first) {
q->next = first->next;
first->next = q;
q = p;
p = p->next;
}
}
}
void show(node* first)
{
node* p = first;
if (p == NULL) cout << "Empty";
else {
while (p != NULL) {
cout << p->data;
p = p->next;
}
cout << endl;
}
}
int main()
{
node* A, * B;
int aLen, bLen;
cin >> aLen;
init(A, aLen);
cin >> bLen;
init(B, bLen);
reverseList(A);
reverseList(B);
add(A, B);
reverseList(A);
show(A);
return 0;
}