C语言链表专题复习

链表c语言题摘要：1.链表的概念和基本结构2.C 语言中链表的实现3.链表的操作及其应用4.链表的优势与局限性正文：一、链表的概念和基本结构链表是一种数据结构，它是由一系列节点组成，每个节点包含两个部分：数据域和指针域。

数据域用于存储数据，指针域则指向下一个节点。

链表的第一个节点称为头节点，最后一个节点称为尾节点。

链表可以根据需要动态增加或删除节点，因此具有很大的灵活性。

二、C 语言中链表的实现在C 语言中，链表的实现通常包括两个部分：链表结构体和链表操作函数。

链表结构体用于定义链表的节点，它包含数据域和指针域。

链表操作函数则负责实现链表的各种操作，如创建节点、插入节点、删除节点等。

以下是一个简单的链表结构体示例：```ctypedef struct Node {int data; // 数据域struct Node *next; // 指针域，指向下一个节点} Node;```三、链表的操作及其应用链表的操作主要包括创建节点、插入节点、删除节点等。

这些操作可以通过链表操作函数来实现。

以下是一些常见的链表操作示例：1.创建节点：```code *createNode(int data) {Node *newNode = (Node *) malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;}```2.插入节点：```cvoid insertNode(Node **head, int data) {Node *newNode = createNode(data);newNode->next = *head;*head = newNode;}```3.删除节点：```cvoid deleteNode(Node **head, int data) {Node *temp;if (*head == NULL) return;if ((*head)->data == data) {temp = *head;*head = (*head)->next;free(temp);return;}Node *prev = *head;while (prev->next!= NULL && prev->next->data!= data) { prev = prev->next;}if (prev->next == NULL) return;temp = prev->next;prev->next = temp->next;free(temp);}```四、链表的优势与局限性链表的优势在于它可以根据需要动态增加或删除节点，因此在存储动态数据时具有很大的灵活性。

