数据结构报告实验报告

1、院 系： 计算机科学学院 专 业： 计科 年 级： 2013 课程名称： 数据结构 学 号： 201321091135 姓 名： 司少武 指导教师： 刘晶 2016年 6月12日实验一 线性结构的基本操作和应用实验目的及要求一、实验目的：1、掌握线性表的结构特点和实现方法，能够编写程序实现线性表的基本操作：初始化，插入，删除，查找，判空，求线性表长度等运算。2、能够掌握特殊线性表（栈和队列）的结构特点及其基本操作；3、能利用栈的特性进行实际应用。二、实验题目及要求：线性结构部分共包含三个实验内容：1、 用顺序表或者链表实现线性表的基本操作：初始化，插入，删除，查找，判空，求线性表长度。2、 线

2、性表的基本应用：从以下两个实验题目中任选一个实现：1） 利用线性表实现一元多项式的相加。2） 利用线性表实现约瑟夫环问题。3、 利用栈的基本操作，编写程序实现括号匹配问题：从键盘输入一组括号，当程序接收第一个左括号之后，期待与之匹配的右括号，如果等到的是另外一组括号的左一半则等待，若等到另外一个不匹配的右括号则程序结束并提示括号不匹配；若整个括号序列判断完毕，但栈未空则表示仍有括号未配对，提示不匹配。否则提示匹配。三、实验报告书写要求： 简明清晰的写出每个实验题目的算法步骤，可以混合使用自然语言、流程图及伪代码的方式，不能直接复制源程序。每个实验题目需要附上程序正确运行结果的截图。题目一 线性

3、表的基本操作算法步骤的简要说明（流程图或伪代码）题目：用顺序表或者链表实现线性表的基本操作：初始化，插入，删除，查找，判空，求线性表长度。1. 算法思想：主要设计了一个包含数据和指针域的结点。 Data *next 主要思想：插入： 删除： 1. 主函数int main() :初始化一个链表L，显示菜单，主要语句：switch语句，while语句，goto语句。2. 创建并输入链表数据linklist createlist（），在该函数中创建头结点，并输入结点上的数据。伪代码：while（当x!=00）p = new list;p->data = x;p->next = NULL;

4、 q->next = p;q = p;3. 显示链表数据void show（linklist L）1） 先判断是否是空表，再逐个寻找想要的元素。2） 主要代码：while(p)cout<<p->data<<"t"p = p->next;4. 获取链表长度int getlength(linklist L)1) 先判断是否为空，再遍历链表，算出链表长度。2) 主要代码：while(p)p = p->next;length+;5. 获取第i个元素int getdata(linklist L,int i)1）当0<i<le

5、ngth时，遍历链表，找到第i个元素。2）主要代码：while(p&&j<i)j+;p = p->next;6. 改变链表数据int changedata(linklist L,int e,int d)1） 找到要修改的值e，再把d赋值给e.2)主要代码：while(p&&p->data!=e)p = p->next;if(!p)return ERROR;p->data = d;7. 插入一个结点linklist insertlist(linklist L,int i,int e)1)因为要插入第i个元素，所以要先找到第i-1个元素

6、，在i-1后面插入。2）主要代码：s->data = e;s->next = p->next ;p->next = s;8. 删除一个结点linklist deletelist(linklist L,int i)1）同插入差不多，先找到第i-1个元素，然后再把i-1结点指针域指向原本指向结点的下一个，把中间那个删除，再free，释放空间，主要代码：q = p->next;p->next =q->next;free(q);实验截图：心得体会:源代码：/*线性表的操作（单链表）*/#include<stdio.h>#include<std

