数据结构实验9：查找子系统

验证性实验9：查找子系统

班级学号BX100420 姓名施程程

1．实验目的

（1）通过查找实验理解查找的基本算法。

（2）熟悉各种查找方法的适用场合及平均查找长度。

（3）掌握静态查找和动态查找的区别。

（4）掌握顺序查找、二分查找的基本思想及其算法。

（5）掌握二叉排序树基本思想及其算法。

2．实验内容

（1）编写顺序查找程序。

（2）编写二分查找程序。

（3）编写建立二叉排序树的程序。

（4）编写在二叉排序树上的查找、插入、删除结点的程序。

（5）编写使二叉排序树中序输出的程序。

（6）设计一个选择式菜单，一级菜单形式如下：

查找子系统

******************************************

* 1------顺序查找*

* 2------二分查找*

* 3------二叉排序树*

* 0------返回*

******************************************

请选择菜单号(0--3)：

二叉排序树二级子菜单如下：

二叉排序树

*******************************************

* 1------更新二叉排序树*

* 2------查找结点*

* 3------插入结点*

* 4------删除结点*

* 5------中序输出排序树*

* 0------返回*

*******************************************

请选择菜单号(0--5)：

3．实验程序

#include

#include

#define SEARCHMAX 100

#define N 10

void SeqSearch()

