《数据结构》C语言版严蔚敏著.docx

《数据结构》C语言版严蔚敏著.docx

《《数据结构》C语言版严蔚敏著.docx》由会员分享，可在线阅读，更多相关《《数据结构》C语言版严蔚敏著.docx（9页珍藏版）》请在冰点文库上搜索。

《数据结构》C语言版严蔚敏著

《数据结构》（C语言版）严蔚敏著

　　　　　　　　　　　　《数据结构》实验指导及报告书　　　　/　　学年第1学期　　　　　　姓　　名：

　　胡汜亮　　　　学　　号：

　　　　班　　级：

　　　　　　指导教师：

　　　　　　　　1　　　　实验一顺序表与链表　　一、实验目的　　1、掌握线性表中元素的前驱、后续的概念。

　　2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。

3、对线性表相应算法的时间复杂度进行分析。

4、理解顺序表、链表数据结构的特点。

　　二、实验预习　　说明以下概念1、线性表：

　　　　2、顺序表：

　　　　3、链表：

　　三、实验内容和要求　　1、阅读下面程序，在横线处填写函数的基本功能。

并运行程序，写出结果。

#include#include#defineERROR0#defineOK1　　#defineINIT_SIZE5　　/*初始分配的顺序表长度*/#defineINCREM5　　/*溢出时，顺序表长度的增量*/typedefintElemType;/*定义表元素的类型*/typedefstructSqlist{　　ElemType*slist;　　/*存储空间的基地址*/intlength;　　/*顺序表的当前长度*/intlistsize;　　/*当前分配的存储空间*/}Sqlist;　　intInitList_sq（Sqlist*L）;/*　　　　*/intCreateList_sq（Sqlist*L,intn）;/*　　　　*/　　intListInsert_sq（Sqlist*L,inti,ElemTypee）;/*　　*/intPrintList_sq（Sqlist*L）;/*输出顺序表的元素*/intListDelete_sq（Sqlist*L,inti）;/*删除第i个元素*/intListLocate（Sqlist*L,ElemTypee）;/*查找值为e的元素*/　　　　2　　　　intInitList_sq（Sqlist*L）{　　L->slist=（ElemType*）malloc（INIT_SIZE*sizeof（ElemType））;　　if（!

L->slist）returnERROR;　　L->length=0;　　　　L->listsize=INIT_SIZE;　　returnOK;　　　　}/*InitList*/　　intCreateList_sq（Sqlist*L,intn）{　　ElemTypee;　　inti;　　for（i=0;i　　printf（\　　scanf（\　　if（!

ListInsert_sq（L,i+1,e））　　returnERROR;　　}　　returnOK;}/*CreateList*/　　/*输出顺序表中的元素*/　　intPrintList_sq（Sqlist*L）{　　inti;　　for（i=1;ilength;i++）　　printf（\　　returnOK;}/*PrintList*/　　intListInsert_sq（Sqlist*L,inti,ElemTypee）{　　intk;　　if（iL->length+1）　　returnERROR;　　　　if（L->length>=L->listsize）{　　L->slist=（ElemType*）realloc（L->slist,　　（INIT_SIZE+INCREM）*sizeof（ElemType））;　　if（!

L->slist）　　returnERROR;　　L->listsize+=INCREM;　　}　　for（k=L->length-1;k>=i-1;k--）{　　　　L->slist[k+1]=L->slist[k];　　}　　L->slist[i-1]=e;　　　　　　3　　L->length++;　　　　returnOK;}/*ListInsert*/　　/*在顺序表中删除第i个元素*/　　intListDelete_sq（Sqlist*L,inti）{}　　/*在顺序表中查找指定值元素，返回其序号*/intListLocate（Sqlist*L,ElemTypee）{　　}　　intmain（）{　　Sqlistsl;　　intn,m,k;　　printf（\输入顺序表的元素个数*/　　scanf（\　　if（n>0）{　　printf（\　　InitList_sq（&sl）;　　CreateList_sq（&sl,n）;　　printf（\　　PrintList_sq（&sl）;　　printf（\　　scanf（\　　ListInsert_sq（&sl,m,k）;　　printf（\　　PrintList_sq（&sl）;　　printf（\　　}　　else　　printf（\　　return0;}?

运行结果　　?

算法分析　　　　4　　　　2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。

