数据算法与结构.ppt
2.3 线性表的链式存储结构n特点：n用一组任意的存储单元存储线性表的数据元素n利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素n每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息n结点n数据域：元素本身信息n指针域：指示直接后继的存储位置数据域 指针域结点ZHAOQIANSUNLIZHOUWUZHENGWANGH例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针线性链表n定义n结点中只含一个指针域的链表叫，也叫单链表实现typedef struct node datatype data; struct node *link;JD;JD *h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD *)malloc(sizeof(JD);系统回收p结点：free(p)ha1a2an h空表头结点.线性链表n头结点：在单链表第一个结点前附设一个结点叫。是整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放线性表的长度等附加信息，也可以不存储任何信息n头结点指针域为空表示线性表为空。线性链表n头指针：n指向链表中的第一个结点；n首元结点：n线性表的第一个元素结点单链表的基本运算n查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULLn算法描述n算法评价While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n nOnTJD *dlbcz(JD *h,int x)JD *p; p=h;while(p!=NULL & p-data!=X)p=p-link;return (p); 单链表的基本运算n插入：在线性表两个数据元素a和b间插入x，已知p指向an算法描述n算法评价pabxss-link=p-link;p-link=s; 1OnT/数据元素的查找，x为要查找的元素void dlbcr(JD *p,int x) JD *s;s=(JD*)malloc(sizeof(JD);s-data=x;s-link=p-link;p-link=s;单链表的基本运算n删除：单链表中删除b，设p指向an算法描述n算法评价pabc 1OnTp-link=p-link-link;void dlbsc(JD *p) JD *q;if(p-link!=NULL)q=p-link; p-link=q-link; free(q); nOnT算法评价h头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0Ch2_3.ch头结点0单链表的基本运算n动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针n算法描述JD* dlbjl(int a,int n)JD *s,*h,*p;int i;h=(JD*)malloc(sizeof(JD);h-data=0;h-link=NULL; for(i=n;i0;i-)s=(JD*)malloc(sizeof(JD); s-data=ai-1; s-link=h-link; h-link=s;return (h);单链表n单链表特点n它是一种动态结构，整个存储空间为多个链表共用n不需预先分配空间n指针占用额外存储空间n不能随机存取，查找速度慢n为什么引入头结点n在一些针对链表的算法中，（如查入，删除、及建表）对其中第一个结点和其余结点的操作，因结构方面的原因而存在差异，从而使算法的设计不方便，加入头结点，使得线性表中第一个元素对应的首元结点变成了链表中的第二个结点，使所有元素结点具有相同的结构，方便算法和程序设计。循环链表(circular linked list)n循环链表是表中最后一个结点的指针指向头结点，使链表构成环状n特点：从表中任一结点出发均可找到表中其他结点，提高查找效率n操作与单链表基本一致,循环条件不同n单链表p或p-link=NULLn循环链表p或p-link=Hhh空表双向链表（double linked list）n单链表具有单向性的缺点，在查找某节点的直接前趋的时间复杂度将达到O(n)。n结点定义typedef struct node datatype element; struct node *prior,*next;JD;priorelementnextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;bcvoid del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);算法描述算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;Pan删除void ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;算法描述算法评价：T(n)=O(1)xSbaP插入2.4 线性表的应用举例n一元多项式的表示及相加n一元多项式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表P表示200001000231)(xxxS但对S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2121)(其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表n单链表的结点定义coefexpnext17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加typedef struct node int coef,exp; struct node *next;JD;设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与q-expp-exp exp: p结点是结果多项式中的一 项，p后移,q不动p-exp q-exp: q结点是结果多项式中的一 项，将q插在p之前,q后移,p不动p-exp = q-exp: 系数相加0：从A表中删去p, 释放p,q，p,q后移0：修改p系数域, 释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可运算规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 Ch2_7.c算法描述void add_poly(JD *pa,JD *pb) JD *p,*q,*u,*pre; int x; p=pa-next; q=pb-next; pre=pa; while(p!=NULL) & (q!=NULL) if(p-expexp) pre=p; p=p-next; else if(p-exp=q-exp) x=p-coef+q-coef; if(x!=0) p-coef=x; pre=p; else pre-next=p-next; free(p); p=pre-next; u=q; q=q-next; free(u); else u=q-next;q-next=p;pre-next=q; pre=q; q=u; if(q!=NULL) pre-next=q; free(pb);重点：线性表的顺序存储； 线性表的链式存储； 顺序表的插入、删除 单链表的插入、删除难点：双向链表的系列操作 线性表的应用。 练习n填空题n线性表是一种典型的 结构。采用 存储结构的线性表叫顺序表N-i+1插入或删除的元素位置n顺序表逻辑上相邻的元素的物理位置 紧邻，单链表中逻辑上相邻的元素的物理位置 紧邻。必定不一定n单链表中除首元结点外，任一结点的存储位置由 指示。其前驱结点的指针域N-in在长度为n的顺序表中第i个元素前插入一个元素，需要移动 个元素，若删除第I个元素，需移动 个元素，移动元素的个数取决于 。数据顺序练习n选择题n以下关于线性表的说法不正确的是( ）nA、线性表中的数据元素可以是数字、字符、记录等不同类型。 nB、线性表中包含的数据元素个数不是任意的。nC、线性表中的每个结点都有且只有一个直接前趋和直接后继。 nD、存在这样的线性表：表中各结点都没有直接前趋和直接后继。练习n线性表的顺序存储结构是一种( )的存储结构。nA、随机存取 nB、顺序存取 nC、索引存取nD、散列存取练习n在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。nA、基地址 nB、结点大小 nC、向量大小 nD、基地址和结点大小练习n4、在等概率情况下，顺序表的插入操作要移动( )结点。nA、全部 nB、一半 nC、三分之一 nD、四分之一练习n5、在( )运算中，使用顺序表比链表好。nA、插入 nB、删除 nC、根据序号查找 nD、根据元素值查找作业： SPR(1) Q=P-next;L24375862437586LSPRQ(2) R-data=P-data;L2437586SPRL2457586SPR(3) R-data=P-next-data;L2437586SPRL2477586SPR(4) P-next-next-next-data=P-data;L2437586SPRL2437556SPR(5) T=P; while(T!=NULL) T-data=(T-data)*2; T=T-next; L2437586SPRL48614101612SPR(6) T=P; while(T-next!=NULL) T-data=(T-data)*2; T=T-next; L2437586SPRL44614101612SPR(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;L2437586SPRP10(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;P10L2437586SPRL2437586SR(8) T=L; T-next=P-next; free(P);LS2837PRT5L2437586SPR3 65 41 11
