第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频)

这篇具有很好参考价值的文章主要介绍了第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

注:笔记截图均来自王卓数据结构教学视频

线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
同一线性表中的元素必定具有相同特性,数据元素间的关系是线性关系。

线性表的逻辑特征

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

稀疏多项式的运算

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

顺序存储结构存在的问题

1、存储空间分配不灵活
2、运算的空间复杂度高

引出链式存储结构:
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

小结

1、线性表中数据元素的类型可以为简单类型,也可以为复杂类型。
2、许多实际应用问题所涉的基本操作有很大相似性,不应为每个具体应用单独编写一个程序。
3、从具体应用中抽象出共性的逻辑结构和基本操作(抽象数据类型),然后实现其存储结构和基本操作。

线性表的类型定义

抽象数据类型线性表的定义如下:
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

基本操作

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

线性表的顺序表示和实现

在计算机内,线性表有两种基本的存储结构:
顺序存储结构和链式存储结构。

线性表的顺序存储表示

线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
线性表的第1个数据元素a1的存储位置,称作线性表的起始位置或基地址。
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

多项式的顺序存储结构类型定义

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

图书表的顺序存储结构类型定义

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

线性表的顺序存储表示

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

顺序表基本操作的实现

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
以下根据教学视频用C++实现:
BOOK对象和HOME对象的建立:

class Book
{
public:
	string Name;
};

class Home
{
public:
	Home();
	~Home();
	void ClearBook();
	int ShowBookAmount();
	void addBook();
	void showBook();
	Book* bookarr;
	int length;
	int Maxlength;
};

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

Home::Home()
{
	cout << "Home构造函数执行" << endl;
	length = 0;//此处应该是从数据库读取数据,但本次案例不考虑数据库,因此直接初始化成0
	int Maxlength = 6;
	while (length>Maxlength)
	{
		Maxlength += 3;//因为是动态存储,这里表示如果初始的Book数量超过了Maxlength,则增加Maxlength直到不再超过
	}
	bookarr = new Book[Maxlength];
	cout << "Home构造函数为Book建了空间数:"<< Maxlength << endl;
}

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

Home::~Home()
{
	cout << "Home析构函数执行" << endl;
	if (bookarr != NULL)
	{
		delete[] bookarr;
	}
}

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

void Home::ClearBook()
{
	length = 0;
}

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

int Home::ShowBookAmount()
{
	return length;
}

因为老师只实现了几个典型的函数后就没有讲解,因此这里也不做过多的设计。
实现功能输出如下:
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
源代码:

/*`cin.ignore(numeric_limits<streamsize>::max(), '\n')`用于清除输入缓冲区中的字符,直到遇到换行符为止。
具体解释如下:
1.cin.ignore(numeric_limits<streamsize>::max(), '\n')`表示使用`cin.ignore()`函数来忽略输入缓冲区中的字符。
2.numeric_limits<streamsize>::max()`表示在忽略字符的数量上没有限制,可以忽略输入缓冲区中的所有字符。
3.'\n'`是指定要忽略的字符,即换行符。
通常,在用户输入不正确的内容后,我们需要清除输入缓冲区中的残留字符,以避免对后续输入产生干扰。
使用这行代码可以确保输入缓冲区中的所有无效字符都被忽略直到遇到换行符为止。这样,程序可以继续等待用户的新输入。*/

#include<iostream>
using namespace std;
#include<string>

class Book
{
public:
	string Name;
};

class Home
{
public:
	Home();
	~Home();
	void ClearBook();
	int ShowBookAmount();
	void addBook();
	void showBook();
	Book* bookarr;
	int length;
	int Maxlength;
};

Home::Home()
{
	cout << "Home构造函数执行" << endl;
	length = 0;//此处应该是从数据库读取数据,但本次案例不考虑数据库,因此直接初始化成0
	Maxlength = 6;
	while (length>Maxlength)
	{
		Maxlength += 3;//因为是动态存储,这里表示如果初始的Book数量超过了Maxlength,则增加Maxlength直到不再超过
	}
	bookarr = new Book[Maxlength];
	cout << "Home构造函数为Book建了空间数:"<< Maxlength << endl;
}

Home::~Home()
{
	cout << "Home析构函数执行" << endl;
	if (bookarr != NULL)
	{
		delete[] bookarr;
	}
}

