数据结构2_线性表

《数据结构2_线性表》由会员分享，可在线阅读，更多相关《数据结构2_线性表（93页珍藏版）》请在金锄头文库上搜索。

1、第二章 线性表内容提要n本课主题： 线性表的类型定义,线性表的顺序表示和实 现,线性表的链式表示与实现，循环链表与双向链表n教学目的： 掌握线性表的概念和类型定义,掌握线性表 的顺序表示和实现方法,掌握线性链表、单链表、静态 链表的概念、表示及实现方法，掌握循环链表的概念 ，掌握双向链表的的表示与实现n教学重点： 线性表的类型定义,线性表的顺序表示和实 现方法,线性链表之单链表的表示及实现方法，双向链 表的表示与实现n教学难点： 线性链表的概念，双向链表的存储表示本章的主要内容n1.线性结构的特点和术语n2.顺序表线性结构的顺序表示n3.链表线性结构的链式表示n4.关键算法(插入、删除)，经典

2、算法(并集 、归并)2.1 线性表的定义n一、线性表的概念n线性表：n个数据元素的有限序列。数据元素可以是字符、数字、图片等。2.1.1线性表的概念n数据元素也可由若干个数据项组成。这 时常把数据元素称为记录。含有大量记 录的线性表又称文件。2.1.1前驱、后继n几个概念：nai是ai+1的直接前驱元素(简称前驱)nai+1是ai的直接后继元素(简称后继)线性结构的特点n在数据元素的非空有限集中：n存在唯一的被称做“第一个”的数据元素；n存在唯一的被称做“最后一个”的数据元素；n除第一个数据元素之外，集合中的每个数据 元素均只有一个前驱；n除最后一个数据元素之外，集合中每个数据 元素均只有一个

3、后继。2.1.1表长、空表、位序n线性表中元素的个数n称为线性表的长度 ，表长为0的线性表称为空表。n在非空表中的每个数据元素都有一个确 定的位置。ai是第i个元素，把i称为数据 元素ai在线性表中的位序(注意不是数组 下标，建议变量按位序来定义)。2.1.2线性表的类型定义n1、抽象数据类型“线性表”的定义如下： ADT List数据对象: D=ai | ai ElemSet,i=1,2,.,n,n=0数据关系: R1=| ai-1, ai D, i=2,.,n /根据该 形式定义可知该结构是线性表！你能注意到这个细 节吗？基本操作： ADT List 2.1.2线性表的类型定义基本操作：

