单循环链表C++实现
#include<iostream> using namespace std; struct SLNode //节点类 { int data; SLNode * next; }; struct SLList{//链表类型 SLNode * pb;//尾指针 size_t size;//元素个数 }; void InitList(SLList & list)//初始化一个空的单循环链表 { list.size = 0; list.pb = 0; } void add(SLList & list,SLNode * s)//将s所指的节点添加到链表的表尾 { if(list.pb==0)//判断是否为空链表 { list.pb = s; list.pb->next = list.pb ; } else { SLNode * p = list.pb->next;//记录下表首节点指针 list.pb->next = s; list.pb = list.pb->next;//移动尾指针 list.pb->next = p;//重新连接成循环链表 } list.size++; } bool delFirst(SLList & list,SLNode * q)//删除链表的第一个节点,并以q返回 { if(list.pb==0)//判断是否为空链表 { return false; } q = list.pb->next; if(list.size == 1)//如果该链表只剩下一个节点,删除后则重新将链表的尾指针设为0指针 list.pb = 0; else list.pb->next = q->next; list.size--; return true ; } bool del(SLList & list,SLNode * q)//删除链表中q所指向的节点,其中q指向的是链表中的一个节点----------------------? { if(list.pb==0) {cout<<"错误一"<<endl;return false;} SLNode * p = 0 ;//记录q节点的前一个节点指针 //找到q节点的前一个节点 if(list.pb->next==q) {p =list.pb;} else { SLNode * p2 = list.pb->next; SLNode * p1 = p2->next; //p2所指向的是p1所指的前一个节点 while(p1!= list.pb->next) { if(p1 == q) { p = p2; break; } p2 = p2->next;//向后移动 p1 = p2->next; } } if(p ==0) {cout<<"错误2"<<endl;return false;} else{ if(list.size==1) list.pb = 0; else p->next = p->next->next; list.size--; delete q; return true; } } bool insBefore(SLList & list,SLNode * q,SLNode * s)//在链表中的q所指向的节点前插入s所指向的节点,其中q指向的是链表中的一个节点 { if(list.pb==0) return false; SLNode * p = 0 ;//记录q节点的前一个节点指针 //找到q节点的前一个节点 if(list.pb->next==q) {p =list.pb;} else { SLNode * p2 = list.pb->next; SLNode * p1 = p2->next; //p2所指向的是p1所指的前一个节点 while(p1!= list.pb->next) { if(p1 == q) { p = p2; break; } p2 = p2->next;//向后移动 p1 = p2->next; } } if(p ==0) return false; else{ p->next = s; s->next = q; list.size++; return true; } } SLNode * FindElem(SLList & list,int t)//在链表中查找第一个元素值与t相等的节点指针 { if(list.pb==0) return false; if(list.pb->next->data==t) { return list.pb->next;}//如果第一个节点的值就与t相等,返回首节点 else { SLNode * p1 = list.pb->next->next;//指向第二个节点 while(p1!= list.pb->next) { if(p1->data == t) { return p1; break; } p1 = p1->next; } } return 0;//当没有找到元素值与t相等的节点是返回0指针 } SLNode * FindElem(SLList & list,int t,bool (*compare)(int,int))//在链表中查找第一个元素值与t满足compare函数关系的节点指针 { if(list.pb==0) return false; if((*compare)(list.pb->next->data,t)) { return list.pb->next;}//如果第一个节点的值就与t相等,返回首节点 else { SLNode * p1 = list.pb->next->next;//指向第二个节点 while(p1!= list.pb->next) { if((*compare)(p1->data , t)) { return p1; break; } p1 = p1->next; } } return 0;//当没有找到元素值与t相等的节点是返回0指针 } SLList & Merge(SLList & list1,SLList & list2)//将两个单循环链表合并成一个链表 { if(list1.pb==0) { return list2; } if(list2.pb==0) { return list1; } SLNode * p = list1.pb->next;//记录下表list1首节点指针 list1.pb->next = list2.pb->next;//将表2的首节点连接到表1的尾节点上 list2.pb->next = p;//将表1的首节点连接到表2的尾节点上 list1.size += list2.size; return list1; } int main() { //创建并初始化一个空的单循环链表 SLList myList; InitList(myList); //给该单循环链表增加元素 cout<<"增加元素1,2,3,4,5"<<endl; SLNode * p = (SLNode *)malloc(sizeof(SLNode)); p->data = 1; add(myList,p); p = (SLNode *)malloc(sizeof(SLNode)); p->data = 2; add(myList,p); p = (SLNode *)malloc(sizeof(SLNode)); p->data = 3; add(myList,p); p = (SLNode *)malloc(sizeof(SLNode)); p->data = 4; add(myList,p); p = (SLNode *)malloc(sizeof(SLNode)); p->data = 5; add(myList,p); //循环该链表输出所有的元素值 cout<<"循环该链表输出所有的元素值"<<endl; p = myList.pb->next;//p指向首节点 cout<<p->data<<" "; p = p->next; while(p!= myList.pb->next ) { cout<<p->data<<" "; p = p->next; } cout<<endl; //删除单循环链表中的第二个节点 p = myList.pb->next->next; if(del(myList,p)==false) cout<<"删除失败!"<<endl;; cout<<"删除单循环链表中的第二个节点"<<endl; p = myList.pb->next;//p指向首节点 cout<<p->data<<" "; p = p->next; while(p!= myList.pb->next ) { cout<<p->data<<" "; p = p->next; } cout<<endl; //查找第一个元素值等于4的节点 p = FindElem(myList,4); cout<<"查找第一个元素值等于4的节点"<<endl; cout<<p->data<<endl; //在第一个第一个元素值等于4的节点前插入一个元素值为7的节点 SLNode* s = (SLNode *)malloc(sizeof(SLNode)); s->data = 7; insBefore(myList,p,s); cout<<"在第一个第一个元素值等于4的节点前插入一个元素值为7的节点:"<<endl; p = myList.pb->next;//p指向首节点 cout<<p->data<<" "; p = p->next; while(p!= myList.pb->next ) { cout<<p->data<<" "; p = p->next; } cout<<endl; //删除该链表的第一个节点 delFirst(myList,p); cout<<"删除该链表的第一个节点,被删除的元素值为:"<<endl; cout<<p->data<<endl; cout<<"链表中剩下的所有元素值为:"<<endl; p = myList.pb->next;//p指向首节点 cout<<p->data<<" "; p = p->next; while(p!= myList.pb->next ) { cout<<p->data<<" "; p = p->next; } cout<<endl; //新建一个单循环线性表2 SLList myList2; InitList(myList2); //给该单循环链表增加元素 cout<<"新建一个单循环线性表2,并初始化值为:"<<endl; p = (SLNode *)malloc(sizeof(SLNode)); p->data = 9; add(myList2,p); p = (SLNode *)malloc(sizeof(SLNode)); p->data = 8; add(myList2,p); p = (SLNode *)malloc(sizeof(SLNode)); p->data = 6; add(myList2,p); p = (SLNode *)malloc(sizeof(SLNode)); p->data = 5; add(myList2,p); p = myList2.pb->next;//p指向首节点 cout<<p->data<<" "; p = p->next; while(p!= myList2.pb->next ) { cout<<p->data<<" "; p = p->next; } cout<<endl; //将循环链表1和循环链表2合并成一个链表 myList = Merge(myList,myList2); cout<<"将循环链表1和循环链表2合并成一个链表,合并后的链表为:"<<endl; p = myList2.pb->next;//p指向首节点 cout<<p->data<<" "; p = p->next; while(p!= myList2.pb->next ) { cout<<p->data<<" "; p = p->next; } cout<<endl; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。