链表（C语言代码）

### 链表（C语言代码） #### 数据结构与操作 链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的链接。链表的操作包括创建、插入、查找、删除等基本功能。 #### 创建链表 在C语言中，创建链表涉及定义节点结构体类型、分配内存空间以及连接这些节点。例如，代码中定义了一个名为`Grade_Info`的结构体类型，用来存储成绩和指向下一个节点的指针。此结构体类型通过`typedef`被命名为`NODE`类型。 ```c struct Grade_Info { int score; struct Grade_Info* next; }; typedef struct Grade_Info NODE; ``` 创建链表的过程是先创建头结点，并将其指针域设置为空，然后逐个创建节点并连接到链表尾部。`Create_LinkList`函数实现了这一过程： ```c NODE* Create_LinkList() { NODE* head, * tail, * pnew; int scor; // 创建头节点 head = (NODE*)malloc(sizeof(NODE)); if (head == NULL) { printf("no enough memory!\n"); return(NULL); } head->next = NULL; // 头节点的指针域置空 tail = head; // 尾指针初始化为头节点 // 输入节点数量 int f; scanf_s("%d", &f); for (int ii = 1; ii <= f; ii++) { scanf_s("%d", &scor); // 输入成绩 if (scor < 0) { // 成绩为负，循环退出 printf("error!"); return 0; } // 创建新节点 pnew = (NODE*)malloc(sizeof(NODE)); if (pnew == NULL) { // 创建新节点失败 printf("no enough memory!\n"); return(NULL); } pnew->score = scor; pnew->next = NULL; // 连接到链表尾部 tail->next = pnew; tail = pnew; } return(head); } ``` #### 插入节点 向链表中插入新节点涉及到找到插入位置的前一个节点，并修改其指针指向新节点。`Insert_LinkList`函数实现这一功能： ```c void Insert_LinkList(NODE* head, NODE* pnew, int i) { NODE* p; int j; p = head; for (j = 0; j < i - 1 && p != NULL; j++) // 找到第i个节点的前一个节点 p = p->next; if (p == NULL) { // 第i个节点不存在 printf("the %d node not found!\n", i); return; } pnew->next = p->next; // 新节点指向第i个节点的后继 p->next = pnew; // 第i个节点指向新节点 } ``` #### 删除节点 删除链表中的节点，需要找到待删节点的前一个节点，并修改其指针指向待删节点的后继。`Delete_LinkList`函数完成了这个任务： ```c void Delete_LinkList(NODE* head, int i) { NODE* p, * q; int j; if (i == 0) return; // 删除头指针，则直接返回 p = head; for (j = 0; j < i - 1 && p != NULL; j++) // 找到第i个节点的前一个节点 p = p->next; if (p == NULL || p->next == NULL) { // 检查第i个节点是否存在 printf("the %d node not found!\n", i); return; } q = p->next; // 要删除的节点 p->next = q->next; // 前一个节点指向要删除节点的后继 free(q); // 释放内存 } ``` #### 查找节点 查找链表中的节点可以通过遍历链表来实现。`Find_LinkList`函数实现了这一功能，它遍历链表直到找到指定位置的节点或到达链表末尾： ```c void Find_LinkList(NODE* head, int i) { NODE* p; int j; p = head->next; // 从第一个有效节点开始查找 for (j = 1; j < i && p != NULL; j++) p = p->next; if (p == NULL) { printf("the %d node not found!\n", i); } else { printf("Score of the %d node is: %d\n", i, p->score); } } ``` #### 总结 以上是对链表基本操作的详细介绍，包括创建、插入、查找和删除节点。这些操作是链表编程的基础，理解并掌握它们对于学习更复杂的算法和数据结构至关重要。