数据结构之单链表-EW帮帮网

从这个暑假开始，学完了基本算法的我，已经开启了数据结构之旅，第一个数据结构是“线性表”，分为链式存储结构和顺序存储结构，一个是顺序表（相当于数组），另一个是链表，分为单链表、双向链表、循环链表（用指针来进行和顺序表一样的操作），在这两个之中，顺序表较为简单，链表就是比较绕，很多人可能会忘记些什么。

而我，在这个星期里面，一步一步听课，写代码，学会了关于单链表的许多操作，今天，我就来写一个关于单链表的总结！

首先，我们需要学会怎么样来定义一个单链表！

我们要知道一个链表的长度是多少。可以用length来表示。
我们还要知道这个链表的数据域是什么。用data来表示。
最后还需要知道这个链表的指针域指向的哪里。用nxet来表示，next代表着链表的指针域，所以是一个指针，需要加上*号。

这样，我们就可以定义一个结构(struct)了，用Node来表示这个结构

定义一个链表代码：

struct Node
{
    int data;
    int length;
	struct Node* next;    	
};

现在，只需要在气体地方写上Node *L，就代表创建了一个链表！

定义了一个链表后，需要先来初始化后才可以使用，在这里，可以使用new函数，意思是分配一个空间，那我们要将空间分配给谁呢？自然是给这个结构了，这个链表有了空间之后，我们需要将这个链表设置为空，那么只需要让这个链表的指针域指向NULL（表示为空）就行了！

链表初始化代码：

bool initList_L(Node *&L)//链表初始化 
{
	L=new Node;
	L->next=NULL;
	return true;
}

指针一般都以->代表指向着什么东西！

定义链表后，又初始化了链表，接下来就可以使用链表了，我们的第一个操作就是判断这个链表是不是空链表（指针域指向空），怎么判断呢，只需要判断一下这个链表的指针域是不是指向空的，是就返回true，不是就代表这个链表的指针域指向了别的东西，返回false。

判断当前链表是否为空代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct Node
{
    int data;
    int length;
	struct Node* next;    	
};
bool initList_L(Node *&L)//链表初始化 
{
	L=new Node;
	L->next=NULL;
	return true;
}
bool ListEmpty(Node *L)//判断链表是否为空 
{
	if(L->next)
	  return false;
	else
	  return true;
}
int main()
{
    Node *p;
    initList_L(p);
    if(ListEmpty(p)==1)
      cout<<"当前链表为空"<<endl;
    else
      cout<<"当前链表不为空"<<endl;
    return 0;
}

之后，我们来学习下一个操作，来销毁这个链表，怎么销毁呢，可以用delete，这个是来销毁当前这个指针指向的地方，我们只需要一个while循环，只要不是指向空的，那么就进行销毁，先定义一个链表p，将p=L；然后p=p->next代表指针p成为了p指向的数据域，然后进行销毁。

销毁当前链表代码：

bool DestroyList_L(Node *&L)//销毁链表 
{
	Node *p;
	while(L!=NULL)
	{
		p=L;
		L=L->next;
		delete p;
	}
	return true;
}

由于我们还没有学习建立链表，这个函数的功能在之后实现！

然后，我们继续来看下一个操作，清空这个链表，就是将L重新设定为空表，这可和初始化不同，因为里面是有数据的，要想清空链表，需要多定义两个链表Node *p,*q;将p=L，然后用while循环知道直到链表为空，然后q=p->next代表指针q成为了p指向的数据域，注意这个是q，然后delete p，直接就销毁了，然后将p=q,相当于重新又定义了一个链表，不过里面的数据被销毁了！

请空当前链表代码：

bool ClearList(Node *&L)//清空链表 
{
	Node *p,*q;
	p=L->next;
	while(p)
	{
		q=p->next;
		delete p;
		p=q;
	}
	L->next=NULL;
	return true;
}

要想测验这个函数的真实作用，还是要学会建立链表，然后将一个不为空的链表“L”放进这个函数里面，执行过后，我们想知道这个链表是否真的被清空了，就可以用到上面我将的判断当前链表是否是空链表的函数！

