C语言数据结构（第三站）——串串一样的单链表

发布于：2022-10-29 ⋅ 阅读:(322) ⋅ 点赞:(0)

文章目录


一、list.h

1、引用库函数

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

2、枚举选择项

enum Option
{
	EXIT,
	push_back,
	push_front,
	show_list,
	pop_back,
	pop_front,
	insert_val,
	find,
	length,
	delete_val,
	sort,
	resver,
	clear,
	destroy
};

3、用结构体构造单链表

a、单链表的构造

typedef struct Node
{
	ElemType data;//数据域
	struct Node* next;指针域
}Node;

b、对单链表的管理

typedef struct List
{
	Node* first;//让其始终指向头结点
	Node* last;//让其始终指向尾结点
	int size;//记录结点个数
}List;

4、函数声明

void InitList(List* list);
void PushBack(List* list, ElemType x);
void PushFront(List* list, ElemType x);
void ShowList(List* list);
void PopBack(List* list);
void PopFront(List* list);
void InsertPos(List* list, ElemType x);
Node* Find(List* list, ElemType key);
void Length(List* list);
void DeletePos(List* list, ElemType val);
void Sort(List* list);
void Resver(List* list);
void Clear(List* list);
void Destroy(List* list);

5、其他

#define ElemType int//进行宏定义，即：凡是用到ElemType的地方都用int代替

二、Main_list.c

1、定义单链表

List mylist;//定义一个单链表

2、选择系统

void menu()
{
	puts("**********************************************************");
	puts("*** 1、尾插        2、头插        3、显示    4、尾删   ***");
	puts("*** 5、头删        6、按位置插入  7、查找    8、求长度 ***");
	puts("*** 9、按位置删除  10、排序       11、逆置   12、清除  ***");
	puts("*** 13、销毁                                 0、退出   ***");
	puts("**********************************************************");
	printf("请选择:> ");
}

void select()
{
	int input = 0;
	ElemType Item;
	while (1)
	{
		system("cls");
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case push_back:printf("请输入要插入的数据（-1）结束:> ");
			while (scanf("%d", &Item), Item != -1)
			{
				PushBack(&mylist, Item);
			}
			break;
		case push_front:printf("请输入要插入的数据（-1）结束:> ");
			while (scanf("%d", &Item), Item != -1)
			{
				PushFront(&mylist, Item);
			}
			break;
		case show_list:ShowList(&mylist);
			break;
		case pop_back:PopBack(&mylist);
			break;
		case pop_front:PopFront(&mylist);
			break;
		case insert_pos:printf("请输入要插入的数据;> ");
			scanf("%d", &Item);
			InsertPos(&mylist, Item);
			break;
		case find:printf("请输入你要查找的数据;> ");
			scanf("%d", &Item);
			Find(&mylist,Item);
			break;
		case length:Length(&mylist);
			break;
		case delete_pos:printf("请输入要删除的数据;> ");
			scanf("%d", &Item);
			DeletePos(&mylist, Item);
			break;
		case sort:Sort(&mylist);
			break;
		case resver:Resver(&mylist);
			break;
		case clear:Clear(&mylist);
			break;
		case destroy:Destroy(&mylist);
			break;
		case EXIT:puts("即将退出！"); system("pause"); Destroy(&mylist); exit(0);
			break;
		default:puts("选择有误，请重试！"); system("pause");
			break;
		}
	}
}

三、Fun_list.c

1、初始化

建立一个头结点，是first指针、last指针都指向头结点！

未命名表单.png

void InitList(List* list)
{
	list->first = list->last = (Node*)malloc(sizeof(Node));
	assert(list->first != NULL);
	list->first->next = NULL;
	list->size = 0;
}

2、尾插

只需更改last的指向即可！

未命名表单.png

void PushBack(List* list, ElemType x)
{
	//给插入的数据开辟一个空间
	Node* s = (Node*)malloc(sizeof(Node));//申请一个插入结点的空间
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
//尾插
	list->last->next = s;//连接前一个结点
	list->last = s;//让last始终指向最后一个结点
	list->size++;
}

3、头插

注意：若为空表，则头插需要改变尾指针的指向！！

未命名表单.png
未命名表单.png

void PushFront(List* list, ElemType x)
{
	Node* s = (Node*)malloc(sizeof(Node));//申请一个插入结点的空间
	assert(s != NULL);
	s->data = x;
	s->next = list->first->next;
	list->first->next = s;
	if (list->size == 0)//如果表中无结点，则插入需改尾指针last的指向
	{
		list->last = s;
	}
	list->size++;
}

4、显示

void ShowList(List* list)
{
	if (list->size == 0)
	{
		puts("链表为空！");
		system("pause");
		return;
	}
	Node* p = list->first->next;//将第一个结点的值赋给p
	while (p != NULL)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("NULL\n");
	system("pause");
}

5、尾删

操作方法：只需将尾指针的指向前一个结点，释放掉最后一个结点即可！

void PopBack(List* list)
{
	if (list->size==0)
	{
		puts("链表为空，无法删除！");
		system("pause");
		return;
	}
	Node* p = list->first;
	while (p->next != list->last)//寻找尾结点的前驱
		p = p->next;
	free(list->last);//找到后将其释放
	list->last = p;//让尾指针指向前驱
	list->last->next = NULL;
	list->size--;
}

6、头删

操作步骤：将头结点的指针域指向它的下下个结点的地址，再释放掉头结点的下一个结点！
注意：链表只有头结点和尾结点的情况（即：只有两个结点）——此时应改变尾指针的指向！

