1. 首页
  2. 文章中心
  3. 算法

第二周 顺序表线性表5.从大神那里学习到的内容

71 阅读 0 评论
我是靠谱客的博主 靓丽黄豆，最近开发中收集的这篇文章主要介绍第二周 顺序表线性表5.从大神那里学习到的内容，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

线性表

知识点补充

（一周中最煎熬、折磨人的数据结构课过去了。说实话，老师上课讲的知识结构有点问题。多数人还是第一次接触现在的内容。上课讲的算法举例跳过了最基础的线性表的创建、头文件之类的。班上只有打ACM的少数人能听得懂。讲完这些就让我们上机做顺序表的实验，写了2个小时代码，都通过不了。有点失望。）

1.线性表的定义

在这里插入图片描述
（注意：逻辑下标是从1开始的。）

如（1，2，3，1，5）

2.线性表的基本运算：

在这里插入图片描述
（ps：GetElem的e变量是形参，就是把返回值暂存在这个变量里。）
在这里插入图片描述
Locate函数值得注意。

3.顺序表

顺序表是线性表采用顺序存储结构在计算机内存中的存储方式，它由多个连续的存储单元构成，每个存储单元存放线性表的一个元素。
在这里插入图片描述

4.空间复杂度

在这里插入图片描述

(按着书上的代码敲，居然是书上自己定义的，不是库函数。无语~)

5.从大神那里学习到的内容

#include<iostream>
using namespace std;
typedef int ElemType;//定义抽象的数据类型？？？

typedef struct
{
    ElemType data[100];
    int length;
}List;

这些是书上给的。是C语言版的线性表；

 struct List
{
    int data[100];//记录表长
    int length;//存储数据
}List;

是C++版的线性表。

（ps： **typedef int ElemType;**将int改名为ElemType是为后续修改方便的目的，如果后续需要另一种类型的顺序表，你就可以直接把int改成其他的数据类型，而不用在下面一个一个改了。）

typedef是C语言里结构体常用的。

实验题的总结

第一道 顺序表

描述

设计整数顺序表的基本运算程序，并用相关数据进行测试

输入

顺序输入顺序表A的元素个数及各个元素

输出

第一行：创建顺序表A后，输出所有元素
第二行：删除第一个元素，输出删除后的所有元素
第三行：输出删除元素后顺序表的长度
第四行：在第二元素处插入一个新的元素100
第五行：输出第一个元素100所在位置

样例输入

6
1 2 3 4 0 9

样例输出

1 2 3 4 0 9
2 3 4 0 9
5
2 100 3 4 0 9
2

在敲代码之前，要搞懂一个东西。书本上的例题，所给出的**线性表基本运算函数，不是库函数！！！**要手动敲函数内容的。

#include<iostream>
using namespace std;
typedef int ElemType;//定义抽象的数据类型？？？①

typedef struct
{
    ElemType data[100];
    int length;
}List;②
int Getlength(List&l)//求线性表的长度
{
    return l.length;
}
int GetElem(List l, int i, ElemType& e)//求线性表中第i个元素
{
    if (i<1 || i>l.length)
        return 0;
    else
    {
        e = l.data[i - 1];//逻辑序号从1开始
        return 1;
    }
}
int Locate(List l, ElemType x)
{
    int i = 0;
    while (i < l.length && l.data[i] != x)
        i++;
    if (i >= l.length) return 0;
    else return (i + 1);
}
int DelElem(List& l, int i)
{
    int j;
    if (i<1 || i>l.length)
        return 0;
    for (j = i; j < l.length; j++)
        l.data[j - 1] = l.data[j];
    l.length--;
    return 1;
}
void CreateList(List& l, ElemType a[], int n)
{
    int i, k = 0;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
        l.data[k] = a[i];//L中增加一个元素
        k++;//l中元素的个数增1
    }
    l.length = k;//设置l的长度
}
void Displist(List l)
{
    int i;
    for (i = 0; i < l.length; i++)
    {
        printf("%d ", l.data[i]);
    }
    printf("n");
}
void Delete(List& A, List B)///
{
    int i, k; ElemType x,e;
    for (i = 1; i <= Getlength(B); i++)
    {
        x = GetElem(B, i,e);
        k = Locate(A, x);
        if (k > 0)DelElem(A, k);
    }
}
int InsElem(List& l, ElemType x, int i)
{
    int j;
    if (i<1 || i>l.length + 1)
        return 0;
    for (j = l.length; j >=i; j--)
        l.data[j] = l.data[j - 1];
    l.data[i - 1] = x;
    l.length++;
    return 1;
}
int main()
{
    List L;
    int n;
    cin >> n;
    int a[100];

    CreateList(L, a, n);

    Displist(L);
    DelElem(L, 1);
    Displist(L);
    cout << Getlength(L) << endl;
    InsElem(L, 100, 2);
    Displist(L);
    cout << Locate(L,100) << endl;
    return 0;
}

