线性表的链式存储结构实现-实验3报告

实验三线性表的链式存储结构实现指导老师：朱芳学号：13011432班级：13083414姓名：张杭俊【实验目的】1.掌握线性表的链式结构的定义；2.掌握链式存储结构结点的访问方法；3.熟练运用链表的基本操作；【实验原理】1.带头结点的单链表基本结构在链表的第一个结点之前附设一个结点，称为头结点。带头结点的单链表：头结点的引入使得单链表的头指针永远不为空，从而给插入、删除等操作带来了方便。2.单链表的基本操作以下p、q为指向任意结点的指针。1)判空表：head-next==NULL2)是否为表尾：p-next==NULL3)指针后移：p=p-next4)结点连接：p-next=q（q结点放在p结点之后）5)前驱：若p-next==q，则p指向q的前驱结点【实验要求】1.熟悉线性表的逻辑结构特点；2.熟悉线性表常用操作特点；3.理解以上给出的线性表顺序存储结构基本原理；4.项目组织及文件命名要规范；【实验内容】1.用chainlist.h和chainlist.cpp文件内容建4工程#chainlist.h#includeiostreamusingnamespacestd;typedefcharDataType;structNode{DataTypedata;structNode*next;};intInitList(Node*&H);intListEmpty(Node*H);intListLength(Node*H);voidTraverseList(Node*H);intFind_item(Node*H,DataTypeitem);intFind_pos(Node*H,intpos,DataType*item);intListInsert(Node*H,intpos,DataTypeitem);intListDelete(Node*H,DataTypeitem);voidDestroyList(Node*&H);#chainlist.cpp#includechainlist.hintInitList(Node*&H){H=newNode;if(!H){cout初始化错误endl;return0;}H-next=NULL;return1;}intListEmpty(Node*H){if(H-next)return0;elsereturn1;}intListLength(Node*H){Node*p=H-next;inttotal=0;while(p){total++;p=p-next;}returntotal;}voidTraverseList(Node*H){Node*p=H-next;while(p){coutp-data;p=p-next;}coutendl;}intFind_item(Node*H,DataTypeitem){Node*p=H-next;intpos=0;while(p){pos++;if(p-data==item)break;p=p-next;}if(p)returnpos;elsereturn0;}intFind_pos(Node*H,intpos,DataType*item){Node*p=H-next;inti=1;while(p&&i!=pos){p=p-next;i++;}if(p==NULL){cout位置无效endl;return0;}*item=p-data;return1;}intListInsert(Node*H,intpos,DataTypeitem){Node*p=H;inti=0;while(p){if(i+1==pos)break;p=p-next;i++;}if(p==NULL){cout插入位置无效endl;return0;}Node*t=newNode;t-data=item;t-next=p-next;p-next=t;return1;}intListDelete(Node*H,DataTypeitem){Node*p=H,*t;inti=0;while(p-next){if(p-next-data==item)break;p=p-next;}if(p-next==NULL){cout删除元素不存在endl;return0;}t=p-next;p-next=t-next;deletet;return1;}voidDestroyList(Node*&H){Node*p=H;while(H){p=H;H=H-next;deletep;}}#主程序（3）#includechainlist.hintmain(){Node*head;DataTypet;InitList(head);for(inti=0;i4;i++)ListInsert(head,1,'a'+i);/*//尾插法for(inti=0;i5;i++)ListInsert(head,i+1,'a'+i);*/if(ListEmpty(head)==1)cout\n单链表空!endl;else{cout\n当前链表长度是ListLength(head)，表中元素为：;TraverseList(head);}Find_pos(head,3,&t);cout\n第三个元素是tendl;cout\na在Find_item(head,'a')号位置endl;ListInsert(head,3,'f');cout\n在3号为插入f表中的元素为：;TraverseList(head);cout\n输入你想要删除的元素：;cint;if(ListDelete(head,t)==1){cout\n删除t成功。表中元素为：;TraverseList(head);}elsecout\n删除\'t\'失败。表中元素没有变化;DestroyList(head);return1;}2.设计接口函数intListInsert_order(Node*H,DataTypeitem);intListInsert_order(Node*H,DataTypeitem){Node*p=H;while(p-next&&itemp-next-data)p=p-next;Node*t=newNode;t-data=item;t-next=p-next;p-next=t;return1;}3.储存学生信息在chainlist.h重新设计链表中的元素类型DataTypestructGrade{intid;floatscore;};typedefGradeDataType;//删除学号为number的节点intListDelete(Node*H,intnumber);主函数#includechainlist.hintmain(){Node*head;InitList(head);DataTypeA[]={{101,85},{103,90.5},{104,73},{105,55}};for(inti=0;i4;i++)ListInsert(head,i+1,A[i]);cout学号成绩endl;TraverseList(head);ListDelete(head,103);cout学号成绩endl;TraverseList(head);DestroyList(head);return1;}【实验总结】通过本次实验，对于线性表的链式存储结构实现的表示方法有了更深的理解；熟悉了工程项目文件的组织方式；将课本上所学到的算法用C++实现，从中看到了链式存储结构的优缺点；对于学习链式存储结构很有帮助。