数据结构实验综合.doc

实 验 一一. 实验题目:线性表的顺序存储结构二. 实验目的:1. 掌握使用Turbo C上机调试线性表的基本方法；2. 掌握线性表的概念及其顺序存储结构3. 熟练采用顺序存储结构实现线性表的基本操作4. 能熟练掌握顺序存储结构中基本算法的实现三. 实验内容:建立包含若干个元素的顺序表,并实现插入,删除,修改且能将结果显示在屏幕上输出.四. 实验步骤:1. 先定义顺序表的数据类型,以0n-1序号建立顺序表,并将此单独定义成一个函数,以便后来反复使用,也为插入,删除和合并等操作定义成单独函数形式.2. 算法实现:#define maxsize 50struct List elemtype listmaxsize; int size;Int insert(elemtype list,int *num,int i,elemtype x) int j; if(i*num+1)print(“error!”); /*插入位置出错*/ return false;if(*num=maxnum-1)printf(“overflow!”); /*表已满*/return false;For(j=*num;j=i;j-)Listj+1=listj; /*数据元素后移*/Listi=x; /*插入X*/(*num)+; /*长度加1*/Return true;int delete(elemtype list,int *num,int i)Int j;If(i*num)printf(“error!”); return false;For(j=i+1;j=*num;j+)Listj-1=listj; (*num)-;Return true;Void merge(elemtype la,elemtype lb,elemtype *lc)int i,j,k; int la-length,lb-length; i=j=0;k=0; la-length=length(la);lb-length=length(lb); /*取表La和Lb的长度*/ initiate(lc); /*初始化表Lc*/ while (i=la-length&j=lb-length) a=get(la,I);b=get(lb,j); if(ab) insert(lc,+k,a);+i; else insert(lc,+k,b);+j; /*将元素插入到Lc中*/ while(i=la-length) a=get(la,i);insert(lc,+k,a); while(jnext=NULL; return TRUE; int insert(slnodetype *h,int i,Elemtype x) slnodetype *p,*q,*s; int j=0; q=p=h; while(p!=NULL&jnext;j+;if ( j!=i-1) printf(“Error!”);return FALSE;if(s=(slnodetype*)malloc(sizeof(slnodetype)=NULL) return FALSE; s-data=x; s-next=p; q-next=s; return TRUE; 3.双向链表算法实现:typedef struct node Elemtype data;struct node *prior,*next; dlnodetype;int insert_dul(dlnodetype *head,int i,Elemtype x)/*在带头结点的双向链表中第i个位置之前插入元素x*/ dbnodetype *p,*s; int j; p=head; j=0; while (p!=NULL&jnext; j+; if(j!=i|idata=x; s-prior=p-prior; p-prior-next=s;s-next=p; p-prior=s; return TRUE;sxpa0ai-1aian-1q headxa0ai-1an-1ai headqps（a）插入前四、 实验结果：祥见第二章2.3节实验三一、 实验题目：栈的顺序存储结构二、 实验目的：1. 熟练掌握栈和多栈共享的概念及其操作特点2. 掌握栈的顺序存储的优缺点3. 掌握顺序栈和多栈共享的基本操作的算法实现三、 实验描述：1. 用C语言先定义一个顺序存储结构的栈，并进行初始化，入栈和出栈等相关操作。2. 顺序算法实现：#define maxnum typedef Struct elemtype stackmaxsize; int top; stacktype; int initStack(sqstack *s) if (s=(sqstack*)malloc(sizeof(sqstack)= =NULL) return FALSE; s-top= -1;return TRUE;int push(sqstack *s, Elemtype x) /*将元素x插入到栈s中,作为s的新栈顶*/if(s-top=MAXNUM-1) return FALSE; /*栈满*/ s-top+; s-stacks-top=x;return TRUE;3.多栈共享的算法实现:typedef Struct elemtype stackmaxnum;int lefttop; /左栈的栈顶指针 int righttop; /右栈的栈顶指针; dupsqstack int initDupStack(dupsqstack *s) if(s=(dupsqstack*)malloc(sizeof(dupsqstack)= =NULL) return FALSE; s-lefttop= -1; s-righttop=MAXNUM; return TRUE;int pushDupStack(dupsqstack *s,char status,Elemtype x) if(s-lefttop+1= =s-righttop) return FALSE; /*栈满*/ if(status=L) s-stack+s-lefttop=x; /*左栈进栈*/ else if(status=R) s-stack-s-lefttop=x; /*右栈进栈*/ else return FALSE; /*参数错误*/ return TRUE; 四、 实验总结：实验四一. 实验题目: 队列顺序存储结构二. 实验目的:1. 掌握队列的概念及C语言定义表示2. 熟练掌握顺序队列的表示,基本运算及其算法实现3. 掌握循环队列的表示三. 实验内容:1. 顺序队列的定义,基本运算及其算法实现2. 循环队列的表示四. 实验步骤:1. C语言定义顺序队列#define maxnum typedef struct elemtype queuemaxnum int front; /*队头指示器*/ int rear; /*队尾指示器*/ sqqueue;2. 顺序队列的基本运算(1) 初始化队列:int initQueue(sqqueue *q)/*创建一个空队列由指针q指出*/if(q=(sqqueue*)malloc(sizeof(sqqueue)= =NULL) return FALSE; q-front= -1; q-rear=-1;return TRUE;(2) 入队列int append(sqqueue *q,Elemtype x)/*将元素x插入到队列q中，作为q的新队尾*/front=-1front=-1Afront= -1ACDBErear=4D（a）（b）（c）（d）rear=-1rear=0rear=4Efront=2if(q-rear=MAXNUM-1) return FALSE; /*队列满*/ q-rear+;q-queueq-rear=x;return TRUE;(3) 出队列Elemtype delete(sqqueue *q)/*若队列q不为空，则返回队头元素*/Elemtype x;if(q-rear= =q-front) return NULL; /*队列空*/x=q-queue+q-front; return x;(4) 循环队列用C语言定义循环队列结构如下： typedef struct Elemtype queueMAXNUM; int front; /*队头指示器*/ int rear; /*队尾指示器*/ int s; /*队列标志位*/ qqueue;五. 实验结果:操作结果祥见章3.30M-11frontrear.实 验 五一、实验题目：串在静态和动态存储方式下求子串二、实验目的： 1.熟练掌握串的基本概念 2.掌握串的静态存储结构和动态存储结构 3.掌握串的常用基本运算的相关函数表示三、实验内容： 在串定义的基础上，静态（把串定义成字符数组形式）或动态（把字符串定义成字符指针形式）方式进行求子串操作四、实验步骤： 1.在静态存储结构方式下求子串：#define MAXNUM typedef struct char strMAXNUM; int length; /*串长度*/ stringtype; /* 串类型定义*/?int substr(stringtype s1,stringtype * s2,int m,int n)int j,k;j=s1.length;if(mj|nk) (*s2).length=k;else (*s2).length=n; /*置子串的串长*/for(j=0;jnext!=NULL;p=p-next) length1+;/*求主串的串长*/ if(mlength1|n0) s2=NULL;return FALSE;/*参数错误*/ p=s1.next; for(j=0;jnext;/*找到子串的起始位置*/ s2=(slstrtype *)malloc(sizeof(slstrtype);/*分配子串的第一个结点*/ v=s2;q=v; for(j=0;jnext!=NULL;j+) /*建立子串*/ q-str=p-str; p=p-next;q=(slstrtype *)malloc(sizeof(slstrtype);v-next=q; v=q; q-str=0;q-next=NULL; /*置子串和尾结点*/return TRUE;五、实验总结：通过求子串进一步了解串中主串和子串的概念及应用实 验 六实验七一、 实验题目：二叉树操作二、 实验目的：1 进一步掌握指针变量的含义。2 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 掌握用指针类型描述、访问和处理二叉树的运算。三、 实验内容：1.认真阅读和掌握本实验的程序。 2. 按先序次序输入二叉树中结点的值（一个字符），0表示空树，生成二叉树的二叉链表存储结构， bt为指向根结点的指针。然后按层次顺序遍历二叉树。四、 实验步骤：1. 本算法采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，遍将右子树根结点入队列，直到队列空为止。因队列是先进先出，从而达到按层次顺序遍历二叉树的目的。2. 算法实现：struct nodexs anytype data; int ltag, rtag; struct nodexs *lch, *rch;typedef struct node int data; struct node *lchild,*rchild;JD;JD *insertbst(JD *r,int x) JD *p,*q,*s; s=(JD *)malloc(sizeof(JD); s-data=x; s-lchild=s-rchild=NULL; q=NULL; if(r=NULL) r=s; return(r); p=r; while(p!=NULL) q=p; if(xdata) p=p-lchild; else p=p-rchild; if(xdata) q-lchild=s; else q-rchild=s; return(r);JD *delnode(JD *r,JD *p,JD *f) JD *q,*s; int flag=0; if(p-lchild=NULL) s=p-rchild; else if(p-rchild=NULL) s=p-lchild; else q=p; s=p-lchild; while(s-rchild!=NULL) q=s; s=s-rchild; if(q=p) q-lchild=s-lchild; else q-rchild=s-lchild; p-data=s-data; free(s); flag=1; if(flag=0) if(f=NULL) r=s; else if(f-lchild=p) f-lchild=s; else f-rchild=s; free(p); return(r);实 验 七一、实验题目：图的操作二、实验目的：1 掌握图的基本存储方法。2 掌握有关