关于链表常考的笔试面试题1、单链表逆序，在原列表的基础上进行调整struct ListNode* ReverseList(struct ListNode* pHead ){// write code here//判断第一个元素是否为空，如果为空，则返回NULL;并判断第二个元素是否为空，如果为空，则不需要逆序，直接返回if(pHead == NULL || pHead->next == NULL) return pHead;//定义三个节点指针，分别存放前一个操作节点，当前操作节点，下一个操作节点struct ListNode *temp1 = NULL,*temp2 = pHead,*temp3 = pHead->next;//当下一个操作节点存在时，执行循环，将当前节点的next指向前一个节点，并移动三个指针位置while(NULL != temp3){temp2->next = temp1;temp1 = temp2;temp2 = temp3;temp3 = temp2->next;}//当temp3为空时，说明temp2指向最后一个节点，只需将它的next指向前一个节点temp2->next = temp1;return temp2;}2、找出链表的倒数第n个节点int query_reverse(List* list,size_t index){Node* f = list->head;Node* s = list->head;for(int i=0;i<index;i++){f = f->next;if(f == NULL) return false;}while(f){f = f->next;s = s->next;}return s->data;3、判断链表中是否有环bool is_ring(List* list){Node* fast = list->head;//快指针Node* slow = list->head;//慢指针while(fast && fast->next){fast = fast->next->next;//快指针每次走两步slow = slow->next;//慢指针每次走一步if(slow == fast) return true;//如果相同，则该链表有环}return false;}4、找到环形链表的入口int ring_in(List* list){if(is_ring){Node* fast = list->head;Node* slow = list->head;Node* meet = list->head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;meet = meet->next;if(slow == fast){slow = list->head;fast = meet;fast = fast->next;slow = slow->next;if(slow == fast)return fast->data;}}}return -1;}5、合并两个有序链表，合并后依然有序List* merge_list(List* list1,List* list2){Node* m = list1->head->next;Node* n = list2->head->next;Node* new = create_node();if(list1 == NULL) return list2;if(list2 == NULL) return list1;if(list1== NULL && list2== NULL) return NULL;while(list1&&list2){if(m->data < n->data){new->next = m;m = m->next;}else{new->next = n;n = n->next;}new = new->next;}new->next = m?m:n;return new;}6、判断两个链表是否是Y型链表bool is_y(List* l1,List* l2){int cnt1 = 0,cnt2 = 0;Node* m = l1->head->next;Node* n = l2->head->next;while(m){cnt1++;m = m->next;}while(n){cnt2++;n = n->next;}if(cnt1>cnt2){for(int i=0;i<cnt1-cnt2;i++){m = m->next;}}else{for(int i=0;i<cnt2-cnt1;i++){n = n->next;}}while(m == NULL || n = NULL){m = m->next;n = n->next;if(m = n) return true;}return false;}。

链表c语言经典例题
链表是计算机科学中的经典数据结构之一，常用于存储和操作动态数据。

以下是一些常见的链表例题，可以帮助理解链表的基本操作和应用。

1. 链表的创建：
- 创建一个空链表。

- 创建一个包含指定节点值的链表。

2. 链表的插入操作：
- 在链表的头部插入一个节点。

- 在链表的尾部插入一个节点。

- 在指定位置插入一个节点。

3. 链表的删除操作：
- 删除链表的头节点。

- 删除链表的尾节点。

- 删除指定数值的节点。

4. 链表的查找操作：
- 查找链表中指定数值的节点。

- 查找链表的中间节点。

5. 链表的逆序操作：
- 反转整个链表。

- 反转链表的前 N 个节点。

- 反转链表的一部分区间内的节点。

6. 链表的合并操作：
- 合并两个有序链表，使其有序。

- 合并 K 个有序链表，使其有序。

7. 链表的环检测：
- 判断链表中是否存在环，若存在，则返回环的起始节点。

8. 链表的拆分操作：
- 将一个链表按照奇偶位置拆分成两个链表。

以上是一些链表的经典例题，通过解答这些例题，可以加深对链表结构和基本操作的理解。

在编写对应的 C 语言代码时，需要注意链表节点的定义、指针的使用以及内存的动态分配和释放等问题。

计算机等级考试二级C语言程序设计专项训练题——单链表一．程序填空题1．给定程序的主函数中，已给出由结构体构成的链表结点a、b、c，各结点的数据域中均存入字符，函数fun的功能是：将a、b、c 三个结点链接成一个单向链表，并输出链表结点中的数据。

请在下划线处填入正确的内容并将下划线删除,使程序得出正确的结果。

注意：不得增行或删行，也不得更改程序的结构！#include <stdio.h>typedef struct list{char data;struct list *next;}Q;void fun(Q *pa, Q *pb, Q *pc){Q *p;/**********found**********/pa->next=___1___;pb->next=pc;p=pa;while( p ){/**********found**********/printf(" %c",____2_____);/**********found**********/p=____3____;}printf("\n");}int main(){Q a, b, c;a.data='E';b.data='F';c.data='G'; c.next=NULL;fun( &a, &b, &c );return 0;}2．给定程序中，函数fun的功能是：统计出带有头结点的单向链表中结点的个数，存放在形参n所指的存储单元中。

请在下划线处填入正确的内容并将下划线删除,使程序得出正确的结果。

注意：不得增行或删行，也不得更改程序的结构！#include <stdio.h>#include <stdlib.h>#define N 8typedef struct list{int data;struct list *next;} SLIST;SLIST *creatlist(int *a);void outlist(SLIST *);void fun( SLIST *h, int *n){SLIST *p;/**********found**********/___1___=0;p=h->next;while(p){(*n)++;/**********found**********/p=p->___2___;}}int main(){SLIST *head;int a[N]={12,87,45,32,91,16,20,48}, num;head=creatlist(a);outlist(head);/**********found**********/fun(___3___, &num);printf("\nnumber=%d\n",num);return 0;}SLIST *creatlist(int a[]){SLIST *h,*p,*q;int i;h=p=(SLIST *)malloc(sizeof(SLIST));for(i=0; i<N; i++){q=(SLIST *)malloc(sizeof(SLIST));q->data=a[i]; p->next=q; p=q;}p->next=0;return h;}void outlist(SLIST *h){SLIST *p;p=h->next;if (p==NULL) printf("The list is NULL!\n");else{printf("\nHead ");do{printf("->%d",p->data);p=p->next;} while(p!=NULL);printf("->End\n");}}3．给定程序中，函数fun的功能是：计算出带头结点的单向链表中各结点数据域之和作为函数值返回。

c语言链表复习题C语言链表复习题链表是C语言中常用的数据结构之一，它可以用来存储和操作大量的数据。

在这篇文章中，我们将复习一些与链表相关的题目，以加深对链表的理解和运用。

1. 链表的基本结构链表由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

我们可以通过定义一个结构体来表示链表节点，例如：```cstruct Node {int data;struct Node* next;};```2. 创建一个链表首先，我们需要定义一个指向链表头节点的指针。

然后，我们可以通过动态分配内存来创建一个新节点，并将头指针指向该节点。

接下来，我们可以按照需要添加更多的节点。

例如，下面的代码演示了如何创建一个包含三个节点的链表：```cstruct Node* head = NULL;// 创建第一个节点struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));node1->data = 1;node1->next = NULL;head = node1;// 创建第二个节点struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));node2->data = 2;node2->next = NULL;node1->next = node2;// 创建第三个节点struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));node3->data = 3;node3->next = NULL;node2->next = node3;```3. 遍历链表要遍历链表，我们可以使用一个指针从头节点开始，依次访问每个节点的数据元素。

下面的代码演示了如何遍历上述创建的链表，并打印每个节点的数据：```cstruct Node* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}```4. 插入节点要在链表中插入一个新节点，我们首先需要找到要插入位置的前一个节点。

下面哪种选项描述了链表的特点？A) 可以随机访问元素B) 拥有固定大小的内存空间C) 元素之间通过指针连接D) 可以自动调整大小答案: C在链表中，头节点的作用是什么？A) 存储链表的长度B) 存储链表的最后一个节点C) 存储链表的第一个节点D) 存储链表的中间节点答案: C下面哪种选项描述了双向链表的特点？A) 每个节点只有一个指针指向下一个节点B) 每个节点只有一个指针指向上一个节点C) 每个节点同时拥有指向前一个节点和后一个节点的指针D) 只能从链表的一端进行操作答案: C在链表中，删除一个节点的操作涉及修改哪些指针？A) 只需要修改被删除节点的前一个节点的指针B) 只需要修改被删除节点的后一个节点的指针C) 需要修改被删除节点的前一个节点和后一个节点的指针D) 不需要修改任何指针答案: C在链表的尾部添加一个新节点的操作复杂度是多少？A) O(1)B) O(n)C) O(log n)D) O(n^2)答案: A如何遍历链表的所有节点？A) 使用for循环B) 使用while循环C) 使用递归函数D) 使用if语句答案: B在链表中，如何找到特定值的节点？A) 使用线性搜索B) 使用二分搜索C) 使用递归搜索D) 使用栈搜索答案: A链表和数组相比，哪个更适合频繁插入和删除操作？A) 链表B) 数组C) 二叉树D) 堆栈答案: A在链表中，如何在指定位置插入一个新节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A链表的头指针指向什么？A) 链表的第一个节点B) 链表的最后一个节点C) 链表的中间节点D) 链表的空节点答案: A链表中节点的个数称为什么？A) 链表的长度B) 链表的高度C) 链表的宽度D) 链表的容量答案: A在链表中，如何删除指定值的节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A单链表的最后一个节点指向什么？A) 链表的第一个节点B) 链表的最后一个节点C) NULLD) 链表的中间节点答案: C双向链表相比于单向链表的优势是什么？A) 占用更少的内存空间B) 遍历速度更快C) 可以从任意方向遍历D) 插入和删除操作更快答案: C在链表中，如何找到倒数第n个节点？A) 遍历整个链表B) 使用递归函数C) 使用栈数据结构D) 使用双指针技巧答案: D链表的删除操作和数组的删除操作的时间复杂度分别是什么？A) 链表的删除操作为O(1)，数组的删除操作为O(n)B) 链表的删除操作为O(n)，数组的删除操作为O(1)C) 链表的删除操作为O(n)，数组的删除操作为O(n)D) 链表的删除操作为O(1)，数组的删除操作为O(1)答案: A在链表中，如何判断链表是否为空？A) 检查头指针是否为NULLB) 检查尾指针是否为NULLC) 检查链表的长度是否为0D) 检查链表的第一个节点是否为NULL答案: A链表的逆序操作是指什么？A) 删除链表中的节点B) 反转链表中节点的顺序C) 插入节点到链表的尾部D) 在链表中查找指定值的节点答案: B在链表中，如何查找指定值的节点？A) 使用线性搜索B) 使用二分搜索C) 使用递归搜索D) 使用栈搜索答案: A在双向链表中，如何删除指定值的节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A链表的插入操作和数组的插入操作的时间复杂度分别是什么？A) 链表的插入操作为O(1)，数组的插入操作为O(n)B) 链表的插入操作为O(n)，数组的插入操作为O(1)C) 链表的插入操作为O(n)，数组的插入操作为O(n)D) 链表的插入操作为O(1)，数组的插入操作为O(1)答案: A如何删除单向链表中的重复节点？A) 使用递归算法B) 使用双指针技巧C) 使用栈数据结构D) 不需要额外操作，链表会自动去重答案: B链表的优势之一是什么？A) 随机访问速度快B) 占用内存空间少C) 插入和删除操作高效D) 支持高级操作如排序和搜索答案: C在链表中，如何找到中间节点？A) 遍历整个链表B) 使用递归函数C) 使用栈数据结构D) 使用快慢指针技巧答案: D在链表中，如何在尾部添加一个新节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 创建一个新节点并更新尾指针答案: D链表的查找操作的时间复杂度是多少？A) O(1)B) O(log n)C) O(n)D) O(n^2)答案: C在双向链表中，如何找到倒数第n个节点？A) 从头节点开始遍历B) 从尾节点开始遍历C) 使用递归函数D) 使用双指针技巧答案: B链表的删除操作的时间复杂度是多少？A) O(1)B) O(log n)C) O(n)D) O(n^2)答案: A链表和数组相比，哪个更适合频繁插入和删除操作？A) 链表B) 数组C) 哈希表D) 栈答案: A如何判断链表是否有环？A) 使用线性搜索B) 使用递归算法C) 使用快慢指针技巧D) 使用栈数据结构答案: C在链表中，如何反转链表的顺序？A) 使用递归算法B) 使用栈数据结构C) 使用双指针技巧D) 使用循环迭代答案: D在链表中，如何删除所有节点？A) 依次删除每个节点B) 修改头指针为NULLC) 修改尾指针为NULLD) 不需要额外操作，链表会自动清空答案: A链表的头节点是什么？A) 链表的第一个节点B) 链表的最后一个节点C) 链表的中间节点D) 链表的空节点答案: A在链表中，如何插入一个新节点到指定位置之前？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A在链表中，如何删除指定位置的节点？A) 修改前一个节点的指针B) 修改后一个节点的指针C) 修改当前节点的指针D) 不需要修改任何指针答案: A单向链表和双向链表的区别是什么？A) 单向链表只有一个指针指向下一个节点，双向链表有两个指针分别指向前一个节点和后一个节点B) 单向链表只能从头到尾遍历，双向链表可以从头到尾或者从尾到头遍历C) 单向链表只能在尾部添加节点，双向链表可以在头部和尾部都添加节点D) 单向链表只能包含整型数据，双向链表可以包含任意类型的数据答案: A链表的删除操作和数组的删除操作的时间复杂度分别是什么？A) 链表的删除操作为O(1)，数组的删除操作为O(n)B) 链表的删除操作为O(n)，数组的删除操作为O(1)C) 链表的删除操作为O(n)，数组的删除操作为O(n)D) 链表的删除操作为O(1)，数组的删除操作为O(1)答案: A如何判断两个链表是否相交？A) 比较链表的长度是否相等B) 比较链表的头节点是否相等C) 比较链表的尾节点是否相等D) 比较链表中的所有节点是否相等答案: B链表和数组的主要区别是什么？A) 链表是一种线性数据结构，数组是一种非线性数据结构B) 链表的长度可变，数组的长度固定C) 链表支持随机访问，数组只能顺序访问D) 链表的插入和删除操作效率高，数组的访问效率高答案: B在链表中，如何找到倒数第k个节点？A) 从头节点开始遍历，直到倒数第k个节点B) 从尾节点开始遍历，直到倒数第k个节点C) 使用递归函数查找倒数第k个节点D) 使用双指针技巧，一个指针先移动k步，然后两个指针同时移动直到第一个指针到达链表末尾答案: D在链表中，如何判断是否存在环？A) 使用线性搜索，检查是否有重复的节点B) 使用递归算法，判断节点是否已经访问过C) 使用栈数据结构，检查节点是否已经入栈D) 使用快慢指针技巧，如果两个指针相遇，则存在环答案: D如何将两个有序链表合并成一个有序链表？A) 创建一个新链表，依次比较两个链表的节点并插入新链表中B) 将第一个链表的尾节点指向第二个链表的头节点C) 将第二个链表的尾节点指向第一个链表的头节点D) 使用递归算法，依次比较两个链表的节点并合并答案: A在链表中，如何删除重复的节点？A) 使用递归算法，遍历链表并删除重复的节点B) 使用双指针技巧，依次比较相邻节点并删除重复的节点C) 使用栈数据结构，检查节点是否已经入栈并删除重复的节点D) 不需要额外操作，链表会自动去重答案: B链表的优点是什么？A) 占用内存空间少B) 插入和删除操作高效C) 支持高级操作如排序和搜索D) 可以随机访问任意位置的元素答案: B。

