数据结构与算法Python语言描述
- 格式：pptx
- 大小：404.90 KB
- 文档页数：37
文档推荐
-
数据结构Python语言描述教学大纲页数:6
-
数据结构与算法Python语言描述页数:37
-
数据结构(python)知识点页数:36
-
数据结构-Python语言描述教案页数:26
下载文档原格式
合集下载
数据结构与算法python语言实现
数据结构与算法python语言实现数据结构，顾名思义，是一种组织数据的方式。
在计算机科学中，数据结构是对计算机中数据的组织、存储和访问的描述，从而使得数据能够更加高效的被利用。
算法则是指一定的计算步骤，用来解决特定类型问题的方法。
结构和算法之间的关系紧密相连，一个好的数据结构可以给出高效的算法实现，而一个好的算法可以在一定的时间内解决大规模问题。
本篇文章主要介绍数据结构与算法在Python语言中的实现。
1. 线性表线性表是一种线性结构，它是多个数据元素按照特定的顺序排列而成，如数组。
Python中列表(list)是一种内置的线性数据结构，支持常见的插入、删除、查找等操作，同时还提供了丰富的方法和函数。
2. 栈栈是一种先进后出(FILO)的结构，只能在表尾进行插入和删除操作。
Python可以用列表(list)模拟栈，列表提供了append()方法作为入栈操作，pop()为出栈操作。
3. 队列队列是一种先进先出(FIFO)的结构，只能在表头和表尾进行插入和删除操作。
在Python中，可以使用collections模块中的deque类实现队列，或者使用列表(list)的pop(0)和append()方法，不过使用deque性能更优。
4. 树树是一种非线性结构，由根节点和若干子树组成。
Python中可以用字典(dictionary)来实现一个树，其中字典的键表示节点，值表示该节点的子节点。
常用的树结构包括二叉树、平衡树等。
5. 图图是一种非线性结构，由若干个节点和它们之间的边组成。
Python中可以使用字典(dictionary)和内置的set类分别表示图的节点和边，或者使用第三方库networkx实现复杂的图算法。
以上仅是数据结构和算法在Python中的简单介绍和实现，还有许多高级数据结构和算法，如哈希表、堆等，可以通过深入学习和实践进一步掌握。
数据结构python语言描述pdf
数据结构python语言描述pdf 标题：数据结构：Python语言描述PDF引言概述：数据结构是计算机科学中的重要概念，它用于组织和管理数据，使其能够高效地被访问和操作。
Python作为一种流行的编程语言，提供了丰富的数据结构库，可以用于描述和实现各种数据结构。
本文将以Python语言为基础，探讨数据结构的基本概念和常见实现，并介绍如何使用Python描述数据结构，并将其保存为PDF文件。
正文内容：1. 数据结构基础1.1 数据结构的定义和分类1.2 数据结构的基本操作1.3 数据结构的时间复杂度分析2. 常见数据结构的Python实现2.1 数组（Array）2.2 链表（Linked List）2.3 栈（Stack）2.4 队列（Queue）2.5 树（Tree）3. 使用Python描述数据结构3.1 使用类和对象实现数据结构3.2 使用Python内置数据结构描述数据结构3.3 使用第三方库描述数据结构4. 将数据结构描述保存为PDF文件4.1 使用Python的PDF库生成PDF文件4.2 将数据结构描述转换为PDF格式4.3 添加样式和格式到PDF文件5. 数据结构的应用和扩展5.1 数据结构在算法中的应用5.2 数据结构的扩展和优化5.3 数据结构的实际应用案例总结：通过本文的介绍，我们了解了数据结构的基本概念和分类，并学习了使用Python语言描述和实现常见的数据结构。
我们还了解了如何将数据结构描述保存为PDF文件，以及数据结构的应用和扩展。
数据结构在计算机科学中起着重要的作用，掌握数据结构的概念和实现方法对于编程人员来说是至关重要的。
希望本文对读者在学习和理解数据结构方面有所帮助。
第1章 绪论(2)-数据结构教程(Python语言描述)-李春葆-清华大学出版社
f(n)是T(n)的上界
这种上界可能很多，通常取最接 近的上界，即紧凑上界
大致情况：
lim T(n) = c n→∞ f(n)
9/50
提示
本质上讲，是一种T(n) 最高数量级的比较
也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化 T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。
P(I)是I出现的概率，有 P(I) 1 ，T(I)是算法在输入I下的执行时间，则算法 IDn
的平均时间复杂度为：
A(n) P(I ) T (I ) IDn
18/50
例如，10个1～10的整数序列递增排序：
n=10 I1={1，2，3，4，5，6，7，8，9，10} I2={2，1，3，4，5，6，7，8，9，10}
3/50
1. 分析算法的时间复杂度
一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有 数据类型的操作，如+、-、*、/、++和--等）构成的。算法执行时间取决 于两者的综合效果。
一个算法的基本构成：
控制语句1 原操作
控制语句2
…
原操作
控制语句n 原操作
4/50
def solve(m,n,a): if (m != n) raise("m!=n") s=0
def fun(n): s=0 for i in range(n+1): for j in range(i+1): for k in range(j): s+=1 return s
基本操作
算法频度为：
17/50
2. 算法的最好、最坏和平均时间复杂度
定义：设一个算法的输入规模为n，Dn是所有输入实例的集合，任一输入I∈Dn，
数据结构的书
数据结构的书以下是一些常见的数据结构书籍推荐：1.《数据结构与算法分析：C语言描述》- 作者：Mark AllenWeiss 这本书以C语言为基础，详细介绍了各种数据结构和算法的实现和分析，并提供了丰富的问题和习题。
2.《算法导论》 - 作者：Thomas H. Cormen, Charles E. Leiserson,Ronald L. Rivest, Clifford Stein 这是一本经典的算法教材，涵盖全面的算法主题和各种数据结构，是算法领域的权威参考。
3.《大话数据结构》 - 作者：程杰这本书通过生动有趣的讲解方式，引入了常见的数据结构和算法，非常适合初学者入门。
4.《数据结构：高级方法与应用》- 作者：T.M. Austin 这本书提供了广泛的数据结构实现示例和应用案例，深入探讨了高级的数据结构和算法设计。
5.《数据结构与算法分析：Java语言描述》 - 作者：Mark AllenWeiss 这本书以Java为基础，介绍了数据结构和算法的实现和分析，同时提供了面向对象编程的角度来理解和应用这些概念。
6.《数据结构与算法分析 in C++》 - 作者：Mark Allen Weiss 这本书使用C++语言进行数据结构和算法的介绍，涵盖了常见的数据结构和算法的实现和分析，提供了丰富的例子和习题。
7.《算法（第4版）》- 作者：Robert Sedgewick, Kevin Wayne这本书以算法为重点，提供了全面的算法和数据结构的讲解，用Java语言实现。
讲解详细，包含大量的示例和练习。
8.《数据结构与算法：Python语言描述》- 作者：Michael T.Goodrich, Roberto Tamassia, Michael H. Goldwasser 这本书以Python作为示例代码的语言，介绍了数据结构和算法的实现，同时还关注类和对象的设计。
9.《数据结构与算法分析 in Java》 - 作者：Mark Allen Weiss 这本书使用Java语言进行数据结构和算法的介绍，对于想要用Java实现数据结构和算法的读者非常适用。
数据结构与算法Python语言描述【共37张PPT】
}
// 加工型——map操作！ void TraverseList(List &L,
void (*visit)(&ElemType)){ for (i = 0; i < L.length; i++)
(*visit)(L.elem[i]); }
// 注意引用参数的使用！！！
Status GetElem(List L, int i, ElemType &e) {
线性表的顺序表示和实现
GetElem( L, i, &e ) //取线性表中第i个数据元素
初始条件：线性表L已存在。
操作结果：依次对L的每个元素调用函数visit()。
• 直接前驱、直接后继 操作结果：用e返回L中第i个元素的值。
操作结果：若cur_e是L的元素，但不是最后一个，则用next_e
for(i = 1; i <= Lb_len; i++){
• 线性表的顺序表示和实现
• 线性表的链式表示和实现
线性表的顺序表示
• 是指用一组地址连续的存储单元依次存放线性表 的数据元素
以元素在计算机内“物理位置相邻”来表示线性表中数 据元素之间的逻辑相邻
线性表的顺序表示和实现
• 是指用一组地址连续的存储单元依次存放线性表 的数据元素
设每个数据元素需占用C个存储单元 – LOC(ai) = LOC(ai-1) + C – LOC(ai) = LOC(a1) + (i-1)×C
i = 1; p = L.elem;
//在有效范围内查询 while(i <= L.length && !(*compare)(*p++, e))
// 加工型——map操作！ void TraverseList(List &L,
void (*visit)(&ElemType)){ for (i = 0; i < L.length; i++)
(*visit)(L.elem[i]); }
// 注意引用参数的使用！！！
Status GetElem(List L, int i, ElemType &e) {
线性表的顺序表示和实现
GetElem( L, i, &e ) //取线性表中第i个数据元素
初始条件：线性表L已存在。
操作结果：依次对L的每个元素调用函数visit()。
• 直接前驱、直接后继 操作结果：用e返回L中第i个元素的值。
操作结果：若cur_e是L的元素，但不是最后一个，则用next_e
for(i = 1; i <= Lb_len; i++){
• 线性表的顺序表示和实现
• 线性表的链式表示和实现
线性表的顺序表示
• 是指用一组地址连续的存储单元依次存放线性表 的数据元素
以元素在计算机内“物理位置相邻”来表示线性表中数 据元素之间的逻辑相邻
线性表的顺序表示和实现
• 是指用一组地址连续的存储单元依次存放线性表 的数据元素
设每个数据元素需占用C个存储单元 – LOC(ai) = LOC(ai-1) + C – LOC(ai) = LOC(a1) + (i-1)×C
i = 1; p = L.elem;
//在有效范围内查询 while(i <= L.length && !(*compare)(*p++, e))
源代码--数据结构与算法(Python版)chap10 排序
20
交换类
（2）快速排序 快速排序采用分而治之(Divide and Conquer)
的策略将问题分解成若干个较小的子问题，采用 相同的方法一一解决后，再将子问题的结果整合 成最终答案。快速排序的每一轮处理其实就是将 这一的基准数定位，直到所有的数都排序完成 为止。
21
快速排序的基本步骤：
1. 选定一个基准值（通常可选第一个元素）； 2. 将比基准值小的数值移到基准值左边，形
14
• 交换类
交换类排序的基本思想是：通过交换无序序列 中的记录得到其中关键字最小或最大的记录，并将 其加入到有序子序列中，最终形成有序序列。交换 类排序可分为冒泡排序和快速排序等。
15
交换类
（1）冒泡排序 两两比较待排序记录的关键字，发现两
个记录的次序相反时即进行交换，直到没有 反序的记录为止。因为元素会经由交换慢慢 浮到序列顶端，故称之为冒泡排序。
3. 最后对这个组进行插入排序。步长的选法 一般为 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
11
【例】给定序列（11，9，84，32，92，26，58，91，35， 27，46，28，75，29，37，12 ），步长设为d1 =5、d2 =3、 d3 =1，希尔排序过程如下：
for i in range(1,len(alist)):
#外循环n-1
for j in range(i,0,-1):
#内循环
if alist[j]<alist[j-1]:
alist[j],alist[j-1]=alist[j-1],alist[j] #交换
li=[59,12,77,64,72,69,46,89,31,9] print('before: ',li) insert_sort(li) print('after: ',li)
交换类
（2）快速排序 快速排序采用分而治之(Divide and Conquer)
的策略将问题分解成若干个较小的子问题，采用 相同的方法一一解决后，再将子问题的结果整合 成最终答案。快速排序的每一轮处理其实就是将 这一的基准数定位，直到所有的数都排序完成 为止。
21
快速排序的基本步骤：
1. 选定一个基准值（通常可选第一个元素）； 2. 将比基准值小的数值移到基准值左边，形
14
• 交换类
交换类排序的基本思想是：通过交换无序序列 中的记录得到其中关键字最小或最大的记录，并将 其加入到有序子序列中，最终形成有序序列。交换 类排序可分为冒泡排序和快速排序等。
15
交换类
（1）冒泡排序 两两比较待排序记录的关键字，发现两
个记录的次序相反时即进行交换，直到没有 反序的记录为止。因为元素会经由交换慢慢 浮到序列顶端，故称之为冒泡排序。
3. 最后对这个组进行插入排序。步长的选法 一般为 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
11
【例】给定序列（11，9，84，32，92，26，58，91，35， 27，46，28，75，29，37，12 ），步长设为d1 =5、d2 =3、 d3 =1，希尔排序过程如下：
for i in range(1,len(alist)):
#外循环n-1
for j in range(i,0,-1):
#内循环
if alist[j]<alist[j-1]:
alist[j],alist[j-1]=alist[j-1],alist[j] #交换
li=[59,12,77,64,72,69,46,89,31,9] print('before: ',li) insert_sort(li) print('after: ',li)
数据结构教程python语言描述
数据结构教程python语言描述数据结构是计算机科学中研究组织和存储数据的方式，它是解决复杂问题的重要工具。
Python是一种高级编程语言，提供了许多内置的数据结构和库，使得开发者可以轻松地实现各种数据结构。
下面是一些常见的数据结构在Python中的描述和使用方法：1. 列表（List）：一组有序的元素集合。
可以使用方括号[]来创建一个列表，并使用索引访问和修改列表中的元素。
pythonmy_list = [1, 2, 3, 4, 5] # 创建一个列表print(my_list[0]) # 输出列表中的第一个元素my_list.append(6) # 添加一个元素到列表末尾2. 元组（Tuple）：一组有序的元素集合，类似于列表，但不可修改。
可以使用圆括号()来创建一个元组，并使用索引访问元组中的元素。
pythonmy_tuple = (1, 2, 3, 4, 5) # 创建一个元组print(my_tuple[0]) # 输出元组中的第一个元素3. 集合（Set）：一组互不相同的元素集合，不保留元素的顺序。
可以使用花括号{}或set()函数来创建一个集合，并使用方法操作集合。
pythonmy_set = {1, 2, 3, 4, 5} # 创建一个集合my_set.add(6) # 添加一个元素到集合中my_set.remove(2) # 从集合中删除一个元素4. 字典（Dictionary）：一种键-值对的无序集合。
可以使用花括号{}或dict()函数来创建一个字典，并使用键访问和修改字典中的值。
pythonmy_dict = {'name': 'Alice', 'age': 20, 'gender': 'female'} # 创建一个字典print(my_dict['name']) # 输出字典中键'name'对应的值my_dict['age']= 21 # 修改字典中键'age'对应的值除了以上常见的数据结构，Python还提供了其他一些数据结构和库，如堆（heapq模块），栈（collections.deque），队列（queue模块）等，开发者可以根据实际需要选择合适的数据结构。
数据结构(Python语言描述)(第2版)
数据结构(Python语言描述)(第2版)简介数据结构是计算机科学的基础概念之一，它是指在计算机中存储、组织和管理数据的方法。
数据结构通常是以一种逻辑或数学模型来描述，它能够提供高效的数据操作和存储空间的利用。
本文档是关于数据结构在Python语言中的描述的第2版。
通过学习本文档，读者将了解到Python中实现各种常见的数据结构的方法和技巧，并能够在实际项目中灵活应用。
目录本文档包括以下几个部分：1.线性数据结构1.数组 (Array)2.链表 (Linked List)3.栈 (Stack)4.队列 (Queue)2.非线性数据结构1.树 (Tree)2.图 (Graph)3.哈希表 (Hash Table)线性数据结构数组 (Array)数组是一种线性数据结构，它由一系列元素组成，每个元素都具有唯一的索引。
在Python中，可以使用列表(List)来表示数组，通过索引可以访问和修改列表中的元素。
本节将介绍数组的基本操作，包括创建、访问、修改和删除元素，以及一些常见的应用场景。
创建数组在Python中，可以使用列表(List)来表示数组。
创建一个包含有5个元素的数组，可以使用以下代码：my_array = [1, 2, 3, 4, 5]访问数组元素数组的元素可以通过索引访问。
Python中的索引从0开始，因此访问第一个元素可以使用以下代码：first_element = my_array[0]修改数组元素可以通过索引修改数组的元素。
将第一个元素修改为10，可以使用以下代码：my_array[0] =10删除数组元素可以使用del关键字删除数组中的元素。
将数组的第一个元素删除，可以使用以下代码：del my_array[0]应用场景数组在很多应用场景中被广泛应用，例如排序、查找和动态规划等。
在排序算法中，使用数组可以方便地进行排序操作。
在查找算法中，可以使用数组来存储数据，并通过索引高效地查找到所需的数据。
数据结构经典书籍
数据结构经典书籍数据结构是计算机科学中的一门基础课程，它研究如何组织和存储数据，以便能够高效地访问和操作。
在学习数据结构时，经典书籍是我们不可或缺的学习资料。
下面是我列举的一些经典的数据结构书籍，它们涵盖了各种不同的数据结构和算法，帮助读者深入理解和掌握数据结构的基本原理和应用。
1. 《数据结构与算法分析》这本书由Mark Allen Weiss编写，是数据结构领域的经典教材之一。
它介绍了各种常见的数据结构和算法，并提供了详细的分析和实现示例。
该书以清晰的语言和丰富的示意图，帮助读者理解不同数据结构的特点和应用场景。
2. 《算法导论》由Thomas H. Cormen等人编写的《算法导论》是计算机科学领域最具影响力的教材之一。
它包含了广泛的算法和数据结构内容，并提供了详细的证明和分析。
该书不仅适合作为教材使用，也是研究和实践中的重要参考资料。
3. 《数据结构与算法分析：C语言描述》这本书由Clifford A. Shaffer编写，以C语言为基础，介绍了数据结构和算法的基本概念和实现方法。
该书通过大量的示例代码和练习题，帮助读者巩固和应用所学知识。
4. 《算法（第4版）》由Robert Sedgewick和Kevin Wayne合著的《算法（第4版）》是一本全面介绍算法和数据结构的教材。
该书以Java语言为例，涵盖了各种经典算法和数据结构的实现和分析。
它还提供了大量的练习题和在线学习资源，帮助读者深入理解和应用所学知识。
5. 《数据结构与算法分析：Java语言描述》这本书由Mark Allen Weiss编写，以Java语言为基础，介绍了数据结构和算法的基本概念和实现方法。
它通过清晰的示例代码和详细的分析，帮助读者理解和应用不同数据结构和算法。
6. 《数据结构与算法分析：Python语言描述》由Clifford A. Shaffer编写的《数据结构与算法分析：Python语言描述》是一本以Python语言为基础的数据结构教材。
第7章图(2)-数据结构教程(Python语言描述)-李春葆-清华大学出版社
4/59
或者
def DFS1(G,v): print(v,end=' ') visited[v]=1 for p in G.adjlist[v]: w=p.adjvex if visited[w]==0: DFS1(G,w)
#邻接表G中从顶点v出发的深度优先遍历 #访问顶点v #置已访问标记 #处理顶点v的所有出边顶点 #取顶点v的一个邻接点w
图采用邻接矩阵为存储结构，其广度优先遍历算法如下：
from collections import deque
MAXV=100
#全局变量，表示最多顶点个数
visited=[0]*MAXV
def BFS(g,v):
#邻接矩阵g中顶点v出发广度优先遍历
qu=deque()
#将双端队列作为普通队列qu
print(v,end=" ")
#访问顶点v
visited[v]=1
#置已访问标记
qu.append(v)
#v进队
while len(qu)>0:
#队不空循环
v=qu.popleft()
#出队顶点v
for w in range(g.n):
if g.edges[v][w]!=0 and g.edges[v][w]!=INF:
#全局变量，表示最多顶点个数
#邻接表G中顶点v出发广度优先遍历 #将双端队列作为普通队列qu #访问顶点v #置已访问标记 #v进队
#队不空循环 #出队顶点v
#处理顶点v的所有出边 #取顶点v的第j个出边邻接点w #若w未访问 #访问顶点w #置已访问标记 #w进队
时间复杂度为O(n+e)。
11/59
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
它的前驱，否则操作失败，pre_e无定义。
NextElem( L, cur_e, &next_e )
//求数据元素的后继
初始条件：线性表L已存在。
操作结果：若cur_e是L的元素，但不是最后一个，则用next_e
返回它的后继，否则操作失败，next_e无定义。
GetElem( L, i, &e ) //取线性表中第i个数据元素 初始条件：线性表L已存在，且1≤i≤LengthList(L)。 操作结果：用e返回L中第i个元素的值。
线性表类型
ADT List { 数据对象：D＝{ ai | ai ∈ ElemSet, i = 1,2,...,n, n≥0 }
数据关系：R1＝{ <ai-1, ai> | ai-1, ai∈D, i = 2,...,n }
基本操作： InitList( &L ) //初始化 操作结果：构造一个空的线性表L。
– 方法：只要从LB中依次取出每个数据元素，并依值在 LA中进行查访，若不存在，则插入。
线性表类型的应用——求集合的并集
void unionSet(List &La, List Lb){
La_len = ListLength(La); Lb_len = ListLength(Lb);
for(i = 1; i <= Lb_len; i++){ GetElem(Lb, i, e); if(!LocateElem(La, e, EQUAL)) InsertList(La, ++La_len, e);
} }
线性表类型的应用——归并操作
• 题目：已知线性表LA和LB中的数据元素按值非 递减有序排列，现要求将LA和LB归并为一个新 的线性表LC，且LC中的数据元素仍按值非递减 有序排列。
– 方法：设置两个指针分别指向LA和LB的当前元素，将 数值较小的元素插入LC中。
void MergeList(List La, List Lb, List &Lc){ ClearList(Lc); // 这里假定Lc已经做过InitList操作， // ClearList之后表的空间还在！
}
while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai);
} while (j <= Lb_len) {
GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); } }
线性表的表示和实现
i = j =1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len)) { GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) {ListInsert(Lc, ++k, ai); ++i;} else {ListInsert(Lc, ++k, bj); ++j;}
LocateElem( L, e, compare() ) //定位函数 初始条件：线性表L已存在，e为给定值， compare()是元素判定函数。 操作结果：返回第1个与e满足compare关系的元素的位序。 若这样的元素不存在，则返回值为0。
ListTraverse( L, visit() ) //遍历线性表 初始条件：线性表L已存在，visit()为某个访问函数。 操作结果：依次对L的每个元素调用函数visit()。 一旦visit()失败，则操作失败。
ListEmpty( L ) //判断线性表是否为空 初始条件：线性表L已存在。 操作结果：若L不空，返回true，否则为false。
PriorElem( L, cur_e, &pre_e )
//求数据元素的前驱
初始条件：线性表L已存在。
操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回
//加工型操作：&L !!!
ClearList( &L ) //线性表置空 初始条件：线性表L已存在。 操作结果：将L重置为空表
ListInsert( &L, i, e ) //插入数据元素 初始条件：线性表L已存在，且1≤i≤LengthList(L)+1 。 操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。
• 线性表的顺序表示和实现
• 线性表的链式表示和实现
线性表的顺序表示
• 是指用一组地址连续的存储单元依次存放线性表 的数据元素
线性表的逻辑结构
尾元素
线性表
• 线性表是n个数据元素的有限序列。 • 一般形式：(a1,…,ai-1,ai,ai+1,…,an)
• 直接前驱、直接后继 • 长度：表中元素的个数n (n=0时称为空表) • 非空表中，每个元素都有一个确定的位置操作
– 结构的创建、结构的销毁：构造与析构 – 引用型（访问型）：get – 加工型（改变型）：set
2016 Fall《数据结构》
第三章 线性表
内容提要
• 线性结构 • 线性表的类型定义 • 线性表的顺序表示和实现 • 线性表的链式表示和实现
线性结构
何处用到线性结构？？？
• 学生信息表 • 通讯录 • 短信、聊天记录 • 邮件列表 • 购物清单 • 账单
线性表
首元素
相邻的元素 组成前驱与后继关系
CreatList( &L, n ) //创建 操作结果：构造一个含n个元素的线性表L。
DestroyList( &L ) //结构销毁 初始条件：线性表L已存在。 操作结果：销毁线性表L。
//引用型操作
ListLength( L ) //求线性表的长度 初始条件：线性表L已存在。 操作结果：返回L中元素个数。
ListDelete( &L, i, &e ) //删除数据元素 初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。 操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。
}ADT List
线性表类型的应用——求集合的并集
• 题目：假设利用两个线性表LA和LB分别表示两 个集合A和B，现要求一个新的集合A=A∪B。