博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
数据结构学习笔记之线性表（2）
阅读量：3934 次
发布时间：2019-05-23

本文共 11514 字，大约阅读时间需要 38 分钟。

单链表

一、基本概念

1、链表的定义

  • 所为链表就是指线性表采用链式存储，用一组任意的存储单元来存放线性表的数据元素。
  • 每个结点，分为数据字段和指针字段，数据字段存放当前节点的数据，指针字段指向下一个结点；因此在空间消耗上，链表要比顺序表的多。
  • 由于链表是通过指针链起来的，因此可以不用一片连续的存储区域来存放线性表的数据，而是能够离散的存储在存储空间中，因此链表也是非随机存取的存储结构。

2、链表的头指针与头节点

  • 通常用一个头指针来标识一个链表，当头指针为NULL时，链表为空。
  • 出于操作方便，通常会在单链表的第一个结点之前附加一个不存放数据的结点，称为头结点。
  • 无论一个链表是否有头结点，头指针始终指向链表的第一个结点。
  • 使用头结点有如下好处：
    1）由于第一个数据结点的位置存放在头结点的指针域中，所以链表的第一个位置上的操作和其他结点的操作一致，无需特殊处理。
    2）无论链表是否为空，其头指针都指向头结点的非空指针，因此空表和非空表的处理得到了同一。

二、C++实现单链表

1、结点结构

  • 单链表的结点的结构如下：
    class LNode{
         private:	int data;	LNode* next;};
  • 出于数据封装，数据字段和指针字段都声明为私有数据。

2、单链空表构造

  • 使用构造方法创建一个空表，语句如下：
    LNode::LNode(){
         	this->data = 0;	this->next = NULL;}

3、初始化

  • 用一个数组来初始化链表，有两种初始化方法：头插法和尾插法。
  • 头插法关键语句：
    LNode* s = new LNode();s->data = value;s->next = L->next;L-next=s;
  • 尾插法关键语句：
    LNode* p = L;LNode* s = new LNode();s->data = value;p->next = s;p=s;
  • 采用头插法生成的链表的元素顺序与数据输入的顺序是相反的，而尾插法生成的链表的元素的顺序与数据输入的顺序是一致的。
  • 因此，我这里采用尾插法初始化链表。
bool LNode::init(int* a, int len){
   	LNode* s;	LNode* p = this;	try {
   		for (int i = 0; i < len; i++)		{
   			s = new LNode();			s->data = a[i];			p->next = s;			p = s;		}		return true;	}	catch (exception e) {
   		cout << e.what() << endl;		return false;	}}

4、链表判空

  • 即判断一个链表是否为空，语句如下：
    bool LNode::isEmpty(){
         	if (this->next == NULL)		return true;	return false;}

5、按序取值

  • 由于链表的是离散存储的，因此链表的取值都是按序取值的，而不是按址取值。
  • 链表取值时，必须从头结点开始按顺序遍历到指定序号的结点停止。
  • 代码如下：
    int LNode::getValue(int index){
         	if (!this->isEmpty())	{
         		int count = 1;		LNode* p = this->next;		if (index == 0)			return this->data;		if (index < 1)			return NULL;		while (p && count < index) {
         			p = p->next;			count++;		}		return p->data;	}	return -1;}
  • 首先进行判空操作，如果时空链表直接返回-1；

6、按值取序

  • 这一操作和上一操作类似，只是在遍历时需要比较每个结点与指定值是否相等，若相等则停止遍历，返回当前结点所在的序号。
    LNode* LNode::getIndex(int value){
         	if (this->isEmpty())		return NULL;	LNode* p = this->next;	while (p != NULL && p->data != value)		p = p->next;	return p;}
  • 由于返回的是一个指针，以及后面的取前件和取后件的操作也都是返回指针，而数据声明为私有的，为了能够获得当前节点的数据值，编辑如下代码：
    int LNode::value(){
         	return this->data;}

