链表基本操作实验报告

实验2链表基本操作实验一、实验目的1．定义单链表的结点类型。2．熟悉对单链表的一些基本操作和具体的函数定义。3．通过单链表的定义掌握线性表的链式存储结构的特点。二、实验内容与要求该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。要求：同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。三、算法分析与设计。1.创建单链表：LinkedListLinkedListCreat()创建链表函数LinkedListL=LinkedListInit(),p,r;调用初始化链表函数r=L;r指向头结点使用malloc函数动态分配存储空间，指针p指向新开辟的结点，并将元素存放到新开辟结点的数据域，p=(LinkedList)malloc(sizeof(LNode));p-data=x;r-next=p;将新的结点链接到头结点r之后r=p;r指向p结点scanf(%d,&x);满足条件循环输入链表元素while(x!=flag)当输入不为-1时循环r-next=NULL;returnL;将链表结尾赋空值，返回头结点L头结点LL......^^AnA1A22.单链表插入pss-data=x;s-next=p-next;p-next=s;3.单链表的删除：pp-next=p-next-next;voidLinkedListInsert(LinkedListL,inti,ElemTypex)链表插入函数（L头指针，i插入位置，x插入元素）LinkedListp,s;定义结构体类型指针p,sj=1;p=L;定义整型j计数，寻找插入位置，p指针指向头结点p=p-next;j++;满足条件时p指针后移，j自加1while(p&&ji)当p为真且ji时循环p=NULL||jiYNprintf(插入位置不正确\n);s=(LNode*)malloc(sizeof(LNode));使用malloc函数动态分配存储空间，指针s指向新开辟的结点，并将插入元素x存放到新开辟结点s的数据域，将结点s指向i+1结点位置，第i个结点指向s，实现了链表元素插入。abxbc四、运行结果1.单链表初始化2.创建单链表3.求链表长度4.检查链表是否为空5.遍历链表6.从链表中查找元素7.从链表中查找与给定元素值相同的元素在顺序表中的位置8.向链表中插入元素插入元素之后的链表9.从链表中删除元素删除位置为6的元素(是3)10.清空单链表五、实验体会经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S流程图。六、C语言版原代码#includestdio.h#includestdlib.h/*定义ElemType为int类型*/typedefintElemType;#defineTRUE1#defineFALSE0#defineNULL0#defineflag-1/*单链表的结点类型*/typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkedList;/*初始化单链表*/LinkedListLinkedListInit(){LinkedListL;L=(LinkedList)malloc(sizeof(LNode));L-next=NULL;returnL;}/*清空单链表*/voidLinkedListClear(LinkedListL){L-next=NULL;printf(链表已经清空\n);}/*检查单链表是否为空*/intLinkedListEmpty(LinkedListL){if(L-next==NULL)returnTRUE;elsereturnFALSE;}/*遍历单链表*/voidLinkedListTraverse(LinkedListL){LinkedListp;p=L-next;if(p==NULL)printf(单链表为空表\n);else{printf(链表中的元素为：\n);while(p!=NULL){printf(%d,p-data);p=p-next;}}printf(\n);}intLinkedListLength(LinkedListL){LinkedListp;intj;p=L-next;j=0;while(p!=NULL){j++;p=p-next;}returnj;}LinkedListLinkedListGet(LinkedListL,inti){LinkedListp;intj;p=L-next;j=1;while(p!=NULL&&ji){p=p-next;j++;}if(j==i)returnp;elsereturnNULL;}intLinkedListLocate(LinkedListL,ElemTypex){LinkedListp;intj;p=L-next;j=1;while(p!=NULL&&p-data!=x){p=p-next;j++;}if(p)returnj;elsereturn0;}voidLinkedListInsert(LinkedListL,inti,ElemTypex){LinkedListp,s;intj;j=1;p=L;while(p&&ji){p=p-next;j++;}if(p==NULL||ji)printf(插入位置不正确\n);else{s=(LNode*)malloc(sizeof(LNode));s-data=x;s-next=p-next;p-next=s;printf(%d已插入到链表中\n,x);}}voidLinkedListDel(LinkedListL,inti){LinkedListp,q;intj;j=1;p=L;while(p-next&&ji){p=p-next;j++;}if(p-next==NULL)printf(删除位置不正确\n);else{q=p-next;p-next=q-next;free(q);printf(第%d个元素已从链表中删除\n,i);}}LinkedListLinkedListCreat(){LinkedListL=LinkedListInit(),p,r;ElemTypex;r=L;printf(请依次输入链表中的元素，输入-1结束\n);scanf(%d,&x);while(x!=flag){p=(LinkedList)malloc(sizeof(LNode));p-data=x;r-next=p;r=p;scanf(%d,&x);}r-next=NULL;returnL;}intscan(){intd;printf(请选择要进行的操作\n);printf(-------------------------------------------------------\n);printf(1.初始化2.清空3.求链表长度4.检查链表是否为空\n);printf(-------------------------------------------------------\n);printf(5.遍历链表6.从链表中查找元素\n);printf(-------------------------------------------------------\n);printf(7.从链表中查找与给定元素值相同的元素在顺序表中的位置\n);printf(-------------------------------------------------------\n);printf(8.向链表中插入元素9.从链表中删除元素10创建线性表\n);printf(-------------------------------------------------------\n);printf(其他键退出。。。\n);printf(输入:);scanf(%d,&d);return(d);}main(){intquit=0;inti,locate;ElemTypee;LinkedListL,p;while(!quit)switch(scan()){case1:L=LinkedListInit();printf(\n);break;case2:LinkedListClear(L);printf(\n);break;case3:printf(链表长度为%d\n,LinkedListLength(L));break;case4:if(LinkedListEmpty(L))printf(链表为空\n);elseprintf(链表非空\n);break;case5:LinkedListTraverse(L);break;case6:printf(请输入待查询元素在链表中的位置:);scanf(%d,&i);p=LinkedListGet(L,i);if(p)printf(链表第%d个元素的值为:%d\n,i,p-data);elseprintf(查询位置不正确\n);break;case7:printf(请输入待查询元素的值:);scanf(%d,&e);locate=LinkedListLocate(L,e);if(locate)printf(%d在链表中的位置是:%d\n,e,locate);elseprintf(链表中没有值为%d的元素\n,e);break;case8:printf(请输入插入元素的位置和值(中间以空格或回车分隔):\n);scanf(%d%d,&i,&e);LinkedListInsert(L,i,e);break;case9:if(LinkedListLength(L)==0)printf(链表已经为空，不能删除!\n);else{printf(请输入待删除元素的位置:);scanf(%d,&i);LinkedListDel(L,i);}break;case10:L=LinkedListCreat();printf(\n);break;default:quit=1;}}