使用 C 的 DSA - 链接列表

概述

链接列表是包含项目的链接序列。每个链接都包含与另一个链接的连接。链接列表是继数组之后第二常用的数据结构。以下是理解链接列表概念的重要术语。

链接 − 链接列表的每个链接都可以存储称为元素的数据。
下一个 − 链接列表的每个链接都包含指向下一个链接的链接，称为下一个。
LinkedList − LinkedList 包含指向第一个 Link 的连接链接，称为 First。

Linked List 表示

如上图所示，以下是需要考虑的重要点。

LinkedList 包含一个名为 first 的链接元素。
每个 Link 都带有一个数据字段和一个称为 next 的链接字段。
每个 Link 都使用其下一个链接与其下一个链接链接。
Last Link 带有一个空 Link 来标记列表的结尾。

Link List 的类型

以下是各种类型的 Link List。

简单链接列表 − 项目导航仅向前。
双向链接列表 − 项目可以向前和向后导航。
循环链接列表 − 最后一项包含第一个元素的链接作为下一个，并且第一个元素具有到最后一个元素的链接作为上一个。

基本操作

以下是列表支持的基本操作。

插入 − 在列表开头添加一个元素。
删除 − 在列表开头删除一个元素。
显示 −显示完整列表。
搜索 − 使用给定的键搜索元素。
删除 − 使用给定的键删除元素。

插入操作

插入是一个三步过程 −

使用提供的数据创建一个新链接。
将新链接指向旧的第一个链接。
将第一个链接指向这个新链接。

//在第一个位置插入链接
void insertFirst(int key, int data){
    //创建一个链接
    struct node *link = (struct node*) malloc(sizeof(struct node));
    link->key = key;
    link->data = data;
    
    //将其指向旧的第一个节点
    link->next = head;
    
    //将 first 指向新的第一个节点
    head = link;
}

删除操作

删除操作分为两个步骤 −

获取 First Link 指向的 Link 作为临时 Link。
将 First Link 指向 Temp Link 的 Next Link。

//删除第一项
struct node* deleteFirst(){
    //保存对第一个链接的引用
    struct node *tempLink = head;
    
    //将第一个链接的下一个标记为第一个
    head = head->next;
    
    //返回已删除的链接
    return tempLink;
}

导航操作

导航是一个递归步骤过程，是搜索、删除等许多操作的基础。 −

获取第一个链接指向的链接作为当前链接。
检查当前链接是否不为空并显示它。
将当前链接指向当前链接的下一个链接并移动到上一步。

注意 −

//显示列表
void printList(){
   struct node *ptr = head;
   printf("
[ ");
   
   //从头开始
   while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}

高级操作

以下是针对列表指定的高级操作。

排序 − 根据特定顺序对列表进行排序。
反转 − 反转链接列表。

排序操作

我们使用冒泡排序对列表进行排序。

void sort(){
   int i, j, k, tempKey, tempData ;
   struct node *current;
   struct node *next;
   int size = length();
   k = size ;
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = head ;
      next = head->next ;
      for ( j = 1 ; j < k ; j++ ) {            
         if ( current->data > next->data ) {
            tempData = current->data ;
            current->data = next->data;
            next->data = tempData ;

            tempKey = current->key;
            current->key = next->key;
            next->key = tempKey;
         }
         current = current->next;
         next = next->next;                        
      }
   }
}

逆操作

以下代码演示了如何逆向一个单链表。

void reverse(struct node** head_ref) {
   struct node* prev   = NULL;
   struct node* current = *head_ref;
   struct node* next;
   while (current != NULL) {
      next  = current->next;  
      current->next = prev;   
      prev = current;
      current = next;
   }
   *head_ref = prev;
}

示例

LinkedListDemo.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;

//显示列表
void printList(){
    struct node *ptr = head;
    printf("
    [ ");
    
    //从头开始
    while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
    }
    printf(" ]");
}
//在第一个位置插入链接
void insertFirst(int key, int data){
   //创建链接
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   
   //将其指向旧的第一个节点
   link->next = head;
   
   //将 first 指向新的第一个节点
   head = link;
}
//删除第一项
struct node* deleteFirst(){
   //保存对第一个链接的引用
   struct node *tempLink = head;
   
   //将第一个链接旁边的标记为第一个
   head = head->next;
   
   //返回删除的链接
   return tempLink;
}
//列表是否为空
bool isEmpty(){
   return head == NULL;
}
int length(){
   int length = 0;
   struct node *current;
   for(current = head; current!=NULL;
      current = current->next){
      length++;
   }
   return length;
}
//找到具有给定键的链接
struct node* find(int key){
   //start from the first link
   struct node* current = head;

   //如果列表为空
   if(head == NULL){
      return NULL;
   }
   //浏览列表
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //go to next link
         current = current->next;
      }
   }
   //如果找到数据，返回当前链接
   return current;
}
//删除指定键的链接
struct node* delete(int key){
   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
   
