单链表详解

xiaoxiao2021-03-01  19

一、简介

单链表:是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。(每个结点       只有一个链域的链表称为单链表)

1)链表中的数据是以结点来表示

2)每个结点的构成:元素(数据元素的映象(Node->data)) + 指针(指示后继元素存储位置(Node->next)),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

3)链接方式存储的线性表简称为链表(Linked List)。

链表的具体存储表示为:

1)用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)                 

2)链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))。 

链表的结构:

data域-->存放结点值的数据域 

next域-->存放 存放结点的直接后继的指针域

二、    单链表的多种操作

代码实现:

头文件:list.h

#pragma once //带头节点的单链表,以NULL结尾 typedef struct Node { int data; struct Node*next; }Node,*List;//List == Node* //初始化 void InitList(List plist); //头插,违背生活规律,尽量少用 bool Insert_head(List plist,int val); //尾插 bool Insert_tail(List plist,int val); //查找 Node* Search(List plist,int key); bool Delete(List plist,int key); int GetLength(List plist); bool IsEmpty(List plist); //清空数据 void Clear(List plist); //销毁链表 void Destroy(List plist); void Show(List plist);

功能实现:.cpp文件;

#include <stdio.h> #include <assert.h> #include <stdlib.h> #include "list.h" #include <vld.h> //初始化 void InitList(List plist) { assert(plist != NULL); if(plist==NULL) { return ; } plist->next = NULL; } //头插 bool Insert_head(List plist,int val) { Node *p = (Node *)malloc(sizeof(Node)); p->data = val; p->next = plist->next; plist->next = p; return true; } //尾插 bool Insert_tail(List plist,int val) { Node *q; for(q=plist;q->next!=NULL;q=q->next);//尾节点q标记为q->next==NULL Node *p = (Node *)malloc(sizeof(Node)); p->data = val; p->next = q->next;//p->next = NULL;//将p插在q的后面 q->next = p; return true; } //查找 Node* Search(List plist,int key) { for (Node *p = plist->next;p != NULL;p = p->next) { if (p->data == key) { return p; } } return NULL; } //查找前驱 Node* Precunrsor_Search(List plist,int key) { for (Node *p = plist;p != NULL;p = p->next) { if (p->next->data == key) { return p; } } return NULL; } bool Delete(List plist,int key) { Node *p = Precunrsor_Search(plist,key);//前驱 if (p == NULL) { return false; } plist = p; p = plist->next; plist->next = plist->next->next; free(p);//注意:由于这里是删除结点,所以要回收内存,free(所选删除的结点),防止内存泄漏。 p = NULL;//置空以防止出现ye return true; } int GetLength(List plist) { int count = 0; for (Node *p = plist->next;p != NULL; p = p->next) { count++; } return count; } bool IsEmpty(List plist) { return plist->next == NULL; } //清空数据 void Clear(List plist) { Destroy(plist); } //销毁链表 void Destroy(List plist) { Node *p; while (plist->next != NULL) { p = plist->next; plist->next = p->next; free(p); p=NULL; } } //打印函数 void Show(List plist) { for(Node *p=plist->next;p!=NULL;p=p->next) { printf("%d ",p->data); } printf("\n"); } 对单链表实现就地逆置(笔试、面试重点) void Reverse(List plist) { if (plist == NULL || plist->next == NULL || plist->next->next == NULL) { return ; } Node *p = plist->next; plist ->next = NULL; Node *q; while (p != NULL) { q = p->next; p->next = plist->next; plist->next = p; p = q; } } 结束语:相比于无头链表,单链表中,增加一个头结点的目的是为了(方便运算的实现),类似于《算法导论》中       讲到的:是作为哨兵的作用,可以使代码简洁方便。而无头链表,没有头结点,则首元素没有前驱结点,在其前插入结点或者删除结点会复杂考虑的多一点。

转载请注明原文地址: https://www.6miu.com/read-3350255.html

最新回复(0)