① typedef是抽象函数的数据类型，具体有啥作用，看大神讲解；
②先敲线性表：也就是起了名字的结构体。

第二道 课本实验

描述

设有一个顺序表L，其元素均为正整数，设计一个算法将L中所有偶数删除并存到另一个顺序表L1中，而顺序表保留原来的所有奇数。并用相关数据进行测试。

输入

输入第一行：数据长度
输入第二行：数据具体数值

输出

输出第一行：数据中包含基数
输出第二行：数据中包含偶数

样例输入

8
1 9 2 8 3 7 4 6

样例输出

1 9 3 7
2 8 4 6

#include<iostream>
using namespace std;
struct List
{
	int data[10000];
	int length;
};
void Displist(List& L)
{
	for (int i = 0; i < L.length; i++)
		cout << L.data[i] << " ";
	cout << endl;//回车的地方，不在for循环里。
}
void DelElem(List& L, int a)
{
	for (int i = a; i < L.length; i++)
		L.data[i] = L.data[i + 1];
	L.length--;
}
int main()
{
	List L, L1;
	cin >> L.length;//这种，有效率，不用打int n；
	for (int i = 0; i < L.length; i++)
	{
		cin >> L.data[i];//循环输入到线性表的data里。
	}
	L1.length = 0;
	for(int i=0;i<L.length;i++)
		if (L.data[i] % 2 == 0)//偶数余0！！！
		{
			L1.data[L1.length] = L.data[i];//
			L1.length++;
			DelElem(L, i);
			i--;//important!
		}
	Displist(L);
	Displist(L1);
	return 0;
}

L1.data[L1.length]=L.data[i]; 如果i是偶数项将被存到L1中。L1的data与length都随之改变。
L1.length一开始是0；存到一个数之后就length++；

第三道 递归

描述

输入一个数，求这个数的各位数字之和。

输入

一个整数n

输出

一个整数，为n的各数位之和

样例输入

1002

样例输出

3

要有递归的思维。不用去判断几位数、去取出每位数字，再加。
整体思路：如果是一位数（大于0小于10）直接返回。
如果是多位数，n%10为个位数上的数字，n/10是除了个位数的位数（百位、千位、万位）add(n/10)就是递归。

#include<iostream>
using namespace std;

int add(int n)
{
    if (n>=0 && n<10)
        return n;
    if (n >= 10)
        return n % 10 + add(n/10);///取余只取一次。
}
int main()
{
    int n;
    cin >> n;
    cout<<add(n)<<endl;

    return 0;
}

第四道 角谷定理

描述

角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。

输入

一个整数n。

输出

一个整数，经过转换的次数。

样例输入

3

样例输出

7

#include<iostream>
using namespace std;
int fun(int n)
{

	if (n % 2 == 0)
	{
		return n / 2;
	}
	if (n % 2 == 1)
	{
		return n * 3 + 1;
	}
}
int main()
{
	int n;
	cin >> n;
	int i = 0;
	while (n != 1)//控制次数；
	{
		n = fun(n);
		i++;
	}
	cout << i;
	return 0;
}


我写的全局变量count的怎么不行呢？？？

第五道 顺序表中删除多余元素

描述

在一个非递减有序的顺序表中删除所有值相等的多余的元素。要求时间复杂度为O（n),空间复杂度为O（1）。

输入

两行，第一行为数据元素的个数n，第二行为n个元素，n<=1000000

输出

删除多余元素后的数据序列

样例输入

10
-1 -1 1 2 2 3 3 3 4 5

样例输出