void Home::ClearBook()
{
	length = 0;
}

int Home::ShowBookAmount()
{
	return length;
}

void Home::addBook()
{
	string bname;
	cout << "请输入书名:" << endl;
	cin >> bname;
	if (length >= Maxlength)
	{
		Maxlength += 3;
		cout << "书库已满……进行扩容->Maxlength将扩容至:" << Maxlength << endl;
		Book* temp = new Book[Maxlength];
		for (int i = 0; i < length; ++i)
		{
			temp[i] = bookarr[i];
		}
		if (bookarr != NULL)
		{
			cout << "delete[] bookarr" << endl;
			delete[] bookarr;
		}
		cout << "new Book[Maxlength]" << endl;
		bookarr = new Book[Maxlength];
		for (int i = 0; i < length; ++i)
		{
			bookarr[i] = temp[i];
		}
		if (temp != NULL)
		{
			cout << "delete[] temp" << endl;
			delete[] temp;
		}
		length += 1;
		bookarr[length - 1].Name = bname;
	}
	else
	{
		length += 1;
		bookarr[length - 1].Name = bname;
	}
}

void Home::showBook()
{
	for (int i = 0; i < length; ++i)
	{
		cout << "图书" << (i + 1) << " :" << bookarr[i].Name << endl;
	}
}

void showTable()
{
	cout << "*************************************************" << endl;
	cout << "********** 图   书   管   理   系   统 **********" << endl;
	cout << "*************************************************" << endl;
	cout << "**********  1、查询数量   2、清空书库  **********" << endl;
	cout << "**********  3、添加书籍   4、显示书籍  **********" << endl;
	cout << "**********  5、待定待定   6、待定待定  **********" << endl;
	cout << "**********  7、刷新屏幕   0、退出系统  **********" << endl;
	cout << "*************************************************" << endl;
}

int main()
{
	showTable();
	Home home;
	int pushnum;
	int bookamount;
	do {
		int availableChars = (int)cin.rdbuf()->in_avail();
		if (availableChars) 
		{
			cin.ignore(numeric_limits<streamsize>::max(), '\n');
		}
		cout << "请输入您要进行的操作>=" << endl;
		cin >> pushnum;

		if (cin.fail()) {
			cout << "您输入的不是一个整数,请重新输入:" << endl;
			cin.clear();
			cin.ignore(numeric_limits<streamsize>::max(), '\n');
			continue;
		}

		if (pushnum < 0 || pushnum>7)
		{
			cout << "您输入数字不合要求:" << pushnum << endl;
			continue;
		}
		switch (pushnum)
		{
		case 1:
			bookamount = home.ShowBookAmount();
			cout << "当前书库书籍数量为:" << bookamount << endl;
			break;
		case 2:
			cout << "执行清空书库操作……" << endl;
			home.ClearBook();
			break;
		case 3:
			cout << "执行添加书籍操作……" << endl;
			home.addBook();
			break;
		case 4:
			cout << "执行显示书籍操作……" << endl;
			home.showBook();
			break;
		case 5:
			break;
		case 6:
			break;
		case 7:
			system("cls");
			showTable();
			break;
		default:
			break;
		}
	} while (pushnum);
	cout << "欢迎下次使用,再见……" << endl;
	return 0;
}

顺序表基本操作的实现

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

顺序表上的查找操作

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

顺序表的查找算法分析:

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
顺序表插入算法的平均时间复杂度为O(n)。

顺序表的删除

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
顺序表删除算法的平均时间复杂度为O(n)。

顺序表(线性表的顺序存储结构)的特点

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构
第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构

顺序表优缺点

第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频),数据结构与算法,学习,数据结构文章来源地址https://www.toymoban.com/news/detail-554364.html

