数据结构CC+循环链表.pptx

例3.1voidinvert(linklisthead){linklistp,q,r;p=head;q=p->next;while(q!=NULL)/*没有后继时停止*/{r=q->next;q->next=p;p=q;q=r;}head->next=NULL;head=p;}堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的。设数组名为data，其下标的下界为0，上界为n。一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。#defineN30Typedefstructstack{datatypedata[N];Inttop;}sqstack;voidpop(sqstack*p){if(p->top==-1)printf(“空栈!\n”);/*栈为空显示相应的信息*/else{x=p->data[p->top];(p->top)--;/*栈顶位置下移*/}returnx;}链堆栈的入栈算法3.3循环链表与双向链表例3.2算法2.带尾指针的循环链表如果循环链表的结点再采用双向指针，就成为双向循环链表。1.双链表的插入3.4表示稀疏矩阵的十字链表例：稀疏矩阵M及其对应的十字链表如图所示。空表头结点的结构二、堆栈的运算链堆栈是栈的链接存储表示，它是只允许在表头进行插入和删除运算的单链表。它与普通的单链表没有什么不同，只是将头指针head改称为栈顶指针top。intpop(linklisttop){intx;linklistp;if(top==NULL)cout<<“栈为空!”;else{x=top->data;p=top;top=top->next;deletep;returnx;}}例3.21.带头指针的循环链表二、双向链表双链表较单链表虽然要多占用一些存储单元，但对其插入和删除操作以及查找结点的前趋和后继都非常方便。双链表结构是一种对称结构，设指针p指向双链表的某一结点，则双链表的对称性可用下式来表示：p=(p->prior)->next=(p->next)->prior即结点*p的地址既存放在其前趋结点*(p->prior)的后继指针域中，又存放在它的后继结点*(p->next)的前趋指针域中。2.双链表的删除将每行的非零元素结点链接成循环链表，又将每列的非零元素结点链接成循环链表，就构成了十字形的链接结构。对于每行、每列的循环链表都有一个空表头结点，以利于元素的插入和删除运算。这些空表头结点的行号、列号都标成零，以便和其它结点相区别。整个十字链表有一个总的空表头结点，在一般结点标以行号、列号之处，此结点是标出矩阵的行数m和列数n。有一个指针HM指向这个总的空表头结点。小结