数据结构之单链表操作（一）

淩亂°似流年 2022-03-20 10:37 273阅读 0赞

链表和数组作为算法中的两个基本数据结构，在程序设计过程中经常用到。尽管两种结构都可以用来存储一系列的数据，但又各有各的特点。  
1,数组的优势，在于可以方便的遍历查找需要的数据。在查询数组指定位置（如查询数组中的第4个数据）的操作中，只需要进行1次操作即可，时间复杂度为O(1)。但是，这种时间上的便利性，是因为数组在内存中占用了连续的空间，在进行类似的查找或者遍历时，本质是指针在内存中的定向偏移。然而，当需要对数组成员进行添加和删除的操作时，数组内完成这类操作的时间复杂度则变成了O(n)。  
2,链表的特性，使其在某些操作上比数组更加高效。例如当进行插入和删除操作时，链表操作的时间复杂度仅为O(1)。另外，因为链表在内存中不是连续存储的，所以可以充分利用内存中的碎片空间。除此之外，链表还是很多算法的基础，最常见的哈希表就是基于链表来实现的。基于以上原因，我们可以看到，链表在程序设计过程中是非常重要的。本文总结了我们在学习链表的过程中碰到的问题和体会，包括链表的建立，释放，节点的增删改查，链表逆序，以及链表实现的选择排序和快速排序以及链表的遍历等操作。  
链表的定义：

typedef struct Node {
         int data;
         struct Node* next;
     }Node;

1，头插：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70]  
代码如下：

Node* Insert_Last (Node* head ,int data)
    {
        // 判断数据传入是否正确
        if (NULL == head)
        {
            return NULL;
        }
         // 创建新结点并判断创建是否成功
        Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));
        if (NULL == node)
        {
            return NULL;
        }
    
        // 给结点成员变量赋值
        Node* p = head;
        node->data = data;
        node->next = p->next;   // 和头指针的不同：node->next = *h;
    
        // 让新结点变为链表的第一个节点
        p->next = node;
    
        return head;
    }

2，尾插  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70 1]  
代码如下：

Node* Insert_Last(Node* head, int data)
    {
        if (NULL == head)
        {
            return NULL;
        }
         // 创建新结点并判断创建是否成功
        Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));
        if (NULL == node)
        {
            return NULL;
        }
    
        // 给结点成员变量赋值
        node->data = data;
        node->next = NULL;
    
         // 让新结点变为链表的最后一个节点
        Node* tmp = head;
        while(tmp->next)
        {
            tmp = tmp->next;
        }
        //找到链表的尾节点并令尾节点指向node
        tmp->next = node;
    
        return head;
    }

3，查找数据节点

Node* SearchByNode(Node* head, int num)
    {
    	Node* pHead = head;
    	while (pHead)
    	{
    		if (pHead->data == num)
    		{
    			return pHead;
    		}
    		pHead = pHead->pNext;
    	}
       return NULL;
     }

4,删除数据节点

Node *del(Node *head,int num)//删除一个节点 
    {
       Node *p,*p1;
       p=head;
      if(head==NULL)//当链表为空时
      {  
              printf("this table is null\n"); 
             goto end;
      }
      while(num!=p->num&&p->next!=NULL)//判断链表中是否存在该结点
      {
           p1=p;
          p=p->next;
      }
      if(num==p->num)//当结点存在时
      {
           if(p==head)
                       head=p->next;
          else
              p1->next=p->next;
        printf("delete\n");
      }
     else
            printf("not find");//找不到该结点时
      return head;
    }

5，更新节点数据(根据id改name)

重新定义数据结构
    struct Node
    {
         int id;
         char name[20];
         struct Node* next;
    }
    
    void updateNode(Node* head,int id,char *name)
    {  
     Node* pHead = head;
     int len = strlen(name);//长度不包括'\0'
    	while (pHead)
    	{
    		if (pHead->id == id)
    		{
    			strcpy(phead->name,name,len);
    			phead->name[len+1]= '\0';
    		}
    		pHead = pHead->pNext;
    	}
     }

6，选择排序

