软件技术基础：线性链表及其运算

1、2.3 线性链表及其运算,线性表的顺序存储结构容易实现，可以随机存取表中的任意元素。 顺序表缺点是： 难于插入、删除操作； 需要预先分配空间，不管这些空间能否最大限度地利用。 链表存储结构在这两个方面恰好是优点： 容易插入、删除操作 不需要预分空间,链表基本概念,定义 ： 线性表的链式存储结构称为线性链表 结点（NODE） ：表中元素的存储单元。由数据域和指针域组成。数据域存放元素数据，指针域存放指向下一结点位置的指针。 结点形式为,链表（Link）：由结点组成的表。 头指针（head）：指向链表中第1个结点的指针,举例,由食品组成的单链表（biscuit,butter,cheese,eggs

2、,grapes,jam,最后一个结点 指针域为空,单链表的物理存储,存储地址 数据域（data） 指针域（next,biscuit,butter,cheese,eggs,grapes,jam,线性链表类 P57,Template struct node T data ; node *next ; ; Template class linked_list private,node *head; public : linked_list(); /建立空链表 int flag_linked_list(); /判断链表状态 if(head = NULL )return 0; return 1; voi

3、d prt_linked_list(); /从头指针开始输出 void ins_linked_list(T );/插入到链表头 T del_linked_list(); /删除链头,参考P58,课堂练习,P58 例子 2.12 定义一个空链表，依次插入1-100 打印输出；然后删除前50个结点，并再次输出,带链的栈,栈也是线性表，可以采用链式存储结构 顺序栈最多可用于2个栈的共享，对于更多的栈就难于表达了。 对于最大空间需要量事先不知的情况，就不能使用顺序栈了。这时，就需要采用链栈,链栈：栈的链式存储结构,链栈示意图,Template struct node T data ; node *ne

4、xt ; ; template class linked_Stack private: node *top; /栈顶指针,栈的链式表示 链栈,public: linked_stack(); void prt_linked_stack ( ) ; int flag_linked_stack (); void ins_linked_stack (T); T del_linked_stack(); T read_linked_stack();,链栈为空的条件： top = NULL 链栈为满的条件(无法继续申请新结点): t = NULL t 为申请的结点,为NULL表示失败,链栈进栈操作,操作步骤

5、: step1 ：申请一个链栈结点，若t=NULL，则表示链满；否则，执行step2 ； step2 ：在top所指结点之前插入新结点，并将top指向新申请的结点t,template void linked_Stack: ins_linked_stack (T x) node *p = new node ; if(p=NULL) return; p - data = x; p - next = top; top= p;,链栈进栈算法,链栈出栈操作,操作步骤: step1 若链栈为空，则输出栈溢出信息；否则，执行step 2。 step2 (保存top)并使top 指向被删除结点的后件结点，删除

6、top所指结点。 step 3 释放被删除结点的存储空间。返回出栈元素值,template T linked_Stack: del_linked_stack() T y ; node *q; if( top = = NULL ) coutdata; top = q- next; delete q; return (y);,课堂练习,P62, 参考2.13; 建立空栈，入栈 10,20,30,40,50； 退栈2次，然后输出栈中所有的元素,4 带链的队列,1). 队列也是线性表，可以采用链式存储结构,2). 存储结构的C+ 语言描述,template /模板声明，数据元素虚拟类型为T class

7、 linked_Queue /循环队列类 private: /数据成员 int mm; /存储空间容量 node* front; /排头指针 node * rear; /队尾指针 public: /成员函数 linked_Queue(int); /构造函数，建立空循环队列 void prt_linked_Queue(); /输出排头与队尾指针以及队中元素 int flag_linked_Queue(); /检测循环队列的状态 void ins_linked_Queue(T); /入队 T del_linked_Queue(); ; /退队,链队列为空的表示,链队列为空， Queue.front

8、 = Queue.rear 表示形式,front,rear,front,rear,an,a2,a1,链队满的条件为:T = NULL。T 为新创建的结点,非空队列,NULL,链队列的入队操作,要求：在链队列中插入一个元素x（入队运算）。 算法操作步骤: Step1：申请建立一个新结点p； Step2：判别p是否为空；若空，表示 队列已满； Step3：非空，将p插入链中，修改rear指针,template /入队 Tlinked_Queue:ins_linked_Queue(T x) node *p; p = new node ; if (p=NULL) coutdada =x; p-next

9、 = NULL; if （ rear = = NULL） front =p; else rear - next =p; rear = p; return ;,链队列的出队操作,出队操作要考虑两种情况: 当队列长度为1时，除了修改队头指针外，还要修改队尾指针,Queue,Queue,front,rear,rear,front,a1,an,a1,a2,a2,an,当队列长度大于1时,只修改队头指针即可,Queue,an,rear,Queue,front,rear,T,front,NULL,链队列的出队操作,要求：在链队列中删除一个元素（退队运算）。 算法描述: Step1：判别队列是否为空；若空，