C语⾔——基础链表详解敢于向⿊暗宣战的⼈，⼼⾥必须充满光明。

⼀、链表的构成1.构成链表是由⼀连串的结构（称为结点）组成的。

(1)结点的构成：数据（要储存的数据）+指针（指向下⼀个结点的指针）(2)关于⼏个定义头结点：链表⾸结点前的⼀个结点（不是必须的，但是如果有就可以在解决某些问题时候⽅便⼀些，通常可以⽤来储存链表的长度等信息）⾸结点：链表的第⼀个数据元素头指针：必须要有的（⽽头结点可以没有，注意两者⼀个是指针⼀个是结点，⼀个必须有⼀个可以没有），指向头结点/⾸节点的指针（永远指向链表的第⼀个结点）2.结点类型声明、创建结点struct node{int value;struct node *next;//创建了⼀个指向⼀个node类型的指针，⽤于指向下⼀个结点};//⾄此声明了⼀个结点类型//头指针:struct node *first = NULL;//结点创建：struct node *new_node;new_node = (struct node *)malloc(sizeof(struct node));//给结点分配内存单元。

注意：malloc返回的是void类型的指针,所以可以强制类型转换⼀下new_node -> value = 10;//把数据存储到结点中⼆、在链表开始处插⼊结点struct node * first = NULL;struct node *new_node;new_node =(struct node *)malloc(sizeof(struct node));new_node ->value = 10;//将new_node结点插⼊链表开始处new_node->next = first;//new_node指向的node类型的next值为NULL，NULL可作为链表结尾（空指针）first = new_node;//让first 指向 new_node指向的结点（其实就是刚才malloc出来的结点）//ok⾄此，现在就已经有了⼀个链表，它有⼀个结点，结点中储存的值是10new_node = (struct node*)malloc(sizeof(struct node));new_node ->value = 2;new_node->next = first;//⼜新创建了个结点并让next指向第⼀次创建的结点（因为first是指向第⼀次创建的结点的）first = new_node;//可以理解为把头指针重置到头部我们把它封装成函数对于这样的函数我们传⼊⼀个链表list，和⼀个希望存⼊链表的数值nstruct node* add_to_list(struct node *list,int n){sturct noed *new_node;new_node = (struct node*)malloc(sizeof(struct node));if(new_node == NULL){printf("malloc error\n");exit(0);}new_node->value = n;new_node->next = list;//把新结点接到链表中return new_node;}first = add_to_list(first,10);first = add_to_list(first,20);//需要注意的是add_to_list函数是没有办法修改指针的（因为这个相当于复制了⼀个指针传进去，能修改它指向的东西，但是没有办法对他本⾝进赋值存储）//所以我们返回⼀个指向新结点的指针，让他作为返回值赋值储存给first需要注意的是add_to_list函数是没有办法修改指针的（因为这个相当于复制了⼀个指针传进去，能修改它指向的东西，但是没有办法对他本⾝进赋值存储），所以我们返回⼀个指向新结点的指针，让他作为返回值赋值储存给first三、搜索链表while循环可以⽤，但是我们都知道for循环是很灵活的。

1、(1)数据结构中，与所使用的计算机无关的是数据的_C_______。

A)存储结构B)物理结构C)逻辑结构D)物理和存储结构评析：数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。

