博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
【数据结构】链表
阅读量：5019 次
发布时间：2019-06-12

本文共 14790 字，大约阅读时间需要 49 分钟。

带头节点单链表

数据结构定义

ListNode.h#ifndef LISTNODE_H#define LISTNODE_Htemplate
    
      class ListNode{private:	T data;	ListNode
     
       *next;public:	ListNode();	ListNode(T value);	int Getdata();	ListNode
      
       * Getnext();	void Setnext(ListNode
       
        * p);	};template
        
         ListNode
         
          ::ListNode():next(NULL){}template
          
            ListNode
           
            ::ListNode(T value):data(value),next(NULL){}template
            
              int ListNode
             
              ::Getdata(){ return data;}template
              
                ListNode
               
                * ListNode
                
                 ::Getnext(){ return next;}template
                 
                   void ListNode
                  
                   ::Setnext(ListNode
                   
                    * p){ next=p;}#endif
带头结点单链表的所有操作实现 

LinkList.h#include
    
     #include "ListNode.h"using namespace std;template
     
      class LinkList{private:	ListNode
      
        *head;	ListNode
       
         *tail;public:	LinkList();	bool IsEmpty();	int ListLength();		//不包括头结点	void AddHead(T value);	void AddTail(T value);	//从第0个位置开始,第0个元素是除过头结点的节点	T GetAtIndex(int index);	bool InsertAt(int index,T value);	bool RemoveAt(int index,T &value);	bool RemoveAtPtr(ListNode
        
         * del);	ListNode
         
          * GetHead(); ListNode
          
           * GetTail(); ListNode
           
            * GetNodePtr(int index); void DestroyList(); void TraverseList();};template
            
              LinkList
             
              ::LinkList(){ head=new ListNode
              
               ; tail=head;}template
               
                 bool LinkList
                
                 ::IsEmpty(){ if (head->Getnext()==NULL) return 1; return 0;}template
                 
                   int LinkList
                  
                   ::ListLength(){ int len=0; ListNode
                   
                    *p=head->Getnext(); while (p) { len++; p=p->Getnext(); } return len;}template
                    
                      void LinkList
                     
                      ::AddHead(T value){ ListNode
                      
                       * p=new ListNode
                       
                        (value); p->Setnext(head->Getnext()); head->Setnext(p);}template
                        
                          void LinkList
                         
                          ::AddTail(T value){ ListNode
                          
                           * p=new ListNode
                           
                            (value); tail->Setnext(p); tail=tail->Getnext();}template
                            
                              T LinkList
                             
                              ::GetAtIndex(int index){ if(index>ListLength()||index<0) { cout<<"选择位置不正确!\n"; return -1;//出错 } int i=0; ListNode
                              
                               * p=head->Getnext(); while (i
                               
                                Getnext();//跳出的时候P指向index节点 i++; } return p->Getdata();}template
                                
                                  bool LinkList
                                 
                                  ::InsertAt(int index,T value){ if(index>ListLength()||index<0) { cout<<"插入位置不正确!\n"; return 0;//出错 } int i=-1; ListNode
                                  
                                   * p=head; ListNode
                                   
                                    * add=new ListNode
                                    
                                     (value); while (i
                                     
                                      Getnext();//跳出的时候P指向index的前一个节点 i++; } add->Setnext(p->Getnext()); p->Setnext(add); return 1; }template
                                      
                                        bool LinkList
                                       
                                        ::RemoveAt(int index,T &value){ if(index>ListLength()||index<0) { cout<<"删除位置不正确!\n"; return 0;//出错 } int i=-1; ListNode
                                        
                                         * p=head; while (i
                                         
                                          Getnext();//跳出的时候P指向index的前一个节点 i++; } ListNode
                                          
                                           * del=p->Getnext(); p->Setnext(del->Getnext()); value=del->Getdata(); delete del; return 1;}template
                                           
                                             bool LinkList
                                            
                                             ::RemoveAtPtr(ListNode
                                             
                                              *del){ ListNode
                                              
                                               * p=GetHead(); while(p->Getnext()!=del) p=p->Getnext();//跳出时p->next==del; ListNode
                                               
                                                * ptrdel=p->Getnext(); p->Setnext(ptrdel->Getnext()); delete ptrdel; return 1;}template
                                                
                                                  ListNode
                                                 
                                                  * LinkList
                                                  
                                                   ::GetHead(){ return head;}template
                                                   
                                                     ListNode
                                                    
                                                     * LinkList
                                                     
                                                      ::GetTail(){ return tail;}template
                                                      
                                                        ListNode
                                                       
                                                        * LinkList
                                                        
                                                         ::GetNodePtr(int index){ ListNode
                                                         
                                                          * p=head->Getnext(); int i=0; while (i
                                                          
                                                           Setnext(p); i++; } return p;}template
                                                           
                                                             void LinkList
                                                            
                                                             ::DestroyList(){ while (head->Getnext()) { ListNode
                                                             
                                                               * del=head->Getnext(); head->Setnext(del->Getnext()); delete del; }}template
                                                              
                                                                void LinkList
                                                               
                                                                ::TraverseList(){ if (IsEmpty()) cout<<"链表为空"; ListNode
                                                                
                                                                 *p=head->Getnext(); while (p) { cout<
                                                                 
                                                                  Getdata()<
                                                                  
                                                                   Getnext(); }}测试：#include "LinkList.h"#include "ListNode.h"#include 
                                                                   
                                                                    using namespace std;void main(){ LinkList
                                                                    
                                                                      myList1; LinkList
                                                                     
                                                                       myList2; myList1.AddTail(2); myList1.AddTail(4); myList1.AddTail(6); myList1.AddTail(8); myList1.AddTail(10); myList1.RemoveAtPtr(myList1.GetHead()->Getnext()); cout<<"myList1元素:\n"; myList1.TraverseList(); myList2.AddTail(3); myList2.AddTail(3); myList2.AddTail(5); myList2.AddTail(7); myList2.AddTail(12); cout<<"myList2元素:\n"; myList2.TraverseList(); cout<<"合并后的链表元素:\n"; int pos=0; ListNode
                                                                      
                                                                       * p=myList2.GetHead()->Getnext(); while (p&&pos
                                                                       
                                                                        Getdata()
                                                                        
                                                                         Getdata());// ListNode
                                                                         
                                                                           *del=p; p=p->Getnext();// myList2.RemoveAtPtr(del);//删除指针对应的节点 int s; myList2.RemoveAt(0,s);//删除首节点 也就是删除第0个元素 } pos++; } if (p) { myList1.GetTail()->Setnext(p); } myList1.TraverseList(); getchar();}
不带头结点单链表 
不带头结点单链表/************************************************************************//* 无头结点链表的创建                                               *//************************************************************************/#include 
    
     typedef struct node{	int data;	struct node *next;}Node,*LinkList;LinkList CreateListHead();//头插创建链表LinkList CreateListRear();//尾插创建链表void TraverseList(LinkList L);//遍历链表bool IsEmpty(LinkList L);//判断是否为空int ListLength(LinkList L);//链表长度bool GetElem(LinkList L,int i,int &e);//获取第i个元素给ebool InsertElem(LinkList &L,int i,int e);//第i个位置插入元素ebool DeleteIndexElem(LinkList &L,int i);//第i个位置插入元素ebool DeletePointElem(LinkList &L,LinkList del);//第i个位置插入元素ebool DestroyList(LinkList &L);//销毁链表/*头插法*/LinkList CreateListHead(){	LinkList head=NULL;	for (int i=1;i<42;i++)	{		LinkList p=new Node;		p->data=i;		p->next=head;		head=p;	}	return head;}/*尾插法*/LinkList CreateListRear(){	LinkList head=NULL;	LinkList tail=head;	for (int i=1;i<42;i++)	{		LinkList p=new Node;		p->data=i;		p->next=NULL;		if (i==1)		{			head=p;			tail=head;		}		else		{			tail->next=p;			tail=p;		}	}	return head;}void TraverseList(LinkList L){	LinkList p=L;	cout<<"链表元素为:"<
     
      data<<" ";		p=p->next;	}	cout<
      
       next;	}	return i;}bool GetElem(LinkList L,int i,int &e){	int j=1;	LinkList p=L;	if (i<1||i>ListLength(L))		return false;	while (j
       
        next;		j++;	}	e=p->data;		return 1;}bool InsertElem(LinkList &L,int i,int e){	LinkList p=L;	int j=1;	LinkList temp=new Node;	if (i<1||i>ListLength(L))		return 0;	else if (1==i)	{		temp->data=e;		temp->next=L;		L=temp;	}	else	{		while (j
        
         next;			j++;		}		temp->data=e;		temp->next=p->next;		p->next=temp;			}	return 1;}bool DeleteIndexElem(LinkList& L,int i){	LinkList p=L;	int j=1;	if (i<1||i>ListLength(L))		return 0;	else if (1==i)	{		L=L->next;		delete(p);	}	else	{		while (j
         
          next; j++; } LinkList temp=p->next; p->next=p->next->next; delete(temp); } return 1;}bool DeletePointElem(LinkList &L,LinkList del){ LinkList p=L; if (del==L) { L=L->next; delete p; } else { while (p->next!=del) p=p->next; p->next=del->next; delete del; } return 1;}bool DestroyList(LinkList &L){ LinkList p=L; while (L) { p=L; L=L->next; delete(p); } return 1;}// 测试void main(){// int e; LinkList List=CreateListRear(); TraverseList(List);// GetElem(List,5,e);// cout<
          
           <
           
            next);// TraverseList(List);}
带头节点的循环链表 

/************************************************************************//* 带头结点的循环链表的创建*//************************************************************************/#include 
    
     typedef struct node{	int data;	struct node *next;}Node,*LinkList;LinkList CreateListHead();//头插创建链表LinkList CreateListRear();//尾插创建链表void TraverseList(LinkList L);//遍历链表bool IsEmpty(LinkList L);//判断是否为空int ListLength(LinkList L);//链表长度bool GetElem(LinkList L,int i,int &e);//获取第i个元素给ebool InsertElem(LinkList L,int i,int e);//第i个位置插入元素ebool DeleteIndexElem(LinkList L,int i);//删除第i个位置的元素bool DeletePointElem(LinkList L,LinkList del);//删除给定指针对应的元素第void main(){//	int e;	LinkList List=CreateListRear();	TraverseList(List);//	cout<
     
      next);//	TraverseList(List);}/*头插法*/LinkList CreateListHead(){	LinkList head=new Node;	head->next=head;	for (int i=1;i<42;i++)	{		LinkList p=new Node;		p->data=i;		p->next=head->next;		head->next=p;	}	return head;}/*尾插法*/LinkList CreateListRear(){	LinkList head=new Node;	head->next=head;	LinkList tail=head;	for (int i=1;i<42;i++)	{				LinkList p=new Node;		p->data=i;		p->next=head;		tail->next=p;		tail=p;	}	return head;}void TraverseList(LinkList L){	LinkList p=L->next;	cout<<"链表元素为:"<
      
       data<<" ";		p=p->next;	}	cout<
       
        next==L)		return 1;	return 0;}int ListLength(LinkList L){	int i=0;	LinkList p=L->next;	while (p!=L)	{		i++;		p=p->next;	}	return i;}bool GetElem(LinkList L,int i,int &e){	int j=0;	LinkList p=L;	if (i<1||i>ListLength(L))		return 0;	while (j
        
         next;		j++;	}	e=p->data;		return 1;}bool InsertElem(LinkList L,int i,int e){	LinkList p=L;	int j=0;	LinkList temp=new Node;	if (i<1||i>ListLength(L))		return 0;	while (j
         
          next; j++; } temp->data=e; temp->next=p->next; p->next=temp; return 1;}bool DeleteIndexElem(LinkList L,int i){ LinkList p=L; int j=0; if (i<1||i>ListLength(L)) return 0; while (j
          
           next; j++; } LinkList temp=p->next; p->next=p->next->next; delete(temp); return 1;}bool DeletePointElem(LinkList L,LinkList del){ LinkList p=L; while (p->next!=del) p=p->next; p->next=del->next; delete del; return 1;}
不带头结点的循环链表 

/************************************************************************//* 不带头结点的循环链表                                               *//************************************************************************/#include 
    
     typedef struct node{	int data;	struct node *next;}Node,*LinkList;LinkList CreateListHead();//头插创建链表LinkList CreateListRear();//尾插创建链表void TraverseList(LinkList L);//遍历链表//bool IsEmpty(LinkList L);//判断是否为空//int ListLength(LinkList L);//链表长度//bool GetElem(LinkList L,int i,int &e);//获取第i个元素给e// bool InsertElem(LinkList L,int i,int e);//第i个位置插入元素ebool DeleteIndexElem(LinkList L,int i);//删除第i个位置的元素bool DeletePointElem(LinkList &L,LinkList del);//删除给定指针对应的元素第void Josephus(LinkList L);// 测试void main(){//	int e;	LinkList List=CreateListRear();	TraverseList(List);//	DeletePointElem(List,List);	Josephus(List);}/*头插法*/// LinkList CreateListHead()// {// 	LinkList head=NULL;// 	for (int i=41;i>0;i--)// 	{// 		LinkList p=new Node;// 		p->data=i;// 		p->next=head;// 		head=p;// 	}// 	return head;// }/*尾插法*/LinkList CreateListRear(){	LinkList head=NULL;	LinkList tail=head;	for (int i=1;i<42;i++)	{		LinkList p=new Node;		p->data=i;		p->next=head;		if (i==1)		{			head=p;			tail=head;		}		else		{			tail->next=p;			tail=p;		}	}	return head;}void TraverseList(LinkList L){	LinkList p=L;	cout<<"链表元素为:"<
     
      next!=L)	{		cout<
      
       data<<" ";		p=p->next;		}	cout<
       
        data;	cout<
        
         next==L)// 		return 1;// 	return 0;// }// int ListLength(LinkList L)// {// 	int i=0;// 	LinkList p=L->next;// 	while (p!=L)// 	{// 		i++;// 		p=p->next;// 	}// 	return i;// }// bool GetElem(LinkList L,int i,int &e)// {// 	int j=0;// 	LinkList p=L;// 	if (i<1||i>ListLength(L))// 		return 0;// 	while (j
         
          next;// j++;// }// e=p->data; // return 1;// }// bool InsertElem(LinkList L,int i,int e)// {// LinkList p=L;// int j=0;// LinkList temp=new Node;// if (i<1||i>ListLength(L))// return 0;// while (j
          
           next;// j++;// }// temp->data=e;// temp->next=p->next;// p->next=temp;// return 1;// }// bool DeleteIndexElem(LinkList L,int i)// {// LinkList p=L;// int j=0;// if (i<1||i>ListLength(L))// return 0;// while (j
           
            next;// j++;// }// LinkList temp=p->next;// p->next=p->next->next;// delete(temp);// return 1;// }bool DeletePointElem(LinkList &L,LinkList del){ LinkList p=L; if (del==L) { while (p->next!=del) p=p->next; L=L->next; p->next=L; delete del; } else { while (p->next!=del) p=p->next; p->next=del->next; delete del; } return 1;}// 约瑟夫问题的解决方法void Josephus(LinkList L){ LinkList p=L; while (L) { cout<
            
             next->next->data<
             
              next->next); p=p->next->next; if(p->next==p) break; }}