10、则显示队列下溢； Step2 ：非空，则判别队列长度是否为1； Step2.1：不为1，修改头指针； Step2.2：为1，则修改头、尾指针； Step3：释放T,template /出队 T linked_Queue:del_linked_Queue() T y; node *q; if ( front = = NULL) coutdata; q=front; front = q-next; delete q; if (front = = NULL ) rear = NULL ; return(y);,课堂练习,P65 例子 2.14 建立空队列，插入1-100； 作40次退队操作； 打印输

11、出,2.3.2 线性链表基本运算,1. 单链表的查找 find 2. 单链表的的插入insert 3. 单链表的删除delete,指针的基本操作,设指针变量p、q的定义为： NODE *p，*q； 对链表的操作实际上是对指针的操作。例如，要删除结点ai，首先要使指针p指向ai，即,指针p是存储单元的地址，地址内的内容可以通过 p-data得到，指向下个元素的指针用p-next 得到,指针的基本操作列表,p=（NODE*）malloc（sizeof（NODE） 申请一个结点空间，并将地址送入p中。 free（p） 释放p指针所指结点的空间 p=q 指针p指向指针q所指的结点 p=q-next 指

12、针p指向指针q所指结点的后件 p=p-next 指针p向后移动一个结点 p-next=q 将指针q所指结点改接为指针p所指结点 的后件 p-next=NULL 将指针p所指结点与后件结点断开,线性链表的查找算法,要求：在头指针为HEAD的非空线性链表中寻找包含元素x的前一个结点p 算法操作步骤: step1 初始化,指针p指向头指针 step2 p非空且p指向的下一个元素不是x, 循环 step3 每循环一次,p后移一个位置 step4 循环结束,返回指针p,template ListNode * List :Find ( T x ) p = head; /当前指针 p 指示第一个结点 whi

13、le ( p -next != NULL,返回的指针p要么是指向x的前一个结点，要么指向最后一个结点,线性链表插入算法,要求：在头指针为HEAD的线性链表中包含元素x的结点之前插入新元素b 算法操作步骤: step1 找到x的位置,使指针p指向x的前一个结点； step2 申请并生成新结点s step3 使s插入到x所在结点之前 考虑几种特殊情况：空链表，首元素为x,template void linked_llist:ins_linked_llist(T x, T b) node *p,*q; p= new node ; p-data =b; if( head = NULL) head=p;

14、p-next=NULL;return; if( head - dada = x) p-next =head;head=p;return; q =head; while(q-next !=NULL,对于空表和第一个结点处理必须单独考虑 （后面引入头结点概念,线性链表删除算法,要求：在头指针为HEAD的线性链表中删除包含元素x的结点。 算法操作步骤: step1 找到x的前件,使指针q指向x的前件； step2 使指针p指向x所在结点； step3 使p所指结点x脱链 step4 释放p,template int linked_llist:del_linked_llist(T x) node *p

15、,*q; if(head=NULL) return 0; if(head-dada=x) p=head-next; delete head; head =p; return 1 q=head ; while(q-next!=NULL),课堂练习,参考P70 例2.15 (1)建立空线性链表 (2)插入1-30； (3)输出链表； (4)将单数的节点删除； (5)再次输出链表,2.3.3 循环链表和双向链表,引入头节点 头结点 ：为方便操作，在头指针和第1个结点之 间设置的结点。 首元结点 第一个结点（a1,空表和非空表表示形式在头结点上得到统一 （任何情况下至少存在一个结点） 空表的形式 :

16、head - next = NULL,非空表的形式: head - Next = Address,引入头节点,无头结点时，空表和非空表的运算不统一； 链表检索只能从头指针开始，且只能顺链表方向移动。 在单链表中，从表的任一结点ai找其前件结点，时间复杂度是O（n）。 如果让链表首尾相接，构成环形，这就是单循环链表。 如果在结点中增加一个指向前一个结点的指针域，链表可以从两个方向检索，效果更佳；这就是双向循环链表,循环单链表,1)单循环链表表示形式,单循环链表为空的条件: head-next=head 表示形式为,2)单循环链表特点： 从表中任一结点出发，均可以找到表中其它结点。 找其前件结点的

