文章目录

  • 前言
      • 1.1 线性表链式存储结构定义
        • 头指针与头结点的异同
      • 1.2 线性表链式存储结构代码描述
        • 1.2.1 定义结点结构体
        • 1.2.2 链表的创建
        • 1.2.3 链表的遍历
        • 1.2.4 链表的释放
        • 1.2.5 链表结点的查找
        • 1.2.6 链表结点的删除
        • 1.2.7 链表中插入一个节点
        • 1.2.8 链表排序
        • 1.2.9 链表逆序
  • 总结

前言

前面提到的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢？

我们反正也是要让相邻元素间留有足够余地，那干脆所有的元素都不要考虑相邻位置了，哪有空位就到哪里，而只是让每个元素知道他下一个元素的位置在哪里，这样，我们可以在第一个元素时，就知道第二个元素的位置(内存地址)，而找到他；在第二个元素时，再找到第三个元素的位置（内存地址）。这样所有的元素我们就都可以通过遍历而找到。

1.1 线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置

以前在顺序结构中，每个元素只需要存储数据元素信息就可以了。现在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。

因此，为了表示每个元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继元素的存储位置）。

我们把存储元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。

这两部分信息组成数据元素ai的存储映像，称为结点(Node)。

n个结点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,a3,…,an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。

之后的每一个结点，其实就是上一个结点的后继指针指向的位置。

那么最后一个结点，当然就意味着直接后继不存在。

所以规定，线性表的最后一个结点指针为“空”（通常用NULL或==”^”==符号表示，如下图所示）。

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点

头结点的数据域可以不存储任何信息。（也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如下图所示）

头指针与头结点的异同

头指针

  • 头指针是链表指向第一个节点的指针，若链表有头结点，则是指向头结点的指针
  • 头指针具有标志作用，所以常用头指针冠以链表的名字
  • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点

  • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可以存放链表的长度）
  • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他节点的操作就统一了
  • 头结点不一定是链表必须要素

1.2 线性表链式存储结构代码描述

1.2.1 定义结点结构体

//定义结点结构体typedef struct student{//数据域int num;//学号int score;//分数char name[20];//姓名//指针域struct student* next;}STU;

从这个定义中我们也就知道，结点由：存放数据元素的数据域和存放后继结点地址的指针域组成

假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向第i+1个元素，即指向ai+1的指针。也就是说，如果p->data等于ai，那么p->next->data等于ai+1，如下图所示。

1.2.2 链表的创建

第一步：创建一个结点

第二步：创建第二个结点，将其放在第一个结点的后面（第一个结点的指针域保存新结点的地址，以此类推）

第三步：再次创建结点，通过遍历找到最后一个结点，接着将最后一个结点的指针域保存新节点的地址，以此类推

代码实现

//链表创建void link_creat_head(STU** p_head, STU* p_new){STU* p_mov = *p_head;if (*p_head == NULL)//当第一次加入链表为空时,head执行p_new{*p_head = p_new;p_new->next = NULL;}else //第二次及以后加入链表{while (p_mov->next != NULL){p_mov = p_mov->next;//找到原有链表的最后一个节点}p_mov->next = p_new;//将新申请的节点加入链表p_new->next = NULL;}}

1.2.3 链表的遍历

第一步：输出第一个结点的数据域，输出完毕后，让指针保存后一个结点的地址

第二步：以此类推，知道结点的指针域为NULL

代码实现

//链表的遍历void link_print(STU* head){STU* p_mov;//定义新的指针保存链表的首地址,防止使用head改变原本链表p_mov = head;//当指针保存最后一个节点的指针域为NULL时,循环结束while (p_mov != NULL){//先打印当前指针保存节点的指针域printf("num=%d score=%d name:%s\n", p_mov->num, p_mov->score, p_mov->name);//指针后移,保存下一个结点的地址p_mov = p_mov->next;}printf("\n");}

1.2.4 链表的释放

重新定义一个指针q，保存p指向结点的地址，然后p后移保存下一个结点的地址，然后释放q对应的结点，以此类推，知道p为NULL为止

代码实现

//链表的释放void link_free(STU** p_head){//定义一个指针变量STU* pb;while (*p_head != NULL){//先保存p_head指向的结点的地址pb = *p_head;//p_head保存下一个结点地址*p_head = (*p_head)->next;//释放结点并防止野指针free(pb);pb = NULL;}}

1.2.5 链表结点的查找

先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下一个结点，如果到达最后一个结点的时候都没有匹配的数，说明要查找数据不存在

//链表的查找//按照学号查找STU* link_search_num(STU* head, int num){STU* p_mov;//定义的指针变量保存第一个结点的地址p_mov = head;//当没有到达最后一个结点的指针域时循环继续while (p_mov != NULL){//如果找到是当前节点的数据,则返回当前节点的地址if (p_mov->num == num)//找到了{return p_mov;}//如果没有找到,则继续对比下一个结点的指针域p_mov = p_mov->next;}//当循环结束的时候还没有找到,说明查找的数据不存在,返回NULL进行标识return NULL;}//按照姓名查找STU* link_search_name(STU* head, char* name){STU* p_mov;p_mov = head;while (p_mov != NULL){if (strcmp(p_mov->name, name) == 0)//找到了{return p_mov;}p_mov = p_mov->next;}return NULL;//没有找到}

