算法与数据结构实验报告

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

实验一  单链表的基本操作

一、实验目的

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表示终止)",i++);

        scanf("%d",&a);

        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&&j        p=p->next;

        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->data);

        p=p->next;

    }

    printf("\\n");

}

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

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

    LinkList *p=L;

    int j=0;

while(j        j++;

        p=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&&j        p=p->next;

        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",&i);

    e=GetElem(L,i);

    printf("%d\\n",e);

    printf("单链表长度为:%d\\n",ListLength(L));

    printf("输入要删除元素的位置:");

    scanf("%d",&i);

if (i>ListLength(L))

    { 

        printf("超出范围重新输入");

        scanf("%d",&i);

    }

    if(ListDelete(L,i,&e)==0){

        printf("未找到元素\\n");

    }

    else DispList(L);

    printf("输入插入元素的位置和值:");

    scanf("%d%d",&i,&e);

    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个值：",++i);

    while(1)

    {

        printf("请输入第%d个值：",++i);

        scanf("%d",&N);//输入节点的值

        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->date );

        p=p->next ;

    }

    printf("%d\\n",p->date );//打印尾节点中的数据

}

（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",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;i        {

            p=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;i    {

        p=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;i    {

        p=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",&Case);

    switch(Case)

    {

    case 1: initLinkList(L);

            L=creat(L);

            break;

    case 2: print(L);

            break;

    case 3: printf("请输入需要插入的位置(之后)及其数据\\n");

            scanf("%d%d",&m,&k);

            L=insert(L,m,k);

            print(L);

            break;

    case 4: printf("请输入需要删除的节点\\n");

            scanf("%d",&Case);

            L=del(L,Case);

            print(L);

            //printf("%d",Length);

            break;

    case 5: Length=length(L);

            printf("循环的长度是%d\\n",Length);

            break;

    case 6: printf("请输入需要查找的节点序号: ");

            scanf("%d",&flag);

            DAT1=search1(L,flag);

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

            break;

    case 7: printf("输入需要查找的值\\n");

            scanf("%d",&e);

            P=search2(L,e);

            printf("所查找的位置是%d\\n",P);

            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);

    t=n;

    while(n)

    {

        push(&s,n%8);

        n=n/8;

    }

    printf("十进制%d转化为八进制为:",t);

    while(!stackempty(&s))

    {

        pop(&s,&e);

        printf("%d",e);

    }

    printf("\\n");

}

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

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

{

    ElemType ch;

    sqStack s;

    int len,i,sum=0;

    InitStack(&s);

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

    scanf("%c",&ch);

    while(ch!='#')

    {

        push(&s,ch);

        scanf("%c",&ch);

    }

    getchar();           //清除缓冲区

    len=stacklen(s);

    printf("栈的当前容量是:%d\\n",len);

for(i=0;i    {

        pop(&s,&ch);

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

    }

    printf("转化为十进制数是%d\\n",sum);

}

（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",len);

     while(!stackempty(&s))

     {

       pop(&s,&e);

       printf("%c",e);

     }

     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",&ch);

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

     {

        //printf("输入第%d元素",i);

        if(enQueue(q,ch)==0)

        printf("队满\\n");

    }*/

    while(1){

        scanf("%c",&ch);

        if(ch=='#')

        break;

        enQueue(q,ch);

    }

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

    printf("%d\\n", QueueLength(q));

    printf("(3)出队\\n");

//for(j=0;j<4;j++)

    while(QueueEmpty(q)!=0){

        deQueue(q,e);

        printf("%c\\n",e);

    }

    return 0;

}

6、测试数据及测试结果

输入：a1 b2 c3 d4 e5 f6 g7  

输出：