脚本宝典收集整理的这篇文章主要介绍了【数据结构学习笔记】二、线性表---链表篇(2),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
注意: 1.从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续 2.现实中的结点一般都是从堆上申请出来的 3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
单向 | 双向 |
---|---|
带头 | 不带头 |
---|---|
循环 | 非循环 |
---|---|
单向与双向、循环和非循环的区别
带头结点和不带头结点的区别 三个维度,总共有 2*2*2 = 8 种结构,其中最常用的为以下两种结构1.无头单向非循环链表∶结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 ⒉.带头双向循环链表︰结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势实现反而简单了,后面我们代码实现了就知道了。
头文件:SList.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
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;
}
以上是脚本宝典为你收集整理的【数据结构学习笔记】二、线性表---链表篇(2)全部内容,希望文章能够帮你解决【数据结构学习笔记】二、线性表---链表篇(2)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。