数据结构（Day19）

一、学习内容

单链表

头删

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;       // 初始化链表长度为0p->next = NULL;   // 初始化链表的next指针为NULLreturn 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指向当前节点的nextt->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];   // 学生姓名，最大长度为20float 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_