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

1、昆明理工大学信息工程与自动化学院学生实验报告(201课程名称：数据结构201学年第一开课实验室：学期)年月日年级、专业、班学号姓名成绩实验项目名称线性表链式存储运算的算法实现指导教师教师评教师签名：语年月日.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、 链表的数据输出。二.实验目的：1. 掌握线性表链式存储结构的C语言描述及运算算法的实现;2. 分析算法的空间复杂度和插入和删除的时间复杂度；3. 总结比较线性表顺序存储存储与链式存储的各自特点。三.主要程序代码分析：Lin kList creatListR1()/用尾插入法建立带头结点的单链表char

2、 *ch=new char();LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点 *headListNode *s,*r,*pp;r=head;/尾指针初值指向头结点r-n ext=NULL;scan f(%s,ch);/读入第一个结点的值while(strcmp(ch,#)!=O) /输入#结束pp=LocateNode(head,ch);if(pp=NULL) s=(ListNode *)malloc(sizeof(ListNode); /生成新的结点 *sstrcpy(s-data,ch);r-n ext=s;/r=s;/r-

3、n ext=NULL;sca nf(%s,ch);/return head;/新结点插入表尾尾指针r指向新的表尾读入下一个结点的值返回表头指针int In sert(ListNode *head)/ListNode *in ,*p,*q;链表的插入int wh;in=(ListNode *)malloc(sizeof(ListNode);i n- next=NULL; p=(ListNode *)malloc(sizeof(ListNode);p- next=NULL;/生成新结点q=(ListNode *)malloc(sizeof(ListNode);q- next=NULL;sca nf

4、(%s,i n-data);sca nf(%d,&wh);/for(p=head;wh0;p=p-n ext,wh-); q=p-n ext;p-n ext=in;in-n ext=q;/输入插入的数据输入插入数据的位置void DeleteList(L in kList head,char *key)ListNode *p,*r,*q=head; p=LocateNode(head,key);/if(p=NULL)exit(0);/while(q-n ext!=p)/pq=q-n ext;r=q-n ext;q-n ext=r- n ext;free(r);/链表的删除按key值查找结点的若

5、没有找到结点，退出 为要删除的结点，q为p的前结点释放结点*r四.程序运行结果:欢迎下载4LJ_g圭冃主冃主冃主冃圭冃主冃a b c Ju ea b cd eR J s *月居居居居居居入入入入入入入青输入要删除的敎据,bbhCCC J.dddreee r G：逐局护5 实卸 Debuglinkli5t. exen请输入插入的数据；XXX:青输入你数据插入的位置,XXX,ddd.eee五.实验总结：通过线性表链式存储运算的算法实现的上机实验，我了解了链式的基本原理和方法, 能编程对数据进行链式存储。由于顺序储存是用物理位置上的邻接关系来表示结点间的逻 辑关系，其插入或删除运算不方便，而且当表长变化较大时，难以确定合适的存储规模， 为了解决这些问题，我们采用链接方式存储线性表。所以，当线性表的长度变化较大，难 以估计其存储规模时，以采用动态链表作