数据结构课程设计

仲恺农业工程学院。

课程设计报告。

课程名称：数据结构

院（系）：

专业：班级：

学号：姓名。

指导老师。2题设线性表存于a[1..size]的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性。

一、数据结构说明。

1、线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置loc(ai+1)和第i个数据元素的存储位置loc(ai)之间满足下列关系：

loc(ai+1)=loc(ai)+l

一般来说，线性表的第i个数据元素ai的存储位置为。

loc(ai) =loc(a1)+(i-1) *l

式中loc(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。

线性表的这种机内表示称做线性表的顺序存储结构或顺序映象(sequential mapping)，反之，称这种存储结构的线性表为顺序表。

它的特点是，为表中相邻的元素ai和ai+1赋以相邻的存储位置loc(ai)和loc(ai+1)。换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。

2、顺序表存储结构：用一段地址连续的存储单元依次存储线性表中的数据元素。

图1 顺序表存续结构示意图。

二、顺序表的存储结构设计。

typedef struct

elemtype *data;//存储空间基址。

int length;//当前长度。

int size;//当前分配的存储容量(以sizeof(elemtype))为单位。

sqlist;

三、算法设计（程序流程图）

图2 顺序表课程设计流程图。

四、详细设计。

#include <>

#include <>exit()

#include <>

#define list_init_size 100/*线性表存储空间的初始分配量*/

#define listincrement 2/*线性表存储空间的分配增量*/

typedef int elemtype;

typedef struct

elemtype *data;//存储空间基址。

int length;//当前长度。

int size;//当前分配的存储容量(以sizeof(elemtype))为单位。

sqlist;

*函数结果状态***/

#define true 1

#define false 0

#define ok 1

#define error 0

#define infeasible -1

#define overflow -2/*因为在中已定义overflow的值为3,故去掉此行*/

typedef int status;/*status是函数的类型，其值是函数结果状态**，如ok等*/

typedef int boolean;/*boolean是布尔类型，其值是true或false*/

status initlist(sqlist &l)

/*操作结果：构造一个空的顺序线性表*/

if(! exit(overflow);/存储分配失败*/

空表长度为0*/

初始存储容量*/

return ok;

status insertorderlist(sqlist &l,elemtype x)

//顺序表l中的元素依值递增有序，本算法将x插入其中适当位置。

//以保持其有序性。入口断言：0<=<

int i,j;

if( return (overflow);

else status listtr**erse(sqlist l)

/*初始条件：顺序线性表l已存在*/

/*操作结果：依次对l的每个数据元素访问并输出*/

elemtype *p;

int i;

p=for(i=1;i<=

printf("%d ",p++)

printf("");

return ok;

void main()

sqlist l1;

elemtype e1,e2;

int i,n;

printf("顺序表第2题");

initlist(l1);/初始化顺序表。

printf("给顺序表长度赋值 n=")

scanf("%d",&n);/通过键盘输入为顺序表长度赋值。

printf("输入元素：");

for(i=1;i<=n;i++)

printf("有序递增顺序表为：")

listtr**erse(l1);/依次对l的每个数据元素访问并输出。

printf("输入一个元素并把它插入表中");

scanf("%d",&e2);

insertorderlist(l1,e2);/调用insertorderlist函数，在有序递增顺序表l中有序插入新的数据元素e2

printf("新有序递增顺序表为：")

listtr**erse(l1);/依次对l的每个数据元素访问并输出。

五、调试分析。

1、调试结果。

图3 顺序表课程设计调试结果。

2、时间复杂度。

status insertorderlist(sqlist &l,elemtype x)函数的时间复杂度为o(n)。

3、程序存在问题和解决办法。

在调试程序的时候发现自己编程序的时候考虑不周，忽略了顺序表的最大容量的问题，程序运行的结果跟预想的结果不吻合。解决办法是在编写程序的时候要把顺序表的最大容量这个问题考虑进去。

5题试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。

一、数据结构说明。

1、线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。因此，为了表示每个数据元素 ai 与其直接后继数据元素ai+1 ，之间的逻辑关系，对数据元素ai 来说，除了存储其本身的信息之外，还需存储—个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai 的存储映象，称为结点(node)。

它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。

n个结点( ai（1≤i≤n)的存储映象)链结成一个链表，即为线性表。

a1 ， a2 ，…an )

的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

2、链表存储结构：用一组任意的存储单元存放线性表的元素。

p结点（*p）

图4 链表存储结构示意图。

二、链表的存储结构设计。

struct lnode;

typedef struct lnode *ptrtonode;

typedef ptrtonode list;

typedef ptrtonode position;

typedef struct lnode

elemtype data;//数据域。

struct lnode *next;//指针域。

*linklist;

linklist l;//l为单链表的头指针。

三、算法设计（程序流程图）

图5 链表课程设计流程图。

四、详细设计。

#include <>eof(=^z或f6),null*/

#include <>exit()*

#include <>

typedef int elemtype;

*函数结果状态***/

#define true 1

#define false 0

#define ok 1

#define error 0

#define infeasible -1

#define overflow -2 因为在中已定义overflow的值为3,故去掉此行 */

typedef int status; /status是函数的类型，其值是函数结果状态**，如ok等*/

typedef int boolean;/*boolean是布尔类型，其值是true或false*/

struct lnode;

typedef struct lnode *ptrtonode;

typedef ptrtonode list;

typedef ptrtonode position;

typedef struct lnode

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了