《实验二单链表基本操作的实现》由会员分享，可在线阅读，更多相关《实验二单链表基本操作的实现（11页珍藏版）》请在金锄头文库上搜索。
1、实验二 单链表基本操作的实现【实验课程名称】数据结构【实验项目名称】单链表基本操作的实现【实验目的】1 理解单链表的存储结构及基本操作的定义；2掌握单链表存储基本操作；3学会设计实验数据验证程序。【实验仪器及环境】计算机，window xp操作系统，VC+6.0【实验内容及步骤】1 单链表顺序存储基本操作存储结构定义：typedef struct LNode /结点类型 ElemType data; struct LNode *next;*Link,*Position;typedef struct /链表类型Link head,tail;int len;LinkList;实现的基本操作：#in
2、clude#include#include#includeusing namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNode /结点类型ElemType data;struct LNode *next;*Link,*Position;typedef struct /链表类型Link head,tail;int l
3、en;LinkList;Position MakeNode_L(Link &p,ElemType e) /创建结点p=(Link)malloc(sizeof(LNode);if(!p) return ERROR;p-data=e;p-next=NULL;return p;void FreeNode_L(Link &q) /释放结点free(q);Status InitList_L(LinkList &L)/初始化L为一个带头结点的空链表,头尾指针指向头结点，表长赋ElemType e;e=-1;/实际应用中此初始化语句需要修改if(!MakeNode_L(L.head,e)return ERR
4、OR;/开辟头结点L.tail=L.head;L.len=0;return OK;/InitList_LStatus DestroyList_L(LinkList &L)/销毁链表LLink p;while(p=L.head-next)/依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head-next=p-next;free(p);free(L.head);L.head=NULL;L.tail=NULL;L.len=0;coutendlThe list has been destroyed!next;while(p)q=p-next;free(p);p=q;L.tail=L.hea
5、d;L.len=0;return OK;Status InsFirst_L(LinkList &L,Link s) /在首元素前插入一个结点s-next=L.head-next;if(!L.head-next)L.tail=s;L.head-next=s;L.len+;return OK;Status DelFirst_L(LinkList &L,Link h,Link &q) /删除首结点h=L.head;q=L.head-next;if(q)h-next=q-next;q-next=NULL;if(!h-next)L.tail=h;L.len-;return OK;elsereturn E
6、RROR;Status Append_L(LinkList &L,Link s) /将两个链表跟一个字符串连接起来Link q;if(!L.head-next)L.head-next=q=s;elseL.tail-next=q=s;while(q-next)q=q-next;L.tail=q;return OK;Position Remove_L(LinkList &L,Link &q) /删除尾结点Link p;p=L.head;if(!L.head-next) coutThe LinkList is empty!next!=L.tail)p=p-next;q=L.tail;L.tail=p
7、;L.tail-next=NULL;L.len-;return q;Status InsBefore_L(LinkList &L,Link &p,Link s) /在p指向的结点前插入一个结点Link q;q=L.head;if(p=L.head) cout 不能在这个地方插入元素!next!=p)q=q-next;s-next=p;q-next=s;L.len+;return OK;Status InsAfter_L(LinkList &L,Link &p,Link s) /在p指向的结点后插入一个结点if(p=L.tail) L.tail=s;s-next=p-next;p-next=s;
8、L.len+;return OK;Status SetCurElem_L(Link &p,ElemType e) /改变p指向的结点的内容p-data=e;return OK;ElemType GetCurElem_L(Link p) /获取p指向的结点的内容return p-data;int ListLength_L(LinkList L) /获取单链表的长度值return L.len;Status ListEmpty_L(LinkList L) /判断单链表是否为空，是返回，否返回if(L.head=L.tail) return TRUE;else return FALSE;Positio
9、n GetHead_L(LinkList L) /获取头指针的地址return L.head;Position GetLast_L(LinkList L) /获取尾指针的地址return L.tail;Position PriorPos_L(LinkList L,Link p) /获取p的前驱Link q;q=L.head;if(p=L.head-next) return NULL;elsewhile(q-next!=p)q=q-next;return q;Position NextPos_L(LinkList L,Link p) /获取p的后继if(!p-next) return NULL;
10、return p-next;Status LocatePos_L(LinkList L,int i,Link &p) /查找p在单链表中的位置iint j;if(inext;for(j=1;jnext;if(!p) return ERROR;return OK;Status compare(ElemType x,ElemType y) /比较函数if(x=y)return 1;elsereturn 0;Status LocateElem_L(LinkList L,ElemType e,Link &p) /返回跟e相同的值，没有的话返回空指针int i=0;p=L.head;doi+;p=p-n
11、ext;while(p&!compare(p-data,e);if(p)coutiendl;elsecoutIt is not in here!next;while(p-next)visit(p-data);p=p-next;return OK;Status ListInsert_L(LinkList &L,int i,ElemType e) /在第i个位置后插入一个元素int j;Link p,s;s=(Link)malloc(sizeof(LNode);p=L.head-next;for(j=1;jnext;s-data=e;s-next=p-next;p-next=s;L.len+;return OK;Status ListDelete_L(LinkList &L,int i) /删除第i个元素的结点if(iL.len) return ERROR;int j;Link p;p=L.head-next;for(j=1;jnext;p-next=p-next-next;L.len-;return OK;
