C语言数据结构实现-单链表表基本操作

链表插入元素

同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：
插入到链表的头部（头节点之后），作为首元节点；
插入到链表中间的某个位置；
插入到链表的最末端，作为链表中最后一个数据元素；

虽然新元素的插入位置不固定，但是链表插入元素的思想是固定的，只需做以下两步操作，即可将新元素插入到指定的位置：
将新结点的 next 指针指向插入位置后的结点；
将插入位置前结点的 next 指针指向插入结点；

例如，我们在链表 {1,2,3,4} 的基础上分别实现在头部、中间部位、尾部插入新元素 5，其实现过程如图 1 所示：

从图中可以看出，虽然新元素的插入位置不同，但实现插入操作的方法是一致的，都是先执行步骤 1 ，再执行步骤 2。
注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤 1。

链表删除元素

从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再利用的存储空间要及时释放。因此，从链表中删除数据元素需要进行以下 2 步操作：
将结点从链表中摘下来;
手动释放掉结点，回收被结点占用的存储空间;

其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点 temp，执行一行程序：

代码的实现思路

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//单链表操作
//思考问题
//1.添加、删除的时候位什么事pos-1 而不是 pos
//2.节点添加的过程怎么操作
typedef struct Node {
    int elem;
    struct Node * pNext;
} node;
//链表初始化
node * initLink(){
    node * p = (node *)malloc(sizeof(node));//头结点
    p->pNext=NULL;
    p->elem=0;
    node * temp = p;//头指针
    for(int i=0;i<=5;i++){
        node * p1 = (node *)malloc(sizeof(node));
        p1->elem = i+1;
        p1->pNext=NULL;
        temp->pNext = p1;
        temp=p1;
    }
    return p;
}
//打印链表
void display(node * pLink){
    node * temp = pLink->pNext;
    while(temp->pNext != NULL){
        printf("%d\n",temp->elem);
        temp = temp->pNext;
    }
}
//添加
void addNode(node * pLink, int pos, int elem){
    int index = 1;
    node * temp = pLink->pNext;
    while(index < pos-1){//思考下位什么要pos-1 而不是 pos
        temp = temp->pNext;
        index++;
    }
    node * p1 = (node *) malloc(sizeof(node));
    p1->elem = elem;
    p1->pNext = temp->pNext;
    temp->pNext = p1;
}
//删除节点
void delNode(node * pLink, int pos){
    node * temp = pLink->pNext;
    int index =1;
    while(index < pos-1){
        temp = temp->pNext;
        index++;
    }
    node * del = temp->pNext;//释放节点
    temp->pNext = temp->pNext->pNext;
    free(del);
}
//查找数据对应位置
int findNode(node * pLink,int elem){
    node * temp = pLink->pNext;
    int index  = 1;
    while(temp->pNext != NULL){
        if(temp->elem == elem){
            break;
        }
        temp = temp->pNext;
        index++;
    }
    return index;
}

void repNode(node * pLink, int pos ,int elem){
    node * temp = pLink->pNext;
    int index =1;
    while(index < pos){
        temp = temp->pNext;
        index++;
    }
    temp->elem = elem;
}

int main(){
    node * pLink = initLink();//初始化
    addNode(pLink,3,100);
    addNode(pLink,4,90);
    //delNode(pLink,3);//删除

    findNode(pLink,100);//找数字
    repNode(pLink,4,40);
    display(pLink);//打印
}