未命名表单.png
未命名表单.png

void PopFront(List* list)
{
	if (list->size == 0)
	{
		puts("链表为空，无法删除！");
		system("pause");
		return;
	}
	Node* p = list->first->next;
	list->first->next = p->next;//让头结点的指针域指向它的下下个结点
	free(p);
	p = NULL;
	if (list->size == 1)//判断是否删除的是最后一个结点
	{
		list->last = list->first;
	}
	list->size--;
}

7、按位置插入

a、查找删除位置的前一个结点

Node* query(List* list,int i)
{
	int n = 0;
	Node* p = list->first;
	for (n = 1; n <= i; n++)
	{
		p = p->next;
	}
	return p;
}

b、插入操作

void InsertPos(List* list, ElemType x)
{
	int pos;
	Node* node = (Node*)malloc(sizeof(Node));//申请一个插入结点的空间
	assert(node != NULL);
	node->data = x;
	printf("请输入你要插入的位置:> ");
	scanf("%d", &pos);
	//判断插入位置的合法性
	//pos小于1或者pos大于了链表长度，则不合法
	//但要排出pos=1并且链表为空时的情况
	if (pos == 1 && list->size==0)
	{
		node->next = list->first->next;
		list->first->next = node;
		list->last = node;
		list->size++;
		return;
	}
	if (pos<1 || pos>list->size)
	{
		puts("插入位置不合法！");
		system("pause");
		return;
	}
	Node* p = query(list,pos - 1);
	node->next = p->next;
	p->next = node;
	list->size++;
}

8、查找

void Find(List* list, ElemType key)
{
	Node* p = list->first->next;
	while (p != NULL && p->data != key)//两者顺序不能颠倒
	{
		p = p->next;
	}
	if (p == NULL)
	{
		puts("要查找的数据在链表中不存在！");
		system("pause");
		return;
	}
	printf("查找结果%d存在\n", p->data);
	system("pause");
}

9、求长度

void Length(List* list)
{
	printf("链表长度为：%d\n", list->size);
	system("pause");
}

10、按位置删除

此处我们用另一种方法实现删除！

未命名表单.png

void DeletePos(List* list, ElemType val)
{
	Node* p = Find(list, val);
	if (p == NULL)
	{
		puts("无法删除！");
		system("pause");
		return;
	}
	//此处不再寻找删除位置的前驱结点
	//采用把删除结点的下一个结点的数据复制到删除结点中
	//再释放掉删除结点的下一结点
	if (p == list->last)//排出掉删除的是最后一个结点的情况
	{
		PopBack(list);
	}
	else
	{
		Node* q = p->next;//保存删除位置的下一个结点地址
		p->data = q->data;
		p->next = q->next;
		free(q);
		q = NULL;
		list->size--;
	}
}

11、排序

void Sort(List* list)
{
	if (list->size == 0 || list->size == 1)
		return;
	Node* s = list->first->next;
	Node* q = s->next;
	//断开链表
	list->last = s;
	list->last->next = NULL;
	//排序
	while (q != NULL)
	{
		s = q;
		q = q->next;
		Node* p = list->first;
		while (p->next != NULL && p->next->data < s->data)
		{
			p = p->next;
		}
		if (p->next == NULL)
		{
			list->last = s;
		}
		s->next = p->next;
		p->next = s;
	}
}

12、逆置

void Resver(List* list)
{
	if (list->size == 0 || list->size == 1)
		return;
	Node* s = list->first->next;
	Node* q = s->next;
	//断开链表
	list->last = s;
	list->last->next = NULL;
	while (q != NULL)
	{
		s = q;
		q = q->next;
		s->next = list->first->next;
		list->first->next = s;
	}
}

13、清除

void Clear(List* list)
{
	if (list->size == 0)
		return;
	Node* p = list->first->next;
	while (p != NULL)
	{
		list->first->next = p->next;
		free(p);
		p = list->first->next;
	}
	list->last = list->first;
	list->size = 0;
}

14、销毁

void Destroy(List* list)
{
	Clear(list);
	free(list->first);
	list->first = list->last = NULL;
}

15、改进

a、申请结点的改进

Node* BuyNode(ElemType x)
{
	Node* s = (Node*)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	return s;
}

b、插入操作的改进

It begin(List* list)
{
	return list->first->next;
}
It end(List* list)
{
	return list->last->next;
}
void Insert(List* list, It pos, ElemType x)
{
	Node* p = list->first;
	while (p->next != pos)
	{
		p = p->next;
	}
	Node* s = BuyNode(x);
	s->next = p->next;
	p->next = s;
	if (pos == NULL)
	{
		list->last = s;
	}
	list->size++;
}

c、头文件中需要添加的声明

Node* BuyNode(ElemType x);
typedef Node* It;
It begin(List* list);
It end(List* list);
void Insert(List* list, It pos, ElemType x);

d、查找方法的改进

Node* Find(List* list, ElemType key)//可更改返回值为查找元素的前驱结点——自行实现
{
	Node* p = list->first->next;
	if (p->data == key)
	{
		printf("查找结果p的前驱结点数据为头结点\n");
		system("pause");
		return p;
	}
	while (p != NULL && p->data != key)//两者顺序不能颠倒
	{
		if (p->next->data == key)
		{
			printf("查找结果p的前驱结点数据为%d\n", p->data);
			system("pause");
			return p;
		}
		p = p->next;
	}
	if (p == NULL)
	{
		puts("要查找的数据在链表中不存在！");
		system("pause");
		return p;
	}
	return p;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布