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

1、链接存贮的线性表 顺序存贮的地址公式: Ki= K0+i*s 线性表的容量不易扩充 对线性表进行插入或删除非常不方便线性链表的存储结构 线性链表(单链表): 采用链接存贮方式存贮的线性表 数据域: 存储数据元素信息的字段 指针域: 用来存放其后继结点的地址的字段 头指针： 指向链表中的第一个结点 linkdataNULLheadhead:头指针heada b c d head把链表画成用箭头相链接的结点的序列结点之间的箭头表示线性链表中的指针头指针head31存储地址 数据域 指针域 1 L 43 7 Q 13 13 S 1 19 W NULL 25 N 37 31 Z 7 37 A 19 4

2、3 B 25headZQSLBNAW (Z,Q,S,L,B,N,A,W)a b c d headtypedef struct node char data; struct node *link; NODE;链接存贮的线性表 用链表表示线性表时,数据元素之间的逻辑关系由结点中的指针指示. 根据结点ki的链接指针,可以找到ki的后继结点ki+1 逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻a b c d headtypedef struct node char data; struct node *link; NODE;#include typedef struct node char da

3、ta; struct node *link; NODE;NODE *head,*p,*q;/*1*/ head=(NODE*)malloc(sizeof(NODE);/*2*/ p=head;建立具有四个结点的线性链表/*3*/ p-data=a;/*4*/ q=(node*)malloc(sizeof(NODE);/*5*/ p-link=q;/*6*/ p=q;/*7*/ p-data=b;/*8*/ q=(node*)malloc(sizeof(NODE);/*9*/ p-link=q;/*10*/ p=q;建立具有四个结点的线性链表/*11*/ p-data=c;/*12*/ q=(n

4、ode*)malloc(sizeof(NODE);/*13*/ p-link=q;/*14*/ p=q;/*15*/ p-data=d;/*16*/ p-link=NULL;建立具有四个结点的线性链表建立具有n个结点的链表NODE *create_link_list(n)int n; int i; NODE *head,*p,*q; if (n=0) return(NULL); head=(NODE*)malloc(sizeof(NODE); p=head;for(i=1;idata); q=(NODE*)malloc(sizeof(NODE); p-link=q; p=q;scanf(“%c

5、”,&(p-data);getchar( );p-link=NULL;return(head);建立具有n个结点的链表线性链表的插入headabc d headabec d pq4132p线性链表的插入 q=(NODE*)malloc(sizeof(NODE); q-data=e; q-link=p-link; p-link=q;insert(p-head,a,b) 在head线性链表中把值为b的结点插在值为a的结点之后 若原链表为空,则b为首结点 若a不在head线性链表中,则把b插在该链表的最后 找到a.void insert(p_head,a,b) NODE *p_head; char

6、a,b; NODE *p,*q; q=(NODE*)malloc(sizeof(NODE); q-data=b; q-link=NULL; if (*p_head=NULL) *p_head=q;else p=*p_head;while (p-data!=a&p-link!=NULL) p=p-link;q-link=p-link;p-link=q;insert(&head,a,b)线性链表的删除headabc d pheadabc d pq123删除前的线性链表删除后的线性链表线性链表的删除 删除位于指针p所指的结点后面的结点 q=p-link; p-link=q-link; free(q)

7、;线性链表的删除 实现在head链表中删除值为a的结点 删除成功返回0 删除的结点为第一个结点 删除的结点为线性链表中其它结点 删除不成功返回1 线性链表为空表 a不在线性链表中int delete(p_head,a)NODE *p_head;char a; NODE *p,*q; q=*p_head; if (q= =NULL) return(1) if (q-data= =a) *p_head=q-link; free(q); return(0);else while(q-data!=a&q-link!=NULL) p=q; q=q-link; if (q-data= =a) p-link

8、=q-link; free(q); return(0); else return(1):i=delete(&head,a)若线性链表中存在第i个元素,将其值赋给eint store(p_head,i,e)int i;NODE *p_head;char e;p=p_head; j=1; while(p-link!=NULL & jlink; +j; if(jdata; return(0)用线性链表表示多项式Coef exp linkcoef: 存放系数exp: 存放指数link: 链接指针,指向多项式的下一个非零项结点零多项式不包含任何非零项,可用一个空的线性链表表示一个零多项式A(x)=8x6

9、0+6x50+4x25+2x10+18 606 504 252 101 0 B(x)=7x60-6x50+3x207 60-6 503 20 ahbhpapb15 604 253 202 101 0 chpcstruct node int coef; int exp; struct node *link; NODE;NODE *ah,*bh,*ch;aham emam-1 em-1.a1 e1a0 e0 .*insert(pc,c,e): 产生一个新的结点,并把新结点挂在pc所指的结点之后 c:系数 e:指数*polyadd-l(ah,bh): 由线性链表ah和bh表示的两个多项式相加 在进行

10、相加之前,先产生一个附加结点pc,在运行到结果多项式的线性表后,再删除这个附加结点多项式相加 pa-exppb-exp:摘取pa指针所指结点插入到结果多项式链表中 pa-expexp:摘取pb指针所指结点插入到结果多项式链表中 pa-exp=pb-exp:则将两个结点中的系数相加 和不为零,则修改pa所指结点的系数值,同时释放pb所指结点 和为零,从多项式A的链表中删除相应结点,并释放指针pa和pb所指结点将两个有序链表合并为一个有序链表void link(la,lb)NODE *la,*lb NODE *pa,*pb,*pc; pa=la; pb=lb; pc=(node*)malloc(s

11、izeof(node); while(pa-link!=NULL & pb-link!=NULL) if (pa-datadata) pc-link=pa; pc=pa; pa=pa-link; else pc-link=pb;pc=pb;pb=pb-link; .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=q2.在链表中,若删除p结点的后续结点,则执行( ) A.p-link

12、=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中.1234 headint 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个结点),其头

13、结点指针为head,编写一个过程将L逆置1.从头到尾扫描单链表L2.将第一个结点的link 域置为NULL3.将第二个结点的link域指向第一个结点4.将第三个结点的link域指向第二个结点5.如此.直到最后个结点,便用head指向它1234 head4321 headvoid 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;几种变形的线性链表 环形链表 线性链表的最后一个结点的指针

14、指向第一个结点headhead.空的环形链表非空的环形链表head=NULL几种变形的线性链表 带表头结点的链表 在链表中增加一个附加结点,称之为表头结点headhead. 空的带表头结点的链表非空的带表头结点的链表表头结点表头结点几种变形的线性链表 带表头结点的环形链表 在带表头结点的链表中,链表中最后一个结点的指针指向表头结点headhead.空的带表头结点的环形链表非空的带表头结点的环形链表表头结点表头结点1.不带头结点的链表head为空的判定条件是( ) A. head=NULL B. head-link=NULL C. head-link=head D. head!=NULL2.带头结点的链表head为空的判定条件是( ) A. head=NULL B. head-link=NULL C. head-link=head D. head!=NULL3.若p指向非空环形链表head的尾结点,则p满足( ) A.p-link=NULL B.p=NULL C.p-li