7、获取表长

  • 返回单链表的序号长度，从1开始。
    int LNode::length(){
         	if (this->isEmpty())		return 0;	LNode* p = this->next;	int count = 0;	while (p)	{
         		count++;		p = p->next;	}	return count;}

8、获取前驱后继

  • 根据指定序号获取该序号的直接前驱或直接后件，代码如下：
    //获取指定下标的前驱LNode* LNode::getPre(int index){
         	if (this->isEmpty())		return NULL;	LNode* p = this->next;	for (int i = 1; i < index - 1; i++)		p = p->next;	return p;}// 获取指定下标的后件LNode* LNode::getNext(int index){
         	if (this->isEmpty())		return NULL;	LNode* p = this->next;	for (int i = 1; i <= index; i++)		p = p->next;	return p;}

9、增加元素

  • 增加元素有两种方式：追加和插入。追加是在尾部增加元素，而插入是在序列中的某个位置插入，链表由于是离散存储，所以进行插入操作时不必像顺序表那样，需要移动插入位置之后的元素以空出位置进行插入，链表的插入操作只需修改指针的链接指向。
    在这里插入图片描述
  • 因此链表的元素增加的时间复杂度都是常数阶，这时链表的特点。代码如下：
    //单链表插入bool LNode::insert(int index, int value){
         	if (this->isEmpty())		return false;	int len = this->length();	if (index <= 0 || index > len)		return false;	LNode* p = this->getPre(index);	LNode* s = new LNode();	s->data = value;	s->next = p->next;	p->next = s;	return true;}//单链表追加bool LNode::append(int value){
         	if (this->isEmpty())		return false;	LNode* p = this->next;	while (p->next)		p = p->next;	LNode* s = new LNode();	s->data = value;	p->next = s;	return true;}

10、修改元素值

  • 由于链表不是随机存取的数据结构，要修改某个元素的值，必须从头结点开始顺序遍历到指定序号的节点处停止，才进行元素值修改，这一点链表的效率不如顺序表。
  • 修改指定序号的元素值代码如下：
    bool LNode::change(int index, int value){
         	if (this->isEmpty())		return false;	int len = this->length();	if (index <= 0 || index > len)		return false;	LNode* p = this->getPre(index + 1);	p->data = value;}
  • 我这里为了提高代码得复用性，巧妙的利用了用于获取指定序号前件的方法。

11、删除

  • 链表的删除操作也比较容易，删除就是将指定序号的前件的指针直接指向指定序号的后件，用图标识如下：
    在这里插入图片描述
  • 代码如下：
    bool LNode::del(int index){
         	if (this->isEmpty())		return false;	int len = this->length();	if (index <= 0 || index > len)		return false;	LNode* p = this->getPre(index);	LNode* q = p->next;	p->next = q->next;	free(q);}

12、遍历

  • 按照顺序从头到尾依次将元素值在屏幕上打印出来。
    void LNode::show(){
         	LNode* p = this->next;	while (p)	{
         		cout << p->data << " ";		p = p->next;	}	cout << endl;}

13、增序排序

  • 将链表元素按照值从小到大的顺序排列。
    void LNode::Ascending(){
         	LNode* p = this->next;	LNode* q = p->next;	while (p)	{
         		q = p->next;		while (q)		{
         			if (p->data > q->data)			{
         				int t = p->data;				p->data = q->data;				q->data = t;			}			q = q->next;		}		p = p->next;	}}
  • 因此单链表类的类体完整声明代码如下：
    class LNode{
         private:	int data;	LNode* next;public:	LNode();	bool init(int* a, int len);	int value();	int getValue(int index);	void show();	LNode* getIndex(int value);	bool insert(int index, int value);	bool del(int index);	bool isEmpty();	LNode* getPre(int index);	LNode* getNext(int index);	int length();	bool append(int value);	bool change(int index, int value);	void Ascending();};

