《计算机科学与编程导论模块10》由会员分享，可在线阅读，更多相关《计算机科学与编程导论模块10（73页珍藏版）》请在金锄头文库上搜索。
1、 主要内容n线性表的定义n抽象链表类n单链表n循环链表一 线性表的定义n线性表的逻辑结构n线性表的顺序存储表示n线性表的链式存储表示1 线性表的逻辑结构n线性表是n=0个数据元素a1，a2an-1，an的 有序集合。表中每个元素ai在表中的位置仅取 决于元素本身的序号i。当1。用一组地址连续的存储单元依次存放线性表中的数据元素a1 a2 ai-1 ai an线性表的起始地址 称作线性表的基地址以“存储位置相邻”表示有序对即：LOC(ai) = LOC(ai-1) + C一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai) = LOC(a1) + (i-1)
2、C基地址逻辑地址数据元素存储地址 数据元素0k0Loc(k0)k01k1Loc(k0)+ck1ikiLoc(k0)+i*ckin-1kn-1Loc(k0)+(n-1)*ckn-1线性表的顺序存储结构示意图 元素的地址表示n假设线性表的每个元素占用C个存储单元，那么，在顺序存储结构中，线性表的第i+1个数据元素ai+1的存储位置与第i个数据元素ai的存储位置之间满足如下关系：LOC(ai+1) = LOC(ai)+CLOC(ai) = LOC(a0)+i*CLOC(a0)为线性表的首地址或基地址。 以元素在计算机内存中的“物理位置相邻” 来表示线性表中数据元素之间的逻辑关系， 只要确定了首地址，
3、线性表中任意数据元 素都可以随机存取 顺序表示法的优缺点优点：1）存储密度大、空间利用率高；2）数据元素逻辑位置相邻，物理位置也相邻。可随机存取，所以称为随机存取结构。缺点：1）插入和删除时要移动大量的元素；2）长度较大的线性表须按最大需要的空间来分配存储空间。3 线性表的链式存储表示n链式存储表示的定义n链式存储表示的实现n链式存储表示的特点 线性表的链式表示用一组地址任意的存储单元存放线性 表中的数据元素以元素(数据元素的映象) + 指针(指示后继元素存储位置)= 结点(表示数据元素 或 数据元素的映象)以“结点的序列”表示线性表 称作链表数据域指针域 结点：数据元素的存储映象，由数据域和
4、 指针域构成 设ai的存储位置为p,则ai+1的地址q是：q=p-next;a1a2a3a4a5a6an 链式存储方式 链式存储结构不要求逻辑上相邻的数据元素在物 理位置上也相邻；链表：是用一组地址任意的存储单元存放线性表 的各个数据元素，通过保存直接后继的存储位置 来表示元素之间的逻辑关系；所有的数据元素都分别保存在具有相同数据结构 的结点中,结点是链表的基本存储单位,结点与数 据元素一一对应；每个结点在链表中使用一块连续的存储空间,而 相邻结点之间不必使用连续的存储空间。 链式存储表示的特点n逻辑上相邻的元素对应的存储位置是通过指针反 映的，不要求物理上相邻。进行插入、删除运算时，只需修改
5、被插入位置指针域。n一般不预先分配好足够的存储空间以备使用，当 有元素插入时，需临时分配一个空的结点空间， 填上信息，插入到线性链表中；当某个结点不再 使用时，应将其存储空间释放。 n不足之处：每个结点设有一个指针域，存储空间 的开销较大。二 抽象链表类n线性链表的实现n抽象链表类的定义n抽象链表类中典型成员函数的实现 链式存储的实现n 数据元素的存储结构结点 结点 (表示 数据元素的映象) = 元素 + 指针(指示后继元素的存储位置)ai数据域 data指针域 next结点如果结点中只包 含一个指针域， 称为单链表n链表是动态数据结构，通过指针（链）将结点 链接在一起。结点包括两部分：数据信
6、息和链 接结点的指针；结点分为表头结点和表结点；n指向链表表头结点的指针(表头指针，也称为头 指针)；n表头结点(链表的第一个结点)，一般不存放数据 元素的信息；n表结点（数据结点，也称为结点，保存数据信 息）。 链表结点与组成n 链表的图示NULL表头指针表头结点数据结点数据结点数据结点数据结点template class ListNodepublic:ListNode( ) next = Null;/无参数，构造一个空结点ListNode(const type next=next1; /包含数据域和指针域type data; /结点的数据域ListNode *next; /结点的指针域 ;
7、datanext 链表结点类的定义n 获取表头指针；n 求链表的长度；n 寻找第i个数据元素；n 根据关键字值求数据元素在链表中的位 置；n 插入数据元素；n 修改数据元素的值；n 删除数据元素。 链表的常用操作1 抽象链表类的定义n线性链表有3种：单链表、循环链表与双向链表；n抽象出上述三种线性链表的相同点（结点、 指针和相同操作），建立一个抽象链表类， 再由此抽象链表类派生出新的链表类（单链 表和循环链表）；n采用类模板机制；n增加表头结点，统一空表和非空表的操作。 抽象链表类定义template /抽象类链表的定义 class ablist public:ListNode*GetHead
8、( ) /获得表头结 点指针 return head; /取出链表中的第i个元素type Get(int i); 抽象链表类定义/将链表中第i个结点元素值设置为xbool Set(type x, int i); /寻找数据元素值为value的结点地址 ListNode*Find1(type value); /寻找链表中第i个结点元素的地址 ListNode*Find(int i); void MakeEmpt( ); /将链表置为空表/纯虚函数，取得结点n的下一个结点位置virtual ListNode *GetNext (ListNode /纯虚函数，将新元素value插入到第i个位置vir
9、tual int Insert(type value, int i)=0; /纯虚函数，将新元素value插入到链表表头处virtual int Insert(type value)=0; /纯虚函数，将链表中第i个结点删去virtual int Remove(int i)=0; /纯虚函数，将元素值为value的结点删去 virtual int Remove(type value)=0; protected: /链表的数据成员：头指针和表长ListNode *head; int length; ;2 抽象链表成员函数的实现n设置函数：将第i个结点数据元素值设为x。 template bool
10、 ablist:Set(type x, int i) ListNode *p = Find(i); /寻找第i个结点位置if(p=NULL|p=head) /i值不合法或为空表，返回falsereturn false;elsep-data=x; /修改第i个结点的数据元素值return ture; n 取值函数：返回第i个结点的数据元素值。templatetype ablist:Get(int i) /寻找指向第i个结点位置ListNode *p=Find(i); assert (p /p不空也不为表头return p-data; /返回第i个结点的数据元素值n 清空链表：用q指向第一个结点，
11、当链表不空时，循链逐个删除，仅保留表头结点。 template void ablist:MakeEmpty() ListNode *q=head-next;int i=1; /链表不空，所以至少有一个结点while(i+ next=q-next;delete q; /循链逐个删除，仅保留表头结点q=head-next;length=0; n 搜索数据元素值为value的结点template ListNode*ablist:Find1(type value) ListNode *p=head-next;int i=1; /循环条件包含空链表的情况while (i+ data!=value)p=p
12、-next; /循链找数据元素值value的结点return p; n 定位函数：返回链表中第i个元素结点的地址 template ListNode*ablist:Find(int i) if(ilength) return NULL;if(i=0) return head; /i=0时返回表头结点的地址ListNode*p=head-next; /让检测指针p指向表中第1个结点int j=1;while(p!=NULL j+; return p; /返回第i个结点地址 三 单链表n单链表的定义n单链表类的定义n单链表常用成员函数的实现1 单链表的定义n单链表的定义n带表头结点的单链表 单链表
13、的定义n单链表用一组任意的存储单元来存储线性 表的各个数据元素，这些存储单元可以是 连续的，也可以是不连续的；n为了表示线性表中每个元素与其直接后继 元素之间的逻辑关系，单链表由一个个结 点组成，每个结点作为数据元素的存储结 构，包含数据域（data）和指针域（next ）两部分。以线性表中第一个数据元素 的存 储地址作为线性表的地址，称作线性表 的头指针。头结点a1 a2 . an 头指针头指针有时为了操作方便，在第一个结点之前 虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时， 头结点的指针域为空 线性表的n个数据元素对应的n个结点通过链接方式链接成一个链表，每个
14、结点只有一个指针域，所以称为单链表。 可以将线性表（a1，a2，a3.an-1，an）直观地表示成用指针相链接的结点序列。ai-1aia2a1ai+1nanhead 整个单链表可以由一个称为头结点的head来指出，标明单链表的首地址； 当链表为空时，head =NULL； 单链表可以由头结点指针唯一确定； 链表中任意结点的存储位置都可以从head开始，通过对链表进行遍历得到； 设p指向元素ai，则元素ai+1的地址q是：q=p-next 带表头结点的单链表n为了算法设计的方便，往往为每一个链表加上一个表头结点 。NULL表头结点表头指针head(不含数据结点的空链表)p表头指针表头结点head
15、数据结点name1NULLn带头结点的单向链表ai-1aia2a1ai+1nanheadnhead空表怎样判断带头结点的单向链表是否为空表？如果：head-next = NULL 成立，则为空表。 等价：如果：head-next != NULL 成立，则不是空表。n不带头结点的单向链表ai-1aia2a1ai+1nanheadNULLhead 空表： head=NULL怎样判断不带头结点的单向链表是否为空表？如果：head = NULL 成立，则为空表。 等价：如果：head != NULL 成立，则不是空表。n结点之间的基本关系a3a4a2a5pp-next =qrsq则下列关系成立：r-next =s=q- next-next =p- next-next-next 通过当前结点 p 要访问下一个结点，则指向下一个 结点的指针为： p-next 通过当前结点 p 要访问下一个结点的下一个： p-next-next2 单链表类的定义n单链表是简单的链表，可以直接从抽象链表类派 生出来，定义如下： class List：public ablist public：List（） /构造函数，建立一个空链表 head = new ListNode ；length = 0；/构造函数，用于通过一个现有链
