《算法与数据结构》实验指导书Status ListDestroy_Link (LinkList L)（/*初始条件：线性表L已存在。*/*操作结果：销毁线性表L*/LinkList q:while(L)tq=L->next;free(L);L=q;-returnOK:3Status ListClear Link (LinkList L)/*不改变L*/（/*初始条件：线性表L已存在。**操作结果：将L重置为空表*LinkList p,q:p=L->next：/*p指向第一个结点*/while(p)/*没到表尾*/q=p->next;free(p);p=q;3L->next=NULL；/*头结点指针域为空*/returnOK;3Status ListEmpty_Link (LinkList L)（/*初始条件：线性表L已存在。*//*操作结果：若L为空表，则返回TRUE，否则返回FALSE*16
《算法与数据结构》实验指导书 16 Status ListDestroy_Link (LinkList L) { /* 初始条件：线性表 L 已存在。*/ /* 操作结果：销毁线性表 L */ LinkList q； while(L) { q=L->next； free(L)； L=q； } return OK； } Status ListClear_Link (LinkList L) /* 不改变 L */ { /* 初始条件：线性表 L 已存在。*/ /* 操作结果：将 L 重置为空表 */ LinkList p,q； p=L->next； /* p 指向第一个结点 */ while(p) /* 没到表尾 */ { q=p->next； free(p)； p=q； } L->next=NULL； /* 头结点指针域为空 */ return OK； } Status ListEmpty_Link (LinkList L) { /* 初始条件：线性表 L 已存在。*/ /* 操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
《算法与数据结构》实验指导书if(L->next)/*非空*/returnFALSE;elsereturn TRUE;3int ListLength_Link (LinkList L)（/*初始条件：线性表L已存在。*/*操作结果：返回L中数据元素个数*/int i=0;LinkListp=L->next；/*p指向第一个结点*/while(p)/*没到表尾*/ti++;p=p->next;return i;3/*算法2.8*/StatusGetElem Link (LinkListL,int i,ElemType&e)（/*初始条件：L为带头结点的单链表的头指针*/*操作结果：当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR*/intj=l/*j为计数器*/LinkListp=L->next；/*p指向第一个结点*/while(p&&j<i)/*顺指针向后查找,直到p指向第i个元素或p为空*/p=p->next:j++;-/*第1个元素不存在*if(pli>i)return ERROR;17
《算法与数据结构》实验指导书 17 if(L->next) /* 非空 */ return FALSE； else return TRUE； } int ListLength_Link (LinkList L) { /* 初始条件：线性表 L 已存在。*/ /* 操作结果：返回 L 中数据元素个数 */ int i=0； LinkList p=L->next； /* p 指向第一个结点 */ while(p) /* 没到表尾 */ { i++； p=p->next； } return i； } Status GetElem_Link (LinkList L,int i,ElemType &e) /* 算法 2.8 */ { /* 初始条件: L 为带头结点的单链表的头指针*/ /* 操作结果：当第 i 个元素存在时,其值赋给 e 并返回 OK,否则返回 ERROR */ int j=1； /* j 为计数器 */ LinkList p=L->next； /* p 指向第一个结点 */ while(p&&j<i) /* 顺指针向后查找,直到 p 指向第 i 个元素或 p 为空 */ { p=p->next； j++； } if(!p||j>i) /* 第 i 个元素不存在 */ return ERROR；
《算法与数据结构》实验指导书/*取第i个元素*/e=p->data;return OK;3int LocateElem Link (LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)（/*初始条件：线性表L已存在，compareO是数据元素判定函数（满足为1,否则为0）*//*操作结果：返回L中第1个与e满足关系compareO的数据元素的位序。*/ /*若这样的数据元素不存在则返回值为0*int i=0;LinkList p=L->next;while(p)ti++;if(compare(p->data,e))/*找到这样的数据元素*/return i;p=p->next;return O;StatusListlnsertLink(LinkListL,inti,ElemTypee)/*算法2.9,不改变L*（/*在带头结点的单链线性表L中第i个位置之前插入元素e*/int j=0;LinkList p=L,s;while(p&&j<i-1)/*寻找第i-1个结点*/p=p->next;j++;1if(!pli>i-1)/*i小于1或者大于表长*/returnERROR;18
《算法与数据结构》实验指导书 18 e=p->data； /* 取第 i 个元素 */ return OK； } int LocateElem_Link (LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始条件: 线性表 L 已存在,compare()是数据元素判定函数(满足为 1,否则为 0) */ /* 操作结果: 返回 L 中第 1 个与 e 满足关系 compare()的数据元素的位序。 */ /* 若这样的数据元素不存在,则返回值为 0 */ int i=0； LinkList p=L->next； while(p) { i++； if(compare(p->data,e)) /* 找到这样的数据元素 */ return i； p=p->next； } return 0； } Status ListInsert_Link (LinkList L,int i,ElemType e) /* 算法 2.9,不改变 L */ { /* 在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e */ int j=0； LinkList p=L,s； while(p&&j<i-1) /* 寻找第 i-1 个结点 */ { p=p->next； j++； } if(!p||j>i-1) /* i 小于 1 或者大于表长 */ return ERROR；
《算法与数据结构》实验指导书s-(LinkList)malloc(sizeof(structLNode))：/*生成新结点*//*插入L中*/s->data=e:s->next=p->next;p->next=s;return OK;3StatusListDelete_Link(LinkList L,int i,ElemType&e)/*算法2.10,不改变L*/（/*在带头结点的单链线性表L中，删除第i个元素,并由e返回其值*/int j=0;LinkList p=L,q:while(p->next&&j<i-1)/*寻找第i个结点,并令p指向其前趋*/tp=p->next;j++;3if(!p->nextli>i-1)/*删除位置不合理*/return ERROR;/*删除并释放结点*/q=p->next;p->next=q->next;e=q->data;free(q);returnOK;1Status ListTraverseLink (LinkListL)（/*初始条件：线性表L已存在*//*操作结果：依次对L的每个数据元素的值进行输出*LinkList p-L->next;while(p)-19
《算法与数据结构》实验指导书 19 s=(LinkList)malloc(sizeof(struct LNode))； /* 生成新结点 */ s->data=e； /* 插入 L 中 */ s->next=p->next； p->next=s； return OK； } Status ListDelete_Link (LinkList L,int i,ElemType &e) /* 算法 2.10,不改变 L */ { /* 在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值 */ int j=0； LinkList p=L,q； while(p->next&&j<i-1) /* 寻找第 i 个结点,并令 p 指向其前趋 */ { p=p->next； j++； } if(!p->next||j>i-1) /* 删除位置不合理 */ return ERROR； q=p->next； /* 删除并释放结点 */ p->next=q->next； e=q->data； free(q)； return OK； } Status ListTraverse_Link (LinkList L) { /* 初始条件：线性表 L 已存在 */ /* 操作结果:依次对 L 的每个数据元素的值进行输出 */ LinkList p=L->next； while(p) {
《算法与数据结构》实验指导书printf("%d",p->data);p=p->next;3printf("\n");return OK;3void CreateList_Link(LinkList&L,int n) /*算法2.11*/（/*逆位序（插在表头）输入n个元素的值，建立带表头结构的单链线性表L*/int i;LinkList p;L=(LinkList)malloc(sizeof(struct LNode):L->next=NULL；/*先建立一个带头结点的单链表*/printf("请输入%d个数据\n",n);for(i=n; i>0; --i)tp=(LinkList)malloc(sizeof(structLNode)：/*生成新结点*scanf("%d",&p->data)；/*输入元素值*/p->next=L->next；/*插入到表头*/L->next=p;11voidCreateList2Link(LinkList&L,intn)（/*正位序（插在表尾）输入n个元素的值，建立带表头结构的单链线性表*/int i;LinkList p,q;L=(LinkList)malloc(sizeof(structLNode))：/*生成头结点*/L->next-NULL;q=L;printf("请输入%d个数据\n",n);for(i=l;i<=n; i++)20
《算法与数据结构》实验指导书 20 printf("%d",p->data)； p=p->next； } printf("\n")； return OK； } void CreateList_Link (LinkList &L,int n) /* 算法 2.11 */ { /* 逆位序(插在表头)输入 n 个元素的值，建立带表头结构的单链线性表 L */ int i； LinkList p； L=(LinkList)malloc(sizeof(struct LNode))； L->next=NULL； /* 先建立一个带头结点的单链表 */ printf("请输入%d 个数据\n",n)； for(i=n；i>0；-i) { p=(LinkList)malloc(sizeof(struct LNode))； /* 生成新结点 */ scanf("%d",&p->data)； /* 输入元素值 */ p->next=L->next； /* 插入到表头 */ L->next=p； } } void CreateList2_Link (LinkList &L,int n) { /* 正位序(插在表尾)输入 n 个元素的值，建立带表头结构的单链线性表 */ int i； LinkList p,q； L=(LinkList)malloc(sizeof(struct LNode))； /* 生成头结点 */ L->next=NULL； q=L； printf("请输入%d 个数据\n",n)； for(i=1；i<=n；i++)