单链表的基本算法实验报告

《单链表的基本算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单链表的的基本算法学号：日期：一、需求分析1.程序的功能（1）程序具备任意选择删除、插入、查找数据元素，和求单链表表长等几项功能。（2）当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。2.输入输出的要求（1）从键盘读入一组整数，按输入顺序形成单链表。（2）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。（3）测试数据从键盘输入一组若干数字使之形成单链表二、概要设计1.本程序所用的抽象数据类型的定义ty

2、pedefstruct{DataTypeitems[LISTSIZE];intlength;}SqList;2．主程序的流程及各程序模块之间的层次关系先定义一个顺序表，结构体里的一位数组为顺序表内容，然后调用intInitList(SqList*L)初始化顺序表，然后已键盘输入的形式输入一组一维数组，保存到顺序表里，次数组以-222作为结束符号，然后调用intTraverseList(SqListL)遍历次顺序表，在主函数里实行do-while在里面进行意选择删除、插入、查找数据元素的功能。删除功能调用intListInsertt(SqList*L)，intListInsertt(SqList

3、*L)又调用intListDelete(SqList*L)，为嵌套调用。插入功能调用intListInsert(SqList*L,intpos,DataTypeitem)此函数。查找功能调用intFind(SqListL)；在以上子函数中要用到intListEmpty(SqListL)判空函数。三、详细设计1．采用c语言定义相关的数据类型（1）用C语言描述的单链表的节点结构typedefstructNode{DataTypedata;structNode*next;}LNode,*PNode,*LinkList;四、调试分析1.调试中遇到的问题及对问题的解决方法在调试过程在运行插入和查找功能时

4、把位置找错，总是找到正确位置的后一个，后来经过仔细阅读课本发现我把书上定义理解错了。果断改正。2.算法的时间复杂度和空间复杂度O(n),空间同样为O(n).求表长3.函数调用的关系插入函数查找函数主函数删除函数五、源程序#include#includetypedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LNode,*PNode,*LinkList;intInitList(LinkList*h)/*初始化单链表*/{*h=(LinkList)malloc(sizeof(LNod

5、e));/*生成头结点*/if(!h){printf("初始化链表错误!");return0;}(*h)->next=NULL;/*头指针的指针域置为空*/return1;}intListLength(LinkListh)/*求表长*/{inttotal=0;PNodep=h->next;while(p){total++;p=p->next;}printf("单链表长度为:%d",total);returntotal;}intListEmpty(LinkListh)/*判表空*/{if(h->next)return0;elsereturn1;}intListInsert(LinkLis

6、th,intpos,DataTypex)/*插入*/{PNodep=h,q;inti=0;while(p&&inext;i++;}if(!p

7、

8、i>pos-1){printf("插入位置不合法!");return0;}q=(PNode)malloc(sizeof(LNode));/*生成新结点*/if(!p){printf("不能生成新结点");return0;}q->data=x;q->next=p->next;p->next=q;return1;}intListInsertt(LinkListh)/*选择插入*/{intpos;DataTypex;prin

9、tf("请输入要插入的位置:");scanf("%d",&pos);printf("请输入要插入的数据:");scanf("%d",&x);ListInsert(h,pos,x);return1;}intListDelete(LinkListh,intpos,DataType*item)/*删除*/{PNodep=h,q;inti=0;while(p->next&&i