数据结构实验综合

一. 实验题目:线性表的顺序存储结构 二. 实验目的:

1.

2. 3. 4.

掌握使用Turbo C上机调试线性表的基本方法； 掌握线性表的概念及其顺序存储结构

熟练采用顺序存储结构实现线性表的基本操作 能熟练掌握顺序存储结构中基本算法的实现

三. 实验内容:

建立包含若干个元素的顺序表,并实现插入,删除,修改且能将结果显示在屏幕上输出.

四. 实验步骤:

1. 先定义顺序表的数据类型,以0~n-1序号建立顺序表,并将此单独定义成一个函

数,以便后来反复使用,也为插入,删除和合并等操作定义成单独函数形式. 2. 算法实现:

#define maxsize 50 For(j=i+1;j<=*num;j++) struct List List[j-1]=list[j]; { elemtype list[maxsize]; (*num)--; int size;} Return true;}

Int insert(elemtype list[],int *num,int Void merge(elemtype i,elemtype x) la[],elemtype lb[],elemtype **lc) int j; if(i<0//i>*num+1) {int i,j,k; {print(“error!”); /*插入位置出错*/ int la-length,lb-length; return false;} i=j=0;k=0; if(*num>=maxnum-1) {printf(“overflow!”); /*表已满*/ la-length=length(la);lb-length=length(

lb); /*取表La和Lb的长度*/ return false;}

initiate(lc); /*初始化表Lc*/ For(j=*num;j>=i;j--)

List[j+1]=list[j]; /*数据元素后移*/ while (i<=la-length&&j<=lb-length) List[i]=x; /*插入X*/ {a=get(la,I);b=get(lb,j); (*num)++; /*长度加1*/ if(a} /*将元素插入到Lc中*/ int delete(elemtype list[],int

*num,int i) while(i<=la-length) Int j; {a=get(la,i);insert(lc,++k,a);} If(i<0//i>*num) while(j<=lb_length) {printf(“error!”); return false;} {b=get(lb,j);insert(lc,++k,b);}}

五. 实验结果:

实 验 二

一、 实验题目：线性表的链式存储结构 二、 实验目的：

1. 掌握线性表的链式存储概念及其结构特点

2. 熟练掌握线性表链式存储的基本运算及其实现

3. 掌握单链表、循环链表和双向链表算法表示区别与联系

三、 实验描述：

1. 先建立一个空的单链表，并将其初始化后，进行插入节点和删除节点操作。 2. 单链表算法实现： Typedef struct slnode int j=0; { Elemtype data; q=p=h; struct slnode *next; while(p!=NULL&&jnext;j++;} slnodetype *p,*q,*s; if ( j!=i-1) {printf(“Error!”);return int Initiate(slnodetype * *h) FALSE; {If((*h=(slnodetype*)malloc(sizeof(slnif((s=(slnodetype*)malloc(sizeof(slnododetype)))==NULL) etype)))==NULL) return FALSE; return FALSE; (*h)->next=NULL; s->data=x; return TRUE; }int s->next=p; insert(slnodetype *h,int i,Elemtype x) q->next=s; { slnodetype *p,*q,*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||i<1)

{ printf(“Error!”); return FALSE;}

if((s=(dlnodetype*)malloc(sizeof(dlnodetype)))==NULL) return FALSE;

s->data=x; s->prior=p->prior; p->prior->next=s;s->next=p; p->prior=s; return TRUE;}

p a a a s x （a）插q p … a x s 四、 实验结果：祥见第二章2.3节

q … … … aa

实验三

一、 实验题目：栈的顺序存储结构 二、 实验目的：

1. 熟练掌握栈和多栈共享的概念及其操作特点 2. 掌握栈的顺序存储的优缺点

3. 掌握顺序栈和多栈共享的基本操作的算法实现

三、 实验描述：

1. 用C语言先定义一个顺序存储结构的栈，并进行初始化，入栈和出栈等相关操作。 2. 顺序算法实现：

FALSE; /*栈满*/ #define maxnum

typedef Struct if(status=’L’)

{ elemtype stack[maxsize]; s->stack[++s->lefttop]=x; /*左栈进栈*/ int top; }stacktype; else if(status=’R’)

s->stack[--s->lefttop]=x; /*右栈进栈*/ int initStack(sqstack *s)

else return FALSE; /*参{if ((s=(sqstack*)malloc(sizeof(sqstack)))=

数错误*/ =NULL) return FALSE;

s->top= -1; return TRUE; return TRUE;} } int push(sqstack *s, Elemtype x) /*将元 素x插入到栈s中,作为s的新栈顶*/

四、 实验总结：

{if(s->top>=MAXNUM-1) return FALSE; /*栈满*/ s->top++;

s->stack[s->top]=x; return TRUE;}

3.多栈共享的算法实现: typedef Struct