数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。

2、栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是____D____。

A)ABCED B)DBCEA C)CDABE D)DCBEA评析：栈操作原则上“后进先出”，栈底至栈顶依次存放元素A、B、c、D，则表明这4个元素中D是最后进栈，B、c处于中间，A最早进栈。

所以出栈时一定是先出D，再出c，最后出A。

3、线性表的顺序存储结构和线性表的链式存储结构分别是____B____。

A)顺序存取的存储结构、随机存取的存储结构B)随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构评析：顺序存储结构中，数据元素存放在一组地址连续的存储单元中，每个数据元素地址可通过公式LOC(ai)。

LOC(a1)+(i-1)L计算得到，从而实现了随机存取。

对于链式存储结构，要对某结点进行存取，都得从链的头指针指向的结点开始，这是一种顺序存取的存储结构。

4、在单链表中，增加头结点的目的是____A__。

A)方便运算的实现B)使单链表至少有一个结点C)标识表结点中首结点的位置D)说明单链表是线性表的链式存储实现评析：头结点不仅标识了表中首结点的位置，而且根据单链表(包含头结点)的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。

5、数据处理的最小单位是___C_____。

A)数据B)数据元素C)数据项D)数据结构评析：数据处理的最小单位是数据项；由若干数据项组成数据元素；而数据是指能够被计算机识别、存储和加工处理的信息载体；数据结构是指数据之间的相互关系和数据运算。

