链表的基本操作总和

Julia999

对链表的操作有：增,删,改,查,初始化。这些操作书上都有，似乎也可以完全看得懂，但是真正写起代码来还是一卡一卡的，所以自己再重新敲了一遍，也发现了一点点小规律。

#include<stdio.h>
#include<stdlib.h>
/*定义结构体链表节点：
        该结构体有两个属性，一个是int类型的数据域data，另一个是这个结构体本身类型的指针next；
        最后给这个结构体定义了一个别名Node，一个指针别名pNode；*/

//节点结构体
struct Node
{
        int data;  //数据域
        struct Node* pNext;  //指针域

};

//头指针和尾指针定义
//为什么要写尾指针呢，方便操作（尾添加）
struct Node* pHead = NULL;
struct Node* pEnd = NULL;

//初始化头结点
void initListHead()
{
        //pHead已经是一个全局变量了
    pHead = (struct Node*)malloc(sizeof(struct Node));
        if (NULL == pHead)
        {
                printf("内存不足！");
                exit(0);
        }
        pHead->pNext = NULL;
        pEnd = pHead;
}

//尾添加
void addListEnd(int a)
{
        //创建一个新节点
        struct Node* pTemp = (struct Node*)malloc(sizeof(struct Node));
        if (NULL == pTemp)
        {
                printf("创建节点失败！");
                exit(0);
        }

        //将新节点赋值
        pTemp->data = a;
        pTemp->pNext = NULL;

        //将新节点链接到链表中
        pEnd->pNext = pTemp;
        pEnd = pTemp;
}

//头添加
void addListHead(int a)
{
        //创建新的节点
        struct Node* pTemp = (struct Node*)malloc(sizeof(struct Node));
        if (NULL == pTemp)
        {
                printf("创建节点失败！");
                exit(0);
        }

        //将新节点赋值
        pTemp->data = a;
        pTemp->pNext = NULL;

        //链接  先连后断
        //(先让节点的指针指向头指针的下一个，再让头指针指向新的节点)
        pTemp->pNext = pHead->pNext;
        pHead->pNext = pTemp;
}

//遍历链表
void showList()
{
        //遍历链表要写一个中间指针，方便我们的操作，不能直接将头指针后指，也不能将尾指针前指
        struct Node *p = pHead->pNext;
        while (NULL != p)
        {
                printf("%d ", p->data);
                p = p->pNext;
        }
        printf("\n");
}


//查询指定元素是否存在,若存在则并返回节点地址
struct Node* SelectNode(int index)
{
        //遍历整个链表
        struct Node *p = pHead->pNext;
        while (NULL != p)
        {
                if (index == p->data)
                {
                        return p;
                }
                p = p->pNext;
        }
        return NULL;
}

//在任意位置插入元素
//在任意位置添加结点的时候需要注意的是：要判断这个链表是不是空链表，还要判断能不能找到这个位置
void addListRand(int index,int a)
{
        //判断这个链表是不是空链表
        if (pHead->pNext == NULL)
        {
                printf("此链表为空表！");
        }

        //进行插入
        //找到插入位置所在的地方（可以在外面再写一个函数，专门找到下标位置)
        struct Node *pTemp=SelectNode(index);

        if (NULL == pTemp)
        {
                //说明没有找到
                printf("找不到该节点");
                return;
        }
        else
        {
                //创建一个新的节点
                struct Node* pNode = (struct Node*)malloc(sizeof(struct Node));
                pNode->data = a;
                //链接(如果我当前要插入的地方刚好是尾巴）
                if (pTemp == pEnd)
                {
                        //尾插入
                        addListEnd(a);
                }
                else
                {
                        pNode->pNext = pTemp->pNext;
                        pTemp->pNext = pNode;
                }
        }
}

//改
void changeList(int index,int a)
{
        //遍历链表
        struct Node*p = (struct Node*)malloc(sizeof(struct Node));
        p = pHead->pNext;
        while (NULL != p)
        {
                if (index == p->data)
                {
                        p->data = a;
                }
                p = p->pNext;
        }
}

//删除
//删除头
void deleteHead()
{
        //步骤：1先定义一个变量去记住要删掉的节点
        //2.将头结点指向要删除的下一个节点
        //3.将记住的节点释放掉

        //如果链表为空表，那么就没有必要删除了
        if (pHead->pNext == NULL)
        {
                printf("此链表为空表！");
        }
        //删除 记住
        struct Node*pTemp = pHead->pNext;
        pHead->pNext = pHead->pNext->pNext;
        //释放
        free(pTemp);
}

