[数据结构]对链表、栈、队列的总结

racaljk

发布于 2018-08-31 11:09:40

4230

发布于 2018-08-31 11:09:40

文章被收录于专栏：racaljkracaljk

1.定义

前面已经已经说过了这三种结构之间有联系，这里特意总结一下

首先我们考虑一下三种结构定义：

//链表
struct node{
  struct node *next;
  int data;
};

//栈
struct node{
  int data;
  struct node *next;
};

struct stack{
  struct node *top;
  struct node *buttom;
};

//队列
struct node{
  int data;
  struct node *next;
};

struct queue{
  struct node *front;
  struct node *rear;
}

你应该发现了一些异常，为什么链表只有node的定义？再来细想一下这三种模型，我们会发现链表其实就是由节点组成的，而栈和队列我们把它视作一个容器，然后可以向里面放node，我们的链表也有头指针和尾指针，我们完全可以这样定义： struct linkedlist{

struct node *head;

struct node *tail;

};

这样没有任何问题，只是大家都已经习惯了使用之前的方法，因为我们能发现头指针已经弱化为了节点，就像这样：

struct node *head;

struct node *A=new node;

struct node *B=new node;

A->next=B;//这里不考虑对AB进行赋值

B->next=NULL;

head = A;//notice

2.插入

这里让我们回想一下插入：

//链表插入(由于链表两头都可插入，这里选择了尾部插入)
struct node *n=new node;
tail->next=n
n->next=NULL;
tail=n;

//队列插入(队列只允许rear插入)
struct node *n=new node;
queue->rear->next=n;
n->next=NULL;
queue->rear=n;


//栈插入
struct node *n=new node;
n->next=stack->top;
stack->top=n;

提醒一点，队列需要判断是否为空。

从上面你又能发现先链表和队列的插入惊人的相似，而栈有些不同，原因你把这些数据结构图在脑中里面想想就能明白了，队列和链表节点都是横着放，而栈是竖着的，所以栈插入一个节点必然next会指向一个节点而队列和链表由于在尾巴上插入所以next指向NULL

3.删除

接着考虑删除操作：

//链表
struct node *temp=head;
head=head->next;
delete temp;
//队列(同样需要考虑队列是否为空)
struct node *temp=queue->front;
queue->front=queue->front->next;
delete temp;
//栈(需要考虑是否为空栈)
struct node *temp=stack->top;
stack->top=temp->next;
delete temp;

种种表面，这三种结构间存在一些联系，如果能考虑到这里那说明学得不错，因为我们的科学家把他们分为了线性结构，当然剩下的树和图就是非线性结构

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-11-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度