二.单链表的基本操作

声明：用C语言实现，，由于自己码的，可能会有出入，仅供参考！

//---------------------线性表的单链表存储结构---------------------//

/*c2.h*/ typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;

1.构造一个空的线性表 L

Status InitList (LinkList *L){ *L=(LinkList)malloc(sizeof(struct LNode));/*产生头结点，并使L指向此头结点*/ if(!*L)/*存储分配失败*/ exit(OVERFLOW); (*L)->next=null;/*指针域为空*/ return OK; }

2.销毁线性表L

Status DestroyList(LinkList *L){ LinkList q; while(*L){ q=(*L)->next; free(*L); *L=q; } return OK; }

3.将线性表L重置为空表

Status ClearList(LinkList L){ LinkList p,q; p=L->next; while(p){ q=p->next; free(p); p=q; } L->next=NULL; return OK; }

4.判断线性表L是否是空表

​ 操作结果：若表为空表，则返回TRUE,否则返回FALSE

Status ListEmpty (LinkList L){ if(L->next) return FALSE; else return TRUE; }

5.判断线性表L中数据元素个数

​ 操作结果：返回线性表L中元素个数

Status ListLength(LinkList L){ int i=0; LinkList p=L->next; while(p){ i++; p=p->next; } return i; }

6.选取单链表中第i个元素（GetElem)

​ 操作结果：当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR

Status GetElem(LinkList L,int i,ElemType *e){ int j=1; LinkList p=->next; while(p&&j<i){ p=p->next; j++; } if(!p||j>i) return ERROR; *e=p->data; return OK; }

7.返回L中第1个与e满足关系compare()的数据元素的位序。

/* 初始条件:线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */ int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 操作结果: 返回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; }

8.返回前驱

Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) { LinkList q,p=L->next; /* p指向第一个结点 */ while(p->next) /* p所指结点有后继 */ { q=p->next; /* q为p的后继 */ if(q->data==cur_e){ *pre_e=p->data; return OK; } p=q; /* p向后移 */ } return INFEASIBLE; }

9.返回后继

Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e) { LinkList p=L->next; /* p指向第一个结点 */ while(p->next) /* p所指结点有后继 */ { if(p->data==cur_e) { *next_e=p->next->data; return OK; } p=p->next; } return INFEASIBLE; }

10.往单链表中插入元素

/* 在带头结点的单链线性表L中第i个位置之前插入元素e */ Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */ { 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(struct LNode)); /* 生成新结点 */ s->data=e; /* 插入L中 */ s->next=p->next; p->next=s; return OK; }

11.删除单链表中某一个元素

/* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */ Status ListDelete(LinkList L,int i,ElemType *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; }

12.ListTraverse–依次对表中的每一个元素调用函数visit().一旦visit()失败，则操作失败

Status ListTraverse(LinkList L,void(*vi)(ElemType)) { LinkList p=L->next; while(p) { vi(p->data); p=p->next; } printf("\n"); return OK; }

%%程序用到的库函数以及宏定义%%

/*c1.h*/ #include<string.h> #include<ctype.h> #include<malloc.h> /* malloc()等 */ #include<limits.h> /* INT_MAX等 */ #include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h> /* atoi() */ #include<io.h> /* eof() */ #include<math.h> /* floor(),ceil(),abs() */ #include<process.h> /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

%%主程序%%

#include"c1.h" typedef int ElemType; #include"c2.h" #include"bo2.c" /*前面12个基本操作方法*/ Status comp(ElemType c1,ElemType c2) { /* 数据元素判定函数(相等为TRUE,否则为FALSE) */ if(c1==c2) return TRUE; else return FALSE; } void visit(ElemType c) /* 与main2-1.c不同 */ { printf("%d ",c); } void main() { LinkList L; ElemType e,e0; Status i; int j,k; /*创建表*/ i=InitList(&L); /*往表中插入元素*/ for(j=1;j<=5;j++) i=ListInsert(L,1,j); printf("在L的表头依次插入1～5后：L="); ListTraverse(L,visit); /* 依次对元素调用visit()，输出元素的值 */ /*判断表是否为空表*/ i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)\n",i); /*清空表中元素*/ i=ClearList(L); printf("清空L后：L="); ListTraverse(L,visit); /*再次判断表是否为空表*/ i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)\n",i); /*再次插入元素*/ for(j=1;j<=10;j++) ListInsert(L,j,j); printf("在L的表尾依次插入1～10后：L="); ListTraverse(L,visit); /*选取单链表中第i个元素*/ GetElem(L,5,&e); printf("第5个元素的值为：%d\n",e); /*返回L中第1个与e满足关系compare()的数据元素的位序*/ for(j=0;j<=1;j++) { k=LocateElem(L,j,comp); if(k) printf("第%d个元素的值为%d\n",k,j); else printf("没有值为%d的元素\n",j); } /*返回前驱*/ for(j=1;j<=2;j++) /* 测试头两个数据 */ { GetElem(L,j,&e0); /* 把第j个数据赋给e0 */ i=PriorElem(L,e0,&e); /* 求e0的前驱 */ if(i==INFEASIBLE) printf("元素%d无前驱\n",e0); else printf("元素%d的前驱为：%d\n",e0,e); } /*返回后继*/ for(j=ListLength(L)-1;j<=ListLength(L);j++)/*最后两个数据 */ { GetElem(L,j,&e0); /* 把第j个数据赋给e0 */ i=NextElem(L,e0,&e); /* 求e0的后继 */ if(i==INFEASIBLE) printf("元素%d无后继\n",e0); else printf("元素%d的后继为：%d\n",e0,e); } k=ListLength(L); /* k为表长 */ /*删除表中某一个数据*/ for(j=k+1;j>=k;j--) { i=ListDelete(L,j,&e); /* 删除第j个数据 */ if(i==ERROR) printf("删除第%d个数据失败\n",j); else printf("删除的元素为：%d\n",e); } printf("依次输出L的元素："); ListTraverse(L,visit); /*销毁表*/ DestroyList(&L); printf("销毁L后：L=%u\n",L); }