实用数据结构电子教案链表市公开课获奖课件

1、数据结构第三章 链表第1页第1页第三章 链表 知 识 点单链表结点形式、组织办法和特点 单链表基本运算和相应算法 循环链表组织办法和基本运算算法 双链表结点形式、组织办法和特点 双链表基本运算和相应算法 顺序表与链表比较，各自优、缺点 链表应用 用十字链表表示稀疏矩阵第三章 链表第2页第2页难 点 双链表插入、删除运算算法利用链接结构特点设计有效算法，处理与链表结构相关应用问题 要 求 纯熟掌握下列内容: 单链表结构特点、基本运算并能设计简朴算法循环链表结构特点、基本运算并能设计简朴算法双链表结构特点、基本运算并能设计简朴算法 理解下列内容： 用十字链表表示稀疏矩阵 链接堆栈，链接队列应用以及

2、一元多项式加法应用实例 第三章 链表第3页第3页第三章目录3.1 单链表及其运算3.2 循环链表与双向链表 3.3 链表应用举例3.4 表示稀疏矩阵十字链表3.5 应用举例及分析小 结习题与练习第三章 链表第4页第4页3.1.1 单链表1. 结点: 在链式存储结构中，结点不但存储数据元素值，还附加一个指针（链），用来指向该结点直接后继结点。其中，data部分称为数据域，用于存储线性表一个元素，next部分称为指针域或链域，用于存储一个指针，即存储该结点直接后继结点地址。 第三章 链表第5页第5页2. 单链表所有结点通过指针链接而构成线性表称为单链表。线性表（a1，a2，an，）单链表可直观地画

3、成：head是单链表头指针，指向开始结点a1, an是终端结点，其指针域为空，不指向任何结点。一个单链表由头指针head唯一标识和拟定，因此，可用头指针来命名单链表。 第三章 链表第6页第6页3. 单链表类型定义 假设线性表中数据元素类型为datatype，单链表类型定义下列：typedef struct node * pointer;struct node datatype data; pointer next;typedef pointer linklist; 一个结点是由两个域data和next构成统计,data是结点数据域，next是结点链域。第三章 链表第7页第7页4. 指针概念 假

4、设p是一个pointer类型，应正确区分指针型变量、指针、指针所指结点和结点内容这四个密切相关不同概念：p值（假如有话）是一个指针，即是一个所指结点地址 。该指针（若不是NULL）指向某个node型结点用*p来标识。结点 *p是由两个域组成统计，这两个域分别用pdata域和pnext域来标识，它们各有自己值，pdata值是一个数据元素，pnext值是一个指针。 第三章 链表第8页第8页3.1.2 单链表基本运算 1. 遍历(Traversal)：依据已给表头指针，按由前向后顺序访问单链表各个结点。 在实际应用中遍历是对单链表最基本运算，比如，当要打印或显示出各个结点数值域值、计算单链表长度(即

5、结点数目)或寻找某一个结点时都需要遍历单链表。 假设head是单链表头指针，计算一个已建立好单链表结点个数算法下列： 第三章 链表第9页第9页计算结点个数算法int length(node *head) /*求表head长度*/ int count=0; /*计数器置初值*/ node *p=head; /*p指向头结点*/ while (p!=NULL) p=p-next; count+; return(count); /*返回表长值*/ 第三章 链表第10页第10页算法分析此算法关键是while循环语句，开始时p指针指向头结点，每一循环都修改指针值，让它指向下一个结点，同时将计数链表长度变

6、量count加1。 这样每循环一次就向后推移一个结点，直到p所指结点*p链域值为NULL为止。空指针NULL起标志作用，若无此标志，尾结点链域值为“无定义”，上述算法中while语句在做最后一次判断时将出现“运营错”，这是应予避免。 第三章 链表第11页第11页2. 插入 所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x结点。实现插入算法主要完毕三个基本操作： 1) 在单链表上找到插入位置，即找到第i个结点。 能够用遍历办法，即从表头起顺次访问单链表结点，直至找到第i个结点。 2) 生成一个以x为值新结点。 可通过C库函数malloc(size)来产生。 3) 将新结点链入单链表中

7、。 需要改变相关结点指针 ，下列面图所表示。 第三章 链表第12页第12页 假设指针p指向单链表中第i个结点，指针s指向已生成新结点，链入新结点操作下列：将新结点*s链域指向结点*p后继结点 (即s-next=p-next)；将结点*p链域指向新结点(即p-next=s)。第三章 链表第13页第13页插入算法 void insert (node *head, int i, x) node *s,*p; int j; s=(node * )malloc(sizeof(node); /*生成新结点*/ s-data=x; if(i=0) /*假如i=0,则将s所指结点插入到表头*/ s-next=

8、NULL; head=s; else p=head; j=1; /*查找第i个结点，由p所指向*/ 第三章 链表第14页第14页插入算法续 while(p!=NULL & jnext; if(p!=NULL) /*把新结点插入其后*/ s-next=p-next; p-next=s; else printf(“未找到！n”); 第三章 链表第15页第15页3. 删除当需要从单链表上删除结点时，就要通过删除运算来完毕。删除单链表上一个其值为x结点主要操作是：1) 用遍历办法在单链表上找到该结点；2) 从单链表上删除该结点。欲从单链表上删除一个结点，需修改该结点前一个结点指针，下列面图所表示。 第

