数据结构线性表单链表基本操作
//LinkNode类型声明 typedef struct LNode { ElemType data; //存放元素值 struct LNode * next; //指向后继结点 } LinkNode; //单链表节点类型
//头插法 void CreatListF(LinkNode * &L,ElemType a[],int n) { LinkNode * s; L=(LinkNode * )malloc(sizeof(LinkNode)); L->next=NULL; //创建头结点，其next域置为NULL for(int i=0;i<n;i++) //循环建立数据结点s { s=(LinkNode * )malloc(sizeof(LinkNode)); s->data=a[i]; //创建数据结点s s->next=L->next; //将结点s插入到原首结点之前，头结点之前 L->next=s; } }
//尾插法 void CreatListR(LinkNode * &L,ElemType a[],int n) { LinkNode * s,* r; L=(LinkNode * )malloc(sizeof(LinkNode)); //创建头结点 r=L; //r始终指向尾结点，初始时指向头结点 for(int i=0;i<n;i++) //循环建立数据结点 { s=(LinkNode)malloc(sizeof(LinkNode)); s->data=a[i]; //创建数据结点s r->next=s; //将结点s插入到结点r之后 r=s; } r->next=NULL; //尾结点的next域置为NULL }
//初始化线性表 void InitList(LinkNode * &L) { L=(LinkNode * )malloc(sizeof(LinkNode)); L->next=NULL; //创建头结点，其next域置为NULL }
//销毁线性表 void DestroyList(LinkNode * &L) { LinkNode * pre=L, * p=L->next; //pre指向结点p的前驱结点 while(p!=NULL) //扫描单链表L { free(pre); //释放pre结点 pre=p; //pre,p同步后移一个结点 p=pre->next; } free(pre); //循环结束时，p为NULL，pre指向尾结点，释放它 }
//判断线性表是否为空表 bool ListEmpty(LinkNode * L) { return(L->next==NULL); //看单链表中是否有数据结点 }
//求线性表的长度 int ListLength(LinkNode * L) { int n=0; LinkNode * p=L; //p指向头结点，n置为0 while(p->next!=NULL) { n++; p=p->next; } return(n); //循环结束，p指向尾结点，其序号n为结点个数 }
//输出线性表 void DispList(LinkNode * L) { LinkNode * p=L->next; //p指向首结点 while(p!==NULL) //p不为NULL，输出p结点的data域 { printf("%d",p->data); p=p->next; //p移向下一个结点 } printf("\n"); }
//求线性表中的某个元素值 bool GetElem(LinkList * L,int i,ElemType &e) { int j=0; LinkNode * p=L; //p指向头结点，j置为0 if(i<=0)return false; //i错误返回假 while(j<i && p!=NULL) //找第i个结点p { j++; p=p->next; } if(p==NULL) //不存在第i个数据结点，返回false { return false; } else //存在第i个数据结点，返回true { e=p->data; return ture; } }
//按元素值进行查找 int LocateElem(LinkNode * L,Elemtype e) { int i=1; LinkNode * p=L->next; //p指向首结点i,置为1 while(p!=NULL && p->data!=e) //查找data值为e的结点，其序号为i { p=p->next; i++; } if(p==NULL) //不存在值为e的结点，返回0 { return 0; } else //存在值为e的结点，返回其逻辑序号i { return (i); } }
//插入数据元素 bool ListInsert(LinkNode * &L,int i,ElemType e) { int j=0; LinkNode * p=L, * s; //p指向头结点，j置为0(即头结点的序号为0) if(i<=0)return false; //i错误返回false while(j<i-1 && p!=NULL) //查找第i-1个结点p { j++; p=p->next; } if(p==NULL) //未找到第i-1个结点，返回false { return false; } else //找到第i-1个结点p，插入新结点并返回true { s=(LinkNode * )malloc(sizeof(LinkNode)); s->data=e; //创建新结点s，其data域置为e s->next=p->next;//将结点s插入到结点p之后 p->next=s; return true; } }
//删除数据元素 bool LinstDelete(LinkNode * &L,ElemType &e) { int j=0; LinkNode * p=L, * q; //p指向头结点，j置为0(即头结点的序号为0) if(i<=0)return false; //i错误返回false while(j<i-1 && p!=NULL) //查找第i-1个头结点 { j++; p=p->next; } if(pNULL) //未找到第i-1个头结点，返回false { return false; } else //找到第i-1个头结点p { q=p->next; //q指向第i个结点 if(qNULL) //若不存在第i个结点，返回false { return false; } e=q->data; p->next=q->next; //从单链表中删除q结点 free(q); //释放q结点 return true; //返回true表示成功删除第i个结点 } }
