数据结构-单链表操作实践

数据结构-单链表操作实践

1. 编写函数，实现输入一组元素，建立一个带头结点的单链表

#include <iostream>
#include <malloc.h>
using namespace std;
/**
 * 定义结点类型结构体，有一个data域和一个next域
 */
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;

/**
 * 初始化，生成带有头结点的单链表
 * @param L 引用类型，头指针
 */
void InitLinkList(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	if (L) {   //内存分配成功
		L->next = NULL;
	}
}

/**
 * 尾插法建立单链表
 * @param L 链表L
 * @param n 需要插入的元素的个数
 */
void RailInsert_LinkList(LinkList& L, int n) {
	LNode* s, * r;  //s用于指向新申请的节点空间，r用于始终指向尾结点
	r = L;   //r初始指向头结点
	for (int i = 1; i <= n; ++i) {
		s = (LNode*)malloc(sizeof(LNode));
		if (s)
		{
			cin >> s->data;
			/**
			 * 尾插法的关键步骤
			 */
			r->next = s;  //直接让r的next指向新结点s
			r = s;        //再让r重新指向当前的尾结点
		}

	}
	r->next = NULL;   //最后，将r的next置空
}
/**
 * 按顺序输出单链表中元素的值
 * @param L 单链表的头指针
 */
void Print_LinkList(LinkList L) {
	LNode* p = L->next;
	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
int main() {
	LinkList L;
	InitLinkList(L);

	int n;

	cin >> n;
	RailInsert_LinkList(L, n);
	Print_LinkList(L);

	return 0;
}

2. 对该链表进行非递减排序

/**
 * 对链表非递减排序
 * @param L 链表L
 */
void Ascend_LinkList(LinkList& L) {
	LNode* p = L->next;
	LNode* q = p->next;
	int tmp;
	int flag=1;  // 标志
	while (flag) {
		flag = 0;  // 没有发生交换就退出
		while (q != NULL) {
			if (p->data < q->data) {  // 交换值
				tmp = p->data;
				p->data = q->data;
				q->data = tmp;
				flag = 1;
			}
			p = p->next;
			q = q->next;
		}
		p = L->next;
		q = p->next;
	}
}

cout << "非递减排序：";
Ascend_LinkList(L);
Print_LinkList(L);

3. 实现在非递减有序链表中删除值为x的结点

/**
 * 删除值为x的结点
 * @param L 链表L
 * @param x 要删除结点的值
 */
void DeleteNode_LinkList(LinkList& L, int x) {
	LNode* p = L;
	LNode* q = L->next;
	while (q != NULL) {
		if (q->data == x) {
			p->next = q->next;
			free(q);
			break;
		}
		p = p->next;
		q = q->next;
	}
	if (!q) {
		cout << "不存在值为" << x << "的结点" << endl;
	}
}

cout << "删除元素：";
int x;
cin >> x;
DeleteNode_LinkList(L, x);
Print_LinkList(L);

完整程序代码

#include <iostream>
#include <malloc.h>
using namespace std;
/**
 * 定义结点类型结构体，有一个data域和一个next域
 */
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;

/**
 * 初始化，生成带有头结点的单链表
 * @param L 引用类型，头指针
 */
void InitLinkList(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	if (L) {   //内存分配成功
		L->next = NULL;
	}
}

/**
 * 尾插法建立单链表
 * @param L 链表L
 * @param n 需要插入的元素的个数
 */
void RailInsert_LinkList(LinkList& L, int n) {
	LNode* s, * r;  //s用于指向新申请的节点空间，r用于始终指向尾结点
	r = L;   //r初始指向头结点
	for (int i = 1; i <= n; ++i) {
		s = (LNode*)malloc(sizeof(LNode));
		if (s)
		{
			cin >> s->data;
			/**
			 * 尾插法的关键步骤
			 */
			r->next = s;  //直接让r的next指向新结点s
			r = s;        //再让r重新指向当前的尾结点
		}

	}
	r->next = NULL;   //最后，将r的next置空
}


/**
 * 对链表非递减排序
 * @param L 链表L
 */
void Ascend_LinkList(LinkList& L) {
	LNode* p = L->next;
	LNode* q = p->next;
	int tmp;
	int flag=1;  // 标志
	while (flag) {
		flag = 0;  // 没有发生交换就退出
		while (q != NULL) {
			if (p->data < q->data) {  // 交换值
				tmp = p->data;
				p->data = q->data;
				q->data = tmp;
				flag = 1;
			}
			p = p->next;
			q = q->next;
		}
		p = L->next;
		q = p->next;
	}
}

/**
 * 删除值为x的结点
 * @param L 链表L
 * @param x 要删除结点的值
 */
void DeleteNode_LinkList(LinkList& L, int x) {
	LNode* p = L;
	LNode* q = L->next;
	while (q != NULL) {
		if (q->data == x) {
			p->next = q->next;
			free(q);
			break;
		}
		p = p->next;
		q = q->next;
	}
	if (!q) {
		cout << "不存在值为" << x << "的结点" << endl;
	}
}

/**
 * 按顺序输出单链表中元素的值
 * @param L 单链表的头指针
 */
void Print_LinkList(LinkList L) {
	LNode* p = L->next;
	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

int main() {
	LinkList L;
	InitLinkList(L);

	int n;

	cin >> n;
	RailInsert_LinkList(L, n);
	Print_LinkList(L);

	cout << "非递减排序：";
	Ascend_LinkList(L);
	Print_LinkList(L);

	cout << "删除元素：";
	int x;
	cin >> x;
	DeleteNode_LinkList(L, x);
	Print_LinkList(L);

	return 0;
}

创作不易，喜欢的话加个关注点个赞，谢谢谢谢谢谢！