速通回忆

如果你之前学过链表，可以直接看我下面的这个项目，实现了下面专题中所有内容；

如果你是个新手，建议先不要看下面这个项目，先好好看一下下面每一个部分的代码思路，并尝试自己去写一下

/* 
 * 功能：单链表操作 
 * 作者：此乃刘同学（www.liustu.com.cn）
 */
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

/* 创建学生信息结构体 */
typedef struct{
    char name[20];      /* 学生姓名 */
    int age;            /* 学生年龄 */
}stu_data;

/* 定义学生的单链表 */
typedef struct Node{
    stu_data data;
    struct Node *next; 
}stu_link,*Link_ponit;

/* 链表初始化 */
Link_ponit Link_Init(){
    Link_ponit link = (Link_ponit)malloc(sizeof(stu_link));        /* 动态分配存储空间 */
    link->next = NULL;          /* 设置链表指针指向空 */
    return link;
}   

/* 
 * 链表创建头插法 
 * 思路：动态分配一个新的空间，存放数据后；把当前链表的next指向stu的next，再修改stu的next指向新链表
 */
void LinkCreateH(Link_ponit p){
    /* 动态分配存储空间 */
    Link_ponit n = (Link_ponit)malloc(sizeof(stu_link));
    Link_ponit stu = p;
    /* 读取信息 */
    printf("（头插法）请输入学生的姓名:");
    scanf("%s",n->data.name);
    printf("（头插法）请输入学生的年龄:");
    scanf("%d",&n->data.age);
    /* 将新节点放在链表头结点的下一个节点 */
    n->next = stu->next;
    stu->next = n;
}

/* 
 * 链表创建尾插法 
 * 思路：动态分配一个新的空间，存放数据后；把传来的链表指针，指向最后一个，把p的next指向最后一个的next最后一个next指向p
 */
void LinkCreateL(Link_ponit n){
    /* 动态分配存储空间 */
    Link_ponit p = (Link_ponit)malloc(sizeof(stu_link));
    Link_ponit stu = n;
    /* 读取信息 */
    printf("（尾插法）请输入学生的姓名:");
    scanf("%s",p->data.name);
    printf("（尾插法）请输入学生的年龄:");
    scanf("%d",&p->data.age);
    /* 将指针指向链表最后一个节点的位置 */
    while(stu->next != NULL) 
        stu = stu->next;
    /* 在链表末尾插入新节点 */
    stu->next = p;
    p->next = NULL;
}

/* 链表遍历输出 */
void LinkList_print(Link_ponit n){
    /* 创建一个新指针，指向链表的头节点 */
    Link_ponit stu = n;
    printf("|   学生姓名    |   学生年龄    |\n");
    /* while循环遍历 */
    while(stu->next != NULL){
        printf("|\t%s\t|\t%d\t|\n",stu->next->data.name,stu->next->data.age);
        stu = stu->next;
    }
}

/* 链表遍历修改某个节点的值 */
void LinkListReplace(Link_ponit n,char *stu_n){
    /* 创建一个新指针，指向链表的头节点 */
    Link_ponit stu = n;
    /* 编译查找与stu_n字符串相同的链表节点 */
    while(stu->data.name != NULL){
        if(strcmp(stu->data.name,stu_n)==0){
            /* 修改信息 */
            printf("请输入你要修改%s同学的年龄:",stu_n);
            scanf("%d",&(stu->data.age));
            break;
        }
        stu = stu->next;
    }
    /* 遍历到头也没有查到，则返回失败 */
    if(stu == NULL)
        printf("查询无此同学\n");
}

/* 在某个位置插入一个节点 */
void LinkList_Insert(Link_ponit n, int space){
    /* 创建一个新指针，指向链表的头节点 */
    Link_ponit stu = n;
    /* 将指针移动到对应位置 */
    for(int i=0; i<space; i++){
        stu = stu->next;
    }
    /* 如果移动次数太多，则超出链表的范围 */
    if(stu == NULL){
        printf("插入位置超出最大范围！\n");
        return ;
    }
    /* 分配一个节点的动态空间，存储要插入的数据 */
    Link_ponit p = (Link_ponit)malloc(sizeof(stu_link));
    printf("（插入操作）请输入学生的姓名:");
    scanf("%s",p->data.name);
    printf("（插入操作）请输入学生的年龄:");
    scanf("%d",&p->data.age);
    /* 修改链表指向新的节点 */
    p->next = stu->next;
    stu->next = p; 
}

/* 删除一个节点 */
void LinkList_Delete(Link_ponit n, char *stu_n){
    /* 创建一个新指针，指向链表的头节点 */
    Link_ponit stu = n;
    Link_ponit p = (Link_ponit)malloc(sizeof(stu_link));
    /* 遍历查找，查看与stu_n字符串相同的节点 */
    while(stu->next != NULL){
        if(strcmp(stu->next->data.name, stu_n) == 0){
            /* 替换要删除的节点 */
            p = stu->next;
            stu->next = p->next;
            /* 释放要删除的节点空间 */
            free(p);
            printf("删除成功\n");
            return;
        }
        stu = stu->next;
    }
    printf("查询无结果\n");
    free(stu);
}

int main()
{
    Link_ponit stu = Link_Init();       /* 创建一个链表 */
    LinkCreateH(stu);                   /* 用头插法插入一个接单 */
    LinkCreateL(stu);                   /* 用尾插法插入一个接单 */
    LinkList_print(stu);                /* 遍历输出所有节点信息 */
    LinkListReplace(stu, "stu");        /* 替换某个节点的信息 */
    LinkList_print(stu);                /* 遍历输出所有节点信息 */
    LinkList_Insert(stu,2);             /* 在某个位置插入一个节点 */
    LinkList_print(stu);                /* 遍历输出所有节点信息 */
    LinkList_Delete(stu, "demo");       /* 删除某个节点 */
    LinkList_print(stu);                /* 遍历输出所有节点信息 */

    free(stu);                          /* 释放动态分配内存 */
    return 0;
}

链表理论

链表的基本思维是，利用结构体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互联系，串联

插入删除操作也就相当简单，只需要修改指针所指向的区域就可以了，不需要进行大量的数据移动操作

链表解决了数组不方便移动，插入，删除元素的弊端，但相应的，链表付出了更加大的内存牺牲换来的这些功能的实现

单链表设计

单链表的结点定义

//定义结点类型
typedef struct Node {
    int data;       //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
    struct Node *next;          //单链表的指针域
} Node,*LinkedList;  
//Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型

单链表的初始化

LinkedList listinit(){
    Node *L;
    L=(Node*)malloc(sizeof(Node));      //开辟空间 
    if(L==NULL){                     //判断是否开辟空间失败，这一步很有必要
        printf("申请空间失败");
        //exit(0);                  //开辟空间失败可以考虑直接结束程序
    }
    L->next=NULL;       //指针指向空
}

创建单链表（头插入法）

使用头插入法最终得到的结果是逆序的

//单链表的建立1，头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
  
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;     //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;

创建单链表（尾插入法）

希望两者次序一致，可采用尾插法

//单链表的建立2，尾插法建立单链表
  
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;            //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}

遍历单链表

• 遍历打印输出

//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
}

• 便利修改

//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}

链表插入操作

//单链表的插入，在链表的第i个位置插入x的元素
  
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
  
    return L;
}

链表删除操作

//单链表的删除，在链表中删除值为x的元素
  
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}