7.21 复习数据结构相干知识【主链表】

顺序表 链表 栈 队列之间的关系

• 顺序表：array list---->基于数组实现的线性表，元素在内存中是一连存储的。
  
• 链表：linked list ---->通过指针将一系列节点连接起来的线性表
  
  
  
  • 单链表：next指针
    
  • 双链表：prior+next指针 //430扁平化多级双向链表
    
  
  
• 栈：stack---->线性数据结构，先进后出，实现方式：链表/顺序表 pop push top
  
• 队列：queue---->线性数据结构，先进先出，实现方式：顺序表/链表 enqueue dequeue
  

   顺序表 和 链表 都是线性表，前者基于数组实现，后者基于指针实现。
栈 和 队列 是两种特殊的线性表，它们可以基于顺序表或链表实现，但在操纵原则上有所不同，栈是LIFO，队列是FIFO。

1. //单链表
2. typedef struct LNode{
3.         ElemType data;
4.         struct LNode* next;
5. }LNode;
6. //双链表
7. typedef struct DLNode{
8.         ElemType data;
9.         struct DLNode* next;
10.         struct DLNode* prior;
11. }DLNode;
12. //顺序表
13. typedef struct Sqlist{
14.         ElemType data[maxsize];
15.         int length;
16. }Sqlist;

复制代码

训练题(手写代码内容)

【说明】由于考试中通常更注意基本概念和传统方法，理解链表的基本操纵会帮助掌握这些概念。发起掌握不使用哑节点的方法，以便在考试中灵活应对各种题目。

• A和B是两个带头节点的元素递增有序的单链表。设计一个算法将A 和B 合并成非递减有序的单链表C。【21 合并两个有序链表】
  

1. void Merge(LNode *& A,LNode *&B,LNode *&C){
2.         //排除AorB为空链表的情况，不令C=A orB来获取相同的头节点。
3.         C = (LNode*)malloc(sizeof(LNode));
4.         C->next = NULL;
5.        
6.         LNode *p = A->next;
7.         LNode *q = B->next;
8.         LNode *r;
9.         r = C;
10.         while(p&&q){
11.                 if(p->data <= q->data){
12.                         r->next = p;
13.                         p = p->next;
14.                 }else{
15.                         r->next = q;
16.                         q = q->next;
17.                 }
18.                 r = r->next;
19.         }
20.         if(p){r->next = p;}
21.         else{r->next = q;}//如果二者同时结束，r->next = NULL;就刚好
22. }

复制代码

• 尾插法建立单链表
  

1. typedef int ElemType;
2. typedef struct LNode{
3.                 ElemType data;
4.                 struct LNode* next;
5. }LNode;
6. void Createl(LNode *&L,ElemType a[],int n){
7.         L = (LNode*)malloc(sizeof(LNode));
8.         //增加内存分配失败检查
9.         if(L == NULL){
10.                 printf("Memory allocation failed\n");
11.         return;
12.         }
13.         L->next = NULL;
14.         LNode *r = L;//尾指针初始化为头节点
15.        
16.         for(int i = 0 ; i < n ; i++){
17.                 LNode *s = (LNode*)malloc(sizeof(LNode));
18.                 if(s == NULL){
19.                         printf("Memory allocation failed\n");
20.                         return;
21.                 }
22.                 s->data = a[i];
23.                 s->next = NULL;
24.                 r->next = s;//将新节点连接到链表的尾部
25.                 r = s;//更新尾指针为新节点
26.         }
27. }

复制代码

• 头插法建立单链表
  

1. void CreateH(LNode *&L, Elemtype a[],int n){
2.         L = (LNode*)malloc(sizeof(LNode));
3.         if(L == NULL){
4.                 printf("Memory allocation failed.\n");
5.                 return;
6.         }
7.         L->next = NULL;
9.         for(int i = 0; i < n ; i++){
10.                 LNode* s = (LNode*)malloc(sizeof(LNode));
11.                 if(s == NULL){
12.                         printf("Memory allocation failed.\n");
13.                         return;
14.                 }
15.                 s->data = a[i];
16.                 s->next = L->next;
17.                 L->next = s;
18.                
19.         }
20. }

复制代码

头插法不需要新建LNode* r;令r = L;r一般做尾指针，在尾插法中才会需要。

• 查找带头节点的单链表L中是否存在节点x，假如存在则删除x节点。【237 删除链表中的节点】条件：只存在一个这样的节点
  

1. int SearchDel(LNode *&L, ElemType x) {
2.     LNode *prev = L, *curr = L->next;
4.     while (curr) {
5.         if (curr->data == x) {
6.             prev->next = curr->next;
7.             free(curr);
8.             return 1;
9.         } else {
10.             prev = curr;
11.             curr = curr->next;
12.         }
13.     }
14.     return 0;
15. }

复制代码

• 使用尾插法建立双链表
  

1. void CreateDL(DLNode *&L, ElemType a[], int n) {
2.     L = (DLNode*)malloc(sizeof(DLNode));
3.     if (L == NULL) {
4.         printf("Memory allocation failed.\n");
5.         return;
6.     }
7.     L->prior = NULL;
8.     L->next = NULL;
9.     DLNode* r = L; // 尾指针
11.     for (int i = 0; i < n; i++) {
12.         DLNode* s = (DLNode*)malloc(sizeof(DLNode));
13.         if (s == NULL) {
14.             printf("Memory allocation failed.\n");
15.             return;
16.         }
17.         s->data = a[i];
18.         s->prior = r;
19.         s->next = NULL;
20.         r->next = s;
21.         r = s;
22.     }
23. }

复制代码

• 双链表查找值x
  

1. DLNode *Search(DLNode *L, ElemType x){
2.         DLNode *s = L->next;
3.         while(s){
4.                 if(s->data == x){
5.                         return s;
6.                 }
7.                 s = s->next;
8.         }
9.         return NULL;
10. }

复制代码

• 双链表在节点p后插入s
  

1. void InsertAfter(DLNode *p, DLNode *s) {
2.     s->next = p->next;      
3.     s->prior = p;         
5.     if (p->next != NULL) {  // 如果p的next不为空，将p的next的prior指向s
6.         p->next->prior = s;
7.     }
9.     p->next = s;            // 将p的next指向s
10. }

复制代码

• 双链表删除p的next节点
  

1. void DeleteNext(DLNode *p) {
2.     DLNode *q = p->next;   
3.     if (q != NULL) {       // 如果q不为空，继续删除操作
4.         p->next = q->next;
6.         if (q->next != NULL) { // 如果q的next不为空，将q的next的prior指向p
7.             q->next->prior = p;
8.         }
10.         free(q); // 释放q节点
11.     }
12. }

复制代码

7 8 两个表明部门轻易忘记

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。