【数据结构学习笔记】二、线性表---链表篇(2)

【数据结构学习笔记】二、线性表---链表篇(2),第1张

【数据结构学习笔记】二、线性表---链表篇(2)


文章目录
    • 链表概念:
    • 链表分类:
    • 单链表的实现:


链表概念:

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

注意:
1.从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续


链表分类: 单向双向 带头不带头 循环非循环

单向与双向、循环和非循环的区别

带头结点和不带头结点的区别

三个维度,总共有 2*2*2 = 8 种结构,其中最常用的为以下两种结构

1.无头单向非循环链表∶结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
⒉.带头双向循环链表︰结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势实现反而简单了,后面我们代码实现了就知道了。


单链表的实现:

头文件:SList.h

#pragma once
#include
#include
#include
#include
typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SListNode;

//申请结点
SListNode* CreateSListNode(SLTDataType x);
//打印
void SListPrint(SListNode* pList);
//判空
bool IsEmpty(SListNode* pList);
//求长
int SListLength(SListNode* pList);
//按值查找
SListNode* SListFindByVal(SListNode* pList,SLTDataType x);
//按位置查找
SListNode* SListFindByPos(SListNode* pList, int pos);
//修改
void SListUpdate(SListNode* Node);

//创建
void SListInit(SListNode** pphead);
//销毁
void SListDestory(SListNode** pphead);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
//头删
void SListPopFront(SListNode** pphead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//任意位置插入
void SListInsertAfter(SListNode** pphead, int pos, SLTDataType x);
//任意位置删除
void SListEraseAfter(SListNode** pphead, int pos);


源文件:SList.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include"SList.h"
//初始化
void SListInit(SListNode** pphead) {
	*pphead = NULL;
}
//销毁
void SListDestory(SListNode** pphead) {
	SListNode* cur = *pphead;
	while (cur) {
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
//申请结点
SListNode* CreateSListNode(SLTDataType x) {
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	if (node == NULL) {
		printf("malloc fail!n");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
}
//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {
	assert(pphead);
	SListNode* newnode = CreateSListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//头删
void SListPopFront(SListNode** pphead) {
	assert(pphead);
	if (IsEmpty(*pphead)) {
		printf("SList is empty ,PopFront fail!n");
		return 0;
	}
	SListNode* head = *pphead;
	*pphead = (*pphead)->next;
	free(head);
}
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x) {
	assert(pphead);
	//找尾结点
	SListNode* tail = *pphead;
	while (tail && tail->next) {
		tail = tail->next;
	}
	//创建新结点
	SListNode* newnode = CreateSListNode(x);
	if (tail == NULL) {
		*pphead = newnode;
	}
	else {
		tail->next = newnode;
	}
}
//尾删
void SListPopBack(SListNode** pphead) {
	assert(pphead);
	if (IsEmpty(*pphead)) {
		printf("SList is empty ,popBack failed!n");
		return 0;
	}
	SListNode* prev = *pphead;
	SListNode* tail = prev->next;
	if (tail == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		while (tail->next) {
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
//任意位置插入
void SListInsertAfter(SListNode** pphead, int pos, SLTDataType x) {
	assert(pphead);
	SListNode* newnode = CreateSListNode(x);
	SListNode* insert = SListFindByPos(*pphead, pos);
	if (insert) {
		newnode->next = insert->next;
		insert->next = newnode;
	}
	else
	{
		*pphead = newnode;
	}
}
//任意位置删除
void SListEraseAfter(SListNode** pphead, int pos) {
	assert(pphead);
	SListNode* erase = SListFindByPos(*pphead, pos);
	if (erase) {
		SListNode* next = erase->next;
		erase->next = next->next;
		free(next);;
	}
	else
		printf("SList is empty,Erase fail!n");
}
//打印
void SListPrint(SListNode* pList) {
	SListNode* cur = pList;
	while (cur) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}
//判空
bool IsEmpty(SListNode* pList) {
	if (pList == NULL)
		return 1;
	return 0;
}
//求长
int SListLength(SListNode* pList) {
	int length = 0;
	SListNode* cur = pList;
	while (cur) {
		length++;
		cur = cur->next;
	}
}
//按值查找
SListNode* SListFindByVal(SListNode* pList, SLTDataType x);
//按位置查找
SListNode* SListFindByPos(SListNode* pList, int pos) {
	SListNode* cur = pList;
	int length = SListLength(pList);
	if (pos < 0 || pos > length) {
		printf("The position to insert is wrong!n");
		return 0;
	}
	while (pos > 0) {
		cur = cur->next;
		pos--;
	}
	return cur;
}
//修改
void SListUpdate(SListNode* Node);

测试函数:Test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include"SList.h"
void TestSList1() {
	SListNode* node1 = (SListNode*)malloc(sizeof(SListNode));
	node1->data = 1;
	SListNode* node2 = (SListNode*)malloc(sizeof(SListNode));
	node2->data = 2;
	SListNode* node3 = (SListNode*)malloc(sizeof(SListNode));
	node3->data = 3;
	SListNode* node4 = (SListNode*)malloc(sizeof(SListNode));
	node4->data = 4;
	SListNode* node5 = (SListNode*)malloc(sizeof(SListNode));
	node5->data = 5;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = node5;
	node5->next = NULL;
	SListPrint(node1);

}
void TestSList2() {
	SListNode* pList = NULL;
	SListPushBack(&pList, 111);
	SListPushBack(&pList, 222);
	SListPushBack(&pList, 333);
	SListPushBack(&pList, 444);
	SListPushBack(&pList, 555);
	SListPrint(pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPrint(pList);
}
void TestSList3() {
	SListNode* pList = NULL;
	SListPushFront(&pList, 99);
	SListPushFront(&pList, 88);
	SListPushFront(&pList, 77);
	SListPushFront(&pList, 66);
	SListPushFront(&pList, 55);
	SListPrint(pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPrint(pList);

	SListInsertAfter(&pList, 0, 1);
	SListInsertAfter(&pList, 0, 2);
	SListInsertAfter(&pList, 0, 3);
	SListInsertAfter(&pList, 0, 4);
	SListInsertAfter(&pList, 0, 5);
	SListPrint(pList);

	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListPrint(pList);

	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListEraseAfter(&pList, 0);
	SListPrint(pList);


}
int main()
{
	//TestSList1();
	//TestSList2();
	TestSList3();
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5698292.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存