2-4尾插建立单链表，C语言输出

77 阅读 0 评论 51 点赞

我是靠谱客的博主老实火车，最近开发中收集的这篇文章主要介绍2-4尾插建立单链表，C语言输出，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文讲述了使用尾插法建立单链表，并用C语言输出整个单链表的值。第二节使用该算法用链表实现了直接插入排序

1.尾插建立单链表，C语言输出。其中L表示头结点，L->next表示第一个元素

#include<stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;

typedef struct LNode {//单链表定义
	int data;
	struct LNode* next;
}LNode, * LinkList;

bool InitList(LinkList& L) {//初始化
	L = (LNode*)malloc(sizeof(LNode));//头指针L指向无数据的头结点
	if (L == NULL)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点的next指针域设为NULL
	return true;
}

LinkList List_TailInsert(LinkList& L) {//尾插法建立
	LNode* s;//工作指针
	LNode* r = L;//r做为表尾指针
	int x, i;
	cout << "单链表元素个数：";
	cin >> i;//插入i个元素
	cout << "请输入单链表元素：";
	scanf_s("%d", &x);
	while (1) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		i--;
		if (i == 0)//输完i个，跳出
			break;
		scanf_s("%d", &x);

	}
	r->next = NULL;
	return L;
}

int main() {
	LinkList L;//创建单链表L
	InitList(L);//初始化
	List_TailInsert(L);
	while (L->next) {
		printf("%d ", L->next->data);
		L = L->next;
	}
}

运行结果
在这里插入图片描述

2.用链表实现直接插入排序【个人想法，非最优】

#include<stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;

bool InitList(LinkList& L) {//初始化
	L = (LNode*)malloc(sizeof(LNode));//头指针L指向无数据的头结点
	if (L == NULL)//内存不足，分配失败
		return false;
	L->next = NULL;//头结点的next指针域设为NULL
	return true;
}
LinkList List_TailInsert(LinkList& L) {
	LNode* s;//工作指针
	LNode* r = L;//r做为表尾指针
	int x;
	int i = 5;
	scanf_s("%d", &x);
	while (1) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		i--;
		if (i == 0)
			break;
		scanf_s("%d", &x);
		
	}
	r->next = NULL;
	return L;
}

LinkList Sort(LinkList& L) {//排序过程
	if (L) {
		LNode* pre = L->next, * p = L->next->next;//工作指针p，前驱pre
		for (; p; p = p->next, pre = pre->next) {
			LNode* pres = L, * s = L->next;//s从头遍历，找到合适位置插入;pres是s的前驱
			for (; s != p; s=s->next,pres=pres->next) {
				if (p->data < s->data) {
					pre->next = p->next;
					p->next = pres->next;
					pres->next = p;

					pre = p;//pre和p先往前拉一位，此处拉pre
					p = pre->next->next;//p先去压S
				}
			}
			p = pre->next;//此处拉p
		}//因for循环p和pre同时后移
	}
	return L;
}

int main() {
	LinkList L;//创建单链表L
	InitList(L);//初始化
	List_TailInsert(L);
	Sort(L);//排序
	while (L->next) {
		printf("%d ", L->next->data);
		L = L->next;
	}
}