C语言笔试练习（二）

1、编写代码，移除未排序链表中的重复结点

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }Link; typedef Link* linken; linken head; void insert_tail(int num) { linken p = head; while(p->next != NULL) { p = p->next; } linken new = (linken)malloc(sizeof(Link)); new->data = num; p->next = new; new->next = NULL; } void display() { linken p = head; while(p->next != NULL) { p = p->next; printf("%d ",p->data); } printf("\n"); } void delete() { linken p = head; linken pre = head; linken ptr = head; while(p->next != NULL) { p = p->next; pre = p; while(pre->next != NULL) { ptr = pre; pre = pre->next; if(pre->data == p->data) { ptr->next = pre->next; } } } } int main() { int i = 0; head = (linken)malloc(sizeof(Link)); if(head == NULL) { perror("malloc"); return 0; } for(i = 0;i < 10;i++) { insert_tail(i+1); } insert_tail(5); insert_tail(6); display(); delete(); display(); return 0; }

---

2、实现一个算法，找出单链表中的倒数第k个结点

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }Link; typedef Link* linken; linken head; void insert_tail(int num) { linken p = head; while(p->next != NULL) { p = p->next; } linken new = (linken)malloc(sizeof(Link)); new->data = num; p->next = new; new->next = NULL; } int display() { linken p = head; int count = 0; while(p->next != NULL) { p = p->next; printf("%d ",p->data); count++; } printf("\ncount = %d\n",count); return count; } void search(int count,int k) { linken p = head; int m_count = 0; int flag = 0; while(p->next != NULL) { p = p->next; m_count++; if(m_count == count-k+1) { printf("倒数第%d个结点为：%d\n",k,p->data); flag = 1; break; } } if(flag == 0) { printf("超出查找范围！\n"); } } int main() { int i = 0; int count = 0; int k = 0; head = (linken)malloc(sizeof(Link)); if(head == NULL) { perror("malloc"); return 0; } for(i = 0;i < 10;i++) { insert_tail(i+1); } insert_tail(5); insert_tail(6); count = display(); printf("请输入k的值："); scanf("%d",&k); search(count,k); return 0; }

---

3、编写代码：以给定x为基准，将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }Link; typedef Link* linken; linken head; void insert_tail(int num) //尾插 { linken p = head; while(p->next != NULL) { p = p->next; } linken new = (linken)malloc(sizeof(Link)); new->data = num; p->next = new; new->next = NULL; } void display() //输出链表 { linken p = head; while(p->next != NULL) { p = p->next; printf("%d ",p->data); } printf("\n"); } void reserve(int num) //将链表分为两半 { linken p = head; linken pre = head; linken temp = NULL; if(p->next == NULL) { printf("no data!\n"); } while(p->next != NULL) { pre = p; p = p->next; if(p->data < num) //如果数字小于所输入的num值 { temp = (linken)malloc(sizeof(Link)); temp->data = p->data; //将数值取出放入新的结点temp里 temp->next = head->next; //然后用temp进行头插 head->next = temp; if(p->next == NULL) { pre->next = NULL; } pre->next = p->next; //删除原来的结点 p = pre; //重新指向原来的结点 } } } int main() { int i = 0; int num = 0; head = (linken)malloc(sizeof(Link)); if(head == NULL) { perror("malloc"); return 0; } insert_tail(6); for(i = 0;i < 10;i++) { insert_tail(i+1); } insert_tail(5); insert_tail(6); display(); printf("请输入数字："); scanf("%d",&num); reserve(num); display(); return 0; }