Node*  SelectSort(Node *head)  
    {  
        Node *pfirst;      /* 排列后有序链的表头指针 */  
        Node *ptail;       /* 排列后有序链的表尾指针 */  
        Node *pminBefore;  /* 保留键值更小的节点的前驱节点的指针 */  
        Node *pmin;        /* 存储最小节点   */  
        Node *p;           /* 当前比较的节点 */  
       
        pfirst = NULL;  
         /*1,在链表中找键值最小的节点。*/  
        while (head != NULL)        
        {  
            /* 注意：这里for语句就是体现选择排序思想的地方 */  
            for (p = head, pmin = head; p->next != NULL; p = p->next) /*循环遍历链表中的节点，找出此时最小的节点。*/  
            {  
                if (p->next->data < pmin->data) /*找到一个比当前min小的节点。*/  
                {  
                    pminBefore = p;           /*保存找到节点的前驱节点：显然p->next的前驱节点是p。*/  
                    pmin       = p->next;     /*保存键值更小的节点。*/  
                }  
            }  
        
        /*上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表。*/  
          
            /*第一件事*/  
            if (pfirst == NULL)     /* 如果有序链表目前还是一个空链表                      */  
            {  
                pfirst = pmin;      /* 第一次找到键值最小的节点。                          */  
                ptail  = pmin;      /* 注意：尾指针让它指向最后的一个节点。                */  
            }  
            else                    /* 有序链表中已经有节点                                */  
            {  
                ptail->next = pmin; /* 把刚找到的最小节点放到最后，即让尾指针的next指向它。*/  
                ptail = pmin;       /* 尾指针也要指向它。                                  */  
            }  
     
            /*第二件事*/  
            if (pmin == head)        /* 如果找到的最小节点就是第一个节点                    */  
            {  
                head = head->next;   /* 显然让head指向原head->next,即第二个节点，就OK       */  
            }  
            else /*如果不是第一个节点*/  
            {  
                pminBefore->next = pmin->next; /*前次最小节点的next指向当前pmin的next,这样就让pmin离开了原链表。*/  
            }  
        }  
    
        if (pfirst != NULL)     /*循环结束得到有序链表first                */  
        {  
            ptail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL */   
        }  
        head = pfirst;  
        return head;  
    }

7，单链表逆序

Node *reserve(Node *head)
    {
            Node *p1,*p2,*p3;　　　　    
            p1=head;
            p2=p1->next;　　　　　　　　　　　　//　这个结点为要移动的结点
            while(p2)
            {
                    p3=p2->next;　　　　　　　//记录的为要移动的结点的下一个结点
                    p2->next=p1;　　　　　　　//移动结点到最前
                    p1=p2;　　　　　　　　　　//移动的结点变为新表头
                    p2=p3;　　　　　　　　　　//下个结点变为要移动的结点
            }
            head->next=NULL;　　　　　　　　//移动完毕后head变为表尾，让它指向为空
            head=p1;　　　　　　　　　　　　　 
            return head;
    }

8,单链表快速排序

//一次快排实现
     Node* GetPartion(Node* pBegin, Node* pEnd)  
    {  
        int key = pBegin->key;  
        Node* p = pBegin;  
        Node* q = p->next;  
      
        while(q != pEnd)  
        {  
            if(q->key < key)  
            {  
                p = p->next;  
                swap(p->key,q->key);  
            }  
      
            q = q->next;  
        }  
        swap(p->key,pBegin->key);  
        return p;  
    }  
     
    void QuickSort(Node* pBeign, Node* pEnd)  
    {  
        if(pBeign != pEnd)  
        {  
            Node* partion = GetPartion(pBeign,pEnd);  
            QuickSort(pBeign,partion);  
            QuickSort(partion->next,pEnd);  
        }  
    }

9，遍历输出节点数据

void print_list(Node* head)
    {
    	Node* p;  //节点声明
    	p = head;   //将pointer节点设为首节点
    	
    	while(p != NULL)
    	{
    		printf("Data number = %d\n", p->num);
    		p = p->next;
    	}
    }

10，释放内存

void free_list(Node* head)
    {
    	Node* p;
    	
    	while(head != NULL)
    	{
    		p = head;
    		head = head->next;
    		free(p);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70]: /images/20220320/76070823de27438abda70abd3502835d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4MzI1_size_16_color_FFFFFF_t_70 1]: /images/20220320/7b562c6210754dc4916b596a56da556b.png