之后，我们就可以学习比较有难度的操作函数了，第一个就是求这个链表的表长，和之前一样，定义Node *p;让p=L;利用while循环知道指向NULL为止，里面要让指针p成为了p指向的数据域，然后在将length++，最后输出length就可以了！

求当前链表的表长代码：

bool qbc_L(Node *L)//求链表的表长 
{
	Node *p;
	p=L->next;
	while(p!=NULL)
	{
		p=p->next;
		L->length++;
	}
	L->length++;
	return true;
}

之后来到五大难关之一，单链表的查找算法（函数），按我们输入的值来查找这个数，意思是在这个链表里面查找一个你输入的数，返回这个数的下标，首先定义一个int类型变量j，代表着在这个链表里面的下标，然后定义Node *p;p=L;， while循环直到为空，里面指针p成为了p指向的数据域，只要这个指针的数据域等于输入的这个数，就可以直接返回j，如果while循环执行完毕都没有找到，那么就返回0；

按输入的值查找代码：

int LocateElem_L(Node *L,int e)//按输入的值查找 
{
	Node *p;
//	initList_L(p);
	int j;
	p=L;
	j=1;
	while(p!=NULL)
	{
		if(p->data==e)
		  return j;
		p=p->next;
		j++;
	}
	return 0;
}

然后，来到五大难关之二，单链表的插入算法，函数执行效果是在这个链表下标为i的地方插入一个e，我们需要定义一个while循环，条件是指针不为空并且j<i-1，里面指针p成为了p指向的数据域，j++，这样是来查找链表下标为i的地方，然后while结束，经过判断，我们可以先连新绳，再解旧绳，所以要重新定义一个指针Node *t,给t分配空间以后，t的数据域data用来指向e，然后t的指针域在指向p的指针域，然后将p的指针域指向t的地址，也就是e。

在当前链表插入一个下标在i的地方的数e代码：

bool insert(Node *&L,int i,int e)
{
	Node *p,*t;
	p=L;
	int j=0;
	while(p&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i-1)
	  return false;
	t=new Node;
	t->data=e;
	t->next=p->next;
	p->next=t;
	return true;
}

有了插入，那当然还有删除了，就是在一个链表里面找到你输入的下标，然后将这个数给删除，和插入一样，首先找到链表下标为i的地方，经过判断，一样的思路，先连新绳，再解旧绳，由于是要删除，就需要多加一个delete q。

在当前链表删除一个下标在i的地方的数：

bool move(Node *&L,int i,int&e)
{
	Node *p,*q;
	p=L;
	int j=0;
	while(p->next&&j<i-1)
	{
		p=p->next;
		j++;
	}
	if(!(p->next)||j>i-1)
	  return false;
	q=p->next;
	p->next=q->next;
	e=q->data;
	delete q;
	return true;
}

现在，我们已经将所以关于单链表的基本操作函数给讲解了一遍，最后就到了建立链表的时候了，建立链表有两种方法，一种是头插法，另一种是尾插法，我个人比较喜欢用尾插法，因为是正着的，而头插法确实正着输入倒着输出的。

我们先来看头插法，首先要建立一个带有头结点的链表，生成一个新的节点，给这个节点分配空间，然后输入你要的元素值，在将元素值按照插入排序的办法插入到表头。

头插法创建链表代码：

Node *tcf(Node *L,int n)
{
	Node *p;
	L=new Node;
	L->next=NULL;
	for(int i=n;i>0;i--)
	{
		p=new Node;
		cin>>p->data;
		p->next=L->next;
		L->next=p;
	}
	return p;
}

尾插法和这个差不多，先用尾指针r指向头结点，然后生成一个新的节点，之后输入元素值，将其插入到表尾。

尾插法创建链表代码：

Node *wcf(Node *L,int n)
{
	Node *p,*r;
	L=new Node;
	L->next=NULL;
	r=L;
	for(int i=0;i<n;i++)
	{
		p=new Node;
		cin>>p->data;
		p->next=NULL;
		r->next=p;
		r=p;	
	}
	return L;
}

接下来，来到了我们的最后一个环节，就是输出一个链表，和之前一样，while循环到这个指针为空，指针p成为了p指向的数据域，然后输出p的数据域内容data。

输出链表代码：

