一个小脑袋

一个小脑袋

关注
发信
关注(28)粉丝(399)

[数据结构]——单链表超详细总结

目录：

链表是个优秀的结构，没有容量概念，可以在任意位置增加删除数据，这个博客，我准备花大量篇幅去总结链表（特别是单链表），同时也总结一下顺序表（顺序表和我们以前写的通讯录动态版类似，一般采用数组存储的方法，在数组上完成数据的增删查改）

一、线性表的概念

线性表的定义：由n个数据元素组成具有相同特性的有限序列。
常见的线性表：顺序表、链表、栈、队列、字符串等等。
线性表的概念：线性表在逻辑上是线性结构，也就是说它是一条直线，它的物理结构并不一定是连续的，线性表在物理上存储时，通常以数组和链表的形式存储。

二、顺序表

顺序表的定义：
顺序表是一段物理地址连续的存储单元，是一种用来依次存储数据的线性结构。
[数据结构]——单链表超详细总结-LMLPHP
1.静态顺序表：使用定常数组存储元素

#define N 7//方便改变数组大小
typedef int SLDatatype;
typedef struct SLD
{
SLDatatype arr[N];//定长数组
size_t size;//有效数据的个数
}SeqList;//顺序表

2.动态顺序表：使用动态开辟的数组存储元素（空间不够就可以扩容）

typedef int SLDatatype;
typedef struct SLD
{
SLDatatype* p;//指向动态开辟的数组
size_t size;//有效数据的个数
size_t capicity;//表示容量空间的大小
}SeqList;//顺序表

三、链表

3.1 链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
注意:
链式结构在逻辑上是连续的，但是在物理上不一定连续。
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

3.2 链表的分类

链表的结构非常多，结合起来有8种：
1、单向或者双向
[数据结构]——单链表超详细总结-LMLPHP
2、带头或者不带头
[数据结构]——单链表超详细总结-LMLPHP
3、循环或者不循环
[数据结构]——单链表超详细总结-LMLPHP
实际中常用的两种结构是：

  1. 无头单向非循环链表 ：
    结构简单，一般不会单独存数据。其他数据的子结构，如哈希桶、图的领接表等等。
  2. 带头双向循环链表：
    结构最复杂，一般可以单独存数据。实际中使用的链表数据结构，都是带头双向循环链表。

3.3 无头+单向+非循环链表的实现

头文件里的函数声明

// slist.h
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);

下面将是各个函数的实现

// slist.c
#include "SList.h"
//动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
//在堆上开辟一个存放指针的变量，并给它初始化
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	node->data = x;
	node->next = NULL;
	return node;//返回指针
}
//单链表打印
void SListPrint(SListNode* plist)
{
//定义一个指针，指针指向头指针
	SListNode* cur = plist;
	//遍历指针，不是空就循环
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//cur指向空
	printf("NULL\n");
}
//单链表尾插一个数据
void SListPushBack(SListNode** pplist, SLTDateType x)
{
//开辟一个新结点
	SListNode* newnode = BuySListNode(x);
	//如果头指针指向的是空就让它指向这个新结点
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else//如果头指针指向的不是空
	{
	//创建一个尾指针
		SListNode* tail = *pplist;
		//尾指针不在尾部，遍历单链表，让尾指针指向链表的最后结点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
//把开辟的新结点尾插到尾指针结点的下一个结点
		tail->next = newnode;
	}
}
//单链表尾删
void SListPopBack(SListNode** pplist)
{
//定义两个指针
	SListNode* prev = NULL;//当前位置的指针
	SListNode* tail = *pplist;//尾结点的指针
	// 1.空、只有一个节点
	// 2.两个及以上的节点
	if (tail == NULL || tail->next == NULL)
	{
//给空间释放
		free(tail);
		*pplist = NULL;
	}
	else
	{
	//遍历链表，找到尾指针
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;
//让最后一个结点指向空
		prev->next = NULL;
	}
}

