数据结构实践基础题: 单链表操作

谁借莪１个温暖的怀抱￠ 2022-02-13 09:57 127阅读 0赞

看点：

1. 用户控制的数据长度（自定义）

2. while循环写的菜单函数

3. 单（循环）链表的建立

4. 求出最大值和次最大值的算法

5. 一次快速排序

//预编译命令：文件包含，宏定义
    #include<stdio.h>
    #include<malloc.h>
    #define LENGTH 100//自定义数组长度
    //数据类型
    typedef int DataType;
    typedef struct Node//单链表的结点的定义
    {
    	DataType data;
    	struct Node *next;
    }SLNode;
    //全局变量
    SLNode *head,*ptr;//定义头结点
    int max_value = 0, submax_value = 0, intermediate = 0;
    DataType *max_pointer, *submax_pointer;
    int select = 1;
    DataType a[LENGTH];
    int N;//自定义数组长度
    //菜单函数声明
    void menu();
    //功能函数声明
    void ListInitiate(SLNode **head);
    void Create(int i, DataType array[]);
    void Check();
    SLNode *Locate(DataType key);
    void GetMaxValue(DataType *max_pointer, DataType *submax_pointer);
    void sorting();
    int main()
    {
    	printf("请输入数组长度：\n");
    	scanf("%d",&N);
    	printf("请输入数组元素：\n");
    	for (int i = 0; i< N; i++)
    	{
    		scanf("%d", &a[i]);
    	}
    	ListInitiate(&head);
    	menu();
    	return 0;
    }
    //菜单函数实现
    void menu()
    {
    	while (select)
    	{
    		printf("————————单循环列表操作界面————————\n");
    		printf("————1. 创建函数            2. 查看链表————\n");
    		printf("————3. 查找函数            4. 返回最值————\n");
    		printf("————5. 排序函数            0. 退出程序————\n");
    		printf("请输入你的选择：\n");
    		scanf_s("%d", &select);
    		switch (select)
    		{
    		case 1:
    			for (int i = 0; i < N; i++)
    			{
    				Create(i, a);
    			}
    			printf("链表信息录入成功！\n");
    			break;
    		case 2:
    			Check();
    			break;
    		case 3:
    			printf("请输入想查找的值：\n");
    			int value;
    			scanf_s("%d", &value);
    			ptr = Locate(value);
    			if (ptr == NULL) {
    				printf("链表中没有所查找的数据。\n");
    			}
    			else printf("查找到的数据是：%d\n", ptr->data);
    			break;
    		case 4:
    			max_pointer = &max_value;
    			submax_pointer = &submax_value;
    			GetMaxValue(max_pointer, submax_pointer);
    			printf("数组中最大值：%d\n数组中次大值：%d\n", *max_pointer, *submax_pointer);
    			break;
    		case 5:
    			sorting();
    			Check();
    			break;
    		case 0: break;
    		default: printf("输入错误！请重新选择。\n");
    		}
    	}
    }
    //操作功能函数的实现（带头结点的单链表）
      //初始化函数（题目要求是循环单链表）
    void ListInitiate(SLNode **head)//head是一个指针，*head也是一个指针
    {
    	*head = (SLNode *)malloc(sizeof(SLNode));
    	(*head)->next = *head;
    }
    //创建单链表函数(插入法实现)
    void Create(int i, DataType array[])
    //在链表尾插入一个存放数据a[i]的结点，失败返回0
    {
    		SLNode *p, *q;//分别用于指向第i个结点和待插入的新结点
    		p = head;
    		while (p->next != head)//把指针P定位到指向第i-1个结点的位置
    		{
    			p = p->next;
    		}
    		q = (SLNode *)malloc(sizeof(SLNode));//用指针Q申请新结点
    		q->data = array[i];//新结点存放相应数组A中的元素
    		q->next = p->next;//Q指针的next域指向P指针的next域，即第i个结点
    		p->next = q;
    }
    //检查链表数据输入是否准确
    void Check()
    {
    	SLNode *p;
    	p = head;
    	printf("链表数据内容为：");
    	while (p->next != head)
    	{
    		p = p->next;
    		printf("%d ",p->data);
    	}
    	printf("\n");
    }
    //定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的第1个元素的结点指针；若找不到，则返回NULL；
    SLNode *Locate(DataType key)
    {
    	SLNode *p;
    	p = head;
    	while (p->next != head)
    	{
    		p = p->next;
    		if (p->data == key) break;
    	}
    	if (p->data == key) return p;
    	else return NULL;
    }
    //求出该链表中值最大和次大的元素值，最大和次大的元素值通过指针变量带回，函数不需要返回值
    void GetMaxValue(DataType *max_pointer, DataType *submax_pointer)
    {
    	SLNode *p;
    	p = head;
    	while (p->next != head)
    	{
    		p = p->next;
    		if (p->data > max_value)
    		{
    			intermediate = max_value;
    			max_value = p->data;
    		}
    		if (p->data > intermediate &&p->data < max_value)
    		{
    			intermediate = p->data;
    		}
    		if (p->data > submax_value && submax_value <= intermediate)
    		{
    			submax_value = intermediate;
    		}
    	}
    	*max_pointer = max_value;
    	*submax_pointer = submax_value;
    
    }
    //将链表中所有值比 key(值 key 通过形参传入)小的结点作为值为 key 的结
    //点前驱，所有值比 key 大的结点作为值为 key 的结点后继，并尽量保持原有结点
    //之间的顺序，要求该算法的时间复杂度为 O(m)
    void sorting()
    {
    	SLNode *k, *p, *front, *rear, *L;
    	DataType key;
    	front = head;
    	p = head->next;
    	printf("请输入key：");
    	scanf_s("%d", &key);
    	L = Locate(key);
    	k = L;
    	rear = k;
    	while (p != head)
    	{
    		if (front->next != k)
    		{
    			if (p->data > k->data)
    			{
    				front->next = front->next->next;//断开结点与链表的连接
    				//插入，让p指向的结点成为key结点的后继节点
    				p->next = rear->next;
    				rear->next = p;
    				rear = rear->next;
    				p = front->next;//p重复利用
    			}
    			else
    			{
    				p = p->next;//指向下一个
    				front = front->next;
    			}
    		}
    		else
    		{
    			p = rear->next;
    			if (p->data < k->data)
    			{
    				rear->next = rear->next->next;
    				p->next = front->next;
    				front->next = p;
    				front = front->next;
    				p = rear->next;
    			}
    			else
    			{
    				p = p->next;
    				rear = rear->next;
    			}
    		}
    	}
    }