ch021线性表1-定义与顺序表.ppt

第2章 线性表,数据结构讲义,- 定义与顺序表示,信息工程学院 王晟 Email:,2019/7/11,24,2,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 线性表的逻辑结构,1. 线性表的定义：是n个数据元素的有限序列,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,2019/7/11,24,3,例1 分析26 个英文字母组成的英文表,（ A, B, C, D, , Z）,例2 分析学生情况登记表,数据元素都是记录; 元素间关系是线性,数据元素都是字母; 元素间关系是线性,同一线性表中的元素必定具有相同特性,2019/7/11,24,4,线性表的抽象数据类型的定义： ADT List 数据对象：D=ai|aiElemset,i=1,2,n,n0 数据关系：R1=|ai-1,aiD,i=2,n 基本操作： InitList(&l) 操作结果：构造一个空的线性表L DestroyList(&l) 初始条件：线性表已存在 操作结果：销毁线性表L,2019/7/11,24,5,自定义 释放线性表内存,Void DestroyList(SqList *L) Free(L-elem); L-length=0; L-listsize=0; ,2019/7/11,24,6,自定义 释放链表内存,全部元素都要释放，可以写为递归程序: typedef struct List ListType data; struct List* next; List,*PList; 可以写为： void Destroy_List(PList list) if(list) Destroy_List(list-next); free(list); list=NULL; list=NULL;是必须要加的，否则后果自负。 如不加上list=NULL;该指针还是指向原来的空间,会发生意外,2019/7/11,24,7,自定义 链表内存释放,如果从一个程序完美的角度来说，还是要释放所有结点的内存为好， 参考代码： template void LinkedList:makeEmpty() LinkedNode* ptr=head;/游标指针 LinkedNode* pre; /指向ptr前个结点的指针 while(ptr!=NULL) pre=ptr; /保存前个结点指针 ptr=ptr-link; delete pre; 一般在析构函数里调用它.,2019/7/11,24,8,自定义 C语言，free函数,遇这种情况会怎么样?,我现在知道了:用malloc申请了空间并使用之后，要用free函数释放内存空间,如果不释放的话，那块内存区等于被一直占据着,而无法被其他函数使用, 但是问题来了. 如:我用malloc申请5个连续空间: p=(int *)malloc(5*sizeof(int); . 在使用之后,我要释放它: for(i=1;i=5;i+) free(p+); 这样就可以释放了, 但是如果我把循环该成 for(i=1;i10;i+) free(p+); 这样:本来我申请了5个，但是我释放的时候，循环了10次，也就是说释放了,后面5个空间了，这样会造成什么后果呢?,2019/7/11,24,9,自定义,1. 分配内存空间函数malloc 调用形式： (类型说明符*)malloc(size) 功能：在内存的动态存储区中分配一块长度为“size“字节的连续区域。函数的返回值为该区域的首地址。 “类型说明符”表示把该区域用于何种数据类型。 (类型说明符*)表示把返回值强制转换为该类型指针。 “size”是一个无符号数。 例如： pc=(char *)malloc(100); 表示分配100个字节的内存空间，并强制转换为字符数组类型，函数的返回值为指向该字符数组的指针，把该指针赋予指针变量pc。 2. 分配内存空间函数 calloc calloc 也用于分配内存空间。 调用形式： (类型说明符*)calloc(n,size) 功能：在内存动态存储区中分配n块长度为“size”字节的连续区域。函数的返回值为该区域的首地址。 (类型说明符*)用于强制类型转换。 calloc函数与malloc 函数的区别仅在于一次可以分配n块区域。 例如： ps=(struet stu*)calloc(2,sizeof(struct stu); 其中的sizeof(struct stu)是求stu的结构长度。因此该语句的意思是：按stu的长度分配2块连续区域，强制转换为stu类型，并把其首地址赋予指针变量ps。,2019/7/11,24,10,自定义,2. 释放内存空间函数free 调用形式： free(void*ptr); 功能：释放ptr所指向的一块内存空间，ptr是一个任意类型的指针变量，它指向被释放区域的首地址。被释放区应是由malloc或calloc函数所分配的区域。 【例】分配一块区域，输入一个学生数据。 main() struct stu int num; char *name; char sex; float score; *ps; ps=(struct stu*)malloc(sizeof(struct stu); ps-num=102; ps-name=“Zhang ping“; ps-sex=M; ps-score=62.5; printf(“Number=%dnName=%sn“,ps-num,ps-name); printf(“Sex=%cnScore=%fn“,ps-sex,ps-score); free(ps); ,2019/7/11,24,11,自定义,本例中，定义了结构stu，定义了stu类型指针变量ps。然后分配一块stu大内存区，并把首地址赋予ps，使ps指向该区域。再以ps为指向结构的指针变量对各成员赋值，并用printf输出各成员值。最后用free函数释放ps指向的内存空间。整个程序包含了申请内存空间、使用内存空间、释放内存空间三个步骤，实现存储空间的动态分配。 一般我们常说的内存泄漏是指堆内存的泄漏。堆内存是指程序从堆中分配的，大小任意的（内存块的大小可以在程序运行期决定），使用完后必须显示释放的内存。应用程序一般使用malloc，realloc，new等函数从堆中分配到一块内存，使用完后，程序必须负责相应的调用free或delete释放该内存块，否则，这块内存就不能被再次使用，我们就说这块内存泄漏了。,2019/7/11,24,12,ClearList(&l) 初始条件：线性表已存在 操作结果：置线性表L为空表 ListEmpty(L) 初始条件：线性表已存在 操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE ListLenght(L) 初始条件：线性表已存在 操作结果：返回线性表L数据元素个数 GetElem(L,i,&e) 初始条件：线性表已存在（1iListLenght(L)） 操作结果：用e返回线性表L中第i个数据元素的值,2019/7/11,24,13,locatElem(L,e,compare() 初始条件：线性表已存在,compare()是数据元素判定函数 操作结果：返回线性表L中第1个与e满足关系compare()的数据元素的位序 PriorElem(L,cur_e,&pre_e) 初始条件：线性表已存在 操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义 NextElem(L,cur_e,&) 初始条件：线性表已存在 操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义,2019/7/11,24,14,ListInsert(&L,i,e) 初始条件：线性表已存在（1iListLenght(L)+1） 操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1 ListDelete(&L,i,&e) 初始条件：线性表已存在（1iListLenght(L)） 操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1 ListTraverse(L,visit() 初始条件：线性表已存在 操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败 ADT List,2019/7/11,24,15,上述是线性表抽象数据类型的定义，其中只是一些基本操作，另外可以更复杂。如：将两个线性表合并等。复杂的操作可用基本操作实现。 例2-2 void MergeList(List la,List lb,list ,2019/7/11,24,16, while(i=la_len) GetElem(la,i+,ai);ListInsert(lc,k+,ai); while(j=lb_len) GetElem(lb,j+,bj); ListInsert(lc,k+,bj); ,2019/7/11,24,17,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义： 把逻辑上相邻的数据元素存储在 物理上相邻的存储单元中的存储结构。,2.2.1 顺序表的表示,2.2 线性表的顺序表示和实现,2019/7/11,24,18,线性表顺序存储特点：,1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是： 设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L,2019/7/11,24,19,线性表的顺序存储结构示意图,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,2019/7/11,24,20,一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是,113,例1,因此：LOC( M3 ) = 98 + 5 (3-0) =113,解：地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,2019/7/11,24,21,线性表的顺序存储结构定义（静态）,#define MAXSIZE 100 typedef struct ElemType elemMAXSIZE; int length; SqList;,2019/7/11,24,22,2.2.2 顺序表的实现（或操作）,数据结构基本运算操作有： 初始化、插入、删除、查找、排序、修改,1）初始化： Status InitList_Sq(SqList ,2019/7/11,24,23,自定义,将L.elem这个指针指向一块通过malloc函数分配的内存的地址 这个内存的大小为Elemtype这个结构体的size*LIST_INIT_SIZE的乘积这么大 malloc 是用于分配指定size的内存的库函数 原型：extern void *malloc(unsigned int num_bytes); 用法：#include 或#include 功能：分配长度为num_bytes字节的内存块 说明：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。 当内存不再使用时，应使用free()函数将内存块释放。 malloc的语法是：指针名=（数据类型*）malloc（长度）,（数据类型*）表示指针.,2019/7/11,24,24,自定义 C语言函数realloc,函数简介 原型：extern void *realloc(void *mem_address, unsigned int newsize); 语法：指针名=（数据类型*）realloc（newsize）,（数据类型*）表示指针。 头文件：#include 有些编译器需要#include ，在TC2.0中可以使用alloc.h头文件 功能：先释放原来mem_address所指内存区域，并按照newsize指定的大小重新分配空间，同时将原有数据从头到尾拷贝到新分配的内存区域，并返回该内存区域的首地址。即重新分配存储器块。 返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。 注意：这里原始内存中的数据还是保持不变的。当内存不再使用时，应使用free()函数将内存块释放。,2019/7/11,24,25,2)插入 在线性表的第i个位置前插入一个元素,实现步骤： 将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满?,长度为n的线性表变为长度为n+1的线性表 （a1,a2,ai-1,ai,an）,（a1,a2,ai-1,x,ai,an）,2019/7/11,24,26,程序： Status ListInsert_sq(SqList ,顺序表插入的演示,2019/7/11,24,27,实现步骤： 将第i +1至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法?,3)删除 删除线性表的第i个位置上的元素,使：长度为n的线性表变为长度为n-1的线性表。（a1,a2,ai-1,ai,ai+1,an）,（a1,a2,ai-1,ai+1,an）,2019/7/11,24,28,Status ListDelete_sq(Sqlist ,顺序表删除的演示,删除顺序表中某个指定的元素的代码和示意图如下：,2019/7/11,24,29,4) 顺序表的合并,参见例【2-2】,2019/7/11,24,30,2.2.3 顺序表的运算效率分析,时间效率分析: 插入算法花费的时间，主要在于循环中元素的后移。但是，插入的位置是不固定的，当插入位置i=1时，全部元素都得移