数据结构实验报告

本文格式为Word版，下载可任意编辑——数据结构实验报告本科试验报告

课程名称：

数据结构（C语言版）

试验工程：

线性表、树、图、查找、内排序

试验地点：

明向校区试验楼208

专业班级：

学号：

学生姓名：

指导教师：

杨永强

2022年

1月10日

试验名称

试验一

线性表

试验目的和要求

本次实习的主要目的是为了使学生熟练把握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求细心阅读并理解以下例题，上机通过，并观测其结果，然后独立完成后面的实习题。

试验内容

1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍旧有序。

2．用单链表ha存储多项式A（x）=a0+a1x1+a2x2++anxn(其中aI为非零系数)，用单链表hb存储多项式B（x）=b0+b1x1+b2x2++bmxm(其中bj为非零系数)，要求计算C（x）=A（x）+B（x），结果存到单链表hc中。试写出程序。

主要仪器设备

台式或笔记本电脑试验记录((写出试验内容中(1)(2)的运行结果和程序代码)(可分栏或加页))

1.#includestdio.h

#includestdlib.h#includestring.h

#defineOK1#defineOVERFLOW-1

typedefcharElemType;

#defineLIST_INIT_SIZE100#defineLISTINCREMENT10

typedefstructLNode{//顺序表节点结构

ElemType*elem;//存储空间基址

intlength;//当前长度

intlistsize;//当前分派的存储容量

}SqList;

intInitList(SqListL){//构造线性表

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);

printf(输入线性表：);

gets(L.elem);

L.length=strlen(L.elem);

L.listsize=LIST_INIT_SIZE;

returnOK;}

intListInsert_Sq(SqListL,ElemTypex){//将元素X插入在适当位置

if(L.length=L.listsize){

ElemType*newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=LISTINCREMENT;

}

inti=-1;//插入元素的位置

for(intj=0;jstrlen(L.elem);j++){

if(xL.elem[j]){

i=j;break;

}

}

if(i==-1)i=strlen(L.elem);

//printf(i=%d\n,i);

ElemType*q;

q=L.elem+i;//q为插入位置

for(ElemType*p=(L.elem+L.length-1);p=q;--p){

*(p+1)=*p;//插入位置及之后元素右移

}

*q=x;

L.length++;

returnOK;

}

voidPrintLinkList(SqListL){//输出顺序表

for(inti=0;iL.length;i++){

printf(%c,L.elem[i]);

}

}intmain(void){

SqListL;

InitList(L);

//PrintLinkList(L);

ElemTypex;

printf(输入插入元素：);

scanf(%c,x);

ListInsert_Sq(L,x);

printf(线性表为：);

PrintLinkList(L);

return0;}

#includestdio.h

#includestdlib.h#includestring.h#defineOK1

typedefstruct{//项的表示，多项式的项作为LinkList的数据元素

floatcoef;//系数

intexpn;//指数

}term,ElemType;

typedefstructLNode{//单链表节点结构

ElemTypedata;

structLNode*next;}LNode,*LinkList;

typedefLinkListpolynomial;

intCreatLinkList(polynomialP,intn){//创立多项式

P=(polynomial)malloc(sizeof(LNode));

polynomialq=P;

q-next=NULL;

polynomials;

for(inti=0;in;i++){

s=(polynomial)malloc(sizeof(LNode));

scanf(%f%d,(s-data.coef),(s-data.expn));

q-next=s;

s-next=NULL;

q=q-next;

}

returnOK;}运行结果

2.voidPrintfPolyn(polynomialP){

polynomialq;

for(q=P-next;q;q=q-next){

if(q-data.coef!=1)

printf(%g,q-data.coef);

if(q-data.expn)

printf(%c%c%d,"x","^",q-data.expn);

elseprintf(%g,q-data.coef);

if(q-next)printf(+);

}

printf(\n);}

voidAddPolyn(polynomialPa,polynomialPb,polynomialPc){

polynomialqa,qb,qc;

qa=Pa-next;

qb=Pb-next;

qc=Pc;

//qa、qb、qc分别指向Pa、Pb、Pc的当前结点

while(qaqb){

if((qa-data.expn)(qb-data.expn)){

qc-next=qa;qc=qa;

qa=qa-next;

}

if((qa-data.expn)(qb-data.expn)){

qc-next=qb;qc=qb;

qb=qb-next;

}

if((qa-data.expn)==(qb-data.expn)){

qa-data.coef+=qb-data.coef;

if(qa-data.coef!=0.0){

qc-next=qa;qc=qa;qa=qa-next;

polynomialb=qb;

qb=qb-next;free(b);

}

else{//删除qaqb当前指向节点qaqb后移

polynomialda,db;

da=qa;db=qb;

qa=qa-next;

qb=qb-next;

free(da);free(db);

if(!qa-next!qb-next)

qc-next=NULL;

}

}

}

qc-next=qa?qa:qb;

free(Pa);

free(Pb);}

