计算机软件技术编程基础 链表.ppt
顺序表的 特点：运算：简单，时间复杂度好存储特性：静态规模，编译前确定问题：程序的通用性和空间利用率之间的矛盾期望：在实际运行过程中，根据实际问题的需要临时确定存储空间，涉及到动态变量动态变量：在程序运行的过程中产生和释放的变量。与之相反的是静态变量静态变量：在程序运行的过程中一直存在的变量。静态变量是出现在说明语句中的变量；动态变量由于是在运行中产生的，因而不会事先说明如何实现动态变量？通过指针来实现：指针变量的说明，动态变量的产生和释放。2.3 线性链表及其运算线性链表及其运算线性表的链式存储结构称为线性链表，即将表中元素用线性表的链式存储结构称为线性链表，即将表中元素用链地址连接起来。链地址连接起来。head头指针结点对线性表中的每一个数据元素，都需用两部分来存储：一部分用对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。结点。链表的存储结构 链式存储结构是利用任意的存储单元来存放线性表中的元素，存链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。储数据的单元在内存中可以连续，也可以零散分布。由于线性表中各元素间存在着线性关系，每一个元素有一个直接由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。结点的结构如下所示。链表结构示意图链表结构示意图 从图中可见，每个结点的存储地址存放在直接前驱的指针域中。从图中可见，每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中数据元素所以要访问链表中数据元素C，必须由头指针必须由头指针head得到第一个结点得到第一个结点（数据（数据A）的地址，由该结点的指针域得到第二个结点（数据的地址，由该结点的指针域得到第二个结点（数据B）的的地址，再由其指针域得到存储数据地址，再由其指针域得到存储数据C的结点地址，访问该结点的数据的结点地址，访问该结点的数据域就可以处理数据域就可以处理数据C了。链表这种顺着指针链依次访问数据元素的特了。链表这种顺着指针链依次访问数据元素的特点，表明链表是一种点，表明链表是一种顺序存储结构顺序存储结构，只能顺序操作链表中元素。不能，只能顺序操作链表中元素。不能像顺序表（数组）那样可以按下标像顺序表（数组）那样可以按下标随机随机存取。存取。在链表存储结构中，不要求存储空间的连续性，数据元素之间在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。的逻辑关系由指针来确定。每个结点由两部分组成：data 数据域存放数据值next指针域存放后继结点的首地址链表通过每个指针域将n个结点按逻辑次序链接成一个整体。&b&b&c&c&d&dHead&a&a头指针结点&b&b&c&c&a&a&datanext表头的地址由head指针提供，表尾结点没有直接后继，其指针域应为空指针，指针域为NULL单向链表单向链表 在图所示的链表中，每个结点只有一个指向后继的指针。在图所示的链表中，每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾，而不能做也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。单的链表。对于空链表，头结点的指针域为空。对于空链表，头结点的指针域为空。图图2-8（a）为带头结点的空链为带头结点的空链 (b)为带头结点的单链表为带头结点的单链表定义链表结点结构的一般形式为Struct 结构体名 数据成员表；结构体名*指针变量名；struct studentint num;float score;student*next;struct ListNode ELEM data；ListNode*next;1672873 79486headtail/建立链表linklist*create()linklist*head,*p1,*p2;head=NULL;int x;cinx;struct linklistint num;float score;linklist*next;p2=p1;/将新的结点作为尾结点p2-next=NULL;cinx;while(x0)p1=new(linklist);p1-num=x;cinp1-score;n=n+1;if(head=NULL)head=p1;else p2-next=p1;&p1p2p2p1p1如果是首结点呢？定义一个新结点p p2 2return head;建立链表的条件void print()coutnendl;/链表输出链表输出形参是什么？需要知道链表的头指针linklist*head如何查找链表？定义一个指针linklist*p1;p1=head;if(head!=NULL)docoutnum score;coutnext;while(p1!=NULL);查找运算查找运算 的实现的实现 设设计计思思路路：设设置置一一个个跟跟踪踪链链表表结结点点的的指指针针p1，初初始始时时p1指指向向链链表表中中的的第第一一个个结结点点，然然后后顺顺着着next域域依依次次指指向向每每个个结结点点，每每指指向向一一个个结结点点就就判判断断其其值值是是否否等等于于i，若若是则返回该结点地址是则返回该结点地址,否则继续往后搜索否则继续往后搜索.要要访访问问单单链链表表中中第第i个个元元素素值值，必必须须从从头头指指针针开开始始遍遍历历链链表表，依依次次访访问问每每个个结结点点，直直到到访访问问到到第第i个个结结点点为为止止。其其时时间间复杂度为复杂度为O(n)。linklist*getnode else coutinum!=i&p1-next!=NULL)p1=p1-next;j+;如果该结点不是要找的结点？if(p1-num=i)j+;coutthe node isjendl;return p1;如果该结点是要找的结点？linklist*del(linklist*head,int num)linklist*p1,*p2;if(head!=NULL)p1=head;else coutnextP1-next删除条件if(p1-num=num)if(p1=head)head=p1-next;elsep2-next=p1-next;n=n-1;else coutnumnextP1-nextwhile(p1-num!=num&p1-next!=NULL)p2=p1;p1=p1-next;如果该结点不是要找的结点？找到该结点如何删除？线性链表的插入：在链式存储结构下的线性表中插入一个新结点线性链表的插入：在链式存储结构下的线性表中插入一个新结点在头指针head的线性链表中包含元素x的结点之前加入一个新结点void inslst(linklist*head,int x)linklist*p1,*p2;p1=new(linklist);cinp1-nump1-score;if(head=NULL)head=p1;p1-next=NULL;p2=getnode(head,x);/寻找包含元素x的结点nextnextnextnextp1p1P2-nextP2-nextp2p2p1-next=p2-next;/将结点p1插入到结点p2后p2-next=p1;在插入和删除算法中，都是先查询确定操作位置，然在插入和删除算法中，都是先查询确定操作位置，然后再进行插入和删除操作。所以其时间复杂度均为后再进行插入和删除操作。所以其时间复杂度均为O(n)。另外在算法中实行插入和删除操作时没有移另外在算法中实行插入和删除操作时没有移动元素的位置，只是修改了指针的指向，所以采用链动元素的位置，只是修改了指针的指向，所以采用链表存储方式要比顺序存储方式的效率高表存储方式要比顺序存储方式的效率高循环链表循环链表循环链表是单链表的另一种形式，是一个首尾相接的链表。特点：最后一个结点的指针域不空，而是指向头结点，整个链表连成环状，从表中任意结点出发均可到达其他结点。&b&b&c&c&d&d&b&b&c&cheadhead&b&b&c&c&d&dhead&b&b&c&cheadheadheadheadhead空循环链表判断表空的条件：head-next=head判断指针指向结点为表尾结点的条件：p-next=head 带带头头结结点点的的单单循循环环链链表表的的操操作作算算法法和和带带头头结结点点的的单单链链表表的的操操作作算算法法很很相相似似，差差别别仅仅在在于于算算法法中中的的循循环环条条件件不不同同。在在循循环环单链表上实现上述基本运算的改动如下：单链表上实现上述基本运算的改动如下：1初始化链表初始化链表initlist(head)创建的头结点指针域创建的头结点指针域next不为空，而是指向自身不为空，而是指向自身head-next=head2线线性性表表查查找找运运算算*getnode(linklist*head,int i)函函数数、链链表表元元素素输输出出运运算算print(linklist*head)函函数数中中，循循环环遍遍历历是是否否进进行行的的条件由条件由p!=NULL改为改为p!=head;其余函数运算没有变化，请自行写出相关函数的定义。其余函数运算没有变化，请自行写出相关函数的定义。在在循循环环链链表表中中，除除了了有有头头指指针针head外外，有有时时还还可可加加上上一一个个尾尾指指针针tail。尾尾指指针针tail指指向向最最后后一一结结点点，沿沿最最后后一一个个结结点点的的指指针针又又可可立立即即找找到到链链表表的的第第一一个个结结点点。在在实实际际应应用用中中，使使用用尾尾指指针针来来代代替替头头指针进行某些操作往往会更简单。指针进行某些操作往往会更简单。【例例】将将两两个个循循环环链链表表首首尾尾相相接接进进行行合合并并，La为为第第一一个个循循环环链链表表表表尾尾指指针针，Lb为为第第二二个个循循环环链链表表表表尾尾指指针针，合合并并后后Lb为为新新链链表表的的尾尾指指针，针，head指向整个合并后的链表。指向整个合并后的链表。【解解】算法思路：算法思路：对对两两个个单单循循环环链链表表La，Lb进进行行的的连连接接操操作作，是是将将Lb的的第第一一个个数数据据结结点点接接到到La的的尾尾部部。操操作作时时需需要要从从La的的头头指指针针开开始始找找到到La的的尾尾结结点点，其其时时间间复复杂杂性性为为O(n)。而而在在循循环环链链表表中中若若采采用用尾尾指指针针La，Lb来来标标识识，则则时时间间性性能能将将变变为为O(1)。其其连连接接过过程程如如图图2-14所示。所示。图图 两个循环链表首尾相接进行合并两个循环链表首尾相接进行合并(a)(a)连接前连接前p=La-p=La-next;qnext;q=Lb-next=Lb-next(b)连接后连接后La-next=La-next=q;Lbq;Lb-next=p-next=p;.a1a2aian.b1b2bibnLaLbpqLbLa.a1a2aian.b1b2bibn双向链表双向链表nextnextdatapriorprior双向链表的结点结构struct dlnode ELEM data；dlnode*next,*prior;对结点p而言，后继结点的地址p-next;前驱结点的地址p-priordatapp1p0P-prior-nextP-next-priorP-priorP-nextsp1p0P1-prior-next=sP1-prior=ss-prior=p1-priors-next=p1双向链表中结点的插入将结点s的插入结点p1之前pP-nextP-prior双向链表中结点的删除P-prior-next=p-nextP-next-prior=p-priordelete P应用举例应用举例 一元多项式相加一元多项式相加 假设用单链表表示多项式：假设用单链表表示多项式：A(x)=12+7x+8x10+5x17，B(x)=8x+15x7-6x10，头指针头指针Ah与与Bh分别指向这两个链表，分别指向这两个链表，如图如图2-21所示：所示：对对两两个个多多项项式式进进行行相相加加运运算算，其其结结果果为为C(x)=12+15x+15 x7+2x10+5x17。如图所示。如图所示。图图 合并以前的链表合并以前的链表 图图 2-22 合并以后的链表合并以后的链表8115 760Bh12 0718105 17Ah15 115 72 105 17012Ch 对对两两个个一一元元多多项项式式进进行行相相加加操操作作的的运运算算规规则则是是：假假设设指指针针qa和和qb分分别别指指向向多多项项式式A(x)和和B(x)中中当当前前进进行行比比较较的的某某个个结结点点，则需比较两个结点数据域的指数项，有三种情况：则需比较两个结点数据域的指数项，有三种情况：(1)指指针针qa所所指指结结点点的的指指数数值值指指针针qb所所指指结结点点的的指指数数值值时时，则则保保留留qa指针所指向的结点，指针所指向的结点，qa指针后移；指针后移；(2)指指针针qa所所指指结结点点的的指指数数值值指指针针qb所所指指结结点点的的指指数数值值时时，则则将将qb指针所指向的结点插入到指针所指向的结点插入到qa所指结点前，所指结点前，qb指针后移；指针后移；(3)指指针针qa所所指指结结点点的的指指数数值值指指针针qb所所指指结结点点的的指指数数值值时时，将将两两个个结结点点中中的的系系数数相相加加。若若和和不不为为零零，则则修修改改qa所所指指结结点点的的系系数数值值，同同时时释释放放qb所所指指结结点点；反反之之，从从多多项项式式A(x)的的链链表表中中删删除除相相应应结点，并释放指针结点，并释放指针qa和和qb所指结点。所指结点。多项式相加算法：多项式相加算法：struct polynode*add_poly(polynode*Ah,polynode*Bh)polynode*qa,*qb,*s,*r,*Ch;qa=Ah;qb=Bh;/qa和和qb分别指向两个链表的第一结点分别指向两个链表的第一结点r=qa;Ch=Ah;/将链表将链表Ah作为相加后的结果链表作为相加后的结果链表while(qa!=NULL&qb!=NULL)/两链表均非空两链表均非空 if(qa-exp=qb-exp)/两者指数值相等两者指数值相等 x=qa-coef+qb-coef;if(x!=0)qa-coef=x;r-next=qa;r=qa;s=qb+;free(s);qa+;/相加后系数不为零时相加后系数不为零时 elses=qa+;free(s);s=qb+;free(s);/相加后系数为零时相加后系数为零时 else if(qa-expexp)r-next=qa;r=qa;qa+;/多项式多项式Ah的指数值小的指数值小 elser-next=qb;r=qb;qb+;/多项式多项式Bh的指数值小的指数值小 链栈链栈toptop栈顶链表的头部作栈顶是最方便的链表的头指针叫做栈顶指针只允许在表头进行插入和删除运算struct linkstackint num;float score;linkstack*next;/置空栈linkstack*init_linkstack()return NULL;/判断栈空int empty_linkstack(linkstack*top)if(top=NULL)return 1;else return 0;/入栈linkstack*push_linkstack(linkstack*top,linkstack*stud)stud-next=top;top=stud;n=n+1;return top;toptopstudstudtoptoptoptop/出栈linkstack*pop_linkstack(linkstack*top,linkstack*stud)if(top=NULL)return NULL;elsestud=top;top=top-next;n=n-1;return top;toptoptoptopstudstud带链的队列带链的队列rearrearfrontfront先进先出的数据结构只允许在表头删除，表尾插入的单链表struct qnodeint num;struct qnode*next;struct lqueueqnode*front,*rear;lqueue*init_lqueue()lqueue*l;qnode*q;l=new(lqueue);q=new(qnode);q-next=NULL;l-front=l-rear=q;return l;创建一个空队列frontrearnextnextstruct qnodeint num;struct qnode*next;struct lqueueqnode*front,*rear;void in_lqueue(lqueue*l,qnode*q)q-next=NULL;/入队frontrearnextnextnextnext只能在表尾插入结点l-rear-next=q;队尾结点的指针域指向新结点l-rear=q;rear存入新结点地址/出队删除表头结点frontrearnextnextnextnextnextnextqnode*out_lqueue(lqueue*l,)qnode*q return q;判断队空的条件if(l-rear=l-front)return NULL;取出队首结点地址q=l-front-next;l-front-next=q-next;队首结点地址给下一个结点作业：P153 2.10 试写出逆转单链表的算法 2.9 试写出循环链表长度的算法上机：星期三晚上7：00（3月27日）作业讲评：2.10 试写出逆转单链表的算法 如何定义一个新结点struct linklistint num;float score;linklist*next;如何建立一个新链表新链表需要头指针head构造新结点指针p11 指针类型的定义-所指变量类型2 申请内存空间分配地址停止建立链表的条件输入学号为0结点名字，包含几部分内容如何将新结点连接到链表中链表尾部结点如何处理/建立链表linklist*create()linklist*head,*p1,*p2;head=NULL;int x;cinx;void main()linklist*head,*rhead;head=create();p2=p1;/将新的结点作为尾结点p2-next=NULL;cinx;while(x0)p1=new(linklist);p1-num=x;cinp1-score;n=n+1;if(head=NULL)head=p1;else p2-next=p1;&p1p2p2p1p1如果是首结点呢？定义一个新结点p p2 2return head;建立链表的条件&p2&p2&p3&p3nextnextp2p2p3p3p1p1P2=p1-nextP3=p2-nextp2-next=P1&p1&p1nextnextp2p2p3p3p1p1p1p1p2p2p3p3nextnextP1=p2P2=p3P3=p2-nextp2p2表表头头表尾如何处理？如何判断逆转链表到头？p1=head;p2=p1-next;p1-next=NULL;While(P2!=NULL)p3=p2-next;p2-next=p1;p1=p2;p2=p3;表尾表尾
