链表的常见操作

链表

文章目录

• 链表
• • 创建链表
  • • • 单链表
      • • 实现
        • 错例
        • 循环链表
        • • 单独创建
          • 逐节点创建
          • 约瑟夫环问题
          • 删除节点
          • • 实现方式一：
            • 实现方式二：
            • 删除节点并建立新链表
            • 逆置链表
            • • 实现：
              • 链表排序

                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;
                }
                

                链表排序