线性链表2.4 数组

2.3线性链表及其运算线性表的顺序存储结构容易实现，可以随机存取表中的任意元素。顺序表缺点是：难于插入、删除操作；需要预先分配空间，不管这些空间能否最大限度地利用。链表存储结构在这两个方面恰好是优点：容易插入、删除操作不需要预分空间。链表基本概念定义：线性表的链式存储结构称为线性链表

结点（NODE）：表中元素的存储单元。由数据域和指针域组成。数据域存放元素数据，指针域存放指向下一结点位置的指针。结点形式为：

datanext数据域指针域链表（Link）：由结点组成的表。头指针（head）：指向链表中第1个结点的指针。举例由食品组成的单链表（biscuit,butter,cheese,eggs,grapes,jam)

grapesbiscuitbuttercheesejameggs^head

头指针最后一个结点指针域为空单链表的物理存储

存储地址数据域（data）指针域（next）grapes60biscuit61cheese13eggs1jamNULLbutter121111213606111头指针

head（biscuit,butter,cheese,eggs,grapes,jam)线性链表类P57Template<classT>

structnode{Tdata;node*next;};Template<classT>classlinked_list{private:node<T>*head;public:linked_list();//建立空链表

intflag_linked_list();//判断链表状态

{if(head==NULL)return0;return1;}voidprt_linked_list();//从头指针开始输出

voidins_linked_list(T);//插入到链表头

Tdel_linked_list();//删除链头}参考P58课堂练习P58例子2.12定义一个空链表，依次插入1-100打印输出；然后删除前50个结点，并再次输出。

带链的栈栈也是线性表，可以采用链式存储结构顺序栈最多可用于2个栈的共享，对于更多的栈就难于表达了。对于最大空间需要量事先不知的情况，就不能使用顺序栈了。这时，就需要采用链栈。链栈：栈的链式存储结构链栈示意图a1a2a3^栈底top栈顶…...aiTemplate<classT>structnode{Tdata;node*next;};template<classT>classlinked_Stack{private:node<T>*top;

//栈顶指针

栈的链式表示—链栈public: linked_stack(); voidprt_linked_stack();intflag_linked_stack();voidins_linked_stack(T);Tdel_linked_stack(); Tread_linked_stack();}

链栈为空的条件：

top=NULL

链栈为满的条件(无法继续申请新结点):t=NULLt为申请的结点,为NULL表示失败。

链栈进栈操作操作步骤:step1：申请一个链栈结点，若t=NULL，则表示链满；否则，执行step2；step2：在top所指结点之前插入新结点，并将top指向新申请的结点t。template<classT>

voidlinked_Stack<T>::

ins_linked_stack(Tx){node<T>*p=newnode<T>;if(p==NULL)return;p->data=x;p->next=top;top=p;}链栈进栈算法链栈出栈操作操作步骤:step1若链栈为空，则输出栈溢出信息；否则，执行step2。step2(保存top)并使top指向被删除结点的后件结点，删除top所指结点。step3释放被删除结点的存储空间。返回出栈元素值。template<classT>

Tlinked_Stack<T>::del_linked_stack(){Ty;node<T>*q;if(top==NULL){cout<<“空栈”<<endl；

return0;}q=top;y=q->data;top=q->next;deleteq;return(y);}课堂练习P62,参考2.13;建立空栈，入栈10,20,30,40,50；退栈2次，然后输出栈中所有的元素；4带链的队列1).队列也是线性表，可以采用链式存储结构。datanext数据域指针域2).存储结构的C++语言描述，template<classT>//模板声明，数据元素虚拟类型为Tclasslinked_Queue//循环队列类{private://数据成员

intmm;//存储空间容量

node<T>*front;//排头指针

node<T>*rear;//队尾指针public://成员函数

linked_Queue(int);//构造函数，建立空循环队列

voidprt_linked_Queue();//输出排头与队尾指针以及队中元素

intflag_linked_Queue();//检测循环队列的状态

