《严蔚敏数据结构课件02：线性表》由会员分享，可在线阅读，更多相关《严蔚敏数据结构课件02：线性表（81页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,2.1 线性表的类型定义,线性结构的特点： 在数据元素的非空有限集中，1）有且仅有一个开始结点；2）有且仅有一个终端结点；3）除第一个结点外，集合中的每个数据元素均有且只有一个前驱；4）除最后一个结点外，集合中的每个数据元素均有且只有一个后继。 线性序列：线性结构中的所有结点按其关系可以排成一个序列，记为(a1,ai,ai+1,an),2.1 线性表的类型定义,1. 线性表 1）线性表是n(n 0)个数据元素的有限序列。 2）线性表是一种最常用且最简单的数据
2、结构。 含有n个数据元素的线性表是一个数据结构： List = (D,R) 其中：D = ai | aiD0,i=1,2,n,n0 R = N, N = | ai-1 , ai D0 , i = 2,3,n D0 为某个数据对象数据的子集 特性：均匀性，有序性（线性序列关系）,2.1 线性表的类型定义,1. 线性表 3）线性表的长度及空表 线性表中数据元素的个数n（n0）定义为线性表的长度 当线性表的长度为0 时，称为空表。 ai 是第i个数据元素，称i为ai 在线性表中的位序。,2. 线性表的基本操作 p19p20,1）InitList( char name20; char sex; int
3、 age; float score; char addr30; ;,结构体类型定义描述结构 的组织形式,不分配内存,结构体类型定义的作用域,例 struct student int num; char name20; char sex; int age; float score; char addr30; ; struct student stu1,stu2;,9.2 结构体变量的定义 先定义结构体类型，再定义结构体变量 一般形式：,struct 结构体名 类型标识符 成员名； 类型标识符 成员名； . ； struct 结构体名 变量名表列；,例 #define STUDENT struct
4、 student STUDENT int num; char name20; char sex; int age; float score; char addr30; ; STUDENT stu1,stu2;,定义结构体类型的同时定义结构体变量 一般形式：,struct 结构体名 类型标识符 成员名； 类型标识符 成员名； . 变量名表列；,例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2;,直接定义结构体变量 一般形式：,struct 类型标识符 成员名；
5、 类型标识符 成员名； . 变量名表列；,例 struct int num; char name20; char sex; int age; float score; char addr30; stu1,stu2;,用无名结构体直接定义 变量只能一次,说明 结构体类型与结构体变量概念不同 类型:不分配内存； 变量:分配内存 类型:不能赋值、存取、运算; 变量:可以 结构体可嵌套 结构体成员名与程序中变量名可相同，不会混淆 结构体类型及变量的作用域与生存期,9.3 结构体变量的引用 引用规则 结构体变量不能整体引用,只能引用变量成员,可以将一个结构体变量赋值给另一个结构体变量 结构体嵌套时逐级引
6、用,成员(分量)运算符 优先级: 1 结合性:从左向右,引用方式： 结构体变量名.成员名,9.5 结构体数组 结构体数组的定义 三种形式：,形式一: struct student int num; char name20; char sex; int age; ; struct student stu2;,形式二: struct student int num; char name20; char sex; int age; stu2;,形式三: struct int num; char name20; char sex; int age; stu2;,9.10 用typedef定义类型 功能
7、：用自定义名字为已有数据类型命名 类型定义简单形式： typedef type name;,例 typedef int INTEGER;,类型定义语句关键字,已有数据类型名,用户定义的类型名,例 typedef float REAL;,类型定义后,与已有类型一样使用,例 INTEGER a,b,c; REAL f1,f2;,说明: 1.typedef 没有创造新数据类型 2.typedef 是定义类型,不能定义变量 3.typedef 与 define 不同,define typedef 预编译时处理 编译时处理 简单字符置换 为已有类型命名,typedef定义类型步骤 按定义变量方法先写出定
8、义体 如 int i; 将变量名换成新类型名 如 int INTEGER; 最前面加typedef 如 typedef int INTEGER; 用新类型名定义变量 如 INTEGER i,j;,例 定义结构体类型 struct date int month; int day; int year; d;,例 定义结构体类型 struct date int month; int day; int year; DATE;,例 定义结构体类型 typedef struct date int month; int day; int year; DATE;,类型定义可嵌套,例 typedef struc
9、t club char name20; int size; int year; GROUP; GROUP clu1;/定义变量 typedef GROUP *PG; PG pclub;, Struct club clu1; GROUP *pclub; struct club *pclub;,GROUP为结构体类型 PG为指向GROUP的指针类型,#define LIST_MAX_LENTH 100/线性表存储空间初始分配量 typedef struct ElemType int *elem; int length; int listsize; SqList; SqList L;,2.顺序存储线
10、性表的描述,C语言中静态分配描述 p22,求置空表 Status ClearList( ,2.顺序存储线性表的描述,C语言中静态分配描述 p22,求长度 int List length( SqList L ) length= L. length; return length; ,2.顺序存储线性表的描述,C语言中静态分配描述 p22,C语言相关函数说明,Malloc函数void * malloc ( unsigned int size);作用是在内存的动态存储区分配一个长度为size的连续空间，返回一个指向该区域起始地址的指针（void类型） Free函数void free(void *p)释
11、放由p指向的内存区,初始化 Status InitList_ SqList( SqList ,2.顺序存储线性表的描述,C语言中静态分配描述 p22,2. 顺序表的描述1) C语言中动态分配描述 p22,#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; SqList; SqList L; 说明：elem数组指针指向线性表的基地址；length指示线性表的当前长度；listsize指示顺序表当前分配的存储空间大小。当空间不足时，再
12、分配的存储空间增量为 LISTINCREMENT*sizeof(ElemType),2) 几个基本操作初始化,p23算法2.3 Status InitList_SqList(SqList ,插入 p24算法2.4,函数realloc的格式及功能 格式： void *realloc(void *p,unsigned size) 功能：将p所指向的已分配内存区域的大小 改为size。 size可以比原来分配的空间大或小。,插入 p24算法2.4,Status ListInsert_sq(SqList 需将第n(即L.length)至第i个元素向后移动一个位置。注意：C语言中数组下标从0开始，则表中
13、第i个数据元素是L.elemi-1。,插入（续）,q= ,删除 p24p25算法2.5,Status ListDelete_sq(SqList return OK 需将第i+1至第L.length个元素向前移动一个位置,插入和删除算法时间分析,用“移动结点的次数”来衡量时间复杂度。与表长及插入位置有关。 插入： 最坏：i=1，移动次数为n 最好: i=表长+1，移动次数为0 平均：等概率情况下，平均移动次数n/2 删除： 最坏：i=1，移动次数为n-1 最好: i=表长，移动次数为0 平均：等概率情况下，平均移动次数(n-1)/2,查找,p25p26算法2.6 int LocateElem_S
14、q(SqList L, ElemType e) i=1; while ( i=L.length ,查找的另一种描述,i=1; p=L.elem; while (i=L.length ,合并 P26算法2.7的另外一种描述,void MergeList_Sq(SqList La,SqList Lb,SqList ,合并 P26算法2.7,void MergeList_Sq(SqList La,SqList Lb,SqList ,pa_last是自定义指针变量,*(pa+),建立,#define LIST_INIT_SIZE 100 Status CreateList_Sq(SqList ,递增插
15、入,Status OrderInsert_Sq(SqList ,递减插入,Status DeOrderInsert_Sq(SqList ,4. 顺序表的分析,1）优点 顺序表的结构简单 顺序表的存储效率高，是紧凑结构 顺序表是一个随机存储结构（直接存取结构） 2）缺点 在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。 对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。 原因：数组的静态特性造成,作业,2.a 编写程序，建立并显示一个有10个数据元素的顺序线性表。（下次课范例演示讲解） 2.2 实现顺序线性表的插入、查找、删除等 算法。,顺序表之整体概念：,elem,0,1,length-1,listsize,length,数组下标,内存状态,变量,操作算法,listsize-1,初始化操作,插入操作,删除操作,查找操作,排序操作,. . . . . .,. . .,. . .,. . .,空闲,表区,elem,顺序表有下列缺点： （1）插入、删除操作时需要移动大量元素， 效率较低