   //如果列表为空
   if(head == NULL){
      return NULL;
   }
   //浏览列表
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //store reference to current link
         previous = current;
         
         //move to next link
         current = current->next;             
      }
   }
   //找到匹配项，更新链接
   if(current == head) {
      //将 first 改为指向 next 链接
      head = head->next;
   } else {
      //绕过当前链接
      previous->next = current->next;
   }
   return current;
}
void sort(){
   int i, j, k, tempKey, tempData ;
   struct node *current;
   struct node *next;
   int size = length();
   k = size ;
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = head ;
      next = head->next ;
      for ( j = 1 ; j < k ; j++ ) {            
         if ( current->data > next->data ) {
            tempData = current->data ;
            current->data = next->data;
            next->data = tempData ;

            tempKey = current->key;
            current->key = next->key;
            next->key = tempKey;
         }
         current = current->next;
         next = next->next;                        
      }
   }
}
void reverse(struct node** head_ref) {
   struct node* prev   = NULL;
   struct node* current = *head_ref;
   struct node* next;
   while (current != NULL) {
      next  = current->next;  
      current->next = prev;   
      prev = current;
      current = next;
   }
   *head_ref = prev;
}

main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("Original List: "); 
   //打印列表
   printList();

   while(!isEmpty()){            
      struct node *temp = deleteFirst();
      printf("
Deleted value:");  
      printf("(%d,%d) ",temp->key,temp->data);        
   }         
   printf("
List after deleting all items: ");          
   printList();
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 
   printf("
Restored List: ");  
   printList();
   printf("
");  

   struct node *foundLink = find(4);
   if(foundLink != NULL){
      printf("Element found: ");  
      printf("(%d,%d) ",foundLink->key,foundLink->data);  
      printf("
");  
   } else {
      printf("Element not found.");  
   }
   delete(4);
   printf("List after deleting an item: ");  
   printList();
   printf("
");
   foundLink = find(4);
   if(foundLink != NULL){
      printf("Element found: ");  
      printf("(%d,%d) ",foundLink->key,foundLink->data);  
      printf("
");  
   } else {
      printf("Element not found.");  
   }
   printf("
");  
   sort();
   printf("List after sorting the data: ");  
   printList();
   reverse(&head);
   printf("
List after reversing the data: ");  
   printList();
}

输出

如果我们编译并运行上述程序，则会产生以下输出 −

Original List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56) 
Deleted value:(5,40) 
Deleted value:(4,1) 
Deleted value:(3,30) 
Deleted value:(2,20) 
Deleted value:(1,10) 
List after deleting all items: 
[ ]
Restored List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1) 
List after deleting an item: 
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data: 
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data: 
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]

使用 C 的 DSA 教程

使用 C 的 DSA 有用资源

使用 C 的 DSA - 链接列表

概述

Linked List 表示

Link List 的类型

基本操作

插入操作

删除操作

导航操作

高级操作

排序操作

逆操作

示例

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！