1.2.6 链表结点的删除

如果链表为空，不需要删除。

如果删除的是第一个结点，则需要将保存链表首地址的指针保存第一个结点的下一个结点的地址。

如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结点的后一个结点的地址即可

//链表节点的删除void link_delete_num(STU** p_head, int num){STU* pb, * pf;pb = *p_head;pf = *p_head;if (*p_head == NULL)//链表为空,不用删{printf("链表为空,没有您要删的结点\n");return;}while (pb->num != num && pb->next != NULL){pf = pb;pb = pb->next;}if (pb->num == num)//找到了一个节点的num和num相同{if (pb == *p_head)//要删除的结点是头结点{//让保存头结点的指针保存后一个节点的地址*p_head = pb->next;}else{//前一个结点的指针域保存要删除的后一个节点的地址pf->next = pb->next;}//释放空间free(pb);pb = NULL;}else//没有找到{printf("没有找到您要删除的结点\n");}}

1.2.7 链表中插入一个节点

链表中插入一个结点，按照原本链表的顺序插入，找到合适的位置

情况（按照从小到大）：

  • 如果链表没有结点，则新插入的就是第一个结点

  • 如果新插入的结点的数值最小，则作为头结点

  • 如果新插入的结点的数值在中间位置，则找到前一个，然后插入到他们中间

  • 如果新插入的结点的数值最大，则插入到最后

代码实现

//链表的插入:按照学号的顺序插入void link_insert_num(STU** p_head, STU* p_new){STU* pb, * pf;pb = pf = *p_head;if (*p_head == NULL)//链表为空链表{*p_head = p_new;p_new->next = NULL;return;}while ((p_new->num >= pb->num) && (pb->next != NULL)){pf = pb;pb = pb->next;}if (p_new->num < pb->num)//找到一个节点的num比新来的结点num大,插在pb的前面{if (pb == *p_head){p_new->next = *p_head;*p_head = p_new;}else{pf->next = p_new;p_new->next = pb;}}else//没有找到pb的num比p_new->num大的结点,插在最后{pb->next = p_new;p_new->next = NULL;}}

1.2.8 链表排序

如果链表为空，不需要排序

如果链表只有一个结点，不需要排序

先将第一个结点与后面所有的结点依次对比数据域，只要有比第一个结点数据域小的，则交换位置 ，交换之后，拿新的第一个结点的数据域与下一个结点再次对比，如果比他小，再次交换，以此类推

第一个结点确定完毕之后，接下来再将第二个结点与后面所有的结点对比，直到最后一个结点也对比完毕为止

代码实现

//链表的排序void link_order(STU* head){STU* pb, * pf, temp;pf = head;if (head == NULL){printf("只有一个结点,不用排序\n");return;}if (head->next == NULL){printf("只有一个节点,不用排序\n");return;}while (pf->next != NULL){pb = pf->next;//pb从基准元素的下个元素开始while (pb != NULL){if (pf->num > pb->num){temp = *pb;*pb = *pf;*pf = temp;temp.next = pb->next;pb->next = pf->next;pf->next = temp.next;}pb = pb->next;}pf = pf->next;}}

1.2.9 链表逆序

第一步：将3结点移动到5结点前面

第二步：将5结点后面的1结点移动到3结点的前面

代码实现

//链表逆序STU* link_reverse(STU* head){STU* pf, * pb, * r;pf = head;pb = pf->next;while (pb != NULL){r = pb->next;pb->next = pf;pf = pb;pb = r;}head->next = NULL;head = pf;return head;}

总结

