软件技术与基础.ppt

《软件技术与基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、软件技术基础第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、点或者表头结点，从而构成一个环形的链。2.3.5循环链表及其运算二，循环链表的特点1）循环链表中增加一个表头结点，其数据域为任意或根据需要来设置，指针域指向第一个元素的节点，循环链表的头指针指向表头结点。2）在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。思考：空表、表尾的判定依据？2.3.5循环链表及其运算二，循环链表的特点空表的判定头结点的指针域是否指向头结点。head->next?=head尾节点判定该节点的指针是否指向头结点。p->next?=head2.3.5循环链表及

3、其运算二，循环链表的特点空表的判定头结点的指针域是否指向头结点。head->next?=head尾节点判定该节点的指针是否指向头结点。p->next?=head2.3.5循环链表及其运算三，循环链表的优点1）给出表中任意结点的位置，可以访问到表中其他所有的结点。2）由于表头结点的存在，任何情况下循环链表中至少存在一个结点，使空表和非空表实现统一。2.3.5循环链表及其运算四，循环链表的运算插入将新结点插入到指定结点之后。1）申请新结点的存储空间；2.1）指定结点为头结点，头结点的指针指向新结点，新结点的指针指向指定结点。2.2）指定结点为中间结点，新结点指针指向指定结点，指

4、定结点前结点指针指向新结点。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循环链表及其运算四，循环链表的运算

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循环链表及其运算四，循环链

6、表的运算删除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(QueueEmpt

7、y(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