4、/这些基本操作是根据日常需要抽象出来的 InitList( Lb_len=ListLength(Lb);for(i=1;i L=(a8-a3)/5 a38=a3+35L= a38=7a8-6a3 p=a3+(n-3)L = n=(5p+3a8-8a3)/(a8-a3)2.2.1线性表的定义和特点n线性表的这种机内表示称做线性表的顺 序存储结构或顺序映象。采用顺序存储 结构的线性表称为顺序表。n顺序表的特点：n逻辑上相邻的元素其存储位置也相邻。n顺序表(而非线性表)是一种可随机存取的存 储结构。2.2.2顺序表的存储结构n提问：线性结构的数据和关系如何存储 ？n基于静态数组的顺序表n基于动态数组

5、的顺序表2.2.2顺序表的存储结构2.2.2顺序表的存储结构n提问： 空表的判断条件：nL.length=0。注意不是elem=NULL。n提问：顺序表和数组的区别：n顺序表是结构体，数组不是结构体；线 性表大小可变，属动态结构，数组大小 不变，属于静态结构；线性表支持插入 、删除、构造等操作，数组只有取元素 、修改元素的操作。 2.2.3顺序表操作的类C语言实现n顺序表的实现(编程技巧)：n如图，线性表有四个基本要素：数组空 间，基地址，表长，分配的空间的大小 。它们四个在一起才能完整描叙一个线 性表！设计任何算法时都请参见该图， 依次看看四要素应分别如何处理。n线性表在使用前要初始化(构造

6、空表)，来 初始化这四个要素，使其是一个合理的 整体。这一点与指针有点象。2.2.3.初始化n1.初始化顺序表： Status InitList(List if(!L.elem) exit(OVERFLOW); /存储分配失败 L.length=0; L.listsize=LIST_INIT_SIZE; /分配初始空间 return OK; 2.2.3.销毁n2.销毁顺序表Status DestroyList(List /释放动态内存L.elem=NULL;L.length=0;L.listsize=0;return OK; 2.2.3.插入n3.顺序表的插入操作Status ListInse

7、rt(List /健壮的程序。插入范围1length+1 if(L.length=L.listsize)/空间不够，需要追加空间 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLOW);/健壮的程序。 L.elem=newbase; L.listsize+=LISTINCREMENT; q= /q为第i个元素的地址 for(p= p=q; -p)*(p+1)=*p; /从后向前移动元素，p的指向从第lengthi个元素 *q=e;/在第i

8、个位置插入元素 +L.length; return OK; /ListInsert提问：本算法时间复杂度？空间如满则插入 范围是1length对吗？直接在表尾插呢？2.2.3.删除n4.顺序表的删除操作2.2.3.删除Status ListDelete(List /健壮的程序。删除范围1lengthp= /q为第i个元素的地址e=*p; /注意先通过形参带回被删元素的值，然后再移动元素！for(p+, q= p=q; p-) /从后向前搜索 ,q为终点位置if(*compare)(*p, e) return p-q+1; /为什么是p-q+1?return 0; /注意前面没有else n更快

9、的算法参见第九章 基于监视哨的查找算法 提问：本算法时间复杂度？如果从前向后搜索呢 return L.length-q+p; 如何能找到多个元素呢？2.2.3.归并n6.有序顺序表的归并操作 void MergeList(List La, List Lb, List pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem) exit(OVERFLOW);pa=La.elem; pa_last=pb=Lb.elem; pb_last=while(padata = a1元素， head-next = inext)

10、printf(*p);2.3.3.初始化n1.初始化操作(创建空表，课本没有) Status InitList(LinkList /申请头结点，初始化头指针if (L=NULL) exit(OVERFLOW);L-next=NULL; /初始化头结点return OK; n2.销毁操作错误算法void DestroyList(LinkList p!=NULL; p=p-next) free(p); L=NULL; n2.销毁操作(课本没有)void DestroyList(LinkList /循环变量p首先指向头结点while(p!=NULL) q=p; p=p-next; free(q);

11、/最后两句不能颠倒顺序， 且头结点也要销毁。注意p=p-next语句的使用技巧L=NULL; 2.3.3.插入n3.插入操作n3.插入操作 Status ListInsert(LinkList p!=NULL; p=p-next, j+) /注意从头结点开始if(j=i-1) break; /寻找前驱。p为循环变量，j为计数器if(p=NULL) return ERROR; /退出循环有两种可能：p=NULL 和j=i-1。前者说明i表长+1，表明参数i非法；否则找到前驱。 注意判断条件不能改为if(j!=i-1)当i=length+2时，退出循环 时j=length+1，此时j=i-1，程序

12、出错！s=(LNode*)malloc(sizeof(LNode); /生成新结点s-data=e; s-next=p-next; /初始化新结点p-next=s; /修改前驱、插入新结点return OK; /ListInsert_LnP29插入操作(略改P29算法，把while-for) Status ListInsert(LinkList p!=NULL /从头结点 开始寻找前驱。 p为循环变量 ，j为计数器。注意循环体空if(p=NULL | ji-1) return ERROR; /退出循环有三种可能： p=NULL，表明：i表长+1；ji-1，表明：idata=e; s-next=

13、p-next; /初始化新结点p-next=s; /修改前驱、插入新结点return OK; /ListInsert_L算法时间复杂度？表头、表尾插入元 素呢？如何在有序表中插入元素？n表头插入元素 Status ListInsertFirst(LinkList /生成新结点s-data=e; s-next=L-next; /初始化新结点L-next=s; /修改前驱、插入新结点return OK; n表尾插入元素 Status ListAppend(LinkList p-next!=NULL; p=p-next) ; /寻找前驱,从头结点到表尾元素s=(LNode*)malloc(sizeo

14、f(LNode); /生成新结点s-data=e; s-next=p-next; /初始化新结点p-next=s; /修改前驱、插入新结点return OK; 两算法时间复杂度 ？2.3.3.插入2.3.3.插入算法总结n插入算法总结： (1)查找前驱，注意判断条件 (2)生成新节点 (3)修改新节点 (4)修改前驱、后继 (5)修改头指针2.3.3.删除n4.删除操作n4.删除操作(略改P30算法，把while-for) Status ListDelete(LinkList p-next!=NULL /寻 找前驱，从头结点到倒数第二个元素。注意循环体空if(p-next=NULL | ji-

15、1) return ERROR; /退出循环有三种可 能：p-next=NULL(p指向尾节点)，表明i表长；ji-1，表明 ：inext=NULL而不是p=NULLq=p-next; /p指向前驱，q指向第i个结点，暂存该指针p-next=q-next; /修改前驱e=q-data; free(q); /释放结点return OK; /ListDelete_L时间复杂度？删除表头、表尾 元素呢？有序表中删除元素呢 ？n删除首元素 Status ListDelete(LinkList /暂存首元素指针q if(q=NULL) return ERROR; /空表返回错误 L-next=q-next; /修改前驱 free(q); n删除表尾元素 Status ListDelete(LinkList for(p=L, q=p-next; q-next!=NULL; p=q, q=q-next) ; /寻找前驱p p-next=NULL; /修改前驱,即倒数第2个元素 free(q); 2.3.3.删除两算法时间复杂度 ？2.3.3.删除算法总结n删除算法总结： (1)查找前驱，注意判断条件 (2)暂存当前节点的指针 (3)修改前驱、后继 (4)修改头指针 (5)释放当前节点2.3.3.查找n5.查找元素的操作(课本没有，本程序未按类C 语言规则写) i