《软件技术基础》实验指导

说明

每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。

1

实验一 线性表

一、 实验目的

1．熟悉线性表的顺序和链式存储结构 2．掌握线性表的基本运算

3．能够利用线性表的基本运算完成线性表应用的运算

二、 实验内容

1．设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）

2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。（文件夹：分解单链表）

实验二 栈和队列

一、 实验目的

1．熟悉栈和队列的顺序和链式存储结构 2．掌握栈和队列的基本运算

3．能够利用栈和队列的基本运算完成栈和队列应用的运算

二、 实验内容

1．设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：判字符串中心对称）

2．假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。（文件夹：循环队列）

实验三 串

一、 实验目的

1． 熟悉串的顺序存储结构 2． 掌握串的基本运算及应用

二、 实验内容

1．串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（文件夹：模式匹配）

2．若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法void SteDelete(char*S,int I,int m)，要求从S中删除从第i个字符开始的连续m个字符。

2

若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均删除。（文件夹：删除子串）

实验四 数组

一、 实验目的

1．熟悉数组的结构 2．掌握矩阵的压缩存储

3．能够对数组和矩阵的压缩存储进行运算

二、 实验内容

1. 若在矩阵Am×n中存在一个元素A[i][j]，其满足A[i][j]是第i行元素中最小值，且又

是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Am

（文件夹：找马鞍点） ×n ，设计算法求出矩阵中所有马鞍点。

2. A和B是两个n×n阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储

存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。（文件夹：对称矩阵相乘）

实验五 树

一、 实验目的

1．熟悉二叉树的链式存储结构

2．掌握二叉树的建立、深度优先递归遍历等算法 3．能够利用遍历算法实现一些应用

二、 实验内容

1．已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，

即结点的左子树变为结点的右子树，右子树变为左子树。（文件夹：交换左右子树） 2．采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。（文件夹：统计二叉树结点）

实验六 图

一、 实验目的

1．熟悉图的邻接矩阵和邻接表的存储结构 2．熟悉图的邻接矩阵和邻接表的建立算法 3．掌握图的遍历算法

二、 实验内容

1． 无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。（文件夹：无向图邻接矩阵）

3

A B D E F C G H 实验七 排序

一、 实验目的

1．熟悉各种内部排序算法

2．能够编写程序显示排序过程中各趟排序的结果 3．能够编写一些排序的算法

二、 实验内容

1． 采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序

的结果。（文件夹：希尔排序）

2． 编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序

的结果。（文件夹：双向起泡排序）

实验八 查找

一、 实验目的

1．熟悉线性表、二叉排序树和散列表的查找 2．能够编写一些查找的算法

二、 实验内容

1． 18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、

49、86、53，编写分块查找的算法进行查找。（文件夹：分块查找）

2． 编写一个判别给定的二叉树是否为二叉排序树的算法，设二叉树以二叉链表存储表示，

结点的数据域只存放正整数。（文件夹：判断二叉排序树）

附录：原代码

实验一：第1题（1） //顺序表逆置的程序代码 #include #include //顺序表结构类型定义 typedef char datatype; const int maxsize=1024;

4

typedef struct

{ datatype data[maxsize]; int last; }sequenlist;

void create(sequenlist*&); void print(sequenlist*); void invert(sequenlist*);

