数据结构实验报告 实验一 线性表链式存储运算的算法实现

-昆明理工大学信息工程与自动化学院学生实验报告（ 201 201 学年 第 一 学期 ）课程名称：数据结构 开课实验室： 年 月 日年级、专业、班 学号 姓名 成绩实验项目名称线性表链式存储运算的算法实现指导教师 教师评语 教师签名： 年 月 日一.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。二.实验目的：1.掌握线性表链式存储结构的C语言描述及运算算法的实现；2.分析算法的空间复杂度和插入和删除的时间复杂度；3.总结比较线性表顺序存储存储与链式存储的各自特点。三.主要程序代码分析： LinkList creatListR1() /用尾插入法建立带头结点的单链表 char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点*head ListNode *s,*r,*pp; r=head; /尾指针初值指向头结点 r-next=NULL; scanf(%s,ch); /读入第一个结点的值 while(strcmp(ch,#)!=0) /输入#结束 pp=LocateNode(head,ch); if(pp=NULL) s=(ListNode *)malloc(sizeof(ListNode); /生成新的结点*s strcpy(s-data,ch); r-next=s; /新结点插入表尾 r=s; /尾指针r指向新的表尾 r-next=NULL; scanf(%s,ch); /读入下一个结点的值 return head; /返回表头指针int Insert(ListNode *head) /链表的插入 ListNode *in,*p,*q;int wh;in=(ListNode *)malloc(sizeof(ListNode);in-next=NULL;/生成新结点p=(ListNode *)malloc(sizeof(ListNode);p-next=NULL;q=(ListNode *)malloc(sizeof(ListNode);q-next=NULL;scanf(%s,in-data); /输入插入的数据scanf(%d,&wh); /输入插入数据的位置for(p=head;wh0;p=p-next,wh-);q=p-next;p-next=in;in-next=q;void DeleteList(LinkList head,char *key) /链表的删除 ListNode *p,*r,*q=head; p=LocateNode(head,key); /按key值查找结点的 if(p=NULL) exit(0); /若没有找到结点，退出 while(q-next!=p) /p为要删除的结点，q为p的前结点q=q-next;r=q-next;q-next=r-next;free(r); /释放结点*r四.程序运行结果：五.实验总结：通过线性表链式存储运算的算法实现的上机实验，我了解了链式的基本原理和方法，能编程对数据进行链式存储。由于顺序储存是用物理位置上的邻接关系来表示结点间的逻辑关系，其插入或删除运算不方便，而且当表长变化较大时，难以确定合适的存储规模，为了解决这些问题，我们采用链接方式存储线性表。所以，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好；如果