软件技术与基础

软件技术基础第3讲基本数据结构及其运算（4）内容提要2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表2.3.1线性链表的基本概念2.3.2线性链表的运算操作2.3.3链式的栈及操作2.3.4链式的队列及操作2.3.5循环链表及运算2.3.6多项式表示与运算2.3.5循环链表及其运算一，循环链表的概念在线性链表运算中，存在一个问题：对于空表和第一个结点的处理必须单独考虑出现分支语句，增加程序复杂度循环链表2.3.5循环链表及其运算一，循环链表的概念循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。2.3.5循环链表及其运算二，循环链表的特点1）循环链表中增加一个表头结点，其数据域为任意或根据需要来设置，指针域指向第一个元素的节点，循环链表的头指针指向表头结点。2）在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。思考：空表、表尾的判定依据？2.3.5循环链表及其运算二，循环链表的特点空表的判定头结点的指针域是否指向头结点。head-next?=head尾节点判定该节点的指针是否指向头结点。p-next?=head2.3.5循环链表及其运算二，循环链表的特点空表的判定头结点的指针域是否指向头结点。head-next?=head尾节点判定该节点的指针是否指向头结点。p-next?=head2.3.5循环链表及其运算三，循环链表的优点1）给出表中任意结点的位置，可以访问到表中其他所有的结点。2）由于表头结点的存在，任何情况下循环链表中至少存在一个结点，使空表和非空表实现统一。2.3.5循环链表及其运算四，循环链表的运算插入将新结点插入到指定结点之后。1）申请新结点的存储空间；2.1）指定结点为头结点，头结点的指针指向新结点，新结点的指针指向指定结点。2.2）指定结点为中间结点，新结点指针指向指定结点，指定结点前结点指针指向新结点。2.3.5循环链表及其运算四，循环链表的运算插入clinkinsertnode(clinkhead,clinkptr,intvalue){clinknew_node;new_node=(clink)malloc(sizeof(cnode));if(!new_node)returnNULL;new_node-data=value;new_node-next=NULL;if(head==NULL){new_node-next=new_node;returnnew_node;}2.3.5循环链表及其运算四，循环链表的运算插入if(ptr==head-next){/*----情况1：插在第一结点之前---*/new_node-next=head-next;head-next=new_node;}else{/*-----情况2：插在第一结点之后-------*/new_node-next=ptr-next;ptr-next=new_node;}returnhead;}2.3.5循环链表及其运算四，循环链表的运算删除删除循环链表中指定结点。1）判断循环链表是否有结点；2）寻找指定结点的前结点；3）指定结点前结点指向的改变。2.3.5循环链表及其运算四，循环链表的运算删除clinkdeletenode(clinkhead,clinkptr){clinkprevious;previous=head;if(head!=head-next)while(previous-next!=ptr)previous=previous-next;previous-next=ptr-next;}例题2.3.5循环链表及其运算四，循环链表的运算出队DataTypeDeQueue(LinkQueue*Q){DataTypex;QueueNode*p;if(QueueEmpty(Q))Error(“Queueunderflow”);//下溢p=Q-front-next;//指向对头结点x=p-data;//保存对头结点的数据Q-front-next=p-next;//将对头结点从链上摘下if(Q-rear==p)Q-rear=NULL;free(p);//释放被删队头结点returnx;//返回原队头数据}内容提要2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表2.3.1线性链表的基本概念2.3.2线性链表的运算操作2.3.3链式的栈及操作2.3.4链式的队列及操作2.3.5循环链表及运算2.3.6多项式表示与运算2.3.6多项式的表示与计算一，多项式的存储问题Pn(x)=anxn+an-1xn-1+…+a1x+a0当多项式中存在大量0系数时，太浪费存储空间，为了合理利用存储空间，可以用链式表来表示。2.3.6多项式的表示与计算二，多项式的表示可以采用线性单链表或者循环链表方式。2.3.6多项式的表示与计算三，多项式的结点结构多项式的非零系数结点结构的数据域包括指数项和系数项两部分；指针域指针指向下一个非零系数项。structnode{intexp;//指数为整型doublecoef;//系数为双精度型node*next;//指针域};2.3.6多项式的表示与计算四，多项式的运算多项式的运算包括多项式链表的生成、释放、多项式的输出、相加和相乘等。建立空多项式链表voidinit_poly(){node*p;p=newnode;//申请一个表头结点p-exp=-1;p-next=p;head=p;return;}2.3.6多项式的表示与计算四，多项式的运算从键盘输入多项式链表voidcreate_poly(){node*p,*k;inte;doublec;k=head;//记住多项式链尾cout“输入:系数空格指数。输入指数-1结束！”endl;//降幂cince;while(e=0){p=newnode;//申请一个新结点p-exp=e;p-coef=c;//填入指数与系数p-next=head;//新结点链到临时多项式链尾k-next=p;k=p;//记住多项式链尾cince;}return;}2.3.6多项式的表示与计算四，多项式的运算从数组复制多项式链表voidcreate2_poly(intn,inte[],doublec[]){intk;node*p;for(k=n-1;k=0;k--){p=newnode;//申请一个新结点p-coef=c[k];p-exp=e[k];//置系数与指数域p-next=head-next;//新结点链到表头head-next=p;}return;}2.3.6多项式的表示与计算四，多项式的运算释放多项式链表voiddel_poly(){node*p,*q;q=head-next;while(q!=head){p=q-next;deleteq;q=p;}q-next=head;return;}2.3.6多项式的表示与计算四，多项式的运算输出多项式链表voidprt_poly(){node*k;if(head-next==head)cout空表endl;k=head-next;while(k!=head){cout(k-coef,k-exp)endl;k=k-next;}return;}2.3.6多项式的表示与计算四，多项式的运算多项式相加voidadd(Poly&p2,Polyp){node*k,*q,*m,*n;inte;doublec;k=p.head;//记住和多项式链尾m=head-next;n=p2.head-next;while((m-exp!=-1)||(n-exp!=-1)){if(m-exp==n-exp)//两个链表当前结点的指数相等{c=m-coef+n-coef;//系数相加e=m-exp;//复抄指数m=m-next;n=n-next;}elseif(m-expn-exp){c=m-coef;e=m-exp;//复抄链表1中的系数与指数值m=m-next;}2.3.6多项式的表示与计算四，多项式的运算多项式相加else{c=n-coef;e=n-exp;//复抄链表2中的系数与指数值n=n-next;}if(c!=0)//相加后系数不为0{q=newnode;//申请一个新结点q-exp=e;q-coef=c;q-next=p.head;k-next=q;k=q;//记住和多项式的链尾}}return(p);}