精华内容
下载资源
问答
  • 单链表简单介绍 单链表是线性表的一种,其逻辑结构为线性结构...单链表数据结构 typedef struct pe{ string name; string sex; int age; bool operator ==(const pe &p)//重载==运算符 { return(p.name==name&

    单链表简单介绍

    单链表是线性表的一种,其逻辑结构为线性结构,采用链式存储结构,不同于顺序表既能顺序存取又可随机存取,单链表只能顺序存取。优点是添加和删除元素方便,时间复杂度为O(1),缺点是查找元素比较麻烦,需从头指针开始遍历,时间复杂度为O(n)。

    单链表数据结构

    typedef struct pe{
        string name;
        string sex;
        int age;
        bool operator ==(const pe &p)//重载==运算符
        {
            return(p.name==name&&p.sex==sex&&p.age==age);
        }
    }people; //自定义数据类型
    typedef struct LNode
    {
        people data; //结点的数据域
        LNode *next; //结点的指针域
    }LNode,*LinkList;//LinkList为指向结构体LNode的指针类型
    

    单链表常用操作

    Status InitList(LinkList &L);//初始化单链表
    void List_HeadCreate(LinkList &L,int n);//采用头插法建立单链表
    void List_TailCreate(LinkList &L,int n);//采用尾插法正向建立单链表
    LNode *GetElem(LinkList &L,int i);//按序号查找
    void ListInsert(LinkList &L,int i,people e);//插入
    void ListDelete(LinkList &L,int i);//删除
    void Print(LinkList L);//打印
    

    具体操作实现

    • 初始化
    //初始化
    Status InitList(LinkList &L)
    {
        L=new LNode;//生成一个新结点,头指针L指向头结点
        L->next=NULL;//头结点的指针域置空
        return OK;
    }
    
    • 头插法创建单链表
    //头插法创建单链表
    void List_HeadCreate(LinkList &L,int n)
    {
        L=new LNode;//生成一个新结点,头指针L指向头结点
        L->next=NULL;//头结点的指针域置空
        for(int i=0;i<n;i++)
        {
            LNode *p=new LNode;//生成新结点*p
            people e;
            cout<<"Please Input the data:";
            cin>>e.name>>e.sex>>e.age;
            p->data=e;
            p->next=L->next;L->next=p;//将新结点插入到头结点之后
        }
        cout<<"Succeed"<<endl;
    }
    
    • 尾插法创建单链表
    //尾插法创建单链表
    void List_TailCreate(LinkList &L,int n)
    {
        InitList(L);
        LinkList r=L;//尾指针指向头结点
        for(int i=0;i<n;i++)
        {
            LNode *p=new LNode;
            people e;
            cout<<"Please Input the data:";
            cin>>e.name>>e.sex>>e.age;
            p->data=e;
            r->next=p;p->next=NULL;//将新结点插入到尾结点之后
            r=p;//r指向新的尾结点
        }
        cout<<"Succeed"<<endl;
    }
    
    • 按序号查找
    //按序号查找
    LNode *GetElem(LinkList &L,int i)
    {
        LNode *p=new LNode;
        p=L->next;//头结点指针赋值给p,p指向首元结点
        int j=1;//计数器,推动链表向后查找
        if(i==0)
            return L;
        if(i<0)//若i无效,则返回NULL
            return NULL;
        while(p!=NULL && j<i)//从第一个结点向后查找
        {
            p=p->next;
            j++;
        }
        return p;//找到则返回p指针,否则返回NULL
    }
    
    • 在第i个结点后插入元素
    //在第i个结点后插入
    void ListInsert(LinkList &L,int i,people e)
    {
        LNode *p=GetElem(L,i-1);//查找第i-1个结点
        if(p)
        {
            LNode *s=new LNode;
            s->data=e;
            s->next=p->next;
            p->next=s;//修改结点的指针域,完成插入操作
            cout<<"Succeed in inserting!"<<endl;
        }
        else
        {
            cout<<"The location is invalid!"<<endl;
        }
    }
    
    • 删除第i个结点
    //删除第i个结点
    void ListDelete(LinkList &L,int i)
    {
        LNode *p=GetElem(L,i-1);
        if(p)
        {
            LNode* q=p->next;//令q指向要删除的结点
            p->next=q->next;//将q结点从链中移出
            delete q;//释放结点的存储空间
        }
         else
            cout<<"The location is invalid!"<<endl;
    }
    
    • 打印单链表
    void Print(LinkList L)
    {
        LNode *p=L->next;
        if(!p)
        {
            cout<<"This is a empty Lnode!"<<endl;
        }
        while(p)
        {
            cout<<p->data.name<<","<<p->data.sex<<","<<p->data.age<<endl;
            p=p->next;
        }
    }
    
    展开全文
  • 数据结构单链表的基本操作及实现(C/C++),包括初始化、创建链表、插入元素、删除元素、获取指定位置的元素等
  • 【源代码】C++实现单链表的基本操作(严蔚敏数据结构)包括基本的插入删除获取长度,清空等操作,还有更重要的单链表合并,连接,多项式运算等。需要说明的是我用的VS2017,低版本的复制粘贴就好
  • #include<iostream> #include<algorithm> #include<vector> using namespace std; template<class datatype> class node; template<class datatype> class LinkList ... int...
    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    template<class datatype>
    class node;
    
    template<class datatype>
    class LinkList
    {
    private:
    	int len;
    	node<datatype> *head;
    public:
    	LinkList();//不带参数的构造函数
    	LinkList(datatype x,int n);//初始化有n个val为x的链表
    	datatype GetElem(int n);//取链表中第n个元素的值
    	int FindElem(datatype value);//找链表中是否存在value的元素,存在返回pos,反之返回-1表示未找到
    	void topinsert(datatype value);//头插法插入元素
    	void backinsert(datatype value);//尾插法插入元素
    	datatype getNthFromEnd(int n);//获取倒数第n个元素的值
    	void removeNthFromEnd(int n);//删除链表倒数第n个元素
    	void removeNthFromStart(int n);//删除链表第n个元素
    	void sortLink1();//排序链表1;
    	void sortLink2();//排序链表2;
    	node<datatype> * mergesort(node<datatype> *node1);
    	node<datatype> * merge(node<datatype>* l1, node<datatype>* l2);
    	void reverseList();//反转链表
    	bool judgeequal(LinkList &a);//判断两个链表是否相等
    	int getlen() //返回链表长度
    	{
    		return len;
    	};
    	friend ostream &operator<<(ostream &output, const LinkList &D)//重载输出流
    	{
    		if (D.len == 0)
    		{
    			cout << "LinkList is empty" << endl;
    			exit(1);
    		}
    		node<datatype> *p = D.head->next;
    		for (int i = 1; i <= D.len; i++)
    		{
    			output << p->val << ' ';
    			p = p->next;
    		}
    		cout << endl;
    		return output;
    	}
    	~LinkList();//析构函数
    };
    
    template<class datatype>
    class node
    {
    	node() {};
    	friend class LinkList<datatype>;
    public:
    	datatype val;
    	node<datatype> * next;
    	node(datatype x) : val(x), next(NULL) {};
    };
    
    //不带参数的构造函数
    template<class datatype>
    LinkList<datatype>::LinkList()
    {
    	head = new node<datatype>;
    	len = 0;
    	head->next = NULL;
    }
    
    //初始化有n个val为x的链表
    template<class datatype>
    LinkList<datatype>::LinkList(datatype x, int n)
    {
    	head = new node<datatype>;
    	len = n;
    	head->next = NULL;
    	node<datatype> *p = head;
    	for (int i = 0; i < n; i++)
    	{
    		p->next = new node<datatype>(x);
    		p = p->next;
    	}
    }
    
    //析构函数
    template<class datatype>
    LinkList<datatype>::~LinkList()
    {
    	node<datatype> *p1 = head, *p2;
    	while (p1 != NULL)//排着释放
    	{
    		p2 = p1->next;
    		delete p1;
    		p1 = p2;
    	}
    }
    
    //取链表中第n个元素的值
    template<class datatype>
    datatype LinkList<datatype>::GetElem(int n)
    {
    	if (n > len || n < 1)
    	{
    		cerr << "取值有误";
    		return -1;
    	}
    	else
    	{
    		node<datatype> *p = head;
    		for (int i = 0; i < n; i++)
    		{
    			p = p->next;
    		}
    		datatype value = p->val;
    		return value;
    	}
    }
    
    //找链表中是否存在value的元素,存在返回pos,反之返回-1表示未找到
    template<class datatype>
    int LinkList<datatype>::FindElem(datatype value)
    {
    	node<datatype> *p = head->next;
    	int pos = 1;
    	while (p)
    	{
    		if (p->val == value)
    			return pos;
    		else
    		{
    			p = p->next;
    			pos++;
    		}
    	}
    	return -1;
    }
    
    //头插法插入元素
    template<class datatype>
    void  LinkList<datatype>::topinsert(datatype value)
    {
    	node<datatype> *p = new node<datatype>(value);
    	node<datatype> *k = head->next;
    	head->next = p;
    	p->next = k;
    	len++;
    }
    
    //尾插法插入元素
    template<class datatype>
    void LinkList<datatype>::backinsert(datatype value)
    {
    	node<datatype> *p = head;
    	for (int i = 0; i < len; i++)
    	{
    		p = p->next;
    	}
    	p->next = new node<datatype>(value);
    	len++;
    }
    
    //获取倒数第n个元素的值
    template<class datatype>
    datatype LinkList<datatype>::getNthFromEnd(int n)
    {
    	if (n > len || n < 0)
    	{
    		cerr << "取值有误";
    		return -1;
    	}
    	else if (n == len)
    		return head->next->val;
    	else
    	{
    		node<datatype> *p = head->next;
    		for (int i = 0; i < len - n; i++)
    		{
    			p = p->next;
    		}
    		return p->val;
    	}
    }
    
    //删除倒数第n个元素的值
    template<class datatype>
    void LinkList<datatype>::removeNthFromEnd(int n)
    {
    	if (n > len || n < 0)
    	{
    		cerr << "取值有误" << endl;
    	}
    	else
    	{
    		if (n == len)
    		{
    			node<datatype> *p = head->next;
    			head->next = head->next->next;
    			delete p;
    		}
    		else if (n == 1)
    		{
    			node<datatype> *p = head->next;
    			for (int i = 1; i < len - 1; i++)
    			{
    				p = p->next;
    			}
    			node<datatype> *k = p->next;
    			p->next = NULL;
    			delete k;
    		}
    		else
    		{
    			node<datatype> *p = head;
    			for (int i = 0; i < len - n; i++)
    			{
    				p = p->next;
    			}
    			node<datatype> *k = p->next;
    			p->next = p->next->next;
    			delete k;
    		}
    		len--;
    	}
    }
    
    //删除第n个元素的值
    template<class datatype>
    void LinkList<datatype>::removeNthFromStart(int n)
    {
    	if (n<0 || n>len)
    		cerr << "取值有误" << endl;
    	else
    	{
    		if (n == 1)
    		{
    			node<datatype> *p = head->next;
    			head->next = head->next->next;
    			delete p;
    		}
    		else if (n == len)
    		{
    			node<datatype> *p = head->next;
    			for (int i = 1; i < len - 1; i++)
    			{
    				p = p->next;
    			}
    			node<datatype> *k = p->next;
    			p->next = NULL;
    			delete k;
    		}
    		else
    		{
    			node<datatype> *p = head;
    			for (int i = 0; i < n-1; i++)
    			{
    				p = p->next;
    			}
    			node<datatype> *k = p->next;
    			p->next = p->next->next;
    			delete k;
    		}
    		len--;
    	}
    }
    
    //反转链表
    template<class datatype>
    void LinkList<datatype>::reverseList()
    {
    	if (!(head == NULL || head->next == NULL))
    	{
    		node<datatype> *p = head->next;//遍历节点的上一个节点
    		node<datatype> *k = p->next;//当前遍历节点
    		head->next->next = NULL;
    		head->next = NULL;//更改头
    		while (k)
    		{
    			node<datatype> *temp = k->next;//临时节点保存下一个遍历节点
    			k->next = p;
    			p = k;
    			k = temp;
    		}
    		head->next = p;
    	}
    }
    
    //排序1
    template<class datatype>
    void LinkList<datatype>::sortLink1()
    {
    	vector<datatype> temp;
    	node<datatype> *p = head->next;
    	for (int i = 0; i < len; i++)
    	{
    		temp.push_back(p->val);
    		p = p->next;
    	}
    	sort(temp.begin(), temp.end());
    	p = head->next;
    	for (int i = 0; i < len; i++)
    	{
    		p->val = temp[i];
    		p = p->next;
    	}
    }
    
    //排序2
    template<class datatype>
    void LinkList<datatype>::sortLink2()
    {
    	head->next=mergesort(head->next);
    }
    
    template<class datatype>
    node<datatype> * LinkList<datatype>::mergesort(node<datatype>*node1)
    {
    	if (!node1 || !node1->next) return node1;
    	node<datatype> *fast = node1;//快指针走两步
    	node<datatype> *slow = node1;//慢指针走一步
    	node<datatype> *brek = node1;//断点
    	while (fast && fast->next)
    	{
    		fast = fast->next->next;
    		brek = slow;
    		slow = slow->next;
    	}
    	brek->next = nullptr;
    	node<datatype> *l1 = mergesort(node1);
    	node<datatype> *l2 = mergesort(slow);
    	return merge(l1, l2);
    }
    
    template<class datatype>
    node<datatype> * LinkList<datatype>::merge(node<datatype>* l1, node<datatype>* l2)
    {
    	if (l1 == NULL)
    	{
    		return l2;
    	}
    	if (l2 == NULL)
    	{
    		return l1;
    	}
    	if (l1->val < l2->val)
    	{
    		l1->next = merge(l1->next, l2);
    		return l1;
    	}
    	else
    	{
    		l2->next = merge(l2->next, l1);
    		return l2;
    	}
    }
    
    //判断两个链表是否相等
    template<class datatype>
    bool LinkList<datatype>::judgeequal(LinkList &a)
    {
    	if (a.getlen() != len)
    		return false;
    	else
    	{
    		node<datatype> *q = a.head->next;
    		node<datatype> *k = head->next;
    		for (int i = 0; i < len; i++)
    		{
    			if (q->val != k->val)
    				return false;
    			q = q->next;
    			k = k->next;
    		}
    		return true;
    	}
    }
    int main()
    {
    	//测试
    	LinkList<int> A;
    	//LinkList<int> B(1,3);
    	LinkList<int> B;
    	//A.topinsert(2);
    	//A.topinsert(1);
    	//A.topinsert(3); 
    	//A.topinsert(0);
    	A.backinsert(2);
    	A.backinsert(3);
    	A.backinsert(1);
    	A.backinsert(1);
    	B.backinsert(2);
    	B.backinsert(3);
    	B.backinsert(1);
    	B.backinsert(1);
    	cout << "此时链表A元素有:" << A;
    	cout << "此时的链表A长度为" << A.getlen() << endl;
    	cout << "此时链表A的倒数第二个元素为" << A.getNthFromEnd(2) << endl;
    	cout << "此时链表B元素有:" << B;
    	//A.removeNthFromEnd(3);
    	//A.removeNthFromStart(4);
    	//A.reverseList();
    	//A.sortLink1();
    	//A.sortLink2();
    	cout << A;
    
    	if (A.judgeequal(B))
    		cout << "两个链表相等" << endl;
    	else cout << "两个链表不相等" << endl;
    	if (A.FindElem(3) != -1)
    	{
    		cout << "找到该元素,在第"<< A.FindElem(3)<<"个位置" << endl;
    	}
    	else cout << "未找到该元素" << endl;
    	if (A.FindElem(1) != -1)
    	{
    		cout << "找到该元素,在第" << A.FindElem(1) << "个位置" << endl;
    	}
    	else cout << "未找到该元素" << endl;
    	//cout << A.GetElem(1) << " " << A.GetElem(2) << endl;
    	//cout << A.GetElem(3) << endl;
    	//A.~LinkList();
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 很多刚接触数据结构的小白在学完单链表,只知道理论知识,却不知道如何实现,这是用c++语言实现的两种单链表初始化过程
  • 数据结构----单链表C++实现)

    千次阅读 2019-03-17 00:46:57
    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储...

    简介

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

    代码(可在main方法中调用运行)

    //单链表基本操纵的实现(包含头结点)
    #include<iostream>
    #define OK 1
    #define ERROR 0
    using namespace std;
    typedef int ElemType;
    typedef int Status;//Status为函数类型,其值是函数结果状态代码,如OK等(状态代码:return OK插入成功,提高代码的可读性,我这里偷懒未使用)
    //单链表的存储结构
    typedef struct LNode
    {
        ElemType data;          //结点的数据域
        struct LNode* next;     //结点的指针域(指向下一个结点)
    }LNode,*LinkList;           //LNode为单链表的结点,LinkList为指向结点LNode的指针(LNode*与LinkList等价,这样使用是为了更好地区分链表与结点)
    
    /*
    作者理解(有误请大佬指出):
    这是定义一个结构体,这个结构体有两个属性,
    一个是ElemType类型的data;
    另一个是这个结构体类型的指针next;
    给这个结构定义了一个别名:LNode,一个指针的别名:LinkList;
    LNode a; 等价于 struct node a;
    都是声明一个struct node结构体类型的结构体变量 a;
    LinkList b; 等价于 struct LNode *b;等价于 LNode *b;
    但是为了提高代码的可读性,我们用LinkList声明链表eg:LinkList L
    声明一个struct LNode结构体类型的指针变量 b(这个指针变量指向结点LNode);
    重要:
    LNode* p=L->next;//这是新建一个指针名叫p,它指向的是首元结点。
    即:p代表首元结点的地址,*p就代表指向这个地址p,这里可理解为*p就是首元结点
    */
    
    //单链表的初始化,这里的L为指向头结点的头指针
    void InitList(LinkList &L)
    {//构造一个空的单链表L
        L=new LNode;    //生成新的结点作为头结点,用头指针L指向头结点(这时候L就代表该单链表)
        L->next=NULL;   //头结点的指针域置空
    }
    //前插法创建单链表
    void CreateList_H(LinkList &L,int n)
    {//逆位序输入n个元素的值,建立带表头结点的单链表L
        for(int i=0;i<n;++i)
        {
            LNode* p=new LNode;//生成新结点指针p
            cout<<"请输入第"<<n-i<<"个元素:";
            cin>>p->data;
            //所有插入元素都插入到头结点之后
            p->next=L->next;
            L->next=p;
        }
    }
    
    //后插法创建单链表
    void CreateList_R(LinkList &L,int n)
    {
        LNode* r=L;//尾指针r指向头结点
        for(int i=0;i<n;++i)
        {
            LNode* p=new LNode;//生成新的结点
            cout<<"请输入第"<<i+1<<"个元素:";
            cin>>p->data;
            p->next=NULL;//将新结点的指针域置空
            r->next=p;//将新结点*p插入尾结点*r之后
            r=p;
        }
    }
    
    //单链表的取值
    ElemType GetElem(LinkList L,int i)
    {
        LNode* p=L->next;//初始化p使p指向首元结点
        int j=1;
        while(p&&j<i)
        {
            p=p->next;//p指向下一结点(例如:p指向第2个结点)
            ++j;//相应计数器加1(那么相应的j的计数就为2)
        }
        if(!p||j>i)
        {
            cout<<"i的值不合法!\n"<<endl;
            return ERROR;
        }
        return p->data;
    }
    
    //单链表的按值查找,返回值为找到的元素结点的指针
    LNode* LocateElem(LinkList L,ElemType e)
    {
        LNode* p=L->next;//初始化p,使p指向首元结点(*p就表示这个首元结点)
        while(p&&p->data!=e)//顺链表扫描,直到p为空或者找到相应元素为止
        {
            p=p->next;
        }
        return p;
    }
    
    //单链表的插入
    void LinkInsert(LinkList &L,int i,ElemType e)
    {
        LNode* p=L;
        int j=0;
        while(p&&(j<i-1))
        {
            p=p->next;
            ++j;
        }//查找到第i-1个结点,并使p指向该结点
        if(!p||j>i-1)
        {
            cout<<"插入位置不合法!\n"<<endl;
            return;
        }
        LNode* s=new LNode;//生成新结点指针s
        s->data=e;//将结点指针s的数据域置为e
        s->next=p->next;
        p->next=s;
        cout<<"数据插入成功!\n"<<endl;
    
    
    }
    
    //单链表的删除
    void ListDelete(LinkList &L,int i)
    {
        LNode* p=L;
        int j=0;
        while((p->next)&&(j<i-1))
        {
            p=p->next;
            j++;
        }//查找表的第i-1个结点,p指向该结点
        if(!(p->next)||(j>i-1))
        {
            cout<<"删除位置不合理!\n"<<endl;
            return;
        }
        LNode* q=p->next;//临时保存被删结点的地址以备释放
        p->next=q->next;//改变删除结点前驱结点的指针域,指向删除结点的后继结点
        delete q;//释放删除结点的空间
    }
    
    //打印单链表
    void PrintList(LinkList L) {
        LNode* p;
        if (L == NULL)
        {
            cout<<"该单链表为空!\n"<<endl;
            return;
        }
        p = L->next;
        while (p)
        {
            cout <<"print:"<< p->data << endl;
            p = p->next;
        }
    }
    //整表删除
    Status ClearList(LinkList L) {
        LinkList p, q;
        if (L == NULL)
            return ERROR;
        p=L->next;
        while (p) {
            cout <<"clear:"<< p->data << endl;
            q = p->next;
            delete p;
            p = q;
            L->next = p;
        }
        if (!p)
            return ERROR;
        L->next = NULL;
        return OK;
    }
    
    //获得单链表的长度
    Status GetLen(LinkList L) {
        Status len=0;
        LNode* p=L;
        if (L == NULL)
            return ERROR;
        while (p->next != NULL)
            {
                p = p->next;
                len++;
            }
        return len;
    }
    int main()
    {
    	//可调用上述方法尝试运行
        return 0;
    }
    
    
    展开全文
  • 数据结构---单链表C++实现)

    千次阅读 2018-06-20 16:01:09
    单链表的一个存储结点(node)包括两个部分:数据域(data)和指针域(link) 数据域:存储线性表的一个数据元素 指针域:存储下一个节点的首地址 只能通过头指针(pHead)进行操作:链表的第一个结点的地址可以...

    单链表


    线性表由于在内存上顺序存储,在插入和删除元素时效率很低。单链表通过链式存储,适用于插入和删除频繁,储存空间不定的情形。

    单链表的一个存储结点(node)包括两个部分:数据域(data)和指针域(link)
    数据域:存储线性表的一个数据元素
    指针域:存储下一个节点的首地址
    这里写图片描述

    1. 只能通过头指针(pHead)进行操作:链表的第一个结点的地址可以通过链表的头指针找到,但是其他结点的指针则在前驱结点的指针域中。
    2. 长度方便扩充:链表的顺序和存放的物理顺序没有影响,扩容时将新结点的地址放在前驱结点的指针域即可。

    单链表的类定义

    通常使用两个类:结点类(linknode)和链表类(list)

    代码实现

    #include<stdlib.h>
    #include<iostream>
    
    using namespace std;
    
    template<class T>
    struct LinkNode //定义成模板之后不能使用typedef
    {
        T _data;//数据域
        LinkNode<T>* _pNext;//指针域
    
        LinkNode(LinkNode<T> * ptr = NULL)//仅初始化指针成员的构造函数
        {
            _pNext = ptr;
        }
        LinkNode(T& item, LinkNode<T>* ptr = NULL)
        {
            _data = item;
            _pNext = ptr;
        }
    };
    
    
    template<class T>
    class List
    {
    public:
        List(){ pHead = new LinkNode<T>; }                      //构造函数
        List(const T& x){ pHead = new LinkNode<T>(x); }         //构造函数
        List(List<T>& L);                                       //复制构造函数
        ~List(){ makeEmpty(); }                                    //析构函数
        void makeEmpty();                                       //链表置空
        int Length()const;                                      //求长度
        LinkNode<T> *getHead()const{ return pHead; }            //返回附加头结点地址
        LinkNode<T> *Search(T x);                               //搜索数据x的位置
        LinkNode<T> *Locate(int i);                             //搜索第i个元素的地址
        bool getData(int i, T& x)const;                         //取第i个元素的值
        void setData(int i, T& x);                              //用x修改第i个元素的值
        bool Insert(int i, T& x);                               //在第i个元素后插入x
        bool Remove(int i, T& x);                               //删除第i个元素的值,x为元素的值
        bool IsEmpty()const                                     //判空,空true
        {
            return pHead->_pNext == NULL ? true : false;
        }
        bool IsFull()const{ return false; }                     //判满,true满
        void Sort();                                            //排序
        void inputFront(T& end);                                //头插输入
        void inputRear(T& end);                                         //尾插输入
        void output();                                          //输出
        List<T>& operator=(List<T>& L);                         //重载函数:赋值
    private:
        LinkNode<T> * pHead;                                    //链表头指针
    };
    
    //复制构造函数
    template<class T>
    List<T>::List(List& L)
    {
        T value;
        LinkNode<T> * srcptr = L.getHead();
        LinkNode<T> * destptr = pHead = new ListNode<T>;
    
        while (srcptr->_pNext! = NULL)
        {
            value = srcptr->_pNext->_data;
            destptr->_pNext = new ListNode<T>(value);
            destptr = destptr->_pNext;
            srcptr = srcptr->_pNext;
        }
        destptr->_pNext = NULL;
    };
    
    
    //链表置空
    template<class T>
    void List<T>::makeEmpty()
    {
        LinkNode<T> * del;
        while (pHead->_pNext != NULL)
        {
            del = pHead->_pNext;
            pHead->_pNext = del->_pNext;
            delete del;
        }
    };
    
    
    //求单链表长度
    template<class T>
    int List<T>::Length()const
    {
        LinkNode<T>* q = pHead->_pNext;
        int count = 0;
        while (q != NULL)
        {
            q = q->_pNext;
            count++;
        }
        return count;
    };
    
    //找到第一个含x的值,没有返回NULL
    template<class T>
    LinkNode<T> * List<T>::Search(T x)
    {
        //在表中搜索含数据x的结点,找到返回该节点地址,否则返回NULL
        LinkNode<T> * current = pHead->_pNext;
        while (current != NULL)
        {
            if (current->_data == x)
                break;
            else
                current = current->_pNext;
        }
        return current;
    };
    
    //搜索第i个元素的地址
    template<class T>
    LinkNode<T> * List<T>::Locate(int i)
    {
        //i<0或i超出表中结点数,返回NULL
        if (i < 0)
            return NULL;
        LinkNode<T> * current = pHead;
        int k = 0;
        while (current != NULL && k < i){
            current = current->_data;
            k++;
        }
        return current;
    }
    
    //取第i个元素的值
    template<class T>
    bool List<T>::getData(int i, T& x)const
    {
        if (i <= 0)
            return false;
        LinkNode<T> * current = Locate(i);
        if (current == NULL)
            return false;
        else
        {
            x = current->_data;
            return true;
        }
    }
    
    //用x修改第i个元素的值
    template<class T>
    void List<T>::setData(int i, T& x)
    {
        if (i < 0)
            return;
        LinkNode<T> * current = Locate(i);
        if (current == NULL)
            return;
        else
        {
            current->_data = x;
        }
    }
    
    //在第i个元素后插入x
    template<class T>
    bool List<T>::Insert(int i, T& x)
    {
        if (i < 0)
            return false;
        LinkNode<T> * current = Locate(i);
        if (NULL == current)
            return false;
        LinkNode<T> * newnode = new LinkNode<T>(x);
        if (newnode == NULL)
        {
            cerr << "内存分配错误" << endl;
            exit(1);
        }
        newnode->_pNext = current->_pNext;
        current->_pNext = newnode;
        return true;
    }
    
    //删除第i个元素的值,x为元素的值
    template<class T>
    bool List<T>::Remove(int i, T& x)
    {
        if (i <= 0)
            reuturn false;
        LinkNode<T> * current = Locate(i - 1);
        if (current == NULL || current->_pNext == NULL)
            return false;
        LinkNode<T> * del = current->_pNext;
        if (del == NULL)
            return false;
        current->_pNext = del->_pNext;
        x = del->_data;
        delete del;
        return true;
    }
    
    //输出到屏幕上
    template<class T>
    void List<T>::output()
    {
        LinkNode<T> * current = pHead->_pNext;
        while (current != NULL)
        {
            cout << current->_data << "--->";
            current = current->_pNext;
        }
        cout << "NULL" << endl;
    }
    
    //重载函数:赋值
    template<class T>
    List<T>& List<T>::operator=(List<T>& L)
    {
        T value;
        LinkNode<T> * srcptr = L.getHead();//被复制表的附加头结点地址
        LinkNode<T> * desptr = new LinkNode<T>;
        while (srcptr->_pNext != NULL)//逐个结点复制
        {
            value = srcptr->_pNext->_data;
            desptr->_pNext = new LinkNode<T>(value);
            srcptr = srcptr->_pNext;
            desptr = desptr->_pNext;
        }
        desptr->_pNext = NULL;
        return *this;
    }
    
    
    //头插输入
    template<class T>
    void List<T>::inputFront(T& end)
    {
        //end是约定的序列结束的标志
        //输入序列为正整数,end可以为0或者负整数
        //输入序列为字符,end可以为"\0"
        LinkNode<T> * newNode;
        T val;
        makeEmpty();
        cin >> val;
        while (val != end)
        {
            newNode = new LinkNode<T>(val);//创建新结点
            if (newNode == NULL)
            {
                cerr << "存储分配错误!" << endl;
                exit(1);
            }
            newNode->_pNext = pHead->_pNext;
            pHead->_pNext = newNode;
            cin >> val;
        }
    
    }
    
    //尾插输入
    template<class T>
    void List<T>::inputRear(T& end)
    {
        //end是约定的序列结束的标志
        //输入序列为正整数,end可以为0或者负整数
        //输入序列为字符,end可以为"\0"
        LinkNode<T> * newNode;
        LinkNode<T> * last = pHead;
        T val;
        makeEmpty();
        cin >> val;
        while (val != end)
        {
            newNode = new LinkNode<T>(val);//创建新结点
            if (newNode == NULL)
            {
                cerr << "存储分配错误!" << endl;
                exit(1);
            }
            last->_pNext = newNode;
            last = last->_pNext
            cin >> val;
        }
        last->_pNext = NULL;
    };
    
    
    int main()
    {
        int i = 0;
        List<int> L;
        L.inputFront(i);
        L.output();
        return 0;
    }

    链表的缺点

    每个结点都需要存储数据信息和下一结点的地址信息,存储空间较线性表更大。

    展开全文
  • 数据结构单链表的实现,包括两个链表的合并,求交集,求并集,增加,删除,插入功能
  • 数据结构单链表的创建,插入,修改,查找以及删除。线性表操作
  • 数据结构单链表

    2016-01-08 14:26:18
    数据结构的一些讲解,供学习者参考,也顺带作为复习需要源代码的欢迎下载,免积分,共同学习,家下来每天都会分享一篇,持续一个星期
  • 数据结构单链表创建(c++) 说明:使用c++创建单链表,使用头插法,动态空间规划法,以‘’#‘’或‘$’结束j键盘输入,最后打印出链表内容。 必备条件:结构体、指针、动态规划、循环语句等 #include <stdio.h...
  • 数据结构C++单链表的实现

    千次阅读 2017-04-01 14:12:59
    因为现在的工作经常要看源码,而源码里面经常也会有数据结构里面的知识,比如说,handler 相关的消息出队和入队。所以打算写个一系列的文章帮助自己加深印象。一、单链表介绍 单链表的每一个节点由数据域和指针域...
  • 单链表的接本操作,有在单链表中插入,删除数据的功能,以及...1.单链表数据结构的建立实现。 2.单链表元素结点插入操作实现。 3.单链表元素结点删除操作实现。 4.实现单链表的合并。 5.实现一元多项式的相加。
  • 洛阳理工学院实验报告 系别 计算机系 班级 学号 姓名 课程名称 数据结构 实验日期 11.7 实验名称 链表的基本操作 成绩 实验目的 熟悉掌握线性表链式存储结构掌握与应用查找插入删除等基本操作 算法训练和提高结构化...
  • 单链表类及测试,可直接运行 visual studio2019(其他也可运行)
  • 单链表结构实现的大数阶乘,VC简单程序复制进去便可实现。采用递归调用的方法。
  • : 结点由数据域和指针域组成, 数据域中可以是任意类型的数据包括结构体甚至其他数据结构, 指针域中是指向链表下一个结点的指针。 头节点 head node :头结点也称表头 哑结点, 数据域无意义, 指针域存储指向链表第...
  • 最近在学数据结构,主要看小甲鱼的“数据结构与算法”视频,自己根据视频实现了单链表的基本操作。 主要包括以下函数; typedef struct Node { ElemType data;//数据域 struct Node *Next;//指针域 }Node,*...
  • 数据结构(顺序表和单链表C++实现 我在自学数据结构,代码是我自己写的,水平有限。
  • 洛阳理工学院实验报告 系别 计算机系 班级 学号 姓名 课程名称 数据结构 实验日期 11.7 实验名称 链表的基本操作 成绩 实验目的 熟悉掌握线性表链式存储结构掌握与应用查找插入删除等基本操作算法训练和提高结构化...
  • 2.采用单链表结构编程实现:两个有序单链表的归并运算。 #include <iostream> #include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef int Status; #define OK 1 #define ERROR 0...
  • 数据结构实验一(2):单链表 实验内容 定义一个包含学生信息(学号,姓名,成绩)的单链表,使其具有如下功能(参见教材中基本操作): (1) 前插法或者后插法构建表; (2) 逐个显示学生表中所有学生的相关信息...
  • 这是我第一次自己写出一个完整的数据结构代码,放在这里记录一下。同时也在梳理一遍代码的结构。 代码实现的是链式存储建立多项式并输出。 #include <iostream> using namespace std; // 定义多项式的节点 ...
  • 一实验目的 1掌握用Vc++上机调试程序的基本方法 2掌握单链表的建立插入删除以及相关操作 二实验内容 1单链表的插入算法 2单链表的删除算法 3两个有序单链表合并成一个有序单链表的算法 三实验要求 1学生用C++/C完成...
  • 数据结构单链表冒泡法排序数据结构C++实现,可输入式程序
  • 数据结构老师布置的作业,运用课本代码,较为基础经典,适合大学本科在上数据结构这门课的同学参考,简单易懂,关于单链表的逆置问题
  • 对学生信息的单链表已经实现以下操作: //初始化 Status InitList(LinkList& L);...包含实验目的,实验分析,实验源程序,实验结果,适合数据结构单链表的作业提交和学习,注释较多,适合基础人群学习。
  • 链表的c++实现链表的c++实现链表的c++实现
  • C++实现单链表(含完整代码)

    千次阅读 多人点赞 2020-03-28 18:03:37
    C++实现单链表(含完整代码) 使用C++实现单链表的基本操作 1、创建单链表 2、遍历单链表 3、插入单链表元素 4、单链表删除元素 5、判断单链表是否为空 6、单链表的长度 7、查找单链表元素 完整代码: #include <...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,855
精华内容 6,742
关键字:

数据结构单链表c++

c++ 订阅
数据结构 订阅