c 語言 單鏈表的操作 易考點

c 語言 單鏈表的操作 易考點

//頭文件
#ifndef __LINKLIST_H__
 
#define __LINKLIST_H__
typedef int DataType;
 
typedef struct LinkList
{
    DataType _data;
    struct LinkList* _next;
}LinkList,*pLinkList;
 
void InitLinkList(pLinkList& pHead);
void PrintLinkList(pLinkList pHead);
int  GetListLength(pLinkList pHead);
void DestroyList(pLinkList& pHead);
void PushBack(pLinkList& pHead,DataType Data);
void PopBack(pLinkList& pHead);
void PushFront(pLinkList& pHead, DataType Data);
void BuyNode(pLinkList& pHead,DataType Data);
pLinkList Find(pLinkList pHead,DataType Data);
void Insert(pLinkList pos, DataType Data);
void Remove(pLinkList& pHead, DataType Data);
void RemoveAll(pLinkList& pHead, DataType Data);
void Erase(pLinkList& pHead, pLinkList pos);
void BubbleSort( pLinkList pHead);
int JosephusCircle(pLinkList pHead, int num);
void QuickSort(pLinkList pHead,pLinkList pEnd);
void ReverseList(pLinkList& pHead);
pLinkList IfCircleList(pLinkList pHead);
 
pLinkList CircleListEntrance(pLinkList pHead);
 
 
#endif
 
//函數文件
#include<stdio.h>
#include"linklist.h"
#include<malloc.h>
#include<assert.h>
 
//初始化節點
void InitLinkList(pLinkList& pNode)
{
    assert(pNode);
    pNode->_next = NULL;
    pNode->_data = 0;
 
}
//遍歷輸出鏈表數據域
void PrintLinkList(pLinkList pHead)
{
    pLinkList tmp = pHead;
    if (pHead == NULL)
    {
        printf("鏈表為空！\n");
    }
    while (tmp)
    {
        printf("%d ", tmp->_data);
        tmp = tmp->_next;
    }
    printf("\n");
}
//求長度
int  GetListLength(pLinkList pHead)
{
    int length = 0;
     
    while (pHead)
    {
        pHead = pHead->_next;
        ++length;
    }
    return length;
 
}
//銷毀鏈表
void DestroyList(pLinkList& pHead)
{
    pLinkList del = pHead;
    if (pHead == NULL)
    {
        printf("鏈表為空！\n");
    }
    while (pHead)
    {
        del = pHead->_next;
        if (pHead->_next==NULL)
        {
            free(pHead);
            pHead =NULL;
            return;
        }
        pHead->_next = pHead->_next->_next;
        free(del);
    }
}
//尾插
void PushBack(pLinkList& pHead,DataType Data)
{
    pLinkList tmp = pHead;
    if (pHead == NULL)
    {
        BuyNode(pHead, Data);
 
    }
    else
    {
        while (tmp->_next)
        {
            tmp = tmp->_next;
        }
        BuyNode(tmp->_next, Data);
    }
     
}
 
//尾刪
void PopBack(pLinkList& pHead)
{
    pLinkList tmp = pHead;
    if (tmp == NULL)
    {
        printf("鏈表已空！\n");
        return;
    }
    if (pHead->_next == NULL)
    {
        free(pHead);
        pHead = NULL;
        return;
    }
    while (tmp->_next->_next!=NULL)
    {
        tmp = tmp->_next;
    }
    free(tmp->_next);
    tmp->_next = NULL;
}
//頭插
void PushFront(pLinkList& pHead, DataType Data)
{
    pLinkList tmp;
    BuyNode(tmp,Data);
    tmp->_next = pHead;
    pHead = tmp;
}
//創建節點
void BuyNode(pLinkList& pNode, DataType Data)
{
    pNode = (pLinkList)malloc(sizeof(LinkList));
    pNode->_data = Data;
    pNode->_next = NULL;
}
//查找
pLinkList Find(pLinkList pHead,DataType Data)
{
    pLinkList tmp = pHead;
    assert(pHead);
    while (tmp)
    {
        if (tmp->_data == Data)
            return tmp;
        tmp = tmp->_next;
         
    }
    return NULL;
}
//中 後插
void Insert(pLinkList pos, DataType Data)
{
    assert(pos);
    pLinkList tmp = pos->_next;
    BuyNode(pos->_next, Data);
    pos->_next->_next = tmp;
}
//刪除給定數據節點
void Remove(pLinkList& pHead, DataType Data)
{
    pLinkList del = Find(pHead, Data);
    pLinkList tmp = pHead;
    if (pHead == NULL)
    {
        printf("鏈表為空！\n");
        return;
    }
    if (pHead == del)
    {
        pHead = pHead->_next;
        free(tmp);
        return;
    }
    while (tmp->_next )
    {
        if (tmp->_next == del)
        {
            tmp->_next = tmp->_next->_next;
            free(del);
            return;
        }
        tmp = tmp->_next;
    }
}
 
