线性表

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;
}

 

上一篇:vue--实现移动端导航栏效果


下一篇:学习python第(n’)天——我在看笨办法学python(参数,解包,变量)