循环链表PPT学习教案.pptx

会计学
1
数据结构CC循环链表
堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的 。
设数组名为data，其下标的下界为0，上界为n。
一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。
top
A
D
C
B
3
6
4
2
1
0
5
data
本例中top=4
在C语言中通常用以下方式定义一个顺序栈结构体：
#define N 30
Typedef struct stack
{datatype data[ N ];
Int top;
}sqstack;
链表应用
第1页/共23页
二、堆栈的运算
入栈（push）
入栈的主要操作是先将栈顶指
针加1；然后将入栈元素放到栈
顶指针所指示下值的位置上。
设用指针P表示堆栈，入栈的元
素值为x，则可得到入栈函数如
下：
#define N 30
Typedef struct stack
{datatype data[ N ];
Int top;
}sqstack;
void push ( sqstack *p, datatype x)
{
if (p->top==N-1)
printf(“栈溢出!\n”); /*显示栈满信息*/
else
{
(p->top)++;
p->data[p->top]=x;
}
}
第2页/共23页
#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;
}
2. 出栈（Pop）
出栈运算时，先将栈顶的元
素值赋给某个变量，以备后
面的运算应用；
然后栈顶指针减1，将栈顶位
置下移。
假设已指定的变量为x，则出
栈的函数如下：
第3页/共23页
链堆栈是栈的链接存储表示，它是只允许在表头进行插入和删除运算的单链表。
它与普通的单链表没有什么不同，只是将头指针head改称为栈顶指针top。
链堆栈
第4页/共23页
链堆栈的入栈算法
在栈顶指针是top的链堆栈中插入一个值为x的结点的算法：
void push (linklist top, datatype x)
{
linklist s;
s=new node ;
/*建立一个结点指针*/
s->data=x;
s->next=top;
top=s;
}
第5页/共23页
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;
}
}
链堆栈的出栈算法
第6页/共23页
循环链表与双向链表
循环链表（circular linked list）是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。
循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。
一、循环链表
第7页/共23页

有两个循环单链表，头指针分为head1和head2，编写函数将链表head2链接到链表head1之后，链接后的链表仍保持是循环链表的形式。
解：先分别找到两个链表的表尾，将head2放入链表head1的表尾，将两个链表链接起来，然后将head1放入原head2链表的表尾，构成新的循环链表。
第8页/共23页