数据结构-实验2-单链表的基本运算.doc

上海应用技术学院数据结构课程实验报告实验名称单链表的基本运算实验序号2实验日期2012-4-8姓 名曹志华院系计算机科学与信息工程学院班 级101041C1学 号1010411501专 业计算机科学与技术指导教师武伟成 绩教师评语一、实验目的和要求1. 了解单链表基本运算的实现；2. 进一步掌握链表使用的步骤；3. 牢固掌握建立单链表算法，特别是尾插法建表算法，是很多其他复杂复杂的基础；二、实验项目摘要编写一个程序algo2-2.cpp.实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：1. 初始化顺序表h；2. 依次采用尾插法插入a,b,c,d,e元素；3. 输出单链表h；4. 输出单链表h长度；5. 判断单链表h是否为空；6. 输出单链表h的第3个元素；7. 输出元素a 的位置；8. 在第4个元素位置上插入“f”元素；9. 输出单链表h;10. 删除单链表h的第3个元素；11. 输出单链表h；12. 释放单链表h。三、实验预习内容单链表基本运算的实现：单链表中，每一个结点有一个指针域指向直接后继。l 插入结点运算l 删除结点运算l 建立单链表l 线性表基本运算的实现1. 初始化线性表2. 求线性表的长度3. 判断该线性表是否为空4. 销毁线性表5. 求线性表中某个数据元素值6. 按元素查找7. 插入数据元素8. 删除数据元素9. 输出线性表三、实验结果与分析 1. 实验结果：2. 实验分析：这次实验与上次的顺序表很相似，但相比之下，单链表比较难一些，通过这次实验我明白了什么是线性表的链式存储结构，在编写程序时出现了很多错误，但通过看书，查找资料慢慢改进，在改进中也学会了很多，比如了解了单链表基本运算算法的基本格式和构成。虽然有很多不足，但在今后的实验中我会慢慢改进。3. 源程序 #include #include/#define maxsize 1024typedef char ElemType;typedef struct nodeElemType data;struct node *next;LinkList; /初始化线性表void InitList (LinkList *&h)h=(LinkList *)malloc(sizeof(LinkList);h-next=NULL;/求线性表的长度 int ListLength(LinkList *h) int i=0;LinkList *p=h-next;while(p!=NULL)i+;p=p-next;return i;/求出线性表中第i个元素int GetElem(LinkList *h,int i,ElemType &e) int j=0;LinkList *p=h-next;if(iListLength(h)return (0);while(jnext;j+;e=p-data;return (1);/判断单链表是否为空 int ListEmpty (LinkList *h) return(h-next=NULL); /输出元素的位置（按元素值查找） int LocateElem(LinkList *h,ElemType e) LinkList *p=h-next; int i=1; while(p!=NULL & p-data!=e) p=p-next; i+; if(p=NULL) return(0); else return(i); /插入数据元素 int ListInsert(LinkList *&h,int i,ElemType e) int j=0; LinkList *p=h,*s; while(jnext; if(p=NULL) return 0; else s=(LinkList *)malloc(sizeof(LinkList); s-data=e; s-next=p-next; p-next=s; return 1; /删除数据元素 int ListDelete (LinkList *&h,int i,ElemType &e) int j=0; LinkList *p=h,*q ; while(jnext; if(p=NULL) return 0; else q=p-next; if(q=NULL) return 0; e=q-data; p-next=q-next; free(q); return 1; /销毁线性表 int DestroyList(LinkList *&h) LinkList *p=h,*q=p-next; while(q!=NULL) free(p); p=q; q=p-next; free(p); /输出线性表int DispList (LinkList *h)LinkList *p=h-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n); /主函数 void main()int i;ElemType e;LinkList *h;InitList(h); /初始化单链表h printf(1.初始化顺序表n); printf(n); printf(2.采用尾插法插入a,b,c,d,e元素n) ;ListInsert(h,1,a); /插入元素 ListInsert(h,2,b); ListInsert(h,3,c); ListInsert(h,4,d); ListInsert(h,5,e); printf(n);printf(3.输出单链表h：); DispList(h);printf(n); printf(4.长度:%dn,ListLength(h); printf(n); printf(5.单链表h为%sn,(ListEmpty(h)?空:非空); printf(n); GetElem(h,3,e); printf(6.单链表h的第3个元素是%cn,e); printf(n); printf(7.元素a的位置是第%d个元素n,LocateElem(h,a); printf(n); printf(8.在第4个元素位置上插入f元素n); ListInsert(h,4,f); printf(n); printf(9.输出单链表h:); DispList(h); printf(n); printf(10.删除h的第3个元素n); ListDelete(h,