-1 1 2 3 4 5
审题要仔细，n<=1000000就是坑所以它要怎么表示呢？1e6或1e6+100之类的。
非递减有序顺序表？那就是递增喽？ 有序是怎么个有序法呢？

#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;

struct node 
{
    bool f = 0;//布尔有啥用？判断是否输出。
    int value;
}p[maxn];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i].value;
    for (int i = 1; i < n; i++)
    {
        if (p[i].value == p[i - 1].value)//如果相同的数不相邻怎么办？
            p[i].f = 1;
    }
    for (int i = 0; i < n; i++)
        if (！p[i].f)cout << p[i].value << " ";
    return 0;
}

题解：

需要注意的是：

  • 这题的数据范围非常大，如果你把顺序表开到1000或者10000，根本过不了，你还会觉得是代码有问题。这个故事告诉我们，题目要求一定要仔细看！
  • 时间复杂度O(n)决定了你不可以用运算函数删除方式，因为那种删除方式是O(n^2) 的复杂度
  • 空间复杂度O(1)决定了你不可以开新的顺序表，必须在原来的顺序表上操作
  • 所以期末考的时候还要背函数的复杂度呗。。。
    第二种代码：
#include<iostream>
using namespace std;
struct List
{
	int data[1000000];//vs上会越界也不懂为啥？
	int length;
};
void output(List&n)
{
	for (int i = 0; i < n.length; i++)
		cout << n.data[i] << " ";
	cout << endl;
}
int main()
{
	List L;
	cin >> L.length;
	for (int i = 0; i < L.length; i++)
	{
		cin >> L.data[i];
	}
	int k = 0;
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == L.data[i - 1]) continue;
		L.data[k] = L.data[i];//用下表k记录有效的数据元素。
		k++;
	}
	L.length = k;
	output(L);
	return 0;
}

（ps:用下标K记录符合条件的数据，无视无效的元素）
continue的用法：是if（满足）跳过continue之后的语句，重新循环。

第六道 删除指定区间的元素

描述

若一个线性表L采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在[x,y]之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。

输入

三行数据，第一行是顺序表的元素个数，第二行是顺序表的元素，第三行是x和y。

输出

删除元素值在[x,y]之间的所有元素后的顺序表。

样式输入

10
5 1 9 10 67 12 8 33 6 2
3 10

样式输出

1 67 12 33 2

我的代码：

#include<iostream>
using namespace std;
struct List
{
	int data[1000];
	int length;
};
void displist(List&n)
{
	for (int i = 0; i < n.length; i++)
	{
		cout << n.data[i] << " ";
	}
	cout << endl;
}
int main()
{
	List L;
	cin >> L.length;
	
	for (int i = 0; i < L.length; i++)
	{
		cin >> L.data[i];
	}
	int a, b;
	int k = 0;
	cin >> a >> b;
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] > a&& L.data[i] < b) continue;
		L.data[k] = L.data[i];
		k++;
	}
	L.length = k;
	displist(L);
	return 0;
}

最后

以上就是靓丽黄豆为你收集整理的第二周 顺序表线性表5.从大神那里学习到的内容的全部内容，希望文章能够帮你解决第二周 顺序表线性表5.从大神那里学习到的内容所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(47)

相关文章

JavaScript 面试题（十五）深拷贝和浅拷贝的区别？如何实现深拷贝？
JavaScript 面试题（十五）深拷贝和浅拷贝的区别？如何实现深拷贝？
3.奇偶数分离
3.奇偶数分离
利用顺序表调整其为左右两部分，左边的为奇数，右边的为偶数
利用顺序表调整其为左右两部分，左边的为奇数，右边的为偶数
无限循环输入任意10个整数，然后将这10个整数数列按照奇数在前、偶数在后的顺序重新排放。并要求奇偶两部分都是升序排列
无限循环输入任意10个整数，然后将这10个整数数列按照奇数在前、偶数在后的顺序重新排放。并要求奇偶两部分都是升序排列
第二周 顺序表线性表5.从大神那里学习到的内容
第二周 顺序表线性表5.从大神那里学习到的内容
NYOJ奇偶数分离
NYOJ奇偶数分离
NYOJ 11 奇偶分离
NYOJ 11 奇偶分离
数组排序,奇数在前偶数在后
数组排序,奇数在前偶数在后

评论列表共有 0 条评论

立即
投稿
返回
顶部