内容发布更新时间 : 2024/11/17 16:02:53星期一 下面是文章的全部内容请认真阅读。

《数据结构》实践任务书

学生姓名： 专业班级： 指导教师：

题 目: 基于链表的排序与查找 要求：

（1）熟练掌握基本的数据结构； （2）熟练掌握各种算法；

（3）运用高级语言编写质量高、风格好的应用程序。

主要任务:

1、系统应具备的功能： （1）建立链表

（2）基于链表的排序算法实现 （3）基于链表的查找算法实现 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现；

5、撰写数据结构实践报告，包括： （1）设计题目； （2）摘要和关键字；

（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现

及测试等； （4）结束语； （5）参考文献。

时间安排： 2014年-2015年 第1学期 第15周-第17周

15周 星期五 1-4节 系统设计，数据结构设计，算法设计 16周 星期四 5-8节 编程并上机调试 16周 星期五 1-4节 编程并上机调试

17周 星期四 5-8节 验收程序，提交数据结构实践报告书

指导教师签名： 2014年11月

1

基于链表的排序和查找算法的设计

与实现

摘要： 该程序的主要功能是对以链表为存储结构的数值型数据进行查

找和排序。排序和查找是链表中的一个重要应用。本文对输入的n个整数进行内部排序，使用交换排序来实现。在本程序中应用链式存储结构，对数据进行了基本的查找和排序。

关键字： 存储结构 链表 排序 排序。

1.引言

查找是求出一个数据元素在序列中的索引或指针，将其返回，本程序返回的为指针。

排序是将一个数据元素(或记录)的任意序列，重新排列成一按关键字(或排序码)有序的序列，以便于进行数据查询。

2.需求分析

本程序是基于链表的排序和查找，所以数据的存储结构为连式存储结构。文件中记录用节点来表示，其物理位置任意，节点之间用指针相连，链表结构的有点在于排序是无需移动记录，只需修改相应记录的指针即可。

排序本程序选用交换排序。

3.数据结构设计

2

3.1建立单链表

3.1.1 链表节点定义：

整形元素 data存储数据，节点指针 next指向下一个节点

typedef struct Cnode {

int data;

struct Cnode *next; }Cnode;

3.1.2 链表数据的存储:

函数insert（）在表尾插入数据：

void insert(Cnode *p,int e) { }

因为insert（）函数如代码所示只是在一个指针后面连接一个指针，想要完成一组数据的链式存储，在主函数中还有相应的存储代码：

int i,n,f,a[100];//={3,1,7,2,5,6,4}; Cnode *h= new Cnode;

Cnode *r,*p,*s;

Cnode *s=new Cnode; s->data=e;

s->next =NULL ;

p->next =s;

3