当前位置：首页 > news >正文

zfk_蓝桥杯C++学习_语言基础_链表、栈、队列

news 2026/5/12 6:47:36

一、链表

1.线性链表：
链表是一组存储线性表的数据元素存储单元;
由若干个节点组成，结点包括两个域:
其中存储数据元素信息的称为数据域;存储直接后继存储位置有域称为指针域。

2.链表的基本操作：
（1）链表存储结构

typedef int ElemType;
typedef struct node
{ElemType data;  //数据域struct node *next;  //指针域
} Node;

（2）单链表-初始化

Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}
int main ()
{Node *list = initList();return 1;
}

（3）单链表-头插法

int insertHead (Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;
}
int main ()
{Node *list = initList();insertHead(list, 10);insertHead(list, 20);
}

（4）单链表-遍历

void listNode (Node* L)
{Node *p = L->next;while (p != NULL){printf ("%dn", p->data) ;p = p->next;}printf("\n");
}

（5）单链表-获取链表长度

int listLength (Node *L)
{Node *p = L;int len = 0;while (p != NULL){p = p->next;len++;}return len;
}

（6）单链表-尾插法

Node* get_tail (Node *L)
{Node *p = L;while (p->next != NULL){p = p->next;}return p;
}

（7）单链表-在指定位置插入数据

int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL)return 0;}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}

（8）单链表-删除节点

int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}

（9）单链表-释放链表

void freeList (Node *L)
{Node *p = L->next;Node *q;while (p != NULL){q = p->next;free (p) ;p = q;}L->next = NULL;
}

3.双向链表：

链式存储结构的节点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针向后寻查其他节点。若要寻查结点的直接前驱、则必须从表头指针出发。换句话说,在单链表中,查找直接后继的执行时间为O(1),而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点,可利用双向链表。在双向链表的节点中有两个指针域,一个指向直接后继,另一个指向直接前驱。

双向链表的结构

typedef int ElemType;typedef struct node
{ElemType data;struct node *prev, *next; //prev为前驱结点，next为后继结点
} Node;

二、栈

1.栈(stack)是限定仅在表尾进行插入或删除操作的线性表。
因此对栈来说,表尾端有其特殊含义,称为栈顶(top),相应地,表头端称为栈底(bottom)。不含元素的空表称为空栈。
假设S=(a1,a2,…,an),则称a1为栈底元素,an为栈顶元素。栈中元素按a1,a2,…,an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按照后进先出的原则进行的。
因此,栈又称为后进先出(Last In First Out,LIFO)的线性表。
栈是限制插入和删除操作只能在一个位置进行的表,该位置是表的末端,叫作栈顶(top)。对栈的基本操作有进栈(push)和出栈(Pop),前者相当于插入,后者则是删除最后插入的元素。

2.栈的基本操作：

（1）栈的链式结构实现：

typedef int ElemType;
typedef struct stack
{ElemType data;struct stack *next;
} Stack;

（2）栈的链式结构实现-初始化：

typedef int ElemType;
typedef struct stack
{ElemType data;struct stack *next;
} Stack;
Stack* initStack ()
{Stack *s = (Stack*)malloc(sizeof(Stack));s->data = 0;s->next = NULL;return s;
}

（3）栈的链式结构实现-判断栈是否为空

int isEmpty (Stack *s)
{if (s->next == NULL){printf("空的\n");return 1;}else{return 0;}
}

（4）栈的链式结构实现-进栈/压栈

int push (Stack *s, ElemType e)
{Stack *p = (Stack*)malloc(sizeof(Stack));p->data = e;p->next = s->next;s->next = p;return 1;
}

（5）栈的链式结构实现-出栈

int pop(Stack *s, ElemType *e)
{if (s->next == NULL){printf("空的\n");return 0;}*e = s->next->data;Stack *q = s->next;s->next = q->next;free (q) ;return 1;
}

（6）栈的链式结构实现-获取栈顶元素

int getTop(Stack *s, ElemType *e)
{if (s->next == NULL){printf("空的\n");return 0;}*e = s->next->data;return 1;
}

三、队列

1.队列(queue)是一种先进先出的线性表。
它只允许在表的一端进行插入,而在另一端删除元素。在队列中,允许插入的一端称为队尾,允许删除的一端则称为队头。假设队列为q=(a1,a2,…,an),那么,a1就是队头元素,an就是队尾元素。
队列中的元素是按照a1,a2,…,an的顺序进入的,退出队列也只能按照这个次序依次退出,也就是说,只有在a1,a2,…,an-1都离开队列之后,an才能退出队列。

2.队列的基本操作：

（1）队列的链式结构-初始化

Queue* initQueue ()
{Queue *q = (Queue*) malloc(sizeof (Queue));QueueNode *node = (QueueNode*)malloc(sizeof (QueueNode)) ;node->data = 0;node->next = NULL;q->front = node;q->rear = node;return q;
}

（2）队列的链式结构

typedef struct QueueNode
{ElemType data;struct QueueNode *next;
} QueueNode;
typedef struct
{QueueNode *front;QueueNode *rear;
} Queue;

（3）队列的链式结构-初始化

Queue* initQueue ()
{Queue *q = (Queue*)malloc(sizeof (Queue));QueueNode *node = (QueueNode*)malloc(sizeof (QueueNode));node->data = 0;node->next = NULL;q->front = node;q->rear = node;return q;
}

（4）队列的链式结构-判断队列是否为空

int isEmpty (Queue *q)
{if (q->front == q->rear){return 1;}else{return 0;}
}

（5）队列的链式结构-入队

void equeue (Queue *q, ElemType e)
{QueueNode *node = (QueueNode*) malloc(sizeof (QueueNode)) ;node->data = e;node->next = NULL;q->rear->next = node;q->rear = node;
}

（6）队列的链式结构-出队

int dequeue(Queue *q, ElemType *e)
{QueueNode *node = q->front->next;*e = node->data;q->front->next = node->next;if (q->rear == node){q->rear = q->front;}free (node) ;return 1;
}

（7）队列的链式结构-获取队头元素

ElemType getFront (Queue *q)
{if (isEmpty (q)){printf("空的\n");return 0;}return q->front->next->data;
}

四、总结

1.基本操作的实现共性与差异
（1）共性
1.存储基础：链表、栈（链式）、队列（链式）均基于节点 + 指针的链式存储结构，通过动态内存分配（malloc）创建节点，借助指针维护元素间的逻辑关系，最终都需通过free释放内存以避免泄漏。

2.初始化逻辑：三者初始化均需创建头节点（或头指针），并将指针域置空（NULL），为后续操作建立初始的空结构。

3.遍历 / 访问逻辑：都需通过指针遍历节点实现元素访问，且访问过程中需判断指针是否为空以防止越界。
（2）差异

结构	核心操作位置	核心操作	时间复杂度（核心操作）	典型应用场景
单链表	任意位置	头插、尾插、指定位置插入 / 删除	插入 / 删除 O (1)（已知位置）、遍历 O (n)	动态数据存储、不定长数据管理
双向链表	任意位置	前驱 / 后继节点的查找与操作	查找前驱 O (1)、其他同单链表	需频繁查找前驱的场景（如链表排序）
栈（链式）	栈顶	压栈、出栈	压栈 / 出栈 O (1)	表达式求值、函数调用栈、回溯算法
队列（链式）	队尾（插入）、队头（删除）	入队、出队	入队 / 出队 O (1)	任务排队、消息队列、广度优先搜索