{ elemtype stack[maxnum];

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

实验四

一. 实验题目: 队列顺序存储结构 二. 实验目的:

1. 掌握队列的概念及C语言定义表示

2. 熟练掌握顺序队列的表示,基本运算及其算法实现 3. 掌握循环队列的表示

三. 实验内容:

1. 顺序队列的定义,基本运算及其算法实现 2. 循环队列的表示 四. 实验步骤:

1. C语言定义顺序队列 #define maxnum <最大元素数> typedef struct {

elemtype queue[maxnum] 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的新队尾*/ if(q->rear>=MAXNUM-1) return FALSE; /*队列满

*/

q->rear++;

q->queue[q->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 queue[MAXNUM]; int front; /*队头指示器*/ int rear; /*队尾指示器*/ int s; /*队列标志位*/ }qqueue;

rear五. 实验结果:操作结果祥见章3.3 =4 rear M-1 …... rear0 frontE D C B A rear=4 front=2 （c

E D 1 rear=-1 （=-1 …... =-1 front =0 frontA front=

（

（

实 验 五

一、实验题目：串在静态和动态存储方式下求子串 二、实验目的：

1.熟练掌握串的基本概念

2.掌握串的静态存储结构和动态存储结构 3.掌握串的常用基本运算的相关函数表示 三、实验内容：

在串定义的基础上，静态（把串定义成字符数组形式）或动态（把字符串定义成字符指针形式）方式进行求子串操作 四、实验步骤：

1.在静态存储结构方式下求子串： #define MAXNUM <80> typedef struct {

char str[MAXNUM]; int length; /*串长度*/ } stringtype; /* 串类型定义*/?

int substr(stringtype s1,stringtype * s2,int m,int n) {int j,k;j=s1.length;

if(m<=0||m>j||n<0) {(*s2).str[0]='\\0';(*s2).length=0;return FALSE; }k=strlen(&s1.str[m-1]) ;/*求子串的长度*/ if (n>k) (*s2).length=k;

else (*s2).length=n; /*置子串的串长*/

for(j=0;j<=(*s2).length;j++,m++) (*s2).str[j]=s1.str[m-1]; (*s2).str[j]=’\\0’;/*置结束标记*/ return TRUE;}

2.动态方式下求子串 typedef struct node{

char str; struct node *next;} slstrtype; int substr(slstrtype s1,slstrtype *s2,int m,int n) {slstrtype *p,*q,*v; int length1,j;p=&s1;

for(lenght1=0;p->next!=NULL;p=p->next) length1++;/*求主串的串长*/ if(m<=0||m>length1||n<0) {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 q->rchild=s; { anytype data; return(r); int ltag, rtag; JD *delnode(JD *r,JD *p,JD *f) struct nodexs *lch, *rch; { JD *q,*s; }; int flag=0;

typedef struct node if(p->lchild==NULL) { int data; s=p->rchild; struct node *lchild,*rchild; else if(p->rchild==NULL) }JD; s=p->lchild; JD *insertbst(JD *r,int x) else{ q=p; { JD *p,*q,*s; s=p->lchild; s=(JD *)malloc(sizeof(JD)); while(s->rchild!=NULL) s->data=x; { q=s; s->lchild=s->rchild=NULL; s=s->rchild;} q=NULL; if(q==p) if(r==NULL) { r=s; return(r);} q->lchild=s->lchild; p=r; else while(p!=NULL) q->rchild=s->lchild; { q=p; p->data=s->data; if(xdata) free(s); p=p->lchild; flag=1; } else if(flag==0) p=p->rchild; { if(f==NULL) r=s; } else if(f->lchild==p) if(xdata) f->lchild=s; q->lchild=s; else f->rchild=s; else free(p);

}

return(r);}}

实 验 七

一、实验题目：图的操作 二、实验目的：

1． 掌握图的基本存储方法。

2． 掌握有关图的操作算法并用高级语言编程实现； 3． 熟练掌握图的两种搜索路径的遍历方法。 三、实验内容：

1.认真阅读和掌握本实验的程序

2. 以邻接矩阵和邻接表的方式存储连通图。然后分别用优先深度算法遍历邻接居真方式存储的图和邻接表方式存储的图。这里假设图只有4个顶点，在实验的时候可以根据需要更改vtxnum的值。 四、实验步骤：

算法实现：深度优先 if(visited[i]==0) void traver(TD g[],int n) bfs(g,i,visited); { int i; } static int visited[M]; void bfs(TD g[],int v,int visited[]) for(i=1;i<=n;i++) { int qu[M],f=0,r=0; visited[i]=0; JD *p; for(i=1;i<=n;i++) printf(\"%d\\n\ if(visited[i]==0) visited[v]=1; dfs(g,i,visited); qu[0]=v; } while(f<=r) void dfs(TD g[],int v,int visited[]) { v=qu[f++]; { JD *w; p=g[v].firstarc; int i; while(p!=NULL) printf(\"%d \ { v=p->adjvex; visited[v]=1; if(visited[v]==0) w=g[v].firstarc; { visited[v]=1; while(w!=NULL) printf(\"%d\\n\ { i=w->adjvex; qu[++r]=v; if(visited[i]==0) } dfs(g,i,visited); p=p->next; w=w->next; } } } }宽度优先搜索 } void traver(TD g[],int n) { int i;

static int visited[M]; for(i=1;i<=n;i++) visited[i]=0; for(i=1;i<=n;i++)