voidins_linked_Queue(T);//入队

Tdel_linked_Queue();};//退队链队列为空的表示链队列为空，

Queue.front=Queue.rear表示形式：

front

rearfront

rear

^...ana2a1链队满的条件为:T=NULL。T为新创建的结点,非空队列:NULL链队列的入队操作要求：在链队列中插入一个元素x（入队运算）。

算法操作步骤:

Step1：申请建立一个新结点p；Step2：判别p是否为空；若空，表示队列已满；Step3：非空，将p插入链中，修改rear指针。template<classT>//入队T linked_Queue<T>::ins_linked_Queue(Tx){

node<T>*p;p=newnode<T>;if(p==NULL){cout<<“队列已满\n”);return(0);}p->dada=x;p->next=NULL;if（rear==NULL）

front=p;elserear->next=p;rear=p;return;}

链队列的出队操作出队操作要考虑两种情况:当队列长度为1时，除了修改队头指针外，还要修改队尾指针。QueueQueuefrontrearrearfronta1

an

^a1a2

...a2

^...an

^

当队列长度大于1时,只修改队头指针即可Queuean^rearQueuefrontrearTfrontNULL链队列的出队操作要求：在链队列中删除一个元素（退队运算）。算法描述:Step1：判别队列是否为空；若空，则显示队列‘下溢’；Step2：非空，则判别队列长度是否为1；

Step2.1：不为1，修改头指针；

Step2.2：为1，则修改头、尾指针；Step3：释放T。

template<classT>//出队Tlinked_Queue<T>::del_linked_Queue(){Ty;node<T>*q;if(front==NULL){cout<<“队列已空\n”);return(0);}y=front->data;q=front;front=q->next;deleteq;if(front==NULL)rear=NULL;return(y);}课堂练习P65例子2.14建立空队列，插入1-100；作40次退队操作；打印输出；2.3.2线性链表基本运算1.单链表的查找find2.单链表的的插入insert3.单链表的删除delete

指针的基本操作设指针变量p、q的定义为：NODE*p，*q；对链表的操作实际上是对指针的操作。例如，要删除结点ai，首先要使指针p指向ai，即：a1......headaian^p指针p是存储单元的地址，地址内的内容可以通过p->data得到，指向下个元素的指针用p->next得到

指针的基本操作列表p=（NODE*）malloc（sizeof（NODE））申请一个结点空间，并将地址送入p中。free（p）释放p指针所指结点的空间p=q指针p指向指针q所指的结点p=q->next指针p指向指针q所指结点的后件p=p->next指针p向后移动一个结点p->next=q将指针q所指结点改接为指针p所指结点 的后件p->next=NULL将指针p所指结点与后件结点断开

线性链表的查找算法要求：在头指针为HEAD的非空线性链表中寻找包含元素x的前一个结点p

算法操作步骤:step1初始化,指针p指向头指针step2p非空且p指向的下一个元素不是x,循环step3每循环一次,p后移一个位置step4循环结束,返回指针p.template<classT>ListNode<T>*List<T>::Find(Tx){p=head;

//当前指针

p

指示第一个结点while(p->next!=NULL&&(p->next)->data!=x)p=p->next;returnp;}返回的指针p要么是指向x的前一个结点，要么指向最后一个结点

线性链表插入算法要求：在头指针为HEAD的线性链表中包含元素x的结点之前插入新元素b

算法操作步骤:step1找到x的位置,使指针p指向x的前一个结点；step2申请并生成新结点sstep3使s插入到x所在结点之前

考虑几种特殊情况：空链表，首元素为x

template<classT>voidlinked_llist<T>::del_linked_llist(Tx,Tb){node<T>*p,*q;p=newnode<T>;p->data=b;if(head==NULL){head=p;p->next=NULL;return;}if(head->dada==x){p->next=head;head=p;return;}q=head;while((q->next!=NULL)&&((q->next)->dada)!=x))q=q->next;p->next=q->next;q->next=p;return;}对于空表和第一个结点处理必须单独考虑（后面引入头结点概念）

