2009级数据结构实验指导书

数据结构实验指导书

教案

2010～2011学年 第1学期

《数据结构》实验教案

教学院（部） 计算机学院

教 研 室 基础教研室

授 课 班 级 09应用

授 课 教 师 杨 慧

职 称 职 务 讲 师

教 材 名 称 《数据结构》 朱战立 主编

2010年 8 月30 日

- 1 -

数据结构实验指导书

实 验 安 排 表

周次 4 5-6 7 8 9 14 15 16 日期 9.20-9.24 9.27-10.8 10.8-10.15 实验课题 实验一 线性表 （一） 实验一 线性表（二） 实验一 线性表 （三） 学时 2 2 2 2 2 2 2 2 实验报告次 数 0 0 1 1 1 1 0 1 10.18-10.22 实验二 栈、队列的实现及应用 10.25-10.29 实验三 串及数组的实验 11.29-12.3 12.6-12.10 实验四 二叉树的基本操作 实验五 查找和排序（一） 12.13-12.17 实验五 查找和排序（二） 检查日期 检查人 一式三份: 一份交教务处,一份存教学系部,一份由本人保存.

- 2 -

数据结构实验指导书

实验一 线性表

一、实验目的

1、掌握用TC环境上机调试线形表的基本方法

2、掌握顺序表、链表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现

二、实验内容

1、顺序表基本操作的实现

