数据结构课程设计
《数据结构》课程设计报告
设计题目：____________________ 姓名：________________________
学号：________________________
专业：________________________
院系：________________________
班级：________________________
指导教师：______________________
年 月 日
数据结构课程设计
摘要
数据结构课程设计
英文摘要
数据结构课程设计
目
录
数据结构课程设计
一、问题描述（内容格式参考下面的描述，以下类似）
1． 题目内容：运用链表的操作来实现通讯录信息系统的管理。
2． 基本要求：系统含有多个菜单项的主控菜单程序，功能包括通讯录的建立，新纪录的插入，过期记录的删除，通讯者的查询，通讯录表的输出，通讯者人数的统计以及按通讯者编号排序等。
3． 要求从文件中读取通讯录。
二、需求分析
1． 本程序的功能包括单通讯录链表的建立，通讯录的插入，通讯者的删除，通讯者的查询，通讯录表的输出，通讯者人数的统计以及按通讯者编号排序等。
2． 程序运行后显现提示信息，等候用户输入0—7以进入相应的操作功能。 3． 用户输入数据完毕，程序将输出运行结束。
4． 测试数据应为通讯者的编号、姓名、性别、联系电话、地址。
三、概要设计
1． 带头结点的单链表抽象数据类型定义为：
ADT hlink_list{ 数据集合K：K={k1,k2,…,kn},n≥0，K中的元素是DataType类型； 数据关系R：R={r}
r={|i=1,2,…,n-1}。 操作集合：
(1)LinkList CreateList(void) 建立一个带头结点的通讯录单链表；
(2)void InserNode(LinkList head ,ListNode *p) 在带头结点的通讯录链表中插入结点； (3)ListNode *ListFind(LinkList head) 在带头结点的通讯录链表中查找结点； (4)void DelNode(LinkList head) 在带头结点的通讯录链表中删除结点；
(5)void PrintList(LinkList head) 输出带头结点的通讯录链表中各个结点的值；
(6)void Bubblesort(LinkList head) 将带头结点的通讯录链表中各个结点按通讯者编号排序。
}ADT hlink_list；
四、数据结构设计
1． 元素类型，结点类型，指针类型
typedef struct{
//通讯录结点类型
int num;
//编号
char name[9];
//姓名
char sex[3];
//性别
char phone[13];
//电话
char addr[31];
//地址 }DataType;
typedef struct node{
//结点类型定义
数据结构课程设计
DataType data;
//结点数据域
struct node *next;
//结点指针域 }ListNode; typedef ListNode *LinkList; LinkList head;
//定义指向单链表的头指针 ListNode *p;
//定义一个指向结点的指针变量 int n=0; int person[10];
五、算法设计
1、算法分析（必须要用语言进行描述）
2、算法实现
LinkList CreateList(void)
// { //尾插法建立带头结点的通讯录链表算法
LinkList head=new ListNode;
//申请头结点
ListNode *p,*rear; int flag=0;
//结束标志置0 rear=head; //尾指针初始指向头结点
while(flag==0) { p=(ListNode *)malloc(sizeof(ListNode));
//申请新结点
printf(\"编号 姓名(8) 性别(2) 电话(11) 地址(31)\\n\");
printf(\"-------\\n\"); scanf(\"%d%s%s%s%s\",&(p->data.num),p->data.name,p->data.sex,p->data.
phone,p->data.addr); n++;
rear->next=p;
//新结点连接到尾结点之后
rear=p;
//尾指针指向新结点
printf(\"结束建表吗？(1/0):\");
scanf(\"%d\",&flag);
//读入一个标志数据
}
rear->next=NULL;
//终端结点指针域置空
return head;
//返回链表头指针
}
3、算法流程图
六、程序测试与实现
1、函数之间的调用关系
数据结构课程设计
2、主程序
void main()
// {
}
3、测试数据
4、测试结果
七、调试分析
1．链表中的结点变量是通过指针变量来访问的。因为在C语言中是用P—>来表示P所指的变量，又由于结点类型是一个结构类型，因此可用P—> data和P—>next分别表示结点的数据域变量和指针域变量。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P 来访问结点，否则会引起程序错误。 2．算法的时空分析：
(1)对于本程序的通讯录单链表，其操作运算主要有建立单链表(尾插法)CreateList,查询(按编号和按姓名)ListFind,插入运算InsertNode,删除运算DelNode等。以上各操作运算的平均时间复杂度为O(n)，其主要时间是耗费在查找操作上。
(2)分析冒泡排序算法Bubblesort的时间和空间效率。冒泡排序的时间复杂度为O(n )。冒泡排序的过程中也只需要一个辅助空间，故空间复杂度为O(1)。
八、遇到的问题及解决办法
九、心得体会