intmain(void){

inta,b;

polynomialPa,Pb,Pc;

printf(分别输入多项式A和多项式B的元素个数:);

scanf(%d%d,a,b);

printf(输入多项式A：);

CreatLinkList(Pa,a);

printf(输入多项式B：);

CreatLinkList(Pb,b);

CreatLinkList(Pc,0);

printf(A(x)=);

PrintfPolyn(Pa);

printf(B(x)=);

PrintfPolyn(Pb);

AddPolyn(Pa,Pb,Pc);

printf(C(x)=);

PrintfPolyn(Pc);

return0;}运行结果

遇到的问题和解决方法

对线性表的基本操作不熟悉，查找课本，屡屡运用，加深理解，以便能够将各种操作及其应用运用到程序中。

心得体会

不能只看课本，要自己动手写程序，在实践中加深理解。

试验名称

试验二

树

试验目的和要求

熟悉树的各种表示方法和各种遍历方式，把握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。

试验内容

编写递归算法，计算二叉树中叶子结点的数目。

主要仪器设备

台式或笔记本电脑试验记录((写出试验内容中(1)(2)的运行结果和程序代码)(可分栏或加页))

#includestdio.h#includestdlib.h

#defineOK1#defineOVERFLOW-1

typedefcharTElemType;

typedefstructBiTNode{//结点结构

TElemTypedata;

structBiTNode

*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;

//按先序序列建立二叉树intCreateBiTree(BiTreeT){

TElemTypech;

scanf(%c,ch);

if(ch==".")T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T-data=ch;

//生成根结点

CreateBiTree(T-lchild);

//构造左子树

CreateBiTree(T-rchild);

//构造右子树

}

returnOK;

}//CreateBiTree

intLeaf(BiTreeT){

if(T==NULL)

return0;

if(!T-lchild!T-rchild)

return1;

returnLeaf(T-lchild)+Leaf(T-rchild);

}intmain(){

BiTreeT;//declaration

printf(\n输入树:\n);

//用例:ABD..EH...CF.I..G..\n

CreateBiTree(T);//创立

printf(\n叶子结点树为:);

intn=Leaf(T);

printf(%d\n,n);

return0;}运行结果

遇到的问题和解决方法

对递归理解不够到位，写关于递归的算法有困难。通过查找资料，请教同学解决问题。

心得体会

要培养自己的动手实践能力。

试验名称

试验三

图

试验目的和要求

熟悉图的存储结构，把握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。

试验内容

试基于图的深度优先探寻策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(ij)。

主要仪器设备

台式或笔记本电脑试验记录((写出试验内容中(1)(2)的运行结果和程序代码)(可分栏或加页))

#includestdio.h#includestdlib.h

#defineMAX_VERTEX_NUM30

typedefstructArcNode{

intadjvex;

structArcNode*nextarc;}ArcNode;

typedefstructVNode{

intdata;

ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];

typedefstruct{

AdjListvertices;

intvexnum,arcnum;}ALGraph;

creat_DG_ALGraph(ALGraph*G){

inti,j,k;ArcNode*p;

p=NULL;

printf(分别输入结点数、边数:);

scanf(%d%d,G-vexnum,G-arcnum);

printf(输入结点:\n);

for(i=0;iG-vexnum;i++)

{

scanf(%d,G-vertices[i].data);

G-vertices[i].firstarc=NULL;

}

/*for(i=0;iG-vexnum;i++)

printf(%d,G-vertices[i].data);

printf(\n);*/

for(k=0;kG-arcnum;k++){

p=(ArcNode*)malloc(sizeof(ArcNode));

printf(输入边i,j:);

scanf(%d,%d,i,j);

printf(\n);

p-adjvex=j;

p-nextarc=G-vertices[i].firstarc;

G-vertices[i].firstarc=p;

}

}

intexist_path_DFS(ALGraphG,inti,intj){

ArcNode*p;

intk,visited[MAX_VERTEX_NUM];

p=NULL;

if(i==j)return1;

else{visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p-nextarc)

{k=p-adjvex;

if(!visited[k]exist_path_DFS(G,k,j));

}

}}

intmain(void){

ALGraph*G;

inti,j;

G=NULL;

creat_DG_ALGraph(G);

printf(输入要查找的路径（从i到j）:\n);

scanf(%d%d,i,j);

if(exist_path_DFS(*G,i,j))printf(Existthepath!);

elseprintf(Notexistthepath);

return0;}遇到的问题和解决方法

不熟悉图的存储结构和有关算法的实现。

心得体会

要多看课本把握基本知识。

试验名称

试验四

查找

试验目的和要求

