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

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;
}