2.2 何时选用顺序表、何时选用链表作为线性表的存储结构.ppt

数据结构 C语言版 内 容 2.1 线性表的定义 2.2 基于抽象数据类型线性表的操作 2.3 线性表的存储结构 2.4 基于顺序存储结构的线性表操作算法 2.5 基于链式存储的线性表操作算法 2.6 循环链表的操作算法 2.7 双向链表的操作算法 2.8 顺序存储线性表与链式存储线性表的比较 2.9 一元多项式的表示及相加 第2章　线性表 循环链表的操作与单链表的差别 循环链表的操作与单链表基本一致，差别仅在于算法中的循环条件不是P或 P－netx 是否为空，而是它们是否等于头指针。 1.在双向链表中插入节点 Status ListInsert_Dul(DuLinkList L,int i,ElemType e){??????//在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1≤i≤表长+1。??????if (!(p=GetElemp_DuL(L,i))) //在L中确定第i个元素的位置指针p????????return ERROR; //p=NULL,即第i个元素不存在??????if(!(s=(DuLinkList) malloc (sizeof (DuLNode)))) return ERROR;??????s-data=e;??????s-prior=p-prior; p-prior-next=s;??????s-next=p; p-prior=s;??????return OK;????}//ListInsert_DuL 2.在双向链表中删除节点 Status ListDelete_Dul(DuLinkList L,int i,ElemType e){??????//删除带头结点的双链循环线性表L中第i个元素，i的合法值为1≤i≤表长。??????if (!(p=GetElemp_DuL(L,i))) //在L中确定第i个元素的位置指针p????????return ERROR;??????e=p-data;??????p-prior-next=p-next;??????p-next-prior=p-prior;??????free(p); return OK;????}//ListDelete_DuL 两个多项式的相加操作算法 　　　根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到和多项式中去。????在此，和多项式链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B当前进行比较的某个结点，则比较两个结点中的指数项，有下列三种情况： ????1）指针qa所指结点的指数值＜指针qb所指结点的指数值，则应摘取指针qa所指结点插入到和多项式链表中去；????2）指针qa所指结点的指数值＞指针qb所指结点的指数值，则应摘取指针qb所指结点插入到和多项式链表中去；????3）指针qa所指结点的指数值＝指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。 两个多项式的相加操作算法描述 　　　int cmp(term a,term b);????//依a的指数值(或=)(或)b的指数值，分别返回-1、0和+1 void AddPolyn(polynomial Pa,polynomial Pb){????//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成和多项式。????ha=GetHead(Pa); hb=GetHead(Pb); //ha和hb分别指向Pa和Pb的头结点????qa=NextPos(ha); qb=NextPos(hb); //qa和qb分别指向Pa和Pb中当前结点????while(!Empty(Pa)!Empty(Pb)){ //Pa和Pb均非空??????a=GetCurElem(qa); b=GetCurElem(qb); //a和b为两表中当前比较元素??????switch(*cmp(a,b)){??????case -1: //多项式PA中当前结点的指数值小????????ha=qa; qa=NextPos(Pa,qa); break;??????case 0: //两者的指数值相等????????sum=a.coef+b.coef;????????if (sum!=0.0){ //修改多项式PA中当前结点的系数值?????