到了这里,关于第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第一百天学习记录:线性代数:行列式(宋浩板书)

    注:二阶行列式和三阶行列式以及排列和逆序数见高等数学自学向量篇中间穿插的线性代数知识点补充。 性质7(☆☆☆) 拉普拉斯 行列式相乘 行列式的计算 题外话:不知不觉已经学习了100天。坚持果然是一件特别好的东西。它能逐渐让人养成学习的习惯。希望往后能够一

    2024年02月13日
    浏览(43)
  • 第一百一十三天学习记录:C++提高:类模板(黑马教学视频)

    类模板作用: 建立一个通用类,类中的成员 数据类型可以不具体定制,用一个虚拟的类型来代表。 语法: 解释: template … 声明创建模板 typename … 表面其后面的符号是一种数据类型,可以用class代替 T … 通用的数据类型,名称可以替换,通常为大写字母 总结:类模板和函

    2024年02月16日
    浏览(38)
  • 第一百一十四天学习记录:C++提高:类模板案例(黑马教学视频)

    main.cpp代码: myarray.hpp代码: 输出: 总结:能够利用所学知识点实现通用的数组。 个人感悟:学习了这个案例之后接下来的课程就是STL了,STL其实在我工作中写代码时经常碰到,尤其是在读同事代码的时候,因为没有学过,通过自行百度获得碎片的知识导致读起来很很吃力

    2024年02月16日
    浏览(45)
  • 第一百一十六天学习记录:C++提高:STL-string(黑马教学视频)

    string是C++风格的字符串,而string本质上是一个类 string和char 区别 1、char 是一个指针 2、string是一个类,类内部封装了char*,管理这个字符串,是一个char 型的容器。 特点: string类内部封装了很多成员方法 例如:查找find,拷贝copy,删除delete替换replace,插入insert string管理char

    2024年02月15日
    浏览(46)
  • 大数据Flink(一百零二):SQL 聚合函数(Aggregate Function)

    文章目录 SQL 聚合函数(Aggregate Function) Python UDAF,即 Python AggregateFunction。Python UDAF 用来针对一组数据进行聚合运算,比如同一个 window 下的多条数据、或者同一个 key 下的多条数据等。针对同一组输入数据,Python AggregateFunction 产生一条输出数据。比如以下示例,定义了一个

    2024年02月08日
    浏览(42)
  • 一百零八、Kettle采集Kafka数据到HDFS(踩坑,亲测有效)

    Kafka到HDFS,除了用Kafka API和flume之外,还可以用kettle,最大优点是不用写代码! 版本:Kettle版本:8.2、Hadoop版本:3.1.3 前提:    详情请看鄙人的一百零一、Kettle8.2.0连接Hive3.1.2(踩坑,亲测有效) http://t.csdn.cn/mWfOC http://t.csdn.cn/mWfOC 前提一、Hadoop系列配置文件已复制到kettle路径

    2024年02月15日
    浏览(37)
  • 大数据Flink(一百零三):SQL 表值聚合函数(Table Aggregate Function)

    文章目录 SQL 表值聚合函数(Table Aggregate Function) Python UDTAF,即 Python TableAggregateFunction。Python UDTAF 用来针对一组数据进行聚合运算,比如同一个 window 下的多条数据、或者同一个 key 下的多条数据等,与 Python UDAF 不同的是,针对同一组输入数据,Python UDTAF 可以产生 0 条、1 条

    2024年02月07日
    浏览(41)
  • C/C++基础讲解(一百零一)之经典篇(打印笑脸/兔子繁殖/素数)

    很多时候,特别是刚步入大学的学子们,对于刚刚开展的计算机课程基本上是一团迷雾,想要弄明白其中的奥秘,真的要花费一些功夫,我和大家一样都是这么啃过来的,从不知到知知,懵懂到入门,每一步都走的很艰辛,课程上,大学老师基本上讲解上机实操得时间特别有

    2024年02月08日
    浏览(46)
  • 一百零六、Hive312的计算引擎由MapReduce(默认)改为Spark(亲测有效)

    一、Hive引擎包括:默认MR、tez、spark 在低版本的hive中,只有两种计算引擎mr, tez 在高版本的hive中,有三种计算引擎mr, spark, tez 二、Hive on Spark和Spark on Hive的区别 Hive on Spark:Hive既存储元数据又负责SQL的解析,语法是HQL语法,执行引擎变成了Spark,Spark负责采用RDD执行。 Spark o

    2024年02月05日
    浏览(47)
  • 客快物流大数据项目(一百零四):为什么选择Elastic Search作为存储服务

    文章目录 为什么选择Elastic Search作为存储服务 一、​​​​​​​​​​​​​​ElasticSearch简介

    2023年04月11日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包