精华内容
下载资源
问答
  • C++链表基本操作 链表的操作基本都有 找个东西不容易
  • 该资源为链表基本操作C++实现),包括两部分:首先是链表基本操作(包括链表的动态创建和销毁、内存释放、节点的插入、删除、打印);其次是链表的强化操作(包括链表的整体反转、特定区间元素反转、各种链表...
  • 链表的12种基本操作C++实现)

    万次阅读 多人点赞 2018-07-23 22:49:03
    链表是一种动态数据结构,他的特点是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放数据元素。链表中每一个元素成为“结点”,每一个结点都是由数据域和指针域组成的,每个结点中的指针域指向下一个...

            链表是一种动态数据结构,他的特点是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放数据元素。链表中每一个元素成为“结点”,每一个结点都是由数据域和指针域组成的,每个结点中的指针域指向下一个结点。Head是“头指针”,表示链表的开始,用来指向第一个结点,而最后一个指针的指针域为NULL(空地址),表示链表的结束。可以看出链表结构必须利用指针才能实现,即一个结点中必须包含一个指针变量,用来存放下一个结点的地址。实际上,链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表,这是最简单的链表结构。再c++中实现一个单链表结构比较简单。
    例如,可定义单链表结构的最简单形式如下:
    struct Node
    {
    int Data;
    Node*next;
    };

            这里用到了结构体类型。其中,*next是指针域,用来指向该结点的下一个结点;Data是一个整形变量,用来存放结点中的数据。当然,Data可以是任何数据类型,包括结构体类型或类类型。在此基础上,我们在定义一个链表类list,其中包含链表结点的插入,删除,输出等功能的成员函数。

    C++实现链表的12种基本操作:

    C++单链表的操作2017-12-25  1 // 单链表.cpp: 定义控制台应用程序的入口点。
    //Author:kgvito 
    //Date: 2017.12.25
    
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    
    typedef int DataType;
    #define Node ElemType
    #define ERROR NULL
    
    //构建一个节点类
    class Node                          
    {
    public:
        int data;     //数据域
        Node * next;  //指针域
    };
    
    //构建一个单链表类
    class LinkList                      
    {
    public:
        LinkList();                      //构建一个单链表;
        ~LinkList();                  //销毁一个单链表;
        void CreateLinkList(int n);   //创建一个单链表
        void TravalLinkList();        //遍历线性表
        int GetLength();              //获取线性表长度
        bool IsEmpty();               //判断单链表是否为空
        ElemType * Find(DataType data); //查找节点
        void InsertElemAtEnd(DataType data);            //在尾部插入指定的元素
        void InsertElemAtIndex(DataType data,int n);    //在指定位置插入指定元素
        void InsertElemAtHead(DataType data);           //在头部插入指定元素
        void DeleteElemAtEnd();       //在尾部删除元素
        void DeleteAll();             //删除所有数据
        void DeleteElemAtPoint(DataType data);     //删除指定的数据
        void DeleteElemAtHead();      //在头部删除节点
    private:
        ElemType * head;              //头结点
    };
    
    //初始化单链表
    LinkList::LinkList()                  
    {
        head = new ElemType;            
        head->data = 0;               //将头结点的数据域定义为0
        head->next = NULL;            //头结点的下一个定义为NULL
    }     
    
    //销毁单链表
    LinkList::~LinkList()
    {
        delete head;                 //删除头结点
    } 
    
    //创建一个单链表
    void LinkList::CreateLinkList(int n)
    {
        ElemType *pnew, *ptemp;
        ptemp = head;
        if (n < 0) {       //当输入的值有误时,处理异常
            cout << "输入的节点个数有误" << endl;
            exit(EXIT_FAILURE);
        }
        for (int i = 0; i < n;i++) {        //将值一个一个插入单链表中
            pnew = new ElemType;
            cout << "请输入第" << i + 1 << "个值: " ;
            cin >> pnew->data;
            pnew->next = NULL;          //新节点的下一个地址为NULL
            ptemp->next = pnew;         //当前结点的下一个地址设为新节点
            ptemp = pnew;               //将当前结点设为新节点
        }
    }
    
    //遍历单链表
    void LinkList::TravalLinkList()
    {
        if (head == NULL || head->next ==NULL) {
            cout << "链表为空表" << endl;
        }
        ElemType *p = head;                 //另指针指向头结点
        while (p->next != NULL)        //当指针的下一个地址不为空时,循环输出p的数据域
        {
            p = p->next;               //p指向p的下一个地址
            cout << p->data << " ";
        }
    }
    
    //获取单链表的长度
    int LinkList::GetLength()
    {
        int count = 0;                  //定义count计数
        ElemType *p = head->next;           //定义p指向头结点
        while (p != NULL)                //当指针的下一个地址不为空时,count+1
        {
            count++;                  
            p = p->next;                //p指向p的下一个地址
        }
        return count;                   //返回count的数据
    }
    
    //判断单链表是否为空
    bool LinkList::IsEmpty()
    {
        if (head->next == NULL) {                 
            return true;
        }
        return false;
    }
    
    //查找节点
    ElemType * LinkList::Find(DataType data)
    {
        ElemType * p = head;
        if (p == NULL) {                           //当为空表时,报异常
            cout << "此链表为空链表" << endl;
            return ERROR;
        }
        else
        {
            while (p->next != NULL)               //循环每一个节点
            {
                if (p->data == data) {
                    return p;                     //返回指针域
                }
                p = p->next;
            }
            return NULL;                           //未查询到结果
        }
    }
    
    //在尾部插入指定的元素
    void LinkList::InsertElemAtEnd(DataType data)
    {
        ElemType * newNode = new ElemType;    //定义一个Node结点指针newNode
        newNode->next = NULL;         //定义newNode的数据域和指针域
        newNode->data = data;
        ElemType * p = head;              //定义指针p指向头结点
        if (head == NULL) {           //当头结点为空时,设置newNode为头结点
            head = newNode;
        }
        else                          //循环知道最后一个节点,将newNode放置在最后
        {
            while (p->next != NULL)
            {
                p = p->next;
            }
            p->next = newNode;
        }
    }
    
    //在指定位置插入指定元素
    void LinkList::InsertElemAtIndex(DataType data,int n)
    {
        if (n<1 || n>GetLength())                   //输入有误报异常
            cout << "输入的值错误" << endl;
        else
        {
            ElemType * ptemp = new ElemType;        //创建一个新的节点
            ptemp->data = data;                     //定义数据域
            ElemType * p = head;                    //创建一个指针指向头结点
            int i = 1;
            while (n > i)                           //遍历到指定的位置
            {
                p = p->next;
                i++;
            }
            ptemp->next = p->next;                 //将新节点插入到指定位置
            p->next = ptemp;
        }
    }
    
    //在头部插入指定元素
    void LinkList::InsertElemAtHead(DataType data)
    {
        ElemType * newNode = new ElemType;    //定义一个Node结点指针newNode
        newNode->data = data;
        ElemType * p = head;              //定义指针p指向头结点
        if (head == NULL) {           //当头结点为空时,设置newNode为头结点
            head = newNode;
        }
        newNode->next = p->next;          //将新节点插入到指定位置
        p->next = newNode;
    }
    
    //在尾部删除元素
    void LinkList::DeleteElemAtEnd()
    {
        ElemType * p = head;          //创建一个指针指向头结点
        ElemType * ptemp = NULL;      //创建一个占位节点
        if (p->next == NULL) {        //判断链表是否为空
            cout << "单链表空" << endl;
        }
        else
        {
            while (p->next != NULL)   //循环到尾部的前一个
            {
                ptemp = p;            //将ptemp指向尾部的前一个节点
                p = p->next;          //p指向最后一个节点
            }
            delete p;                //删除尾部节点
            p = NULL;
            ptemp->next = NULL;
        }
    }
    
    //删除所有数据
    void LinkList::DeleteAll()
    {
        ElemType * p = head->next;
        ElemType * ptemp = new ElemType;
        while (p != NULL)                    //在头结点的下一个节点逐个删除节点
        {
            ptemp = p;
            p = p->next;
            head->next = p;
            ptemp->next = NULL;
            delete ptemp;
        }
        head->next = NULL;                 //头结点的下一个节点指向NULL
    }
    
    //删除指定的数据
    void LinkList::DeleteElemAtPoint(DataType data)
    {
        ElemType * ptemp = Find(data);    //查找到指定数据的节点位置
        if (ptemp == head->next) {        //判断是不是头结点的下一个节点,如果是就从头部删了它
            DeleteElemAtHead();
        }
        else
        {
            ElemType * p = head;          //p指向头结点
            while (p->next != ptemp)      //p循环到指定位置的前一个节点
            {
                p = p->next;
            }
            p->next = ptemp->next;         //删除指定位置的节点
            delete ptemp;
            ptemp = NULL;               
        }
    
    }
    
    //在头部删除节点
    void LinkList::DeleteElemAtHead()
    {
        ElemType * p = head;
        if (p == NULL || p->next == NULL) {   //判断是否为空表,报异常
            cout << "该链表为空表" << endl;
        }
        else
        {
            ElemType * ptemp = NULL;      //创建一个占位节点
            p = p->next;
            ptemp = p->next;              //将头结点的下下个节点指向占位节点
            delete p;                     //删除头结点的下一个节点
            p = NULL;
            head->next = ptemp;           //头结点的指针更换
        }
    }
    
    //测试函数
    int main()
    {
        LinkList l;
        int i;
        cout << "1.创建单链表   2.遍历单链表   3.获取单链表的长度   4.判断单链表是否为空   5.获取节点\n";
        cout << "6.在尾部插入指定元素   7.在指定位置插入指定元素   8.在头部插入指定元素\n";
        cout<<"9.在尾部删除元素   10.删除所有元素   11.删除指定元素   12.在头部删除元素   0.退出" << endl;
        do
        {
            cout << "请输入要执行的操作: ";
            cin >> i;
            switch (i)
            {
            case 1:
                int n;
                cout << "请输入单链表的长度: ";
                cin >> n;
                l.CreateLinkList(n);
                break;
            case 2:
                l.TravalLinkList();
                break;
            case 3:
                cout << "该单链表的长度为" << l.GetLength() << endl;
                break;
            case 4:
                if (l.IsEmpty() == 1)
                    cout << "该单链表是空表" << endl;
                else
                {
                    cout << "该单链表不是空表" << endl;
                }
                break;
            case 5:
                DataType data;
                cout << "请输入要获取节点的值: ";
                cin >> data;
                cout << "该节点的值为" << l.Find(data)->data << endl;
                break;
            case 6:
                DataType endData;
                cout << "请输入要在尾部插入的值: ";
                cin >> endData;
                l.InsertElemAtEnd(endData);
                break;
            case 7:
                DataType pointData;
                int index;
                cout << "请输入要插入的数据: ";
                cin >> pointData;
                cout << "请输入要插入数据的位置: ";
                cin >> index;
                l.InsertElemAtIndex(pointData, index);
                break;
            case 8:
                DataType headData;
                cout << "请输入要在头部插入的值: ";
                cin >> headData;
                l.InsertElemAtHead(headData);
                break;
            case 9:
                l.DeleteElemAtEnd();
                break;
            case 10:
                l.DeleteAll();
                break;
            case 11:
                DataType pointDeleteData;
                cout << "请输入要删除的数据: ";
                cin >> pointDeleteData;
                l.DeleteElemAtPoint(pointDeleteData);
                break;
            case 12:
                l.DeleteElemAtHead();
                break;
            default:
                break;
            }
        }while (i != 0);
    
        system("pause");
        return 0;
    }

    积累积累。

    展开全文
  • 以下是对C++中单链表的建立与基本操作进行了详细的介绍,需要的朋友可以过来参考下,希望对大家有所帮助
  • c++链表基本操作

    2012-09-25 10:32:30
    通过链表的学习,可以较彻底地了解,学习以及操作较难理解的指针。
  • 链表基本操作C++实现

    千次阅读 2013-03-04 18:51:52
    主要实现双链表如下功能: void AddBack(T val); //链表尾部添加元素 void AddFront(T val); //链表头部添加元素 bool InsertAt(int pos, T val); //在指定的索引处插入元素 bool RemoveBack(); //尾部删除...

    主要实现双链表如下功能:

    void AddBack(T val);  //链表尾部添加元素

    void AddFront(T val);  //链表头部添加元素

    bool InsertAt(int pos, T val); //在指定的索引处插入元素

    bool RemoveBack(); //尾部删除元素

    bool RemoveFront(); //头部删除元素

    bool RemoveAt(int pos); //删除指定索引处元素

     

    bool Find(T val); //找到元素返回索引,没找到返回-1

    void Clear(); //清空链表

    bool IsEmpty();//判断链表是否为空

    int Size(); //返回链表元素个数

     

    1.定义链表节点类

    template<class T>

    class DNode

    {

    public:

    ~DNode(void){ }

     

    T val; //节点值

    DNode<T>* next; //指向后面节点指针

    DNode<T>* prior; //指向前面节点指针

    DNode(T nVal)

    {

    val = nVal;

    next = prior = NULL;

    }

    DNode(void){}

    };

     

     

    2.双链表类定义

    #include "DNode.h"

    #include <iostream>

    using namespace std;

     

    template<class T>

    class DLinkList

    {

    int size;

    public:

    DNode<T>* head; //指向头部的指针

    DNode<T>* tail; //指向尾部指针

    DLinkList(void)

    {

    head = tail = NULL;

    size = 0;

    }

    ~DLinkList(void){ Clear(); }

     

    void AddBack(T val)  //尾部添加元素

    {

    DNode<T>* pNode = new DNode<T>(val);

    if(head == NULL) //链表为空时

    {

    head = tail = pNode; 

    }

    else{

    tail->next = pNode; 

    pNode->prior = tail;

    tail = pNode; //新节点是尾部节点

    }

    size ++;

    }

     

    void AddFront(T val) //头部添加元素

    {

    DNode<T>* pNode = new DNode<T>(val);

    if(head == NULL) //链表为空时

    {

    head = tail = pNode;

    }

    else{

    head->prior = pNode;

    pNode->next = head;

    head = pNode;

    }

    size ++;

    }

     

    bool InsertAt(int pos, T val) //任意位置插入元素

    {

    DNode<T>* pNode = NULL;

    if(pos < 0 || pos > size){

    cout<<"out of range"<<endl;

    returnfalse;

    }

    pNode = new DNode<T>(val);

    if(pos == 0) // 头部位置

    AddFront(val);

    elseif(pos == size - 1)

    AddBack(val);

    else{

    DNode<T>* priorNode = GetPointerAt(pos - 1);

    pNode->next = priorNode->next;

    pNode->prior = priorNode;

    priorNode->next->prior = pNode;

    priorNode->next = pNode;

     

    }

    size++;

    return true;

    }

     

    bool RemoveAt(int pos) //删除指定索引处元素

    {

    DNode<T>* pNode =NULL;

    if(size == 0){

    cout<<"list is empty"<<endl;

    returnfalse;

    }

    if(pos < 0 || pos > size - 1){

    cout<<"out of range"<<endl;

    returnfalse;

    }

    if(size == 1)

    Clear();

    else{

    if(pos == 0) //头部位置

    {

    pNode = head;

    head = head->next;

    head->prior = NULL;

    delete pNode;

    }

    else{

    DNode<T>* priorNode = GetPointerAt(pos - 1);

    pNode = priorNode->next;

    priorNode->next = pNode->next;

    pNode->next->prior = priorNode;

    delete pNode;

    if(pos == size - 1) //如果是尾部元素

    tail = priorNode;

    }

    }

    }

     

    bool RemoveBack(){return RemoveAt(size - 1);}

     

    bool RemoveFront(){return RemoveAt(0);}

     

    int Find(T val)

    {

    int index = 0;

    DNode<T>* ip = head;

    while(ip != NULL){

    if(ip->val == val)

    return index;

    ip = ip->next;

    index++;

    }

    return -1;

    }

     

    bool IsEmpty(){return size == 0 ?true:false;}

    int Size(){return size;}

    void Clear(){

    while(head != NULL){

    DNode<T>* tmp = head->next;

    delete head;

    head = tmp;

    }

    tail = NULL;

    size = 0;

    }

     

    private:

    DNode<T>* GetPointerAt(int pos)

    {

    DNode<T>* pNode = NULL;

    if(pos < 0 || pos>size - 1)

    cout<<"out of range"<<endl;

    else{

    pNode = head;

    for(int i = 1; i<= pos; i++)

    pNode = pNode->next;

    }

    return pNode;

    }

    };

     

    展开全文
  • 下面小编就为大家带来一篇C++ 单链表的基本操作(详解)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 1.概念 双向链表也叫双链表,是链表的一种,它的每个...2.基本操作实例 DoubleList.cpp #include stdafx.h #include DoubleList.h #include #include #include DoubleList::DoubleList() { pDoubleListNode pDo
  • 使用C++语言,结合单链表的基本操作,实现二叉树的存储,前序、种序、后序遍历及其他基本操作
  • c++链表基本操作

    2018-11-18 20:16:26
    这篇博客主要讲述了用c++实现单链表的一些基本操作,主要实现了包括单链表的创建,打印链表,获取链表长度,在链表的第i个节点处插入值为e的节点,删除第i个节点,获取第i个节点的数据,在链表中搜索数据的功能。...

    最近在刷《剑指offer》的题目,才发现自己许多数据结构的知识都忘记了,正在恶补中。这篇博客主要讲述了用c++实现单链表的一些基本操作,主要实现了包括单链表的创建,打印链表,获取链表长度,在链表的第i个节点处插入值为e的节点,删除第i个节点,获取第i个节点的数据,在链表中搜索数据的功能。不多说,直接上代码。

    #include "stdafx.h"
    #include"stdio.h"
    #include<iostream>
    
    using namespace std;
    
    /*
    功能:实现对单链表的一些基本操作
    */
    
    struct node{
    	int value;
    	node* next;
    };
    
    //链表类
    class LinkList{
    private:
    	node* head;
    public:
    	LinkList();//构造函数,在创建对象时自动调用
    	void CreateLinkList(int n);//创建链表
    	void PrintLinkList();//打印链表
    	int Length();//获取链表长度
    	void Insert(int i,int e);//在链表的第i个节点处插入值为e的节点
    	void Delete(int i);//删除第i个节点
    	int GetValue(int i);//获取第i个节点的数据
    	bool SearchValue(int target);//在链表中搜索target
    };
    
    //构造函数
    LinkList::LinkList(){
    	//初始化头结点
    	head=new node;
    	head->next=NULL;
    }
    
    //创建链表
    //输入参数;n为节点数
    void LinkList::CreateLinkList(int n) {
    	node* temp;
    	node* p;
    	p=head;
    	cout<<"创建链表:"<<endl;
    	for(int i=0;i<n;i++){
    		cout<<"请输入第"<<i+1<<"个节点的整数值"<<endl;
    		temp=new node;
    		cin>>temp->value;
    		/*如果输入的数不为整数,输入流会出错*/
    		while(cin.fail()){
    			cout<<"输入的数据类型错误!请重新输入:"<<endl;
    			cin.clear();
    			cin.sync();
    			cin>>temp->value;
    		}
    		p->next=temp;
    		p=temp;
    	}
    	p->next=NULL;
    	cout<<"创建链表成功!"<<endl;
    }
    
    //打印链表
    void LinkList::PrintLinkList(){
    	node* p;
    	p=head->next;
    	if(p==NULL){
    		cout<<"链表为空!"<<endl;
    	}
    	else{
    		cout<<"打印链表:"<<endl;
    		while(p){
    			cout<<p->value<<" ";
    			p=p->next;
    		}
    		cout<<endl;
    	}
    
    }
    
    //获取链表长度
    int LinkList::Length(){
    	node* p;
    	p=head->next;
    	int length=0;
    	while(p!=NULL){
    		length++;
    		p=p->next;
    	}
    	return length;
    }
    
    //插入节点
    //输入参数:i为要插入的节点的位置(1=<i<=len+1),e的插入节点的数据
    void LinkList::Insert(int i,int e){
    	//先获取链表长度
    	int len=Length();
    	if(i<=0||i>len+1)
    		cout<<"输入的位置参数错误!";
    	else{
    		node* p;
    		node* temp;
    		p=head;
    		temp=new node;
    		temp->value=e;
    		int j=1;
    		//把p移动到节点i的前一个节点
    		while(j<i){
    			p=p->next;
    			j++;
    		}
    		temp->next=p->next;
    		p->next=temp;
    		cout<<"在"<<i<<"处插入节点成功!"<<endl;
    	}
    }
    
    //删除节点
    //输入参数:要删除的节点的位置
    void LinkList::Delete(int i){
    	//获取链表长度
    	int len=Length();
    	if(i<=0||i>len)
    		cout<<"输入的位置数据错误!"<<endl;
    	else{
    		node* p;
    		node* temp;
    		int j=1;
    		p=head;
    		//线将p移动到节点i的前一个节点
    		while(j<i){
    			p=p->next;
    			j++;
    		}
    		temp=p->next;
    		p->next=temp->next;
    		temp->next=NULL;
    		cout<<"删除"<<i<<"处节点成功!"<<endl;
    	}
    	
    }
    
    //获取第i个节点的数据
    //输入参数:要获取数据的节点位置
    int LinkList::GetValue(int i){
    	//获取链表长度
    	int len=Length();
    	if(i<=0||i>len){
    		cout<<"输入的位置参数错误!"<<endl;
    	}
    	else{
    		node* p;
    		//将p移动到第i个节点处
    		p=head;
    		int j=1;
    		while(j<=i){
    			p=p->next;
    			j++;
    		}
    
    		return p->value;
    	}
    
    }
    
    //在链表中搜索target,若找到则输出第一个出现该数据的节点的位置
    bool LinkList::SearchValue(int target){
    	node* p;
    	int i=1;
    	p=head->next;
    	while(p!=NULL){
    		if(p->value==target){
    			cout<<"链表中第一次出现该数据的节点位置为:"<<i<<endl;
    			return true;
    		}
    		p=p->next;
    		i++;
    	}
    	cout<<"链表中不存在该数据!"<<endl;
    	return false;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	LinkList list;
    	int num;
    	//创建链表
    	cout<<"输入要创建的链表的节点数:"<<endl;
    	cin>>num;
    	list.CreateLinkList(num);
    	cout<<endl;
    	//打印链表
    	list.PrintLinkList();
    	cout<<endl;
    	//获取链表长度
    	int len=list.Length();
    	cout<<"链表的节点数为:"<<len<<endl;
    	cout<<endl;
    	//插入节点,在第2个节点插入99
    	list.Insert(2,99);
    	cout<<endl;
    	//打印链表
    	list.PrintLinkList();
    	cout<<endl;
    	//删除第2个节点
    	list.Delete(2);
    	cout<<endl;
    	//打印链表
    	list.PrintLinkList();
    	cout<<endl;
    	//获取第i个节点的值
    	int id;
    	cout<<"请输入要查询数据的节点位置:"<<endl;
    	cin>>id;
    	int value=list.GetValue(id);
    	cout<<"第"<<id<<"个节点的值为:"<<value<<endl;
    	cout<<endl;
    	//搜索数据
    	int target;
    	cout<<"输入待搜索的数据:"<<endl;
    	cin>>target;
    	bool r=list.SearchValue(target);
    	cout<<endl;
    
    	return 0;
    }
    

    运行程序进行测试的结果如下:
    在这里插入图片描述

    展开全文
  • 利用C++实现双向链表基本操作

    千次阅读 2019-07-25 19:15:22
    本文采用利用C++实现了对双向链表基本操作。操作包括:双向链表的构建、链表指定位置的插入、链表指定位置的删除、链表长度的获取、链表指定位置元素的获得及指定元素位置的获得、整体链表的删除。

    利用C++实现双向链表的基本操作

    本文采用利用C++实现了对双向链表的基本操作。操作包括:双向链表的构建、链表指定位置的插入、链表指定位置的删除、链表长度的获取、链表指定位置元素的获得及指定元素位置的获得、整体链表的删除。

    双向链表是链表的另一种形式,它的结点特点是每个结点包括两个指针域和一个数据域,两个指针域Prior和Next分别指向该结点的前驱和后继元素。双向结点的结构如下图所示。
    双向链表结点
    双向链表除了头结点没有前驱和尾结点没有后继外,其他结点都有前驱结点和后驱结点,其结构下图所示。
    双向链表结构
    从图中的结构可以清楚的看到,双向链表可以从任何一个结点到达链表的头结点和尾结点。双向链表与单链表的操作过程类似,都可已进行插入、删除、获取、以及清空等基本操作。利用C++实现的具体代码如下。

    #include<iostream>
    
    using namespace std;
    
    template<typename datatype> class doubleLink;       //双向链表声明
    /***************************************双向链表数据结构定义*************************************************/
    template<typename datatype>class doubleNode
    {
    public:
    
    	//无参数构造函数,将指针域初始化为NULL
    	doubleNode()
    	{
    		p_prior = NULL;
    		p_next = NULL;
    	}
       //带参数的构造函数,初始化数据域与指针域
    	doubleNode(datatype item, doubleNode<datatype> * prior=NULL, doubleNode<datatype> * next=NULL)
    	{
    		data = item;
    		p_prior = prior;
    		p_next = next;
    	}
    	//析构函数
    	~doubleNode()
    	{
    		p_prior = NULL;
    		p_next = NULL;
    	}
    
    private:
    	doubleNode<datatype> *p_prior;                         //指向前节点的指针
    	doubleNode<datatype> *p_next;                          //指向后节点的指针
    	datatype data;                                         //自身节点的数据
    	int length;                                            //链表长度
    	//定义友元类
    	friend  class doubleLink<datatype>;
    };
    /***************************************双向链表定义*************************************************/
    template<typename datatype>class doubleLink
    {
    public:
    	//双向链表的构造函数,链表产生新头结点
    	doubleLink()
    	{
    		head = new doubleNode<datatype>();                  //链表产生新头结点
    	}
    	//双向链表的构造函数,链表产生新头结点
    	doubleLink(doubleNode<datatype>*note)
    	{
    		head = note;
    	}
    	//双向链表的析构函数,链表删除头节点
    	~doubleLink()
    	{
    		delete head;
    	}
    public:
    	void cleandoubleLink();                                 //清空双向链表
    	int  getLength();                                       //获取链表长度
    	int  findData(datatype item);                           //寻找给定数值的结点
    	bool insertNode(datatype item,int n);                   //在i个结点插入datatype类型item
    	bool deleteNode(int n);                                 //删除第i个结点的数据
    	datatype getData(int n);                                //获取第i个结点的数据
    private:
    	doubleNode<datatype> * head;                            //头指针
    };
    /********************************************清空双向链表*************************************************/
    template<typename datatype>
    void doubleLink<datatype>::cleandoubleLink()
    {
    	doubleNode<datatype> *P_move = head->p_next, *P_middle;  //设置游标指针   
    	while (P_move!=NULL)                                     //判断头指针后面的结点
    	{
    		P_middle = P_move;
    		P_move = P_middle->p_next;                           //游标指针借助中间指针向后移
    		delete P_middle;                                     //删除中间指针,即删除后面的结点
    	}
    	head->p_next = NULL;                                     //将头指针的指向空
    }
    /********************************************获取链表长度*************************************************/
    template<typename datatype>
    int doubleLink<datatype>::getLength()
    {
    	doubleNode<datatype> *P_move = head->p_next;             //设置游标指针
    	int length=0;
    	//遍历链表,计算结点数
    	while(P_move!=NULL)
    	{
    		P_move = P_move->p_next;                            //游标指针后移
    		length++;                                           //计算length
    	}
    	return length;
    }
    /***************************************寻找给定数值的结点*************************************************/
    template<typename datatype>
    int doubleLink<datatype>::findData(datatype item)
    {
    	doubleNode<datatype> *P_move = head;             //设置游标指针
    	if (P_move->p_next==NULL)
    	{
    		cout << "当前链表为空链表!" << endl;
    		return 0;
    	}
    	int length = 0;                     
    	while (P_move->data!= item)
    	{
    		P_move = P_move->p_next;                             //游标指针后移
    		length++;
    	}
    	return length;
    }
    /************************************在i个结点插入datatype类型item*****************************************/
    template<typename datatype>
    bool doubleLink<datatype>::insertNode(datatype item, int n)
    {
    
      if (n<1)
      {
    	cout << "输入非有效位置" << endl;
    	return false;
    		}
      doubleNode<datatype>  * P_move = head;             //创建新指针,并设置游标指针
      
      //找到插入位置
      for (int i = 1; i <n; i++)
      {
    	  P_move = P_move->p_next;                                                                      //游标指针后移
    	  if (P_move==NULL&&i<=n)
    	  {
    		  cout << "插入位置无效" << endl;
    		  return false;
    	  }
      }
      doubleNode<datatype> * newNode = new doubleNode<datatype>(item);
      //插入新结点
      if (newNode == NULL)
      {
    	  cout << "内存分配失败,新结点无法创建" << endl;
    	  return false;
      }
      newNode->p_next= P_move->p_next;   
      if (P_move->p_next!=NULL)
      {
    	  P_move->p_next->p_prior = newNode;
      }
      newNode->p_prior = P_move;
      P_move->p_next = newNode;
      return true;
    }
    /***************************************删除第i个结点的数据*************************************************/
    template<typename datatype>
    bool doubleLink<datatype>::deleteNode(int n)
    {
    	if (n<1||n>getLength())
    	{
    		cout << "输入非有效位置" << endl;
    		return false;
    	}
    	doubleNode<datatype> * P_move = head,* p_delete;             //设置游标指针
    	//查找删除结点的位置
    	for (int i = 1; i <= n; i++)
    	{
    		P_move = P_move->p_next;                                         //游标指针后移
    	}
    	//删除结点
    	p_delete = P_move;      
    	P_move->p_prior->p_next = p_delete->p_next;
    	P_move->p_next->p_prior = p_delete->p_prior;
    	delete p_delete;
    	return true;
    }
    /***************************************获取第i个结点的数据*************************************************/
    template<typename datatype>
    datatype doubleLink<datatype>::getData(int n)
    {
    	if (n<1|| n>getLength())
    	{
    		cout << "输入非有效位置" << endl;
    		return 0;
    	}
    	doubleNode<datatype> * P_move = head;             //设置游标指针
    	for (int i = 1; i<=n; i++)
    	{
    		P_move = P_move->p_next;                                         //游标指针后移
    	}
    	if (P_move==NULL)
    	{
    		cout << "没有所要查找的结点" << endl;
    		return 0;
    	}
    	return P_move->data;
    }
    /***************************************************主函数***************************************************/
    int main()
    {
    
    	doubleNode<int> Note;
    	doubleLink<int> Link(&Note);
    	cout << "*******************************操作选择*******************************" << endl;
    	cout << "1.产生链表" << endl;
    	cout << "2.给链表中插入元素" << endl;
    	cout << "3.删除链表中的元素" << endl;
    	cout << "4.获取链表中的元素" << endl;
    	cout << "5.获取链表中的数据位置" << endl;
    	cout << "6.清空链表中的元素" << endl;
    	cout << "**********************************************************************" << endl;
    	while (1)
    	{
    		int Opera_Number;
    		cin >> Opera_Number;
    		switch (Opera_Number)
    		{
    			//产生链表
    		   case 1:
    		  {
    			   int doubleLink_Number;
    			   cout << "输入你需要的链表长度:" << endl;
    			   cin >> doubleLink_Number;
    			   for (int i = 1; i <=doubleLink_Number; i++)
    			   {
    				   Link.insertNode(i*11,i);
    			   }
       cout << "*****************************当前链表为********************************" << endl;
    			   for (int i = 1; i <=doubleLink_Number; i++)
    			   {
    				   cout << Link.getData(i) << "  ";
    			   }
    			   break;
    		            }
    		  //给链表中插入元素
    		   case 2:
    		   {
    			   int insert_Number, insert_Data;
    			   cout << "输入插入位置点:" << endl;
    			   cin >> insert_Number;
    			   cout << "输入插入数据:" << endl;
    			   cin >> insert_Data;
    			   Link.insertNode(insert_Data, insert_Number);
    			   cout << "*****************************当前链表为********************************" << endl;
    			   for (int i = 1; i <=( Link.getLength()); i++)
    			   {
    				   cout << Link.getData(i) << "   ";
    			   }
    			   break;
    		   }
    		   //删除链表中的元素
    		   case 3:
    		   {
    			   int delete_Number;
    			   cout << "输入删除位置点:" << endl;
    			   cin >> delete_Number;
    			   Link.deleteNode(delete_Number);
    			   cout << "*****************************当前链表为********************************" << endl;
    			   for (int i = 1; i <= (Link.getLength()); i++)
    			   {
    				   cout << Link.getData(i) << "  ";
    			   }
    			   break;
    		   }
    		   //获取链表中的元素
    		   case 4:
    		   {
    			   int get_Number;
    			   cout << "输入获取位置点:" << endl;
    			   cin >> get_Number;
    			   cout << "获取到的数据:" << Link.getData(get_Number) << endl;
    			   break;
    		   }
    		  //获取链表中的数据位置
    		   case 5:
    		   {
    			   int data;
    			   cout << "输入想查询的数据:" << endl;
    			   cin >> data;
    			   if ((Link.findData(data)!=0))
    			   {
    				   cout << "该数据在链表中的位置为:" << Link.findData(data) << endl;
    			   }
    			   break;
    		   }
    		   //清空链表中所有的元素
    		   case 6:
    		   {
    			   cout << "删除前的链表长度:" << Link.getLength() << endl;
    			   Link.cleandoubleLink();
    			   cout << "删除后的链表长度:" << Link.getLength() << endl;
    			   break;
    		   }
    		   //未在操作数范围内
    		   default:
    		   {
    			   cout << "输入操作数未在操作数范围内" << endl;
    			   break;
    		   }
    		}
    	}
    	return 0;
    }
    
    

    代码在创建过程中,主要参照了由胡浩主编的《妙趣横生的算法》的搭建方式与搭建方法。在编程的过程中,我认为我遇到的比较核心的主要有两点:
    1.游标指针的设置:通过游标指针的后移,可以帮助我们很方便的对结点从头结点后进行查找。
    2.链表的插入、删除的基本算法的理解:插入与删除的基本算法说到底就是对前驱指针和后继指针的设置,只要将这两个指针域搞清楚了,基本操作也就掌握了。(ps:如果想详细了解,将insertNode函数、deleteNode函数多看几遍即可。)

    零零散散就写这么多,程序自己亲自跑了一遍,感觉没什么太大的问题。大家如果看的过程中有什么问题,也欢迎大家相互交流!!

    展开全文
  • C++链表基本操作

    万次阅读 多人点赞 2019-06-16 20:12:56
    链表基本操作定义基本操作1. 插入节点2. 删除节点3. 反转链表4. 倒数第K个节点5. 是否有环 本文所述均为单向链表。 定义 struct ListNode{ int val; struct ListNode* next; LsiatNode(int val): val(x), ...
  • (1)定义双向链表基本结构 代码如下:typedef struct _DOUBLE_LINK_NODE { int data; struct _DOUBLE_LINK_NODE* prev; struct _DOUBLE_LINK_NODE* next; }DOUBLE_LINK_NODE;  (2)创建双向链表节点 代码...
  • C++链表的12种基本操作

    千次阅读 多人点赞 2019-12-16 20:16:29
    定义:链表是一种动态数据结构,他的特点是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放数据元素。链表中每一个元素成为“结点”,每一个结点都是由数据域和指针域组成的,每个结点中的指针域指向下...
  • 链表基本操作源码

    2017-12-28 19:12:20
    c 语言 链表基本操作,创建 查找 删除 插入 双向链表源码
  • C++实现线性链表基本操作

    千次阅读 2017-01-10 13:55:06
    C++实现顺序结构线性表的基本操作
  • 这是链表操作中比较基本操作,我是模仿单向链表来进行双向链表的构建,其插入和删除操作也和单向链表大同小异,代码并不晦涩难懂,适合新手研读,有错误或者不够完善的希望大家指出。 #include "pch.h" #include...
  • 期末课程设计题目,使用C++实现关于链表基本操作,本人也是学生,初学,写的不好,仅供参考。
  • C++实现链表基本操作

    万次阅读 多人点赞 2016-01-10 21:56:57
    前几天找实习的时候,一个面试官给我留了一个题,做一个链表demo,要求实现创建、插入、删除等操作链表是一种常见的数据结构,它是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中...
  • C++ STL list链表基本操作

    千次阅读 2018-09-28 20:53:27
    #include&... //双向链表 //#include&lt;forward_list&gt; //单向链表 头 C11 #include&lt;algorithm&gt; using namespace std; struct Node { int a; char c; }; void fun(No...
  • linklist 链表基本操作c++,实现添加数据,删除,查找,插入等功能,顺利通过
  • C/C++ 链表详解

    2019-11-15 09:04:52
    冗余的话不多说,直接实际操作。 一、 合并成有序链表 说明: 已知两个有序链表,自定义函数把这两个链表合并成一个依然有序的链表。 注意: 以下代码,可以按序全部拷贝到开发工具中(有时会遇到版本兼容性问题)。 1...
  • C++链表基本操作大全

    2010-03-23 05:45:41
    C++链表基本(创建、插入、删除、释放)
  • C++单链表基本操作

    千次阅读 多人点赞 2018-07-02 20:21:07
    #include &lt;iostream&gt; using namespace std; struct NODE { int data; NODE * next; }; class List ...则表示不带头结点的链表,只有头指针 List() { head = new NODE; head-&gt...
  • 实例讲解C++链表基本操作

    千次阅读 2016-04-26 08:09:28
    1.概念  双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个...2.基本操作实例   DoubleList.cpp #include "stdafx.h
  • 数据结构双链表基本操作(C/C++实现) 注意:本代码为了测试运行默认含有操作所需数据,如有需要可自己增删改相关数据 涉及基本运算 初始化双链表 依次采用尾插法插入元素 输出双链表 输出双链表的长度 判断双链表...
  • 【源代码】C++实现单链表的基本操作(严蔚敏数据结构)包括基本的插入删除获取长度,清空等操作,还有更重要的单链表合并,连接,多项式运算等。需要说明的是我用的VS2017,低版本的复制粘贴就好

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,698
精华内容 25,079
关键字:

链表的基本操作c++

c++ 订阅