17、时间复杂度是O（n,双向循环链表,在单向循环链表中，也存在检索前件结点费时的问题（所需时间是O（n）。 双向循环链表，其存储结构： template struct node T d; node *next，*prior； ； 其它定义与单向链表相同,1）双向循环链表结点结构,2）双向循环链表表示形式,双向循环链表表示形式,双向循环链表为空的条件: head -prior = head-next = head 表示形式为,总结:双向循环链表特点,适合于两个方向的移动。 找其前件结点的时间复杂度是O(1,循环链表的运算特点,空表与非空表统一 判断链表结束的条件改变了 P-next=null P-n

18、ext=head 双向链表的运算要修改两个指针,循环链表的插入 template void linked_llist:ins_linked_llist(T x,T b) node *p,*q; p= new node ; p-dada =b; q =head; while(q-next !=head,循环链表的删除 template int linked_llist:del_linked_llist(T x) node *p,*q; q=head ; while(q-next!=head),链表存储结构的特点,插入、删除操作极为方便 数据非连续存放、顺序存取 逻辑上相邻，物理上不一定相邻 存储

19、结构较复杂、需要额外的存储空间 结论： 链表存储结构适合于表中元素频繁变动的线性表,课堂练习,参考P74 例2.16 (1)建立单向空循环链表; (2)插入1-100； (3)删除单数结点,作业,P152: 2.3 2.7,1.思考题： 1）假设一单循环链表的长度大于1，且表中即无头结点也无头指针。已知S为指向链表中某结点的指针。试写出删除表中结点S 的算法。 2）假设以数组sequm-1存放循环队列的元素，设变量rear和quelen分别为指示队尾元素位置和队中元素个数，试写出入队和出队算法,作 业,2.4 数组,2.4.1 数组的顺序存储结构 2.4.2 规则矩阵的压缩 2.4.3 一般稀

20、疏矩阵的表示,2.4.1 数组的顺序存储,数组是相同类型数据元素的有限集合； 数组中的各个分量称为数组元素； 每个数组元素值可以用数组名和一个下标值唯一地确定,数组是有限个数组元素的集合。 数组中所有元素有相同的特性。 每个数组元素由数组名和下标组成。 每个具有下标值的数组元素有一个与该下标值对应的数组元素值,二维数组 三维数组,行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k,数组元素之间的关系,二维数组m行n列可以看作是m个或n个一维数组: Amn = (a11a12a1n),(a21a22a2n),. (am1am2amn,数组的操作,数组有两种基

21、本的操作： 给定下标，读取相应的数组元素； 给定下标，修改相应数组元素的值,数组的顺序存储结构,数组元素是连续存放的，因此采用顺序存储结构。 无论几维数组，在计算机中都是按一维数组来存放。数组存放通常采用两种方式： 按行优先顺序(Pascal，C) 按列优先顺序(Fortran,1).按行优先顺序存储结构,例如：二维数组Amn，可以看作m个行向量，每个行向量n个元素。数组中的每个元素由元素的两个下标表达式唯一确定。 地址计算公式： LOC（aij）=LOC（a11）+（i-1）n+（j-1）L 其中，L 是每个元素所占的存储单元,二维数组按行优先存储举例,有二维数组如下,LOC( a23)=

22、LOC( a11)+( 2-1)4+( 3-1)= 7 LOC( a34)= 1 + ( 3-1)4 + ( 4-1) = 12 LOC( a14)= 1 + ( 1-1)4 + ( 4-1) = 4,2).按列优先顺序存储结构,按列优先顺序存放是将数组看作若干个列向量。 例如，二维数组Amxn，可以看作n个列向量，每个列向量m个元素。数组中的每个元素由元素的两个下标表达式唯一确定,地址计算公式： LOC（aij）=LOC（a11）+（j-1）*m+（i-1）*L 其中，L 是每个元素所占的存储单元,二维数组按列优先存储举例,LOC（a23）= LOC（a11）+（3-1）* 4+（2-1）=

23、 10 LOC（a34）= 1 + （4-1）* 4 + （3-1） = 15 LOC（a14）= 1 + （4-1）* 4 + （1-1） = 13,有二维数组如下,2.4.2 规则矩阵的压缩,实际工程问题中推导出的数组常常是高阶、含大量零元素的矩阵，或者是一些有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储。 压缩的含义是： 相同值的多个元素占用一个存储单元； 零元素不分配存储单元,能够采用压缩存储的矩阵,对称矩阵:存储主对角线以上（下）的元素； 上（下）三角矩阵:只存储三角阵元素； 带状矩阵:只存储带状元素； 稀疏矩阵:只存储非零元素,1 下三角矩阵的压缩存储,开辟一个长

24、度为n（n+1）/2的一维数组B，然后一行接一行地依次存放A中下三角部分的元素,以行为主压缩存储,以列为主压缩存储,2 对称矩阵的压缩存储,对称矩阵的元素满足：aij = aji 1 i ，j n 因此将n*n 个元素压缩存放到 n（n+1）/2 个单元的一维数组S（n+1）*n/2）中。 （按行存放）aij的地址为,对称矩阵的压缩存储举例,存于一维数组S6 S6=( a11, a21, a22, a31, a32, a33 ) 1 2 3 4 5 6 LOC(a31)=3(3-1)/2+1= 4 LOC(a22)=2(2-1)/2+2= 3 LOC(a21)=2(2-1)/2+1= 2,设有

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