[问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

[基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。 [实现提示] 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。 [程序实现]

#include #include typedef int DataType ; # define maxnum 20 typedef struct {int data[maxnum]; int length; }SeqList; /*插入函数*/

int insert(SeqList *L , int i , DataType x) /* 将新结点x插入到顺序表L第i个位置 */ { int j ;

if( i<0 || i>(*L).length +1) { printf(\值不合法 ! \ return 0; }

if((* L).length >=maxnum-1) { printf(\表满不能插入!\ return 0; }

for(j=(*L).length;j>=i;j--) (*L).data[j+1]=(*L).data[j]; (*L).data[i] = x; (*L).length++; return 1; }

/*删除函数*/

int delete( SeqList *L ,int i) /*从顺序L中删除第i个结点*/ { int j ;

if( i<0|| i>(*L).length )

{ printf(\删除位置错误 ! \return 0; }

for(j=i+1;j<=(*L).length;j++) (*L).data[j-1] =(*L).data[j];

- 3 -

数据结构实验指导书

(*L).length--; return 1; }

/*生成顺序表*/

void creatlist(SeqList * L) { int n , i;

printf(\请输入顺序表 L 的数据个数：\\n\scanf(\for(i=0 ; i

{ printf(\ scanf(\}

(*L).length=n-1; printf(\}/*creatlist */

/*输出顺序表 L*/

printout(SeqList * L) { int i ;

for (i=0 ; i<=(* L).length ; i++) { printf(\ printf(\}/*printout */ printf(\}

main()

{ SeqList *L ; char cmd ; int i, x; clrscr() ; creatlist(L); do {

printf(\插入\\n\printf(\删除\\n\printf(\退出\\n\do

{cmd=getchar() ;

}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q')); switch(cmd) { case 'i': case 'I': printf(\ scanf(\ printf(\ scanf(\ insert(L,i,x) ;

- 4 -

数据结构实验指导书

printout(L); break ; case 'd': case 'D' : printf(\ scanf(\ delete(L,i);

printout(L); break ;

}

}while((cmd!='q')&&(cmd!='Q')); }

2、有序顺序表的合并

[问题描述] 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc

[基本要求] lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表 [程序实现]

# include # define maxnum 20 typedef int DataType ; typedef struct

{ DataType data[maxnum] ; int length ; }SeqList ;

int MergeQL(SeqList la , SeqList lb , SeqList *lc) { int i , j , k ;

if (la.length+1 + lb.length+1>maxnum) { printf(\return 0; }

i=j=k=0;

while(i<=la.length && j<=lb.length) { if (la.data[i]<=lb.data[j])

lc->data[k++]=la.data[i++] ; else

lc->data[k++]=lb.data[j++]; }

/* 处理剩余部分 */

while (i<=la.length) lc->data[k++]=la.data[i++]; while (j<=lb.length) lc->data[k++]=lb.data[j++]; lc->length=k-1; return 1; }

main()

{ SeqList la={{3,4,7,12,15},4} ; SeqList lb={{2,5,7,15,18,19},5} ; SeqList lc ;

- 5 -

数据结构实验指导书

int i ;

if (MergeQL(la,lb,&lc)) { printf(\

for(i=0;i<=lc.length ; i++) printf(\} }

3、单链表基本操作的实现

[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素

x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。

[基本要求]用链式存储结构实现存储

[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结

点，而要从单链表的头结点开始一个一个地计数寻找。

[程序实现]

# include # include typedef char DataType ;

typedef struct node{

DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode;

void Init_List(ListNode **L) {

(*L)=(ListNode *)malloc(sizeof(ListNode));/*产生头结点*/ (*L)->next=NULL; }

int List_Length(ListNode *L ) {

int n=0;ListNode *p=L->next; while(p!=NULL) { n++;

p=p->next; }

return n; }

ListNode* GetNode(ListNode *L,int i) {

int j;

ListNode *p;

p=L;j=0; /*从头结点开始扫描*/

while(p->next&&j!=i) /*顺指针向后扫描,直到p->next为NULL或i=j为止*/

- 6 -

数据结构实验指导书

{

p=p->next; j++; }

if(i==j)

return p; /*找到了第i个结点*/ else

return NULL; /*当i<0或i>0时,找不到第i个结点*/ }

void InsertList(ListNode *L,DataType x,int i) {

ListNode *p,*s;

p=GetNode(L,i-1); /*寻找第i-1个结点*/

if (p==NULL) /*i<1或i>n+1时插入位置i有错*/ { printf(\ return ; }

s=(ListNode *)malloc(sizeof(ListNode)); s->data=x;s->next=p->next;p->next=s; }

void DeleteList(ListNode *L ,int i) {

ListNode *p,*r;

p=GetNode(L,i-1); /*找到第i-1个结点*/

if (p==NULL||p->next==NULL) /*i<1或i>n时,删除位置错*/ { printf(\ return ; }

r=p->next; /*使r指向被删除的结点a*/ p->next=r->next; /*将ai从链上删除*/ free(r); }

/*使用头插法建立带头结点链表算法*/ ListNode * CreatListF(void) {

char ch;

ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ ListNode *s; /*工作指针*/ head->next=NULL;

ch=getchar(); /*读入第1个字符*/ while(ch!='\\n') {

s=(ListNode *)malloc(sizeof(ListNode)); /*生成新结点*/

s->data=ch; /*将读入的数据放入新结点的数据域中*/ s->next=head->next;

- 7 -

数据结构实验指导书

head->next=s;

ch=getchar(); /*读入下一字符*/ }

return head; }

/*使用尾插法建立带头结点链表算法*/ ListNode * CreatListR1(void) {

char ch;

ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ ListNode *s,*r; /*工作指针*/

r=head; /*尾指针初值也指向头结点*/ while((ch=getchar())!='\\n') {

s=(ListNode *)malloc(sizeof(ListNode)); s->data=ch; r->next=s; r=s; }

r->next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; }

/*复制链表A中的内容到表B中*/

void copy(ListNode *a, ListNode *b) {

ListNode *pa=a->next; ListNode *u; ListNode *rb=b; while(pa!=NULL) {

u=( ListNode *)malloc(sizeof(ListNode)); u->data=pa->data; rb->next=u; rb=u;

pa=pa->next; }

rb->next=NULL; }

/*输出带头结点的单链表*/

void DisplaySL(ListNode *la, char *comment) { ListNode *p ; p=la->next ;

if(p) printf(\ while(p) { printf(\ p=p->next; }

printf(\

- 8 -

数据结构实验指导书

}

/*主函数*/ main( )

{ ListNode *la ,*lb,*lc, *p ; int n,x,i;

printf(\用头插法建立链表la，请输入节点内容:\la=CreatListF();

DisplaySL(la,\新生成链la节点内容:\

printf(\链表la的长度: -\printf(\请输入要插入的元素: \scanf(\

printf(\请输入要插入的位置：\scanf(\InsertList(la,x,i);

DisplaySL(la,\插入后链la节点内容\printf(\请输入要删除元素的位置：\scanf(\DeleteList(la,i);

DisplaySL(la, \删除后链la节点内容\

printf(\用尾插法建立链表lb，请输入节点内容:\fflush(stdin); lb=CreatListR1();

DisplaySL(lb,\新生成链lb节点内容:\Init_List(&lc); copy(la,lc);

DisplaySL(lc,\复制生成的链lc节点内容:\}

4、有序单链表的合并

[问题描述] 已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。

[基本要求] 不破坏la表和lb表的结构。 [程序实现]

# include #include #define NULL 0

typedef int DataType; typedef struct SLNode { DataType data;

struct SLNode * next; }slnodetype;

int MergeSL(slnodetype *la,slnodetype *lb,slnodetype **lc); int CreateSL(slnodetype *la,int n);

void DisplaySL(slnodetype *la , char * comment); main( )

{ slnodetype *la, *lb, *lc ,*p; int n,m;

la=(slnodetype *)malloc(sizeof(slnodetype)); la->next=NULL;

- 9 -

数据结构实验指导书

lb=(slnodetype *)malloc(sizeof(slnodetype)); lb->next=NULL;

lc=(slnodetype *)malloc(sizeof(slnodetype)); lc->next=NULL;

printf(\输入链la节点数:\scanf(\

printf(\输入链la 节点内容:\CreateSL(la,n);

DisplaySL(la,\链la 节点内容:\printf(\输入链lb节点数:\scanf(\

printf(\输入链lb节点内容:\CreateSL(lb,m);

DisplaySL(lb,\链lb 节点内容:\

if(MergeSL(la,lb,&lc)) DisplaySL(lc,\合成后的链lc:\getchar(); }

int MergeSL(slnodetype * la , slnodetype *lb,slnodetype * *lc) { slnodetype * pa, * pb, * pc;

lc=(slnodetype *)malloc(sizeof(slnodetype)); pa=la->next; pb=lb->next; pc= *lc;

while(pa&&pb) {

pc->next=(slnodetype*)malloc(sizeof(slnodetype));

pc=pc->next;

if(pa->data<=pb->data) { pc->data=pa->data; pa=pa->next; }

else{ pc->data=pb->data; pb=pb->next; } }

while (pa) /*插入la链的剩余段 */

{

pc->next=(slnodetype*)malloc(sizeof(slnodetype)); pc=pc->next;

pc->data=pa->data; pa=pa->next; }

/*插入lb链的剩余段*/ while(pb) {

pc->next=(slnodetype*)malloc(sizeof(slnodetype)); pc=pc->next;

pc->data=pb->data; pb=pb->next;

- 10 -

数据结构实验指导书

}

}

/*生成单链表*/

int CreateSL(slnodetype *la ,int n) { int i ;

slnodetype *p , *q ; q=la ;

for (i=1 ; i<=n ; i++)

{ p=(slnodetype *)malloc(sizeof(slnodetype)); scanf(\q->next=p; q=p; }

q->next=NULL ; return 1 ; }

/*输出单链表*/

void DisplaySL(slnodetype *la, char *comment) { slnodetype *p ; p=la->next ;

if(p) printf(\while(p)

{ printf(\p=p->next ; }

printf(\}

5、约瑟夫环问题

[问题描述]设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。

[基本要求] 选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。

[实现提示] 程序运行之后，首先要求用户指定初始报数的下限值，可以n<=30,此题循环链表可不设头节点，而且必须注意空表和非空表的界限。

如 n=8, m=4 时，若从第一个人， 设每个人的编号依次为 1，2，3，?开始报数，则得到的出列次序为4，8，5，2，1，3，7，6，

如下图所示，内层数字表示人的编号 ，每个编号外层的数字代表人出列的序号。 [程序实现]

#include #include typedef struct node { int num;

struct node *next; }linklist;

linklist *creat(head,n) /*使n个人围成一圈，并给每个人标识号数*/ linklist *head; int n ;

- 11 -

数据结构实验指导书

{linklist *s,*p; int i;

s=(linklist * )malloc(sizeof(linklist)); head=s; s->num=1; p=s;

for(i=2;i<=n; i++)

{ s=(linklist *) malloc(sizeof(linklist)); s->num=i; p->next=s; p=s; }

p->next=head; return(head); }/* creat */

linklist * select(linklist *head, int m) { linklist *p, *q; int i, t; p=head; t=1;

q=p; /* q为p的前趋指针*/ p=p->next; do {

t=t+1 ; /*报一次数*/ if(t%m==0) { printf(\ q->next=p->next; free(p); p=q->next; }

else { q=p; p=p->next; } }while(q!=p); head=p;

printf(\ return (head); }/* select */

main( ) { int n,m;

linklist *head;

printf(\ scanf(\

printf(\ scanf(\ head=creat(head,n); head=select(head,m);

printf(\

- 12 -

数据结构实验指导书

}/* main */

三、注意事项

1、 删除元素或插入元素表的长度要变化。

2、 在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的

元素复制到总表去即可。

3、 链表中在第i个节点前删除或插入节点需要用指针来表示第i-1个

节点。

4、 在合并链表时需要设置多个指针变量。

5、 循环链表如果不是要删除的节点则指针后移，否则删除该节点。

思考题：编程实现两个循环单链表的合并。

实验二 栈、队列的实现及应用

一、实验目的

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。

二、实验内容

1、实现栈的顺序存储

# define MAXSIZE 100 typedef int ElemType; typedef struct

{ ElemType data[MAXSIZE]; int top; }SeqStack;

void InitStack(SeqStack *s) {s->top=0; return 1; }

int StackEmpty(SeqStack *s) { if(s->top==0) return 1; else return 0; }

int StackFull(SeqStack *s)

{ if(s->top==MAXSIZE-1) return 1; else return 0; }

void Push(SeqStack *s,int x)

{ if (StackFull(s)){ printf(\ return 0; }

- 13 -

数据结构实验指导书

else { s->data[s->top]=x;

s->top++; }

}

void Display(SeqStack *s) {if(s->top==0)

printf(\ else{ while(s->top!=0)

{ printf(\ s->top=s->top-1;

}

} }

ElemType Pop(SeqStack *s)

{ if(StackEmpty(s)) return 0; else return s->data[--s->top]; }

ElemType StackTop(SeqStack *s) { int i;

if(StackEmpty(s)) return 0; else { i=s->top-1;

return s->data[i];} /*返回栈顶元素的值，但不改变栈顶指针*/

}

main(SeqStack *p)

{int n,i,k,h,x1,x2,select;

printf(\ InitStack(p);

printf(\ scanf(\ for(i=0;i

{ printf(\ scanf(\ Push(p,k); }

printf(\ printf(\ printf(\

printf(\

printf(\ scanf(\ switch(select)

{case 1:{ display(p); break;}

case 2:{ printf(\ scanf(\ Push(p,h);

- 14 -

数据结构实验指导书

case 3:{ display(p); break;} x1=Pop(p);

printf(\ display(p); break;

} case 4:{ x2=StackTop(p);

printf(\

break;

}

}

2、利用栈实现数制转换

# define MAXSIZE 100

typedef int ElemType； /*将顺序栈的元素定义为整型*/ typedef struct

{ ElemType data[MAXSIZE]; int top; }SeqStack;

void InitStack(SeqStack *s) {s->top=0; return 1; }

int StackEmpty(SeqStack *s) { if(s->top==0) return 1; else return 0; }

int StackFull(SeqStack *s) { if(s->top==m-1) return 1; else return 0; }

void Push(SeqStack *s,int x)

{ if (StackFull(s)){ printf(\ return 0; }

else { s->data[s->top]=x;

s->top++; }

}

ElemType Pop(SeqStack *s) { ElemType y;

if(StackEmpty(s)){ printf(\ return 0;

- 15 -

}

数据结构实验指导书

}

else { y=s->data[s->top]; s->top=s->top-1; return y; } }

ElemType StackTop(SeqStack *s) { if(StackEmpty(s)) return 0; else return s->data[s->top]; }

void Dec_to_Ocx (int N) /* n是非负的十进制整数，输出等值的八进制数*/ {

SeqStack *S； /*定义一个顺序栈*/ ElemType x； Init_SeqStack(S)； /*初始化栈*/ if(N<0) {

printf(\。\； return； }

if(!N) Push(S,0)；

while(N) /*自右向左产生八进制的各位数字，并将其进栈*/ { Push(S，N%8)； /*余数入栈 */ N=N/8； /*商作为被除数*/ }

printf(\

while(StackEmpty(S)) /*栈非空时退栈输出*/ { x=Pop(S)；

printf(“%d”,x)； }

printf(\}

main( ) { int n;

printf(\scanf(\Dec_to_Ocx (n); }

三、注意事项

1、进栈、出栈栈顶指针都要改变。

2、数制转换余数入栈后商作为被除数。

思考题

1、实现循环队列的顺序存储

- 16 -

数据结构实验指导书

实验三 串及数组的实验

一、实验目的及要求

1、了解串及数组的两种存储方法，掌握数组在作为存储结构中的地址计算方法。

2、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。 二、实验内容

（一）顺序串的基本操作

#define MaxSize 100 typedef struct {

char str[MaxSize]; int len; } strtype;

void assign(strtype *s,char t[]) {

int i=0;

while (t[i]!='\\0') { s->str[i]=t[i]; i++; }

s->str[i]='\\0'; s->len=i; }

void strcopy(strtype *s,strtype t) {

int i;

for (i=0;i<=t.len;i++) s->str[i]=t.str[i]; }

int length(strtype s) {

return(s.len); }

int equal(strtype s,strtype t) {

int i=0;

if (s.len!=t.len) return(0); else { for (i=0;i

- 17 -

数据结构实验指导书

strtype concat(strtype s,strtype t) {

strtype r; int i,j;

for (i=0;i

for (j=0;j<=t.len;j++) r.str[s.len+j]=t.str[j]; r.len=i+j; return(r); }

int index(strtype s,strtype t) {

int i,j,k;

for (i=0;s.str[i];i++) for (j=i,k=0;s.str[j]==t.str[k];j++,k++) if (!t.str[k+1]) return(i); return(-1); }

strtype substr(strtype s,int i,int k) {

strtype t; int j;

for (j=i;j

t.str[t.len]='\\0'; return(t); }

void insert(strtype *s,int i,strtype t) {

strtype r; int j;

if (i>s->len) printf(\位置参数值错误\\n\ else { for (j=i;jlen;j++) /*将s的第i个位置之后的字串复制到r中*/ r.str[j-i]=s->str[j]; r.len=j-i; r.str[r.len]='\\0'; for (j=0;jstr[i+j]=t.str[j]; for (j=0;jstr[i+t.len+j]=r.str[j]; s->len=s->len+t.len; /*修改s串长度*/ s->str[s->len]='\\0'; } }

- 18 -

数据结构实验指导书

void delete(strtype *s,int i,int k) {

int j;

if (i>s->len || i+k>s->len) printf(\位置参数值错误\\n\ else { for (j=i+k;jlen;j++) /*将s的第i+k个位置之后的字串前移k位*/ s->str[j-k]=s->str[j]; s->len=s->len-k; /*修改s的长度*/ s->str[s->len]='\\0'; } }

strtype replace(strtype s,strtype t,strtype v) {

int i;

i=index(s,t); while (i>=0) { delete(&s,i,t.len); insert(&s,i,v); i=index(s,t); }

return(s); }

void display(strtype s) {

printf(\字符串:%s\\n\ }

main() {

strtype s,t,r,v;

assign(&s,\ assign(&t,\ assign(&v,\ display(s); display(t); display(v);

printf(\长度=%d\\n\ printf(\与v连接\ display(concat(t,v));

printf(\中的t替换成v后的\ display(replace(s,t,v)); }

（二）三元组稀疏矩阵的基本操作

#include #define Max 100 #define M 3 #define N 3 #define K 3

- 19 -

数据结构实验指导书

typedef int smat[Max][3]; void display();

void creatmat(int A[M][N],smat B) /*A是一个稀疏矩阵,B是产生的相对应的三元组存储*/ {

int i,j,k=1;

for (i=0;i

B[0][0]=M;B[0][1]=N;

B[0][2]=k-1; /*存入非0元素个数*/ }

int findval(smat A,int x) {

int i,t;

t=A[0][2]; /*非0元素个数*/ i=1;

while (i<=t && A[i][2]!=x) i++; /*查找等于x的元素值*/ if (i<=t) return(1); else return(0); }

void trsmat(smat A,smat B) /*A是稀疏矩阵的三元组形式,B是存放A的转置矩阵的三元组*/ {

int m,n,p,q,t,col; /* m:A中的行数; n:A中的列数; t:A的非0元素个数*/ /* q:B的下一个项位置; p:A的当前项*/ m=A[0][0]; n=A[0][1]; t=A[0][2];

B[0][0]=n; B[0][1]=m; B[0][2]=t; /*产生第0行的结果*/ if (t>0) /*非0元素才做转置*/ {

q=1; for (col=0;col

void matadd(smat A,smat B,smat C) {

int i=1,j=1,k=1;

while (i<=A[0][2] && j<=B[0][2])

- 20 -

数据结构实验指导书

/*若A的当前项的行号等于B的当前项的行号,则比较其列号,将较小列的项*/ /*存入C中,如果列号也相等,则将对应的元素值相加后存入C中*/ if (A[i][0]==B[j][0]) if (A[i][1]

else if (A[i][1]>B[j][1]) { C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2]; k++;j++; } else { C[k][0]=B[j][0];C[k][1]=B[j][1]; C[k][2]=A[i][2]+B[j][2]; k++;i++;j++; }

else if (A[i][0]

/*若A的当前项的行号小于B的当前项的行号,则将A的项存入C中*/ { C[k][0]=A[i][0];C[k][1]=A[i][1];C[k][2]=A[i][2]; k++;i++; } else

/*若A的当前项的行号大于B的当前项的行号,则将B的项存入C中*/ { C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2]; k++;j++; }

C[0][0]=A[0][0]; /*产生第0行的结果*/ C[0][1]=A[0][1]; C[0][2]=k-1; }

void matmul(int m,int n,int k,smat A,smat B,smat C) {

int i,j,l,p=1,s; for (i=0;i

- 21 -

数据结构实验指导书

} C[0][0]=m; /*产生第0行的结果*/ C[0][1]=k; C[0][2]=p-1; }

int value(smat C,int i,int j) /*用在matmul函数之中,计算C[i][j]的值*/ {

int k=1;

while (k<=C[0][2] && (C[k][0]!=i || C[k][1]!=j)) k++; if (k<=C[0][2]) return(C[k][2]); /*找到了返回该位置的值*/ else return(0); /*未找到说明该元素为0*/ }

void display(char *s,smat A) {

int i;

printf(\三元组:\\n\\t Row Col Val\\n\ for (i=1;i<=A[0][2];i++) printf(\ }

main() {

int A[M][N]={{0,1,0},{6,0,0},{1,0,0}}; int B[M][N]={{1,2,0},{0,4,0},{0,3,0}}; smat C,D,E,F,G; creatmat(A,C); creatmat(B,D);

display(\矩阵\

printf(\处的值:%d\\n\ printf(\元素3是否存在:%d\\n\ matadd(C,D,E);

display(\ matmul(M,N,K,C,D,F); display(\×B\ trsmat(C,G); display(\

}

三、注意事项

1、三元组中两个矩阵相加，只有同行同列时对应元素才相加。

实验四 二叉树的基本操作

一、实验目的

1、进一步掌握指针变量、动态变量的含义。

2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。

二、实验内容

- 22 -

数据结构实验指导书

1、以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。

#define M 10

typedef int DataType;/*元素的数据类型*/ typedef struct node { DataType data;

struct node *lchild,*rchild; }BitTNode,*BiTree; int front=0,rear=0; BitTNode *que[10]; BitTNode *creat() {BitTNode *t; DataType x; scanf(\ if(x==0) t=NULL;

else{ t=(BitTNode *)malloc(sizeof(BitTNode)); t->data=x;

t->lchild=creat(); t->rchild=creat(); }

return(t); }/*creat*/

/* 前序遍历二叉树t */ void preorder(BiTree t) { if(t!=NULL)

{ printf(\ preorder(t->lchild);

preorder(t->rchild); } }

/* 中序遍历二叉树t */ void inorder(BiTree t) { if(t!=NULL)

{ inorder(t->lchild); printf(\ inorder(t->rchild); } }

/* 后序遍历二叉树t */ void postorder(BiTree t) { if(t!=NULL)

{ postorder(t->lchild); postorder(t->rchild);

printf(\ }

- 23 -

数据结构实验指导书

}

void enqueue(BitTNode *t) {if (front!=(rear+1)%M) { rear=(rear+1)%M; que[rear]=t; }

}/*enqueue*/

BitTNode * delqueue()

{ if(front==rear)return NULL; { front=(front+1)%M; return (que[front]); }

}/*delqueue*/

/* 按层次遍历二叉树t */

void levorder(BiTree t) { BitTNode *p; if(t!=NULL) { enqueue(t);

while (front!=rear) { p=delqueue();

printf(\

if(p->lchild!=NULL) enqueue(p->lchild); if(p->rchild!=NULL) enqueue(p->rchild); } }

}/* levorder */ main()

{BitTNode *root; root=creat();

printf(\按先序遍历次序生成的二叉树\ printf(\前序遍历二叉树\ preorder(root);

printf(\中序遍历二叉树\ inorder(root);

printf(\后序遍历二叉树\ postorder(root);

printf(\层次顺序遍历二叉树\ levorder(root); }

2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法

#include #define MaxSize 100 typedef char ElemType; typedef struct node

- 24 -

数据结构实验指导书

{

ElemType data;

struct node *left,*right; } BTree;

BTree * createbt( ) { BTree *q; struct node1 *s[30]; int j,i,x; printf(\建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\\n\\n\ printf(\ scanf(\ while(i != 0 && x != '$') { q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/ q->data = x; q->left = NULL; q->right = NULL; s[i] = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，对应的结点是根结点*/ { j = i / 2; /*求双亲结点的编号j*/ if(i % 2 == 0)

s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/

else

s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ }

printf(\ scanf(\

} return s[1]; /*返回根结点地址*/ }

void preorder(BTree *BT) /* 前序遍历二叉树t */

{ if(BT!=NULL)

{ printf(\ preorder(BT ->left);

preorder(BT ->right); } }

int BTreeDepth(BTree *BT) {

int leftdep,rightdep; if (BT==NULL) return(0); else { leftdep=BTreeDepth(BT->left); rightdep=BTreeDepth(BT->right); if (leftdep>rightdep) return(leftdep+1); else return(rightdep+1);

- 25 -

数据结构实验指导书

} }

int nodecount(BTree *BT) {

if (BT==NULL) return(0); else return(nodecount(BT->left)+nodecount(BT->right)+1); }

int leafcount(BTree *BT) {

if (BT==NULL) return(0);

else if (BT->left==NULL && BT->right==NULL) return(1); else return(leafcount(BT->left)+leafcount(BT->right)); }

int notleafcount(BTree *BT) {

if (BT==NULL) return(0);

else if (BT->left==NULL && BT->right==NULL) return(0); else return(notleafcount(BT->left)+notleafcount(BT->right)+1); }

int onesoncount(BTree *BT) {

if (BT==NULL) return(0);

else if ((BT->left==NULL && BT->right!=NULL) ||

(BT->left!=NULL && BT->right==NULL))

return(onesoncount(BT->left)+onesoncount(BT->right)+1); else return(onesoncount(BT->left)+onesoncount(BT->right)); }

int twosoncount(BTree *BT) {

if (BT==NULL) return(0);

else if (BT->left==NULL || BT->right==NULL) return(twosoncount(BT->left)+twosoncount(BT->right)); else if (BT->left!=NULL && BT->right!=NULL) return(twosoncount(BT->left)+twosoncount(BT->right)+1); }

- 26 -

数据结构实验指导书

main() {

BTree *B;

B=creatree();

printf(\按先序遍历次序生成的二叉树\preorder(B);

printf(\二叉树深度:%d\\n\ printf(\总结点个数:%d\\n\ printf(\叶子结点个数:%d\\n\

printf(\非叶子结点个数:%d\\n\ printf(\具有双孩子结点个数:%d\\n\ printf(\具有单孩子结点个数:%d\\n\ }

三、注意事项

1、 遍历的思想。 思考题

1、用非遍历算法如何实现？

实验七 查找与排序

一、实验目的

1、掌握查找的不同方法，并能用高级语言实现查找算法。

2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。

3、掌握二叉排序树的生成、插入、删除、输出运算。 4、掌握常用的排序方法，并能用高级语言实现排序算法。

5、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。 6、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验内容

1、顺序表的顺序查找

#include

#define KEYTYPE int #define MAXSIZE 100 typedef struct { KEYTYPE key; }SSELEMENT;

typedef struct

{ SSELEMENT r[MAXSIZE]; int len; }SSTABLE;

int seq_search(KEYTYPE k, SSTABLE *st) {/*顺序表上查找元素*/

- 27 -

数据结构实验指导书

int j;

j = st->len; /*顺序表元素个数*/

st->r[0].key = k; /*st->r[0]单元作为监视哨*/ while(st->r[j].key != k) j--; /*顺序表从后向前查找*/

return j; /*j=0, 找不到；j<>0 找到*/ }

main( )

{ SSTABLE a; int i, j, k;

printf(\请输入顺序表元素(整型量)，用空格分开，-99为结束标志 ：\j = 0; k = 1; i = 0; scanf(\while (i != -99)

{ j++; a.r[k].key = i; k++; scanf(\输入顺序表元素*/ a.len = j;

printf(\顺序表元素列表显示 ：\for (i = 1; i<=a.len; i++) printf(\printf(\

printf(\输入待查元素关键字 : \scanf(\

k = seq_search(i, &a);

if (k == 0) printf(\表中待查元素不存在\\n\\n\

else printf(\表中待查元素存在,为第%d个元素\\n\，k ); }

2、有序顺序表的二分查找的递归算法

#include

#define KEYTYPE int #define MAXSIZE 100 typedef struct { KEYTYPE key; }SSELEMENT;

typedef struct

{ SSELEMENT r[MAXSIZE]; int len; }SSTABLE;

int search_bin(KEYTYPE k, int low, int high) { /*有序表上二分法查找,递归算法*/ int mid; mid = -1;

if(low <= high) /*low 表示当前表中第1个元素所在下标*/ /*high表示当前表中最后一个元素所在下标*/ {

mid = (low +high)/2; /*mid表示当前表中中间一个元素所在下标*/ if(a.r[mid].key < k)

mid = search_bin(k, mid + 1,high); /*二分法递归查找*/

- 28 -

数据结构实验指导书

else if(a.r[mid].key > k)

mid = search_bin(k,low,high - 1);

}

return mid; /*mid = -1 查找不成功；mid!=-1 查找成功*/ }

main( )

{ SSTABLE a; int i, j, k;

printf(\请输入有序表元素，元素为整型量（从小到大输入），用空格分开，

-99为结束标志 ：\

j = 0; k = 1; i = 0; scanf(\while (i != -99)

{ j++; a.r[k].key = i; k++; scanf(\输入有序表元素*/ a.len = j;

printf(\有序表元素列表显示 ：\for (i = 1; i<=a.len; i++) printf(\printf(\

printf(\输入待查元素关键字 : \scanf(\

k = search_bin(i, 1, a.len);

if (k == -1) printf(\表中待查元素不存在\\n\\n\

else printf(\表中待查元素存在,为第%d个元素\\n\，k); }

3、排序综合练习

#include #define KEYTYPE int #define MAXSIZE 100 int createList(RECNODE *r) { int j, k;

printf(\输入待排序数据(整数，以空格隔开，0 结束) : \k = 0; scanf(\

while(j != 0) { k++; r[k].key = j; scanf(\ return k; }

frontdisplayList(RECNODE *r, int n) {int i;

printf(\排序前 : \

for (i = 0; i < n; i++) printf(\ printf(\}

reardisplayList(RECNODE *r, int n) {int i;

printf(\排序后 : \

- 29 -

数据结构实验指导书

for (i = 0; i < n; i++) printf(\ printf(\}

void insertsort(RECNODE *r, int n) {/*直接插入排序*/ int i,j; for(i = 2; i <= n; i++) { r[0] = r[i];

j = i - 1; /*r[0]是监视哨，j表示当前已排好序列的长度*/

while(r[0].key < r[j].key) /*确定插入位置*/ {r[j + 1] = r[j]; j--;} r[j + 1] = r[0]; /*元素插入*/ } }

void bublesort(RECNODE *r, int n) {/*简单交换排序:冒泡排序*/ int i, j; RECNODE temp; for(i = 1; i < n; i++) for(j = n - 1; j >= i; j--) if(r[j + 1].key < r[j].key) {temp = r[j + 1]; r[j + 1] = r[j]; r[j] = temp;} }

int partition(RECNODE *r, int *low, int *high)

{/*一趟快速排序,返回i,产生了两个独立的待排子序列*/ int i, j; RECNODE temp; i = *low; j = *high; temp = r[i]; /*枢轴记录保存在temp变量中*/ do

{ while((r[j].key >= temp.key) && (i < j))

j--; /*j指针记录和枢轴记录比较*/

if(i < j) { r[i] = r[j]; i++;} while((r[i].key <= temp.key) && (i < j))

i++; /*i指针记录和枢轴记录比较*/

if(i < j) { r[j] = r[i]; j--;} } while(i != j); r[i] = temp; /*枢轴记录的排序位置确定在i*/ return i; }

void quicksort(RECNODE *r, int start, int end) {/*快速排序*/ int i; if(start < end) { i = partition(r, &start, &end);

/*一趟快速排序,返回i,产生了两个独立的待排子序列*/

- 30 -

数据结构实验指导书

}

void selesort(RECNODE *r, int n) {/*简单选择排序*/ int i,j,k; RECNODE temp; for(i = 1; i < n; i++) { k = i; /*k:最小关键字的初始位置*/ for(j = i + 1; j <= n; j++) if(r[j].key < r[k].key) k = j; /*k:跟踪记录当前最小关键字的位置*/ if(k != i) /*最小关键字元素和待排序列的第一个元素交换*/ {temp = r[i]; r[i] = r[k]; r[k] = temp;} } }

void sift(RECNODE *r, int i, int m)

{/*i是根结点编号,m是以i结点为根的子树中最后一个结点的编号*/ int j; RECNODE temp; temp = r[i]; j = 2 * i; /*j为i根结点的左孩子*/ while(j <= m) {if(j < m && (r[j].key < r[j + 1].key)) j++; /*当i结点有左右孩子时,j取关键字大的孩子结点编号*/ if(temp.key < r[j].key) /*按堆定义调整,并向下一层筛选调整 */ { r[i] = r[j]; i = j; j = 2 * i;} else break; /*筛选调整完成,跳出循环 */ } r[i] = temp; }

void heapsort(RECNODE *r, int n)

{/*堆排序: n为r表中记录数,从r[1]开始放起*/ int i; RECNODE temp; for(i = n/2; i >= 1; i--) sift(r, i, n); /*将无序序列建成大堆*/ for(i = n; i >= 2; i--) {temp = r[1]; /*堆顶及堆尾元素交换*/ r[1] = r[i]; r[i] = temp; sift(r,1,i - 1);

/*交换后,从第一个元素开始调整为大堆,每次记录个数少一个*/

} }

quicksort(r, start, i - 1);

/*对两个独立的待排子序列分别递归调用快速排序算法*/

quicksort(r, i + 1,end);}

- 31 -

数据结构实验指导书

void merge(RECNODE *r, int low, int m, int high)

{ /*两相邻的有序表(一个从low到m;另一个从m+1到high)*/

/*合并为一个有序表(从low到high)*/

RECNODE r1[MAXSIZE]; /*合并时用的缓冲向量*/ int i, j, k; i = low; j = m + 1; k = 0; while(i <= m && j <= high) /*两相邻的有序表合并*/ if(r[i].key <= r[j].key) {r1[k] = r[i]; i++; k++;} else {r1[k] = r[j]; j++; k++;} while(i <= m) /*有序表剩余部分处理*/ {r1[k] = r[i]; i++; k++;} while(j <= high) //有序表剩余部分处理 {r1[k] = r[j]; j++; k++;} for(i = low, k = 0; i <= high; i++, k++)/*缓冲向量r1复制到原来的r中*/ r[i] = r1[k]; }

void merge_one(RECNODE *r, int lenth, int n) {/*二路归并中的\一趟归并\算法*/ int i = 0; while(i + 2 * lenth - 1 < n) {merge(r, i, i + lenth - 1, i + 2 * lenth - 1);/*两子序列长度相等的*/ i = i + 2 * lenth;} /*情况下调用merge*/ if(i + lenth - 1 < n - 1) merge(r, i, i + lenth - 1, n - 1); /*序列中的余留部分处理*/ }

void mergesort(RECNODE *r, int n) {/*二路归并排序算法*/ int lenth = 1; /*有序子序列长度初始值 = 1*/ while(lenth < n) {merge_one(r, lenth, n); /*调用\一趟归并\的算法*/ lenth = 2 * lenth;} /*有序子序列长度加倍*/ }

void main() { RECNODE a[MAXSIZE]; int len, b, j, k; int loop = 1; while (loop) { printf(\排序综合练习\\n\\n\ printf(\退出\\n\ printf(\直接插入排序\\n\ printf(\简单交换(冒泡)排序\\n\

- 32 -

数据结构实验指导书

printf(\快速排序\\n\printf(\简单选择排序\\n\printf(\堆排序\\n\

printf(\二路归并排序\\n\printf(\请选择项号 ： \scanf(\printf(\

if(b >= 0 && b <= 6) switch(b) { case 0: loop = 0; break; case 1: len = createList(a); frontdisplayList(a,len); insertsort(a,len); reardisplayList(a,len); break; case 2: len = createList(a); frontdisplayList(a,len); bublesort(a, len); reardisplayList(a,len); break; case 3: len = createList(a); frontdisplayList(a,len); quicksort(a, 1, len); reardisplayList(a,len); break; case 4: len = createList(a); frontdisplayList(a,len); selesort(a, len); reardisplayList(a,len); break; case 5: len = createList(a); frontdisplayList(a,len); heapsort(a, len); reardisplayList(a,len); break; case 6:

printf(\输入待排序数据(整数，以空格隔开，0 结束) : \k = 0; scanf(\

while(j != 0) { k++; a[k-1].key = j; scanf(\ len = k;

printf(\排序前 : \

for (j = 0; j < len; j++) printf(\ printf(\ mergesort(a, len);

printf(\排序后 : \

for (j = 0; j < len; j++) printf(\ printf(\ break; }

- 33 -

数据结构实验指导书

printf(\结束此练习吗? (0 -- 结束 1 -- 继续) : \ scanf(\ printf(\ }

}

三、注意事项

1、查找时mid的变化。

2、一趟快速排序如何产生了两个独立的待排子序列。 3、堆排序中如何生成堆顶元素。

思考题

1、在用拉链法解决冲突的散列表上如何插入元素？

- 34 -

本文来源：https://www.bwwdw.com/article/56bx.html