顺序表 链表 栈 队列之间的关系
- 顺序表:array list---->基于数组实现的线性表,元素在内存中是连续存储的。
- 链表:linked list ---->通过指针将一系列节点连接起来的线性表
- 单链表:next指针
- 双链表:prior+next指针 //430扁平化多级双向链表
- 栈:stack---->线性数据结构,先进后出,实现方式:链表/顺序表 pop push top
- 队列:queue---->线性数据结构,先进先出,实现方式:顺序表/链表 enqueue dequeue
顺序表 和 链表 都是线性表,前者基于数组实现,后者基于指针实现。
栈 和 队列 是两种特殊的线性表,它们可以基于顺序表或链表实现,但在操作原则上有所不同,栈是LIFO,队列是FIFO。
//单链表
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode;
//双链表
typedef struct DLNode{
ElemType data;
struct DLNode* next;
struct DLNode* prior;
}DLNode;
//顺序表
typedef struct Sqlist{
ElemType data[maxsize];
int length;
}Sqlist;
练习题(手写代码内容)
【说明】由于考试中通常更注重基本概念和传统方法,理解链表的基本操作会帮助掌握这些概念。建议掌握不使用哑节点的方法,以便在考试中灵活应对各种问题。
- A和B是两个带头节点的元素递增有序的单链表。设计一个算法将A 和B 合并成非递减有序的单链表C。【21 合并两个有序链表】
void Merge(LNode *& A,LNode *&B,LNode *&C){
//排除AorB为空链表的情况,不令C=A orB来获取相同的头节点。
C = (LNode*)malloc(sizeof(LNode));
C->next = NULL;
LNode *p = A->next;
LNode *q = B->next;
LNode *r;
r = C;
while(p&&q){
if(p->data <= q->data){
r->next = p;
p = p->next;
}else{
r->next = q;
q = q->next;
}
r = r->next;
}
if(p){r->next = p;}
else{r->next = q;}//如果二者同时结束,r->next = NULL;就刚好
}
- 尾插法建立单链表
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode;
void Createl(LNode *&L,ElemType a[],int n){
L = (LNode*)malloc(sizeof(LNode));
//增加内存分配失败检查
if(L == NULL){
printf("Memory allocation failed\n");
return;
}
L->next = NULL;
LNode *r = L;//尾指针初始化为头节点
for(int i = 0 ; i < n ; i++){
LNode *s = (LNode*)malloc(sizeof(LNode));
if(s == NULL){
printf("Memory allocation failed\n");
return;
}
s->data = a[i];
s->next = NULL;
r->next = s;//将新节点连接到链表的尾部
r = s;//更新尾指针为新节点
}
}
- 头插法建立单链表
void CreateH(LNode *&L, Elemtype a[],int n){
L = (LNode*)malloc(sizeof(LNode));
if(L == NULL){
printf("Memory allocation failed.\n");
return;
}
L->next = NULL;
for(int i = 0; i < n ; i++){
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s == NULL){
printf("Memory allocation failed.\n");
return;
}
s->data = a[i];
s->next = L->next;
L->next = s;
}
}
头插法不需要新建LNode* r;令r = L;r一般做尾指针,在尾插法中才会需要。
- 查找带头节点的单链表L中是否存在节点x,如果存在则删除x节点。【237 删除链表中的节点】前提:只存在一个这样的节点
int SearchDel(LNode *&L, ElemType x) {
LNode *prev = L, *curr = L->next;
while (curr) {
if (curr->data == x) {
prev->next = curr->next;
free(curr);
return 1;
} else {
prev = curr;
curr = curr->next;
}
}
return 0;
}
- 利用尾插法建立双链表
void CreateDL(DLNode *&L, ElemType a[], int n) {
L = (DLNode*)malloc(sizeof(DLNode));
if (L == NULL) {
printf("Memory allocation failed.\n");
return;
}
L->prior = NULL;
L->next = NULL;
DLNode* r = L; // 尾指针
for (int i = 0; i < n; i++) {
DLNode* s = (DLNode*)malloc(sizeof(DLNode));
if (s == NULL) {
printf("Memory allocation failed.\n");
return;
}
s->data = a[i];
s->prior = r;
s->next = NULL;
r->next = s;
r = s;
}
}
- 双链表查找值x
DLNode *Search(DLNode *L, ElemType x){
DLNode *s = L->next;
while(s){
if(s->data == x){
return s;
}
s = s->next;
}
return NULL;
}
- 双链表在节点p后插入s
void InsertAfter(DLNode *p, DLNode *s) {
s->next = p->next;
s->prior = p;
if (p->next != NULL) { // 如果p的next不为空,将p的next的prior指向s
p->next->prior = s;
}
p->next = s; // 将p的next指向s
}
- 双链表删除p的next节点
void DeleteNext(DLNode *p) {
DLNode *q = p->next;
if (q != NULL) { // 如果q不为空,继续删除操作
p->next = q->next;
if (q->next != NULL) { // 如果q的next不为空,将q的next的prior指向p
q->next->prior = p;
}
free(q); // 释放q节点
}
}
7 8 两个注释部分容易遗忘