第05讲 循环链表等.ppt

1、2.3.1 线性链表,回顾 单链表分为哪两种？为什么说“已知一个头指针”，就是“已知一个单链表”？ 已知单链表的头指针，如何找到它的第i个结点？,2.插入 ListInsert( p=L; for (i=1;inext=(LinkList)malloc(sizeof(LNode); p=p-next; p-data=i*2-1; p-next=NULL; for (i=4;i=1;i-) InsertList(L, i+1, i*2); for (i=1;i=3;i+) DeleteList(L, i);,2.简述以下算法的功能,Status A (LinkList L) if ( L ,静态

2、链表,借用一维数组来描述线性链表。,线性表：adbec,f,2,6,存储结构的定义： #defint MAXSIZE 1000 typedef struct ElemType data; int cur; SLinkListMAXSIZE;,2.3.2 循环链表,存储结构:最后一个结点的指针域指向头结点，整个链表形成一个环。 c.f.单链表 图示：非空表与空表,常用操作 1. 查找算法 GetElem(L, i, /数据域 struct LNode *prior; /指向前驱 struct LNode *next; /指向后继 DuLNode, *DuLinkList;,双向链表也可以循环：双

3、向循环链表。,2.常用操作,1) 插入 ListInsert( s-prior=p-prior; p-prior=s; s-next=p;,2) 删除 listDelete( p-next-prior=p-prior; p-prior-next=p-next; free(p),2.4 一元多项式的表示及相加,符号多项式操作，已成为表处理的典型。 一个一元多项式Pn(x)可按升幂写成： Pn(x)=p0 + p1x + p2x2 + + pnxn,可用线性表P来表示： P=(p0 , p1 , p2 , , pn),同理，多项式Qm(x)可用线性表Q表示成： Q=(q0 , q1 , q2 ,

4、, qm),当mn,则 Pn(x)+ Q m(x) 可用线性表R表示为： R=(p0 +q0 , p1 +q1 , , pm+ qm , , pn),1.存储结构,1)存储所有系数 例子：A(x)=5+7x2+6x4 B(x)=17+8x1000+29x2000 2）只存储非零系数项：除系数还需存储指数. 重新考虑上述例子,链式结构的定义：,typedef struct Node float xs; int zs; struct Node *next; Node;,2.使用链式存储实现一元多项式的相加： A(x)=A(x)+B(x),例子： A(x)=7+3x+9x8+5x17 B(x)=8x

5、+22x7-9x8,运算规则：指数相同的项，对应系数相加。,作业： 已知线性表中的元素以值递增有序排列， 并以单链表作存储结构。试写一高效算法， 删除表中所有值大于mink且小于maxk的元素 （若表中存在这样的元素）同时释放被删结 点空间（注意：mink和maxk是给定的两个参 变量）。,约瑟夫环问题,约瑟夫(Joseph)问题的描述：编号为1, 2, , n的人顺时针围坐一圈，每人持一密码。 一开始任取一正整数m作为报数上限，从第一个人开始报数，报至m的人出列，并以其密码作为新的m，从他在顺时针方向的下一个人重新开始从1报数，如此下去，直至所有人出列。 设计一个程序求出出列顺序。,本章小结,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称