//删除尾
void deleteEnd()
{
        //如果链表为空表，那么就没有必要删除了
        if (pHead->pNext == NULL)
        {
                printf("此链表为空表！");
                return;
        }
        //只有一个节点
        if (pHead->pNext = pEnd)
        {
                free(pEnd);
                pHead->pNext = NULL;
                pHead = pEnd;
        }
        else 
        {
                //不止一个节点
        //找到尾节点的上一个节点
                struct Node*p = pHead->pNext;

                while (NULL != p)
                {
                        if (p->pNext = pEnd)
                        {
                                break;
                        }
                        p = p->pNext;
                }
                //这个时候p就是尾节点的上一个节点
                //删除
                free(pEnd);
                //变新的尾节点
                p = pEnd;
                pEnd = NULL;
        }
        
}

//删除任意(删除元素为a的节点）
void deleteRand(int a)
{
        //判断这个链表是否为空
        if (pHead->pNext == NULL)
        {
                printf("此链表为空表！");
                return;
        }
        //链表不为空,遍历找到要删除的那个节点的上一个节点
        struct Node*p = pHead->pNext;

        while (NULL != p)
        {
                if (p->pNext->data==a)
                {
                        break;
                }
                p = p->pNext;
        }
        //这个时候p就是要删除的那一个节点的上一个节点了
        //如果p这个时候已经是尾节点了
        if (p->pNext == pEnd)
        {
                deleteEnd();
        }
        else
        {
                //先记住要删除的节点
                struct Node* pTemp = p->pNext;
                p->pNext = p->pNext->pNext;
                free(pTemp);
        }
}

//释放整个链表
void freeList()
{
        //遍历整个链表（注意，删除的时候需要先记住要删除的节点）
        struct Node* pTemp = pHead;
        while (pTemp != NULL)
        {
                struct Node* pT = pTemp;
                pTemp = pTemp->pNext;
                free(pT);
        }
        pHead = NULL;
        pEnd = NULL;
}

int main(void)
{
        //在main函数中一定要对头节点进行初始化！！！！
        //链表空头
        //但是在后面的代码中，我们发现头结点的初始化是经常要写的，所以我们为了方便还是写一个函数专门初始化头结点
        /*struct Node* pHead = (struct Node*)malloc(sizeof(struct Node));
        pHead->pNext = NULL;
        pEnd = pHead;*/
        initListHead();

        //操作
        addListEnd(1);
        addListEnd(2);
        addListEnd(3);
        addListEnd(4);

        addListRand(2, 6);

        changeList(3, 5);
        //deleteHead();

        //deleteEnd();

        showList();

        deleteRand(5);

        showList();

        printf("删除整个链表\n");
        freeList();
        showList();

        system("pause");
        return 0;
}

要想真正搞清楚，不会混乱，其实也没有那么难，将大的化小，有时候就清楚明了了。
在上面代码中，定义了头指针和尾指针，那为什么要定义两个指针呢？只定义一个指针不行吗？其实定义两个指针也是为了后面的方便，能够更好的理解。


初始化：在main函数中，一般都是要写对头结点的初始化的。


增：向链表中添加元素...emmm，咋填？
      分解来看，有三种向链表中增加元素的方法：1.头插入 2.尾插入 3.给定位置插入
      注意了：不管是什么方式插入，都有一样的操作：step 1：创建一个新的节点用来存需要插入的数据   step 2：将数据放进新创建的节点中  step 3：链接到链表上去
      特别的，在任意给定位置插入新节点的时候，需要注意能不能找到这个位置。


删：删除要记住了：
      //步骤：1先定义一个变量去记住要删掉的节点
       //2.将头结点指向要删除的下一个节点
       //3.将记住的节点释放掉同样的 ，删除也可以分成三个方法来删除：1.删头  2.删尾  3.任意删
这三种删除方式都有一个必须要判断的是：这个链表是不是空链表（如果是链表，那删除个啥？？？）
删头：删头的方式很简单，记住之后之间将头指针指向被删节点的下一个节点，然后释放记住的节点。
删尾：删尾相比较于删头复杂了一点点，但是也是很好理解的：要分成只有一个节点的情况和有多个结点的情况。
特别的，有多个结点的情况的删除，要找到尾节点的上一个节点（只有找到了尾节点的上一个节点，才能重定义尾指针）
任意删：任意删除给定位置的节点的时候，同样需要注意这个链表是不是空链表，并且需要判断能不能找到这个要删除的节点，如果找到了，再进行删除。


改：改的操作就很简单了，遍历整一个链表，如果找到了需要修改的位置，直接将该节点的数据域改成需要修改的值就可以了（需要注意的是，要写出找不到需修改节点的情况）


查：与改类似，略


删除整个链表：删除整个链表的时候，需要定义一个新的节点来记住要删除的节点，然后不断的后移，释放。


emmm，总之，还是要自己亲自动手操作才能完全掌握和理解滴~~