数据结构之线性表课件.pptxVIP

数据结构之线性表课件

目录线性表基本概念线性表顺序存储结构线性表链式存储结构线性表应用举例线性表性能分析线性表实验与课程设计

01线性表基本概念Chapter

线性表（LinearList）是由n（n≥0）个数据元素（结点）a[0]，a[1]，…，a[n-1]组成的有限序列。除首尾元素外，每个元素有且仅有一个直接前驱和一个直接后继。线性表是一种典型的线性结构，数据元素之间存在一对一的关系。线性表定义

线性表是一种可以存储在计算机外存或内存中的数据结构，其存储方式有多种，如顺序存储、链式存储等。线性表中元素之间存在严格的逻辑顺序，即每个元素（除第一个和最后一个外）都有一个直接前驱和一个直接后继。线性表中的元素具有相同的数据类型。线性表的长度（即元素个数）可变。在定义线性表时，其长度是未定的，可以插入或删除元素。有序性同一性可变性可存储性线性表特点

03删除操作删除线性表中的指定元素。01初始化操作建立一个空的线性表。02插入操作在线性表的指定位置插入一个元素。线性表基本操作线性表中查找指定元素，并返回其位置。查找操作依次访问线性表中的每个元素。遍历操作返回线性表的长度（即元素个数）。长度操作将线性表中的所有元素删除，使其成为一个空表。清空操作线性表基本操作

02线性表顺序存储结构Chapter

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。在程序设计中，通常使用数组来实现线性表的顺序存储结构。数组是一种随机存取的数据结构，可以通过下标直接访问数组中的元素。顺序存储结构定义

优点无须为表示表中元素之间的逻辑关系而增加额外的存储空间。可以快速地存取表中任一位置的元素。顺序存储结构优缺点

缺点插入和删除操作需要移动大量元素。当线性表长度变化较大时，难以确定存储空间的容量。造成存储空间的“碎片”序存储结构优缺点

顺序存储结构实现方式一体式结构将线性表的元素和长度等信息存放在一个数组中，通过数组下标访问元素。分离式结构将线性表的元素存放在一个数组中，另外用一个变量记录线性表的长度。动态分配方式在程序运行时动态分配存储空间，根据需要动态地改变数组的大小。这种方式可以充分利用存储空间，但需要处理动态内存分配的问题。

03线性表链式存储结构Chapter

逻辑上相邻的元素在物理位置上不一定相邻，元素之间的逻辑关系是通过指针链接来实现的。每个元素包含两个部分：数据域和指针域。数据域存放数据元素的信息，指针域存放其后继元素的地址信息。链式存储结构是指用一组任意的存储单元存储线性表中的数据元素。链式存储结构定义

逻辑结构与物理结构分离，插入、删除操作不需要移动元素，只需修改指针。优点需要额外的存储空间来存储指针信息，且访问元素时需要按链表的顺序进行，不能像顺序存储结构那样随机访问。缺点链式存储结构优缺点链表每个结点只包含一个指针域，指向其后继结点。循环链表尾结点的指针域指向头结点，形成一个环状的链表结构。双链表每个结点包含两个指针域，分别指向其前驱结点和后继结点。静态链表利用数组来描述线性表的链式存储结构，数组的每个元素对应链表中的一个结点，通过游标来模拟指针的功能。链式存储结构实现方式

04线性表应用举例Chapter

问题描述：设计一个算法，实现两个一元多项式的相加。多项式采用顺序存储结构，每个多项式由一个数组表示，数组的每个元素对应多项式的一项。多项式相加问题

算法设计输入：两个一元多项式的数组表示。多项式相加问题

处理1.创建一个新的数组，用于存储相加后的多项式。2.遍历两个输入数组，将对应位置的元素相加，并将结果存入新数组中。多项式相加问题

0102多项式相加问题输出：相加后的一元多项式的数组表示。3.处理进位问题，若某一项的和超过10，则将进位加到下一项中。

问题描述：设计一个算法，实现一元多项式在给定点的求值。多项式采用顺序存储结构，每个多项式由一个数组表示，数组的每个元素对应多项式的一项。一元多项式求值问题

算法设计输入：一元多项式的数组表示和求值点x。一元多项式求值问题

处理2.遍历多项式的数组表示，对于每一项ai*x^i，计算其在x处的值ai*x^i，并累加到sum中。输出：多项式在x处的值sum。1.初始化一个变量sum为0，用于存储多项式在x处的值。一元多项式求值问题

问题描述：设有n个人围成一圈，从第一个人开始报数，每次报到m的人出列，然后从他的下一个人开始继续报数，直到所有人都出列为止。求每次出列的人的序号。约瑟夫环问题

算法设计输入：总人数n和报数上限m。约瑟夫环问题

处理1.创建一个长度为n的循环链表，表示n个人围成的圈。2.初始化一个指针prev指向链表的最后一个节点，一个指针curr指向链表的第一个节