第二章 线性表Chapter 2 Linear ListChapter 2 Linear List数据结构课程涉及数学、计算机硬件和计算机软 件 数据结构定义指互相有关联的数据元素的集合， 用D_S=( D, R ) 或 S=( D, R) 表示。表示。 数据结构内容数据的逻辑结构、存储结构和运算 算法效率指标时间效率和空间效率 要点回顾数据的逻辑结构 数据的存储结构 数据的运算线性结构 非线性结构顺序存储链式存储 线性表、栈、队列、串、数组树形结构图形结构散列存储索引存储插入、删除、修改、查找、排序等逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖于存储结构运算的实现依赖于存储结构线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构（单链表）应用实例本章内容若结构是非空有限集，则有且仅有一个开始结 点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。可表示为：（a0 , a1 , , an-1） 线性结构的定义：线性结构的特点： 只有一个首结点和一个尾结点； 除首尾结点外，其他结点只有一个直接前驱和一 个直接后继。线性结构包括线性表、堆栈、队列、字符串、数 组等等，其中，最典型最常用的是-（ a0 , a1 ai-1，ai, ai1 ，, an-1）2.1 线性表的逻辑结构 1. 线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点（首结点）ai的直接前趋ai的直接后继下标，是元素的 序号，表示元素 在表中的位置空表线性终点（尾结点）n为元素总个 数，即表长例1 分析26 个英文字母组成的英文表（ A, B, C, D, , Z）学号姓名性别年龄班级06032001李春梅女 18微电061 06032002何 鹏男 18微电061 06032003王 爽女 18微电061 06032004王亚武男 18微电061： ：例2 分析学生情况登记表每个数据元素由5个数据项组成; 元素之间的关系是线性的数据元素都是字母; 元素之间的关系是线性的同一线性表中的元素必定具有相同特性2. 线性表的基本操作vInitiate(L) 初始化操作。建立一个空线性表L。vLength(L) 求表长。求给定线性表L中数据元素的个数。vGet(L,i) 读取元素。读取线性表L中第i个数据元素。vInsert(L,i,x) 前插。在线性表L中第i个数据元素ai之前插入一个新的数据元素x。vDelete(L,i) 删除。删除线性表L中第i个的数据元素ai。vLocate(L,x) 定位函数。返回线性表L中元素值等于x的数据元素ai的序号i。2.2 线性表的顺序存储结构顺序表 一、顺序表用一组地址连续的存储单元存储线性表的各个 数据元素，称作线性表的顺序存储结构，简称顺 序表。 顺序表的特点：1. 逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元素存放位置 亦可求出（利用数组下标，参见存储结构示意图）。逻辑地址数据元素存储地址 数据元素0a0Loc(a0)a01a1Loc(a0)+Ka1iaiLoc(a0)+i*Kain-1an-1Loc(a0)+(n-1)*Kan-1线性表的顺序存储结构示意图首地址每个元素 占K字节一个一维数组，下标的范围是到 ，每个数组元素用相邻的个字节存储。存 储器按字节编址，设存储数组元素的 第一个字节的地址是98，则的第一个 字节的地址是 113例1：因此：LOC( M3 ) = 98 + 5 3=113解：地址计算通式为：LOC(ai) = LOC(a0) + L *i用c语言定义顺序表#define Maxlen 100 typedef struct char name10;char sex;int age; elemtype; elemtype ListMaxlen; int num=-1;/*定义数据类型*/*定义顺序表*/*当前数据元素下标*/*顺序表最大长度*/姓名性别年龄 张三M18 李四F19 typedef struct elemtype ListMaxlen;int num; SeqList;s s-nums-List0s-List1s-List2s-ListMaxlen-1SeqList a; SeqList *s;a.num， a.List0numList0List1用c语言定义顺序表二、顺序表的基本操作1.初始化 ListInitiate(L)void ListInitiate(SeqList *L) L-num=-1;/*num指示线性表最后一个元素的下标*/2.求表长 ListLength(L)int ListLength(SeqList L) return L.num+1; 3.取数据元素 ListGet(L，i，x)int ListGet(SeqList L,int i,elemtype *x) if(iL.num) printf(“ERROR!n”);return 0; else *x=L.Listi;return 1; Maxlen-1a0 a1 ai-1 ai ai+1an-10 1 i-1 i i+1n-1a0 a1 ai-10 1 i-1 iMaxlen-1ai+1an-1aii+1i+2na0 a1 ai-1ai ai+1an-1Maxlen-10 1 i-1 i i+1i+2nx4. 插入（在第i个（0=i;j-)aj+1=aj;ai=x;num+;注意：n表示数据元素 的个数,num是线性表 最后一个元素的下标增强健壮性int ListInsert(SeqList *L, int i, elemtype x) int j;if( iL-num+1 ) printf(“errorn”); return 0; if (L-num)=Maxlen-1) printf(“overflown”); return 0; for(j=L-num;j=i;j-)L-listj+1L-Listj;L-Listix; L-numL-num+1;return 1; 判断i是否合法判断表是否 已满若i合法，元 素后移将元素x存放在 i位置当前数据元素下 标加1用c语言描述插入算法该算法的时间复杂度：该算法的时间复杂度：E Eisis: : 插入一个元素所需平均插入一个元素所需平均移动次数移动次数: : 则则因此因此, , 该算法的时间复杂度为该算法的时间复杂度为O(nO(n) )。a0 a1 ai-10 1 i-1 iai5.删除（删除第i个（0numL-num) printf (“n the position is invalid”);return 0; else *x=L-listi; for ( j=i+1; jnum; j+) L-listj-1=L-listj;L-num-;return 1; /*删除顺序表L中的第i个 元素,并将其保存在x中*/*判断表是否为空*/*若i合法，元素依次前移*/*当前数据元素下标减1*/*判断i值是否合法*/该算法的时间复杂度：该算法的时间复杂度：E Edldl：删除一个元素所需：删除一个元素所需平均移动次数平均移动次数因此因此, , 该算法的时间复杂度为该算法的时间复杂度为O(nO(n) )。v算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数)v移动元素的个数取决于插入或删除元素的位置.顺序表时间效率分析:顺序表的空间复杂度S(n)=O(1) （没有占用辅助空间）顺序表空间效率分析:三、顺序存储结构的特点顺序表的优点： 无需为表示节点间的逻辑关系而增加额外的存储空间 可以方便地随机存取表中的任一节点顺序表的缺点： 插入和删除运算不方便,需要移动大量的数据元素。 由于要求占用连续的存储空间，存储分配只能预先进 行作业：P55 2-8 2-14(顺序表) 如何克服顺序表 的这些缺点呢？第二章 线性表1. 线性结构的特点： 2. 仅有一个首、尾结点，其余元素仅有一个直接前 驱和一个直接后继。2. 线性表逻辑结构：“一对一” 或 1:1存储结构：顺序存储、链式存储3.顺序表特征：逻辑上相邻，物理上一定相邻 优点：随机查找快 缺点：插入、删除慢；需要预先知道线性表的长度单链表基本概念单链表基本操作 线性表的链式存储结构链表循环单链表双向链表单链表初始化插入删除求元素个数取元素单链表的基本概念线性表链式存储结构的一种。用一 组不一定连续的存储单元来存放数据元 素。数据域指针域结点头指针空指针130Ahead a01475130Aa110CB1475a210CB数据元素的逻辑顺序是通过链表中的指针 连接次序来实现的。 结点结点 datanext数据域数据域指针域指针域typedef struct Node DataType data; struct Node *next; SLNode；单链表 结点的定义：2.3.1 单链表的存储结构单链表的存储结构Loc(a1)Loc(a2)Loc(an-1)Loc(a0)第2个学生信息第3个学生信息最后一个学生信息第1个学生信息逻辑示意图第2个学生信息Loc(a2)第3个学生信息Loc(a3)第n个学生信息结束标志第1个学生信息Loc(a1)物理示意图第n个 学生信息NULLNULL第1个 学生信息Loc(aLoc(a2 2) )第2个 学生信息Loc(aLoc(a3 3) )headhead 链表结构示意图带头结点的单链表12EFhead 130A12EF a01475130A a110CB1475 a210CB带头结点的空单链表headhead-next=NULL不带头结点的单链表130Ahead a01475130A a110CB1475 a210CB不带头结点的空单链表headhead=NULL头指针头结点首元结点何谓头指针、头结点和首元结点？头指针是指向链表中第一个结点（或为头结点或为 首元结点）的指针。单链表可由一个头指针唯一确定。 头结点是在链表的首元结点之前附设的一个结点； 数据域内只放空表标志和表长等信息; 首元结点是指链表中存储线性表第一个数据元素a0 的结点。 头指针头结点 首元结点 a0一个线性表的逻辑结构为：（ ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结 构用单链表表示如下，请问其头指针的值是多少？存储储地址数据域指针针域 1LI43 7QIAN13 13SUN1 19WANGNULL 25WU37 31ZHAO7 37ZHENG19 43ZHOU25例：答：头指针是指向链表 中第一个结点的指针， 因此关键是要寻找第一 个结点的地址。7ZHAOH 31头指针的值是31上例