数据结构---------------线性表（下篇）之单链表

朴灿烈づ我的快乐病毒、 2022-05-10 08:04 323阅读 0赞

# ![70][] #

# 单链表 #

特点：储存空间不连续

结点（数据元素组成）：数据域（储存数据）和指针域（指针）A1

![70 1][]

若用p来指向  则数据域为p->date   指针域为p->next

链式储存结构： 单链表、循环链表、双向链表根据链表结点所含指针个数、指针指向、指针连接方式可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等

非线性结构：二叉链表、十字链表、邻接表、邻接多重表等

//-----------------单链表的储存结构------------

typedef struct LNode
    {
    	ElemType date;     //结点数据域
    	struct LNode *next;//结点指针域 
     } LNode，*LinkList    //LinkList 为指向结构体LNoded的指针类型

1）对于LNode 和 \*LinkList   只写一个就可以   两者都是结构体的类型的名称

区别在于第二个为指针类型    也就是说  如果定义了一个LNode \*p  与定义一个LinkList p 是等价的存在；

① p为指向单链表中某结点的指针，是指针变量，\*p代表该结点，是结点变量；

②LNode \*  强调定义的是指向单链表中任意结点的指针变量，LinkList p 强调定义的是某个单链表的头指针；

2）单链表是由表头指针唯一确定的，换句话说，只要找到单链表的头指针，就能顺着找到这串链，所以单链表可以用头指针（表中的第一个结点）的名字来命名，若头指针名是L，则简称改链表为表L；

## 辨析   首元结点、头结点、头指针 ##

首元结点是指链表中储存第一个数据元素的结点

头指针是指向链表中第一个结点的指针

头结点是在第一个数据元素之前附近设立的一个结点，其指针域储存首元结点的地址                                                                                                       作用：1）便于首元结点的处理    2）便于空表和非空表统一处理                                                                                                                                                                                      当链表不设头结点时  判空条件为L==NULL 设头结点时  判空条件为L->next==NULL

有头结点时 头指针指向头结点   无头结点时  头指针就指向首元结点

## 特殊语句 ##

1）p=q;

![70 2][]

2)  p=q->next;

![70 3][]

3)  p->next=q;

![70 4][]

4)  p->next=q->next;

![70 5][]

## 单链表基本操作的实现 ##

### 1）初始化 ###

【算法描述】

Status  InitList(LinkList &L)    // 构造一个空的单链表 
    {
     	L=new LNode;              //生成的新结点作为头结点，用头指针L指向头结点 
    	L->next=NULL;             //头结点的指针置空 
    	return 1; 
    } 
    
     Status  InitList(LinkList &L)    // 构造一个空的单链表 
    {	
    	L=NULL;             //不带头结点，头指针置空 
    }

### 2）求链表长度 ###

【算法描述】

int ListLength(LinkList L)
    {
    	LinkList p;    //定义一个新指针 
    	p=L->next;   //指向第一个数据元素  没有头结点时 p=L; 
    	int k=0;     //计数器 
    	while(p)     //指针不为空，循环继续 
    	{
    		k++;
    		p=p->next;//指针指向下一个结点 
    	}
    	return k;     //返回链表长度 
     }

【算法分析】

求链表长度时需要将整个链跑一边  所以  时间复杂度为O(n);

### 3)销毁链表 ###

【算法描述】

void DestroyList(LinkList &L)
    {
     	LinkList p=L->next; //定义新节点并指向头指针 
     	while(p!=NULL)      //指针不为空 继续 
    	 {
    	 	L->next=p->next;//看下图 
    	 	delete p;       //释放该结点 
    	 	p=L->next;      //重复操作 
    	  } 
    	  delete L;         //释放头结点 
    }

L->next=p->next;    //即L的指针域存放的是下下一个结点的地址

![70 6][]

【算法分析】

依旧是要跑整个链  所以 时间复杂度为O(n);

### 4)取值 ###

【算法分析】

Status GetElem(LinkList L,int i,ElemType &e)
    {   //在带头结点的单链表L中根据序号i获得元素的值，用e返回L中第i个数据元素的值 
    	LinkList p;int j;
    	p=L->next;j=1;  //初始化p指向首元结点，计数器j初赋值为1 
    	while(p&&j<i)   //顺链域向后扫描，直到p为空或p指向第i个元素，一共跑i-1次 
    	{
    		p=p->next;  //指向下一个结点 
    		++j;         
    	 } 
    	 if(!p||j<i) return -2;   //i值不合法i>n 或 i<=n
    	  e=p->date;              //取第i个结点的数据域 
     }

【算法分析】