//单链表头插法
void SListPushFront(SListNode** pplist, SLTDateType x)
{
//这个指针是空就报错
	assert(pplist);
	// 1.空
	// 2.非空
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)//pplist指针指向的是空
	{
		*pplist = newnode;
	}
	else
	{
	//在*pplist指针指向的那个结点前面头插一个结点
		newnode->next = *pplist;
		//*pplist指针重新指向头结点
		*pplist = newnode;
	}
}
//单链表头删
void SListPopFront(SListNode** pplist)
{
	// 1.空
	// 2.一个
	// 3.两个及以上
	SListNode* first = *pplist;//定义一个头指针，它为空就返回，
	if (first == NULL)
	{
		return;
	}
	else if (first->next == NULL)//只有一个结点，就释放空间，然后置空
	{
		free(first);
		*pplist = NULL;
	}
	else
	{
	//两个以上结点
		SListNode* next = first->next;//把头指针的下一个结点位置存起来
		free(first);//释放头指针
		*pplist = next;//让首指针重新指向头指针
	}
}
 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}

	return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)//用单链表查找，找到值x的位置，返回的指针给pos
{
	assert(pos);
	SListNode* next = pos->next;//next指针存放pos之后的节点
	SListNode* newnode = BuySListNode(x);//开辟一个新结点
	pos->next = newnode;//在pos后面插入新开辟的结点
	newnode->next = next;//让新结点连接上next指向的那个结点
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)//用单链表查找，找到值x的位置，返回的指针给pos
{
	assert(pos);
	// pos next nextnext
	SListNode* next = pos->next;

	if (next != NULL)
	{
		SListNode* nextnext = next->next;
		free(next);
		pos->next = nextnext;
	}
}
// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
    
    SListNode* cur = *pplist;
    while (cur)
    {
        *pplist = cur->next;
        free(cur);
        cur = *pplist;
    }
}

3.4 带头+双向+循环链表的实现

头文件里的函数声明

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
//创建新结点
 ListNode* ListNodes(LTDataType x);
//双向链表初始化
 ListNode* ListInit();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
//求链表有多少数据
int listsize(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

函数的定义实现

// 创建新节点
ListNode* ListNodes(LTDataType x)
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    head->data = x;
    head->next = NULL;
    head->prev = NULL;
    return head;
}
//链表初始化
ListNode* ListInit()
{
    ListNode* phead = ListNodes(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* newnode = ListNodes(x);//创建一个新节点
    ListNode* tail = phead->prev;
    newnode->data = x;
    //双向链表尾插
    tail->next = newnode;
    newnode->next = phead;
    newnode->prev = tail;
    phead->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
    assert(phead);
    assert(phead->next != NULL);
    ListNode* tail = phead->prev;
    ListNode* tailPrev = tail->prev;
    free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
    ListNode* next = phead->next;
    ListNode* newnode = ListNodes(x);
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = next;
    next->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* phead)
{
    assert(phead);
    assert(phead->next != NULL);
    ListNode* node = phead->next;
    phead->next = node->next;
    node->next->prev = phead;
    free(node);
}
//求链表有多少数据
int listsize(ListNode* phead)
{
    int  size = 0;
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        size++;
        cur = cur->next;
    }
    return size;
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
    ListNode* newnode = ListNodes(x);
    ListNode* prevnode = pos->prev;
    prevnode->next = newnode;
    newnode->prev = prevnode;
    newnode->next = pos;
    pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* nodeprev = pos->prev;
    ListNode* nodenext = pos->next;
    free(pos);
    nodeprev->next = nodenext;
    nodenext->prev = nodeprev;
}
// 双向链表打印
void ListPrint(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
}
// 双向链表销毁
void ListDestory(ListNode* phead)
{
    //断言指针指针不为NULL
    assert(phead);
    ListNode* cur = phead;//定义一个指针
    //断开循环链表
    phead->prev->next = NULL;

    while (cur)
    {
        ListNode* Next = cur->next;
        free(cur);
        cur = Next;
    }
}

四、顺序表和链表的区别和联系

[数据结构]——单链表超详细总结-LMLPHP
补充： 高速缓存利用率
先要对存储器的层次结构有一定了解
如图：
[数据结构]——单链表超详细总结-LMLPHP
数据是存在内存中的，CPU要访问数据，它不会去内存直接访问数据。看数据在不在缓存，在缓存，数据就命中（cpu访问数据时，数据恰好在缓存里），不在缓存，访问不命中（cpu访问数据，不会把4个字节加载到缓存，它会把一长段的数据加载到缓存）

注意：CPU访问数据第一次不命中，第二次一定命中

10-15 06:59
Powered by LMLPHP ©2024 一个小脑袋 0.009842