--昆明理工大学信息工程与自动化学院学生实验报告（201—201学年第一学期）课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称线性表链式存储运算的算法实现指导教师教师评语教师签名：年月日一.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。二.实验目的：1.掌握线性表链式存储结构的C语言描述及运算算法的实现；2.分析算法的空间复杂度和插入和删除的时间复杂度；3.总结比较线性表顺序存储存储与链式存储的各自特点。三.主要程序代码分析：LinkListcreatListR1()//用尾插入法建立带头结点的单链表{char*ch=newchar();LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成头结点*headListNode*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));//生成新的结点*sstrcpy(s->data,ch);r->next=s;//新结点插入表尾r=s;//尾指针r指向新的表尾r->next=NULL;}scanf("%s",ch);//读入下一个结点的值}returnhead;//返回表头指针}intInsert(ListNode*head)//链表的插入{ListNode*in,*p,*q;intwh;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;wh>0;p=p->next,wh--);q=p->next;p->next=in;in->next=q;}voidDeleteList(LinkListhead,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}四.程序运行结果：五.实验总结：通过线性表链式存储运算的算法实现的上机实验，我了解了链式的基本原理和方法，能编程对数据进行链式存储。由于顺序储存是用物理位置上的邻接关系来表示结点间的逻辑关系，其插入或删除运算不方便，而且当表长变化较大时，难以确定合适的存储规模，为了解决这些问题，我们采用链接方式存储线性表。所以，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好；如果对于频繁进行插入删除的线性表，以采用链表做存储结构。链接存储是最常用的存储方法之一，它不仅可以表示线性表，还可以用来表示各种非线性的数据结构。