9、三章 链表第16页第16页 假设指针q指向待删除结点前一个结点，指针p指向要删除结点，删除该结点操作下列：将该结点前一个结点*q链域指向*p后继结点（即q-next=p-next）。 第三章 链表第17页第17页删除算法void delete(node *head, int x) node *p, *q; if (head=NULL) printf(“链表下溢！n”); /*判空*/ if(head-data=x) / *如表头结点值等于x*/ p=head; head=head-next; free(p); else q=head; /*从第二个结点开始查找*/ p=head-next; 第

10、三章 链表第18页第18页删除算法续 while(p!=NULL & p-data!=x) q=p; p=p-next; if(p!=NULL) /*找到该结点，删除*/ q-next=p-next; free(p); else printf(“未找到！n”); 返回第三章 链表第19页第19页3.2.1 循环链表循环链表（circular linked list）是一个首尾相接链表，将单链表表尾结点本来空指针改为指向表头结点，就成为循环链表。循环链表并不多占存储单元，但从循环链表任一个结点出发都能够访问到此链表每一个结点，由于当访问到表尾结点后又能返回到头结点。 第三章 链表第20页第20页

11、1. 带头指针循环链表通常在循环链表表头结点前面再加一个空结点,也叫空表头结点。表空时空表头结点指针指向其本身，下列面图所表示为空循环链表。 空表头结点除指针以外数据域是没有用，但为了将此结点与普通结点相区别，经常是将其赋以一个尤其数据，以与普通结点相区别。 第三章 链表第21页第21页2. 带尾指针循环链表另一个办法是不设头指针而改设尾指针，这样无论是找头结点还是尾结点都很以便。由于尾结点由尾指针rear来批示，则头结点位置是rear-next-next。 第三章 链表第22页第22页3.2.2 双链表 双向链表中每个结点除了有向后指针外，还有指向其前一个结点指针，这么形成链表中有两条不同方

12、向链，因此从某一结点均可向两个方向访问。 双链表结点形式为： 其中链域prior和next分别指向本结点直接前趋和直接后继结点。 第三章 链表第23页第23页假如循环链表结点再采用双向指针，就成为双向循环链表。第三章 链表第24页第24页双链表较单链表即使要多占用一些存储单元，但对其插入和删除操作以及查找结点前趋和后继都非常以便。 双链表结构是一个对称结构，设指针p指向双链表某一结点，则双链表对称性可用下式来表示： p=(p-prior)-next=(p-next)-prior 即结点*p地址既存储在其前趋结点 *(p-prior)后继指针域中，又存储在它后继结点*(p-next)前趋指针域中

13、。 第三章 链表第25页第25页1. 双链表插入设要在p所指结点前面插入一个新结点*q，则需要修改4个指针 ：q-prior=p-prior; q-next=p; (p-prior)-next=q; p-prior=q; 第三章 链表第26页第26页2. 双链表删除设p指向待删除结点，则删除该结点环节为：(p-prior) -next=p-next; (p-next) -prior=p-prior; 这两个语句执行顺序能够颠倒，执行这两个语句之后，可调用free(p),将*p结点释放。 返回第三章 链表第27页第27页3.3.1 链堆栈链堆栈是栈链接存放表示，它是只允许在表头进行插入和删除运算