void main() { sequenlist*L; create(L);//建立顺序表 print(L);//输出顺序表 invert(L);//调用顺序表逆值的函数 print(L);//输出顺序表 }

//建立顺序表

void create(sequenlist*&L) { L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0; char ch; while((ch=getchar())!='*') { L->last++; L->data[L->last]=ch; } }

//输出顺序表

void print(sequenlist*L) { for(int i=1;i<=L->last;i++) printf(\ printf(\}

//顺序表逆置

实验一：第1题（2） //单链表逆置的程序代码 #include #include

//单链表结构类型定义 typedef char datatype;

5

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

void create(linklist*&); void print(linklist *); void invert(linklist*); void main() { linklist*head; create(head); print(head); invert(head);//调用单链表逆置的函数 print(head); }

//采用尾插法建立具有头结点的单链表 void create(linklist*&head) { char ch; linklist *s,*r; head=(linklist*)malloc(sizeof(linklist)); r=head; while((ch=getchar())!='*') { s=(linklist*)malloc(sizeof(linklist)); s->data=ch; r->next=s; r=s; } r->next=NULL; }

//输出单链表

void print(linklist *head) { linklist*p=head->next; while(p!=NULL) { printf(\ p=p->next; } printf(\}

//单链表逆置

6

实验一：第2题

//分解单链表的程序代码 #include #include //链表结构类型定义 typedef char datatype; typedef struct node { datatype data; struct node *next; }linklist;

void create(linklist*&);

void resolve(linklist*,linklist*,linklist*,linklist*); void insert(linklist*,linklist*); void print1(linklist*); void print2(linklist*); void main()

{ linklist *head,*letter,*digit,*other; create(head); print1(head);

letter=(linklist*)malloc(sizeof(linklist));//建立3个空循环链表 letter->next=letter;

digit=(linklist*)malloc(sizeof(linklist)); digit->next=digit;

other=(linklist*)malloc(sizeof(linklist)); other->next=other;

resolve(head,letter,digit,other);//调用分解单链表的函数 print2(letter);//输出循环链表 print2(digit); print2(other); }

//建立单链表

void create(linklist*&head) { datatype x; linklist *s,*r;

head=new linklist; r=head;

while((x=getchar())!='$') { s=(linklist*)malloc(sizeof(linklist)); s->data=x; r->next=s; r=s; }

r->next=NULL; }

7

//在循环链表中插入

void insert(linklist*h,linklist*p) { linklist *q=h;

while(q->next!=h) q=q->next; q->next=p; p->next=h; }

//输出单链表

void print1(linklist*head) { linklist *p=head->next; while(p!=NULL)

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

printf(\}

//输出循环链表

void print2(linklist*head) { linklist *p=head->next; while(p!=head) { printf(\ p=p->next; }

printf(\}

//按字母、数字、其它字符分解单链表

实验二：第1题

//判字符串中心对称的程序代码 #include #include #include //定义单链表结构类型 typedef char datatype; typedef struct node { datatype data; struct node *next; }linklist;

//定义顺序栈结构类型 const int maxsize=40;

8

typedef struct

{ datatype elements[maxsize]; int top; }stack;

void setnull(stack *&); int length(linklist*); void printlink(linklist*);

void create(linklist *&,datatype*); void push(stack*,datatype); datatype pop(stack*);

int symmetry(linklist*,stack*);//判字符串是否中心对称的函数声明

void main() { linklist *head;stack *s; datatype str[80]; gets(str); create(head,str); printlink(head); setnull(s); if(symmetry(head,s)) printf(\字符串\\\中心对称\\n\ else printf(\字符串\\\不是中心对称\\n\}

//栈初始化

void setnull(stack *&s) { s=(stack*)malloc(sizeof(stack)); s->top=-1; }

//求单链表长度

int length(linklist*head) { linklist *p=head->next; int n=0;

while(p!=NULL){ n++; p=p->next; } return n; }

//输出单链表

void printlink(linklist*head) { linklist *p=head->next; while(p!=NULL)

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

printf(\}

9

//建立具有头结点的单链表

void create(linklist *&head,datatype*str) { datatype *p=str; linklist *s,*r;

head=(linklist*)malloc(sizeof(linklist)); r=head;

while(*p!='\\0') { s=(linklist*)malloc(sizeof(linklist)); s->data=*p; r->next=s; r=s; p++; }

r->next=NULL; }

//顺序栈入栈

void push(stack*s,datatype e) { s->top++; s->elements[s->top]=e; }

//顺序栈出栈

datatype pop(stack*s) { datatype temp; s->top--; temp=s->elements[s->top+1]; return temp; }

//判字符串是否中心对称

实验二：第2题

//循环队列入队出队的程序代码 #include #include #include

//循环队列的结构类型定义 const int m=5;

typedef int datatype; typedef struct

10

{ datatype sequ[m]; int rear, quelen; }qu;

void setnull(qu*);

void enqueue(qu*, datatype); datatype *dequeue(qu*);

void main() { qu *sq;

datatype x, *p; int key;

sq=(qu*)malloc(sizeof(qu)); setnull(sq); do

{ printf(\ 2.Delete Queue -1.Quit:\ scanf(\ switch(key)

{ case 1: printf(\ enqueue(sq,x); break; case 2: p=dequeue(sq); if(p!=NULL) printf(\ break; case -1: exit(0); }

}while(1); }

//置空队

void setnull(qu *sq) { sq->rear=m-1; sq->quelen=0; }

//入队

//出队

实验三：第1题

//模式匹配的程序代码 #include #include #include

11

//顺序串的结构类型定义 #define maxsize 100 typedef struct { char str[maxsize]; int len; }seqstring;

int Index(seqstring*, seqstring*);

void main() { seqstring*S,*subS; S=(seqstring*)malloc(sizeof(seqstring)); subS=(seqstring*)malloc(sizeof(seqstring)); printf(\输入串：\ S->len=strlen(S->str); printf(\输入子串：\ subS->len=strlen(subS->str); if(Index(S,subS)>0) printf(\匹配成功！\\n\ else printf(\匹配失败！\\n\}

//顺序串的朴素模式匹配

实验三：第2题

//删除子串的程序代码 #include #include #include

//顺序串的结构类型定义 #define maxsize 100 typedef struct { char str[maxsize]; int len; }seqstring;

void strPut(seqstring*);

void strDelete(seqstring*,int,int); void main() { seqstring*S; int i,m;

12

S=(seqstring*)malloc(sizeof(seqstring)); printf(\输入串：\ S->len=strlen(S->str); strPut(S); printf(\删除的开始位置:\ printf(\删除的字符个数:\ strDelete(S,i,m); strPut(S); }

//输出串

void strPut(seqstring*S) { int i; for(i=0;ilen;i++) printf(\ printf(\}

//删除子串

实验四：第1题 //找马鞍点程序代码 #include #include //数组的结构类型定义 const int m=3; const int n=3; typedef struct{ int A[m+1][n+1]; int max[m+1],min[n+1]; }array;

void minmax(array*);

void main() { array*pa=(array*)malloc(sizeof(array)); int i, j;

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

scanf(\ minmax(pa); }

13

//找马鞍点

实验四：第2题

//对称矩阵相乘的程序代码 #include #include

//数组结构类型的定义.h const int n=3;

const int size=n*(n+1)/2; typedef int datatype; typedef struct{ datatype A[size],B[size],C[n][n]; }array;

void input(datatype[]); void output(datatype[][n]); void mult(array*);

void main() { array*pa; pa=(array*)malloc(sizeof(array)); printf(\以行为主序输入矩阵A的下三角:\\n\ input(pa->A);//以行为主序输入矩阵A的下三角 printf(\以行为主序输入矩阵B的下三角:\\n\ input(pa->B);//以行为主序输入矩阵B的下三角 mult(pa); output(pa->C);//输出矩阵C }

//对称矩阵的输入 void input(datatype x[]) { for(int i=0;i

//矩阵的输出

void output(datatype x[][n]) { for(int i=0;i

14

printf(\ printf(\ } }

//对称矩阵相乘

实验五：第1题

//交换左右子树的程序代码 #include #include

//二叉链表的结构类型定义 const int maxsize=1024; typedef char datatype; typedef struct node { datatype data; struct node *lchild,*rchild; }bitree;

bitree*creattree(); void preorder(bitree*); bitree*swap(bitree*);

void main() { bitree*pb; pb=creattree(); preorder(pb); printf(\ swap(pb); preorder(pb); printf(\}

//二叉树的建立 bitree*creattree() { char ch; bitree*Q[maxsize]; int front,rear; bitree*root,*s; root=NULL;

15

front=1;rear=0; printf(\按层次输入二叉树，虚结点输入'@'，以'#'结束输入：\\n\ while((ch=getchar())!='#') { s=NULL; if(ch!='@') { s=(bitree*)malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)front++; } } return root; }

//先序遍历按层次输出二叉树 void preorder(bitree*p) { if(p!=NULL) { printf(\ if(p->lchild!=NULL||p->rchild!=NULL) { printf(\ preorder(p->lchild); if(p->rchild!=NULL)printf(\ preorder(p->rchild); printf(\ } } }

//交换左右子树

16

实验五：第2题

//统计结点总数及叶子结点总数的程序代码 #include #include

//二叉链表的结构类型定义 const int maxsize=1024; typedef char datatype; typedef struct node { datatype data; struct node *lchild,*rchild; }bitree;

bitree*creattree(); void preorder(bitree*); int countnode(bitree*); int countleaf(bitree*);

void main() { bitree*root; int leafnum,nodenum; root=creattree(); printf(\删除子树之前的二叉树：\ preorder(root); printf(\

nodenum=countnode(root);

printf(\结点总数是：%d\\n\ leafnum=countleaf(root);

printf(\叶子结点总数是：%d\\n\}

//建立二叉树 bitree*creattree() { datatype ch; bitree*Q[maxsize]; int front,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf(\按层次输入结点值，虚结点输入'@'，以换行符结束：\ while((ch=getchar())!='\\n') { s=NULL; if(ch!='@') { s=(bitree*)malloc(sizeof(bitree)); s->data=ch;

17

s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)front++; } } return root; }

//先序遍历输出二叉树 void preorder(bitree*p) { if(p!=NULL) { printf(\ if(p->lchild!=NULL||p->rchild!=NULL) { printf(\ preorder(p->lchild); if(p->rchild!=NULL) printf(\ preorder(p->rchild); printf(\ } } }

//统计结点个数

//统计叶子结点个数

18

实验六：第1题

//无向图邻接矩阵搜索遍历的程序代码 #include

//图的邻接矩阵类型定义 const int n=8; const int e=10;

typedef char vextype; typedef int adjtype; typedef struct { vextype vexs[n]; adjtype arcs[n][n]; }graph;

graph*g=new graph; void creatgraph(); void dfsa(int); int visited[n];

void main() { creatgraph(); int i; while(1) { for(i=0;i

//建立无向图邻接矩阵 void creatgraph() { int i,j,k; char ch; printf(\输入8个顶点的字符数据信息:\\n\ for(i=0;ivexs[i]=ch; for(i=0;iarcs[i][j]=0; printf(\输入10条边的起、终点i,j:\\n\ for(k=0;karcs[i][j]=g->arcs[j][i]=1;

19

} }

//深度优先搜索遍历

实验七：第1题

//希尔排序的程序代码 #include

//顺序表结构类型定义 typedef int datatype; typedef struct{ int key; datatype data; }rectype;

const int N=10; const int D1=5;

void create(rectype[],int); void print(rectype[],int);

void shellsort(rectype[],int[]);

void main() {

rectype r[N+D1];//D1个元素存放监视哨，N个元素存放记录 int d[3]={5,3,1};//设置3趟的增量 create(r,N);//建立存放记录的顺序表 printf(\排序前的数据：\ print(r,N);//输出排序前的记录表 shellsort(r,d);//希尔排序 printf(\排序后的数据：\ print(r,N);//输出排序后的记录表 }

//建立顺序表

void create(rectype r[],int n) { printf(\输入10个整型数：\ for(int i=0;i

//输出顺序表

20

void print(rectype r[],int n) { for(int i=0;i

//希尔排序

实验七：第2题

//双向起泡排序的程序代码 #include #include #include

//顺序表结构类型定义 typedef int datatype; typedef struct{ int key; datatype data; }sequenlist;

void create(sequenlist[],int); void print(sequenlist[],int);

void dbubblesort(sequenlist[],int);

void main() { const int n=10; sequenlist r[n+1]; create(r,n); printf(\排序前的数据：\ print(r,n); dbubblesort(r,n); printf(\排序后的数据：\ print(r,n); }

//建立顺序表

void create(sequenlist r[],int n) { srand(time(0)); for(int i=1;i<=n;i++) r[i].key=rand()?; }

21

//输出顺序表

void print(sequenlist r[],int n) { for(int i=1;i<=n;i++) printf(\ printf(\}

//双向起泡排序

实验八：第1题

//分块查找的程序代码 #include //类型定义

typedef int keytype; typedef struct { keytype key; int low,high; }index;

typedef struct { keytype key; }record;

const int recN=18; const int idxN=3;

int blksearch(record[],index[],keytype,int); void main() { record r[recN]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53}; index idx[idxN]={{22,0,5},{48,6,11},{86,12,17}}; keytype key; int loc,i; printf(\待查找的记录关键字表：\\n\ for(i=0;i

22

//折半查找索引表，块内顺序查找

实验八：第2题

//判断二叉排序树的程序代码 #include #include #include

//二叉链表的结构类型定义 const int maxsize=1024; typedef int keytype; typedef struct node { keytype key; struct node *lchild,*rchild; }bitree;

bitree*creattree(); void preorder(bitree*); void inorder(bitree*);

void main() { bitree*pb; pb=creattree(); preorder(pb); printf(\ inorder(pb); printf(\是二叉排序树！\\n\}

//二叉树的建立 bitree*creattree() { keytype x; bitree*Q[maxsize]; int front,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf(\按层次输入二叉排序树的整型结点数据，0表示虚结点，-1表示结束：\\n\ scanf(\输入0表示虚结点，-1表示结束 while(x!=-1) {

23

s=NULL; if(x!=0) { s=(bitree*)malloc(sizeof(bitree)); s->key=x; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)front++; } scanf(\ } return root; }

//二叉树的输出

void preorder(bitree*p) { if(p!=NULL) { printf(\ if(p->lchild!=NULL||p->rchild!=NULL) { printf(\ preorder(p->lchild); if(p->rchild!=NULL) printf(\ preorder(p->rchild); printf(\ } } }

//判断二叉排序树

24

本文来源：https://www.bwwdw.com/article/8yp8.html