链表一、链表的基本结构(此处先展示单向链表)链表的每一个节点都拥有一个或多个变量记录特定数据，以及一个特定的指针变量用于指向它的下一个节点，一个连着一个形成链状，因此形象地称之为“链表”。

NULL的含义为“空指针”，可理解为该指针不指向任一节点。

二、单项链表的程序实现(1)单个节点结构体的定义(2)创建一个空链表(首节点不做存值作用的写法)①给首节点分配空间②初始化首节点调用方式：注：初始化步骤(head->num=-1;head->next=NULL;对程序实质上无影响)(3)插入(将一个值为num的节点插入到链表的最后)①给新节点分配空间②将数值存储到新节点中，并将next初始化为NULL③将上一个节点的next指针指向这一个节点④返回这一个节点，以供主过程中将最后一个节点更新为新节点调用方式：(now表示最后一次被更新的节点，num为需要被存储的数值，now初始化为head)(4)查询(查询存储的数值为num的节点，不存在则返回NULL)①从首节点开始，一次利用next查找下一个节点直至查到该数值或查完整个链表(5)删除(删除指定节点，可配合(4)使用以删除指定数值的节点)①从首节点开始，寻找该节点的上一个节点②将上一个节点的next指向该节点的下一个节点，即next③释放该节点的空间调用方式：(6)打印整个链表①从首节点的下一个节点开始，通过next依次打印整条链表调用方式:接下来给出以上函数的测试：三、双向链表双向链表就是在单向链表的基础上，给结点增加一个指向“上一个节点”的指针，可以显著加快如上述的删除操作的速度。

程序部分略。

四、循环链表当一条链表读入完成后，将其尾节点的next指针指向首节点，在这种情况下首节点不能按上述过程处理，而需要将其作为一个存储数值的节点进行处理。

程序部分略。

计算机等级考试二级C语言链表复习资料一、为什么用动态内存分配但我们未学习链表的时候，如果要存储数量比较多的同类型或同结构的数据的时候，总是使用一个数组。

比如说我们要存储一个班级学生的某科分数，总是定义一个float型（存在0.5分）数组：float score[30];但是，在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？在很多的情况下，你并不能确定要使用多大的数组，比如上例，你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。

这样，你的程序在运行时就申请了固定大小的你认为足够大的内存空间。

即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。

这种分配固定大小的内存分配方法称之为静态内存分配。

但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时：在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。

那么有没有其它的方法来解决这样的外呢体呢？有，那就是动态内存分配。

所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。

动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。

从以上动、静态内存分配比较可以知道动态内存分配相对于景泰内存分配的特点：1、不需要预先分配存储空间；2、分配的空间可以根据程序的需要扩大或缩小。

二、如何实现动态内存分配及其管理要实现根据程序的需要动态分配存储空间，就必须用到以下几个函数1、malloc函数malloc函数的原型为：void *malloc (unsigned int size)其作用是在内存的动态存储区中分配一个长度为size的连续空间。

其参数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。

结构体与链表11.1 结构体类型的定义结构体是由C语言中的基本数据类型构成的、并用一个标识符来命名的各种变量的组合，其中可以使用不同的数据类型。

1.结构体类型的定义Struct结构体名{ 类型标识符1 成员名1；类型标识符2 成员名2；……类型标识符n 成员名n；};Struct结构体名——结构体类型名2.关于结构体类型的说明：(1)“struct 结构体名”是一个类型名，它和int、float等作用一样可以用来定义变量。

