数据结构（Day19）

🕗 发布于 2024-09-24 07:23 数据结构 算法 c语言 linux 开发语言

一、学习内容

单链表

头删

int front_dele(Plink L)
{
if(L==NULL||L->len==0)
{
printf("头删失败\n");
return -1;
}
Plink Q = L->next;//保留要删除的1号节点
L->next = L->next->next;
L->len--;
free(Q);//释放空间
Q=NULL;
return 0;
}

尾删

int rear_dele(Plink L)
{
if(empty(L))
{
printf("尾删失败\n");
return -1;
}
int i;
Plink t = L;
for(i = 0;i<L->len-1;i++)//将t指向要删除节点的前驱
{
t = t->next;
}
Plink Q = t->next;//保留要删除的节点
t->next = NULL;
L->len--;
free(Q);
Q=NULL;
return 0;
}

按值删除

int value_dele(Plink L,int key)
{
if(empty(L))
{
printf("按值删除失败\n");
return -1;
}
int i,flag=0;
Plink t = L;//指向头节点
for(i = 0;i<L->len;i++)//遍历整个单链表查找该值是否存在
{
if(key==t->next->data)
{
flag=1;
break;//退出循环t指向查找到的节点前驱
}
t  = t->next;
}
if(flag==0)
{
printf("没有该值，删除失败\n");
}
else
{
Plink Q = t->next;//保留要删除的节点
t->next = t->next->next;
free(Q);
Q=NULL;
L->len--;
}
return 0;

按值修改

int value_change(Plink L,int key,int e)
{
if(empty(L))
{
printf("按值修改失败\n");
return -1;
}
int i,flag=0;
Plink t = L;//指向头节点
for(i = 0;i<L->len;i++)//遍历整个单链表查找该值是否存在
{
if(key==t->data)
{
flag=1;
break;//退出循环t指向查找到的节点
}
t  = t->next;
}
if(flag==0)
{
printf("没有该值，修改失败\n");
}
else
{
t->data = e;
}
return 0;
}

按值查找返回地址

Plink value_find(Plink L,int key)
{
int i;
Plink t = L;
for(i = 0;i<L->len;i++)
{
t = t->next;
if(t->data==key)
{
return t;
}
}
return NULL;
}

链表逆置

int link_re(Plink L)
{
Plink Q,t;
Q = L->next;
t = Q->next;
while(t!=NULL)
{
Q->next = t->next;
t->next = L->next;
L->next = t;

t = Q->next;
}
return 0;
}

排序


int popul_sort(Plink L)
{
int temp,i;
Plink j;
for(i = 1;i<L->len;i++)
{
for(j = L->next;j->next!=NULL;j=j->next)
{
if(j->data>j->next->data)
{
temp = j->data;
j->data = j->next->data;
j->next->data = temp;
}
}
}
return 0;
}

去重

int node_dele(Plink L,Plink j)
{
Plink Q = j->next;
j->next = j->next->next;
free(Q);
Q=NULL;
L->len--;
}
int Dedup(Plink L)
{
Plink i,j,Q;
for(i = L->next;i->next!=NULL;i = i->next)
{
for(j = i;j->next!=NULL;)
{
if(i->data==j->next->data)
{
node_dele(L,j);
}
else
{
j = j->next;
}
}
}
}

注意事项：删除重复的节点后，不需要移动 j ，继续将i与 j->next比较。

销毁

int link_destroy(Plink L)
{
if(L==NULL)
{
printf("销毁失败\n");
return -1;
}
Plink t = L;
while(t!=NULL)
{
t = t->next;
free(L);
L = t;
}
printf("销毁成功\n");
}

单向链表的优缺点
1. 优点
  1. 插入删除不需要移动元素，只需要修改指针。
  2. 节点之间不连续，可以充分利用内存碎片存储数据。
  3. 不需要预估存储空间。
  4. 节点个数不受限制。
2. 不足
  1. 修改查找需要循环遍历节点。
  2. 相同长度的线性表，与顺序表相比单链表占用空间较多。
  3. 只能从头往后访问，不能反向访问。

双向链表
- 作用
  - 单向链表只能单向访问链表，而双向链表可以正序或倒序访问查找链表
  - 单向链表不能自我删除，每次都需要找到要删除结点的前一个结点进行删除，引入双向链表可以实现自我删除，找到要删除的结点，让要删除的前驱结点链接到要删除结点的后继结点，然后删除结点即可。
- 结构体类型格式
  - - ```
    typedef struct node
    {
        union{
            int len;
            int data;    
        };
        struct node *pro;//前一个节点地址
        struct node *next;//后一个节点地址
    }Link,*Plink;
```
- 双向链表的相关操作
  - 双向链表的创建
    - ```
    Plink creat_double()
    {
    Plink p = malloc(sizeof(Link));
    if(p==NULL)
    {
    printf("申请失败\n");
    return NULL;
    }
    p->len = 0;
    p->pro = NULL;
    p->next = NULL;
    return p;
    }
```
  - 功能：创建一个双向链表头结点。
  - 参数：void
  - 返回值：申请到的头结点的地址指针
  - 思路：在堆区申请一个头结点的空间大小，对其进行初始化，数据域len为0，指针域为NULL
  - 注意：判断申请到的空间是否合法
- 判空
  - ```
  int empty(Plink L)
  {
  if(L==NULL)
  {
  return 1;
  }
  return 0;
  }
```
    - 功能：判断双向链表是否为空
    - 返回值：真和假，空是 1，不空是0，int
    - 参数：双向链表
    - 思路：为空的条件 1、头结点的指针域为空 2、头结点的指针域为0
    - 注意：判断接收到的双向链表是否合法
  - 头插
    - 1、没有1号节点时新节点p后指针置空新节点前指针指向头节点头节点后指针指向新节点
      2、有1号节点时新节点后指针指向1号节点新节点前指针指向头节点 1号节点前指针指向新节点头节点后指针指向新节点。
      - int front_insert(Plink L,int e) { if(empty(L)) { printf("头插失败\n"); return -1; } Plink p = malloc(sizeof(Link)); p->data = e; if(L->next==NULL)//没有1号节点时 { p->next = NULL; p->pro = L; L->next = p; } else//有1号节点时 { p->next = L->next; p->pro = L; L->next->pro = p; L->next = p; } L->len++; }
        
        功能：在头结点的后面插入一个结点
        
        返回值：成功1 失败0
        
        参数：双向链表、要插入的元素
        
        思路：1、给要插入元素申请结点
        
        2、将要插入的结点插在头结点的后面
        
        3、链表长度+1
        
        注意：判断接收到的双向链表是否合法
  - 尾插法
    - 1、没有1号节点时新节点p后指针置空新节点前指针指向头节点头节点后指针指向新节点
      2、有1号节点时新节点后指针指向空新节点前指针指向 t t的后指针指向新节点p
      - int rear_insert(Plink L,int e) { if(empty(L)) { printf("尾插失败\n"); return -1; } Plink p = malloc(sizeof(Link)); p->data = e; if(L->next==NULL)//没有1号节点时 { p->next = NULL; p->pro = L; L->next = p; } else//有1号节点时 { int i; Plink t =L; for(i = 0;i<L->len;i++)//循环len次指向最后一个节点 { t = t->next; } p->next = NULL; t->next = p; p->pro = t; } L->len++; }
        
        功能：在头结点的后面插入一个结点
        
        返回值：成功1 失败0
        
        参数：双向链表、要插入的元素
        
        思路：1、给要插入元素申请结点
        
        2、将要插入的结点插在头结点的后面
        
        3、链表长度+1
        
        注意：判断接收到的双向链表是否合法
  - 双向链表的遍历
    - ```
    int output_link(Plink L)
    {
    if(empty(L)||L->len==0)
    {
    printf("输出失败\n");
    return -1;
    }
    int i;
    Plink t = L;
    for(i = 0;i<L->len;i++)
    {
    t = t->next;
    printf("%d\t",t->data);
    }
    printf("\n");
    return 0;
    }
```
  - 功能：共头到尾输出双链表【也可以从尾到头输出双链表】
  - 返回值：无
  - 参数：双链表
  - 思路：只要双链表不空，从头结点开始一个接着一个的输出
- 任意位置插入
  - - int anypos_insert(Plink L,int pos,int e) { if(pos<1||pos>L->len+1||empty(L)) { printf("插入失败\n"); return -1; } int i; Plink t = L; for(i = 0;i<pos-1;i++)//循环pos-1次指向待插入节点的前驱 { t =t->next; } Plink p = malloc(sizeof(Link)); p->data = e; p->next = t->next; p->pro = t; t->next->pro = p; t->next = p; L->len++; return 0; }
      
      功能：在双链表长度范围之内的任意位置，插入一个结点
      
      返回值：成功1 失败0 int
      
      参数：双链表、要插入的数据、指定的位置
      
      思路：知道要插入的位置
- 任意位置删除
  - - int anypos_dele(Plink L,int pos) { if(pos<1||pos>L->len||L->len==0||empty(L)) { printf("删除失败\n"); return -1; } int i; Plink Q,t = L; for(i = 0;i<pos-1;i++) { t = t->next; } Q = t->next;//保留要删除的节点 t->next = t->next->next; Q->next->pro = t; free(Q); Q=NULL; L->len--; }
- 链表销毁
  - ```
  int link_destroy(Plink L)
  {
  if(L==NULL)
  {
  printf("销毁失败\n");
  return -1;
  }
  Plink t = L;
  while(t!=NULL)
  {
  t = t->next;
  free(L);
  L = t;
  }
  printf("销毁成功\n");
  }
```
脑图

二、作业

完成单链表操作，要求节点构造类型。

1、建立学生结构体（学号，姓名，成绩）

2、循环调用头插法创建整表

3、遍历单链表

4、任意位置插入一个完整的学生信息

5、任意位置删除一个学生。

6、单链表逆置

7、单链表按照学生成绩排序。

代码解答：

头文件：

#include "stu.h"

int main(int argc, const char *argv[]) {
    Plink L = creat_link();  // 创建链表头节点
    int pos;  // 用于记录插入或删除操作的位置
    student new_student;  // 用于存储插入的学生信息
    int ch;  // 记录用户的选择

    // 无限循环，直到用户选择退出
    while (1) {
        // 打印功能菜单
        printf("\n----------菜单----------\n");
        printf("\t1、输入学生信息（头插法创建链表）\n");
        printf("\t2、任意位置插入一个学生\n");
        printf("\t3、任意位置删除一个学生\n");
        printf("\t4、遍历单链表\n");
        printf("\t5、单链表逆置\n");
        printf("\t6、单链表按照学生成绩排序\n");
        printf("\t0、退出程序\n");
        printf("\n请输入你的选择：");
        scanf("%d", &ch);  // 获取用户的菜单选择

        // 根据用户输入选择对应功能
        switch (ch) {
            case 1:  // 输入学生信息，头插法创建链表
                input_link(L);  // 调用函数通过头插法创建链表
                break;

            case 2:  // 任意位置插入学生信息
                printf("请输入要插入的位置：");
                scanf("%d", &pos);  // 获取用户指定的位置
                printf("请输入学生的学号、姓名、成绩：\n");
                scanf("%d %s %f", &new_student.id, new_student.name, &new_student.score);  // 输入新学生信息
                anypos_insert(L, pos, new_student);  // 调用插入函数在指定位置插入
                break;

            case 3:  // 任意位置删除学生
                printf("请输入要删除的学生位置：");
                scanf("%d", &pos);  // 获取要删除的学生位置
                anypos_dele(L, pos);  // 调用删除函数删除指定位置的学生
                break;

            case 4:  // 遍历链表
                output_lin(L);  // 调用遍历函数输出链表内容
                break;

            case 5:  // 链表逆置
                link_re(L);  // 调用逆置函数对链表进行逆置
                printf("链表逆置成功！\n");
                break;

            case 6:  // 按照学生成绩排序
                bubble_sort(L);  // 调用排序函数对链表进行冒泡排序（根据成绩）
                printf("链表按成绩排序成功！\n");
                break;

            case 0:  // 退出程序
                printf("程序退出！\n");
                return 0;  // 退出程序

            default:  // 输入无效时提示
                printf("输入无效，请重新选择！\n");
                break;
        }
    }

    return 0;
}

函数文件：

#include "stu.h"

// 创建链表的头节点，返回头节点指针
Plink creat_link() {
    Plink p = malloc(sizeof(llink));  // 分配头节点的内存
    if (NULL == p) {
        printf("申请头节点失败\n");  // 内存分配失败时的错误处理
        return NULL;
    }
    p->len = 0;       // 初始化链表长度为0
    p->next = NULL;   // 初始化链表的next指针为NULL
    return p;         // 返回头节点
}

// 通过头插法输入学生信息并创建链表
int input_link(Plink L) {
    if (NULL == L) {
        printf("单链表不存在，创建失败\n");  // 检查链表是否存在
        return -1;
    }

    int n;
    printf("请输入学生个数：");
    scanf("%d", &n);   // 输入学生个数
L->len = n;        // 初始化链表长度

    for (int i = 0; i < n; i++) {
        // 分配新节点的内存
        Plink p = (Plink)malloc(sizeof(llink));
        if (p == NULL) {
            printf("内存分配失败\n");  // 内存分配失败时的处理
            return -1;
        }

        // 输入学生信息
        printf("请输入第 %d 个学生的学号、姓名、成绩：\n", i + 1);
        scanf("%d %s %f", &p->data.id, p->data.name, &p->data.score);

        // 头插法插入新节点
        p->next = L->next;  // 新节点的next指向当前链表的第一个节点
        L->next = p;        // 链表头节点的next指向新节点
L->len += 1;         // 更新链表长度
    }

    return 0;
}

// 遍历链表，输出学生信息
int output_lin(Plink L) {
    if (L == NULL || L->next == NULL) {
        printf("链表为空！\n");  // 如果链表为空则提示
        return -1;
    }

    Plink t = L->next;  // 从第一个有效节点开始遍历
    while (t != NULL) {
        // 输出当前节点的学生信息
        printf("学号：%d\t姓名：%s\t成绩：%.2f\n", t->data.id, t->data.name, t->data.score);
        t = t->next;  // 移动到下一个节点
    }

    return 0;
}

// 在链表中的任意位置插入一个学生信息
int anypos_insert(Plink L, int pos, student new_student) {
    // 检查插入位置是否合法
if (pos < 1 || pos > L->len + 1) {
printf("插入失败\n");
return -1;
}

    // 分配新节点的内存
Plink p = (Plink)malloc(sizeof(llink));
if (NULL == p) {
printf("内存分配失败\n");
return -1;
}
p->data = new_student;  // 将新学生信息赋给新节点

    // 找到插入位置的前一个节点
Plink t = L;
for (int i = 1; i < pos; i++) {
t = t->next;
}

    // 插入新节点
p->next = t->next;  // 新节点的next指向当前节点的next
t->next = p;        // 当前节点的next指向新节点
L->len++;           // 更新链表长度
printf("插入成功\n");
return 0;
}

// 删除链表中任意位置的学生
int anypos_dele(Plink L, int pos) {
    // 检查链表是否为空或删除位置是否合法
if (L == NULL || pos < 1 || pos > L->len) {
printf("删除失败\n");
return -1;
}

    // 找到删除位置的前一个节点
Plink t = L;
for (int i = 1; i < pos; i++) {
t = t->next;
}

    // 删除节点并释放内存
Plink Q = t->next;       // 指向要删除的节点
t->next = t->next->next; // 前一个节点的next指向删除节点的下一个节点
free(Q);                 // 释放删除节点的内存
Q = NULL;                // 防止野指针
L->len--;                // 更新链表长度
return 0;
}

// 逆置链表
int link_re(Plink L) {
    // 如果链表为空或只有一个节点则无需逆置
    if (L == NULL || L->next == NULL) {
        printf("链表为空或只有一个节点，无需逆置\n");
        return -1;
    }

    Plink prev = NULL;   // 前一个节点指针
    Plink curr = L->next;  // 当前节点指针
    Plink next = NULL;   // 下一个节点指针

    // 遍历链表并逆置
    while (curr != NULL) {
        next = curr->next;  // 保存当前节点的下一个节点
        curr->next = prev;  // 当前节点的next指向前一个节点
        prev = curr;        // 更新前一个节点为当前节点
        curr = next;        // 更新当前节点为下一个节点
    }

    L->next = prev;  // 最终头节点的next指向逆置后的第一个节点
    printf("链表逆置成功！\n");
    return 0;
}

// 使用冒泡排序按学生成绩对链表进行排序
int bubble_sort(Plink L) {
    // 如果链表为空或只有一个节点则无需排序
if (NULL == L || L->next == NULL) {
return -1;
}

    Plink p, q;
    student t;  // 临时存储变量用于交换数据

    // 外层循环遍历链表
for (p = L->next; p != NULL; p = p->next) {
        // 内层循环进行两两比较
for (q = L->next; q->next != NULL; q = q->next) {
if (q->data.score > q->next->data.score) {
                // 交换节点数据
t = q->data;
q->data = q->next->data;
q->next->data = t;
}
}
}
return 0;
}

主函数文件：

#ifndef _STU_H_     // 防止头文件重复包含
#define _STU_H_

#include <myhead.h>  // 包含自定义头文件（假设这个文件包含标准库头文件和其他必要声明）

// 定义学生信息的结构体
typedef struct {
    int id;          // 学生学号
    char name[20];   // 学生姓名，最大长度为20
    float score;     // 学生成绩
} student;

// 定义链表节点结构体，用于存储学生信息
typedef struct iceberg {
    // 使用共用体：链表头节点存储长度，普通节点存储学生信息
    union {
        int len;       // 链表头节点存储链表长度
        student data;  // 普通节点存储学生信息
    };
    struct iceberg *next;  // 指向下一个节点的指针
} llink, *Plink;  // llink为链表节点结构体类型，Plink为指向链表节点的指针类型

// 函数声明

// 创建链表头节点，返回链表头节点指针
Plink creat_link();

// 输入学生信息，通过头插法创建链表
int input_link(Plink);

// 遍历链表，输出学生信息
int output_lin(Plink);

// 在链表的任意位置插入学生信息
int anypos_insert(Plink, int, student);

// 删除链表的任意位置的学生信息
int anypos_dele(Plink, int);

// 逆置链表，反转链表中的节点顺序
int link_re(Plink);

// 使用冒泡排序按学生成绩对链表进行排序
int bubble_sort(Plink);

#endif  // _STU_H_

成果展现：

三、总结

学习内容概述

1. 链表基本概念：

理解单链表、双向链表和循环链表的结构及其操作方式。

单链表：

每个节点只包含一个指向下一个节点的指针。

双向链表：

每个节点包含指向前一个节点和后一个节点的两个指针。

循环链表：

尾节点指向头节点，形成一个环形结构。

2.链表的基本操作：

包括链表的插入、删除、遍历、修改等操作。

头插法和尾插法：

不同的插入方法影响链表的构建顺序和效率。

节点的删除：

包括删除头节点、中间节点和尾节点的不同处理方式。

3. 链表与顺序表的对比：

链表在动态插入和删除时效率高，而顺序表适合快速随机访问。

4. 复杂链表操作：

包括链表的逆序、合并、排序等高阶操作。

学习难点

1. 链表的指针操作：

需要时刻保持对指针的准确控制，尤其在插入、删除和逆序操作中容易出现指针丢失或错误指向的情况。

2. 双向链表的节点操作：

每次操作时需要同时维护前驱指针和后继指针，操作复杂度增加。

3. 循环链表的特殊性：

因为尾节点指向头节点，操作时需要额外的边界条件判断，避免无限循环。

4. 链表的逆序与合并：

涉及多个指针的同步操作，特别是当链表长度不一致或需要多次遍历时容易出错。

主要事项

1. 链表的节点插入与删除：

在单链表中进行头插法和尾插法时，注意在头插时更新头节点指针，在尾插时确保尾节点指针指向新节点。

2. 内存管理与泄漏问题：

链表的节点是动态分配的内存，必须确保在删除节点时正确释放内存，以防止内存泄漏。

3. 链表的遍历与输出：

在遍历链表时，特别是在循环链表中，注意终止条件，防止出现死循环。

4. 逆序与排序：

逆序操作需要在遍历的同时调整链表的指针指向，排序操作则需额外的算法支持（如冒泡排序或归并排序）来调整节点位置。

未来学习的重点

1. 复杂链表结构的实现：

学习如何实现双向循环链表，并深入理解其操作方式与使用场景。

2. 链表排序与优化：

研究如何高效地对链表进行排序，尤其是在不占用额外内存的前提下，完成链表的原地排序。

3. 链表在实际项目中的应用：

链表在内存管理、图结构、数据库等领域有广泛应用，未来可以通过实战项目进一步强化对链表操作的掌握。

4. 多种数据结构结合使用：

探索链表与其他数据结构（如栈、队列、树等）结合的应用场景，增强对数据结构整体的理解和应用能力。

原文地址：https://blog.csdn.net/weixin_65095004/article/details/142465449

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：前端框架对比和选择
下一篇：王道408考研数据结构-树与二叉树-第五章-第三四节

UML概述、类图关系及连接线表示
继承和实现体现的是一种类与类、或者类与接口间的纵向关系;依赖关联聚合组合体现的是类与类、类与接口间的引用，即横向关系;这几种关系，所表现的强弱程度依次为：组合 > 聚合 > 关联 >
阅读更多2024-11-17
131. HTML标签遮挡Canvas画布事件
HTML元素标签外面div父元素遮挡了Canvas画布鼠标事件，会造成相机控件的旋转、缩放等操作无效，也有可能会影响你的射线拾取,等等任何与canvas画布有关的鼠标事件都有可能收到影响，不过这算是普
阅读更多2024-11-17
Scala-字符串（拼接、printf格式化输出等）-用法详解
Scala-字符串（拼接、printf格式化输出等）用法
阅读更多2024-11-17
c++原型模式（Prototype Pattern）
每个原型类实现自己的克隆方法，从而确保了对象的正确复制。
阅读更多2024-11-17
问题大集-01-kafka问题
1、Windows下启动单机kafka出现：系统找不到指定路径解决：是kafka不能识别本机的java环境（JVM），故需要指定java路径，进入kafka路径下的\bin\windows，找到：ka
阅读更多2024-11-17
【点云上采样】最近邻插值上采样算法增加点云密度
传感器采集到的点云比较稀疏，毕竟价位在那，好的太贵，买便宜的点又太稀，需要增加点云数据。
阅读更多2024-11-17
阮一峰科技爱好者周刊（第 325 期）推荐工具：一个基于 Next.js 的博客和 CMS 系统
近期，阮一峰在科技爱好者周刊第 325 期中推荐了一款开源工具——ReactPress，ReactPress一个基于 Next.js 的博客和 CMS 系统，可查看 demo站点。（@fecommun
阅读更多2024-11-17
js识别二维码
将二维码转换为链接
阅读更多2024-11-17
C 语言【单链表】
‌数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。单链表的特点包括动态存储、非连续存储、易于插入和删除。节点可以定义成一个结构体，每个节点中包含一个数据和下一个节点的地址。上面的结构体定
阅读更多2024-11-17
校园求职招聘系统（程序+数据库+报告）
基于Spring Boot框架实现的校园求职招聘系统，系统包含两种角色：管理员、用户,系统分为前台和后台两大模块
阅读更多2024-11-17