数据结构基础

计算机最基本数据结构

计算机最基本的数据结构有四种：数组、链表、栈和队列。这些数据结构是计算机科学中最重要的概念之一，也是任何计算机程序员必须掌握的基础知识。

一、数组

数组是一种线性数据结构，它由相同类型的元素组成，这些元素按照一定的顺序排列。每个元素都可以通过索引访问，索引通常从零开始。数组在计算机科学中非常有用，因为它们可以快速访问和修改元素，而且它们的空间效率很高。

二、链表

链表也是一种线性数据结构，但与数组不同的是，链表中的元素不必按照顺序存储。链表中的每个元素都包含一个指向下一个元素的指针。这些指针将所有元素连接在一起，形成了一个链表。链表在插入和删除元素时非常高效，但是访问元素时需要遍历整个链表，效率较低。

三、栈

栈是一种后进先出（LIFO）的数据结构，它只允许在栈顶插入和删除元素。当你将一个元素压入栈中时，它就成了栈顶元素，当你从栈中弹出一个元素时，它就不再是栈顶元素。栈在计算机科学中有很多应用，例如函数调用和表达式求值。

四、队列

队列是一种先进先出（FIFO）的数据结构，它允许在队列的末尾插入元素，并从队列的前面删除元素。队列在计算机科学中也有很多应用，例如进程调度和消息传递。

总结

数组、链表、栈和队列是计算机科学中最基本的数据结构之一。它们在计算机程序中有广泛的应用，任何计算机程序员都必须掌握它们。了解这些数据结构的优缺点，可以帮助你更好地设计和实现计算机程序，提高程序的效率和可靠性。

数据结构的四种基本类型

一、引言

数据结构是计算机科学中的重要基础概念，它是指数据对象以及它们之间的关系，以及在这些对象上执行的操作。数据结构可以分为四种基本类型，包括线性结构、树形结构、图形结构和集合结构。本文将详细介绍这四种基本类型的定义、特点和应用。

二、线性结构

1.定义：线性结构是一组有序的数据元素，每个元素最多只有一个前驱和一个后继。

2.特点：线性表中的元素之间存在一对一的关系，即除了第一个和最后一个元素外，其他元素都有且仅有一个前驱和后继。

3.应用：常见的线性结构包括数组、链表、栈和队列。其中数组适用于需要频繁访问某个位置上的元素；链表适用于插入和删除操作频繁的场景；栈适用于需要实现先进后出（LIFO）策略的场景；队列适用于需要实现先进先出（FIFO）策略的场景。

三、树形结构

1.定义：树形结构是一组非线性数据元素，由若干个节点组成，节点之间存在一对多或多对多的关系。

2.特点：树形结构中的节点之间存在一对多或多对多的关系，其中只有根节点没有父节点，而其他节点都有且仅有一个父节点。

3.应用：常见的树形结构包括二叉树、平衡树和B+树。其中二叉树适用于需要快速查找某个元素的场景；平衡树适用于需要维护数据平衡性的场景；B+树适用于需要支持高效范围查询和排序的场景。

四、图形结构

1.定义：图形结构是一组非线性数据元素，由若干个顶点和边组成，顶点之间可以存在多个连接关系。

2.特点：图形结构中的顶点之间可以存在多个连接关系，其中边表示两个顶点之间的连通关系。

3.应用：常见的图形结构包括有向图、无向图和带权图。其中有向图适用于描述某些行为或事件发生先后顺序的场景；无向图适用于描述某些物品或概念之间相互关联的场景；带权图适用于需要考虑权重因素影响的场景。

五、集合结构

1.定义：集合结构是一组无序数据元素，每个元素都是唯一的。

2.特点：集合结构中的元素之间没有任何顺序关系，且每个元素都是唯一的。

.

复习提纲

第一章 数据构造概述

根本概念与术语〔P3〕

1． 数据构造 是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科.

2． 数据 是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算 机识别的符号的集合

2．数据元素 是数据的根本单位

3．数据对象 一样性质的数据元素的集合

4．数据构造 三方面容:数据的逻辑构造.数据的存储构造.数据的操作.

〔1〕数据的逻辑构造 指数据元素之间固有的逻辑关系.

〔2〕数据的存储构造 指数据元素及其关系在计算机的表示

( 3 ) 数据的操作 指在数据逻辑构造上定义的操作算法,如插入,删除等.

5.时间复杂度分析

--------------------------------------------------------------------------------------------------------------------

1、名词解释：数据构造、二元组

2、根据数据元素之间关系的不同，数据的逻辑构造可以分为

集合、线性构造、树形构造和图状构造四种类型。

3、常见的数据存储构造一般有四种类型，它们分别是___顺序存储构造_____、___链式存储构造_____、___索引存储构造_____和___散列存储构造_____。

4、以下程序段的时间复杂度为___O(N2)_____。

int i,j,*;

for(i=0;i

for(j=0;j

*+=i;

------------------------------------------------------------------------------------------------------------------

Python程序设计语言基础知识

一、Python的基本数据类型

常见的Python基本数据类型有：整型、实型、字符串型、布尔型。具体形式如下表所示：

数据类型名 数据表示形式

整型 指数学中的整数，如1，－1，0等

实型 数学中的实数，如9.8，－2.34等

字符串型 用单引号、双引号或三引号表示，如'Python'、″中国″、″'12'″等

布尔型 也叫逻辑型，只有两种值：True和False

二、Python运算符

(1)算术运算符：**、*、/、//、%、＋、－。

(2)关系运算符：<、<＝、>、>＝、＝＝、！＝、in。

“==”表示判断，“=”表示赋值。

(3)逻辑运算符：not、and、or。

(4)Python运算符的优先级(数字越小，优先级越高)

类型 算术运算符 关系运算符 逻辑运算符

运算符 ** * / // % ＋ － > < >＝ <＝ ＝＝ ！＝ in not and or

优先级 1 2 3 4 5 6 7 8

(5)x＋＝1：将变量x的值加1，与“x＝x＋1”等价，类似还有“－＝”、“*＝”、“/＝”、“%＝”

(6)取某三位数n各个位的方法：

个位：n % 10 十位： n // 10 % 10 或n %100 // 10 百位： n //100

三、字符串

字符串是用单引号(')、双引号(″)或三引号(''')括起来的一个字符序列，起始和末尾的引号必须要一致。

1.字符串的特点

(1)字符串是不可变对象。即一旦创建了一个字符串，那么这个字符串的内容是不可改变的。

(2)通过索引来访问字符串中的字符。索引表示字符在字符串的位置，第一个元素的索引号是0，第二个元素的索引号是1，以此类推。

2.字符串的切片操作

通过字符串的切片操作可以获得字符串的一个子串。 格式为：字符串名[start：end：step]

step默认为1，表示返回下标从start到end－1的字符构成的一个子串。