带头结点的单链表_不带头结点与带头结点的单链表 - CSDN
  • 单链表的概念: 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。 在这里我们称每个数据元素ai为一个节点,它包含两个域,其中存储信息的是数据域,存储直接后继存储位置的域称为指针域。...

    声明:本文章的所有代码全部使用C++语言,本文章所涉及的操作全部为基本操作。

    单链表的概念:

    线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。

    在这里我们称每个数据元素ai为一个节点,它包含两个域,其中存储信息的是数据域,存储直接后继存储位置的域称为指针域。

    单链表的定义:

    typedef int ElemType;
    struct LNode
    {
        ElemType data;
        LNode *next;
        LNode(ElemType _data = 0, LNode *_next = NULL) : data(_data), next(_next) {}
    };
    typedef LNode *LinkList;

    说明:

    1.ElemType为对应的数据域的数据类型,不仅仅是基本的数据类型,也可以复杂的数据类型。

    2.next即为指向直接后继存储位置的指针

    3.LNode *类型我们用来指向单个节点,而LinkList类型我们用来表示一个链表,也就是如果指向头结点的指针为L那么我们成该立案表为L,声明为LinkList L;

    单链表的声明:

    LinkList L;

    这样我们声明了一个链表L,L指向头结点(因为这里我们讨论带头结点的单链表),实际上不管是带头结点还是不带头结点,L永远都指向链表的第一个元素。

    单链表的初始化:

    bool InitList(LinkList &L)
    {
        L = new LNode();
        if(L != NULL)
            return true;
        else
            return false;
    }

    我们动态建立新的节点给L作为整个链表的头结点,如果节点申请成功也就是L不指向空返回true,反之申请不成功L指向空返回false。

    单链表的遍历:

    LNode *pcur = L->next;
    while(pcur)
    {
        cout << pcur->data << " ";
        pcur = pcur->next;
    }

    我们只要每次操作完当前结点,让当前位置的指针指向下一个位置就可以了,但是需要注意的一点是,我们往往不直接用头指针L去遍历链表,而是用一个指向结点的指针去遍历链表,这样做是为了保存链表的头指针,否则整个链表会失去起点(因为是单链表)。

    单链表当中元素的查找:

    1.查找链表当中第i个元素:

    ElemType GetElem(LinkList L, int pos)
    {
        int j = 1;
        L = L->next;
        while(L && j < pos)
        {
            L = L->next;
            j++;
        }
    
        if(!L || j > pos)
            return -1;
        return L->data;
    }

    注:上面代码实现的功能是在带头结点的单链表L中查找第pos个数据元素,如果存在则返回这个数据元素,否则返回不存在的标记(因为在这里ElemType实际上就是int,所以返回-1用来标识,具体视情况而定)。

    1.首先我们标记一个计数器j用来标记当前结点是单链表的第几个结点,然后我们依次遍历整个单链表,因为单链表是带头结点的,因此我们首先L = L->next,将指针指向首元节点,然后依次遍历直到找到第pos个结点。

    2.如果最后我们得到的节点指针是指向空的,也就是说明整个链表不存在第i个元素(链表当中的数据元素的个数小于i),或者是j>i(j大于i说明i是违法的,也就是i<=0)。

    2.查找第一个数据域等于e的节点:

    int LinkFind(LinkList L, ElemType e)
    {
        int j = 1;
        L = L->next;
        while(L && L->data != e)
        {
            L = L->next;
            j++;
        }
    
        if(!L)
            return -1;
        return j;
    }

    注:该函数实现的功能为查找第一个数据为e的结点,返回结点的标号。

    1.跟上一个查找第i个结点的操作很相似,只要L结点的数据域不等于e就往后遍历即可。

    链表元素的插入:

    1.前插法:

    前插法就是将新的结点插入在链表的首元结点之前,即链表的顺序与输入顺序相反。

    ElemType x;
    while(cin >> x && x != -1)
    {
        LNode *p = new LNode(x);
        p->next = L->next;
        L->next = p;
    }

    前插法的图解如下:

    图中s所指向的节点即为新加节点(p)

    1.首先我们将链表L的首元节点(a1)接在节点p后面(p->next = L->next),实际上只要将首元节点接在p后面,相当于将整个链表(头结点除外)接在了p后面,因为a1的next指针指向a2,而a2的next指针又指向了a3……

    2.之后我们将p节点接在链表L的头结点的后面(L->next = p),在整个过程当中L始终指向链表的头结点,这时就完成了新节点p的前插。

    2.后插法:

    尾插法就是将新的节点插在整个链表的尾部,即链表的顺序与输入顺序相同。

    LNode *pcur = L;
    ElemType x;
    while(cin >> x && x != -1)
    {
        pcur->next = new LNode(x);
        pcur = pcur->next;
    }

    尾插法的图解如下:

    1.我们创建一个指向结点的指针,这个指针永远都指向整个链表的最尾部的节点,每次我们都将新的节点接在当前链表的最尾结点的后面(pcur->next = new LNode(x))。

    2.将链表的指针后移(pcur = pcur->next),目的是为了保证pcur指针永远指向链表的最尾部节点。

    3.在第i个位置插入元素e

    bool ListInsert(LinkList L, int pos, ElemType e)
    {
        int j = 0;
        while(L && j < pos - 1)
        {
            L = L->next;
            j++;
        }
    
        if(!L || j > pos - 1)
            return false;
    
        LNode *s = new LNode(e);
        s->next = L->next;
        L->next = s;
    
        return true;
    }

    注:该函数实现的功能是在第i个结点之前插入数据元素e,如果插入成功返回true,否则返回false。

    1.如果想要在第i个结点之前插入数据元素e,我们必须要获得第i个结点的直接前驱,也就是第i-1个结点,因此我们先遍历链表查找第i-1个结点。

    2.当我们找到第i-1个结点时,此时我们可以将问题转化为类似前插法,将数据元素插入(一定要注意先后次序)。

    链表元素的删除:

    删除第i个位置的结点:

    bool ListDelete(LinkList L, int pos)
    {
        int j = 0;
        while(L && j < pos - 1)
        {
            L = L->next;
            j++;
        }
    
        if(!L || j > pos)
            return false;
    
        LNode *p = L->next;
        L->next = L->next->next;
        delete p;
    
        return true;
    }

    注:该函数实现的功能为删除链表的第i个结点,如果删除失败成功true,否则返回false。

    1.要删除第i个结点我们首先要获取第i个结点的直接前驱,也就是第i-1一个结点。

    2.我么将ai-1的next指针指向ai的下一个结点(L->next = L->next->next),就完成了将ai移出链表,但是我们必须要清空ai所占的内存,于是用结点指针p指向ai方便我们的删除。

    链表的清空:

    void ClearList(LinkList &L)
    {
        LNode *p = L->next;
        L->next = NULL;
        while(p)
        {
            LNode *temp = p;
            p = p->next;
            delete temp;
        }
    }

    注:该函数实现的功能为,清空链表L,也就是删除除头结点之外的所有结点。

    1.首先我们用结点指针指向当前要删除的结点,然后将链表L的头结点与首元结点的关系断开(L->next = NULL)。

    2.然后我们用结点指针p遍历整个链表,一边遍历一遍删除结点(注意顺序)。

    链表的销毁:

    void DestroyList(LinkList &L)
    {
        LNode *p = L;
        while(p)
        {
            LNode *temp = p;
            p = p->next;
            delete temp;
        }
        L = NULL;
    }

    注:该函数实现的功能为销毁整个链表,销毁与清空的区别就是销毁就是连头结点也要删除。
    1.类似清空操作,只不过我们删除之后,将链表L的头指针指向空,也就是这个链表不存在。(区分L指向空与L->next指向空的区别)。

    展开全文
  • pragma once include include include

    pragma once

    include

    include

    include

    展开全文
  • 1、单链表i的创建(头插法与尾插法) 2、单链表的元素插入 3、单链表元素的删除 4、单链表中固定位置元素的获取 5、寻找单链表与给定数字相同的元素位置 6、获取单链表的长度 7、展示整个链表的元素 #include...

    实现功能:
    1、单链表i的创建(头插法与尾插法)

    2、单链表的元素插入

    3、单链表元素的删除

    4、单链表中固定位置元素的获取

    5、寻找单链表与给定数字相同的元素位置

    6、获取单链表的长度

    7、展示整个链表的元素

    #include<bits/stdc++.h>

    using namespace std;

    struct Node

    {

    int data;

    Node *next;

    };

    class Linklist

    {

    private:

    Node *Head;

    public:

    Linklist();

    void CreatheadList();//头插法创建链表

    void CreathailList();//尾插法创建链表

    void Insert();//插入元素

    int Delete();//删除表中元素

    int GetData();//取得表中元素

    int Search();//在表中寻找匹配项

    int ListLength();//获得表中的长度

    void Display();//展示整个链表

    };

     

    Linklist::Linklist()

    {

    Head=new Node;

    Head->next=NULL;

    }

     

    void Linklist::CreatheadList()//头插法创建链表

    {

    int n;

    cout<<"请输入链表元素个数:";

    cin>>n;

    Node *p;

    Node *temp;

    p=Head;

    cout<<"请输入"<<n<<"个链表的值:";

    for(int i=0;i<n;i++)

    {

    temp=new Node;

    cin>>temp->data;

    temp->next=p->next;

    p->next=temp;

    }

    Display();

    }

     

    void Linklist::CreathailList()//尾插法创建链表

    {

    cout<<"请输入链表元素个数:";

    int n;

    cin>>n;

    Node *p;

    Node *temp;

    p=Head;

    cout<<"请输入"<<n<<"个链表的值:";

    for(int i=0;i<n;i++)

    {

    temp=new Node;

    cin>>temp->data;

    p->next=temp;

    p=temp;

    }

    Display();

    }

     

    void Linklist::Insert()//在i处插入e

    {

    int i,e;

    cout<<"请输入在何处插入元素:";

    cin>>i;

    cout<<"请输入插入元素为:";

    cin>>e;

    Node *temp;

    temp=Head;

    int j=0;

    while(temp&&j<i-1)

    {

    temp=temp->next;

    j++;

    }

    if(!temp||j>i-1)

    {

    cout<<"插入位置错误";

    return;

    }

    else

    {

    Node *s;

    s=new Node;

    s->data=e;

    s->next=temp->next;

    temp->next=s;

    }

    Display();

    }

     

    int Linklist::Delete()//删除i处的元素

    {

    int i;

    cout<<"请输入删除何处的元素:";

    cin>>i;

    Node *temp;

    temp=Head;

    int j=0;

    while(temp&&j<i-1)

    {

    temp=temp->next;

    j++;

    }

    if(!temp||j>i-1)

    {

    cout<<"删除位置错误"<<endl;

    return 0;

    }

    else

    {

    Node *s;

    s=temp->next;

    temp->next=s->next;

    delete s;

    }

    Display();

    }

     

    int Linklist::GetData()//得到i处的元素

    {

    int i;

    cout<<"请输入得到何处的元素:";

    cin>>i;

    Node *temp;

    temp=Head;

    int j=0;

    while(temp&&j<i-1)

    {

    temp=temp->next;

    j++;

    }

    if(!temp||j>i-1)

    {

    cout<<"寻找位置错误"<<endl;

    return 0;

    }

    else

    {

    cout<<i<<"处的元素为:"<<temp->next->data<<endl;

    // return temp->data;

    }

    }

     

    int Linklist::Search()//寻找链表中有无该元素

    {

    int obj;

    cout<<"请输入要查找的元素:";

    cin>>obj;

    int j=1;

    Node *temp;

    temp=Head->next;

    while(temp&&temp->data!=obj)

    {

    temp=temp->next;

    j++;

    }

    if(temp==NULL)

    {

    cout<<"链表中无此元素"<<endl;

    return 0;

    }

    else

    {

    cout<<"在该链表中第"<<j<<"个元素等于"<<obj<<endl;

    }

    return j;

    }

     

    int Linklist::ListLength()//计算链表的长度

    {

    Node *temp;

    temp=Head->next;

    int j=1;

    while(temp)

    {

    temp=temp->next;

    j++;

    }

    cout<<"该链表的长度为:"<<j-1<<endl;

    return j;

    }

     

    void Linklist::Display()//输出链表的元素

    {

    Node *temp;

    temp=Head->next;

    cout<<"该链表的元素依次为";

    while(temp)

    {

    int e=temp->data;

    cout<<e<<" ";

    temp=temp->next;

     

    }

    cout<<endl;

    }

    int main()

    {

    Linklist headlist;

    Linklist haillist;

    int temp;

    while(1)

    {

    cout<<"请选择链表生成方法:";

    cin>>temp;

    if(temp==1)

    {

    headlist.CreatheadList();

    headlist.Insert();

    headlist.GetData();

    headlist.Search();

    headlist.Delete();

    headlist.ListLength();

    }

    else

    {

    haillist.CreatheadList();

    haillist.Insert();

    haillist.GetData();

    haillist.Search();

    haillist.Delete();

    haillist.ListLength();

    }

    }

    system("pause");

    return 0;

    }

    展开全文
  • 带头结点单链表

    2012-08-19 15:46:49
    1.带头结点单链表之描述  带头结点单链表是指,在单链表的第一个结点之前增加一个特殊的结点,称为头结点。头结点的作用就是让所有的链表(包括空链表)的头指针非空,并使对单链表的插入、删除操作不需要区分...

             1.带头结点的单链表之描述

                       带头结点的单链表是指,在单链表的第一个结点之前增加一个特殊的结点,称为头结点。头结点的作用就是让所有的链表(包括空链表)的头指针非空,并使对单链表的插入、删除操作不需要区分是否为空表或者是否在第一个位置进行,也就是说,与在其他位置的插入和删除操作一致。

            2.java实现

    package linearList;
    
    public class HSLinkedList<E> implements LList<E> {
    	protected Node<E> head;//头指针,指向单链表的头结点
    	protected Node<E> rear;//尾指针,指向单链表最后一个结点
    	protected int n;//单链表长度
    	
    	/*
    	 * 构造空单链表
    	 */
    	public HSLinkedList(){
    		this.head = new Node<E>(null);//创建头结点
    		this.head = this.rear;//表明是空单链表
    		this.n = 0;
    	}
    	
    	/*
    	 * 判断单链表是否为空
    	 */
    	public boolean isEmpty(){
    		return this.head.next == null;
    	}
    	
    	/*
    	 * 返回单链表长度
    	 */
    	public int length(){
    		return this.n;
    	}
    	
    	/*
    	 * 方法体略,详见单链表类
    	 */
    	public E get(int index){return null;}
    	public E set(int index,E element){return null;}
    	public String toString(){return null;}
    	
    	/*
    	 * 在单链表最后插入element对象
    	 */
    	public boolean add(E element){
    		if(element==null){
    			return false;
    		}else{
    			this.rear.next = new Node(element);//尾插入
    			this.rear = this.rear.next;//移动尾指针
    			this.n++;
    		}
    		return true;
    	}
    	
    	/*
    	 * 插入element对象,插入位置序号为index
    	 */
    	public boolean add(int index,E element){
    		if(element==null){
    			return false;
    		}else if(index>=this.n){
    			return this.add(element);//尾插入
    		}else{
    			int i = 0;
    			Node<E> p = this.head;
    			while(p.next!=null&&i<index){
    				p = p.next;
    				i++;
    			}
    			Node<E> q = new Node(element,p.next);//将q结点插入在p结点之后
    			p.next = q;
    			this.n++;
    		}
    		return true;
    	}
    	
    	/*
    	 * 移除序号为index的对象,返回被移除的对象
    	 */
    	public E remove(int index){
    		E old = null;
    		if(index>=0){
    			int i = 0;
    			Node<E> p = this.head;
    			while(p.next!=null&&i<index){
    				p = p.next;
    				i++;
    			}
    			if(p.next!=null){
    				old = (E)p.next.data;
    				if(p.next==this.rear){
    					this.rear = p;
    				}
    				p.next = p.next.next;//删除p的后继结点
    				this.n--;
    			}
    		}
    		return old;
    	}
    	
    	/*
    	 * 清空单链表
    	 */
    	public void clear(){
    		this.head.next = null;
    		this.rear = this.head;
    		this.n = 0;
    	}
    }
    
              3.分析

                       本次采用变量n和尾指针rear,使得返回单链表的长度和在单链表尾插入时,时间复杂度有原来的O(n)变成了O(1),显著的提升了效率。

    展开全文
  • /**************************************/ /* 链表实现的头文件,文件名slnklist.h */ /**************************************/ #include <stdio.h>.../************************...
  • 带头结点单链表是指,在单链表的第一个结点之前增加一个特殊的结点,称为头结点。 头结点的作用:使所有链表(包括空表)的头指针非空,并使对单链表的插入,删除操作不需要区分是否为空表或是否在第一个位置进行...
  • 单链表的定义 #include&amp;amp;amp;amp;lt;stdio.h&amp;amp;amp;amp;gt; #include&amp;amp;amp;amp;lt;malloc.h&amp;amp;amp;amp;gt; #include&amp;amp;amp;amp;lt;stdlib.h&amp;amp;...
  • 一直以来,带头结点和不带头节点的单链表的操作实现困扰着我。在没有理解和实现之前,光凭思考真的是很难理解清楚 1.两者之间代码的差异; 2.带不带头结点的区别; 3.带头结点之后,什么情况下形参必须传二级指针...
  • #include #include typedef struct node{ int data;...//创建带头结点单链表 create(node *L){ L= (node*)malloc(sizeof(node)); if (L==NULL){ printf ("0"); } else { L->next=NULL;...
  •  对于带头结点的点链表,逆置其中最核心的步骤就是对链表就行头插法。   第一步:先定义两个指针(pCur 和 pNext),同时指向第一个元素的地址;    第二步:使头结点和第一个元素断开链接(Phead-&gt;...
  • 带头结点 #include "stdio.h" #include "stdlib.h" typedef struct List { int data; //数据域 struct List *next; //指针域 } List; List * HeadCreatList() //头插法建立链表,不带头结点...
  • 带头结点和不带头结点单链表注意的小细节 在写不带头结点的单链表中发现了一个问题,这个问题在带头结点的单链表中也存在,那就是值传递的问题。 首先来看一下 #include&amp;amp;amp;lt;stdio.h&amp;amp;...
  • 带头结点单链表的建立
  • 关键字:带头结点单链表+分解 思路 关注:递归算法的设计重点在于找到“递归”的部分,即重复调用函数,改变部分相关变量 设f(L,x)的功能是:删除以L为首结点指针的单链表中所有值等于x的结点,显然有f(L->next,x...
  • 完善教材上带头结点单链表的就地逆置问题 #include using namespace std; typedef struct node { char a; struct node *next; }node,*LinkList; //初始化单链表 void initList(LinkList *L) { *L=(LinkList)...
  • 关键字:带头结点单链表,逆向输出 思路 关注:递归算法的设计重点在于找到“递归”的部分,即重复调用函数,改变部分相关变量 设f(L,x)的功能是:删除以L为首结点指针的单链表中所有值等于x的结点,显然有f(L->...
  • 利用c++实现不带头结点链表的基本操作实现,如逆序建立链表,插入、删除链表元素等。
  • 这里先实现带头结点单链表操作。 大概有以下知识点. 1;结点:结点就是单链表中研究的数据元素,结点中存储数据的部分称为数据域,存储直接后继地址的部分称为指针域。 2;结点示意图: 3;头指针:头指针始终...
  • 题目:设线性表L=(a1,a2,a3,…an-2,an-1,an)采用带头结点的单链表保存,链表中的结点定义如下: typedef struct node { int data; struct node*next }Node; 请设计一个空间复杂度为O...关键字:带头结点单链表+...
  • 关键字:带头结点单链表+递增有序 思路 关注:递归算法的设计重点在于找到“递归”的部分,即重复调用函数,改变部分相关变量 设f(L,x)的功能是:删除以L为首结点指针的单链表中所有值等于x的结点,显然有f(L->...
1 2 3 4 5 ... 20
收藏数 10,242
精华内容 4,096
关键字:

带头结点的单链表