大家好,又见面了,我是全栈君。
带头节点单链表
数据结构定义
ListNode.h #ifndef LISTNODE_H #define LISTNODE_H template<class T> class ListNode { private: T data; ListNode<T> *next; public: ListNode(); ListNode(T value); int Getdata(); ListNode<T>* Getnext(); void Setnext(ListNode<T>* p); }; template<class T>ListNode<T>::ListNode():next(NULL){} template<class T> ListNode<T>::ListNode(T value):data(value),next(NULL){} template<class T> int ListNode<T>::Getdata() { return data; } template<class T> ListNode<T>* ListNode<T>::Getnext() { return next; } template<class T> void ListNode<T>::Setnext(ListNode<T>* p) { next=p; } #endif
带头结点单链表的全部操作实现
LinkList.h #include<iostream> #include "ListNode.h" using namespace std; template<class T>class LinkList { private: ListNode<T> *head; ListNode<T> *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<T>* del); ListNode<T>* GetHead(); ListNode<T>* GetTail(); ListNode<T>* GetNodePtr(int index); void DestroyList(); void TraverseList(); }; template<class T> LinkList<T>::LinkList() { head=new ListNode<T>; tail=head; } template<class T> bool LinkList<T>::IsEmpty() { if (head->Getnext()==NULL) return 1; return 0; } template<class T> int LinkList<T>::ListLength() { int len=0; ListNode<T>*p=head->Getnext(); while (p) { len++; p=p->Getnext(); } return len; } template<class T> void LinkList<T>::AddHead(T value) { ListNode<T>* p=new ListNode<T>(value); p->Setnext(head->Getnext()); head->Setnext(p); } template<class T> void LinkList<T>::AddTail(T value) { ListNode<T>* p=new ListNode<T>(value); tail->Setnext(p); tail=tail->Getnext(); } template<class T> T LinkList<T>::GetAtIndex(int index) { if(index>ListLength()||index<0) { cout<<"选择位置不对!\n"; return -1;//出错 } int i=0; ListNode<T>* p=head->Getnext(); while (i<index) { p=p->Getnext();//跳出的时候P指向index节点 i++; } return p->Getdata(); } template<class T> bool LinkList<T>::InsertAt(int index,T value) { if(index>ListLength()||index<0) { cout<<"插入位置不对!\n"; return 0;//出错 } int i=-1; ListNode<T>* p=head; ListNode<T>* add=new ListNode<T>(value); while (i<index-1) { p=p->Getnext();//跳出的时候P指向index的前一个节点 i++; } add->Setnext(p->Getnext()); p->Setnext(add); return 1; } template<class T> bool LinkList<T>::RemoveAt(int index,T &value) { if(index>ListLength()||index<0) { cout<<"删除位置不对!\n"; return 0;//出错 } int i=-1; ListNode<T>* p=head; while (i<index-1) { p=p->Getnext();//跳出的时候P指向index的前一个节点 i++; } ListNode<T>* del=p->Getnext(); p->Setnext(del->Getnext()); value=del->Getdata(); delete del; return 1; } template<class T> bool LinkList<T>::RemoveAtPtr(ListNode<T>*del) { ListNode<T>* p=GetHead(); while(p->Getnext()!=del) p=p->Getnext();//跳出时p->next==del; ListNode<T>* ptrdel=p->Getnext(); p->Setnext(ptrdel->Getnext()); delete ptrdel; return 1; } template<class T> ListNode<T>* LinkList<T>::GetHead() { return head; } template<class T> ListNode<T>* LinkList<T>::GetTail() { return tail; } template<class T> ListNode<T>* LinkList<T>::GetNodePtr(int index) { ListNode<T>* p=head->Getnext(); int i=0; while (i<index) { p=p->Setnext(p); i++; } return p; } template<class T> void LinkList<T>::DestroyList() { while (head->Getnext()) { ListNode<T> * del=head->Getnext(); head->Setnext(del->Getnext()); delete del; } } template<class T> void LinkList<T>::TraverseList() { if (IsEmpty()) cout<<"链表为空"; ListNode<T>*p=head->Getnext(); while (p) { cout<<p->Getdata()<<endl; p=p->Getnext(); } } 測试: #include "LinkList.h" #include "ListNode.h" #include <iostream> using namespace std; void main() { LinkList<int> myList1; LinkList<int> 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<int>* p=myList2.GetHead()->Getnext(); while (p&&pos<myList1.ListLength()) { if (p->Getdata()<myList1.GetAtIndex(pos)) { myList1.InsertAt(pos,p->Getdata()); // ListNode<int> *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 <iostream.h> 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个位置插入元素e bool DeleteIndexElem(LinkList &L,int i);//第i个位置插入元素e bool DeletePointElem(LinkList &L,LinkList del);//第i个位置插入元素e bool 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<<"链表元素为:"<<endl; while (p) { cout<<p->data<<" "; p=p->next; } cout<<endl; } bool IsEmpty(LinkList L) { if(L=NULL) return 1; return 0; } int ListLength(LinkList L) { int i=0; LinkList p=L; while (p) { i++; p=p->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<i) { p=p->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<i-1) { p=p->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<i-1) { p=p->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<<e<<endl; // DeleteIndexElem(List,1); // DeletePointElem(List,List->next); // TraverseList(List); }
带头节点的循环链表
/************************************************************************/ /* 带头结点的循环链表的创建*/ /************************************************************************/ #include <iostream.h> 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个位置插入元素e bool DeleteIndexElem(LinkList L,int i);//删除第i个位置的元素 bool DeletePointElem(LinkList L,LinkList del);//删除给定指针相应的元素第 void main() { // int e; LinkList List=CreateListRear(); TraverseList(List); // cout<<IsEmpty(List); // cout<<ListLength(List); // GetElem(List,44,e); // cout<<e; // InsertElem(List,41,100); // TraverseList(List); // DeleteIndexElem(List,1); // TraverseList(List); // DeleteIndexElem(List,40); // TraverseList(List); // DeletePointElem(List,List->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<<"链表元素为:"<<endl; while (p!=L) { cout<<p->data<<" "; p=p->next; } cout<<endl; } bool IsEmpty(LinkList L) { if(L->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<i) { p=p->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<i-1) { p=p->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<i-1) { p=p->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 <iostream.h> 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个位置插入元素e bool 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<<"链表元素为:"<<endl; while (p->next!=L) { cout<<p->data<<" "; p=p->next; } cout<<p->data; cout<<endl; } // bool IsEmpty(LinkList L) // { // if(L->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<i) // { // p=p->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<i-1) // { // p=p->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<i-1) // { // p=p->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<<p->next->next->data<<endl; DeletePointElem(L,p->next->next); p=p->next->next; if(p->next==p) break; } }
双向链表
#include<stdio.h> #include<malloc.h> 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<i) { p=p->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<stdio.h> #include<malloc.h> 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<i) { p=p->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; } } }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115596.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...