数据结构 第二章 线性表2：单链表

数据结构 第二章 线性表2：单链表

越行勤 965 2021-02-11

线性存储的链式存储

链式存储又叫链表，分可以分为单链表 双链表，循环链表，静态链表。

单链表

何为单链表：使用链式存储的结构实现线性存储（逻辑结构）。顺序表在物理上是连续存放的，单链表无需这样，原因就是 每个简单除了存放数据元素之外，还存储了指向下一个节点的指针

优点： 不要求大片连续存储空间，改变容量方便。

缺点： 不可以随机读取，要花费一定的空间存储指针。

单链表有两种实现方式，带头节点和不带头节点的。

实现单链表

typedef struct
{
    int data;           //数据域
    struct LNode *next; //指针域
} LNode;

增加一个新的结点：在内存中申请空间，并用指针p指向这个节点

LNode *P = (LNode *)malloc(sizeof(struct LNode));

typedef 的使用

基本语法: typedef <数据类型> <别名> 。

使用typedef 我们可以简化很多。

typedef struct LNode
{
    int data;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

其实 只要把 struct LNode{} 看出一个整体就好理解了，结合 typedef <数据类型> <别名> ，是不用一目了然。

等价于 typedef struct LNode LNode; typedef struct LNode* linkList;

我们就可 声明 LinkList 声明头指针， LNode 声明结构体。

初始化单链表 和判断是否为空

不带头节点

不带头节点其实非常好理解

bool InitList(LinkList &L)//无比传入引用，要不然操作的就是局部变量
{
    L = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkList L)
{
    return (L==NULL);
}

使用话 用 LinkList 开辟头指针就好了。

void test()
{
    LinkList L; //声明指向单链表的指针
    InitList(L);
}
带头节点

其实带头节点有一点点不好理解。

bool InitList(LinkList &L)
{
    //开辟头节点，并且是头指针指向头节点
    L = (LNode *)malloc(sizeof(LNode));
    //开辟空间失败retrun flase
    if (L == NULL)
    {
        return false;
    }
    L->next = NULL;
    return true;
}
bool Empty(LinkList L)
{
    return (L->next == NULL);
}

void test()
{
    LinkList L; //声明指向单链表的指针
    InitList(L);
}
image-20210210152210283

首先加了头节点是为了实现某些操作方便，头节点不存储数据。

image-20210210153422747

带头节点和不带头节点有何区别

不带头节点，写代码比较麻烦，因为第一个数据点和后续数据不一样，所以需要不同的代码逻辑，并且对空表和非空表的处理也需要不同的逻辑。

结论：我们使用带头节点的，不适用不带头节点的。

单链表插入

带头节点

插入操作，在第i个位置上出入指定元素e。头节点可以作为第零个节点。

其实我们要做的事情就是

  1. 判断 i是否合法
  2. 在 i处 插入节点，就获取它前面一个节点 i-1
  3. 判断找到的i-1个节点是否存在
  4. 开辟新的节点并 连接到链表中
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1)//i表示为序 不允许小于1
        return false;
    LNode *p = L; //p 指向当前扫描到的节点
    int j = 0;    //当前p指向的是那个节点
    //循环时为了获取 i-1节点
    while (p != NULL && j < i - 1) //扫描到 第i-1节点 当p == NULL说明到了表尾
    {
        p = p->next;
        j++;
    }
    // 如果在大于表尾的地方插入数据，那节点存在 ，那么插入失败
    if (p == NULL)
        return false;
    //开始新的节点，并存储数据 e
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    // 将s指向下一个节点，并且p（第i-1）节点的next指向 s
    s->next = p->next;
    p->next = s;
    return true;
}
不带头节点

其实就多了一个处理插入第一个位置的特殊情况 ，由于没有头节点 ，那么就要改 头地址LinkList的指向，

if(i==1)
{
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    // 将s指向原来的下一个节点，并且头指针指向 s
    s->next = L->next;
    L->next = s;
    return true;
}

所以不带头节点就有点麻烦,以后的情况就说明有头节点。

任意节点后插操作

bool InsertNextNode(LNode* p,int e)
{
    //传入节点不存在 失败
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)//开辟空间失败
        return false;
    s->data=e;
    s->next = p->next;
    p->next = s;
    return true;
}

前插操作

由于我们单链表，知道某一个节点就可以知道它后面的所有节点，但是在他之前的呢，就单单这个条件的话无法知道的。

