算法与数据结构实验报告

2015-2016学年第二学期

《算法与数据结构》课程实验报告

教育资料

专

业

软件工程 学生姓名 成晓伟 班级 软件141 学

号

1410075094

实验学时 16 实验教师

徐秀芳

信息工程学院

.

实验一 单链表的基本操作

一、实验目的

1.熟悉C语言上机环境，进一步掌握C语言的基本结构及特点。 2.掌握线性表的各种物理存储表示和C语言实现。 3.掌握单链表的各种主要操作的C语言实现。

4.通过实验理解线性表中的单链表存储表示与实现。

二、主要仪器及耗材

普通计算机

三、实验内容与要求

1、用C语言编写一个单链表基本操作测试程序。 （1）初始化单链表 （2）创建单链表 （3）求单链表长度

（4）输出单链表中每一个结点元素 （5）指定位置插入某个元素 （6）查找第i个结点元素的值

（7）查找值为e 的结点，并返回该结点指针

（8）删除第i个结点 （9）销毁单链表 2、实验要求

（1）程序中用户可以选择上述基本操作。 程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。

（2）要求用线性表的顺序存储结构，带头结点的单链表存储结构分别实现。 （3）主函数实现对基本操作功能的调用。 3、主要代码

（1）初始化单链表 }

LinkList *InitList(){ //创建一个空链表,初始化线性表 LinkList *L;

L=(LinkList *)malloc(sizeof(LinkList)); L->next=NULL; return L;

教育资料

.

（2）创建单链表//头插法

void CreateListF(LinkList *L){ LinkList *s; int i=1,a=0; while(1){

printf(\"输入第%d个元素(0表示终止)\ scanf(\"%d\ if(a==0) break;

s=(LinkList *)malloc(sizeof(LinkList)); s->data=a;

s->next=L->next; L->next=s; }

}

（3）求链表长度

int ListLength(LinkList *L){ //求链表长度 int n=0;

LinkList *p=L;

while(p->next!=NULL)

{

p=p->next; n++; }

return(n); }

（4）在指定位置插入元素

int InsertList(LinkList *L,int i,ElemType e){ LinkList *p=L,*s; int j=0;

while(p!=NULL&&jnext; j++;

} //找出要插入的位置的前一个位置 if(p==NULL){ return 0; }

else{

教育资料

.

s=(LinkList *)malloc(sizeof(LinkList));

s->data=e;

s->next=p->next; p->next=s; return 1; } }

（5）输出链表

void DispList(LinkList *L){ //输出链表 LinkList *p=L->next; while(p!=NULL)

{

printf(\"%d\p=p->next;

}

printf(\"\\n\"); }

（6）查找链表中指定元素

int GetElem(LinkList *L,int i){ //查找链表中指定元素 LinkList *p=L;

int j=0;

while(jp=p->next; }

if(p==NULL){ return 0; }

else{

return p->data;

} }

（7）查找值是e的结点并返回该指针

LinkList *LocateElem(LinkList *L,ElemType e){ //查找值是e的结点并返回该指针

int i=1;

LinkList *p=L; while(p!=NULL)

教育资料

.

{

if(p->data==e) return p; }

if(p==NULL){ return NULL; } }

（8）删除元素

int ListDelete(LinkList *L,int i,ElemType *e){ //删除元素 LinkList *p=L,*q; int j=0;

while(p!=NULL&&jnext; j++;

} //找到要删除元素地址的前一个地址 if(p==NULL)

{ return 0;} //不能删除 else{

q=p->next; *e=q->data;

p->next=q->next;

free(q); //删除成功 return 1; } }

（9）销毁链表

void DestroyList(LinkList *L){//销毁链表 LinkList *pre=L,*p=L->next; while(p!=NULL) { }

教育资料

free(pre); pre=p;

p=pre->next; }

free(pre);

.

……

main函数：

int main(){ LinkList *L; ElemType e; int i;

L=InitList(); CreateListF(L); DispList(L);

printf(\"输入要查找的元素位置:\\n\"); scanf(\"%d\e=GetElem(L,i); printf(\"%d\\n\

printf(\"单链表长度为:%d\\n\printf(\"输入要删除元素的位置:\"); scanf(\"%d\

if (i>ListLength(L)) {

printf(\"超出范围重新输入\"); scanf(\"%d\}

if(ListDelete(L,i,&e)==0){ printf(\"未找到元素\\n\"); }

else DispList(L);

printf(\"输入插入元素的位置和值:\"); scanf(\"%d%d\ InsertList(L,i,e); DispList(L); return 0; }

教育资料

.

4、测试数据及测试结果 输入：23 56 12 28 45

输出：

四、注意事项

1、存储结构定义和基本操作尽可能用头文件实现。 2、采用缩进格式，加足够多的注释。 3、注意循环条件、边界条件等。

4、善于发现问题、分析问题、解决问题，并总结思考。 5、对于算法描述及实现完全理解。

五、拓展提高

1、若L为带头结点的单链表，删除最大值结点 2、将两个单链表合并为一个单链表

教育资料

.

实验二 循环链表的基本操作

一、实验目的

熟练掌握线性表的基本操作在链式循环存储结构上的实现。

二、主要仪器及耗材

普通计算机

三、实验内容

1、在上一次单链表基本操作的基础上，修改程序，将其改为单循环链表，并实现相关操作。

（1）初始化单循环链表 （2）创建单循环链表 （3）求单循环链表长度

（4）输出单循环链表中每一个结点元素 （5）指定位置插入某个元素 （6）查找第i个结点元素的值

（7）查找值为e 的结点，并返回该结点指针 （8）删除第i个结点 （9）销毁单循环链表

2、实验要求

（1）程序中用户可以选择上述基本操作。 程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。

（2）要求用不带头结点的循环链表实现。 （3）具体功能测试由主函数实现。 3、主要代码

（1）初始化单循环链表

void initLinkList(LinkList L)//初始化循环单链表 {

L=(LinkList)malloc(sizeof(LNode)); L->next=L;//创建一个空表 }

（2）创建单循环链表

LinkList creat(LinkList L)//给循环链表赋值 {

LinkList p,q,r;

教育资料

.

int N,i=0;

//printf(\"请输入第%d个值：\while(1) {

printf(\"请输入第%d个值：\ scanf(\"%d\输入节点的值 if(N==0)//以0为结尾 {

break; }

if(i==1)//当只有一个节点时

{

p=(LinkList)malloc(sizeof(LNode));//给p节点分配内存空间 p->date =N;

p->next =NULL; q=p; }

else//当节点不为1时 {

r=(LinkList)malloc(sizeof(LNode));

r->date =N; r->next =NULL; q->next =r; q=r;// } }

if(q!=NULL) {

q->next =p;//将尾节点指向头节点完成循环 }

L=p;

return L;//返回头指针 }

（3）打印循环链表

void print(LinkList L)//打印循环链表 {

LinkList p;

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

教育资料

.

p=L;

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

if(p==NULL)//当链表尾空表时 {

printf(\"这是一个空表\\n\"); }

while(p->next!=L)//只有当p节点不为尾节点是打印节点中的数据域 {

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

printf(\"%d \ p=p->next ;

}

printf(\"%d\\n\打印尾节点中的数据 }

（4）求链表的长度

int length(LinkList L)//求链表的长度 {

LinkList p;

//printf(\"**\\n\"); int n=1;

//printf(\"**\\n\"); p=L;

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

while(p->next!=L)//当p节点不为尾节点时计数 {

n++;

//printf(\"**\\n\"); p=p->next; }

return n;//返回链表长度

//printf(\"%d****\\n\}

（5）删除指定位置的节点

LinkList del(LinkList L,int flag)//删除指定位置的节点 {

LinkList p,q; int i; p=L;

教育资料

.

q=L->next ;

//int i=1;

if(flag==1)//当删除节点为头结点时 {

while(q->next !=L)//让p节点为尾节点 {

q=q->next ; }

L=p->next ;//头结点为L->NEXT节点 q->next =L;//让尾节点指向新的头结点 free(p);//释放p } else {

for(i=1;ip=p->next ; q=q->next ; }

p->next =q->next ;

free(q);//删除q节点 }

return L;//返回头指针 }

（6）查找第i个结点元素的值

int search1(LinkList L,int flag)//按照节点的位置返回节点中的数据 {

LinkList p; int i; p=L;

for(i=1;ip=p->next; }

return p->date;//返回节点的数据

}

（7）查找值为e 的结点，并返回该结点指针

教育资料

.

int search2(LinkList L,int data)//按照数据来查找节点的位置 {

LinkList p; int i=1; p=L; while(1) {

if(p->date==data)//当查找到数据域与查找的数据相同是跳出循环 {

break; }

else {

i++;

p=p->next; } }

return i; }

（8）删除第i个结点

LinkList insert(LinkList L,int falg,int data)//指定位置插入元素 {

LinkList p,s; int i; p=L;

s=(LinkList)malloc(sizeof(LNode)); for(i=1;ip=p->next; } }

s->date=data;//将data赋值给s节点 s->next=p->next; p->next=s; return L;

（9）销毁单循环链表

LinkList destroy(LinkList L)//销毁循环链表 {

教育资料

.

LinkList p,q; p=L->next ; while(p!=L) {

q=p->next ; free(p); p=q; }

free(L); L=NULL; return L;

} ……

main函数： int main() {

LinkList L=NULL;

int m,k,Case,Length,DAT1,flag,P,e; printf(\"**1.创建一个循环链表**\\n\");

printf(\"**2.打印所创建的循环链表**\\n\"); printf(\"**3.插入节点**\\n\"); printf(\"**4.删除节点**\\n\"); printf(\"**5.求循环的长度**\\n\"); printf(\"**6.查找第i节点**\\n\");

printf(\"**7.查找某个值得节点**\\n\"); printf(\"**8.销毁链表**\\n\"); printf(\"**9.删除最大节点**\\n\"); printf(\"**10.退出程序**\\n\"); for(;;){

printf(\" 请输入操作的序号 \\n\"); scanf(\"%d\switch(Case) {

case 1: initLinkList(L); L=creat(L); break; case 2: print(L);

教育资料

.

}

break;

case 3: printf(\"请输入需要插入的位置(之后)及其数据\\n\"); scanf(\"%d%d\ L=insert(L,m,k); print(L); break;

case 4: printf(\"请输入需要删除的节点\\n\"); scanf(\"%d\ L=del(L,Case); print(L);

//printf(\"%d\

break;

case 5: Length=length(L);

printf(\"循环的长度是%d\\n\ break;

case 6: printf(\"请输入需要查找的节点序号: \"); scanf(\"%d\ DAT1=search1(L,flag);

printf(\"所查找的节点数据为%d\\n\ break;

case 7: printf(\"输入需要查找的值\\n\"); scanf(\"%d\ P=search2(L,e);

printf(\"所查找的位置是%d\\n\ break;

case 8: L=destroy(L); print(L); break; //case 10:

case 9: exit(0); break; } }

return 0;

4、测试数据及测试结果

教育资料

.

输入：1 2 3 4 5 输出：

四、注意事项

1、存储结构定义和基本操作尽可能用头文件实现。 2、采用缩进格式，加足够多的注释。 3、注意循环条件、边界条件等。

教育资料

.

五、拓展提高

1、双向链表中间结点P后插入新结点S的算法； 2、删除双向链表中间结点P后的结点Q的算法；

教育资料

.

实验三 栈的基本操作及应用

一、实验目的

1、掌握栈的顺序表示和基本操作实现； 2、熟练掌握栈的基本操作； 3、会用栈解决一些实际应用；

4、掌握十进制数转化为N进制整数的工作原理。

二、主要仪器及耗材

普通计算机

三、实验内容

1、栈的基本运算

（1）InitStack(SqStack *s) //初始化栈

（2）Push(SqStack *s, SElemType e)//入栈操作 （3）pop(SqStack *s, SElemType e)//出栈操作

（4）GetTop(SqStack *s, SElemType e)//取栈顶元素 （5）IsEmpty(SqStack *s) //判断是否为空 （6）GetLength(SqStack *s) //求栈的长度

2、创建一个长度为100的顺序栈T，每个数据元素的类型为字符型char。 编写代码，利用栈的基本运算和顺序栈T，正序输入并存储26个英文字母A—Z，然后逆序输出。

3、利用栈的基本运算，写出十进制转化为二进制（八进制呢？十六进制呢？N进制呢？）的具体实现，并输出。

4、实验要求

（1）程序中用户可以选择上述基本操作。 程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。

（2）要求用不带头结点的循环链表实现。 （3）具体功能测试由主函数实现。 5、主要代码 （1）初始化栈

void InitStack(sqStack *s)//初始化栈,构造一个空栈 {

s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//动态分配存储空间

if(!s->base)

exit(0);//存储分配失败

教育资料

.

s->top=s->base;//栈空标记

s->stacksize=STACK_INIT_SIZE; }

（2）取栈顶元素

int GetTop(sqStack *s, ElemType e)//取栈顶元素 {

*(s->top)=e; return e; }

（3）元素入栈

void push(sqStack *s,ElemType e)//元素入栈 {

if(s->top-s->base>=s->stacksize)

{

s->base=(ElemType*)realloc(s->base,(s->stacksize+STACK_INIT_SIZE)*sizeof(ElemType));//栈满,追加存储空间

if(!s->base) exit(0);

}

*(s->top)=e;//输入元素e s->top++;//栈顶指针++ }

（4）元素出栈

void pop(sqStack *s,ElemType *e)//出栈 {

if(s->top==s->base)return;// *e=*--(s->top); }

（5）求栈的长度

int stacklen(sqStack s)//栈的长度 {

return(s.top-s.base); }

（6）判断是否栈空

int stackempty(sqStack *s)//判断是否栈空 {

教育资料

.

if(s->top==s->base)

return 1; else

return 0; }

（7）十进制转化为八进制

void conversion() //十进制转化为八进制 {

sqStack s; int n,t;

ElemType e; InitStack(&s);

printf(\"请输入正整数:\"); scanf(\"%d=n; while(n) {

push(&s,n%8); n=n/8;

}

printf(\"十进制%d转化为八进制为:\ while(!stackempty(&s)) {

pop(&s,&e); printf(\"%d\ }

printf(\"\\n\"); }

（8）二进制转化为十进制

void BintoDec()//二进制转化为十进制 {

ElemType ch; sqStack s;

int len,i,sum=0;

教育资料

InitStack(&s);

printf(\"请输入二进制数，输入#表示结束！\\n\"); scanf(\"%c\

.

while(ch!='#')

{

push(&s,ch); scanf(\"%c\ }

getchar(); //清除缓冲区 len=stacklen(s);

printf(\"栈的当前容量是:%d\\n\ for(i=0;ipop(&s,&ch);

sum=sum+(ch-48)*pow(2,i); }

printf(\"转化为十进制数是%d\\n\

}

（9）26个字母逆序输出 void AZZA()//字母逆序输出 {

ElemType ch[26],e; sqStack s;

int len,i;

for(i=0;i<26;i++) ch[i]='A'+i; InitStack(&s); for(i=0;i<26;i++) {

push(&s,ch[i]); }

len=stacklen(s);

printf(\"栈的当前容量是:%d\\n\ while(!stackempty(&s)) {

pop(&s,&e); printf(\"%c\ }

printf(\"\\n\"); }

教育资料

.

……

main函数 int main() {

AZZA();

printf(\"\\n\"); BintoDec(); printf(\"\\n\"); conversion(); return 0; }

6、测试数据及测试结果 输入：10 34 输出：

四、注意事项

1、存储结构定义和基本操作尽可能用头文件实现。 2、注意栈空和栈满的条件判断。 3、进制转换时余数的存储及输出。

五、拓展提高

*1、输入一个包含’（’和’）’的字符串，检测括号是否匹配（其中括号中能嵌套括号），并输出括号是否匹配的信息（匹配，缺少左括号，缺少右括号）。

*2、输入一个整数表达式，计算出其值，然后输出。（学习表达式的后缀形式及后缀表达式的计算方法）

**3、汉诺塔问题求解。

教育资料

.

实验四 队列的基本操作及应用

一、实验目的

1、会定义顺序队列和链队的结点类型； 2、熟练队列的入队和出队代表的实际意义；

3、掌握两种存储结构下队列的基本操作：入队、出队和输出队列等； 4、熟悉C语言中函数的定义和调用。

二、主要仪器及耗材

普通计算机

三、实验内容

1、建立队列并输出 2、插入元素后输出队列 3、删除元素后输出队列 要求：在输入数据的过程中程序做相应的是否继续输入的提示。每个功能用不同函数实现

4、实验要求

（1）程序中用户可以选择上述基本操作。 程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。 （2）要求用不带头结点的循环链表实现。 （3）具体功能测试由主函数实现。 5、主要代码

（1）初始化队列 /*初始化*/

void InitQueue(sqQueue *&q){

q=(sqQueue *)malloc(sizeof(sqQueue));//动态分配存储空间 q->front=q->rear=0; }

/*初始化队列,构造一个空队列*/ （2）判断队列是否为空

int QueueEmpty(sqQueue *q) {

if(q->rear==q->front) return 0; else return 1;

教育资料

.

}/*判断队列是否为空*/

（3）队列长度

int QueueLength(sqQueue *q){

return (q->rear-q->front+MaxLen)%MaxLen; }

/*队列长度(队元素个数)*/ （4）进队

void enQueue(sqQueue *&q,Elemtype e){ if((q->rear+1)%MaxLen==q->front)//队满 {

printf(\"队满\\n\");

} else {

q->rear=(q->rear+1)%MaxLen; q->data[q->rear]=e; }

}/*进队*/ （5）出队

int deQueue(sqQueue *&q,Elemtype &e){ if(q->front==q->rear)//队空溢出 return 0;

q->front=(q->front+1)%MaxLen; e=q->data[q->front]; return 1; }

/*出队*/ ……

main函数 int main(){

教育资料

int i,j;

Elemtype e,ch; sqQueue *q;

printf(\"(1)初始化队列q\\n\"); InitQueue(q);

printf(\"(2)依次进队MaxLen个元素\\n\"); //getchar();

//scanf(\"%c\

.

/* for(ch='A';ch<'E';ch++) {

//printf(\"输入第%d元素\ if(enQueue(q,ch)==0) printf(\"队满\\n\"); }*/

while(1){

scanf(\"%c\ if(ch=='#') break;

enQueue(q,ch);

}

printf(\"队元素个数:\");

printf(\"%d\\n\printf(\"(3)出队\\n\"); //for(j=0;j<4;j++)

while(QueueEmpty(q)!=0){ deQueue(q,e); printf(\"%c\\n\}

return 0; }

6、测试数据及测试结果

输入：a1 b2 c3 d4 e5 f6 g7 输出：

教育资料

.

教育资料