数据结构——单链表

栏目: 数据库 · 发布时间: 7年前

内容简介:数据结构——单链表

前面介绍了顺序表的特点和实现!但是顺序表有很多的不足,比如要给顺序表的前面插入一个数据,就必须先把后面的数据先一个一个的往后挪动,然后再将所要插入的数据放进去。就相当于一个数组一样。

还有就是顺序表的大小分配,如果采用静态分配内存的方式,那么势必就会造成剩余内存的浪费,不利于CPU工作。要是用动态内存分配,可以减少内存浪费情况,但是一次性开辟的内存不能太大也不能太小,遇到一个结构体数据刚刚存放满,这时候在想增加数据就要再申请空间,那么申请的空间只用了一个,其他的也就造成了浪费。

所以这时候为了方便存储,和更加节省空间,就采用了单链表的方式。先来看看为什么单链表有这么多好处

数据结构——单链表

单链表采用上一个节点的头结点和下个节点相邻,相当于把好多的数据直接连起来,用的时候只需要改变节点之间的连接。而且增容是一次增加一个节点的大小,实现了真正的用多少分配多少。

写单链表的时候一定要注意你的首节点,别丢了,丢了就找不回来。还有就是在删除节点的时候一定要对那个节点负责,不然让它成为野指针了,对谁都不好。

单链表如何实现,还有接口怎么封装,具体在程序中看一下,重点部分都做了标识。

ListNode.h

#ifndef _LISTNODE_H_
#define _LISTNODE_H_

#include <stdio.h>
#include <windows.h>
#include <assert.h>


typedef int Datatype;

typedef struct ListNode
{
	Datatype data;
	struct ListNode *next;
}ListNode;

void PushBack(ListNode **pplist, Datatype x);//从后面插入一个data为x的节点
void PopBack(ListNode **plist);	//从后面删除一个节点
void PrintList(ListNode *plist);  //打印单链表
void PushFront(ListNode **pplist, Datatype x); //从前面插入一个data为x的节点
void PopFront(ListNode **pplist);	//从前面删除一个节点
ListNode* Find(ListNode* pList, Datatype x); //查找data为x的节点,并返回这个节点

//在pos前插入||删除
void Insert(ListNode **pplist, ListNode *pos, Datatype x);//在所指定的节点前插入一个data为x的节点
void Erase(ListNode **pplist, ListNode *pos);//删除指定的节点




#endif
ListNode.cpp
#include "ListNode.h"

ListNode *BuyNode(Datatype x)	//生成节点封装接口
{
	ListNode *Node = (ListNode *)malloc(sizeof(ListNode));// 以动态的形式生成一个大小为一个结构体大小的节点
	Node->data = x;	//所要生成的节点数据
	Node->next = NULL;	//将生成节点的下个赋为空
	return Node;
}

void PrintList(ListNode *plist)//打印单链表
{
	ListNode *cur = plist;
	while(cur != NULL)
	{
		printf("%d->",cur->data);//将单链表的数据正向输出
		cur = cur->next;
	} 
	printf("NULL\n");
}