所以还要传入参数 头指针 LinkList，通过它来找到它前面节点，但是这样的算法时间复杂度无疑是 O(n);没有更简单的方法呢？

偷天换日

虽然节点是死的，但是数据是活的。找不到前驱节点就创造节点

  1. 我们继续指向后插操作
  2. 插入的节点覆盖插入节点的数据
  3. 原来的节点覆盖新数据。
bool InsertPriorNode(LNode *p, int e)
{
    //传入节点不存在 失败
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) //开辟空间失败
        return false;
    // 继续查到后面
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

很妙。

删除节点

删除操作,我们就需要进行如下几步

  1. 找到删除节点的前驱节点
  2. 让前驱节点的next指针跳过删除节点指向下一个节点。
  3. 释放删除节点的空间
按位序删除
// 按序位删除
bool ListDelete(LinkList &L, int i, int &e)
{
    if (i < 1)
        return false;
    LNode *p;
    int j = 0;
    p = L;
    // 扫描它前面一个节点
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    if (p->next == NULL) //发现i-1节点是 尾巴 就失败
        return false;
    //删除节点i
    LNode *q = p->next; //q是被删除节点
    e = q->data;//e是返回删除节点的值
    p->next = q->next;
    free(q);
    return true;
}
删除指定节点

和前插操作一样，我们这样进行

  1. 让它的后驱节点和自己交换数据域data 和指针域
  2. 释放后驱节点
bool DeleteNode(LNode *p)
{
    if (p == NULL)
        return false;
    LNode *q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}

但是这样是有bug的时候，假如删除最后一个节点就无法后驱节点（此时后驱节点是NULL）和自己交换数据域data 和指针域。

所以当时最后一个节点的时候，就要扫描到它的前驱节点

查找

按位查找

其实这个就简单多了，一个循环就可以解决

LNode *GetElem(LinkList L, int i)
{
    if (i < 0)
        return NULL;
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}
按元素查找
LNode *LocaleElem(LinkList L, int e)
{
    LNode *p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}

求表的长度

