2019考研计算机数据结构考点：栈和队列的链式存储结构
根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。三、栈和队列的链式存储结构
1.栈的链式存储结构
1.1概念
采用链式存储结构称链栈，并由其栈顶指针惟一确定。
设ls为栈顶指针，栈=(a1,a2,…,an)，a1为栈底元素，an为栈顶元素。
1.2基本运算
①建栈。
Void initstack(linkstack *s)
{
s->top=NULL;
}
②判栈空。
Int stackempty (linkstack *s)
{
return s->top==NULL;
}
3进栈。
Void push(linkstack *s,datatype x)
{
stacknode *p=(stacknode *)malloc(sizeof(stacknode));
p->data=x;
p->next=s->top;
s->top=p;
}
④退栈。
Datatype pop(linksatck *s)
{
datatype x;
stacknode *p=s->top;
if(stackempty(s))
error(“stack underflow”);
x=p->data;
s->top=p->next;
free(p);
return x;
}
5取栈顶元素。
Datatype stacktop(linkstack *s)
{
if(stackempty(s))
error(“stack is empty”);
return s->top->data;
}
2.队的链式存储结构
2.1概念
用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元
素。如图所示：
http://file.koolearn.com/29461545094950.png
2.2基本运算
①建空队
Void initqueue(linkqueue *q)
{
q->front=q->rear=NULL;
}
②判队空。
Int queueempty(linkqueue *q)
{
return q->front==NULL&&q->rear==NULL;
}
3入队。
Void enqueue(linkqueue *q,datatype x)
{
queuenode *p=(queuenode *)malloc(sizeof(queuenode));
p->data=x;
p->next=NULL;
if(queueempty(q))
q-front=q->rear=p;
else{
q->rear->next=p;
q->rear=p;
}
}
④出队。
Datatype dequeue(linkqueue *q)
{
datatype x;
queuenode *p;
if(queueempty(q))
error(“queue is underflow”);
p=q->front;
x=p->data;
q->front=p->next;
if(q->rear==p) q->rear=NULL;
free(p);
return x;
}
5取队头元素。
Datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(“queue is empty”);
return q->front->data;
}
页:
[1]