前面两篇文章我已经把线性表的顺序存储和链式存储都实现了一次,还记得学数据结构的时候,看着老师给的代码,觉得操作很简单,自己再实现一次的时候,发现还是有很多需要考虑周全的。
我们一直都是创建的有头结点的链表,因为有头结点的链表在操作起来很方便,尤其是在一些边界处理上,不容易出错,而且关键是比较好理解。无头结点的单链表相比起来在边界的处理上稍微要复杂一些了,容易出现错误,代码也要难理解一些。我是在有头结点的单链表上进行修改,添加了利用头插法和尾插法创建链表的函数,保留了原来的在特定位置插入新结点的函数,实现了一个无头结点的单链表,以前觉得很简单,真正做下去才发现没有头结点的单链表,在很多情况下都无法很好的实现对其统一操作,特别是在删除、插入等的操作上,需要细心。代码奉上,大家相互学习
/* *用头插法与尾插法实现了无头结点单链表的创建 *数据结构<三> *链式存储线性表(无头节点) */ #include <iostream> #include <stdlib.h> using namespace std; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList;//LNode 结构体类型,LinkList 结构体指针类型 //构造一个空的线性表 int InitList(LinkList &L) { L=(LinkList)malloc(sizeof(LNode));//head为头指针 if(!L) return 1; L=NULL; return 0; } //销毁线性表线性表 void DestroyList(LinkList &L) { LinkList p; if(L!=NULL) while (L->next!=NULL) { p=L->next; L->next=L->next->next; free(p); //释放p结点 } L=NULL; //头指针置空 cout<<"销毁链表操作成功!"<<endl; } //将L重置为空表 void ClearList(LinkList &L) { LinkList p; if(L!=NULL) while (L->next!=NULL)//如果链表非空,则置空 { p=L->next; L->next=L->next->next; free(p); } L=NULL; if(L==NULL) cout<<"置空链表操作成功!"<<endl; } //若L为空表,则返回TRUE,否则返回FALSE int ListEmpty(LinkList L) { if (L==NULL) { return 1; } else return 0; } //输出L中数据元素的个数 int ListLength(LinkList L) { int num=0; LinkList p; if(L!=NULL) for(p=L;p != NULL;p=p->next) num++; return num; } //用e返回L中第i个数据元素的值 int GetElem(LinkList L,int i,ElemType *e) { int num; LinkList p; p=L; if(L != NULL) if(i>=1 && i<=ListLength(L)) for(num=0;num<i-1;num++) p=p->next; *e=p->data; cout<<"第 "<<i<<" 个数据元素的值为 "<< *e << endl; return *e; } //返回L中第1个与e满足相等关系的数据元素的位序。 void LocateElem(LinkList L,ElemType e) { int position=0; LinkList p=L; if(L!=NULL) while (p!=NULL) { position++; if(e==p->data)//找到满足条件的数据 cout<<"元素 "<<e<<" 链表中的的位置为第 "<<position<<" 位"<<endl; p=p->next; } } //若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义 void PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) { LinkList p=L; LinkList q=p; int count=0; int flag=0;//用来标识当前元素是否是首元节点 if(L!=NULL) while (p->next != NULL) { count++; if(cur_e==p->data) { flag=1;//当前元素为首元节点 break; } if(cur_e == p->next->data && cur_e != L->data) { flag=0; break; } p=p->next; } if(flag==0 && count != 0 && p != NULL) { cout<<cur_e<<" 的前驱结点为:"<< p->data<<endl; } if(flag==1)//首元节点没有前驱 { cout<<"第一个元素没有前驱!!!!"<<endl; } } //若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义 void NextElem(LinkList L,ElemType cur_e,ElemType *next_e) { LinkList p=L; if(L!=NULL) while (p!=NULL) { if(cur_e==p->data){ break; } p=p->next; } if (p!=NULL&&p->next!=NULL) { *next_e=p->next->data; cout<<cur_e<<" 的后继结点为:"<<*next_e<<endl; } else cout<<"最后一个元素没有后继!!!!"<<endl; } //向已存在的无头节点链表插入元素 void ListInsert(LinkList &L,int i,ElemType e) { LinkList p=L; LinkList q=L; LinkList s; int j=0; while (q->next!=NULL && j<i-1)//从首元节点开始寻找第i-1个节点 { q=q->next; if(p->next!=q) p=p->next;//将p指向要插入节点位置的前驱节点处 j++; } if(!(q->next) || j>i-1)//i小于1或者大于表长加1 { cout<<"插入位置不合法!"<<endl; exit(0); } s=(LinkList)malloc(sizeof(*s));//生成新结点保存要插入的数据结点 if(!s)//分配空间失败 exit(0); s->data=e; if(i==1){ s->next=p; L=s; } else { s->next=q; p->next=s; } } //头插法创建无头节点链表 void ListHeadInsert(LinkList &L) { LinkList p;//p指向要插入节点的位置 int i,j; for(i=1,j=0;i<=10;i++,j++){ p=(LinkList)malloc(sizeof(*p)); if(!p)//分配空间失败 exit(0); p->data=j; if(L!=NULL) p->next=L; else p->next=NULL; L=p;//头指针移动 } } //尾插法创建无头节点链表 void ListTailInsert(LinkList &L) { LinkList pTail=L;//把尾赋给尾指针 LinkList p; int i,j; for(i=1,j=0;i<=10;i++,j++) { p=(LinkList)malloc(sizeof(*p)); if(!p)//分配空间失败 exit(0); p->data=j; if(L!=NULL) pTail->next=p;//链表非空时,新结点插入在尾部 else L=p;//链表为空时,p赋给第一个节点 p->next=NULL; pTail=p;//修改尾指针指向新的尾结点 } } //删除L的第i个数据元素,并用e输出其值 void ListDelete(LinkList &L,int i,ElemType *e) { LinkList p=L; LinkList q=L; int j=0; while(q->next != NULL && j < i-1)//寻找第i个结点,并令p指向其前驱 { q=q->next; if(p->next!=q) p=p->next; j++; } if(!(q->next) || j > i-1) { cout<<"删除位置不合理!"<<endl; exit(0); } if(i==1)//删除位置为1 { q=p; *e=q->data; p=q->next; L=p;//头指针移动 } else { *e=q->data; p->next=q->next; } cout<<"删除第 "<<i<<" 个数据 "<< *e <<" 成功"<<endl; free(q); //释放删除的结点 } //依次对L的每个数据元素遍历 void ListTraverse(LinkList L) { LinkList p=L; cout<<"输出链表为:"; while (p != NULL) { cout<<p->data<<" "; p=p->next; } cout<<endl; } int main() { LinkList L; InitList(L); ListHeadInsert(L);//头插法 //ListTailInsert(L);//尾插法 ListTraverse(L); /* int cPosition; ElemType cData; int length=ListLength(L); cout<<"请输入需要插入位置(1-"<<length-1<<"):"; cin>>cPosition; cout<<"请输入需要插入的元素:"; cin>>cData; ListInsert(L,cPosition,cData);//在特定位置插入结点 ListTraverse(L);//新链表输出 */ /* //测试ListDelete函数 ElemType dNum; int dPosition; cout<<"请输入删除元素的位置:"; cin>>dPosition; ListDelete(L,dPosition,&dNum); ListTraverse(L); */ /* //测试PriorElem函数和NexElem函数 ElemType cur_e,pre_e,next_e; cout<<"请输入当前元素数据:"; cin>>cur_e; PriorElem(L,cur_e,&pre_e); NextElem(L,cur_e,&next_e); */ /* //测试LocateElem函数 ElemType elem; cout<<"请输入需要查找的元素:"; cin>>elem; LocateElem(L,elem); */ /* //测试GetElem函数 ElemType elem; int ePosition; cout<<"请输入需要获取元素的位置:"; cin>>ePosition; GetElem(L,ePosition,&elem); */ /* //测试ListLength函数 int len; len=ListLength(L); cout<<"链表长度为:"<<len<<endl; */ /* //测试ListEmpty函数 int re =ListEmpty(L); cout<<re<<endl;//返回0表示非空,1表示链表为空 */ /* //测试ClearList函数 ClearList(L); */ /* //测试DestroyList函数 DestroyList(L); */ return 0; }