最好情况O(1） 最坏O(n)     所以  算法时间复杂度为 O(n)；

### 5)查找 ###

【算法描述】

LNode *LocateEle(LinkList L,ElemType e)
     {//在带头结点的单链表L中查找元素为e的元素 返回地址
         LinkList p;
    	 p=L->next;              //初始化，p指向首元结点 
     	 while(p && p->date!=e)  //顺链域向后扫描，直到p为空或p所指结点数据等于e
    	  p=p->next;             //p指向下一个结点 
    	return p;                // 查找成功返回值为e的结点的地址，查找失败p为NULL 
      }

【算法分析】

最好情况O(1） 最坏O(n)     所以  算法时间复杂度为 O(n)；

### 6）插入 ###

插入分两种情况 1）p之后插入新节点s

2）p之前插入新节点s      带头结点   不带头结点

1） p之后插入新节点s

![70 7][] 先1后2

【算法描述】

void ListAfterInsert(LinkList &L,LNode *p,LNode *s)
     {//在单链表L中p结点之后插入一个结点s 
     	s->date =e;
     	s->next =NULL;  //给结点赋初值
    	
    	s->next =p->next;  //第一步 s的指针域存放p下一个结点的地址
    	p->next =s;        //第二步 p的指针域存放s的 
      }

【算法分析】

不需要遍历  时间复杂度为O(1);

2）p之前插入新节点s

![70 8][]

带头结点

【算法描述】

void ListAfterInsert(LinkList &L,LNode *p,LNode *s)
     {//在带头结点的单链表L中p结点之前插入结点s
         LinkList q=L;    //定义新指针并赋予头指针
    	 while(q->next!=p) //判断是否为p结点的前驱
    	    q=q->next;     //指向下一个结点
    	q->next=s;         //将s的地址赋给q的指针域 
    	s->next=p;         //将p的地址赋给s的指针域 
      }

不带头结点    比带头指针多一种判断

【算法描述】

void ListAfterInsert(LinkList &L,LNode *p,LNode *s)
     {//在不带头结点的单链表L中p结点之前插入结点s
        if(p==L)          //判断是否为头指针
    	 {
    	 	s->next =L;   //s指针域存放头指针地址
    		L=s;          //s为头指针 
          }
        else
    	 { 
            LinkList q=L;    //定义新指针并赋予头指针 
    	    while(q->next!=p) //判断是否为p结点的前驱
    	        q=q->next;     //指向下一个结点
    	    q->next=s;         //将s的地址赋给q的指针域 
        	s->next=p;         //将p的地址赋给s的指针域 
    	 } 
      }

【算法分析】

要找到插入点之前的结点 所以要遍历  时间复杂度为O(n);

### 6)删除 ###

![70 9][]

带头结点

【算法描述】

void ListDelete(LinkList &L,LNode *p,Elemtype &e)
     {//在带头结点的单链表L中删除p结点 并用e返回p的数据元素 
         LinkList q=L;    //定义新指针并赋予头指针
    	 while(q->next!=p) //判断是否为p结点的前驱
    	    q=q->next;     //指向下一个结点
       	q->next=p->next;   //将p下个结点的地址赋给q的指针域 
    	e=p->date;         //e 储存p的数据元素   
    	delete p;          //释放内存 
      }

不带头结点

【算法描述】

void ListDelete(LinkList &L,LNode *p,Elemtype &e)
     {//在带头结点的单链表L中删除p结点 并用e返回p的数据元素 
         if(p==L)          //判断是否为头指针
    	 	L=L->next;     //L的下个结点的地址赋给L 
          
         else
    	  { 
             LinkList q=L;    //定义新指针并赋予头指针
    	     while(q->next!=p) //判断是否为p结点的前驱
    	        q=q->next;     //指向下一个结点
       	    q->next=p->next;   //将p下个结点的地址赋给q的指针域
    	  } 
    	e=p->date;         //e 储存p的数据元素 	  
    	delete p;          //释放内存 
      }

【算法分析】

需要找到待删除结点之前的结点  遍历  时间复杂度为O(n);

# 单链表的简单应用（int） #

#include<iostream>
    using namespace std;
    typedef struct Lnode
    {
    	int date;
    	struct Lnode *next;
    }Lonode,*linklist;
    void Getelem(linklist L,int i,int e)//取值 
    {
    	Lnode *p;
        p=L->next;
    	int j=1;
    	while(p&&j<i)
    	{
    		p=p->next;
    		++j;
    	}
    	e=p->date;
    	cout<<"第"<<i<<"个元素的值为："<<e<<endl<<endl;
    }
    void Locateelem(linklist L,int e)//查找 
    {
    	Lnode *p;
    	int i=1;
    	p=L->next;
    	while(p&&p->date!=e)
    	{
    		p=p->next;
    		i++;
    	 } 
    	 cout<<"查找的元素在该链表的第"<<i<<"个位置"<<endl;
    	 cout<<"查找元素的地址为:"<<p<<endl<<endl; 
    }
    void Maxelem(linklist L)//取最大值 
    {
    	Lnode *p;
    	p=L->next->next;
    	int max=L->next->date;
    	
    	while(p)
    	{
    		max=max>p->date?max:p->date;
    		p=p->next;
    	}
    	cout<<"该链表中的最大值为："<<max<<endl<<endl; 
    }
    void linkInsert(linklist &L,int i,int e)//插入 
    {
    	linklist p;
    	p=L;
    	int j=0;
    	while(p&&j<i-1)
    	{
    		p=p->next;
    		++j;
    	 } 
    	 linklist s;
    	 s=new Lnode;
    	 s->date =e;
    	 s->next=p->next;
    	 p->next=s;
    	 cout<<"元素"<<e<<"已成功插入！！！"<<endl<<endl; 
    }
    void linkdelete(linklist &L,int i)//删除 
    {
    	linklist p;
    	p=L;
    	int j=0;
    	while(p&&j<i-1)
    	{
    		p=p->next;
    		++j;
    	}
    	linklist q;
    	q=p->next;
    	p->next=q->next;
    	delete q;
    	
    	cout<<"第"<<i<<"位置上的元素已成功删除！！！"<<endl<<endl; 
    }
    void creatlist_h(linklist &L,int n)//头插法
    {
    	cout<<"请倒叙输入数据：";
    	Lnode *p;
        L=new Lnode;
    	L->next=NULL;
      for(int i=n;i>0;i--)
      {
    	  p=new Lnode;
    	  cin>>p->date;
    	  p->next=L->next;
    	  L->next=p;
      }
    }
    void creatlist_d(linklist &L,int n)//尾插法
    {
    	cout<<"请输入数据：";
    	L=new Lnode;
    	L->next=NULL;
    	Lnode *p;
    	linklist r;
    	r=L;
    	for(int i=0;i<n;i++)
    	{
    		p=new Lnode;
            cin>>p->date;
    		p->next=NULL;
    		r->next=p;
    		r=p;
    	}
    }
    
    	
    void traverse(linklist L)//遍历
    {
    	cout<<"该单链表的数据为：";
         Lnode *p=L->next;
    	
    	while(p)
    	{
    		cout<<p->date<<" ";
    		p=p->next;
    	}
    	cout<<endl;
    }
    int main()
    {
        	linklist L;
         	int n;
    	
    	    int m;
    		while(1)
    		{
    		cout<<"1,创建"<<endl;
    		cout<<"2,取值"<<endl;
    		cout<<"3,查找"<<endl;
    		cout<<"4,取最大值"<<endl;
    		cout<<"5,插入"<<endl;
    		cout<<"6,删除"<<endl;
    		cout<<"7,遍历"<<endl;
    		cout<<"0,结束"<<endl;
            cout<<"请输入您的操作：";
    		  cin>>m;
    		
    			if(m==1)
    			{
    	   	        int p;
        	        cout<<"1，头插法"<<endl;
        	        cout<<"2，尾插法"<<endl;
    	        	cout<<"0,返回上一步 "<<endl<<endl;
    	            cout<<"输入你的选择：";
        	        cin>>p;
        	        while(p)
        	        {
        	          if(p==1)
    		            {
                          cout<<"链表长度:";
        	              cin>>n;
        	              creatlist_h(L,n);
    	        	     }
        	          else if(p==2)
    		            {
                          cout<<"链表长度:";
        	              cin>>n;
        	              creatlist_d(L,n); 
    		            }
    		            cout<<"请输入你的选择：";
    					cin>>p; 
                     }
    			}
    			else if(m==2)
    			{
    				int i,e=0;
    				cout<<"请输入待取值的位置：";
    				cin>>i;
    				Getelem(L,i,e);
    			}
    			else if(m==3)
    			{
    				int e;
    				cout<<"请输入需查找的元素：";
    				cin>>e;
    				Locateelem(L,e); 
    			}
    			else if(m==4)
    			{
    				Maxelem(L);
    			}
    			else if(m==5)
    			{
    				int i,e;
    				cout<<"请输入插入元素的位置：";
    				cin>>i;
    				cout<<endl<<"请输入带插入元素：";
    				cin>>e;
    				linkInsert(L,i,e); 
    			} 
    			else if(m==6)
    			{
    				int i;
    				cout<<"请输入要删除元素的位置：";
    				cin>>i;
    				linkdelete(L,i); 
    			}
    			else if(m==7)
    			{
    				traverse(L);
    			}
    			else if(m==0)
    			{
    				return 0;
    			}
    			else
    			{
    				cout<<"输入错误！！！"<<endl; 
    			}
    			cout<<endl;
    		 } 
    		
    	return 0;
    }

over~~~~~~~~~~~~

才怪ヽ(￣▽￣)ﾉ

下篇  顺序表和链表的比较

[70]: /images/20220510/87ae69c5589548019e04fb6084b26a28.png
[70 1]: /images/20220510/a3249f246aa64b669deb407e0f6f46d6.png
[70 2]: /images/20220510/3d5c6303d5214b9283b2d1bda811fbe9.png
[70 3]: /images/20220510/cbdd19e2992140da892ec1640b05df07.png
[70 4]: /images/20220510/89f8d28c25f14db78a31143c00a26b3e.png
[70 5]: /images/20220510/438da50ce4104105a3493a29f2629ec7.png
[70 6]: /images/20220510/1800969b0efe4302af545e233894ffba.png
[70 7]: /images/20220510/c34f8bec2bce4e3a8aa901f28f13bcec.png
[70 8]: /images/20220510/5e79b7509ecf43eb87514e518774ad00.png
[70 9]: /images/20220510/b7227b55d6a341d18a8640985f1e2326.png