数据结构教程--链接的线性表.ppt

1.在一个链表中,已知q结点是p结点的前驱结点, 若在q和p之间插入s结点,则执行( ) A.s-link=p-link p-link=s B.p-link=s-link s-link=p C.q-link=s s-link=p D.p-link=s s-link=q 2.在链表中,若删除p结点的后续结点,则执行( ) A.p-link=p-link-link B.p=p-link p-link=p-link-link C.p-link=p-link D.p=p-link-link 有一个单链表(不同结点的数据域值可能相同), 头指针为head,编写过程计算数据域为x的结点个数 扫描通过该链表的每个结点,每遇到一个值 为x结点,结点个数加1,结点个数存贮在变量n中. 1 2 3 4 ^ head int count (head) NODE *head; { int n=0; NODE *p; p=head; while (p-link!=NULL) { if (p-data==x) n=n+1; p=p-link;} } 有一个单链表L(至少有1个结点),其头结点指针为 head,编写一个过程将L逆置 1.从头到尾扫描单链表L 2.将第一个结点的link 域置为NULL 3.将第二个结点的link域指向第一个结点 4.将第三个结点的link域指向第二个结点 5.如此…..直到最后个结点,便用head指向它 1 2 3 4 ^ head 4 3 2 1 ^ head void invert(head) NODE *head; { NODE *p,*q,*r; p=head; q=p-link; while (p-link!=NULL) { r=q-link; q-link=p; p=q; q=r;} head-link=NULL; head=p;} 几种变形的线性链表 环形链表 线性链表的最后一个结点的指针指向第一个结点 ^ head head …….. 空的环形链表 非空的环形链表 head=NULL 几种变形的线性链表 带表头结点的链表 在链表中增加一个附加结点,称之为表头结点 head head …….. ^ 空的带表头结点的链表 非空的带表头结点的链表 ^ 表头结点 表头结点 几种变形的线性链表 带表头结点的环形链表 在带表头结点的链表中,链表中最后一个结点的指针指向表头结点 head head …….. 空的带表头结点的环形链表 非空的带表头结点的环形链表 表头结点 表头结点 1.不带头结点的链表head为空的判定条件是( ) A. head=NULL B. head-link=NULL C. head-link=head D. head!=NULL 2.带头结点的链表head为空的判定条件是( ) A. head=NULL B. head-link=NULL C. head-link=head D. head!=NULL 3.若p指向非空环形链表head的尾结点,则p满足( ) A.p-link=NULL B.p=NULL C.p-link=head C.p=head 带表头结点的环形链表表示多项式 A(x)=3x10-5x5+2x+8 head 3 10 …….. 8 0 表头结点 -1 -5 5 …….. 2 1 表示A(x)的带表头结点的环形链表 作业 1.试编写一个求已知单链表的数据域的平均值的函数 2.已知带有头结点的环形链表中头指针为head，试写出删除并释放数据域值为x的所有结点的函数 3.线性表中的元素值按递增有序排列,针对顺序表和环形链表两种不同的存储方式,分别编写函数删除线性表中值介于a与b(ab)之的元素 链接存贮的线性表 顺序存贮的地址公式: ? Ki= ? K0+i*s 线性表的容量不易扩充 对线性表进行插入或删除非常不方便 线性链表的存储结构 线性链表(单链表): 采用链接存贮方式存贮的线性表 数据域: 存储数据元素信息的字段 指针域: 用来存放其后继结点的地址的字段 头指针： 指向