(2)结构体名是结构体的标识符不是变量名，也不是类型名。

(3)构成结构体的每一个类型变量称为结构体成员，它像数组的元素一样，单数组中元素以下标来访问，而结构体是按结构体变量名来访问成员的。

(4)结构体中的各成员既可以属于不同的类型，也可以属于相同的类型。

(5)成员也可以是一个结构体类型，如：Struct date{Int month;Int day;Int year;};Struct person{Float num;Char name[20];Char sex;Int age;Struct date birthday;Char address[10];};11.2 结构体类型变量11.2.1 结构体类型变量的定义1.先定义结构体类型，再定义结构体变量形式：Struct 结构体名{类型标识符1 成员名1；类型标识符2 成员名2；……类型标识符n 成员名n；};Struct 结构体名变量名表；例如：Struct student{char name[20];Char sex;Int age;Float score;};Struct student stu1,stu2;2.在定义结构体类型的同时定义变量形式：Struct 结构体名{类型标识符1 成员名1；类型标识符2 成员名2；……类型标识符n 成员名n；}变量名表；例如：Struct student{Char name[20];Char sex;Int age;Float score;}stu1,stu2;3.用匿名形式直接定义结构体类型变量形式：Struct{类型标识符1 成员名1；类型标识符2 成员名2；……类型标识符n 成员名n；}变量名表；例如：StructChar naem[20];Char sex;Int age;Float score;}stu1,stu2;11.2.2 结构体变量的使用结构体是一种新的数据类型，因此结构体变量也可以像其它类型的变量一样赋值、运算，不同的是结构体变量以成员作为基本变量。

