编写程序实现单链表的各种基本运算要求用菜单组织所有功能。设单链表中存储的数据元素为int型要实现的功能包括：1输出单链表中的所有元素若单链表为空则给出提示信息；2按序号查找指定元素即输出单链表中的第i个元素；3按值查找指定元素即输出单链表中值为x的元素的序号；4在指定位置插入元素即在第i个元素前面插入值为x的元素；5删除指定元素即删除第i个元素；6求单链表的长度即数据结点的个数；7返回单链表中最后

#include <stdio.h> #include <stdlib.h>

//定义链表节点结构体 typedef struct node { int data; struct node *next; } Node;

//函数声明 Node *createList(); //创建链表 void printList(Node *head); //输出链表 Node *getNodeByIndex(Node *head, int index); //按序号查找节点 int getIndexByValue(Node *head, int value); //按值查找节点的序号 void insertNode(Node *head, int index, int value); //在指定位置插入节点 void deleteNode(Node *head, int index); //删除指定位置的节点 int getLength(Node *head); //获取链表长度 int getLastMinIndex(Node *head); //获取最后一个最小值节点的序号 void sortList(Node *head); //将链表排序 void deleteRange(Node *head, int x, int y); //删除[x,y]范围内的节点 void destroyList(Node *head); //销毁链表

int main() { Node *head = NULL; //链表头指针 int choice; //菜单选择项 int index, value; //序号、值 int x, y; //范围 while(1) { printf("\n"); printf("1. 创建链表\n"); printf("2. 输出链表\n"); printf("3. 按序号查找节点\n"); printf("4. 按值查找节点的序号\n"); printf("5. 在指定位置插入节点\n"); printf("6. 删除指定位置的节点\n"); printf("7. 获取链表长度\n"); printf("8. 获取最后一个最小值节点的序号\n"); printf("9. 将链表排序\n"); printf("10. 删除[x,y]范围内的节点\n"); printf("11. 销毁链表并退出\n"); printf("请选择："); scanf("%d", &choice); switch(choice) { case 1: head = createList(); printf("创建链表成功！\n"); break; case 2: printList(head); break; case 3: printf("请输入要查找的节点的序号："); scanf("%d", &index); if(index < 1 || index > getLength(head)) { printf("序号无效！\n"); } else { Node *node = getNodeByIndex(head, index); printf("节点的值为：%d\n", node->data); } break; case 4: printf("请输入要查找的节点的值："); scanf("%d", &value); index = getIndexByValue(head, value); if(index == -1) { printf("节点不存在！\n"); } else { printf("节点的序号为：%d\n", index); } break; case 5: printf("请输入要插入的节点的序号："); scanf("%d", &index); if(index < 1 || index > getLength(head) + 1) { printf("序号无效！\n"); } else { printf("请输入要插入的节点的值："); scanf("%d", &value); insertNode(head, index, value); printf("插入节点成功！\n"); } break; case 6: printf("请输入要删除的节点的序号："); scanf("%d", &index); if(index < 1 || index > getLength(head)) { printf("序号无效！\n"); } else { deleteNode(head, index); printf("删除节点成功！\n"); } break; case 7: printf("链表的长度为：%d\n", getLength(head)); break; case 8: index = getLastMinIndex(head); if(index == -1) { printf("链表为空或所有节点的值均不相等！\n"); } else { printf("最后一个最小值节点的序号为：%d\n", index); } break; case 9: sortList(head); printf("链表排序成功！\n"); break; case 10: printf("请输入x和y的值："); scanf("%d%d", &x, &y); deleteRange(head, x, y); printf("删除范围[%d,%d]内的节点成功！\n", x, y); break; case 11: destroyList(head); printf("销毁链表成功，程序退出！\n"); exit(0); default: printf("选择无效！\n"); break; } } return 0; }

//创建链表 Node *createList() { Node *head = NULL; //链表头指针 Node *tail = NULL; //链表尾指针 int value; //节点的值 printf("请输入节点的值（输入-1结束）："); while(1) { scanf("%d", &value); if(value == -1) { break; } Node node = (Node)malloc(sizeof(Node)); //创建节点 node->data = value; //设置节点的值 node->next = NULL; //设置节点的后继指针 if(head == NULL) { //链表为空 head = node; tail = node; } else { //链表不为空 tail->next = node; tail = node; } } return head; }

//输出链表 void printList(Node *head) { if(head == NULL) { printf("链表为空！\n"); } else { printf("链表中的元素为："); Node *p = head; while(p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } }

//按序号查找节点 Node *getNodeByIndex(Node *head, int index) { Node *p = head; for(int i = 1; i < index; i++) { p = p->next; } return p; }

//按值查找节点的序号 int getIndexByValue(Node *head, int value) { Node *p = head; int index = 1; while(p != NULL) { if(p->data == value) { return index; } p = p->next; index++; } return -1; }

//在指定位置插入节点 void insertNode(Node *head, int index, int value) { Node node = (Node)malloc(sizeof(Node)); //创建节点 node->data = value; //设置节点的值 node->next = NULL; //设置节点的后继指针 if(index == 1) { //插入到链表头部 node->next = head; head = node; } else { //插入到链表中间或尾部 Node *p = getNodeByIndex(head, index - 1); //查找插入位置的前驱节点 node->next = p->next; p->next = node; } }

//删除指定位置的节点 void deleteNode(Node *head, int index) { if(index == 1) { //删除链表头部节点 Node *p = head; head = head->next; free(p); } else { //删除链表中间或尾部节点 Node *p = getNodeByIndex(head, index - 1); //查找要删除的节点的前驱节点 Node *q = p->next; //要删除的节点 p->next = q->next; free(q); } }

//获取链表长度 int getLength(Node *head) { int length = 0; Node *p = head; while(p != NULL) { length++; p = p->next; } return length; }

//获取最后一个最小值节点的序号 int getLastMinIndex(Node *head) { if(head == NULL) { return -1; } int min = head->data; //最小值 int index = 1; //最小值节点的序号 int lastMinIndex = -1; //最后一个最小值节点的序号 Node *p = head; while(p != NULL) { if(p->data < min) { //找到新的最小值 min = p->data; lastMinIndex = index; } else if(p->data == min) { //找到与最小值相同的节点 lastMinIndex = index; } p = p->next; index++; } return lastMinIndex; }

//将链表排序 void sortList(Node *head) { if(head == NULL || head->next == NULL) { //链表为空或只有一个节点，无需排序 return; } //冒泡排序 int length = getLength(head); //链表长度 for(int i = 0; i < length - 1; i++) { Node *p = head; for(int j = 0; j < length - i - 1; j++) { if(p->data > p->next->data) { //相邻两个节点需要交换 int temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next; } } }

//删除[x,y]范围内的节点 void deleteRange(Node *head, int x, int y) { sortList(head); //先将链表排序 Node *p = head; while(p != NULL && p->data < x) { //找到第一个值大于等于x的节点 p = p->next; } while(p != NULL && p->data <= y) { //删除值在[x,y]范围内的节点 deleteNode(head, getIndexByValue(head, p->data)); p = p->next; } }

//销毁链表 void destroyList(Node *head) { Node *p = head; while(p != NULL) { Node *q = p->next; free(p); p = q; } }