三、C++ 实现双链表

1、双链表的结点

  • 所谓双链表，就是结点有两个指针域，分别指向前件和后件，结点结构如下：
    class DNode{
         private:	int data;	DNode* prior, * next;public:	DNode();	bool init(int a[], int len);	void show();	void insert(int index, int value);	void del(int index);};
  • 由于双向链表的大部分操作与单链表的一样，只是多了一个指向前件的指针的相关操作，因此这里只展示构造方法、初始化方法、插入和删除。

2、构造与初始化

DNode::DNode(){
   	this->data = 0;	this->prior = nullptr;	this->next = nullptr;}bool DNode::init(int a[], int len){
   	try {
   		DNode* p = this;		DNode* s = new DNode();		s->data = a[0];		s->prior = p;		p->next = s;		p = s;		for (int i = 1; i < len; i++)		{
   			s = new DNode();			s->data = a[i];			s->prior = p;			p->next = s;			p = s;		}		return true;	}	catch (exception e) {
   		cout << e.what() << endl;		return false;	}}

3、插入与修改

  • 双向链表的修改，与单链表的修改有所不同，如下图所示：
    在这里插入图片描述
  • 左边的是向双向链表插入结点的操作，右边是从双向链表删除结点的操作。
  • 我实现插入操作的代码与图示的有所不同，图示的是定位到插入序号所在结点，而我是定位到插入序号所在的结点的前件，为了代码更容易理解：
    void DNode::insert(int index, int value){
         	DNode* p = this->next;	for (int i = 1; i < index - 1; i++)		p = p->next;	DNode* s = new DNode();	s->data = value;	s->prior = p;	s->next = p->next;	p->next = s;}
  • 删除操作也是与图示不同，图示用一个辅助指针，我用两个。
    void DNode::del(int index){
         	DNode* p = this->next;	for (int i = 1; i < index; i++)		p = p->next;	DNode* t = p->prior;	t->next = p->next;	p->next->prior = t;	delete p;}

四、循环链表与静态链表

  • 在链表的基础上，还可以构造出循环链表。循环链表有两种循环方式：单循环和双循环。分别是用单链表构造和用双链表构造。

1、单循环链表

  • 单循环链表利用next指针进行循环，让最后一个数据结点的next指针指向头结点，如下图：
    在这里插入图片描述
  • 由图也可以看出，单循环链表的判空操作就是，判断下一结点是否就是头结点，用代码表示就是：
    if(p->next==p)	return true;return false;
  • 单循环链表的插入操作与删除操作的算法与单链表的一样，追加操作则于单链表不一样：追加元素的下一个结点指向头结点。
  • 比起单链表，单循环链表不必从头结点开始也可以遍历整个链表。
  • 由于链表的很多操作是针对表头和表尾进行的，单循环链表若只设尾指针可以提高操作效率，因为尾指针的下一结点就是头结点，对于表头与表尾的操作都只需O(1)的时间复杂度，若设头指针，要操作尾结点时则必须遍历到尾结点才能进行，时间复杂度为O(n)。
  • 出于实际实现的需要，例如为了避免遍历时一直循环，通常要统计定位指针的移动次数，当次数与链表元素数量相等时终止循环；或者采用为头结点的数据域进行特殊操作，给头结点的数据域赋一个用于标识它为头结点的值，例如0，这样的话0 就不能作为有效数据。

2、双循环链表

  • 在双向链表的基础上，让头结点的前一个结点指向链表的最后一个结点，而让最后一个结点的下一个结点指向头结点，如下图：
    在这里插入图片描述
  • 双向链表的判空，即判断头结点下一结点和前一结点是不是都指向头结点。
  • 双向链表的插入与删除结点的算法，与双向链表的算法一样，同样只是元素追加的操作不太一样。
  • 遍历时如何终止同样有指针移动计次和头结点特殊处理两种。

