[数据结构与算法]C语言链表相关操作

代码中的注释详细，可直接运行，粘贴在编译器中研究更好！

创建结点
链表初始化
尾插法插入一个元素
头插法插入一个元素
按照下标插入一个元素
通过下标查询元素
通过下标更改元素
打印链表
通过下标删除元素
逆序输出链表
反转链表

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;                                           //数据域
    struct Node *next;                                  //指针域
}Node,*List;                                            //List代表链表，Node代表一个结点

/*********************************************************************
 *                            方法定义区                              *
 *********************************************************************/
Node* CreateNode(int data);                             //创建结点
List Init();                                            //链表初始化
void InsertByTail(List L,int data);                     //尾插法插入一个元素
void InsertByHead(List L,int data);                     //头插法插入一个元素
void InsertByIndex(List L,int data,int index);          //按照下标插入一个元素
void PrintList(List L);                                 //打印链表
void DeleteNodeByIndex(List L,int index);               //通过下标删除元素
int SelectByIndex(List L,int index);                    //通过下标查询元素
void UpdateByIndex(List L,int data,int index);          //通过下标更改元素
int ListSize(List L);                                   //统计有多少个元素，不包含头结点
Node* FindByIndex(List L,int index);                    //找到下标前的一个元素，返回其地址
List ReversePrintList(List L);                          //逆序输出链表
List ReverseList(List L);                               //反转链表
int main(){
    List L = Init();  //初始化
    int i,index,num;
    //创建一个链表，元素为 1 2 3 4 5 6 7 8 9 10
    for(i=1;i<11;i++){
        InsertByTail(L,i);
        //InsertByHead(L,i);
    }
    printf("原来的链表为：");
    PrintList(L);  //打印

//    //按下标删除
//    printf("请输入要删除第几个元素:\n");
//    scanf("%d",&index);
//    DeleteNodeByIndex(L,index);
//    printf("删除第%d个元素后为：",index);
//    PrintList(L);  //打印
//
//    //按下标插入
//    printf("请输入要插入的下标:\n");
//    scanf("%d",&index);
//    printf("请输入要插入的数据:\n");
//    scanf("%d",&num);
//    InsertByIndex(L,num,index);
//    printf("在第%d个位置插入%d后为：\n",index,num);
//    PrintList(L);  //打印
//
//    //按下标查找
//    printf("请输入要查找的下标:\n");
//    scanf("%d",&index);
//    printf("%d对应的数据为：%d\n",index,SelectByIndex(L,index));
//
//    //按下标更新
//    printf("请输入要更新的下标:\n");
//    scanf("%d",&index);
//    printf("请输入要更新的值:\n");
//    scanf("%d",&num);
//    UpdateByIndex(L,num,index);
//    printf("更新后的数据为：\n");
//    PrintList(L);

    //逆序输出
//    printf("逆序输出后为：\n");
//    ReversePrintList(L->next);

    //逆转链表
    List new = ReverseList(L);
    printf("逆转后为：");
    PrintList(new);
    return 0;
}
void InsertByTail(List L,int data){
    Node *p, *node = CreateNode(data); //创建新结点
    p = L;
    node->data = data;
    node->next = NULL;
    while (p->next) //找到最后一个结点
    {
        // p++; 千万不要写p++啊，害死人不偿命！！！
        p = p -> next;
    }
    p->next = node;
}
Node* CreateNode(int data){     //创建结点
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    return node;
}
List Init(){           //初始化链表
    return CreateNode(0); //头指针
}
void PrintList(List L){
    Node* p = L->next;
    while (p != NULL){
        printf("%d ",p->data);
        p = p -> next;
    }
    printf("\n");
}
void InsertByHead(List L,int data){  //头插法
    Node *node = CreateNode(data);  //创建结点
    node->next = L->next;
    L->next = node;
}
void DeleteNodeByIndex(List L,int index){
    Node *temp;
    Node* p = FindByIndex(L,index); //找到index的前一个结点
    if(index > ListSize(L) || index < 1){  //下标有误
        return ;
    }
    // 删除结点
    temp = p->next;
    p->next = p->next->next;
    free(temp);
}
int ListSize(List L){
    int i = 0;
    Node* p = L->next;
    while (p != NULL){
        i++;
        p = p-> next;
    }
    return i;
}
Node* FindByIndex(List L,int index){
    int i;
    Node* p = L;
    for (i = 1; i < index; i++) { //找到index的前一个结点
        p = p -> next;
    }
    return p;
}
void InsertByIndex(List L,int data,int index){
    Node* p = FindByIndex(L,index);
    //创建结点
    Node* node = CreateNode(data);
    //开始插入
    node->next = p->next;
    p->next = node;
}
int SelectByIndex(List L,int index){
    Node* p = FindByIndex(L,index);
    return p->next->data;
}
void UpdateByIndex(List L,int data,int index){
    Node* p = FindByIndex(L,index);
    p->next->data = data;
}
List ReversePrintList(List L){
    //顺序输出很简单，逆序输出可以用递归
    if(L == NULL) return NULL;
    ReversePrintList(L->next);
    printf("%d ",L->data);
}
List ReverseList(List L){
    List now = Init();  //创建一个链表
    Node* p = L->next;
    while (p!=NULL){ //遍历L链表
        InsertByHead(now,p->data);  //用头插法插入新链表
        p = p->next;
    }
    return now;
}