线性链表删除算法要求：在头指针为HEAD的线性链表中删除包含元素x的结点。算法操作步骤:step1找到x的前件,使指针q指向x的前件；step2使指针p指向x所在结点；step3使p所指结点x脱链step4释放ptemplate<classT>intlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;if(head==NULL)return0;if(head->dada==x){p=head->next;deletehead;head=p;return1}q=head;while((q->next!=NULL)&&((q->next)->d!=x))q=q->next;if(q->next==NULL)return0;p=q->next;q->next=p->next;deletep;return1;}课堂练习参考P70例2.15(1)建立空线性链表(2)插入1-30；(3)输出链表；(4)将单数的节点删除；(5)再次输出链表；2.3.3循环链表和双向链表引入头节点头结点：为方便操作，在头指针和第1个结点之 间设置的结点。首元结点

第一个结点（a1）。head头指针a1首元结点

ai...第i个结点头结点空表和非空表表示形式在头结点上得到统一（任何情况下至少存在一个结点）空表的形式

:head->next=NULL

head^头结点head头结点非空表的形式:head->Next=Address引入头节点无头结点时，空表和非空表的运算不统一；链表检索只能从头指针开始，且只能顺链表方向移动。在单链表中，从表的任一结点ai找其前件结点，时间复杂度是O（n）。如果让链表首尾相接，构成环形，这就是单循环链表。如果在结点中增加一个指向前一个结点的指针域，链表可以从两个方向检索，效果更佳；这就是双向循环链表。循环单链表(1)单循环链表表示形式：headhead...a1a2an单循环链表为空的条件:head->next=head表示形式为:(2)单循环链表特点：从表中任一结点出发，均可以找到表中其它结点。找其前件结点的时间复杂度是O（n）。双向循环链表在单向循环链表中，也存在检索前件结点费时的问题（所需时间是O（n））。双向循环链表，其存储结构：template<classT>structnode{Td; node*next，*prior；

}；其它定义与单向链表相同。（1）双向循环链表结点结构指向后件结点指针域数据域指向前件结点指针域

priordatanext（2）双向循环链表表示形式双向循环链表表示形式：head^^head......ana2a1双向循环链表为空的条件:

head->prior=head->next=head表示形式为:总结:

双向循环链表特点

适合于两个方向的移动。找其前件结点的时间复杂度是O(1)。循环链表的运算特点空表与非空表统一判断链表结束的条件改变了P->next=nullP->next=head双向链表的运算要修改两个指针循环链表的插入template<classT>voidlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;p=newnode<T>;p->dada=b;

q=head;while((q->next!=head)&&((q->next)->dada)!=x))q=q->next;p->next=q->next;q->next=p;return;}循环链表的删除template<classT>intlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;q=head;while((q->next!=head)&&((q->next)->dada!=x))q=q->next;if(q->next==head)return0;p=q->next;q->next=p->next;deletep;return1;}链表存储结构的特点插入、删除操作极为方便数据非连续存放、顺序存取逻辑上相邻，物理上不一定相邻存储结构较复杂、需要额外的存储空间结论：链表存储结构适合于表中元素频繁变动的线性表。课堂练习参考P74例2.16(1)建立单向空循环链表;(2)插入1-100；(3)删除单数结点；作业P152:2.32.71.思考题：1）假设一单循环链表的长度大于1，且表中即无头结点也无头指针。已知S为指向链表中某结点的指针。试写出删除表中结点S的算法。2）假设以数组sequ[m-1]存放循环队列的元素，设变量rear和quelen分别为指示队尾元素位置和队中元素个数，试写出入队和出队算法。作业2.4数组

2.4.1

数组的顺序存储结构

2.4.2

规则矩阵的压缩

2.4.3

一般稀疏矩阵的表示

