数据结构 C C++ 循环链表.pptVIP

例3.1 有一个单链表L(至少有一个结点)，其头结点指针为head，编写一个函数将L逆置，即最后一个结点变成第1个结点，原来倒数第二个结点变成第二个结点……如此等等。 解：本题采用的算法是，从头到尾遍历单链表L，并设置3个附加指针p、q、r,p指向当前处理的结点，q指向p的下一个结点，r指向q的下一个结点，q、r的作用是为了防止倒置指针时，下一个结点的丢失而设置的，有了这三个指针，就可以方便地实现指针的倒置。最后将第一个结点的next域置为NULL，并将头指针指向最后一个结点，这样达到了本题的要求。 void invert( linklist head) { linklist p, 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也叫做栈指针。 二、堆栈的运算 入栈（push） 入栈的主要操作是先将栈顶指 针加1；然后将入栈元素放到栈 顶指针所指示下值的位置上。 设用指针P表示堆栈，入栈的元 素值为x，则可得到入栈函数如 下： #define N 30 Typedef struct stack {datatype data[ N ]; Int top; }sqstack; void pop (sqstack *p) { if (p-top== -1) printf(“空栈!\n”); /*栈为空显示相应的信息*/ else { x=p-data[p-top]; ( p- top)--; /*栈顶位置下移*/ } return x; } 链堆栈是栈的链接存储表示，它是只允许在表头进行插入和删除运算的单链表。 它与普通的单链表没有什么不同，只是将头指针head改称为栈顶指针top。 链堆栈的入栈算法 在栈顶指针是top的链堆栈中插入一个值为x的结点的算法： void push (linklist top, datatype x) { linklist s; s=new node ; /*建立一个结点指针*/ s-data=x; s-next=top; top=s; } int pop(linklist top) { int x; linklist p; if( top= = NULL) cout“栈为空!” ; else {x=top-data; p=top; top=top-next; delete p; return x; } } 3.3 循环链表与双向链表 循环链表（circular linked list）是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。 循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。 例3.2 有两个循环单链表，头指针分为head1和head2，编写函数将链表head2链接到链表head1之后，链接后的链表仍保持是循环链表的形式。 解：先分别找到两个链表的表尾，将head2放入链表head1的表尾，将两个链表链接起来，然后将head1放入原head2链表的表尾，构成新的循环链表。 例3.2算法 link(linklist head1,head2) { linklist p, q; p=head1; while(p-next!=head1) p=p-