软件技术基础实验一单链表的各种基本运算.doc

#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0typedefint Status;typedefintElemType;typedefstructLNode ElemType data;structLNode *next;LNode,*LinkList;Status InitList_L(LinkList&L) /初始化线性表L=(LinkList )malloc(sizeof(LNode); /L指向头节点，头节点数据域为空L-next=NULL;return OK;/ InitList_LStatus DispList_L(LinkList&L) /输出线性表LinkList p=L-next;while(p!=NULL)printf(%c,p-data);p=p-next;return OK; / DispList_LStatus CreateList_L(LinkList&L,ElemType a,int n) /尾插法建表LinkLists,r;inti;L=(LinkList )malloc(sizeof(LNode);r=L;for(i=0;idata=ai;r-next=s;r=s; r-next=NULL;return OK;/ CreateList_LStatus ListLength_L(LinkList L) /求线性表的长度LinkList p=L;int n=0;while(p-next!=NULL)n+;p=p-next;return(n);/ ListLength_LStatus ListEmpty_L(LinkList L) /判断单链表是否为空return(L-next=NULL);/ ListEmpty_LStatus DestroyList_L(LinkList&L) /销毁线性表LinkList p=L,q=p-next;while(q!=NULL)free(p);p=q;q=p-next;free(p);return OK;/ DestroyList_LStatus GetElem_L(LinkList L, inti, ElemType&e) / L为带头节点的单链表的头指针。/ 当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORint j=0;LinkList p=L;while(jnext;if(p=NULL)return ERROR;elsee=p-data;return OK;/ GetElem_LStatus ListInsert_L(LinkList&L, inti, ElemType e) /插入数据元素int j=0;LinkList p=L,s;/*找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素*/while(jnext;if(p=NULL)return ERROR;elses=(LinkList )malloc(sizeof(LNode);s-data=e; s-next=p-next; p-next=s;return OK;/ ListInsret_LStatus ListDelete_L(LinkList&L, inti, ElemType&e) /删除数据元素int j=0;LinkList p=L,q;while(jnext;if(p=NULL)return ERROR;elseq=p-next;/q为要删除的元素节点if(q=NULL)return ERROR;e=q-data;/e为删除节点的数据区域p-next=q-next;free(q);return OK;/ ListDelete_LintLocateElem_L(LinkList L, ElemType e) /按元素值查找元素LinkList p=L-next;inti=1;while(p!=NULL&p-data!=e)p=p-next;i+;/如果要插入的节点为头节点，则退出if(p=NULL)return ERROR;elsereturn(i);/ LocateElem_Lint main() ElemTypee,a5=a,b,c,d,e;LinkList L;printf(1)初始化单链表Ln);InitList_L(L); /初始化单链表Lprintf(2)依次采用尾插法插入a,b,c,d,e元素n);CreateList_L(L,&a0,5); /依次采用尾插入法插入a，b，c，d，e元素printf(3)输出单链表L：); DispList_L(L); /输出单链表Lprintf(n);printf(4)单链表L的长度为：); printf(%d,ListLength_L(L); /输出单链表L的长度printf(n);if(ListEmpty_L(L) printf(5)该单链表为空n); elseprintf(5)该单链表不为空n); /判断单链表L是否为空GetElem_L(L,3,e);printf(6)单链表L的第三个元素为：); printf(%c,e); printf(n); /输出单链表L的第3个元素printf(7)单链表L中a的位置为：); printf(%d,LocateElem_L(L,a); /输出元素a的位置printf(n); ListInsert_L(L,4,f); /在第4个元素位置插入f元素printf(8)在第4个元素位置上插入 f 元素n); printf(9)输出单链表L：);DispList_L(L); /输出单链表Lprintf(n); ListDelete_L(L,3,e); /删除L的第3个元素