《数据结构域算法设计ch02_1_线性表1-定义与顺序表示[1]》由会员分享，可在线阅读，更多相关《数据结构域算法设计ch02_1_线性表1-定义与顺序表示[1]（33页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,数据结构讲义,- 定义与顺序表示,信息工程学院 王晟 Email:,2018/9/11,24,2,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 线性表的逻辑结构,1. 线性表的定义：是n个数据元素的有限序列,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,2018/9/11,24,3,例1 分析26 个英文字母组成的英文表,（ A, B, C, D, , Z）,例2 分析学生情况登记表,数据元素都是记录; 元素间关系是线性,数据元素都是字母; 元素间关系是线性
2、,同一线性表中的元素必定具有相同特性,2018/9/11,24,4,线性表的抽象数据类型的定义：ADT List数据对象：D=ai|aiElemset,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitList(&l)操作结果：构造一个空的线性表LDestroyList(&l)初始条件：线性表已存在操作结果：销毁线性表L,2018/9/11,24,5,自定义 释放线性表内存,Void DestroyList(SqList *L) Free(L-elem); L-length=0; L-listsize=0; ,2018/9/11,24,6,自定义 释放链表内存
3、,全部元素都要释放，可以写为递归程序: 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;该指针还是指向原来的空间,会发生意外,2018/9/11,24,7,自定义 链表内存释放,如果从一个程序完美的角度来说，还是要释放所有结点的内存为好， 参考代码：
4、 template void LinkedList:makeEmpty() LinkedNode* ptr=head;/游标指针 LinkedNode* pre; /指向ptr前个结点的指针 while(ptr!=NULL) pre=ptr; /保存前个结点指针 ptr=ptr-link; delete pre; 一般在析构函数里调用它.,2018/9/11,24,8,自定义 C语言，free函数,遇这种情况会怎么样?,我现在知道了:用malloc申请了空间并使用之后，要用free函数释放内存空间,如果不释放的话，那块内存区等于被一直占据着,而无法被其他函数使用, 但是问题来了. 如:我用ma
5、lloc申请5个连续空间: p=(int *)malloc(5*sizeof(int); . 在使用之后,我要释放它: for(i=1;i=5;i+) free(p+); 这样就可以释放了, 但是如果我把循环该成 for(i=1;inum=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); ,2018/9/11,24,11,自定义,本例中，定义了结
6、构stu，定义了stu类型指针变量ps。然后分配一块stu大内存区，并把首地址赋予ps，使ps指向该区域。再以ps为指向结构的指针变量对各成员赋值，并用printf输出各成员值。最后用free函数释放ps指向的内存空间。整个程序包含了申请内存空间、使用内存空间、释放内存空间三个步骤，实现存储空间的动态分配。 一般我们常说的内存泄漏是指堆内存的泄漏。堆内存是指程序从堆中分配的，大小任意的（内存块的大小可以在程序运行期决定），使用完后必须显示释放的内存。应用程序一般使用malloc，realloc，new等函数从堆中分配到一块内存，使用完后，程序必须负责相应的调用free或delete释放该内存块
7、，否则，这块内存就不能被再次使用，我们就说这块内存泄漏了。,2018/9/11,24,12,ClearList(&l)初始条件：线性表已存在操作结果：置线性表L为空表ListEmpty(L)初始条件：线性表已存在操作结果：若线性表L为空表，则返回TRUE，否则返回FALSEListLenght(L)初始条件：线性表已存在操作结果：返回线性表L数据元素个数GetElem(L,i,&e)初始条件：线性表已存在（1iListLenght(L)）操作结果：用e返回线性表L中第i个数据元素的值,2018/9/11,24,13,locatElem(L,e,compare()初始条件：线性表已存在,comp
8、are()是数据元素判定函数操作结果：返回线性表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无定义,2018/9/11,24,14,ListInsert(&L,i,e)初始条件：线性表已存在（1iListLenght(L)
9、+1）操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1ListDelete(&L,i,&e)初始条件：线性表已存在（1iListLenght(L)）操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1ListTraverse(L,visit()初始条件：线性表已存在操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败ADT List,2018/9/11,24,15,上述是线性表抽象数据类型的定义，其中只是一些基本操作，另外可以更复杂。如：将两个线性表合并等。复杂的操作可用基本操作实现。 例2-2 void MergeLis
10、t(List la,List lb,list ,2018/9/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); ,2018/9/11,24,17,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：把逻辑上相邻的数据元素存储在 物理上相邻的存储单元中的存储结构。,2.2.1 顺序表的表示,2.2 线性表的顺序表示和实现,2018/9/11,24,18,线性表顺序存储特点：,1. 逻辑上相邻的数据元素
11、，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai) = LOC(a1) + L *（i-1）LOC(ai+1) = LOC(ai)+L,2018/9/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,2018/9/11,24,20,
12、一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是,113,例1,因此：LOC( M3 ) = 98 + 5 (3-0) =113,解：地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,2018/9/11,24,21,线性表的顺序存储结构定义（静态）,#define MAXSIZE 100 typedef struct ElemType elemMAXSIZE;int length; SqList;,2018/9/11,24,22,2.2.2 顺序表的实现（或操作）,数据结构基本运
13、算操作有： 初始化、插入、删除、查找、排序、修改,1）初始化： Status InitList_Sq(SqList ,2018/9/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（长度）,（数据类型*）表示指针.,
