实验1单链表实验报告.doc

实验一 单链表 实验目的 掌握单链表中元素的前驱、后续的概念。 掌握单链表的建立、插入元素、删除表中某元素的算法。 3、对单链表相应算法的时间复杂度进行分析。 4、理解单链表数据结构的特点（优缺点）。 二、实验内容 说明以下概念 单链表：用一组任意的存储单元存储线性表的数据元素。以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素或数据元素的映象) 结点和单链表的 C 语言描述 typedef struc LNode{ // 定义单链表结点 ElemType data; struct LNode *next； // 指向后继的指针域 }LNode, *LinkList (*p)表示p所指向的结点 (*p).data(p-data表示p指向结点的数据域 (*p).next(p-next表示p指向结点的指针域 1、线性表的操作ListInsert(L, i, e) 在单链表中的实现： 有序对 ai-1, ai 改变为 ai-1, e 和e, ai 在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。 算法的时间复杂度为: O(ListLength(L)) 2、线性表的操作ListDelete (L, i, e) 在链表中的实现: 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。 有序对ai-1, ai 和 ai, ai+1 改变为 ai-1, ai+1 q = p-next; p-next = q-next; e = q-data; free(q); 算法的时间复杂度为: O(ListLength(L)) 单链表的优点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 插入、删除操作方便 4、单链表的缺点 指针占用额外存储空间 不能随机存取，查找速度慢 5、插入函数程序 int ListInsert(LinkList L,int i,ElemType e) { LNode *p,*s; int j; p=L; j=0; while(pji-1) { p=p-next;++j; } if(!p||ji-1) return ERROR; s=(LinkList) malloc ( sizeof(LNode) ); s-data=e; s-next=p-next; p-next=s; return OK; } 4、删除函数程序 int ListDelete(LinkList L,int i) { LNode *p,*q; int j; p=L; j=0; while(p-nextji-1){ p=p-next; ++j; } if(!(p-next)||ji-1) return ERROR; q=p-next;p-next=q-next; free(q); return OK;} 三、运行结果 指针域数据域 结点 ai-1 e ai-1 e e ai-1 e ai-1 ai-1 ai-1 e ai-1 ai-1 ai-1 e ai-1 ai-1 ai ai-1 ai ai+1 ai-1 p ai-1 ai ai+1 ai-1 p ai-1 ai ai+1 ai-1 p ai-1 ai ai+1 ai-1 p ai-1 p ai-1 ai ai+1 ai-1 ai-1 ai ai+1 ai-1 ai-1 ai ai+1 ai-1 ai-1 ai ai+1 ai-1 ai-1 q ai-1 ai ai+1 ai-1 ai-1 ai ai+1 ai-1 ai-1 ai ai+1 ai-1 ai-1 ai ai+1 ai-1 ai-1