通过本次试验，把握查找表上的有关查找方法，并分析时间繁杂度。

试验内容

1．编写程序实现下面运算：在二叉排序树中查找关键字为key的记录。

2.试将折半查找的算法改写成递归算法。

主要仪器设备

台式或笔记本电脑试验记录((写出试验内容中(1)(2)的运行结果和程序代码)(可分栏或加页))

1.#includestdio.h

#includestdlib.h

#defineFALSE0#defineTURE1

typedefstructBiTNode

{

intkey;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

intSearchBST(BiTreeT,intkey,BiTreef,BiTreep)//查找

{

if(!T)

{p=f;returnFALSE;}

elseif(key==T-key){p=T;returnTURE;}

elseif(keyT-key)SearchBST(T-lchild,key,T,p);

elseSearchBST(T-rchild,key,T,p);

}

intInsertBST(BiTreeT,intkey)//插入

{

if(!T)

{

T=(BiTree)malloc(sizeof(BiTNode));

T-key=key;

T-lchild=(T)-rchild=NULL;

}

if(key==T-key)returnFALSE;

if(keyT-key)InsertBST(T-rchild,key);

elseInsertBST(T-lchild,key);

}

intmain(void)

{

inte,n;

BiTreeT=NULL,f,p;

printf(输入长度：);

scanf(%d,n);

printf(输入关键字：);

while(n--)

{

scanf(%d,e);

InsertBST(T,e);

}

printf(输入要查找元素：);

scanf(%d,e);

if(SearchBST(T,e,f,p))printf(查找成功\n);

elseprintf(查找失败\n);

return0;

}运行结果

2.#includestdio.h#includestdlib.h

#defineOK1#defineOVERFLOW-1

#defineLIST_INIT_SIZE100

//顺序表初始分派量#defineLISTINCREMENT10

//分派增量

typedefintKeyType;

typedefstruct{//元素结构

KeyTypekey;//主键

//

//其他}SElemType;

typedefstruct{//顺序查找表结构

SElemType*elem;

intlistsize;

intlength;}SSTable;

intPrintSqList(SSTableST){//输出顺序表

printf(SequenlialList.\nPos\tKey\n);

for(inti=1;i=ST.length;i++)

printf(%5d\t%5d\n,i,ST.elem[i]);

returnOK;}//PrintSSTable

intInitSSTable(SSTableST,SElemTypevalue[],intn){//初始化顺序表

ST.elem=(SElemType*)malloc(LIST_INIT_SIZE*sizeof(SElemType));

if(!ST.elem)exit(OVERFLOW);

ST.listsize=LIST_INIT_SIZE;

ST.length=n;

SElemType*p=ST.elem[1];//elem[0]作为哨兵

for(inti=0;in;i++)*p++=value[i];

returnOK;}//InitSSTable

//折半查找intSearch_Bin(SSTableST,KeyTypekey,intlow,inthigh){

if(low=high){

intmid=(low+high)/2;

if(ST.elem[mid].key==key)returnmid;

if(ST.elem[mid].keykey)returnSearch_Bin(ST,key,low,mid-1);

if(ST.elem[mid].keykey)returnSearch_Bin(ST,key,mid+1,high);

}

elsereturn0;}

intmain(void){

SSTableST;//声明

SElemTypevalue[]={12,23,28,35,37,39,50,60,78,90};//用例

InitSSTable(ST,value,(sizeof(value))/(sizeof(SElemType)));//初始化

PrintSqList(ST);//输出

KeyTypekey=23;//关键字

printf(key=%d\tpos=%d\n,key,Search_Bin(ST,key,1,(sizeof(value))/(sizeof(SElemType))));//折半查找

key=58;

printf(key=%d\tpos=%d\n,key,Search_Bin(ST,key,1,(sizeof(value))/(sizeof(SElemType))));//折半查找

}

运行结果

遇到的问题和解决方法

不熟悉树的存储结构和有关算法的实现。

心得体会

要多看课本把握基本知识。

试验名称

试验五

内部排序

试验目的和要求

通过本次试验，把握线性表的排序方法，并分析时间繁杂度。

试验内容

设计一个用链表表示的直接选择排序算法，并用程序实现。

算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点，从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已排序序列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后面，让r指向这个结点。反复执行这个过程，直到排好序。

主要仪器设备

台式或笔记本电脑试验记录((写出试验内容中(1)(2)的运行结果和程序代码)(可分栏或加页))

#includestdio.h

#includestdlib.h#includestring.h

#defineOK1

typedefintElemType;typedefstructLNode{//单链表节点结构

ElemType

data;

structLNode

*next;}LNode,*LinkList;

intCreatLinkList(LinkListL,intn){//创立带头单链表

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

ElemTypee;

L-next=NULL;

LinkListp;