//刪除所有給定數據節點
void RemoveAll(pLinkList &pHead, DataType Data)
{
    pLinkList del = Find(pHead, Data);
    pLinkList tmp = pHead;
    if (pHead == NULL)
    {
        printf("鏈表為空！\n");
        return;
    }
     
    while (tmp->_next&&del!=NULL)
    {
        del = Find(pHead, Data);
        if (pHead == del)
        {
            pHead = pHead->_next;
            free(tmp);
            tmp = pHead;
        }
         
        else if (tmp->_next== del)
        {
            tmp->_next = tmp->_next->_next;
            free(del);
        }
        else
            tmp = tmp->_next;
    }
}
 
//刪除位置節點
void Erase(pLinkList& pHead, pLinkList pos)
{
    pLinkList tmp = pHead;
    assert(pHead);
    assert(pos);
    if (pHead == pos)
    {
        pHead = pHead->_next;
        return;
    }
    while (tmp)
    {
        if (tmp->_next == pos)
        {
            tmp->_next = tmp->_next->_next;
            free(pos);
            break;
        }
        tmp = tmp->_next;
    }
 
}
//冒泡排序 升序
void BubbleSort(pLinkList pHead)
{
    pLinkList tmp = pHead,index=pHead;
    int count = 0;
    assert(pHead);
    while (index)
    {
        tmp = pHead;
        while (tmp->_next)
        {
            if ((tmp->_data) > (tmp->_next->_data))
            {
                DataType change = tmp->_data;
                tmp->_data = tmp->_next->_data;
                tmp->_next->_data = change;
                ++count;
            }
            tmp = tmp->_next;
        }
        if (count <= 1)
            return;
        else
        {
            tmp = pHead;
            index = index->_next;
        }
    }
}
//約瑟夫環 假設鏈表為環 num=3
int JosephusCircle(pLinkList pHead, int num)
{
    pLinkList tmp = pHead;
    assert(pHead);
    while (tmp->_next!=tmp)
    {
        pLinkList del = NULL;
        tmp = tmp->_next->_next;
        tmp->_data = tmp->_next->_data;
        del = tmp->_next;
        tmp->_next = tmp->_next->_next;
        free(del);
    }
    return tmp->_data;
}
//快排
void QuickSort(pLinkList pHead, pLinkList pEnd)
{
    pLinkList cur ;
    pLinkList prev = pHead;
    pLinkList key = pHead;
    DataType tmp = 0;
     
    if (pHead==NULL||pHead->_next==NULL)
    {
        return;
    }
    cur = pHead->_next;
    if (pEnd == pHead->_next||pEnd==pHead)
    {
        return;
    }
    while (cur!=pEnd)
    {
        if (cur->_data < key->_data)
        {
            prev = prev->_next;
            if (cur != prev)
            {
                DataType tmp = cur->_data;
                cur->_data = prev->_data;
                prev->_data = tmp;
            }      
        }
        cur = cur->_next;
    }
    tmp = prev->_data;
    prev->_data = key->_data;
    key->_data = tmp;
     
    QuickSort(pHead, prev);
    QuickSort(prev->_next, pEnd);
 
}
//逆置
void ReverseList(pLinkList& pHead)
{
    pLinkList NewHead = NULL;
    pLinkList tmp =NULL;
    if (!pHead || !pHead->_next)
        return;
    while (pHead)
    {
        NewHead = pHead->_next;
        pHead->_next =tmp;
        tmp = pHead; 
        pHead = NewHead;
    }
    pHead = tmp;
     
}
//判斷單鏈表是否帶環
pLinkList IfCircleList(pLinkList pHead)
{
    pLinkList fast = pHead;
    pLinkList slow = pHead;
    assert(pHead);
    while (fast&&fast->_next)
    {
        fast = fast->_next->_next;
        slow = slow->_next;
        if (fast == slow)
        {
            return fast;
        }
 
    }
    return NULL;
}
//判斷環的入口點
pLinkList CircleListEntrance(pLinkList pHead)
{
    pLinkList head = pHead;
    pLinkList tmp = IfCircleList(pHead);
    if (pHead==NULL&&tmp==NULL)
    {
        return NULL;
    }
    while (tmp != head)
    {
        tmp = tmp->_next;
        head = head->_next;
    }
    return tmp;
}