双向链表

#include
    
     #include
     
      typedef struct node {	int data;	struct node *prior;	struct node *next;}DNode,*DLinkList;DLinkList CreateDList();void TraverseList(DLinkList L);bool IsEmpty(DLinkList L);int  Length(DLinkList L);DLinkList GetElem(DLinkList L,int i);bool InsertElem(DLinkList L,int i,int e);bool DeleteElem(DLinkList L,int i,int &e);void main(){	DLinkList Dlist=CreateDList();	printf("list的元素:\n");	TraverseList(Dlist);	InsertElem(Dlist,3,3);	printf("插入元素后的list:\n");	TraverseList(Dlist);}DLinkList CreateDList(){	//尾插法	DLinkList head=(DLinkList)malloc(sizeof(DNode));	DLinkList tail;	head->next=head->prior=NULL;//建立一个带头结点的空表	tail=head;	for (int i=0;i<4;i++)	{		DLinkList p=(DLinkList)malloc(sizeof(DNode));		scanf("%d",&p->data);		p->next=NULL;		p->prior=tail;		tail->next=p;		tail=p;	}	return head;}bool IsEmpty(DLinkList L){	if (L->next==NULL)		return 1;	return 0;}void TraverseList(DLinkList L){		if (!IsEmpty(L))	{		DLinkList p=L->next;		while (p!=NULL)		{			printf("%d\n",p->data);			p=p->next;		}	}}int  Length(DLinkList L){	int len=0;	if (!IsEmpty(L))	{		DLinkList p=L->next;		while (p!=NULL)		{			len++;			p=p->next;		}	}	return len;}DLinkList GetElem(DLinkList L,int i){	DLinkList p=L->next;	int j=1;	if(i<1||i>Length(L))	{		return 0;	}	while (j
      
       next;		j++;	}	return p;}bool InsertElem(DLinkList L,int i,int e){	DLinkList p;	if(!(p=GetElem(L,i-1)))		return 0;	DLinkList s=(DLinkList)malloc(sizeof(DNode));	s->data=e;	s->next=p->next;	p->next->prior=s;	p->next=s;	s->prior=p;	return 1;}

