习题一：牛牛的单向链表
描述
- 牛牛从键盘输入一个长度为 n 的数组，问你能否用这个数组组成一个链表，并顺序输出链表每个节点的值。
输入描述
- 第一行输入一个正整数 n ，表示数组的长度
输出描述
- 制作一个链表然后输出这个链表的值
示例
输入： 4 5 4 2 1 输出： 5 4 2 1 说明： 请实现链表后再遍历输出结果！
代码实现
#include <stdio.h> #include <stdlib.h> //单向循环链表 typedef struct node { int data; struct node *next; }node; //创建头节点 node *add_head() { node *Head = (node *)malloc(sizeof(node)); if(Head == NULL) return NULL; Head->next = Head; return Head; } //尾插法 void add_node(node *Head,int data) { node *new = (node*)malloc(sizeof(node)); if(new == NULL) return; //节点成员赋值 new->data = data; new->next = NULL; //链接 node *pT = NULL; for(pT = Head;pT->next != Head;pT = pT->next); new->next = pT->next; pT->next = new; } //输出链表 void output(node *Head) { if(Head->next == Head) return; node *pT = Head->next; while(pT != Head) { printf("%d ",pT->data); pT = pT->next; } } int main(void) { node *Head = add_head();//头节点 int n,i,j; scanf("%d",&n); int arr[n]; //将键盘键入的数据存放到数组中 for(i = 0;i < n;i++) scanf("%d",&arr[i]); //将数据插入链表 for(j = 0;j < n;j++) add_node(Head, arr[j]); output(Head); return 0; }
习题二：牛牛的链表交换
描述
- 牛牛尝试把一个长度为 n 的数组转换成链表并把链表前两个节点交换位置和把链表最后两个节点交换位置。
输入描述
- 第一行输入一个正整数 n 表示数组的长度
- 第二行输入 n 个正整数，表示数组中各个元素的值
输出描述
- 把数组转换成链表后输出交换位置后的链表
示例1
输入： 4 2 3 4 5 输出： 3 2 5 4
示例2
输入： 3 3 2 1 输出： 2 1 3
代码实现
#include <stdio.h> #include <stdlib.h> //单向循环链表 typedef struct node { int data; struct node *next; }node; //创建头节点 node *add_head() { node *Head = (node *)malloc(sizeof(node)); if(Head == NULL) return NULL; Head->next = Head; return Head; } //尾插法 void add_node(node *Head,int data) { node *new = (node*)malloc(sizeof(node)); if(new == NULL) return; //节点成员赋值 new->data = data; new->next = NULL; //链接 node *pT = NULL; for(pT = Head;pT->next != Head;pT = pT->next); new->next = pT->next; pT->next = new; } //节点交换 void swap_node(node *Head) { node *p1 = Head->next;//第一个节点 node *p2 = Head->next->next;//第二个节点 //前两个节点交换 p1->next = p2->next; p2->next = p1; Head->next = p2; node *pT = NULL; node *pT1 = NULL; node *pT2 = NULL; for(pT = Head;pT->next->next->next != Head;pT = pT->next);//找到倒数第三个节点 for(pT1 = Head;pT1->next->next != Head;pT1 = pT1->next);//倒数第二个 for(pT2 = Head;pT2->next != Head;pT2 = pT2->next);//最后一个节点 //后两个节点交换 pT1->next = Head; pT2->next = pT1; pT->next = pT2; } //输出链表 void output(node *Head) { if(Head->next == Head) return; node *pT = Head->next; while(pT != Head) { printf("%d ",pT->data); pT = pT->next; } } int main(void) { node *Head = add_head();//头节点 int n,i,j; scanf("%d",&n); int arr[n]; //将键盘键入的数据存放到数组中 for(i = 0;i < n;i++) scanf("%d",&arr[i]); //将数据插入链表 for(j = 0;j < n;j++) add_node(Head, arr[j]); swap_node(Head); output(Head); return 0; }
习题三：牛牛的单链表求和
描述
- 牛牛输入了一个长度为 n 的数组，他想把这个数组转换成链表，链表上每个节点的值对应数组中一个元素的值，然后遍历链表并求和各节点的值。
输入描述
- 第一行输入一个正整数 n ，表示数组的长度。
- 第二行输入 n 个正整数，表示数组中各个元素的值。
输出描述
- 把数组转换成链表然后对其求和并输出这个值。
示例
输入： 5 5 2 3 1 1 输出： 12
代码实现
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLDataType; typedef struct SListNode { struct SListNode*next; SLDataType Data; }SLNode; SLNode*BuyNode(SLDataType X) { SLNode*newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { printf("malloc is fail\n"); } else { newnode->next = NULL; newnode->Data = X; } return newnode; } void SLNodePushBack(SLNode**pHead, SLDataType X) { SLNode*newnode = BuyNode(X); if (*pHead == NULL) { *pHead = newnode; } else { SLNode*tail = *pHead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } int SLNodeSum(SLNode*pHead) { SLNode*tail=pHead; int sum=0; while(tail!=NULL) { sum+=tail->Data; tail=tail->next; } return sum; } int main() { SLNode*PList = NULL; int i, n = 0; int arr[100] = { 0 }; scanf("%d\n", &n); for (i = 0; i<n; i++) { scanf("%d ", &arr[i]); SLNodePushBack(&PList, arr[i]); } int sum=SLNodeSum(PList); printf("%d ",sum); return 0; }
习题四：牛牛的双链表求和
描述
- 牛牛输入了两个长度相同的数组分别是 a 和 b ，然后把数组 a 和 b 转换成链表 a 和链表 b 。把链表 a 中的全部值按顺序加到链表 b 中。
输入描述
- 第一行输入一个正整数 n ，表示数组的长度。
- 第二行和第三行分别输入 n 个正整数，表示数组 a 和 数组 b 的值。
输出描述
- 把数组 a 和数组 b 转换成链表，然后把链表 a 中的值加到链表 b 中，然后输出加和后的链表。
示例
输入： 5 5 4 2 1 3 2 4 5 8 9 输出： 7 8 7 9 12
代码实现
#include <stdlib.h> //单向循环链表 typedef struct node { int data; struct node *next; }node; //创建链表b头节点 node *add_head() { node *Head = (node *)malloc(sizeof(node)); if(Head == NULL) return NULL; Head->next = Head; return Head; } //尾插法 void add_node(node *Head,int data) { node *new = (node*)malloc(sizeof(node)); if(new == NULL) return; //节点成员赋值 new->data = data; new->next = NULL; //链接 node *pT = NULL; for(pT = Head;pT->next != Head;pT = pT->next); new->next = pT->next; pT->next = new; } //输出链表 void output(node *Head) { if(Head->next == Head) return; node *pT = Head->next; while(pT != Head) { printf("%d ",pT->data); pT = pT->next; } } int main(void) { node *Head = add_head();//链表头节点 int n,i,j; scanf("%d",&n); int arr[n]; int brr[n]; //将键盘键入的数据存放到数组中 for(i = 0;i < n;i++) scanf("%d",&arr[i]); for(i = 0;i < n;i++) scanf("%d",&brr[i]); //将数据插入链表 for(j = 0;j < n;j++) add_node(Head, arr[j]+brr[j]); output(Head); return 0; }
习题五：牛牛的链表删除
描述
- 牛牛从键盘输入了一个长度为 n 的数组，把这个数组转换成链表然后把链表中所有值是 x 的节点都删除。
输入描述
- 第一行输入两个正整数 n 和 x 表示数组的长度和要删除的链表节点值 x 。
- 第二行输入 n 个正整数表示数组中每个元素的值。
输出描述
- 把数组转换成链表然后删除所有值是 x 的节点，删除后输出这个链表。
示例1
输入： 5 3 1 5 3 2 3 输出： 1 5 2
示例2
输入： 5 3 1 5 2 7 8 输出： 1 5 2 7 8
代码实现
#include <stdio.h> #include <stdlib.h> //单向循环链表 typedef struct node { int data; struct node *next; }node; //创建链表头节点 node *add_head() { node *Head = (node *)malloc(sizeof(node)); if(Head == NULL) return NULL; Head->next = Head; return Head; } //尾插法 void add_node(node *Head,int data) { node *new = (node*)malloc(sizeof(node)); if(new == NULL) return; //节点成员赋值 new->data = data; new->next = NULL; //链接 node *pT = NULL; for(pT = Head;pT->next != Head;pT = pT->next); new->next = pT->next; pT->next = new; } //删除节点 void delete_node(node *Head,int data) { node *del = Head->next; while(del != Head) { //找到要删除节点的前一个节点 if(del->next->data == data) { node *ptemp = del->next;//要删除的节点 del->next = ptemp->next; free(ptemp); } del = del->next; } } //输出链表 void output(node *Head) { if(Head->next == Head) return; node *pT = Head->next; while(pT != Head) { printf("%d ",pT->data); pT = pT->next; } } int main(void) { node *Head = add_head();//链表头节点 int n,i,j,x; scanf("%d",&n); int arr[n]; scanf("%d",&x); //将键盘键入的数据存放到数组中 for(i = 0;i < n;i++) scanf("%d",&arr[i]); //将数据插入链表 for(j = 0;j < n;j++) add_node(Head, arr[j]); //删除节点 delete_node(Head, x); //输出链表 output(Head); return 0; }
习题六：牛牛的链表添加节点
描述
- 牛牛输入了一个长度为 n 的数组，他把这个数组转换成链表并在第 i 个节点的后面添加一个值为 i 的新节点
输入描述
- 第一行输入两个正整数分别是 n 和 i ，表示数组的长度、需要添加节点的位置和节点的值
- 第二行输入 n 个正整数表示数组中每个元素的值。
输出描述
- 把数组转换成链表并在第 i 个节点后的添加一个新节点值，新节点的值是 i。
示例
输入： 5 3 5 4 8 6 3 输出： 5 4 8 3 6 3
代码实现
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLDataType; typedef struct SListNode { struct SListNode*next; SLDataType Data; }SLNode; SLNode*BuyNode(SLDataType X) { SLNode*newnode=(SLNode*)malloc(sizeof(SLNode)); if(newnode==NULL) { printf("malloc is fail\n"); } else { newnode->next=NULL; newnode->Data=X; } return newnode; } void SLNodePushBack(SLNode**pHead,SLDataType X) { SLNode*newnode=BuyNode(X); if(*pHead==NULL) { *pHead=newnode; } else { SLNode*tail=*pHead; while(tail->next!=NULL) { tail=tail->next; } tail->next=newnode; } } void SLNodeInsert(SLNode*pHead,SLDataType p) { SLNode*prev=NULL; SLNode*cur=pHead; int j=0; while(j<p) { j++; prev=cur; cur=cur->next; } SLNode*newnode=BuyNode(p); prev->next=newnode; newnode->next=cur; } void SLNodePrint(SLNode*pHead) { SLNode*cur=pHead; while(cur!=NULL) { printf("%d ",cur->Data); cur=cur->next; } } int main() { SLNode*PList=NULL; int i,n,p=0; int arr[100]={0}; scanf("%d %d",&n,&p); for(i=0;i<n;i++) { scanf("%d ",&arr[i]); SLNodePushBack(&PList,arr[i]); } SLNodeInsert(PList,p); SLNodePrint(PList); free(PList); PList=NULL; return 0; }