删除算法代码：

　　?

运行结果　　?

算法分析　　　　查找算法代码：

　　?

运行结果　　?

算法分析　　　　5

　　　　　　　　3、阅读下面程序，在横线处填写函数的基本功能。

并运行程序，写出结果。

#include#include#defineERROR0#defineOK1　　typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/　　ElemTypedata;　　structLNode*next;}LNode,*LinkList;　　LinkListCreateList（intn）;/*　　　　　　*/voidPrintList（LinkListL）;/*输出带头结点单链表的所有元素*/　　intGetElem（LinkListL,inti,ElemType*e）;/*　　*/　　LinkListCreateList（intn）{　　LNode*p,*q,*head;　　inti;　　head=（LinkList）malloc（sizeof（LNode））;　　head->next=NULL;　　p=head;　　for（i=0;i　　q=（LinkList）malloc（sizeof（LNode））;　　printf（\　　data%i:

\　　scanf（\输入元素值*/　　q->next=NULL;　　　　/*结点指针域置空*/　　p->next=q;　　　　/*新结点连在表末尾*/　　p=q;　　}　　returnhead;}/*CreateList*/　　intInsertList（LinkListL,ElemTypee,inti）{//InsertbeforeithelementLNode*p=L;intj=0;　　while（p&&jnext;j++;}　　if（!

p||j>i）returnERROR;　　LNode*s=（LinkList）malloc（sizeof（LNode））;s->data=e;　　s->next=p->next;　　6　　p->next=s;returnOK;}　　intDeleteList（LinkListL,ElemType&e,inti）{//删除第i个元素，并e返回其值LNode*p=L;intj=0;　　while（p->next&&jnext;j++;}　　if（!

（p->next）&&jnext;p->next=q->next;e=q->data;free（q）;　　returnOK;}　　voidPrintList（LinkListL）{　　LNode*p;　　p=L->next;/*p指向单链表的第1个元素*/　　while（p!

=NULL）{　　printf（\　　p=p->next;　　}　　}/*PrintList*/　　intGetElem（LinkListL,inti,ElemType*e）{　　LNode*p;intj=1;　　p=L->next;　　while（p&&jnext;j++;　　}　　if（!

p||j>i）　　returnERROR;　　　　　　*e=p->data;　　　　returnOK;}/*GetElem*/　　intmain（）{　　intn,i;ElemTypee;　　LinkListL=NULL;　　/*定义指向单链表的指针*/　　　　7　　printf（\输入单链表的元素个数*/　　scanf（\　　if（n>0）{　　printf（\　　L=CreateList（n）;　　　　printf（\　　PrintList（L）;　　　　printf（\　　printf（\　　scanf（\　　if（GetElem（L,i,&e））　　　　printf（\　　else　　printf（\　　}else　　printf（\　　return0;}　　?

　　运行结果　　　　?

　　算法分析　　4、为第3题补充插入功能函数和删除功能函数。

并在主函数中补充代码验证算法的正确性。

插入算法代码：

　　?

运行结果　　8　　　　?

　　算法分析　　　　删除算法代码：

　　?

运行结果　　?

算法分析　　　　以下为选做实验：

　　5、循环链表的应用　　n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。

　　提示：

用一个无头结点的循环单链表来实现n个元素的存储。

?

算法代码　　　　9　　6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。

　　提示：

指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。

?

算法代码　　　　四、实验小结　　　　五、教师评语　　10

　　　　　　实验二栈和队列　　一、实验目的　　1、掌握栈的结构特性及其入栈，出栈操作；　　2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。

　　　　二、实验预习　　说明以下概念1、顺序栈：

　　　　2、链栈：

　　　　3、循环队列：

　　　　4、链队　　三、实验内容和要求　　1、阅读下面程序，将函数Push和函数Pop补充完整。

要求输入元素序列12345e，运行结果如下所示。

　　　　#include#include#defineERROR0#defineOK1　　#defineSTACK_INT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT5/*存储空间分配增量*/typedefintElemType;/*定义元素的类型*/typedefstruct{　　ElemType*base;　　ElemType*top;　　intstacksize;　　/*当前已分配的存储空间*/　　　　11　　}SqStack;　　intInitStack（SqStack*S）;/*构造空栈*/intpush（SqStack*S,ElemTypee）;/*入栈*/intPop（SqStack*S,ElemType*e）;/*出栈*/intCreateStack（SqStack*S）;　　/*创建栈*/　　voidPrintStack（SqStack*S）;/*出栈并输出栈中元素*/　　intInitStack（SqStack*S）{　　S->base=（ElemType*）malloc（STACK_INT_SIZE*sizeof（ElemType））;　　if（!