{

int a[N],i,x,y;

char ch;

printf("\n\t\t建立一个整数的顺序表（以回车符为间隔，以-1结束）：

\n");

for(i=0;i

{

printf("\t\t");

scanf("%d",&a[i]);

getchar();

if(a[i]==-1)

{

y=i;break;

}

}

printf("\n\t\t需要查找请输入Y，否则输入N：");

scanf("%c",&ch);

while(ch=='y'||ch=='Y')

{

printf("\n\t\t请输入要查找的数据：");

scanf("%d",&x);getchar();

i=y-1;

while(i>=0&&a[i]!=x)

i--;

if(i==-1)

printf("\n\t\t抱歉！没有您要查找的数据。\n");

else

printf("\n\t\t您要查找的数据在第%d个位置上。\n",i+1);

printf("\n\t\t继续查找输入Y，否则输入N：");

scanf("%c",&ch);

}

}

void BinSearch()

{

int R[SEARCHMAX],i,k,low,mid,high,m,nn;

char ch;

printf("\n\t\t建立递增有序的查找顺序表（以回车符间隔，以-1结束）：\n");

for(i=0;i

{

printf("\t\t");

scanf("%d",&R[i]);

getchar();

if(R[i]==-1)

{

nn=i;break;

}

}

printf("\n\t\t查找请输入Y，退出输入N：");

scanf("%c",&ch);

getchar();

while(ch=='y'||ch=='Y')

{

printf("\n\t\t请输入要查找的数据：");

scanf("%d",&k);

getchar();

low=0;

high=nn-1;

m=0;

while(low<=high)

{

mid=(low+high)/2;

m++;

if(R[mid]>k)

high=mid-1;

else

if(R[mid]

low=mid+1;

else

break;

}

if(low>high)

{

printf("\n\t\t抱歉！没有您要查找的数据。\n");

printf("\n\t\t共进行%d次比较。\n",m);

if(R[mid]

mid++;

printf("\n\t\t可将此数据插入到第%d个位置上。\n",mid+1);

}

else

{

printf("\n\t\t要找的数据%d在第%d个位置上。\n",k,mid+1);

printf("\n\t\t共进行%d次比较。\n",m);

}

printf("\n\t\t继续查找输入Y，否则输入N：");

scanf("%c",&ch);getchar();

}

}

typedef int KeyType;

typedef struct node

{

KeyType key;

struct node *lchild,*rchild;

}BSTNode;

typedef BSTNode *BSTree;

BSTree CreateBST(void);

void SearchBST(BSTree T,KeyType key);

void InsBST(BSTree *Tptr,KeyType key);

void DelBSTNode(BSTree *Tptr,KeyType key);

void InorderBST(BSTree T);

void BTSearch()

{

BSTree T;

char ch1,ch2;

KeyType Key;

printf("\n\t\t建立一颗二叉树的二叉链表存储\n");

T=CreateBST();

ch1='y';

getchar();

while(ch1=='y'||ch1=='Y')

{

printf("\n");

printf("\n\t\t 二叉排序树");

printf("\n\t\t*********************************************");

printf("\n\t\t* 1------更新二叉排序树 *");

printf("\n\t\t* 2------查找结点*");

printf("\n\t\t* 3------插入结点*");

printf("\n\t\t* 4------删除结点*");

printf("\n\t\t* 5------中序输出排序树*");

printf("\n\t\t* 0------返回*");

printf("\n\t\t*********************************************");

printf("\n\t\t 请选择菜单号(0--5)：");

scanf("%c",&ch2);

getchar();

switch(ch2)

{

case '1':T=CreateBST();break;

case '2':printf("\n\t\t请输入要查找的数据：");

scanf("%d",&Key);

getchar();

SearchBST(T,Key);

printf("\n\t\t查找完毕。\n");break;

case '3':printf("\n\t\t请输入要插入的数据：");

scanf("%d",&Key);

getchar();

InsBST(&T,Key);

printf("\n\t\t插入完毕。\n");break;

case '4':printf("\n\t\t请输入要删除的数据：");

scanf("%d",&Key);

getchar();

DelBSTNode(&T,Key);

printf("\n\t\t删除完毕。\n");break;

case '5':printf("\n\t\t");

InorderBST(T);

printf("\n\n\t\t二叉排序树输出完毕。\n");break;

case '0':ch1='n';

return;

default:printf("\n\t\t输出错误！请重新输入。\n");

}

}

}

BSTree CreateBST(void)

{

BSTree T;

KeyType Key;

T=NULL;

printf("\n\t\t请输入一个整数关键字（输入0时结束输入）：");

scanf("%d",&Key);

while(Key)

{

InsBST(&T,Key);

printf("\n\t\t请输入下一个整数关键字（输入0时结束输入）：");

scanf("%d",&Key);

}

return T;

}

void SearchBST(BSTree T,KeyType Key)

{

BSTNode *p=T;

while(p)

{

if(p->key==Key)

{

printf("\n\t\t已经找到您输入的数据。\n");

return;

}

p=(Keykey)?p->lchild:p->rchild;

}

printf("\n\t\t没有找到您输入的数据。\n");

}

void InsBST(BSTree *T,KeyType Key)

{

BSTNode *f,*p;

p=(*T);

while(p)

{

if(p->key==Key)

{

printf("\n\t\t树中已有%d，不需插入。\n",Key);

return;

}

f=p;

p=(Keykey)?p->lchild:p->rchild;

}

p=new BSTNode;

p->key=Key;

p->lchild=p->rchild=NULL;

if((*T)==NULL)

(*T)=p;

else

if(Keykey)

f->lchild=p;

else

f->rchild=p;

}

void DelBSTNode(BSTree *T,KeyType Key)

BSTNode *parent=NULL,*p,*q,*child;

p=*T;

while(p)

{

if(p->key==Key)

break;

parent=p;

p=(Keykey)?p->lchild:p->rchild;

}

if(!p)

{

printf("\n\t\t没有找到您要删除的结点。");

return;

}

q=p;

if(q->lchild&&q->rchild)

for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);

child=(p->lchild)?p->lchild:p->rchild;

if(!parent)

*T=child;

else

{

if(p==parent->lchild)

parent->lchild=child;

else

parent->rchild=child;

if(p!=q)

q->key=p->key;

}

delete(p);

}

void InorderBST(BSTree T)

{

if(T!=NULL)

{

InorderBST(T->lchild);

printf("\t%d",T->key);

InorderBST(T->rchild);

}

}

void main()

{

int choice;

char ch;

ch='y';

while(ch=='y'||ch=='Y')

{

printf("\n");

printf("\n\t\t 查找子系统");

printf("\n\t\t********************************************");

printf("\n\t\t* 1------顺序查找*");

printf("\n\t\t* 2------二分查找*");

printf("\n\t\t* 3------二叉排序树 *");

printf("\n\t\t* 0------返回*");

printf("\n\t\t********************************************");

printf("\n\t\t请选择菜单号(0--3)：");

scanf("%d",&choice);

switch(choice)

{

case 1:SeqSearch();break;

case 2:BinSearch();break;

case 3:BTSearch();break;

case 0:ch='n';break;

default:printf("\n\t\t菜单选择错误！请重新输入。");

}

}

}

4．程序运行

5．实验小结

本章主要要求我们掌握的是查找的运用，即查找的方法及怎样求其平均查找长度；还有就是哈希表的运用以及处理冲突的方法。

这个实验要求我们设计的算法要求有二份查找程序，建立二叉排序树程序，以及在二叉排序树上的的查找、插入、删除节点和中序输出的程序。书上给了我们参考程序，但是我觉得书上给的程序在开头缺了#include这一句话，从而导致在编译过程中出现问题。不过，我能运用以前所学过的知识把它改正，这说明我学的还是不错的，也表明不是白学的，也是有用的，能学以致用是最好的。

因此，本次实验是成功的。

数据结构课程实验指导书

数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出

现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的

数据结构实验七 查找

实验七查找 一、实验目的 1. 掌握查找的不同方法，并能用高级语言实现查找算法； 2. 熟练掌握二叉排序树的构造和查找方法。 3. 熟练掌握静态查找表及哈希表查找方法。 二、实验内容 设计一个读入一串整数，然后构造二叉排序树，进行查找。 三、实验步骤 1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。 2. 在二叉排序树中查找某一结点。 3.用其它查找算法进行排序（课后自己做）。 四、实现提示 1. 定义结构 typedef struct node { int key; int other; struct node *lchild, *rchild; } bstnode; void inorder ( t ) { if (t!=Null) { inorder(t→lchild); printf(“%4d”, t→key); inorder(t→rchild); } } bstnode *insertbst(t, s) bstnode *s, *t; { bstnode *f, *p; p=t;

while(p!=Null) { f=p; if (s→key= =p→key) return t; if (s→key

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构实验报告代码

线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) {

数据结构实验7实验报告

暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.51 指导教师孙世良 实验项目编号实验7 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 (二)实验内容和要求 编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则应该在输出时添上。 (三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序 #include #include typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void create(bitree &T){ char t; t=getchar();

if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } void middle_order(bitree &Node){ if(Node != NULL){ if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf("( "); middle_order(Node->lchild); if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf(") "); printf("%c ", Node->data); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf("( "); middle_order(Node->rchild); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf(") "); } } int main() { bitree y; printf("以先序遍历的方式输入二叉树："); create(y); printf("输出表达式："); middle_order(y); return 0; } (五)数据调试

数据结构实验一的源代码

#include #include typedef struct Node { int key;//密码 int num;//编号 struct Node *next;//指向下一个节点 } Node, *Link; void InitList(Link &L) //创建一个空的链表{ L = (Node *)malloc(sizeof(Node)); if (!L) exit(1); L->key = 0; L->num = 0; L->next = L; } void Creatlinklist(int n, Link &L) //初始化链表{ Link p, q; q = L; for (int i = 1; i <= n; i++) { p = (Node *)malloc(sizeof(Node)); if (!p) exit(1); scanf("%d", &p->key); p->num = i; L->next = p; L = p; } L->next = q->next; free(q); } Link Locate_m(Link &p, int m)//找到第m个 { Link q; for (int j = 1; jnext; q = p->next; m = q->key;

return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码：\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); }

数据结构实验报告七查找、

云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日

云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include

数据结构实验八内部排序

实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include #include #define MAX 50 int slist[MAX]; /*待排序序列*/ void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n); void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n); /*直接插入排序*/ void insertSort(int list[], int n) { int i = 0, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序：\n"); printf("初始序列为：\n"); printList(list, n); for(i = 1; i < n; i++) { node = list[i]; j = i - 1; while(j >= 0 && node < list[j]) { list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果：\n", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v)

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验程序

顺序表的基本操作 #include using namespace std; typedef int datatype; #define maxsize 1024 #define NULL -1 typedef struct { datatype *data; int last; }sequenlist; void SETNULL(sequenlist &L) { L.data=new datatype[maxsize]; for(int i=0;i>https://www.wendangku.net/doc/5e8747890.html,st; cout<<"请输入"<>L.data[i]; } int LENGTH(sequenlist &L) { int i=0; while(L.data[i]!=NULL) i++; return i; } datatype GET(sequenlist &L,int i) { if(i<1||i>https://www.wendangku.net/doc/5e8747890.html,st) { cout<<"error1"<

int j=0; while(L.data[j]!=x) j++; if(j==https://www.wendangku.net/doc/5e8747890.html,st) { cout<<"所查找值不存在！"<=maxsize-1) { cout<<"overflow"; return NULL; } else if(i<1||(i>https://www.wendangku.net/doc/5e8747890.html,st)) { cout<<"error2"<=i-1;j--) L.data[j+1]=L.data[j]; L.data[i-1]=x; https://www.wendangku.net/doc/5e8747890.html,st++; } return 1; } int DELETE(sequenlist &L,int i) { int j; if((i<1)||(i>https://www.wendangku.net/doc/5e8747890.html,st+1)) { cout<<"error3"<

数据结构实验七图的创建与遍历

实验七图的创建与遍历 实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。 实验内容与要求： 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计： #include #include #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }Graph; //队列类 class Queue{ public: void InitQueue() { base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0;

. } void EnQueue(int e) { base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e) { e=base[front]; front=(front+1)%QUEUE_SIZE; } public: int *base; int front; int rear; }; //图G中查找元素c的位置 int Locate(Graph G,char c) { for(int i=0;i

数据结构实验报告[3]

云南大学 数据结构实验报告 第三次实验 学号： 姓名： 一、实验目的 1、复习结构体、指针； 2、掌握链表的创建、遍历等操作； 3、了解函数指针。 二、实验内容 1、（必做题）每个学生的成绩信息包括：学号、语文、数学、英语、总分、加权平均分；采用链表存储若干学生的成绩信息；输入学生的学号、语文、数学、英语成绩；计算学生的总分和加权平均分（语文占30%，数学占50%，英语占20%）；输出学生的成绩信息。 三、算法描述 （采用自然语言描述） 首先创建链表存储n个学生的成绩信息，再通过键盘输入学生的信息，创建指针p所指结点存储学生的成绩信息，从键盘读入学生人数，求出学生的总分和加权平均分，输出结果。 四、详细设计 （画出程序流程图）

五、程序代码 （给出必要注释） #include #include typedef struct score {int number; int chinese; int math; int english; int total; float average; struct score *next; } student; //创建链表存储n个学生的信息，通过键盘输入信息student*input_score(int n) {int i; student*stu,*p; for(i=0,stu=NULL;inumber);

《数据结构实验》实验题目及实验报告模板

《数据结构实验》的实验题目及实验报告模板 实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #include #include #include //定义客房链表结点结构 typedef struct HNode { char roomN[7]; //客房名称 float Price; //标准价格 float PriceL; //入住价格(默认值=标准价格*80%) int Beds; //床位数Beds char State[5]; //入住状态(值域："空闲"、"入住"、"预订"，默认值为"空闲") struct HNode *next; //指针域 }Hotel, *HLink; (1)实现创建客房信息链表函数void Build(HLink &H)，输入（客房名称、标准价格、床位数），同时修改入住价格、入住状态为默认值，即入住价格=标准价格*80%，入住状态为”空闲”（提示：用strcpy()字符串拷贝函数）。为了提高程序调试效率，要求：用文件操作来输入客房信息（客房名称、标准价格、床位数）； (2)实现输出客房信息函数void Exp(HLink H)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态； (3)函数int Find(HLink &H, char *roomN)，查找房间名称为roomN的客房。如果找到，则返回该客房在链表中的位置序号（>=1），否则返回0。提示：用strcmp()字符串比较函数； (4)实现函数void updateH(HLink &H, int beds, char *state)，将床位数为beds的客房入住状态改为state。提示：用strcpy()字符串拷贝函数； (5)函数void Add(HLink &H)，将该链表中未入住的客房入住价格均加价20%； (6)求出入住价格最高的客房函数HLink FirstH(HLink &H)，该函数内return语句返回入住价格最高的客房结点指针，返回前将该结点在链表中删除； (7)函数void MoveK1(HLink &H, int k)，将单链表中倒数第k个结点移到第一个结点位置，注意：严禁采用先计算链表长度n再减k（即n-k）的方法；

数据结构上机实验线性表单链表源代码

#include template class LinearList { public: virtual bool IsEmpty()const=0; virtual int Length()const=0; virtual bool Find(int i,T& x)const=0; virtual int Search(T x)const=0; virtual bool Insert(int i,T x)=0; virtual bool Update(int i,T x)=0; virtual bool Delete(int i)=0; virtual void Output(ostream& out)const=0; protected: int n; }; #include "linearlist" template class SeqList:public LinearLisr { public: SeqList(int mSize); ~SeqList(){delete [] elements;} bool IsEmpty()const; bool Find(int i,T& x)const; int Length()const; int Search(T x)const; bool Insert(int i,T x); bool Update(int i,T x); bool Delete(int i); void Output(ostream& out)const; private: int maxLength; T *elements; }; template SeqList::SeqList(int mSize) { maxLength=mSize;

数据结构实验七

(*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++){ (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++){ YLX_select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight ; } } void YLX_outputHuffman(HuffmanTree HT, int m){ if(m!=0){ YLX_outputHuffman(HT,HT[m].LChild); if(!HT[m].LChild&&!HT[m].RChild)printf("%c \t", HT[m].data); YLX_outputHuffman(HT,HT[m].RChild); } } void YLX_CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n){ char *cd; int i; unsigned int c; int start; int p; hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); cd=(char * )malloc(n * sizeof(char )); cd[n-1]='\0'; for(i=1;i<=n;i++){ start=n-1; for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) if( (*ht)[p].LChild == c) cd[--start]='0'; else cd[--start]='1'; hc[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(hc[i],&cd[start]); } free(cd); for(i=1;i<=n;i++) printf("%c编码为%s\n",(*ht)[i].data,hc[i]); } void main() { HuffmanTree HT; HuffmanCode HC; int n; int m; printf("*******袁丽湘*******"); printf("\n"); printf("输入叶子节点的个数:" ); scanf("%d",&n); YLX_CrtHuffmanTree(&HT,n); m=2*n-1;printf("中序输出哈夫曼树叶子节点：\n"); YLX_outputHuffman(HT,m); printf("\n"); YLX_CrtHuffmanCode(&HT,&HC,n); } 六、运行结果截图

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验(七种排序算法的实现)题目和源程序

1、直接插入排序 2、希尔排序 3、2-路归并排序 4、折半插入排序 5、冒泡排序 6、快速排序 7、堆排序 /*---------------------------------------- * 07_排序.cpp -- 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘2011年写 ----------------------------------------*/ // ds07.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "stdio.h" #include #include using namespace std; #define MAXSIZE 20 typedefintKeyType; typedefstruct{ KeyType key; //关键字项 KeyType data; //数据项 }RedType; //记录类型 typedefstruct{ RedTypearr[MAXSIZE+1]; //arr[0]闲置或用作哨兵单元int length; //顺序表长度 }SqList; //顺序表类型typedefSqListHeapType; //对顺序表L做一趟希尔插入排序 //前后记录位置的增量是dk //r[0]只是暂存单元 //当j<=0时，插入位置已找到 voidshellInsert(SqList&L, intdk) {

int i, j; for (i = dk + 1; i <= L.length; i++) { if (L.arr[i].key 0 &&L.arr[0].key = high + 1; j--) L.arr[j + 1] = L.arr[j];//记录后移 L.arr[high + 1] = L.arr[0];//插入 }//for }//BInsertSort //直接插入排序