3、静态链表

  • 所谓静态链表，是指不使用真正的指针来连接结点，而是用伪指针。通常静态链表借助数组来描述，此时伪指针就是结点的相对地址（数组下标），又称游标；由于是用数组描述，因此静态链表初始化时，需要预先分配足够的空间。
    在这里插入图片描述
  • 相对于静态链表，前面的几种用到真正的指针的链表都称为动态链表。
  • 静态链表的结点结构如下：
    class SNode{
         	int data;	int next;};
  • 用 next==-1来表示最后一个结点，插入、删除操作与动态链表一样，只需修改指针，不用移动元素。
  • 静态链表适用于不支持指针的高级编程语言，如Basic。

五、与单链表相关的算法

// 将链表从(a1,a2,a3...an)变成(a1,an,a2,an-1....)void LNode::changeList(){
   	LNode* p, * q, * r, * s;	p = q = this;	while (q->next != NULL)	{
   		p = p->next;		q = q->next;		if (q->next != NULL)q = q->next;	}	q = p->next;	p->next = NULL;	while (q != NULL)	{
   		r = q->next;		q->next = p->next;		p->next = q;		q = r;	}	s = this->next;	q = p->next;	p->next = NULL;	while (q != NULL)	{
   		r = q->next;		q->next = s->next;		s->next = q;		s = q->next;		q = r;	}}// 从链表中删除绝对值相同的元素，保留第一个元素void LNode::delSameAbsolut(){
   	LNode* p = this, * r;	int* q, m;	int n = this->length();	q = new int[n + 1];	for (int i = 0; i < n + 1; i++)		*(q + i) = 0;	while (p->next != NULL)	{
   		m = p->next->data > 0 ? p->next->data : -(p->next->data);		if (*(q + m) == 0)		{
   			*(q + m) = 1;			p = p->next;		}		else		{
   			r = p->next;			p->next = r->next;			free(r);		}	}	free(q);}// 查找链表中倒数第k个元素的值int LNode::searchK(int k){
   	LNode* p = this->next, * q = this->next;	int count = 0;	while (p != NULL)	{
   		if (count < k)count++;		else q = q->next;		p = p->next;	}	if (count < k)		return 0;	else {
   		cout << q->data << endl;		return 1;	}}// 提取两个链表中的公共元素作为一个新链表返回,并且不破坏原来的两个链表void LNode::getCommon(LNode* l, LNode*& newL){
   	LNode* p = this->next, * q = l->next, * r, * s;	r = newL;	while (p != NULL && q != NULL)	{
   		if (p->data < q->data)			p = p->next;		else if (p->data > q->data)			q = q->next;		else if (p->data == q->data)		{
   			s = new LNode();			s->data = p->data;			r->next = s;			r = s;			p = p->next;			q = q->next;		}	}	r->next = NULL;}// 将两个递增顺序的链表合并为一个递增顺序的新链表void LNode::merge(LNode* l){
   	LNode* r, * pa = this->next, * pb = l->next;	this->next = NULL;	while (pa && pb)	{
   		if (pa->data <= pb->data)		{
   			r = pa->next;			pa->next = this->next;			this->next = pa;			pa = r;		}		else		{
   			r = pb->next;			pb->next = this->next;			this->next = pb;			pb = r;		}	}	if (pa)		pb = pa;	while (pb)	{
   		r = pb->next;		pb->next = this->next;		this->next = pb;		pb = r;	}}//去掉增序链表中值相同的多余元素，即去重void LNode::DelSame(){
   	LNode* p = this->next, * q;	if (p == NULL)		return;	while (p->next != NULL)	{
   		q = p->next;		if (p->data == q->data)		{
   			p->next = q->next;			free(q);		}		else		{
   			p = p->next;		}	}}// 将一个链表按照序号的奇偶分别拆成两个链表LNode* LNode::divide(){
   	int i = 0;	LNode* B = new LNode();	LNode* ra = this, * rb = B;	LNode* p = this->next;	this->next = NULL;	while (p != NULL)	{
   		i++;		if (i % 2 == 0)		{
   			rb->next = p;			rb = p;		}		else		{
   			ra->next = p;			ra = p;		}		p = p->next;	}	ra->next = NULL;	rb->next = NULL;	return B;}//寻找两个链表的公共结点LNode* LNode::searchCommon(LNode* L1){
   	int len1 = this->length();	int len2 = L1->length();	int dist;	LNode* longL, * shortL;	if (len1 > len2)	{
   		longL = this->next;		shortL = L1->next;		dist = len1 - len2;	}	else {
   		longL = L1->next;		shortL = this->next;		dist = len2 - len1;	}	while (dist--)		longL = longL->next;	while (longL != NULL)	{
   		if (longL == shortL)			return longL;		else {
   			longL = longL->next;			shortL = shortL->next;		}	}	return NULL;}// 删除值在指定范围内的元素的值bool LNode::RangeDel(int min, int max){
   	if (this->isEmpty())		return false;	LNode* pre = this, * p = this->next;	while (p != NULL)	{
   		if (p->data > min && p->data < max)		{
   			pre->next = p->next;			free(p);			p = pre->next;		}		else {
   			pre = p;			p = p->next;		}	}}//使用插入排序使链表增序void LNode::insertSort(){
   	LNode* p = this->next, * pre;	LNode* r = p->next;	p->next = NULL;	p = r;	while (p != NULL)	{
   		r = p->next;		pre = this;		while (pre->next != NULL && pre->next->data < p->data)			pre = pre->next;		p->next = pre->next;		pre->next = p;		p = r;	}}//就地逆置链表void LNode::reverse(){
   	// r 为 p 的后继，用于防止断链	LNode* p, * r;	p = this->next;	this->next = NULL;	while (p != NULL)	{
   		r = p->next;		p->next = this->next;		this->next = p;		p = r;	}}//删除链表中的最小值bool LNode::DelMin(){
   	if (this->isEmpty())		return false;	// 工作指针	LNode* pre = this, * p = pre->next;	// 存储最小值的相关指针	LNode* minpre = pre, * minp = p;	while (p != NULL)	{
   		if (p->data < minp->data)		{
   			minp = p;			minpre = pre;		}		pre = p;		p = p->next;	}	minpre->next = minp->next;	free(minp);	return true;}//逆序输出链表void ReversePrint(LNode* L){
   	if (L->next != NULL)		ReversePrint(L->next);	if (L != NULL && L->data != 0)		cout << L->data << " ";}// 删除链表中所有值等于x的结点bool LNode::DelX(int x){
   	if (this->isEmpty())		return false;	LNode* p = this->next, * pre = this, * q;	while (p != NULL)	{
   		if (p->data == x)		{
   			q = p;			p = p->next;			pre->next = p;			free(q);		}		else {
   			pre = p;			p = p->next;		}	}	return true;}

转载地址：http://vqqgn.baihongyu.com/

你可能感兴趣的文章
rake应用
查看>>
opera插件开发
查看>>
2012工作日志
查看>>
MongoDB基本介绍及一些用法
查看>>
hash对象
查看>>
基本数据类型和对象
查看>>
mongoDB应用
查看>>
MongoDB 和 MongoMapper的示例用法简介
查看>>
欢迎使用CSDN-markdown编辑器
查看>>
Hadoop和大数据开源工具推荐
查看>>
聚类算法
查看>>
大数据的六大规则
查看>>
rails加载方式
查看>>
Hadoop Storm Spark比较
查看>>
职业测试~~
查看>>
Ruby on Rails调试经验分享
查看>>
ruby中保留2位小数
查看>>
ruby 字符串处理
查看>>
rails console环境下显示AR sql
查看>>
rails console production
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-09-18 16:55:25   当前IP: 3.139.97.53   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我