S->base）returnERROR;　　S->top=S->base;　　S->stacksize=STACK_INT_SIZE;　　returnOK;}/*InitStack*/　　intPush（SqStack*S,ElemTypee）{　　　　}/*Push*/　　intPop（SqStack*S,ElemType*e）{　　　　}/*Pop*/　　intCreateStack（SqStack*S）{　　inte;　　if（InitStack（S））　　printf（\　　else{　　printf（\　　returnERROR;　　}　　printf（\　　while（scanf（\　　Push（S,e）;　　returnOK;}/*CreateStack*/　　voidPrintStack（SqStack*S）{　　ElemTypee;　　while（Pop（S,&e））　　printf（\}/*Pop_and_Print*/　　12　　intmain（）{　　SqStackss;　　printf（\　　CreateStack（&ss）;　　printf（\　　PrintStack（&ss）;　　return0;}　　　　?

　　算法分析：

输入元素序列12345，为什么输出序列为54321？

体现了栈的什么特性？

　　　　2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数，并验证其正确性。

?

实现代码　　intdecToBin（intx）{　　Returny;}　　?

验证　　　　3、阅读并运行程序，并分析程序功能。

#include#include#include#defineM20　　#defineelemtypechartypedefstruct{　　elemtypestack[M];　　inttop;}　　stacknode;　　　　13　　voidinit（stacknode*st）;　　voidpush（stacknode*st,elemtypex）;voidpop（stacknode*st）;　　voidinit（stacknode*st）{　　st->top=0;}　　voidpush（stacknode*st,elemtypex）{　　if（st->top==M）　　printf（\　　else　　{　　st->top=st->top+1;　　st->stack[st->top]=x;　　}}　　voidpop（stacknode*st）{　　if（st->top>0）st->top--;　　elseprintf（“StackisEmpty!

\\n”）;}　　intmain（）{　　chars[M];　　inti;　　stacknode*sp;　　printf（\　　sp=（stacknode*）malloc（sizeof（stacknode））;　　init（sp）;　　printf（\　　gets（s）;　　for（i=0;i　　if（s[i]==‘（‘）　　push（sp,s[i]）;　　if（s[i]==‘）’）　　pop（sp）;　　}　　if（sp->top==0）　　printf（\　　else　　printf（\　　return0;}　　?

?

?

?

?

　　输入：

2+（（c-d）*6-（f-7）*a）/6运行结果：

　　输入：

a-（（c-d）*6-（s/3-x）/2运行结果：

　　程序的基本功能：

　　　　　　14　　以下为选做实验：

4、假设一带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，试编写相应的置空队列、入队列、出队列的算法。

实现代码：

　　　　四、实验小结　　　　五、教师评语　　15