经典面试题：快慢指针实现快速找到链表的中间元素（带头结点单链表）

#include
    
     #include
     
      typedef struct node {	int data;	struct node *next;}Node,*LinkList;LinkList CreateDList();void TraverseList(LinkList L);bool IsEmpty(LinkList L);int  Length(LinkList L);LinkList GetElem(LinkList L,int i);bool InsertElem(LinkList L,int i,int e);//bool DeleteElem(LinkList L,int i,int &e);int MidElem(LinkList L);//返回中间元素void main(){	LinkList list=CreateDList();	printf("list的元素:\n");	TraverseList(list);//	InsertElem(list,3,3);//	printf("插入元素后的list:\n");//	TraverseList(list);	printf("中间的元素为:%d\n",MidElem(list));}LinkList CreateDList(){	//尾插法	LinkList head=(LinkList)malloc(sizeof(Node));	LinkList tail;	head->next=NULL;//建立一个带头结点的空表	tail=head;	for (int i=0;i<3;i++)	{		LinkList p=(LinkList)malloc(sizeof(Node));		scanf("%d",&p->data);		p->next=NULL;		tail->next=p;		tail=p;	}	return head;}bool IsEmpty(LinkList L){	if (L->next==NULL)		return 1;	return 0;}void TraverseList(LinkList L){		if (!IsEmpty(L))	{		LinkList p=L->next;		while (p!=NULL)		{			printf("%d\n",p->data);			p=p->next;		}	}}int  Length(LinkList L){	int len=0;	if (!IsEmpty(L))	{		LinkList p=L->next;		while (p!=NULL)		{			len++;			p=p->next;		}	}	return len;}LinkList GetElem(LinkList L,int i){	LinkList p=L->next;	int j=1;	if(i<1||i>Length(L))	{		return 0;	}	while (j
      
       next;		j++;	}	return p;}bool InsertElem(LinkList L,int i,int e){	LinkList p;	if(!(p=GetElem(L,i-1)))		return 0;	LinkList s=(LinkList)malloc(sizeof(Node));	s->data=e;	s->next=p->next;	p->next=s;	return 1;}//快慢指针实现快速找到链表的中间元素int MidElem(LinkList L){	LinkList p;	LinkList mid;	p=mid=L;		//P必须指向头结点这样才能保证链表在不为空的下限时p->next->next是正确的语句	if (p->next==NULL)		return 0;//空链表	while(1)	{		if (p==NULL||p->next==NULL)//p为NULL时是奇数个数字的情况p->next==NULL是偶数个的情况			return mid->data;		else		{			p=p->next->next;			mid=mid->next;		}	}}

转载于:https://www.cnblogs.com/qhyuan1992/p/5385329.html

你可能感兴趣的文章
MD5--3D模型
查看>>
“云时代”solo模式的网站创建
查看>>
Windows 内核（WRK）简介
查看>>
6.1.2.1 html-head相关的标签
查看>>
【C++】如何利用直方图实现快速中值滤波
查看>>
poj3678 Katu Puzzle
查看>>
MVC4--Model常见问题
查看>>
C++笔记
查看>>
第1课：SQL注入原理深度解析
查看>>
MySQL百万级数据库优化方案
查看>>
生成订单编号：站点编号前三位 + [5,12]位自增编号
查看>>
Python学习第二步骤
查看>>
A*寻路初探（转）
查看>>
排序算法（五）归并排序
查看>>
mysql 修改root 用户密码
查看>>
网络操作系统第二章课后习题解答
查看>>
jquery 的 each 方法中 return 的坑
查看>>
844. Backspace String Compare判断删除后的结果是否相等
查看>>
多个EXCEL文件合并成一个
查看>>
故事板
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-14 01:10:17   当前IP: 3.139.97.43   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我