链表专题复习数组作为存放同类数据的集合;给我们在程序设计时带来很多的方便;增加了灵活性..但数组也同样存在一些弊病..如数组的大小在定义时要事先规定;不能在程序中进行调整;这样一来;在程序设计中针对不同问题有时需要3 0个元素大小的数组;有时需要5 0个数组元素的大小;难于统一..我们只能够根据可能的最大需求来定义数组;常常会造成一定存储空间的浪费..我们希望构造动态的数组;随时可以调整数组的大小;以满足不同问题的需要..链表就是我们需要的动态数组..它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间;决不构成对存储区的浪费..链表是一种复杂的数据结构;其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表;下面只介绍单向链表..7.4.1 单链表图7 - 3是单链表的结构..单链表有一个头节点h e a d;指向链表在内存的首地址..链表中的每一个节点的数据类型为结构体类型;节点有两个成员：整型成员实际需要保存的数据和指向下一个结构体类型节点的指针即下一个节点的地址事实上;此单链表是用于存放整型数据的动态数组..链表按此结构对各节点的访问需从链表的头找起;后续节点的地址由当前节点给出..无论在表中访问那一个节点;都需要从链表的头开始;顺序向后查找..链表的尾节点由于无后续节点;其指针域为空;写作为N U L L..图7 - 3还给出这样一层含义;链表中的各节点在内存的存储地址不是连续的;其各节点的地址是在需要时向系统申请分配的;系统根据内存的当前情况;既可以连续分配地址;也可以跳跃式分配地址..看一下链表节点的数据结构定义：struct node{int num;struct node p;} ;在链表节点的定义中;除一个整型的成员外;成员p是指向与节点类型完全相同的指针..在链表节点的数据结构中;非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型..这是在C中唯一规定可以先使用后定义的数据结构..单链表的创建过程有以下几步：1 定义链表的数据结构..2 创建一个空表..3 利用m a l l o c 函数向系统申请分配一个节点..4 将新节点的指针成员赋值为空..若是空表;将新节点连接到表头；若是非空表;将新节点接到表尾..5 判断一下是否有后续节点要接入链表;若有转到3 ;否则结束..单链表的输出过程有以下几步1 找到表头..2 若是非空表;输出节点的值成员;是空表则退出..3 跟踪链表的增长;即找到下一个节点的地址..4 转到2 ..下列是用尾插法创建链表新开辟的节点总是插在表末例7-5 创建一个存放正整数输入负数时做结束标志的单链表;并打印输出..include <stdlib.h> /包含ma l l o c 的头文件/include <stdio.h>struct node /链表节点的结构 /{int num;struct node next; } ;m a i n{struct node creat; / 函数声明 /void print;struct node head; / 定义头指针 /head=NULL;/建一个空表/head=creathead;/创建单链表/printhead;/打印单链表/ }//struct nodecreatstructnodehead函/数返回的是与节点相同类型的指针/{struct nodep1;p2;p1=p2=structnodemallocsizeofstructnode;申请/新节点/scanf"%d";&p1->num;/输入节点的值/p1->next=NULL;/将新节点的指针置为空/whilep1->num>0/输入节点的数值大于0/{ifhead==NULLhead=p1;/空表;接入表头/elsep2->next=p1;/非空表;接到表尾/p2=p1;p1=structnodemallocsizeofstructnode;申/请下一个新节点/scanf"%d";&p1->num;/输入节点的值/}return head;/返回链表的头指针/ }//void printstruct nodehead输/出以head为头的链表各节点的值/{struct node temp;temp=head;/取得链表的头指针/whiletemp=NULL/只要是非空表/{printf"%6d";temp->num;/输出链表节点的值/temp=temp->next;/跟踪链表增长/ } }在链表的创建过程中;链表的头指针是非常重要的参数..因为对链表的输出和查找都要从链表的头开始;所以链表创建成功后;要返回一个链表头节点的地址;即头指针..下列是用头插法创建链表新开辟的结点总是作为表头结点程序清单位：include <stdio.h>include <stdlib.h>struct node{ int num;struct node next; };struct node creatstruct node head{ struct node top; /top为新开辟的结点/top=struct node mallocsizeofstruct node;scanf“%d”;&top->num;whiletop->num>=0｛top->next=head; /原来的第一个结点接在新开辟的结点后面/head=top; /新开辟结点作表头结点;也就是说插在表头/top=struct node mallocsizeofstruct node;scanf“%d”;&top->num; }return head; }7.4.2 单链表的插入与删除在链表这种特殊的数据结构中;链表的长短需要根据具体情况来设定;当需要保存数据时向系统申请存储空间;并将数据接入链表中..对链表而言;表中的数据可以依此接到表尾或连结到表头;也可以视情况插入表中；对不再需要的数据;将其从表中删除并释放其所占空间;但不能破坏链表的结构..这就是下面将介绍的链表的插入与删除..1. 链表的删除在链表中删除一个节点;用图7 - 4描述如下：例7-6 创建一个学生学号及姓名的单链表;即节点包括学生学号、姓名及指向下一个节点的指针;链表按学生的学号排列..再从键盘输入某一学生姓名;将其从链表中删除..首先定义链表的结构：从图7 - 4中看到;从链表中删除一个节点有三种情况;即删除链表头节点、删除链表的中间节点、删除链表的尾节点..题目给出的是学生姓名;则应在链表中从头到尾依此查找各节点;并与各节点的学生姓名比较;若相同;则查找成功;否则;找不到节点..由于删除的节点可能在链表的头;会对链表的头指针造成丢失;所以定义删除节点的函数的返回值定义为返回结构体类型的指针..struct node deletstruct node head;char pstr/he a d 为头指针;删除ps t r 所在节点/{struct node temp;p;t e m p = h e a d ; / 链表的头指针 /if head==NULL / 链表为空 /printf"\nList is null\n";else /非空表 /{t e m p = h e a d ;while strcmptemp->str;pstr=0&&temp->next=NULL/ 若节点的字符串与输入字符串不同;并且未到链表尾 /{p = t e m p ;t e m p = t e m p - > n e x t ; / 跟踪链表的增长;即指针后移 / }ifstrcmptemp->str;pstr==0 / 找到字符串 /{iftemp==head { / 表头节点 /printf"delete string :%s\n";temp->str;h e a d = h e a d - > n e x t ;f r e e t e m p ; / 释放被删节点 /}e l s e{p->next=temp->next; /表中节点/printf"delete string :%s\n";temp->str;f r e e t e m p ;} }else printf"\nno find string\n"; /没找到要删除的字符串/}r e t u r n h e a d ; / 返回表头指针 / }2. 链表的插入首先定义链表的结构：struct{ int num; /学生学号 /char str20; /姓名 /struct node next; } ;在建立的单链表中;插入节点有三种情况;如图7 - 5所示..插入的节点可以在表头、表中或表尾..假定我们按照以学号为顺序建立链表;则插入的节点依次与表中节点相比较;找到插入位置..由于插入的节点可能在链表的头;会对链表的头指针造成修改;所以定义插入节点的函数的返回值定义为返回结构体类型的指针..节点的插入函数如下：struct node inserthead;pstr;n / 插入学号为n、姓名为p s t r 的节点 /struct node head; / 链表的头指针 /char pstr;int n;{ struct node p1;p2;p3;p1=struct nodemallocsizeofstruct node分;配/一个新节点/s t r c p y p 1 - > s t r ; p s t r ; / 写入节点的姓名字串 / p 1 - > n u m = n ; / 学号 /p 2 = h e a d ;if head==NULL / 空表 /{head=p1; p1->next=NULL;/ 新节点插入表头 /}e l s e{ /非空表 /whilen>p2->num&&p2->next=NULL/ 输入的学号小于节点的学号;并且未到表尾 /{p 3 = p 2 ;p 2 = p 2 - > n e x t ; / 跟踪链表增长 /}if n<=p2->num / 找到插入位置 /if head==p2 / 插入位置在表头 /{h e a d = p 1 ;p 1 - > n e x t = p 2 ;}e l s e{ /插入位置在表中 /p 3 - > n e x t = p 1 ;p 1 - > n e x t = p 2 ;}e l s e{ /插入位置在表尾 /p 2 - > n e x t = p 1 ;p 1 - > n e x t = N U L L ;}}r e t u r n h e a d ; / 返回链表的头指针 / }3. 实例例7 - 7创建包含学号、姓名节点的单链表..其节点数任意个;表以学号为序;低学号的在前;高学号的在后;以输入姓名为空作结束..在此链表中;要求删除一个给定姓名的节点;并插入一个给定学号和姓名的节点..include "stdlib.h"include "malloc. h"struct node /节点的数据结构 /{int num;char str20;struct node next; } ;main{ / 函数声明 /struct node creat;struct node insert;struct node delet;void print ;struct node head;char str20;int n;head=NULL; /做空表 /head=creat head; / 调用函数创建以head 为头的链表 / p r i n t h e a d ；/ 调用函数输出节点 / printf"\n input inserted num;name:\n";getsstr; /输入学号 /n=atoi str;getsstr; /输入姓名 /head=insert head; str; n; 将/节点插入链表/print head； / 调用函数输出节点/printf"\n input deleted name:\n";getsstr; /输入被删姓名 /head=delethead;str; /调用函数删除节点/ print head; /调用函数输出节点 /r e t u r n ; }/ 创建链表 /struct node creatstruct node head{char temp30;struct node pl;p2;pl=p2=struct node mallocsizeofstruct node; printf "input num; name: \n;"printf"exit:double times Enter\n";g e t s t e m p ;gets p1->str;pl->num=atoi temp;p l - > n e x t = N U L L ;while strlen pl->str>0{if head==NULL head=pl；else p2->next=p1;P 2 = p l ；pl=struct node mallocsizeofstruct node; printf "input num; name: \n";printf"exit:double times Enter\n";g e t s t e m p ;getspl ->str;p1->num=atoi temp;p1 - > n e x t = N U L L ; }return head; }/ 插入节点 /struct node insert head; pstr;n;struct node head;char pstr;int n;{ struct node pl;p2;p3;p1=struct nodemallocsizeofstruct node; strcpy p1->str; pstr;p 1 - > n u m = n ;p 2 = h e a d ;i f h e a d = = N U L L{h e a d = p l ; p l - > n e x t = N U L L ;}e l s e{while n>p2->num&&p2->next=NULL {p 3 = P 2p 2 = p 2 - > n e x t ; } if n<=p2->numif head==p2{h e a d = p l ;p l - > n e x t = p 2 ; } else{p 3 - > n e x t = p l ;p l - > n e x t = p 2 ; } else{p 2 - > n e x t = p l ;p l - > n e x t = N U L L ;} }r e t u r n h e a d ; }/ 删除节点 /struct node delet struct node head; char pstr{struct node temp;p;t e m p = h e a d ;if head==NULLprintf"\nList is null\n";else{ t e m p = h e a d ;while strcmptemp->str;pstr=O&&temp->next=NULL{p = t e m p ;t e m p = t e m p - > n e x t ;}i f s t r c m p t e m p - > s t r ; p s t r = = 0 {if temp== head{h e a d = h e a d - > n e x t ;f r e e t e m p ;}else{p->next =temp->next;printf"delete string :%s\n";temp->str;f r e e t e m p ;} }else printf"\nno find string\n";}returnhead; }/ 链表各节点的输出 /void print struct node head{struct node temp;t e m p = h e a d ;while temp=NULL{p r i n t f " \ n % d - - - - % s \ n " ; t e m p - > n u m ;t e m p - > s t r ；t e m p = t e m p - > n e x t ； }r e t u r n ; }带头结点与不带头结点链表的区别：题目中没说明;就当不带头结点;除非明确规定了带头结点..带头结点的链表的第一个结点没有数据域;只有指针域..例如要计算链表中所有结点数据的和;应定义一个指向结构体结点的指针;指向链表的第一个含数据的结点;给它赋值时;应是 struct node p=head->next; 其中head为链表的头指针..因为头结点不含数据;头结点指向的结点才开始带数据..如果是不带头结点的链表;第一个结点就含数据;因此;给它赋值时;应是struct node p=head;附：常见算法用链表实现1.查找算法例：如果有如下链表结构：struct st｛ char name20; /学生姓名/int cj; /学生成绩/struct st next; };如果链表已创建正确;要求输入一个学生姓名;查找该生成绩;并输出该生姓名;成绩;以及该生在链表中的位置第几个结点struct st searchstruct st h;char x{ struct st p=h;int flag=0;position=0;whilep=NULL{ position++；ifstrcmpp->name;x==0 {flag=1；break;}p=p->next; }ifflag==1{printf“在链表中的第%d个结点”;position;return p; } /找到了;返回该结点的地址/else{ printf“no found”; return ;} ｝main{ struct st q;head;char xm20;getsxm;head=creatNULL; /链表已创建;题目已规定;创建链表过程省略/ q=searchhead;xm;printf“%s: %d\n”;q->name;q->cj; }2.排序算法欲将链表中结点的成绩从大到小排列输出..include <stdlib.h>include <stdio.h>struct st{ int cj;struct st link; };void sortstruct st head{struct st p;q;int t;forp=head;p=NULL;p=p->linkforq=p->link;q=NULL;q=q->linkifq->cj>p->cj {t=p->cj;p->cj=q->cj;q->cj=t;} }注意：由于链表中结点在内存中是不连续的;故不可使用p++指针自增;指向链表的下一个结点;只能通过p=p->link指向下一个结点..单向链表只能从当前结点找到表尾方向的下一个结点;不可从当前结点找到表头方向的前一个结点..因为当前结点只存放了下一个结点的地址..。