软件技术与基础

软件技术基础第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?=head

2.3.5循环链表及其运算二，循环链表的特点空表的判定

头结点的指针域是否指向头结点。

head->next?=head尾节点判定

该节点的指针是否指向头结点。

p->next?=head

2.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;//降幂cin>>c>>e;while(e>=0){p=newnode;//申请一个新结点

p->exp=e;p->coef=c;//填入指数与系数

p->next=head;//新结点链到临时多项式链尾

k->next=p;k=p;//记住多项式链尾

cin>>c>>e;}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->exp>n->exp) {c=m->coef;e=m->exp;//复抄链表1中的系数与指数值

m=m->next;}2.3.6多项式的表示与计算四，多项式的运算多项式相加