2.4.1数组的顺序存储数组是相同类型数据元素的有限集合；数组中的各个分量称为数组元素；每个数组元素值可以用数组名和一个下标值唯一地确定；数组是有限个数组元素的集合。数组中所有元素有相同的特性。每个数组元素由数组名和下标组成。每个具有下标值的数组元素有一个与该下标值对应的数组元素值。

二维数组三维数组行向量下标i页向量下标i列向量下标j行向量下标j

列向量下标k数组元素之间的关系

二维数组m行n列可以看作是m个或n个一维数组:Am×n=((a11a12…a1n),(a21a22…a2n),..(am1am2…amn))数组的操作数组有两种基本的操作：给定下标，读取相应的数组元素；给定下标，修改相应数组元素的值。数组的顺序存储结构数组元素是连续存放的，因此采用顺序存储结构。无论几维数组，在计算机中都是按一维数组来存放。数组存放通常采用两种方式：按行优先顺序(Pascal，C)按列优先顺序(Fortran)1).按行优先顺序存储结构

例如：二维数组Am×n，可以看作m个行向量，每个行向量n个元素。数组中的每个元素由元素的两个下标表达式唯一确定。地址计算公式：

LOC（aij）=LOC（a11）+（（i-1）×n+（j-1））×L

其中，L是每个元素所占的存储单元。二维数组按行优先存储举例有二维数组如下：LOC(a23)=LOC(a11)+(2-1)×4+(3-1)=7LOC(a34)=1+(3-1)×4+(4-1)=12LOC(a14)=1+(1-1)×4+(4-1)=42).按列优先顺序存储结构

按列优先顺序存放是将数组看作若干个列向量。例如，二维数组Amxn，可以看作n个列向量，每个列向量m个元素。数组中的每个元素由元素的两个下标表达式唯一确定。

地址计算公式：

LOC（aij）=LOC（a11）+（（j-1）*m+（i-1））*L

其中，L是每个元素所占的存储单元。二维数组按列优先存储举例LOC（a23）=LOC（a11）+（3-1）*4+（2-1）=10LOC（a34）=1+（4-1）*4+（3-1）=15LOC（a14）=1+（4-1）*4+（1-1）=13

有二维数组如下：2.4.2规则矩阵的压缩

实际工程问题中推导出的数组常常是高阶、含大量零元素的矩阵，或者是一些有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储。

压缩的含义是：相同值的多个元素占用一个存储单元；零元素不分配存储单元。能够采用压缩存储的矩阵对称矩阵:存储主对角线以上（下）的元素；上（下）三角矩阵:只存储三角阵元素；带状矩阵:只存储带状元素；稀疏矩阵:只存储非零元素；1下三角矩阵的压缩存储

开辟一个长度为n（n+1）/2的一维数组B，然后一行接一行地依次存放A中下三角部分的元素。以行为主压缩存储以列为主压缩存储

2对称矩阵的压缩存储

对称矩阵的元素满足：aij=aji1≤i，j≤n

因此将n*n个元素压缩存放到

n（n+1）/2个单元的一维数组S（（n+1）*n/2）中。

（按行存放）aij的地址为：对称矩阵的压缩存储举例存于一维数组S[6]S[6]=(a11,a21,a22,a31,a32,a33)123456LOC(a31)=3(3-1)/2+1=4LOC(a22)=2(2-1)/2+2=3LOC(a21)=2(2-1)/2+1=2设有A3x3矩阵:3三对角矩阵的压缩存储

在三对角矩阵中，三条对角线以外的元素均为零，并且，除了第一行与最后一行外，其他每一行均只有三个元素为非零，因此，n阶三对角矩阵共有3n-2个非零元素。对角矩阵的压缩存储以行为主存放：以列为主存放：2.4.3一般稀疏矩阵的表示如果一个矩阵中绝大多数的元素值为零，只有很少的元素值非零，则称该矩阵为稀疏矩阵。1三列二维数组表示（1）非零元素所在的行号i；（2）非零元素所在的列号j；（3）非零元素的值V。即每一个非零元素可以