7、lib.h>typedef struct LNodeint data; struct LNode *next;  LNode, *Linklist;/*线性表的结构*/ /*基本操作函数*/*构造空线性表。操作结果：构造空线性表，如成功返回1，否则返回0。*/int InitList(Linklist L) L=(Linklist)malloc(sizeof(LNode);  if(L)   L->next=NULL; return 1;  else return 0;/*顺序创建一个线性链表函数。当输入的结点的数据值为0

8、时，线性链表创建结束。返回线性表的头结点指针。*/Linklist hrear_create() int x; Linklist head, p, rear; head=(Linklist)malloc(sizeof(LNode); head->data=0; rear=head; printf("请输入线性表中的元素值，以0结束输入:n"); scanf("%d",&x); while(x!=0) p=(Linklist)malloc(sizeof(LNode); p->data=x; rear->next=p; rear=p

9、; scanf("%d",&x);rear->next=NULL;return head;/*判断链表是否为空。初始条件：线性表存在。操作结果：若线性表为空，返回1，否则返回0。*/int ListEmpty(Linklist L) if(L->next=NULL)return 1; else return 0; /*求线性链表的长度函数。初始条件：线性表存在。操作结果：返回线性表中数据元素的个数。*/int Listlength(Linklist L) Linklist p; int count=0; p=L; while(p->next!=NU

10、LL) p=p->next; count+; return count;/*确定元素e的位置。初始条件：线性表存在。操作结果：返回第一个与e相同的元素的位置；如果这样的元素不存在，则返回0。*/int LocateElem(Linklist L,int e) Linklist p; int pos=1; p=L->next; while(p!=NULL) if(p->data!=e) p=p->next; pos+; else return pos; return 0;/*在第i个元素前插入元素。初始条件：线性表存在，且1<=i<=ListLength(L)

11、+1*。操作结果：在L中第i个位置之前插入新的元素e，插入成功返回1，否则返回0。*/int ListInsert(Linklist L, int i, int e) Linklist p,findpri;/*p用于申请空间，findpri用于找第i个节点的前驱*/ int j; if(1<=i)&&(i<=Listlength(L)+1)/*判断i是否合法*/ p=(Linklist)malloc(sizeof(LNode); if(!p) return 0;/*判断申请空间是否成功*/ else p->data=e; findpri=L; for(j=1;

12、j<i;j+) findpri=findpri->next; p->next=findpri->next; findpri->next=p; return 1; else return 0;/*删除第i个结点，并将其数据元素作为返回值返回。初始条件：线性表非空且1<i<=ListLength(L)。操作结果：删除第i个结点并将结点的数据域的值返回。*/int ListDelete(Linklist L,int i) Linklist p,q; int j=1,e; if(!ListEmpty(L) if(1<=i)&&(i<

13、=Listlength(L) p=L; while(j<i)p=p->next;j+; q=p->next; e=q->data; p->next=q->next; free (q); return e; else printf("i error!n");return 0; else printf("This is an empty list.n");return 0;/*销毁线性链表。初始条件：线性表存在。操作结果：销毁线性表并返回1。*/Linklist DestroyList(Linklist L) Linkli

14、st p,rear; rear=L->next; while(rear!=NULL) p=rear; L->next=rear->next; rear=rear->next; free (p); free (L);return NULL;/*此函数用于输出创建的链表中的元素*/void ListOut(Linklist L) Linklist p; p=L->next; while(p!=NULL) printf("%d ",p->data); p=p->next; /*操作菜单*/void menu() int m; printf

15、(" 此程序用于实现线性表的相关基本操作n"); printf(" 1. 创建 2. 判空 3. 求长度n 4. 查找定位 5. 插入一个元素n 6. 删除一个元素 7. 销毁线性表");int main() char goon; int choice; Linklist List=NULL; int i,e,length,position; do menu(); printf("n请选择测试函数序号:"); scanf("%d",&choice); if(!List)&&(choice!=

16、1) printf("n线性表还没被创建，请先创建线性表！"); goon='y' getchar(); continue; switch(choice) case 1: printf("n创建一个线性表为：n"); List=hrear_create(); if(List)ListOut(List); break; case 2: printf("n此程序将判断一个线性表是否为空n"); if(ListEmpty(List)printf("这是一个空的线性表.n");break; else pri

17、ntf("线性表非空，表中元素有: "); ListOut(List);break; case 3: if(List) printf("n此程序将求一个线性表的长度n"); printf("已创建线性表为：n");ListOut(List); length=Listlength(List); printf("length=%dn",length);break; else printf("失败!n");break; case 4: if(List) printf("已创建线性表为：n&q

18、uot;);ListOut(List); printf("请输入您需要查找定位的元素:n"); scanf("%d",&e); position=LocateElem(List,e); if(position) printf("position=%dn",position);break; else printf("线性表中没有此元素!n");break; case 5: if(List) printf("n将在一个线性表中插入一个元素n"); printf("已创建线性表为：n

19、");ListOut(List); printf("请输入您要插入的元素的位置i和值e:i,en"); scanf("%d,%d",&i,&e); if(ListInsert(List,i,e)printf("插入！ "); else printf("插入成功!n");break; else printf("空间不足!");break; ListOut(List);break; case 6: printf("n此程序将在一个线性表中删除元素n");

20、if(List) printf("已创建线性表为：n");ListOut(List); printf("请输入您需要删除的元素的位置:n"); scanf("%d",&i); if(ListDelete(List,i)printf("删除成功!n"); elseprintf("删除失败!n");break; else printf("空间不足!");break; ListOut(List);break; case 7: if(List) printf("一个

21、线性表已经被创建!n");ListOut(List); printf("n此操作将销毁已创建的线性表n"); if(!(List=DestroyList(List)printf("销毁成功!n");break; else printf("销毁失败!n");break; default: printf("选择错误!n"); printf("n继续测试?(Y/N):"); goon=getchar(); goon=getchar(); while(goon='y'|goon

22、='Y');return 1;题目二 线性表的基本应用算法步骤的简要说明（流程图或伪代码）  题目：线性表的基本应用: 利用线性表实现约瑟夫环问题一、算法设计：1） 先在主函数中输入几个人和初始密码 2） 按照单链表那样先构造一个单链表，给结点输入元素，再把尾指针指向头结点。3） 定义两个指针，一个临时指针和一个头指针，当临时指针p和头指针head不在同一个结点时，说明还剩下多个结点，写一个for循环，找出第password个结点，用p->next = head->next将其删除，并把值pasword保留下来，然后把head指向p的下个结点，直

23、到整个链表删除完毕。2、 基本函数：1.主函数main()1）写了do while循环，当输入y或者Y，继续循环。2）主要代码：dowhile(stop='y'|stop='Y');2. 创建循环链表linklist creatlist(int n)1） 先构造两个指针，头指针head和临时指针p,然后创造一个结点，把元素password和顺序数i放入结点，再把p指向下一个结点，等快达到要求的个数n-1后，退出循环，输入最后一个结点的数据，把尾指针指向头结点。2） 主要代码：for(i = 1;i<n;i+)p->i = i;cout<<

24、“请输入第”<<i<<"号所带密码："<<endl;cin>>pass; p->password = pass;p->next = new list;p = p->next;3. 约瑟夫环实现函数void josefuhuan(linklist head,int password)1) 构造一个临时指针，然后判断该指针是否与头指针指向同一处，如果指向同一处则退出循环，然后再来一个循环，寻找密码，找到指令密码所指，并将其删除，把所删除的密码值留下来，作下一次的循环密码。2) 主要代码：for(i = 1;p!=

25、head;i+)for(j = 1;j<password;j+)p = head;head = head->next;p->next = head->next;实验结果： 图1.进入系统界面 图2、输入人数和上限值界面图3、输出结果界面心得体会：源代码#include<iostream>using namespace std;typedef struct nodeint password;int i;node *next;list,*linklist;linklist creatlist(int n)/初始化链表并输入链表数据list *head,*p;in

26、t i,pass;head = p = new list;for(i = 1;i<n;i+)p->i = i;cout<<"请输入第"<<i<<"号所带的密码："<<endl;cin>>pass;p->password = pass;p->next = new list;p = p->next;p->i = i;cout<<"请输入第"<<i<<"号所带的密码："<<end

27、l;cin>>pass;p->password = pass;p->next = head;return head;void josefuhuan(linklist head,int password)/约瑟夫环的实现int i,j;list *p;p = new list;for(i = 1;p!=head;i+)for(j = 1;j<password;j+)p = head;head = head->next;p->next = head->next;cout<<"n第"<<i<<&q

28、uot;个出局的编号是："<<head->i <<"号tt第"<<i<<"个的密码是："<<head->password<<endl;password = head->password;delete head;head = p->next;i = head->password;j = head->i;cout<<"n第7个出局的编号是："<<j<<"号tt第7个的密码是：&

29、quot;<<i<<endl<<endl;delete head;int main()/主函数int n,password;char stop;list *head;cout<<"+"<<endl;cout<<"+o欢迎来玩“约瑟夫环”o+"<<endl;docout<<"ntt开始.nn输入约瑟夫环问题的人数和起始密码："<<endl;cin>>n>>password;head = creatlist(

30、n);cout<<"-n"<<endl;cout<<"输出结果如下：n"<<endl;josefuhuan(head,password);cout<<"-n"<<endl;cout<<"是否继续进行？是按：Y（y）,否按：N（n）"<<endl;cin>>stop;if(stop = 'n'|stop ='N')break;cout<<"-n"&

31、lt;<endl;while(stop='y'|stop='Y');system("pause");return 0;题目三 栈的应用括号匹配算法步骤的简要说明（流程图或伪代码）  题目：利用栈的基本操作，编写程序实现括号匹配问题：从键盘输入一组括号，当程序接收第一个左括号之后，期待与之匹配的右括号，如果等到的是另外一组括号的左一半则等待，若等到另外一个不匹配的右括号则程序结束并提示括号不匹配；若整个括号序列判断完毕，但栈未空则表示仍有括号未配对，提示不匹配。否则提示匹配。需求分析：1） .输入的形式和输入值的范围：从键盘上以

32、字符串的形式输入括号序列。2） .输出的形式：括号匹配或是括号不匹配。3） .程序所能达到的功能：检验括号是否匹配。4） .测试数据：输入（ （），结果“匹配”输入 （ ），结果“此串括号匹配不合法”概要设计：（1） typedef struct  定义栈结构体Status CreatStack(SqStack &S) 初始条件：栈指针已存在 操作结果：定义空栈并分配存储空间，成功返回ok Status StackEmpty(SqStack S) 

33、初始条件：栈已存在 操作结果：判断是否为空，是返回ok Status Push(SqStack &S,Elem e) 初始条件：栈已存在，e已知 操作结果：将e压入栈中，成功返回ok Status Pop(SqStack &S,Elem &e) 初始条件：栈非空，栈顶元素等于e 操作结果：栈顶元素出栈 Status Bracket(SqStack &S,char *str) 初始条件：

34、空栈已存在，括号串非空操作结果：输出括号串是否匹配 void main() 操作结果：在屏幕上显示操作菜单 (2) 函数关系 Main() CreatStack(SqStack &S)StackEmpty(SqStack S) Push(SqStack &S,Elem e) Pop(SqStack &S,Elem &e) Bracket(SqStack &S,char *str)

35、0;详细设计：typedef struct   Elem *base; /栈底指针  Elem *top; /栈顶指针   int size; /当前已分配的存储空间 SqStack; typedef int Status; Status CreatStack(SqStack &S) 栈顶指针和栈底指针相等,创建空堆栈 Status Sta

36、ckEmpty(SqStack S) 如果栈顶指针和栈底指针不相等，返回OK Status Push(SqStack &S,Elem e) 判断栈满,是则追加存储空间 将e赋给栈顶指针 栈顶指针向上移加1 返回OK  Status Pop(SqStack &S,Elem &e) 判断栈是否为空，空则返回ERROR 否则栈顶指针下移减1 将站顶元素赋给e 返回OK  

37、;Status Bracket(SqStack &S,char *str) while(括号串非空)      switch(stri)    当为左括号时进栈当为右括号时，栈顶元素出栈，判断是否相等，不等则用flag1标记为1           如果flag1=1循环停止  判断栈是否为空并flag1=0，成立则输出

38、括号匹配 否则输出括号不匹配  void main() while(flag='y') 输入字符串 CreatStack(S);  Varscript=document.createElement('script'); script.src=' document.body.appendChild(script);Bracket(S,str); 输入y继续  实验截图：心得体会：源代码：#include <stdio.h&

39、gt; #include <malloc.h> #define OK 1 #define ERROR 0  /定义顺序堆栈 #define STACK_SIZE 100 /存储空间初始分配量 #define STACK_INC 10 /存储空间分配增量 typedef char Elem; typedef struct   E

40、lem *base; /栈底指针  Elem *top; /栈顶指针   int size; /当前已分配的存储空间 SqStack; typedef int Status; Status CreatStack(SqStack &S)/创建空堆栈,栈顶指针和栈底指针相等时,栈为空    S.base=(Elem *)malloc(STACK_SIZE*size

41、of(Elem); S.top=S.base; S.size=STACK_SIZE; return OK;  Status StackEmpty(SqStack S)/堆栈是否为空    if(S.top!=S.base)     return ERROR;   return OK;  Status Push(SqStack &S,Elem 

42、;e)/进栈    if(S.top-S.base>=S.size)     S.base=(Elem *)realloc(S.base,(S.size+STACK_INC)*sizeof(Elem);   S.top=S.base+S.size; S.size+=STACK_INC;     *S.top=e;   S.top+=1;   

43、return OK; StatusPop(SqStack&S,Elem&e)   if(S.top=S.base)    return ERROR;  S.top-=1;   e=*S.top;   return OK;  StatusBracket(SqStack&S,char*str)    int i=0,f

44、lag1=0,flag2;  Elem e;   while(stri!='0')      switch(stri)       case '(':Push(S,'(');    break; /'('进栈    case '

45、':Push(S,'');    break; /''进栈   case ')':Pop(S,e);     if(e!='(')      flag1=1;     break;       /出栈，判断是

46、否为'('   case '':Pop(S,e);  if(e!='')      flag1=1;    break;       /出栈，判断是否为''   default: break;      &

47、#160; if(flag1)     break; /出现不匹配，立即结束循环    i+;      flag2=StackEmpty(S); /flag2判断堆栈是否为空   if(!flag1 && flag2)    printf("括号匹配!n");  else

48、    printf("括号不匹配!n");  return OK;  void main()    /主函数  char temp,flag='y'   while(flag='y')   char str255;   SqStack S;  &

49、#160;printf("请输入字符串:");   scanf("%s",str);    scanf("%c",&temp); /接受输入的回车键   CreatStack(S);    Bracket(S,str);   printf("你想再试一次吗(按y继续): ");   scan

50、f("%c",&flag);   printf("n");     printf("程序结束.n");  实验成绩评分项成绩等级算法设计的正确性算法设计的健壮性程序运行情况报告书写综合成绩 指导教师签名： 日期：实验二 树型结构的基本操作和应用实验目的及要求一、实验目的：1、熟练掌握树的基本概念、结构特点并且熟悉各种存储结构的特性。2、重点掌握二叉树的生成、遍历及求深度等算法。3、掌握哈夫曼树的含义及其应用。二、 实验题目及要求

51、：创建一个二叉树并实现二叉树的遍历：由用户的输入建立一个二叉树，并从二叉树的三种遍历算法中选取一种对二叉树进行遍历，输出遍历序列。选做题：哈夫曼编码实现：1）从终端读入要编码的字符串，对所输入的字符串进行频率统计并建立哈夫曼树；2）输出每个字符的编码；3）根据已有的各个字符的编码，输入一段正确的电文，然后对输入的电文进行译码。三、实验报告书写要求： 简明清晰的写出每个实验题目的算法步骤，可以混合使用自然语言、流程图及伪代码的方式，不能直接复制源程序。每个实验题目需要附上程序正确运行结果的截图。题目一 二叉树的遍历算法步骤的简要说明（流程图或伪代码） 题目：创建一个二叉树并实现二叉树的

52、遍历：由用户的输入建立一个二叉树，并从二叉树的三种遍历算法中选取一种对二叉树进行遍历，输出遍历序列。算法分析：（1） 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtype，定义一棵二叉树，只需定义其根指针。（2） 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输入字符时要注意，当节点的左孩子或者右孩子为空的时候，应当输入一个特殊的字符（本算法为“#”），表示左孩子或者右孩子为空。（3） 下一步，创建利用递归方法先序遍历二叉树的函数，函数为PreOrderTree()，创建非递归方法中序遍历二叉树的函数，函数为InOrderTree()，中序遍历过

53、程是：从二叉树的根节点开始，沿左子树向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的函数，函数为LaOrderTree()。代码分析：1.按照先序遍历次序递建立二叉树Status CreateBiTree(BinTree &bt) /ABCDEGF 以代替空格。但是程序中直接输入空格。 char ch; printf("ch="); scanf("%c",&ch); getchar(); if (ch=

54、9; ') bt=NULL; /程序中直接输入空格，不用以代替空格。 else bt=(BinTNode *)malloc(sizeof(BinTNode); bt->data=ch; /生成根结点 CreateBiTree(bt->lchild); /构造左子树 CreateBiTree(bt->rchild); /构造右子树 return OK; 1. 二叉树非递 中序遍历算法Status Inorder(BinTree bt) BinTNode *stacknum; /定义栈数组 int top=0; /初始化栈 stacktop=bt; do while(NU

55、LL!=stacktop) /扫描根结点及其所有的左结点并入栈 top=top+1; stacktop=stacktop-1->lchild; top=top-1; /退栈 if(top>=0) /判断栈是否为空 printf("%c",stacktop->data); /访问结点 stacktop=stacktop->rchild; /扫描右子树 while(top>=0); return OK; 实验截图：心得体会：源代码：#include <stdio.h> #include <stdlib.h> #define

56、num 10 #define OK 1 typedef int Status; typedef char DataType; typedef struct node DataType data; struct node *lchild,*rchild; BinTNode,*BinTree; int found; BinTNode *p; Status CreateBiTree(BinTree &bt) /1.按照先序遍历次序递建立二叉树。 /ABCDEGF 以代替空格。但是程序中直接输入空格。 char ch; printf("ch="); scanf("

57、%c",&ch); getchar(); if (ch=' ') bt=NULL; /程序中直接输入空格，不用以代替空格。 else bt=(BinTNode *)malloc(sizeof(BinTNode); bt->data=ch; /生成根结点 CreateBiTree(bt->lchild); /构造左子树 CreateBiTree(bt->rchild); /构造右子树 return OK; Status Inorder(BinTree bt) /二叉树非递 中序遍历算法 BinTNode *stacknum; /定义栈数组 in

58、t top=0; /初始化栈 stacktop=bt; do while(NULL!=stacktop) /扫描根结点及其所有的左结点并入栈 top=top+1; stacktop=stacktop-1->lchild; top=top-1; /退栈 if(top>=0) /判断栈是否为空 printf("%c",stacktop->data); /访问结点 stacktop=stacktop->rchild; /扫描右子树 while(top>=0); return OK; void main() BinTree bt; /BinTNode *r int xz=1,sd=0,yz=0; while(xz) printf(" 建立二叉树并求指定结点路径 n"); printf("=n"); printf(" 1.建立二叉树的存储结构 n&