void PushBack(ListNode **pplist, Datatype x)//在做这些之前要先理清思路,都有哪几种情况,然后敲
{
	//1.空 2.只有一个 3.多个
	assert(pplist);
	if(*pplist == NULL)//没有节点的时候直接把节点给首节点
	{
		*pplist = BuyNode(x);
	}
	else if((*pplist)->next == NULL)
	{
		(*pplist)->next = BuyNode(x);//只有一个就把生成的节点串在首节点后面
	}
	else
	{
		ListNode *cur = *pplist;	
		while((cur)->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = BuyNode(x);
	}
}

void PopBack(ListNode **pplist)//和Push一样都要考虑清楚,然后就很好写
{
	//1.NULL 2.1个 3.多个
	assert(pplist);
	if(*pplist == NULL)
	{
		return;
	}
	else if((*pplist)->next == NULL)
	{
		free(*pplist);//只有一个的话直接释放
		*pplist = NULL;//一定要将这个节点置空,不然容易成为野指针
	}
	else
	{
		ListNode *tmp = *pplist;//先定义两个指针,分别保存要删除的节点和上一个节点
		ListNode *cur = tmp;
		while(tmp->next != NULL)
		{
			cur = tmp;
			tmp = tmp->next;
		}
		free(tmp);//删除指定节点
		cur->next = NULL;//将上个节点的next给置空
		tmp = NULL;//记得置空
	}
}

void PushFront(ListNode **pplist, Datatype x)//和尾插一样,只是情况还要具体分析
{
	//1.NULL 2.一个 3.多个
	assert(pplist);
	if(*pplist == NULL)
	{
		*pplist = BuyNode(x);
	}
	else
	{
		ListNode *cur = BuyNode(x);
		cur->next = *pplist;
		*pplist = cur;
	}
}

void PopFront(ListNode **pplist)
{
	//1.NULL 2.一个 3.多个
	assert(pplist);
	if(*pplist == NULL)
	{
		return;
	}
	else if((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		ListNode *tmp = *pplist;
		*pplist = tmp->next;
		free(tmp);
	}
}

ListNode* Find(ListNode* plist, Datatype x)//查找节点并不改变数据,所以不用传结构体指针的地址
{
	while(plist)
	{
		if(plist->data == x)//当找到要查找的数时,就直接返回
		{
			return plist;
		}
		plist = plist->next;
	}
	//perror("Find");	//出错打印错误信息
	//system("pause");
	//exit(EXIT_FAILURE);//程序直接退出
	return NULL;
}

void Insert(ListNode **pplist, ListNode *pos, Datatype x)//先调Find
{
	//1.NULL 2.在第一个前插或只有一个数据 3.多个
	assert(pplist);
	assert(pos);
	if(*pplist == NULL)
	{
		*pplist = BuyNode(x);
	}
	else if(((*pplist)->next == NULL) || (pos == *pplist))
	{
		PushFront(pplist, x);
	}
	else
	{
		ListNode *tmp = *pplist;//这里要找到指定插入节点的上个节点和下个节点
		while(tmp->next != pos)
		{
			tmp = tmp->next;
		}
		ListNode *p = BuyNode(x);
		tmp->next = p;
		p->next = pos; 
	}
}

void Erase(ListNode **pplist, ListNode *pos)//要删除首先就要调用Find函数查找到相应的节点
{
	//1.NULL或1个 2.多个
	assert(pplist);
	assert(pos);
	if(((*pplist) == NULL) || ((*pplist)->next) == NULL)//只有一个或者没有节点时直接采用前删
	{
		PopFront(pplist);
	}
	else
	{
		ListNode *tmp = *pplist;
		while(tmp->next != pos)
		{
			tmp = tmp->next;
		}
		tmp->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


test.cpp
#include "ListNode.h"

struct ListNode* plist;

void test1()
{
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);

	PopBack(&plist);
	PopBack(&plist);
	PopBack(&plist);
	PopBack(&plist);
	PopBack(&plist);

	PrintList(plist);
}

void test2()
{
	PushFront(&plist, 1);
	PushFront(&plist, 2);
	PushFront(&plist, 3);
	PushFront(&plist, 4);

	PrintList(plist);

	PopFront(&plist);
	PopFront(&plist);
	PopFront(&plist);
	PopFront(&plist);
	PopFront(&plist);

	PrintList(plist);
}

void test3()
{
	ListNode *pos = NULL;
	PushBack(&plist, 1);
	/*PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);*/

	pos = Find(plist, 2);
	Insert(&plist, pos, 5);
	//Erase(&plist, pos);
	PrintList(plist);
}

int main()
{
	//test1();
	//test2();
	test3();
	system("pause");
	return 0;
}

数据结构——单链表

为了更加明确的了解链表的增删查改,在 Linux 环境下来演示一下具体的过程

#include "ListNode.h"

struct ListNode* plist;

void test1()
{
    int i = 0;
    int j = 0;
    printf("尾插,尾删\n");
    printf("\n");
    while(i<5){
        PushBack(&plist, i++);
        PrintList(plist);
        sleep(1);
    }
    while(j<5){
        PopBack(&plist);
        PrintList(plist);
        sleep(1);
        j++;
    }
}

void test2()
{
    int i = 0;
    int j = 0;
    printf("前插,前删\n");
    printf("\n");
    while(i<5){
        PushFront(&plist, i);
        PrintList(plist);
        sleep(1);
        i++;
    }while(j<5){
        PopFront(&plist);
        PrintList(plist);
        sleep(1);
        j++;
    }
}
void test3()
{
    int i = 0;
    ListNode *pos = NULL;
    printf("链表的节点插入、删除和查找\n");
    printf("\n");
    while(i<5){
        PushBack(&plist, i++);
        PrintList(plist);
        sleep(1);
    }
    pos = Find(plist, 2);
    printf("查找单链表里数据为2的节点i\n");
    printf("给2的前面插入5\n");
    Insert(&plist, pos, 5);
    PrintList(plist);
    sleep(1);
    printf("删除2\n");
    Erase(&plist, pos);
    PrintList(plist);
    }
int main()
{
        test1();
        test2();
        test3();
        return 0;

}
数据结构——单链表

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

云计算安全与隐私

云计算安全与隐私

Tim Mather、Subra Kumaraswamy、Shahed Latif / 刘戈舟、杨泽明、刘宝旭 / 机械工业出版社华章公司 / 2011-6 / 65.00元

《云计算安全与隐私》可以使你明白当把数据交付给云计算时你所面临的风险,以及为了保障虚拟基础设施和网络应用程序的安全可以采取的行动。本书是由信息安全界知名专家所著,作者在书中给出许多中肯的忠告和建议。本书的读者对象包括:IT职员、信息安全和隐私方面的从业人士、业务经理、服务提供商,以及投资机构等。阅读本书你会了解直到现在还严重匮乏的云计算安全方面的详尽信息。 《云计算安全与隐私》主要内容包括:......一起来看看 《云计算安全与隐私》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具