数据结构实验习题

实验一 线性表

一、 实验目的

1. 掌握在Borland C 3.1的集成环境中调试程序的基本方法。 2. 掌握线性表的插入和删除操作在顺序存储结构上的实现。

3. 掌握线性表的建立、插入、删除、打印和查找操作在链式存储结构上的实现。 4. 理解一元多项式的求和操作在链式存储结构上的实现。

二、 实验内容

1. 线性表的插入和删除操作在顺序存储结构上的实现。其中函数insertsqllist的功能是在顺序线性表中第i个元素之前插入一个元素，函数deletesqlist的功能是删除顺序线性表中第i个元素。 #define m 1000 #include \

typedef int datatype;

typedef struct{datatype a[m]; int n;} sqlist; void insertsqlist (sqlist &list, int i, datatype x) {

int j;

if(list.n+1>m) printf(\

else if(i<1||i>list.n+1) printf(\else {

for(j=list.n-1;j>=i-1; j--) list.a[j+1]=list.a[j];

/* 以上循环语句的功能是将从第i个位置开始的元素均向后移动一个位置 */ list.a[i-1]=x; list.n=list.n+1; }

}

void deletesqlist(sqlist &list, int i, datatype *y) {

int j;

if(i<1||i>list.n) printf(\else {

*y=list.a[i-1]; list.n=list.n-1;

for(j=i;j<=list.n-1; j++) list.a[j-1]=list.a[j]; } }

main( ) {

datatype i,y;

sqlist list={{1,2,3,4},4}; /* 初始化线性表list中有4个元素 */ for(i=0; i

for(i=0; i

- 1 -

for(i=0; i

}

2. 线性表的建立、插入、删除、打印和查找操作在链式存储结构上的实现。其中函数createlklist的功能是利用从尾部插入的方法建立一个有n个结点的单链表，函数printlklist的功能是从单链表的头部开始顺序打印单链表，函数locatelklist的功能是在单链表查找指定的结点并将指向该结点的指针作为函数值返回，函数insertlklist的功能是在单链表中值为y的结点之前插入一个值为x的新结点，函数deletelklist的功能是在单链表中删除值为x的结点。 #include \#include \#define n 10

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void createlklist(lklist *&head ) {

int i; lklist *p,*q; for (i=1;i<=n;i++) {

p=(lklist *)malloc(sizeof(lklist)); scanf(\ if(i==1)head=q=p;else {q->next=p;q=p;} } }

void printlklist(lklist *head) {

lklist *p=head;

while(p!=0){ printf(\ printf(\

}

lklist *locatelklist(lklist *head,datatype x) {

lklist *p=head;

while(p!=0) {if(p->data==x) return(p); else p=p->next;} return(0);

}

void insertlklist(lklist *&head, datatype x, datatype y) {

lklist *r,*p,*q;

r=(lklist *)malloc(sizeof(lklist)); r->data=x; if (head==0) printf(\

else if (head->data==y){r->next=head; head=r;} else {

for(q=head, p=head->next; p!=0; q=p, p=p->next) if (p->data==y) break; if (p!=0){q->next=r; r->next=p;} else printf(\} }

- 2 -

void deletelklist(lklist *&head, datatype x)

{

lklist *p,*q;

if(head==0) printf(\

else if(head->data==x) {p=head; head=head->next; free(p); } else {

for(q=head, p=head->next;p!=0; q=p, p=p->next) if (p->data==x) break;

if(p!=0){q->next=p->next; free(p);}else printf(\ } }

main( ) {

lklist *head=0,*p;

createlklist(head); printlklist(head); p=locatelklist(head,2);

if (p!=0) printf(\ %d\\n\else printf(“not found\\n”); insertlklist(head,100,3); printlklist(head); deletelklist(head,2); printlklist(head); }

3. 一元多项式的求和操作在链式存储结构上的实现。其中函数createlklist是利用从尾部插入结点的方法建立链式结构表示一元多项式，函数createitem的功能是生成结果多项式中的一个结点并将之链接到结果多项式链表中，函数printlklist的功能是从单链表头部开始顺序打印单链表中的结点元素，函数addmutiploy的功能是计算两个一元多项式的和。 #include \#include \#define n 4

struct node{int exp; float coef; struct node *next;}; void createlklist(struct node *&head ) {

int i; struct node *p,*q; for (i=1;i<=n;i++)

{

p=(struct node *)malloc(sizeof(struct node )); scanf(\ if(i==1)head=q=p;else {q->next=p;q=p;} }

}

void createitem(struct node *&pc,float coef,int exp) {

struct node *p;

p=(struct node *)malloc(sizeof(struct node)); p->next=0; p->coef=coef; p->exp=exp; pc->next=p; pc=p; }

void printlklist(struct node *head) {

- 3 -

struct node *p=head;

while(p!=0){ printf(\

printf(\}

void addmutiploy(struct node *pah,struct node *pbh,struct node *&pch) {

struct node *pa=pah,*pb=pbh,*pc=0; float x;

pc=pch=(struct node *)malloc(sizeof(struct node)); /* 为头指针pch申请头结点 */ while(pa!=0 && pb!=0) {

if(pa->exp==pb->exp)

{x=pa->coef+pb->coef; if(x!=0)createitem(pc,x,pa->exp);pa=pa->next; pb=pb->next;} else if(pa->exp>pb->exp){createitem(pc,pa->coef,pa->exp); pa=pa->next;} else if(pa->expexp){createitem(pc,pb->coef,pb->exp); pb=pb->next;} }

while (pa!=0) {createitem(pc,pa->coef,pa->exp); pa=pa->next;} while (pb!=0) {createitem(pc,pb->coef,pb->exp); pb=pb->next;} pc=pch; pch=pch->next; free(pc); /* 释放头指针pch中的头结点 */ }

main( )

{

struct node *pa=0,*pb=0,*pc=0; createlklist(pa); printlklist(pa); createlklist(pb); printlklist(pb);

addmutiploy(pa,pb,pc);printlklist(pc); }

- 4 -

实验二 栈和队列

一、 实验目的

1． 掌握栈的入栈和出栈操作在顺序存储结构上的实现。 2． 掌握栈的入栈和出栈操作在链式存储结构上的实现。

3． 掌握队列的入队列和出队列操作在顺序存储结构上的实现。 4． 掌握队列的入队列和出队列操作在链式存储结构上的实现。

二、 实验内容

1． 栈的入栈和出栈操作在顺序存储结构上的实现。其中函数pushsqstack的功能是实现入栈操作，函数popsqstack的功能是实现出栈操作。 #include \#define m 100

typedef int datatype;

typedef struct{datatype s[m]; int top;}sqstack; void pushsqstack(sqstack &stack, datatype x) {

if (stack.top==m-1) printf(\ else { stack.top=stack.top+1; stack.s[stack.top]=x; } }

void popsqstack(sqstack &stack, datatype *y) {

if (stack.top== -1) printf(\ else { *y=stack.s[stack.top]; stack.top=stack.top-1; }

}

main( ) {

int y; sqstack stack={{1,2,3,4,5},4}; /* 初始化stack栈中的元素及当前栈顶指针 */ pushsqstack(stack,100); pushsqstack(stack,200); popsqstack(stack,&y); printf(\ popsqstack(stack,&y); printf(\ popsqstack(stack,&y); printf(\

}

2． 入栈和出栈操作在链式存储结构上的实现。其中函数pushlkstack的功能是实现链栈的入栈操作，函数poplkstack的功能是实现链栈的出栈操作。 #include \#include \#define n 10

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lkstack; void pushlkstack(lkstack *&top, datatype x) {

lkstack *p;

p=(lkstack *)malloc(sizeof(lkstack)); p->data=x; p->next=top; top=p; }

- 5 -

void poplkstack(lkstack *&top,datatype *y) {

lkstack *p;

if (top==0) printf(\

else{p=top;*y=p->data; top=p->next; free(p);}

}

main( ) {

int i,x,y; lkstack *head=0;

for(i=1; i<=n; i++) {scanf(“%d”,&x); pushlkstack(head,x);} for(i=1; i<=n; i++) {poplkstack(head,&y); printf(\

}

3． 入队列和出队列操作在顺序存储结构上的实现。其中函数insertsqcyqueue的功能是实现顺序循环队列的入队列操作，函数deletesqcyqueue的功能是实现顺序循环队列的出队列操作。 #include \typedef int datatype; #define m 100

#define n 10

typedef struct {int rear,front; datatype q[m];}sqcyqueue; void insertsqcyqueue(sqcyqueue &queue, datatype x)

{

if ((queue.rear+1)%m==queue.front) printf(\ else { queue.rear=(queue.rear+1)%m;queue.q[queue.rear]=x; } }

void deletesqcyqueue(sqcyqueue &queue, datatype *y) {

if (queue.front==queue.rear) printf(\

else {queue.front=(queue.front+1)%m;*y=queue.q[queue.front]; } }

main( ) {

sqcyqueue queue; queue.front=queue.rear=0; int i,x,y;

for(i=1; i<=n; i++) {scanf(“%d”,&x); insertsqcyqueue(queue,i);} for(i=1; i<=n; i++) {deletesqcyqueue(queue,&y);printf(\

}

4． 链式队列的入队列和出队列操作。其中函数insertlkqueue的功能是完成链式队列的入队列操作，函数deletelkqueue的功能是完成链式队列的出队列操作。 #include \#include \#define n 10

typedef int datatype;

typedef struct node{datatype data; struct node *next;} lkqueue;

void insertlkqueue(lkqueue *&front,lkqueue *&rear,datatype x) {

lkqueue *p;

p=(lkqueue *) malloc(sizeof(lkqueue)); p->data=x; p->next=0;

- 6 -

if(rear==0) front=rear=p; else {rear->next=p; rear=p;} }

void deletelkqueue(lkqueue *&front,lkqueue *&rear,datatype *y) {

lkqueue *p;

if(front==0) printf(\

else { p=front; front=front->next; *y=p->data; free(p); if(front==0) rear=front; } }

main( ) {

int i,x,y; lkqueue *front=0,*rear=0;

for(i=1;i<=n;i++) {scanf(“%d”,&x); insertlkqueue(front,rear,x);} for(i=1;i<=n;i++) {deletelkqueue(front,rear,&y); printf(\}

- 7 -

实验三 字符串和数组

一、 实验目标

1． 掌握求字符串长度、插入字符串、删除字符串、求主串的子串和模式匹配等操作在顺序存储结构的实现。 2． 理解基于映射的字符串匹配算法在顺序存储结构上的实现。 3． 理解求稀疏矩阵的转置矩阵算法在三元组表上的实现。

二、 实验内容

1. 求字符串长度、插入字符串、删除字符串、求主串的子串和模式匹配等操作在顺序存储结构的实现。其中函数lenstring的功能是实现求字符串长度，函数insertstring的功能是实现在第一个字符串中第start个位置的后面插入第二个字符串，函数deletestring的功能是实现删除字符串中从第start个位置开始的count个字符，函数substring的功能是实现将第一个字符串从start位置开始的count个字符复制到第二个字符串，函数matchstring的功能是实现简单的模式匹配算法（查找子串在主串中第一次出现的位置）。 #include \#include “string.h”

#define stringmaxlen 127 long lenstring (char s[ ]) {

int n=0; char *p=s;

while(*p!=?\\0?) {p++; n++;} return(n); }

void insertstring(char s[ ],long start,char t[ ]) {

long i, len1=strlen(s), len2=strlen(t);

if (start<0 || start>len1) printf(\

else if (len1+len2>=stringmaxlen) printf(\else {

for(i=len1-1;i>=start; i--) s[i+len2]=s[i]; for(i=0;i<=len2-1; i++) s[start+i]=t[i];

s[len1+len2]=?\\0?; }

}

void deletestring(char s[ ], long start, long count) {

long i,j,length=strlen(s); char *p,*q;

if (start<1||start>length) printf(\ else if (start+count-1>length) printf(\ {

i=start+count-1; j=start-1; p=s+i; q=s+j; while (*p!='\\0'){*q=*p; q++; p++;} *q='\\0'; } }

- 8 -

void substring(char s[ ], long start, long count, char t[ ])

{

long i,j,length=strlen(s);

if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i

long matchstring(char t[ ], char p[ ]) {

long i,j,k ,len1=strlen(t),len2=strlen(p); for(i=0; i<=len1-len2; i++)

{

for(k=i, j=0;j

return(0);

}

main( ) {

char s[ ]=\ printf(\ insertstring(s,8,t); printf(\ deletestring(s,1,3); printf(\

substring(s,1,4,t); printf(\

if (matchstring(s,\else printf(\

}

2. 基于映射的字符串匹配算法在顺序存储结构上的实现。其中函数rkindex的功能是在主串t中查找出子串p的所有位置。 #define n 7 #define pp 193 #define d 3

void rkindex(char p[],char t[]) {

long i,j,k=0,x,y,z;

for(i=1,x=1;i<=m-1;i++) x=(x*d) % pp; for(i=0,y=0;i<=m-1;i++) y=(y*d+p[i]) % pp; for(i=0,z=0;i<=m-1;i++) z=(z*d+t[i]) % pp; for(i=0;i<=n-m;i++,k=i) {

if (y==z) {for(j=0;j<=m-1;j++,k++) if (p[j]!=t[k]) break; if (j==m) printf(\ if(i

}

main( ){char p[]=\}

- 9 -

3. 稀疏矩阵的转置矩阵算法在三元组表上的实现。其中函数translatematrix的功能是实现将稀疏矩阵a转化为

稀疏矩阵b。 #include \typedef int datatype; #define m 100

struct triple{int i; int j; datatype v;};

struct sparsematrix{int mu; int nu; int tu; struct triple data[m];}; void translatematrix(struct sparsematrix a, struct sparsematrix &b) {

int p,q=0,col;

b.mu=a.nu; b.nu=a.mu; b.tu=a.tu;

if (b.tu!=0) for(col=0; col

if (a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;q=q+1;} }

main( ) {

int i;

struct sparsematrix a={4,4,6,{{0,0,20},{0,2,8},{0,3,10},{1,2,30},{2,3,16},{3,0,-9}}},b; translatematrix(a,b);

for(i=0;i

- 10 -

实验四 树

一、 实验目标

1． 掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历算法在链式存储结构上实现。

2． 掌握利用遍历二叉树的递归思想实现建立二叉树、复制二叉树、交换二叉树和求二叉树中叶子结点数目等

算法。

3． 理解建立中序线索二叉树和遍历中序线索二叉树算法。

二、 实验内容

1． 建立二叉树、遍历二叉树、统计二叉树中叶子结点数目、交换二叉树的左右子树、复制二叉树操作运算在链式存储结构上实现。其中函数createbitree的功能是利用前序遍历二叉树的算法思想实现建立一棵二叉树，函数preorder、inorder、postorder和levelorder的功能分别是实现前序遍历、中序遍历、后序遍历和层次遍历二叉树，函数swapbiree的功能是实现交换二叉树中所有结点左右子树，函数copybitree的功能是实现复制一棵二叉树，函数countleaf的功能是实现统计二叉树中叶子结点数目。 #include \#include \#define m 100

typedef char datatype;

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; void visitnode(bitree *bt) {

printf(\}

void createbitree(bitree *&bt)

{

char ch; scanf(\ if(ch=='#') {bt=0; return;}

bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); }

void preorder(bitree *bt) {

if(bt!=0) { visitnode(bt); preorder(bt->lchild); preorder(bt->rchild);} }

void inorder(bitree *bt) {

if(bt!=0) { inorder(bt->lchild);visitnode(bt); inorder(bt->rchild);} }

void postorder(bitree *bt) {

if(bt!=0) { postorder(bt->lchild);postorder(bt->rchild); visitnode(bt); } }

void levelorder(bitree *bt)

{

struct {int front,rear; bitree *q[m];}queue; bitree *p=bt;

- 11 -

queue.rear=queue.front=0;

if(bt!=0) {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p;}

while (!(queue.front==queue.rear)) {

queue.front=(queue.front+1)%m; p=queue.q[queue.front]; visitnode(p);

if(p->lchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->lchild;}; if(p->rchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->rchild;}; }

}

void countleaf(bitree *bt,int &count) {

if(bt==0) return;

if(bt->lchild==0 && bt->rchild==0) count++; if(bt->lchild!=0) countleaf(bt->lchild,count); if(bt->rchild!=0) countleaf(bt->rchild,count); }

void swapbitree(bitree *bt) {

bitree *p;

if(bt==0) return;

swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; }

void copybitree(bitree *bt1,bitree *&bt2) {

if (bt1==0) {bt2=0; return;}

bt2=(bitree *)malloc(sizeof(bitree)); bt2->data=bt1->data;

copybitree(bt1->lchild,bt2->lchild); copybitree(bt1->rchild,bt2->rchild); }

main( ) {

bitree *bt=0,*bt2=0; int count=0;

createbitree(bt); printf(\ preorder(bt); printf(\ inorder(bt); printf(\ postorder(bt); printf(\ levelorder(bt);printf(\

countleaf(bt,count); printf(\ swapbitree(bt); preorder(bt); printf(\ copybitree(bt,bt2); preorder(bt2);printf(\

}

2． 建立中序线索二叉树和遍历中序线索二叉树的算法。其中函数createbitree的功能是实现建立一棵二叉树，函数createthreadbitree的功能是实现根据已知一棵二叉树建立一棵线索二叉树，函数inthread的功能是实现对以p为根指针的二叉树进行中序线索化，函数inorderthreadbitree的功能是实现中序遍历线索二叉树。 #include \#include \

- 12 -

typedef char datatype;

typedef struct node {datatype data; struct node *lchild,*rchild;int ltag,rtag;} threadbitree; threadbitree *pre; /* 指针变量pre始终指向刚刚被访问过的结点，是一个全局变量 */ void createbitree(threadbitree *&bt) {

char ch; scanf(\ if(ch=='#') {bt=0; return;}

bt=(threadbitree*)malloc(sizeof(threadbitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); }

void inthread(threadbitree *p) {

if(p!=0) {

inthread(p->lchild);

if (p->lchild==0) {p->ltag=1; p->lchild=pre;} /* 建立前驱线索 */

if (pre->rchild==0) {pre->rtag=1; pre->rchild=p;} /* 建立后继线索 */ pre=p; inthread(p->rchild); } }

void createthreadbitree(threadbitree *&head, threadbitree *bt) {

head=(threadbitree *)malloc(sizeof(threadbitree)); head->ltag=0; head->rtag=1; head->rchild=head; if (bt==0) {head->lchild=head; head->ltag=1; return;} head->lchild=bt; pre=head; inthread(bt);

pre->rchild=head; pre->rtag=1; head->rchild=pre; head->rtag=1; /* 最后一个结点线索化 */ }

void inorderthreadbitree(threadbitree *head) {

threadbitree *p=head->lchild;

while (p!=head) {

while (p->ltag==0) p=p->lchild; printf(“%c\\t”,p->data);

while (p->rtag==1 && p->rchild!=head){p=p->rchild; printf(“%c\\t”,p->data);} p=p->rchild; }

}

main( ) {

threadbitree *bt=0,*head=0; createbitree(bt);

createthreadbitree(head,bt); inorderthreadbitree(head); }

- 13 -

实验五 图

一、 实验目标

1． 掌握建立无向图（有向图）的邻接矩阵和邻接表算法。 2． 掌握无向图的深度优先遍历和广度优先遍历算法。 3． 理解连通图的最小生成树算法（普里姆算法）。 4． 理解有向无环图的拓扑排序算法。

二、 实验内容

1. 图的深度优先遍历在链式存储结构（邻接表）上的实现。其中函数createadjlist的功能是实现建立邻接表，函数dfs的功能是实现图的深度优先遍历算法。 #include \#define m 100 #include \#define n 6 #define e 6

int visited[m];

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void createadjlist(glinkheadnode g[ ]) {

int i,j,k; glinklistnode *p;

for(i=0;i

scanf(\

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p;

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; }

}

void dfs(glinkheadnode g[ ], int v0) {

glinklistnode *p;

printf(\

while(p!=0){ if(visited[p->adjvertex]==0)dfs(g,p->adjvertex); p=p->nextarc; }

}

main( ) {

glinkheadnode g[m]; createadjlist(g); dfs(g,0); }

2. 图的广度优先遍历在顺序存储结构（邻接矩阵）上的实现。其中函数creatematrix的功能是实现建立邻接矩阵，函数bfs的功能是实现图的广度优先遍历。 #include \

- 14 -

#define m 100 #define n 6

#define e 6 int visited[m];

typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; void createadjmatrix(gadjmatrix &g) {

int i,j,k;

for(i=0; i

for(i=0; i

for (k=0;k

void bfs(gadjmatrix g, int v0)

{

struct {int front; int rear; int q[m];}queue; int i,j; printf(\ queue.front=queue.rear=0;

queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=v0; while(queue.front!=queue.rear)

{

queue.front=(queue.front+1)%m; i=queue.q[queue.front]; for(j=0;j

{

printf(\

queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=j; } }

}

main( ) {

gadjmatrix g; createadjmatrix(g); bfs(g,0);

}

3. 连通图的最小生成树算法（普里姆算法）在顺序存储结构上的实现。函数prim的功能是实现从编号为v0顶点开始构造最小生成树。 #include \#define max 32767 #define n 6

void prim(int matrix[n][n],int v0) {

int i,j,k,min,lowcost[n],closet[n]; for(i=0; i<=n-1;i++)

if (i!=v0){lowcost[i]=matrix[v0][i];closet[i]=v0;} else lowcost[i]=0; for(i=1;i<=n-1;i++) {

for(min=max,j=0;j<=n-1;j++)

if (min>lowcost[j]&&lowcost[j]!=0) {min=lowcost[j];k=j;}

- 15 -

printf(\

for(j=0;j<=n-1;j++) if(matrix[k][j]

}

main( ) {

int matrix[n][n]={{max,6,1,5,max,max},{6,max,5,max,3,max},{1,5,max,max,6,4}, {5,max,max,max,max,2},{max,3,6,max,max,6},{max,max,4,2,6,max}}; prim(matrix,5); }

4. 在链式存储结构上实现有向无环图的拓扑排序算法。其中函数createadjlist的功能是实现建立有向图，函数topsort的功能是实现拓补排序。 #include \#include \#define m 100 #define n 7

#define e 8

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void createadjlist(glinkheadnode g[ ]) {

int i,j,k; glinklistnode *p;

for(i=0;i

scanf(\

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; } }

void toposort(glinkheadnode g[ ]) {

int i,v,w,sum=0, indegree[n]; struct {int s[n];int top;} stack; glinklistnode *p;

for (i=0; i

for (i=0; inextarc) indegree[p->adjvertex]++; for(i=0,stack.top= -1; i

printf(\

v=stack.s[stack.top]; stack.top=stack.top-1; p=g[v].firstarc; while (p!=0) {

w=p->adjvertex;indegree[w]=indegree[w]-1;

- 16 -

if (indegree[w]==0) {stack.top=stack.top+1; stack.s[stack.top]=w;} p=p->nextarc;

} }

if(sum

main( ) {

glinkheadnode g[m]; createadjlist(g); toposort(g); }

- 17 -

实验六 排序

一、 实验目标

1. 掌握插入排序在顺序存储结构上的实现。 2. 掌握交换排序在顺序存储结构上的实现。 3. 掌握选择排序在顺序存储结构上的实现。 4. 掌握归并排序在顺序存储结构上的实现。 5. 理解基数排序在链式存储结构上的实现。

二、 实验内容

1. 插入排序在顺序存储结构上的实现。其中函数straightinsertsort的功能是实现直接插入排序，函数biinsertsort的功能是实现折半插入排序，函数shellsort的功能是实现希尔排序，库函数random的功能是产生一个随机整数且该随机数的取值范围在0到num-1，其中num是其形式参数。 #include \#include “stdlib.h” typedef int datatype;

#define m 10

struct record {int key;datatype others;}; void straightinsertsort(struct record r[ ],int n) {

int i,j; struct record temp; for(i=1;i<=n-1;i++)

{for(temp=r[i],j=i-1; j>=0; j--) if(temp.key

void biinsertsort(struct record r[ ],int n) {

int i,j,low,mid,high; struct record temp; for(i=1;i<=n-1;i++) {

low=0; high=i-1;

while(low<=high){mid=(low+high)/2;if(r[i].key>r[mid].key)low=mid+1; else high=mid-1;}

for(temp=r[i],j=i-1; j>=low; j--) r[j+1]=r[j]; r[low]=temp; }

}

void shellsort(struct record r[ ], int n) {

int i,j,h; struct record temp;

for(h=n/2;h>=1;h=h/2) for(j=h;j<=n-1;j++) {

for(temp=r[j], i=j-h; i>=0; i=i-h) if (r[i].key>temp.key) r[i+h]=r[i];else break; r[i+h]=temp; } }

- 18 -

main( )

{

struct record r[m]; int i;

for( i=0; i<=m-1; i++) r[i].key=random(100); straightinsertsort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); biinsertsort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); shellsort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); }

2. 交换排序在顺序存储结构上的实现。其中函数bubblesort的功能是实现冒泡排序，函数betterbubblesort的功能是实现在冒泡排序的基础上提前结束排序，函数quickpass的功能是实现一趟快速排序，函数quicksort的功能是实现快速排序。 #include \#include “stdlib.h” typedef int datatype;

#define m 10

struct record {int key;datatype others;}; void bubblesort(struct record r[ ],int n) {

int i,j; struct record temp;

for (i=0; i<=n-2; i++) for (j=0;j<=n-i-2;j++) if(r[j].key>r[j+1].key) {temp=r[j];r[j]=r[j+1];r[j+1]=temp;} }

void betterbubblesort(struct record r[ ],int n) {

int i,j,flag; struct record temp; for (i=0; i<=n-2; i++) {

for (flag=0,j=0;j<=n-i-2;j++) if(r[j].key>r[j+1].key) {temp=r[j];r[j]=r[j+1];r[j+1]=temp; flag=1;} if (flag==0) break; }

}

void quickpass(struct record r[], int s, int t, int &i) {

int j=t; struct record x=r[s]; i=s; while(i

while (ix.key) j=j-1; if (i

- 19 -

void quicksort(struct record r[ ], int s, int t) {

int k;

if (s

main( ) {

struct record r[m]; int i;

for( i=0; i<=m-1; i++) r[i].key=random(100); bubblesort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); betterbubblesort(r,0,m-1);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); quicksort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”);

}

3. 选择排序在顺序存储结构上的实现。其中函数simpleselectsort的功能是实现简单选择排序，函数createheap的功能是实现“筛选”建堆，函数heapsort的功能是实现堆排序。 #include \#include “stdlib.h” typedef int datatype;

#define m 10

struct record {int key;datatype others;};

void simpleselectsort(struct record r[],int n) {

int i,j,k; struct record temp; for(i=0;i<=n-2;i++) {

for(k=i,j=i+1;j<=n-1;j++) if (r[j].key

}

void createheap(struct record r[ ],int k,int n) {

int i=k,j=2*i+1; struct record temp=r[i]; while (j<=n-1) {

if (jr[j+1].key) j=j+1; /* 如果条件成立则调整到右子树 */ if (temp.key<=r[j].key)break; else{r[i]=r[j]; i=j; j=2*i+1;} }

r[i]=temp; }

void heapsort(struct record r[ ],int n) {

- 20 -

int i; struct record temp;

for (i=n/2-1;i>=0;i--) createheap(r,i,n); /* 建初始堆 */ for (i=n-1;i>=1;i--)

{temp=r[0];r[0]=r[i];r[i]=temp; createheap(r,0,i);} }

main( ) {

struct record r[m]; int i;

for( i=0; i<=m-1; i++) r[i].key=random(100); simpleselectsort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); heapsort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”);

}

4. 归并排序在顺序存储结构上的实现。其中函数merge的功能是实现将两个有序的子文件合并成一个有序的子文件，函数mergesort的功能是实现归并排序。 #include \#include “stdlib.h”

typedef int datatype; #define m 10

struct record {int key;datatype others;};

void merge(struct record r[], int low,int mid,int high) {

int i=low,j=mid+1,k=low; struct record temp[m]; while (i<=mid && j<=high) {

if (r[i].key<=r[j].key){temp[k]=r[i]; i=i+1;} else {temp[k]=r[j]; j=j+1;} k=k+1; }

while(i<=mid){temp[k]=r[i]; i=i+1;k=k+1;} while(j<=high){temp[k]=r[j];j=j+1;k=k+1;} for (i=low;i<=high;i++) r[i]=temp[i];

}

void mergesort(struct record r[ ], int s, int t) {

if(s!=t){mergesort(r,s,(s+t)/2); mergesort(r,(s+t)/2+1,t); merge(r,s,(s+t)/2,t);} }

main( ) {

int i; struct record r[m];

for( i=0; i<=m-1; i++) r[i].key=random(100); mergesort(r,0,m-1);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); }

- 21 -

5. 基数排序在链式存储结构上的实现。其中函数radix的功能是实现对长度为3的整数序列进行排序，函数

createlklist是建立一个链式存储结构的待排序记录序列，库函数itoa的功能是将整型数据转化为字符型数据（第一个参数表示被转化的整型值，第二个参数存储经转化得到的字符串，第三个参数表示按何种进制进行转化，本算法中用10表示按十进制数进行转化）。 #include \#include \#define n 11

typedef struct node{int data; struct node *next;} lklist;

void createlklist(lklist *&head) {

int i,a[n]={312,290,180,653,358,432,865,264,451,526,239}; lklist *p,*q; for(i=0,head=0; i

p=(lklist *)malloc(sizeof(lklist)); p->data=a[i]; p->next=0; if(i==0) head=q=p; else {q->next=p; q=p;} } }

void radixsort(lklist *&head, int d) {

struct node *p,*q,*h[10],*t[10]; int i,j,x; char string[20]; for(i=d-1; i>=0; i--) {

for(j=0; j<=9; j++) h[j]=t[j]=0; for(p=head; p!=0; p=p->next) {

ltoa(p->data,string,10); x=string[i]-'0';

if(h[x]==0) h[x]=t[x]=p; else {t[x]->next=p; t[x]=p;}

}

for(j=0; h[j]==0; )j++; head=h[j]; q=t[j];

for(x=j+1; x<=9; x++) if(h[x]!=0) {q->next=h[x]; q=t[x];} q->next=0; }

}

main( ) {

lklist *head=0,*p; createlklist(head); radixsort(head,3);

for(p=head; p!=0; p=p->next) printf(\}

- 22 -

实验七 查找

一、 实验目标

1． 掌握顺序表的查找算法在顺序存储结构上的实现。

2． 掌握建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。 3． 掌握散列表的建立和查找算法在顺序存储结构上的实现。 4． 掌握散列表的建立和查找算法在链式存储结构上的实现。

二、 实验内容

1． 顺序表查找在顺序存储结构上的实现。其中函数sqsearch的功能是实现在顺序线性表中顺序查找关键字，函数bisearch的功能是实现在顺序线性表中折半查找关键字。 #include \#include “stdlib.h”

typedef int datatype; #define n 10

struct record {int key;datatype others;};

int sqsearch(struct record r[ ], int k) {

int i;

for(i=0; i<=n-1; i++) if (r[i].key==k) return(i+1); return(0); }

int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1; while(low<=high) {

mid=(low+high)/2;

if(r[mid].key==k) return(mid+1);

else if(r[mid].key>k) high=mid-1; else low=mid+1; } return(0);

}

main( ) {

int i; struct record r[n];

for (i=0;i

if (sqsearch(r,44)>0) printf(“44 found\\n”); else printf(“44 not found\\n”); if(bisearch(r,44)>0) printf(“44 found\\n”); else printf(“44 not found\\n”);

}

2． 建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。其中函数bstsearch的功能是实现利用递归方法在二叉排序树上查找指定结点，函数bstsearch1的功能是实现利用非递归方法在二叉排序树上查找指定结点，函数bstinsert的功能是实现在二叉排序树上插入结点，函数createbsttree的功能是实现建立一棵二叉排序树，函数inorder的功能是实现中序遍历二叉树。 #include \

- 23 -

#include \typedef int datatype;

#define n 10

typedef struct node{int key; struct node *lchild,*rchild;}bitree;

void inorder(bitree *bt) {

if (bt!=0) {inorder(bt->lchild); printf(“%d\\t”,bt->key); inorder(bt->rchild);} }

bitree *bstsearch(bitree *t, int key) {

if (t==0 || t->key==key) return(t);

else if (t->keyrchild,key)); else return(bstsearch(t->rchild,key)); }

bitree *bstsearch1(bitree *t, int key) {

bitree *p=t;

while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild; return(0); }

void bstinsert(bitree *&bt,int key)

{

if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }

void createbsttree(bitree *&bt)

{

int i;

for(i=1;i<=n;i++) bstinsert(bt,random(100)); }

main( ) {

bitree *bt=0;

createbsttree(bt);

inorder(bt); printf(“\\n”);

if(bstsearch(bt,44)!=0) printf(“found\\n”); else printf(“not found\\n”);

}

3． 建立散列表和在散列表中查找指定结点的算法在顺序存储结构的实现。其中函数createsqhash的功能是实现建立顺序存储结构的散列表，函数hashsqsearch的功能是实现在顺序存储结构上实现散列表查找。 #include \#define m 8 #define n 7 #define p 7

struct record {int key; int flag;}; int a[n]={7,9,16,23,30,32,34};

void createsqhash(struct record hashtable[]) {

- 24 -

int i,j,k;

for(k=0;k

for(k=0;k

j=i=a[k] % p; while(1)

if(hashtable[j].flag==0){hashtable[j].key=a[k];hashtable[j].flag=1;break;} else {j=(j+1)%m; if(j==i){printf(\ }

}

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k && hashtable[j].flag!=0 ) {j=(j+1)%m; if (i==j) return(-1);} if (hashtable[j].key==k) return(j); else return(-1); }

main( ) {

struct record hashtable[m]; int i;

createsqhash(hashtable);

for(i=0;i

4． 建立散列表和在散列表中查找指定结点的算法在链式存储结构的实现。其中函数createlkhash的功能是实现建立链式存储结构的散列表，函数hashlksearch的功能是实现在链式存储结构上实现散列表查找。 #include \#include \#define m 8 #define n 7 #define p 7

typedef struct node {int key; struct node *next;} lklist; int a[n]={7,9,16,23,30,32,34};

void createlkhash(lklist *hashtable[ ]) {

int i,k; lklist *s;

for(i=0;i

for(i=0;ikey=a[i];k=a[i] % p; s->next=hashtable[k]; hashtable[k]=s;} }

lklist *hashlksearch(lklist *hashtable[ ],int k) {

int i=k % p; lklist *s;

for(s=hashtable[i]->next; s!=0; s=s->next) if (s->key==k) return(s); return(0); } main( ) {

- 25 -

lklist *hashtable[m],*s; int i; createlkhash(hashtable);

for(i=0;inext) printf(“%d\\t”,s->key); printf(“\\n”);} if (hashlksearch(hashtable,16)!=0) printf(\}

- 26 -

lklist *hashtable[m],*s; int i; createlkhash(hashtable);

for(i=0;inext) printf(“%d\\t”,s->key); printf(“\\n”);} if (hashlksearch(hashtable,16)!=0) printf(\}

- 26 -

本文来源：https://www.bwwdw.com/article/09vo.html