中南民族大学《数据结构》学生实验报告.doc

1、院 系： 计算机科学学院 专 业： 网络工程 年 级： 2012 课程名称： 数据结构 学 号： 姓 名： 指导教师： 2014 年 6 月日年级 2012 学号专业 网络工程 班号 1201 组号 姓名实验名称 第二章 线性表 实验室实验目的或要求了解线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在某种存储结构上如何实现这些基本运算。在熟悉上述内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。实验原理（算法流程）1、 实验内容单链表的各种基本操作，包括创建，查找，插入，删除，输出，合并等2、存储结构

2、描述及说明链式存储结构typedef struct node char data; struct node *next; linklist;3、函数说明linklist *rcrect(linklist *head) 尾插法建立单链表void print(linklist *head) 输出函数，输出单链表。linklist location(linklist *head) 按序号查找函数，按序号查找单链表中数据。linklist inset(linklist *head) 插入函数，在单链表中插入数据。linklist delet(linklist *head) 删除函数，删除单链表中的数据

3、。int main() 主函数，程序运行调用各子函数。4、模块之间的调用关系开 始主函数创建单链表查找单链表数据删除数据输出函数插入函数程序清单：#include#include#include typedef struct node /定义节点类型char data;struct node *next; /因为上面结构体的类型名是 struct node linklist 是别名 linklist; /一般 List 顺序表，linklist 链表int main()int a;linklist *head;head=(linklist *)malloc(sizeof(linklist);p

4、rintf(“请先建立单链表!n“); linklist *rcrect(linklist *head); /调用尾插法rcrect(head);/*linklist *hcrect(); /或者调用头插法hcrect();*/for(;)printf(“n 您想要对此单链表表做何种操作 :n0.退出t1.查找t2.插入t3. 删除n“);scanf(“%d“,if(a3)printf(“您输入的数字有误，请重新输入 !n“);if(a=0) /退出exit(0);if(a=1) linklist location(linklist *head); /调用按序号查找函数location(hea

5、d); if(a=2)linklist inset(linklist *head); /调用插入函数inset(head);if(a=3)/调用删除函数 linklist delet(linklist *head); /调用删除函数delet(head);return 0;/1.尾插法建立单链表linklist *rcrect(linklist *head) /尾插法 链接到已经建立好的单链表的末尾linklist *p,*last;char ch; /用于输入字符last=head; printf(“请输入你要存储的字符,以!号结束：n“);while(ch!=!)p=(linklist *

6、)malloc(sizeof(linklist);scanf(“%c“,p-data=ch; /每次都申请一个节点，数据域存放数据，指针域为空 / printf(“%ct“,p-data); 可以用来测试存储是否正确 last-next=p; last=p; /上一次的最后一个元素的地址赋给 lastp-next=NULL; void print(linklist *head); /调用输出函数print(head);return head;/2.输出函数函数void print(linklist *head) linklist *p;p=head-next;printf(“n 你存储的数据为

7、 :n“);while(p!=NULL)printf(“%ct“,p-data);p=p-next;/3.按序号查找函数linklist location(linklist *head)linklist *p;int i,k=0;p=head;printf(“n 请输入你要查找链表中第几个元素： n“);scanf(“%d“, while(pk+;if(ki|!p)printf(“输入的序号有误，查找失败！n“);exit(0); elseprintf(“第%d 个元素的值为：%cn“,i,p-data);return *head;/4.插入函数linklist inset(linklist

8、*head)linklist *p,*p1; int i,k=0;char ch;p=head; /不能为 head-nextprintf(“请输入你要在链表的第几个位置?t 插入什么元素?n“);scanf(“%d %c“, p1=(linklist *)malloc(sizeof(linklist); /新建一个节点p1-data=ch;p1-next=NULL; while(pk+; if(ki-1|!p)printf(“输入的序号有误，插入失败！n“);exit(0); else p1-next=p-next;p-next=p1;printf(“插入后的新数据为:n“); /输出插入后

9、的新数据 p=head-next;while(p!=NULL)printf(“%ct“,p-data);p=p-next; printf(“n“);return *head;/5.删除函数linklist delet(linklist *head)linklist *p,*p1,*p2;p=head;int i,k=0;printf(“请输入你要删除第几个元素:n“);scanf(“%d“,while(pk+;if(ki-1|!p)printf(“输入的序号有误，删除失败！n“);exit(0); else p2=p-next;p-next=p2-next;free(p2);printf(“删

10、除后的新数据为:n“); /输出插入后的新数据 p=head-next;while(p!=NULL) printf(“%ct“,p-data);p=p-next; printf(“n“);return *head; 组内分工（可选）无实验结果分析及心得体会实验结果截图：心得体会：通过本次实验对于线性表的运用更熟练了，对于单链表的建立，删除，插入，输出更加熟悉。成绩评定教师签名：年 月 日年级 2012 学号 2012213773专业 网络工程 班号 1201 组号 姓名 黄勇实验名称 第三章 栈和队列 实验室实验目的或要求在掌握栈（队列）特点的基础上，懂得在什么样的情况下能够使用栈（队列） 。

11、能熟练使用栈（队列）的一种存储表示，以及在该存储结构上如何实现栈（队列）的基本操作。在熟悉上述内容的基础上，能够针对具体应用问题的特点，选择栈（队列）设计出相应的有效算法，解决与栈（队列）相关的实际问题。实验原理（算法流程）1、实验内容括号匹配的检验。合法的括号包括（）和【】两类，利用栈判断任意输入的一个括号序列是否匹配对出现，若是输出“right“，否则输出”error！“。且提示错误原因。2、 存储结构描述及说明typedef struct int *base;int *top;int stacksize;SqStack;顺序存储结构3、函数说明int InitStack(SqStack

12、*S) 构造函数，构造一个空栈 S，该栈预定义大小为STACK_INIT_SIZEint push(SqStack *S,int e) 插入函数，在栈 S 中插入元素 e 为新的栈顶元素。int pop(SqStack *S,int *e) 删除函数，若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 1；否则返回 ERRORvoid match(char str) 检测函数，对输入的表达式进行检测，括号是否匹配，匹配则返回配对，否则返回不配对。int main() 主函数。4、模块之间的调用关系主函数构造函数 插入函数删除函数检测函数程序清单：#include “stdio.h“#i

13、nclude “conio.h“ #include “stdlib.h“ #define ERROR -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct int *base;int *top;int stacksize;SqStack;int InitStack(SqStack *S) S-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);if(!S-base) printf(“n 磁盘不足.n“); getch();exit(ERROR); S-top=S-

14、base;S-stacksize=STACK_INIT_SIZE;return 1; int push(SqStack *S,int e) if(S-top-S-base=S-stacksize) S-base=(int *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(int);if(!S-base) printf(“n 磁盘不足 .n“); getch(); exit(ERROR); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=e; return 1;

15、int pop(SqStack *S,int *e) if(S-top=S-base) printf(“n 栈已满.n“); return ERROR; *e=*-S-top;return 1; void match(char str) SqStack S;char *p;int e; InitStack( p=str; while(*p) if(*p=(|*p=|*p=)push( else if(*p=)|*p=|*p=)if(*(S.top-1)+1=*p|*(S.top-1)+2=*p)pop(else printf(“n 不配对.n“); return; p+; if(S.top=S.base)printf(“n 配对.n“);else printf(“n 不配对！n“); int main() char str100;printf(“n 输入表达式:n“); gets(str); match(str); getch();