数据结构实验上机指导(5)

数据结构与算法实验指导书

{ C[k][0]=A[i][0];C[k][1]=A[i][1];C[k][2]=A[i][2]; k++;i++; }

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 -

数据结构与算法实验指导书

}

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(\

}

c

实验七 查找

一、实验目的

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

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

3、掌握二叉排序树的生成、插入、删除、输出运算。

二、实验内容

1、顺序表的顺序查找

#include

#define KEYTYPE int

- 22 -

数据结构与算法实验指导书

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

typedef struct

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

int seq_search(KEYTYPE k, SSTABLE *st) {/*顺序表上查找元素*/ 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;

- 23 -

数据结构与算法实验指导书

}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); /*二分法递归查找*/

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 #include

#define KEYTYPE int #define MAXSIZE 100 typedef struct node {

KEYTYPE key;

struct node *next; }CHAINHASH;

- 24 -

数据结构与算法实验指导书

void creat_chain_hash(CHAINHASH *HTC[])

{ /*建立开散列表*/ CHAINHASH *p;

int i, j;

scanf(\输入开散列表元素关键字值*/ while (i != -99) {

j = i % 13; /*散列函数： ADD(rec(key)) = key MOD 13*/ p = (CHAINHASH *) malloc(sizeof(CHAINHASH));

/*生成结点，挂入开散列表中*/

p->next = HTC[j]; p->key = i; HTC[j] = p;

scanf(\输入开散列表元素关键字值*/ }

void print_chain_hash(CHAINHASH *HTC[]) {/*显示开散列表 */ int i;

CHAINHASH *p;

for(i =0; i < 13; i++) {

if(HTC[i] == NULL) printf(\ else { p = HTC[i];

printf(\ while(p != NULL) {printf(\ printf(\ } } }

int search_chain_hash(CHAINHASH *HTC[], int k) {/*开散列表中查找元素*/ CHAINHASH *p; int j;

j = k % 13; /*散列函数： ADD(rec(key)) = key MOD 13*/ p = HTC[j];

if(p != NULL) /*开散列表中查找元素*/

{ while((p->key != k)&&(p->next != NULL)) p = p->next; if (p->key == k) return 1; /*查找成功，返回 1*/ else return 0; /*查找不成功，返回 0*/ }

else return 0; }

insert_chain_hash(CHAINHASH *HTC[], int i) {/*元素插入散列表中*/ CHAINHASH *p; int j;

j = i % 13; /*散列函数： ADD(rec(key)) = key MOD 13*/ p = (CHAINHASH *) malloc(sizeof(CHAINHASH));

/*生成结点，挂入开散列表中*/

- 25 -