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