数据结构单链表定义及例题(上)

本文简要的介绍了单链表的定义,以及单链表的头插法和尾插法的实现

一、单链表数据结构的定义

二、头插法建立单链表(带头节点)

三、尾插法建立单链表(带头节点)

四、打印单链表

五、测试及全部代码

总结

---

前言

单链表是学习,以及考研无论是408还是自命题都是很重要的,单链表只要深入理解了,这部分的题会没有问题的.

一、单链表数据结构的定义

//单链表的数据结构定义
typedef struct LNode {
	ElemType data;//数据
	struct LNode* next;//下一个节点
}LNode,*Linklist;

二、头插法建立单链表(带头节点)

这里先说一下头节点

头节点:就是建立一个不存储数据的节点当链表为空时,此时就有一个结点,此节点方便插入和删除操作,因为可以不用修改指向链表的指针.

头插法,就是在表头插入元素,这样使得数据在链表中数据的顺序,与插入的顺序相反,故头插法可以将链表逆置.

void CreateLinklist1(Linklist &L,int arr[],int arrlength) {
	L = (LNode*)malloc(sizeof(LNode));//申请一个头节点
	assert(L);
	L->next = NULL;
	for (int i = 0; i < arrlength; i++) {
		LNode*pNode = (LNode*)malloc(sizeof(LNode));
		assert(pNode);
		pNode->data = arr[i];
		pNode->next = L->next;//指向头节点的下一个节点
		L->next = pNode;//更改头节点的下一个节点为插入节点
	}
}

使用数组向链表中插入元素.

三、尾插法建立单链表(带头节点)

尾插法,就是在链表的尾部插入元素,但链表的指针只指向头节点,所以只能遍历链表找到最后一个节点,但这样太麻烦,所以我们干脆定义一个指针指向尾节点就可以了.

//使用尾插法建立单链表
void CreateLinklist2(Linklist& L,int arr[],int arrlength) {
	L = (LNode*)malloc(sizeof(LNode));//申请一个头节点
	assert(L);
	L->next = NULL;
	LNode* pTail = L;
	for (int i = 0; i < arrlength; i++) {
		LNode* pNode = (LNode*)malloc(sizeof(LNode));
		assert(pNode);
		pNode->data = arr[i];//元素赋值
		pNode->next = pTail->next;//指向尾节点的下一个节点,可以=NULL
		pTail->next = pNode;//尾节点的指针指向当前节点
		pTail = pNode;//变化尾指针
	}
}

四、打印单链表

//打印单链表函数
void print(Linklist L) {
	LNode* p = L->next;
	while (NULL != p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

五、测试及全部代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
typedef int ElemType;

//单链表的数据结构定义
typedef struct LNode {
	ElemType data;//数据
	struct LNode* next;//下一个节点
}LNode,*Linklist;
//使用头插法建立单链表
void CreateLinklist1(Linklist &L,int arr[],int arrlength) {
	L = (LNode*)malloc(sizeof(LNode));//申请一个头节点
	assert(L);
	L->next = NULL;
	for (int i = 0; i < arrlength; i++) {
		LNode*pNode = (LNode*)malloc(sizeof(LNode));
		assert(pNode);
		pNode->data = arr[i];
		pNode->next = L->next;
		L->next = pNode;
	}
}
//使用尾插法建立单链表
void CreateLinklist2(Linklist& L,int arr[],int arrlength) {
	L = (LNode*)malloc(sizeof(LNode));//申请一个头节点
	assert(L);
	L->next = NULL;
	LNode* pTail = L;
	for (int i = 0; i < arrlength; i++) {
		LNode* pNode = (LNode*)malloc(sizeof(LNode));
		assert(pNode);
		pNode->data = arr[i];
		pNode->next = pTail->next;
		pTail->next = pNode;
		pTail = pNode;
	}
}
//打印单链表函数
void print(Linklist L) {
	LNode* p = L->next;
	while (NULL != p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

int main() {
	Linklist La=NULL;
	Linklist Lb = NULL;
	int arr[20] = { 0 };
	int arrlength = 0;
	int enterNum = 999999;
	printf("请输入序列S:");
	while (scanf("%d", &enterNum) && enterNum < 999999) {//999999表示输入结束标志
		arr[arrlength++] = enterNum;
	}
	//使用头插法建立单链表
	CreateLinklist1(La, arr, arrlength);
	//使用尾插法建立单链表
	CreateLinklist2(Lb, arr, arrlength);
	printf("输出头插法链中序列L:");
	print(La);
	printf("输出尾插法链中序列L:");
	print(Lb);
	return 0;
}

?输入加输出结果:

---

总结

单链表的数据结构定义,以及采用头插法和尾插法建立单链表,最后输出测试,这部分一定好好理解,对后面的练习会更有帮助.