14、单链表。它与普通单链表没有什么不同，只是将头指针head改称为栈顶指针top。 第三章 链表第28页第28页链堆栈入栈算法 在栈顶指针是top链堆栈中插入一个值为x结点算法：void push (node *top, int x) node *s; s=(node *)malloc(sizeof(node); /*建立一个结点指针*/ s-data=x; s-next=top; top=s; 第三章 链表第29页第29页链堆栈出栈算法int pop(node *top) int x; node *p; if(top=NULL) printf(“栈为空!n”); else x=top-data;

15、 p=top; top=top-next; free(p); return(x); 第三章 链表第30页第30页3.3.2 链队列链队列需要两个指针，其中队首指针front指向链表表头，队尾指针rear指向链表表尾。 普通插入时只修改队尾结点指针和队尾指针rear，删除时只修改队首指针front。当将第一个元素插入空队列或删除了最后一个元素而使队列为空时，front和rear都需要修改。 第三章 链表第31页第31页链队列插入算法void insert(node *front, rear, int x) node *s; s= (node *) malloc (sizeof (node); s

16、-data=x; s-next=NULL; if (rear =NULL) /*处理空队列情况*/ front=s; rear=s; else rear-next=s; rear=s; 第三章 链表第32页第32页链队列删除算法int delete(node *front,rear) node *p; int x; if (front=NULL) printf(“空队列!n”); else x=front-data; p=front; if ( front = rear) front=NULL; rear=NULL; else front=front-next; free(p); return

17、(x); 第三章 链表第33页第33页3.3.3 一元多项式算术运算设一个一元多项式为1. 假如用数组来表示一元多项式，以各项指数作为下标，将各个系数存入一维数组中。 第三章 链表第34页第34页2. 用单链表表示一元多项式将单链表每个结点相应着一元多项式中一个非零项，它由三个域构成，分别表示非零项系数、指数和指向下一个结点指针。设两个一元多项式为: 求此两一元多项式之和C(x)=A(x)+B(x)。 第三章 链表第35页第35页3. 运算规则将二个一元多项式中所有指数相同项系数相加，相加后，若和不为零，则构成“和一元多项式”中一项；若和为零，则“和一元多项式”中无此项；所有指数不相同项均抄到

18、“和一元多项式”中。第三章 链表第36页第36页返回第三章 链表第37页第37页3.4 表示稀疏矩阵十字链表在十字链表中，矩阵每个非零元素相应着一个含有五个域结点，这五个域分别为该非零元素在稀疏矩阵中行号、列号、元素数值以及两个指针，其中一个指针指向同一列下一个非零元素结点，另一个指针指向同一行右边一个非零元素结点。 第三章 链表第38页第38页将每行非零元素结点链接成循环链表，又将每列非零元素结点链接成循环链表，就构成了十字形链接结构。对于每行、每列循环链表都有一个空表头结点，以利于元素插入和删除运算。这些空表头结点行号、列号都标成零，以便和其它结点相区别。整个十字链表有一个总空表头结点，在

19、普通结点标以行号、列号之处，此结点是标出矩阵行数m和列数n。有一个指针HM指向这个总空表头结点。 第三章 链表第39页第39页例：稀疏矩阵M及其相应十字链表如图所表示。第三章 链表第40页第40页第三章 链表第41页第41页空表头结点结构因各列、各行空表头结点中行号和列号都是零，且每列空表头结点只用到向下指针，每行空表头结点只用到向右指针，故可将这组空表头结点合用。由于数值域也没有用，可将空表头结点数值域改为一个指针域，将各个空表头结点也链接成一个循环链表。 返回第三章 链表第42页第42页例3.1有一个单链表L(至少有一个结点)，其头结点指针为head，编写一个函数将L逆置，即最后一个结点变

20、成第1个结点，本来倒数第二个结点变成第二个结点如此等等。解：本题采用算法是，从头到尾遍历单链表L，并设置3个附加指针p、q、r,p指向当前处理结点，q指向p下一个结点，r指向q下一个结点，q、r作用是为了预防倒置指针时，下一个结点丢失而设置，有了这三个指针，就能够以便地实现指针倒置。最后将第一个结点next域置为NULL，并将头指针指向最后一个结点，这样达到了本题要求。 第三章 链表第43页第43页例3.1算法void invert(node *head) node *p,*q,*r; p=head; q=p-next; while(q!=NULL) /*没有后继时停止*/ r=q-next;

21、 q-next=p; p=q; q=r; head-next=NULL; head=p; 第三章 链表第44页第44页例3.2有两个循环单链表，头指针分为head1和head2，编写函数将链表head2链接到链表head1之后，链接后链表仍保持是循环链表形式。解：先分别找到两个链表表尾，将head2放入链表head1表尾，将两个链表链接起来，然后将head1放入原head2链表表尾，构成新循环链表。 第三章 链表第45页第45页例3.2算法link(node *head1,head2) node *p,*q; p=head1; while(p-next!=head1) p=p-next; q=

22、head2; while(q-next!=head2) q=q-next; p-next=head2; q-next=head1; 第三章 链表第46页第46页例3.3给出在双链表中第i个结点(i0)之后插入一个元素为x结点函数。 解：在前面双链表一节中，已经给出了在一个结点之前插入一个新结点办法，在一个结点之后插入一个新结点思想与前面是同样。第三章 链表第47页第47页例3.3算法void insert(dnode *head,int i,x) dnode *s,*p; int j; s=(dnode *)malloc(sizeof(dnode); /*建立一个待插入结点，由s指向*/ s-

23、data=x; if(i=0) /*如i=0,将s所指结点插入到表头后返回*/ s-next=head; head-prior=s; head=s; 第三章 链表第48页第48页例3.3算法续 else p=head; /*查找第i个结点，由p指向*/ j=1; while(p!=NULL & jnext; if(p!=NULL) /*若查找成功，把s插入到p之后*/ if(p-next=NULL)/*若p是最后一个结点，则直接把s结点链入*/ 第三章 链表第49页第49页例3.3算法续 p-next=s; s-next=NULL; s-prior=p; else s-next=p-next; p-next-prior=s; p-next=s; s-prior=p; else printf(“未找到!n”); 返回第三章 链表第50页第50页小结单链表 循环链表双向链表 双向循环链表 十字链表 返回第三章 链表第51页第51页习题与练习一