#include<iostream> using namespace std; #include<malloc.h> #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; }LinkNode; void InitList(LinkNode *&L) { L=(LinkNode*)malloc(sizeof(LinkNode)); L->next = L; } void CreateListF(LinkNode *&L,ElemType a[],int n)//头插法 { LinkNode *p; L = (LinkNode * )malloc(sizeof(LinkNode)); L->next = NULL; for(int i = 0;i<n;i++) { p =(LinkNode * )malloc(sizeof(LinkNode )); p->data = a[i]; p->next = L->next; L->next = p; } p = L->next;//查找尾结点 while(p->next != NULL)//p指向尾结点 { p = p->next; } p->next = L;//尾结点next指向头结点 } void CreateListR(LinkNode *&L,ElemType a[],int n)//尾插法 { LinkNode *p,*r; L = (LinkNode *)malloc(sizeof(LinkNode)); L->next = NULL; r = L; for(int i =0;i<n;i++) { p = (LinkNode *) malloc(sizeof(LinkNode)); p->data = a[i]; r->next = p;//将结点p插入r之后 r = p; } r ->next =L;//尾结点指向L } void DestoryList(LinkNode *&L) { LinkNode *pre = L; LinkNode *p =pre->next; while(p!=L) { free(pre); pre = p; p = p->next; } free(p); } bool ListEmpty(LinkNode *L) { return(L->next ==NULL); } int ListLength(LinkNode *L) { LinkNode *p =L; int j =0; while(p->next != L) { j++; p = p->next; } return j; } void DispList(LinkNode *L) { LinkNode *p = L->next; while(p!=L) { cout<<" "<<p->data; p =p->next; } cout<<endl; } bool GetElem(LinkNode *L,int i,ElemType &e) { LinkNode *p = L->next ; int j = 0; if(i<=0 || L->next ==L) return false;//i错误或为空表 if(i==1)//求第一个结点的值,特殊处理 { e = L->next->data; return true; } else { while(j< i-1 && p!=L) { j++; p = p->next; } if(p==L) { return false; } else { e =p->data; return true; } } } int LocateElem(LinkNode *L,ElemType e) { LinkNode * p = L->next; int j = 1; while(p!= L && p->data!=e) { j++; p = p->next; } if( p == L) { return false; } else { return j; } } bool InsertList(LinkNode *&L,int i ,ElemType e) { LinkNode *p = L; LinkNode *s; int j = 1; if(i <= 0) return false; if(p->next == L || i ==1)//原链表为空 或 i==1 { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data =e ; s->next = p->next; p->next = s; return true; } else { p = L->next; while( j< i-1 && p !=L)//找到i-1个结点 { j++; p = p->next; } if(p == L) { return false; } else { s = (LinkNode* )malloc(sizeof(LinkNode)); s->data = e; s->next = p->next; p->next =s; return true; } } } bool ListDelete(LinkNode *&L,int i ,ElemType &e) { int j =1; LinkNode *p =L; LinkNode *q; if(i <= 0 || L->next == L) { return false; } if(i == 1)//i==1 特殊处理 { q = L->next; e = q->data; L->next = q->next; free(q); return true; } else//i不为1时 { p = L->next; while(j< i-1 && p!=L) { j++; p = p->next; } if( p ==L) { return false; } else { q = p->next; e = q->data; p->next = q->next; free(q); return true; } } } int main() { LinkNode *h; ElemType e; cout<<"循环单链表基本操作"<<endl; cout<<"初始化"<<endl; InitList(h); cout<<"依次插入97,98,99,100,101"<<endl; InsertList(h,1,97);InsertList(h,2,98);InsertList(h,3,99);InsertList(h,4,100); InsertList(h,5,101); cout<<"Print"<<endl; DispList(h); cout<<"Length is "<<ListLength(h)<<endl; GetElem(h,3,e); cout<<"第3个元素为"<<e<<endl; cout<<"在第4个位置上插入 60"<<endl; InsertList(h,4,60); cout<<"Print "<<endl; DispList(h); cout<<"删除第3 个元素"<<endl; ListDelete(h,3,e); cout<<"Print"<<endl; DispList(h); cout<<"释放循环单链表"<<endl; DestoryList(h); return 1; }
运行结果