void printList(Node *p)
{
	p=p->next;
	while(p!=NULL)
	{
		printf("%d,",p->data);
		p=p->next; 
	}
	cout<<endl;
}

最后，我把这些函数所有的都整理了一遍，可以依照以下的程序来进行实现所有的链表操作！

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct Node
{
    int data;
    int length;
	struct Node* next;    	
};
bool initList_L(Node *&L)//链表初始化 
{
	L=new Node;
	L->next=NULL;
	return true;
}
bool ListEmpty(Node *L)//判断链表是否为空 
{
	if(L->next)
	  return false;
	else
	  return true;
}
bool DestroyList_L(Node *&L)//销毁链表 
{
	Node *p;
	while(L!=NULL)
	{
		p=L;
		L=L->next;
		delete p;
	}
	return true;
} 
bool ClearList(Node *&L)//清空链表 
{
	Node *p,*q;
	p=L->next;
	while(p)
	{
		q=p->next;
		delete p;
		p=q;
	}
	L->next=NULL;
	return true;
}
bool qbc_L(Node *L)//求链表的表长 
{
	Node *p;
	p=L->next;
	while(p!=NULL)
	{
		p=p->next;
		L->length++;
	}
	L->length++;
	return true;
}
int LocateElem_L(Node *L,int e)//按输入的值查找 
{
	Node *p;
//	initList_L(p);
	int j;
	p=L;
	j=1;
	while(p!=NULL)
	{
		if(p->data==e)
		  return j;
		p=p->next;
		j++;
	}
	return 0;
} 
bool insert(Node *&L,int i,int e)
{
	Node *p,*t;
	p=L;
	int j=0;
	while(p&&j<i-1)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i-1)
	  return false;
	t=new Node;
	t->data=e;
	t->next=p->next;
	p->next=t;
	return true;
}
bool move(Node *&L,int i,int&e)
{
	Node *p,*q;
	p=L;
	int j=0;
	while(p->next&&j<i-1)
	{
		p=p->next;
		j++;
	}
	if(!(p->next)||j>i-1)
	  return false;
	q=p->next;
	p->next=q->next;
	e=q->data;
	delete q;
	return true;
}
void printList(Node *p)
{
	p=p->next;
	while(p!=NULL)
	{
		printf("%d,",p->data);
		p=p->next; 
	}
	cout<<endl;
}
Node *tcf(Node *L,int n)
{
	Node *p;
	L=new Node;
	L->next=NULL;
	for(int i=n;i>0;i--)
	{
		p=new Node;
		cin>>p->data;
		p->next=L->next;
		L->next=p;
	}
	return p;
}
Node *wcf(Node *L,int n)
{
	Node *p,*r;
	L=new Node;
	L->next=NULL;
	r=L;
	for(int i=0;i<n;i++)
	{
		p=new Node;
		cin>>p->data;
		p->next=NULL;
		r->next=p;
		r=p;	
	}
	return L;
}
int main()
{
	Node *p;
	initList_L(p);
//No.1头插法 
//	p=tcf(p,10);
//	printList(p);
//No.2尾插法
//    p=wcf(p,10);
//	printList(p); 
/
/
/
/
//No.1判断链表是否为空 
//    cout<<endl;  
//    cout<<"当前链表:";
//    cout<<ListEmpty(p)<<endl;
//No.2销毁这个链表
//    cout<<endl;
//    cout<<"当前链表:";
//    DestroyList_L(p);
//	printList(p);
//No.3清空这个链表
//    cout<<endl;
//    cout<<"当前链表:";
//	ClearList(p);
//	printList(p);
//No.4求链表的表长
//    cout<<endl;
//	qbc_L(p);
//	cout<<"链表长度:"<<p->length;
//No.5按输入的值查找 
//    cout<<endl;
//	int n;
//	cin>>n;
//	cout<<LocateElem_L(p,n)<<endl;
//No.7删除一个数
//    cout<<endl;
//	int i,v;
//	cin>>i;
//	move(p,i,v);
//	printList(p);
//	cout<<v<<endl;
//No.6插入一个数	
//    int n,e;
//	cout<<endl;
//	cin>>n>>e;
//	insert(p,n,e);
//	printList(p);
}

数据结构之单链表