#include #include #include //定义结点结构体typedef struct student{//数据域int num;//学号int score;//分数char name[20];//姓名//指针域struct student* next;}STU;//链表创建void link_creat_head(STU** p_head, STU* p_new){STU* p_mov = *p_head;if (*p_head == NULL)//当第一次加入链表为空时,head执行p_new{*p_head = p_new;p_new->next = NULL;}else //第二次及以后加入链表{while (p_mov->next != NULL){p_mov = p_mov->next;//找到原有链表的最后一个节点}p_mov->next = p_new;//将新申请的节点加入链表p_new->next = NULL;}}//链表的遍历void link_print(STU* head){STU* p_mov;//定义新的指针保存链表的首地址,防止使用head改变原本链表p_mov = head;//当指针保存最后一个节点的指针域为NULL时,循环结束while (p_mov != NULL){//先打印当前指针保存节点的指针域printf("num=%d score=%d name:%s\n", p_mov->num, p_mov->score, p_mov->name);//指针后移,保存下一个结点的地址p_mov = p_mov->next;}printf("\n");}//链表的释放void link_free(STU** p_head){//定义一个指针变量STU* pb;while (*p_head != NULL){//先保存p_head指向的结点的地址pb = *p_head;//p_head保存下一个结点地址*p_head = (*p_head)->next;//释放结点并防止野指针free(pb);pb = NULL;}}//链表的插入:按照学号的顺序插入void link_insert_num(STU** p_head, STU* p_new){STU* pb, * pf;pb = pf = *p_head;if (*p_head == NULL)//链表为空链表{*p_head = p_new;p_new->next = NULL;return;}while ((p_new->num >= pb->num) && (pb->next != NULL)){pf = pb;pb = pb->next;}if (p_new->num < pb->num)//找到一个节点的num比新来的结点num大,插在pb的前面{if (pb == *p_head){p_new->next = *p_head;*p_head = p_new;}else{pf->next = p_new;p_new->next = pb;}}else//没有找到pb的num比p_new->num大的结点,插在最后{pb->next = p_new;p_new->next = NULL;}}//链表的查找//按照学号查找STU* link_search_num(STU* head, int num){STU* p_mov;//定义的指针变量保存第一个结点的地址p_mov = head;//当没有到达最后一个结点的指针域时循环继续while (p_mov != NULL){//如果找到是当前节点的数据,则返回当前节点的地址if (p_mov->num == num)//找到了{return p_mov;}//如果没有找到,则继续对比下一个结点的指针域p_mov = p_mov->next;}//当循环结束的时候还没有找到,说明查找的数据不存在,返回NULL进行标识return NULL;}//按照姓名查找STU* link_search_name(STU* head, char* name){STU* p_mov;p_mov = head;while (p_mov != NULL){if (strcmp(p_mov->name, name) == 0)//找到了{return p_mov;}p_mov = p_mov->next;}return NULL;//没有找到}//链表节点的删除void link_delete_num(STU** p_head, int num){STU* pb, * pf;pb = *p_head;pf = *p_head;if (*p_head == NULL)//链表为空,不用删{printf("链表为空,没有您要删的结点\n");return;}while (pb->num != num && pb->next != NULL){pf = pb;pb = pb->next;}if (pb->num == num)//找到了一个节点的num和num相同{if (pb == *p_head)//要删除的结点是头结点{//让保存头结点的指针保存后一个节点的地址*p_head = pb->next;}else{//前一个结点的指针域保存要删除的后一个节点的地址pf->next = pb->next;}//释放空间free(pb);pb = NULL;}else//没有找到{printf("没有找到您要删除的结点\n");}}//链表的排序void link_order(STU* head){STU* pb, * pf, temp;pf = head;if (head == NULL){printf("只有一个结点,不用排序\n");return;}if (head->next == NULL){printf("只有一个节点,不用排序\n");return;}while (pf->next != NULL){pb = pf->next;//pb从基准元素的下个元素开始while (pb != NULL){if (pf->num > pb->num){temp = *pb;*pb = *pf;*pf = temp;temp.next = pb->next;pb->next = pf->next;pf->next = temp.next;}pb = pb->next;}pf = pf->next;}}//链表逆序STU* link_reverse(STU* head){STU* pf, * pb, * r;pf = head;pb = pf->next;while (pb != NULL){r = pb->next;pb->next = pf;pf = pb;pb = r;}head->next = NULL;head = pf;return head;}int main(){STU* head = NULL, * p_new = NULL;STU* pb;char name[32] = "";int num, i;int flag;printf("请输入链表初始个数:\n");scanf("%d", &num);for (i = 0; i < num; i++){p_new = (STU*)malloc(sizeof(STU));//申请一个新的节点printf("请输入学号,分数,姓名:\n");//给新节点赋值scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);link_creat_head(&head, p_new);}link_print(head);//查学号do{printf("请输入您要查找学生的学号\n");scanf("%d", &num);pb = link_search_num(head, num);if (pb != NULL){printf("找到了 num=%d score=%d name:%s\n", pb->num, pb->score, pb->name);printf("您是否要继续,退出请按1,重新请按0\n");scanf("%d", &flag);}else{printf("没有查找到您要查找到结点,是否退出" />);scanf("%d", &flag);}} while (flag != 1);//查姓名do{printf("请输入您要查找的学生的姓名:\n");scanf("%s", name);pb = link_search_name(head, name);if (pb != NULL)//找到了{printf("找到了 num=%d score=%d name:%s\n", pb->num, pb->score, pb->name);printf("您是否要继续,退出请按1,重新请按0\n");scanf("%d", &flag);}else{printf("没有查找到您要查找到结点,是否退出?退出请按1,重新请按0\n");scanf("%d", &flag);}} while (flag != 1);printf("请输入您要删除的结点的学号\n");scanf("%d", &num);link_delete_num(&head, num);printf("删除后的链表为:\n");link_print(head);do{printf("请输入您要插入节点的 num score name\n");p_new = (STU*)malloc(sizeof(STU));//申请一个新节点scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);link_insert_num(&head, p_new);link_print(head);printf("您是否要继续,继续请按0,退出请按1\n:");scanf("%d", &flag);} while (flag==0);printf("*********************\n");printf("排列后的顺序是:\n");link_order(head);link_print(head);printf("*********************\n");printf("逆序排列后的顺序是:\n");head = link_reverse(head);link_print(head);link_free(&head);}