　　　　　　voidtdfs（graph*g）;　　/*深度优先搜索整个图*/　　voidbfs（intk,graph*g）;　　/*从第k个顶点广度优先搜索*/voidtbfs（graph*g）;　　/*广度优先搜索整个图*/voidinit_visit（）;　　/*初始化访问标识数组*/　　voidcreateGraph（graph*g）/*建立一个无向图的邻接矩阵*/{inti,j;　　charv;　　g->vexnum=0;　　g->arcnum=0;　　i=0;　　printf（\输入顶点序列（以#结束）：

\\n\　　while（（v=getchar（））!

=‘#’）　　{　　g->vexs[i]=v;　　/*读入顶点信息*/　　i++;　　}　　g->vexnum=i;　　/*顶点数目*/　　for（i=0;ivexnum;i++）/*邻接矩阵初始化*/　　for（j=0;jvexnum;j++）　　g->arcs[i][j]=0;　　printf（\输入边的信息：

\\n\　　scanf（\读入边i,j*/　　while（i!

=-1）　　/*读入i,j为－1时结束*/　　{　　g->arcs[i][j]=1;　　g->arcs[j][i]=1;　　scanf（\　　}}　　voiddfs（inti,graph*g）/*从第i个顶点出发深度优先搜索*/{　　intj;　　printf（\　　visited[i]=TRUE;　　for（j=0;jvexnum;j++）　　if（（g->arcs[i][j]==1）&&（!

visited[j]））　　dfs（j,g）;}　　voidtdfs（graph*g）　　/*深度优先搜索整个图*/{　　inti;　　26　　printf（\从顶点%C开始深度优先搜索序列：

\　　for（i=0;ivexnum;i++）　　if（visited[i]!

=TRUE）　　dfs（i,g）;}　　voidbfs（intk,graph*g）/*从第k个顶点广度优先搜索*/{　　inti,j;　　queueqlist,*q;　　q=&qlist;　　q->rear=0;　　q->front=0;　　printf（\　　visited[k]=TRUE;　　q->data[q->rear]=k;　　q->rear=（q->rear+1）%N;　　while（q->rear!

=q->front）　　{　　i=q->data[q->front];　　q->front=（q->front+1）%N;　　for（j=0;jvexnum;j++）　　if（（g->arcs[i][j]==1）&&（!

visited[j]））　　{　　　　printf（\　　visited[j]=TRUE;　　q->data[q->rear]=j;　　q->rear=（q->rear+1）%N;　　}　　}}　　voidtbfs（graph*g）/*广度优先搜索整个图*/{　　inti;　　printf（\从顶点%C开始广度优先搜索序列：

\　　for（i=0;ivexnum;i++）　　if（visited[i]!

=TRUE）　　bfs（i,g）;}　　voidinit_visit（）/*初始化访问标识数组*/{　　inti;　　27　　for（i=0;i　　visited[i]=FALSE;}　　intmain（）{　　graphga;　　inti,j;　　createGraph（&ga）;　　printf（\无向图的邻接矩阵：

\\n\　　for（i=0;i　　for（j=0;j　　printf（\　　printf（\　　}　　init_visit（）;　　tdfs（&ga）;　　init_visit（）;　　tbfs（&ga）;　　return0;}　　?

根据右图的结构验证实验，输入：

ABCDEFGH#0,1　　00,2　　0,51B1,31,4　　4E3D2,5　　2,6　　7H3,7　　4,7-1,-1?

运行结果：

　　　　2、阅读并运行下面程序，补充拓扑排序算法。

#include#include#defineN20　　AC2F5G6　　28　　typedefstructedgenode{/*图的邻接表：

邻接链表结点*/　　intadjvex;/*顶点序号*/　　structedgenode*next;/*下一个结点的指针*/}edgenode;　　typedefstructvnode{/*图的邻接表：

邻接表*/　　chardata;　　/*顶点信息*/　　intind;　　/*顶点入度*/　　structedgenode*link;/*指向邻接链表指针*/}vnode;　　voidcreateGraph_list（vnodeadjlist,int*p）；/*建立有向图的邻接表*/voidtopSort（vnodeg,intn）；/*拓扑排序*/　　voidcreateGraph_list（vnodeadjlist,int*p）{/*建立有向图的邻接表*/　　inti,j,n,e;　　charv;　　edgenode*s;　　i=0;n=0;e=0;　　printf（\输入顶点序列（以#结束）：

\\n\　　while（（v=getchar（））!

=‘#’）　　{　　adjlist[i].data=v;　　/*读入顶点信息*/　　adjlist[i].link=NULL;　　adjlist[i].ind=0;　　i++;　　}　　n=i;　　*p=n;　　/*建立邻接链表*/　　printf（\请输入弧的信息（i=-1结束）：

i,j:

\\n\　　scanf（\　　while（i!

=-1）{　　s=（structedgenode*）malloc（sizeof（edgenode））;　　s->adjvex=j;　　s->next=adjlist[i].link;　　adjlist[i].link=s;　　adjlist[j].ind++;/*顶点j的入度加1*/　　e++;　　scanf（\　　}　　printf（\邻接表:

\　　for（i=0;i　　printf（\　　29　　s=adjlist[i].link;　　while（s!

=NULL）{　　printf（\　　s=s->next;　　}　　}}　　voidtopSort（vnodeg,intn）{/*拓扑排序*/　　}　　intmain（）{　　vnodeadjlist[N];　　intn,*p;　　p=&n;　　createGraph_list（adj