上海古都建筑设计集团,上海办公室装修设计公司,上海装修公司高质量的内容分享社区,上海装修公司我们不是内容生产者,我们只是上海办公室装修设计公司内容的搬运工平台

链表的常见操作

guduadmin503月前

链表

文章目录

  • 链表
    • 创建链表
        • 单链表
          • 实现
          • 错例
          • 循环链表
            • 单独创建
            • 逐节点创建
            • 约瑟夫环问题
            • 删除节点
              • 实现方式一:
              • 实现方式二:
              • 删除节点并建立新链表
              • 逆置链表
                • 实现:
                • 链表排序
                  struct List
                  {
                  	int data;
                  	struct List* next;
                  }
                  

                  创建链表

                  单链表
                  实现
                  struct List* listCreate()
                  {
                  	int data;
                      struct List* head = NULL;
                      struct List* pre = NULL;
                      struct List* current = NULL;
                      
                      while(scanf("%d",&data) && data != -1)
                      {
                          current = (struct List*)malloc(sizeof(struct List));
                          if(head == NULL)
                              head = current;
                          else
                              pre->next = current;
                          current->next = NULL;
                          current->data = data;
                          pre = current;
                      }
                      return head;
                  }
                  
                  错例
                  struct List* listCreate()
                  {
                  	int data;;
                  	struct List* current = NULL;
                  	struct List* head = current;
                  	while (scanf("%d", &data) && data != -1)
                  	{
                  		current = (struct List*)malloc(sizeof(struct List));
                  		if (head == NULL)
                  			head = current;
                  		current->data = data;
                  		current = current->next;
                  	}
                  	return head;
                  }
                  

                  在使用malloc函数开辟的空间中,不要进行指针的移动,因为一旦移动之后可能出现申请的空间和释放空间大小的不匹配

                  循环链表

                  单独创建
                  struct List* circle_listCreate()
                  {
                  	int data;
                      struct List* head = NULL;
                      struct List* pre = NULL;
                      struct List* current = NULL;
                      
                      while(scanf("%d",&data) && data != -1)
                      {
                          current = (struct List*)malloc(sizeof(struct List));
                          if(head == NULL)
                              head = current;
                          else
                              pre->next = current;
                          current->next = head;
                          current->data = data;
                          pre = current;
                      }
                      return head;
                  }
                  
                  逐节点创建
                  void Append(struct List** L,int data)
                  {
                      struct List* head = *L;
                      struct List* newNode = NULL;
                      if((*L) == NULL)
                      {
                          (*L) = (struct List*)malloc(sizeof(struct List));
                          (*L)->data = data;
                          head = (*L);
                          (*L)->next = head;
                      }
                      else
                      {
                          while ((*L)->next != head){
                              (*L) = (*L)->next;
                          }
                          newNode = (struct List*)malloc(sizeof(struct List));
                          newNode->data = data;
                          (*L)->next = newNode;
                          newNode->next = head;
                          *L = head;
                      }
                  }
                  
                  约瑟夫环问题
                  void Append(struct List** L,int data)
                  {
                      struct List* head = *L;
                      struct List* newNode = NULL;
                      if((*L) == NULL)
                      {
                          (*L) = (struct List*)malloc(sizeof(struct List));
                          (*L)->data = data;
                          head = (*L);
                          (*L)->next = head;
                      }
                      else
                      {
                          while ((*L)->next != head){
                              (*L) = (*L)->next;
                          }
                          newNode = (struct List*)malloc(sizeof(struct List));
                          newNode->data = data;
                          (*L)->next = newNode;
                          newNode->next = head;
                          *L = head;
                      }
                  }
                  void Display(struct List* L,int num)
                  {
                      struct List* head = L;
                      struct List* pre = NULL;
                      struct List* kill = NULL;
                      int nodeNum = 0;
                      while (L->next != head)
                      {
                          nodeNum++;
                          L = L->next;
                      }
                      pre = L;
                      L = L->next;
                      nodeNum++;
                      while (nodeNUm)
                      {
                          if (nodeNum == 1)
                          {
                              printf("%d",L->data);
                              free(L);
                              return;
                          }
                          for (int i=1; i < m; i++)
                          {
                              pre = L;
                              L = L->next;
                          }
                          printf("%d ", L->data);
                          kill = L;
                          L = L->next;
                          free(kill);
                          nodeNum--;
                      }
                  }
                  

                  删除节点

                  实现方式一:

                  struct list* listDelete(struct list* L,int data)
                  {
                      struct list* pre = L;
                      struct list* head = L;
                      struct list* kill;
                      
                      while(head != NULL && head->data == m)
                      {
                          kill = head;
                          head = head->next;
                          free(kill);
                      }
                      if(head == NULL)
                          return head;
                      
                      pre = head;
                      kill = head->next;
                      while(kill!=NULL)
                      {
                          if(kill->data == m)
                          {
                              pre->next = kill->next;
                              free(kill);
                              kill = pre->next;
                          }
                          else
                          {
                              pre = kill;
                              kill = kill->next;
                          }
                      }
                      return head;
                  }
                  

                  实现方式二:

                  struct list* listDelete(struct list** L,int data)
                  {
                      struct list* head = (*L), * pre = (*L);
                      struct list* newL = *L;
                      struct list* kill = NULL;
                      while (*L !- NULL)
                      {
                          if((*L)->data == data)
                          {
                              if((*L) == newL)
                                  newL == newL->next;
                              else
                                  pre->next = (*L)->next;
                              kill = (*L);
                              (*L) = (*L)->next;
                              free(kill);
                          }
                          else
                          {
                              pre = (*L);
                              (*L) = (*L)->next;
                          }
                      }
                      *L = newL;
                      return head;
                  }
                  

                  删除节点并建立新链表

                  struct list* list_Delete_Create(struct list** L) //数据为奇数存为新链表
                  {
                      struct list* newhead = NULL, * newcurrent = NULL, * newpre = NULL;
                      struct list* newL = *L;
                      struct list* kill = NULL;
                      struct list* pre = *L;
                      while (*L)
                      {
                          if((*L)->data%2 == 1)
                          {
                              newcurrent = (struct list*)malloc(sizeof(struct list));
                              if(newhead == NULL)
                                  newhead = newcurrent;
                              else
                                  newpre->next = newcurrent;
                              newcurrent->data = (*L)->data;
                              newcurrent->next = NULL;
                              newpre = newcurrent;
                              
                              if((*L) == newL)
                                  newL = newL->next;
                              else
                                  pre-next = (*L)->next;
                              kill = (*L);
                              (*L)=(*L)->next;
                              free(kill);
                          }
                          else
                          {
                              pre = (*L);
                              (*L) = (*L)->next;
                          }
                      }
                      *L = newL;
                      return newhead;
                  }
                  

                  逆置链表

                  实现:

                  struct list* reverse(struct list* L)
                  {
                      struct list* newhead = NULL, * current;
                      while (L != NULL)
                      {
                          current = (struct list*)malloc(sizeof(struct list));
                          current->data = L->data;
                          L = L->next;
                          current->next = newhead;
                          newhead = current;
                      }
                      free(L);
                      return newhead;
                  }
                  

                  链表排序

网友评论

搜索
最新文章
热门文章
热门标签
 
 梦到掉头发怎么化解  女性梦见和死人说话好不好  梦见别人身上流很多血