C教程——链表

创建一个链表：

定义

使用链表存储的数据元素，物理储存位置是随机的根本

为了体现出数据之间的逻辑关系，链表为每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。

链式存储结构 —— 数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构

链表的节点

链表的单元是节点

typedef struct Link{

    char elem; //代表数据域

    struct Link * next; //代表指针域，指向直接后继元素

}link; //link为节点名，每个节点都是一个 link 结构体

因为指针域的指针指向的是【节点】 因此要声明为struct Link*,表明指向类型是整个节点

头节点，头指针和首元节点

一个完整的链表需要由以下几部分构成：

1. 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
2. 节点：链表中的节点又细分为头节点、首元节点和其他节点：

• 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
• 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
• 其他节点：链表中其他的节点；

有头结点，H指向头结点，没有头结点，H指向NULL

创建链表

link * initLink() {

    int i;

    link * p = NULL;//创建头指针

    link * temp = (link*)malloc(sizeof(link));//创建首元节点

    //首元节点先初始化

    temp->elem = 1;

    temp->next = NULL;

    p = temp;//头指针指向首元节点

    //从第二个节点开始创建

    for (i = 2; i < 5; i++) {

        //创建一个新节点并初始化

        link *a = (link*)malloc(sizeof(link));

        a->elem = i;

        a->next = NULL;

        //将temp节点与新建立的a节点建立逻辑关系

        temp->next = a;

        //指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对

        temp = temp->next;

    }

    //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表

    return p;

含有头结点

link * initLink(){

    int i;

    link * p=(link*)malloc(sizeof(link));//创建一个头结点

    link * temp=p;//声明一个指针指向头结点，

    //生成链表

    for (i=1; i<5; i++) {

        link *a=(link*)malloc(sizeof(link));

        a->elem=i;

        a->next=NULL;

        temp->next=a;

        temp=temp->next;

    }

    return p;

}

使用例

#include <stdio.h>

#include <stdlib.h>

//链表中节点的结构

typedef struct Link {

    int  elem;

    struct Link *next;

}link;

//初始化链表的函数

link * initLink();

//用于输出链表的函数

void display(link *p);

int main() {

    link*p = NULL;

    //初始化链表（1，2，3，4）

    printf("初始化链表为：\n");

    p = initLink();

    display(p);

    return 0;

}

link * initLink() {

    int i;

    link * p = NULL;//创建头指针

    link * temp = (link*)malloc(sizeof(link));//创建首元节点

    //首元节点先初始化

    temp->elem = 1;

    temp->next = NULL;

    p = temp;//头指针指向首元节点

    for (i = 2; i < 5; i++) {

        link *a = (link*)malloc(sizeof(link));

        a->elem = i;

        a->next = NULL;

        temp->next = a;

        temp = temp->next;

    }

    return p;

}

void display(link *p) {

    link* temp = p;//将temp指针重新指向头结点

    //只要temp指针指向的结点的next不是Null，就执行输出语句。

    while (temp) //如果带有头结点创建链表，那么这里要换成(temp->next)

    {

        printf("%d ", temp->elem);

        temp = temp->next;

    }

    printf("\n");

}

链表的增加、删除、查找、修改

链表插入元素

同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：

• 插入到链表的头部（头节点之后），作为首元节点；
• 插入到链表中间的某个位置；
• 插入到链表的最末端，作为链表中最后一个数据元素；

插入一个链表

1.将新节点的next指针 指向插入位置之后的节点

2.将插入位置前的节点next指针指向插入节点

注意：顺序不可以颠倒，如果先执行了步骤2，会失去插入位置以后的链表

//p为原链表，elem表示新数据元素，add表示新元素要插入的位置

link * insertElem(link * p, int elem, int add) {

    link * temp = p;//创建临时结点temp

    link * c = NULL;

    int i = 0;

    //首先找到要插入位置的上一个结点

    for (i = 1; i < add; i++) {

        if (temp == NULL) {

            printf("插入位置无效\n");

            return p;

        }

        temp = temp->next;

    }

    //创建插入结点c

    c = (link*)malloc(sizeof(link));

    c->elem = elem;

    //向链表中插入结点

    c->next = temp->next;

    temp->next = c;

    return  p;

}

从链表中删除元素

1.摘掉节点

temp->next=temp->next->next;

2.释放内存

使用free函数，在摘掉节点之前先设置一个指针保留，再删除

//p为原链表，add为要删除元素的值

link * delElem(link * p, int add) {

    link * temp = p;

    link * del = NULL;

    int i = 0;

    //temp指向被删除结点的上一个结点

    for (i = 1; i < add; i++) {

        temp = temp->next;

    }

    del = temp->next;//单独设置一个指针指向被删除结点，以防丢失

    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域

    free(del);//手动释放该结点，防止内存泄漏

    return p;

}

从链表中查找元素

遍历法

从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL（比对失败的标志）。

//p为原链表，elem表示被查找元素、

int selectElem(link * p, int elem) {

    //新建一个指针t，初始化为头指针 p

    link * t = p;

    int i = 1;

    //由于头节点的存在，因此while中的判断为t->next

    while (t->next) {

        t = t->next;

        if (t->elem == elem) {

            return i;

        }

        i++;

    }

    //程序执行至此处，表示查找失败

    return -1;

}

（待补充）

从链表中添加元素

查找之后直接修改即可

//更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值

link *amendElem(link * p, int add, int newElem) {

    int i = 0;

    link * temp = p;

    temp = temp->next;//在遍历之前，temp指向首元结点

    //遍历到被删除结点

    for (i = 1; i < add; i++) {

        temp = temp->next;

    }

    temp->elem = newElem;

    return p;

}

增删查改

#include <stdio.h>

#include <stdlib.h>

typedef struct Link {

    int  elem;

    struct Link *next;

}link;

link * initLink();

//链表插入的函数，p是链表，elem是插入的结点的数据域，add是插入的位置

link * insertElem(link * p, int elem, int add);

//删除结点的函数，p代表操作链表，add代表删除节点的位置

link * delElem(link * p, int add);

//查找结点的函数，elem为目标结点的数据域的值

int selectElem(link * p, int elem);

//更新结点的函数，newElem为新的数据域的值

link *amendElem(link * p, int add, int newElem);

void display(link *p);

int main() {

    link *p = NULL;

    int address;

    //初始化链表（1，2，3，4）

    printf("初始化链表为：\n");

    p = initLink();

    display(p);

    printf("在第4的位置插入元素5：\n");

    p = insertElem(p, 5, 4);

    display(p);

    printf("删除元素3:\n");

    p = delElem(p, 3);

    display(p);

    printf("查找元素2的位置为：\n");

    address = selectElem(p, 2);

    if (address == -1) {

        printf("没有该元素");

    }

    else {

        printf("元素2的位置为：%d\n", address);

    }

    printf("更改第3的位置上的数据为7:\n");

    p = amendElem(p, 3, 7);

    display(p);

    return 0;

}

link * initLink() {

    link * p = (link*)malloc(sizeof(link));//创建一个头结点

    link * temp = p;//声明一个指针指向头结点，用于遍历链表

    int i = 0;

    //生成链表

    for (i = 1; i < 5; i++) {

        link *a = (link*)malloc(sizeof(link));

        a->elem = i;

        a->next = NULL;

        temp->next = a;

        temp = temp->next;

    }

    return p;

}

link * insertElem(link * p, int elem, int add) {

    link * temp = p;//创建临时结点temp

    link * c = NULL;

    int i = 0;

    //首先找到要插入位置的上一个结点

    for (i = 1; i < add; i++) {

        if (temp == NULL) {

            printf("插入位置无效\n");

            return p;

        }

        temp = temp->next;

    }

    //创建插入结点c

    c = (link*)malloc(sizeof(link));

    c->elem = elem;

    //向链表中插入结点

    c->next = temp->next;

    temp->next = c;

    return  p;

}

link * delElem(link * p, int add) {

    link * temp = p;

    link * del = NULL;

    int i = 0;

    //遍历到被删除结点的上一个结点

    for (i = 1; i < add; i++) {

        temp = temp->next;

    }

    del = temp->next;//单独设置一个指针指向被删除结点，以防丢失

    temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域

    free(del);//手动释放该结点，防止内存泄漏

    return p;

}

int selectElem(link * p, int elem) {

    link * t = p;

    int i = 1;

    while (t->next) {

        t = t->next;

        if (t->elem == elem) {

            return i;

        }

        i++;

    }

    return -1;

}

link *amendElem(link * p, int add, int newElem) {

    int i = 0;

    link * temp = p;

    temp = temp->next;//tamp指向首元结点

    //temp指向被删除结点

    for (i = 1; i < add; i++) {

        temp = temp->next;

    }

    temp->elem = newElem;

    return p;

}

void display(link *p) {

    link* temp = p;//将temp指针重新指向头结点

    //只要temp指针指向的结点的next不是Null，就执行输出语句。

    while (temp->next) {

        temp = temp->next;

        printf("%d ", temp->elem);

    }

    printf("\n");

}

翻转链表

struct ListNode *reverse( struct ListNode *head )

{

  struct ListNode *p=NULL,*q=NULL;

  while(head!=NULL)

  {

    p=(struct ListNode *)malloc(sizeof(struct ListNode));

    p->data=head->data;

    p->next=q;

    q=p;

    head=head->next;

  }

  return p;

}

原来链表进行遍历，每次把head的数据放在p中，并更新p；