int Length(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

建立单链表

尾插法

所谓尾插法就是在链表的后面的节点插入数据。

LinkList List_TailInsert(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L; //s表示开创的节点,r 为尾指针
    scanf("%d", &x);
    while (x != 9999) //9999 作为退出标志
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; //新开辟的节点接入s 链表
        r = s;       //r有和新开创的节点重合
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
头插法

所谓头插法就是 一致在头节点插入数据

我们使用头插法，插入数据的话，插入数据是输入数据的逆序。

输入的数据是 1 2 3 那么存储数据恰好是 3 2 1, 这就叫逆置

LinkList List_HeadInsert(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s;
    L->next = NULL;
    scanf("%x", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        //头插入操作
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%x", &x);
    }
    return L;
}

我们就可以更具这个写出一个逆置的函数, 其实就把后一个元素前插到前一个元素

void Inverse(LinkList &L)
{
    LNode *p, *q;
    p = L->next;
    L->next = NULL; //初始化空表
    while (p != NULL)
    {
        q = p; //p,q同时指向next结点
        p = p->next;//p为下一个指针。

        //头插操作
        q->next = L->next; //第一次执行时L->next为NULL
        L->next = q;
    }
}

总结

其实获取单链表这么多运算离不开，前插，后插操作，扫描节点的这几个操作。

分享一下 个人写的c语言实现(未完善)的单链表

# include <stdio.h>
# include <stdlib.h>

/**********************
线性表的实现:单链表
by 越行勤 2021年 3月 9日
***********************/

typedef struct LNode 
{
	int data;						//数据域
	struct LNode* next;				//指针域
}LNode,*LinkList;

/*
LNode 特指结点
LinkList 等于 LNode * 特指  单链表这个数据结构

头节点相当于 0号结点 不存储数据也就是 L所指向的节点
本LinkList是 带头节点的
*/
bool Init_LinkList(LinkList& L);					//初始化单链表
bool Empty_LinkList(LinkList L);					//判断单链表是否为空
bool GetElem_LinkList(LinkList L,int i,int &e);		//获取第i个元素
bool DelteList_LinkList(LinkList &L, int i, int& e); //按位删除结点
bool InsertLisk_LinkList(LinkList& L, int i, int e); //按位插入元素
void Print_LinkList(LinkList L);					//打印出每一个链表的数据



bool GetNode_LinkList(LinkList L, int i, LNode*& p);	//获取第i个结点Node
bool InsertNext_LinkList(LNode* L, int e);			//在任意结点之后插元素---后插
bool InsertPrior_LinkList(LNode* L, int e);			//再任意结点之前插元素---前插
bool DeleteNode_LinkList(LNode* L, int &e);         //删除指定结点



void test()
{
	LinkList L;
	int e;
	LNode* p;

	Init_LinkList(L);
	printf("初始化完成^_^\n");

	for (int i = 1; i <= 10; i++)
	{
		InsertNext_LinkList(L, i);
	}
	printf("后插数据完成 ^_^\n");

	InsertLisk_LinkList(L, 5,44);
	printf("往5号插入元素完成\n");

	Print_LinkList(L);

	DelteList_LinkList(L, 5, e);
	printf("删除第5个节点成功\n");
	Print_LinkList(L);
	
	getchar();
}
int main()
{
	test();
	return 0;
}

bool Init_LinkList(LinkList& L)
{
	//头指针L 指向 头节点
	L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL)
		return false;
	//头结点的后驱结点为 NULl
	L->next = NULL;
	return true;
}

bool Empty_LinkList(LinkList L)
{
	//直接判断头节点是否指向 NULl
	if (L->next == NULL)
		return true;
	return false;
}

bool GetNode_LinkList(LinkList L, int i, LNode* & p)
{
	LNode* q = L->next; 
	int j = 1;//负责计数
	while (q != NULL && j < i)
	{
		q = q->next; 
		j++;
	}
	if (!q || j > i)// 说明i结点不存在
		return false;
	p = q;
	return true;
}
bool GetElem_LinkList(LinkList L, int i, int& e)
{
	LNode* p;
	if (!GetNode_LinkList(L, i, p))
		return false;
	e= p->data;
	return true;
}
bool InsertNext_LinkList(LNode* L, int e)
{
	if (L == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	// 分配空间失败
	if (s == NULL)
		return false;

	s->data = e;
	//插入结点s
	s->next = L->next;
	L->next = s;
	return true;
}
/*
前插结点：
虽然我们没有办法直接找到前一个结点 但是可以先进行后插操作
然后 再交换  插入结点和 插入点结点的数据
就相当于 向前插入结点了一样
*/
bool InsertPrior_LinkList(LNode* L, int e)
{
	if (!InsertNext_LinkList(L, e))
		return false;
	// 交换  插入结点和 插入点结点
	int t = L->data;
	L->data = L->next->data;
	L->next->data = t;
	return true;
}

/*
删除指定结点 其实向前插入节点的思想一致 、
和将后继节点的数据存储到当前节点 然后删除原来的后继节点
其实就相当于删除自己了

但是如果删除表尾元素 遍历找到前驱节点 才可以 
*/
bool DeleteNode_LinkList(LNode* L, int& e)
{
	if (L == NULL)
		return false;
	if (L->next==NULL) //说明删除表尾元素
	{
		LNode* p;
		p = L;
		//扫描到倒数第二个节点
		while (p->next)
			p = p->next;
		free(p->next);
		p->next = NULL;
		return true;
	}
	//如果不是表尾节点
	e = L->data;
	LNode* p = L->next;
	L->next = p->next;
	L->data = p->data;
	free(p);
	return true;
}

bool DelteList_LinkList(LinkList& L, int i, int& e)
{
	if (L == NULL)
		return false;
	LNode* p=L->next;
	int j = 1;
	//扫描到到第 i-1个节点
	while (p->next && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (p->next == NULL || j > i - 1)    //删除位置不合理
		return false;
	// 将第 i个位置上的节点剔除链表
	LNode* q = p->next;
	p->next = q->next;
	e = q->data;
	free(q);
	return true;
}

void Print_LinkList(LinkList L)
{
	printf("---------------------------\n");
	if (L->next == NULL)
	{
		printf("此链表为空表");
	}
	else
	{
		LNode* p = L->next;//头节点
		int i = 1;
		while (p)
		{
			printf("第%4d数据：        %4d\n", i, p->data);
			p = p->next;
			i++;
		}
		printf("打印完毕 此链表长%4d\n",i-1);
	}
	printf("---------------------------\n");
}
bool InsertLisk_LinkList(LinkList& L, int i, int e)
{
	LNode* p;
	if (!GetNode_LinkList(L, i, p))
		return false;
	return (InsertPrior_LinkList(p, e));
}
数据结构