数据结构上机实验题目

第一次上机：

1．书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现；

2．习P18 2.21 2.22；

3．习P18 2.25 2.26； （或要求将结果置于A表中）

4．习P18 2.29 2.30；(选做题)

5．习P19 2.38；

第二次上机：

1．完成第一次上机题；

2．书P45 ADT Stack 基本操作9个：用顺序存储结构实现；

3．书P59 ADT Queue 基本操作9个：用链式存储结构实现；

4．习P26 3.32；

第三次上机：

1．完成第一、二次上机题；

2．表达式求解；

3．八皇后问题；(选做题*)

第四次上机：

1．完成第一、二、三次上机题；

2．三元组（稀疏矩阵）转置（1、2）；

3．迷宫求解；(选做题)

4．随机队列模拟；(选做题)

第五次上机：

1．书P121 ADT BinaryTree 基本操作20个：用二叉链表存储结构实现；

2．非递归实现二叉树的先序、中序、后序遍历算法；

3．习P42 6.42；

4．习P43 6.45 6.48；(选做题)

5．习P43 6.49；

第六次上机：

1．实现10个字符的Huffman编码；

2．习P44 6.62；

3．习P44 6.63；(选做题)

4．习P44 6.64；(选做题)

5．完成第五次上机题；

第七次上机：

1．书P156 ADT Graph 基本操作13个：用邻接矩阵存储结构实现；

2．实现深度优先搜索算法；

3．实现广度优先搜索算法；

4．实现求解关键路径、最短路径算法；(选做题)

第八次上机：

1．实现插入、交换、选择、归并等简单排序算法；

2．实现快速排序算法；

3．实现堆排序算法；

4．实现基数排序算法；(选做题)

第二篇：数据结构上机实验十(十一

数据结构上机实验

本课程实验中已知的预定义常量和类型如下：

#define  TRUE  1

#define  FALSE  0

#define  OK  1

#define  ERROR  0

#define  INFEASIBLE  -1

#define  OVERFLOW  -2

typedef  int  Status；

实验一顺序表(一)

一、  实验目的

掌握顺序表的定义、存储结构及其基本操作。

二、  实验内容

已知：线性表的动态分配顺序存储结构为

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef  struct{

int  *elem；

int  length；

int  listsize；

}SqList；

在主程序中调用如下函数 实现构造线性表，在线性表中插入数值，最后输出线性表。

1. 编写函数，Status  InitList(SqList  *L) 实现构造一个空的线性表，若构造成功则返回OK，否则返回ERROR。

2. 编写函数，Status  ListInsert(SqList  *L , int i , int e) 实现在线性表L中第i个位置之前插入新的数据元素e，L的长度加1。若插入成功返回OK，否则返回ERROR。

（提示：i的合法值为：i>=1&&i<=L—>length+1）

3. 编写函数，void  ListPrint（SqList  *L）实现将线性表中的元素依次输出到屏幕上。

4．编写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-4中的任一个数字）：

输入  1：InitList

2：ListInsert

3：ListPrint

4：Exit

实验二  顺序表（二）

一、  实验目的

掌握顺序表的定义、存储结构及其基本操作。

二、  实验内容

在实验一的基础上，继续完成如下实验内容。

1.编写函数，Status  ListDelete(Splist *L ，int i ，int *e)，实现删除L的第i个数据元素，并用e返回其值，L的长度减1。删除成功返回OK（1），否则返回ERROR（0）。

（提示：i的合法值为：i>=1&&i<=L—>length）

2.编写函数 Status GetElem（SqList *L，int  i，int *e）,实现用e将线性表中第i个数据元素返回。若返回成功则函数返回OK（1），否则返回ERROR（0）。（提示：i的合法值为：i>=1&&i<=L—>length）

3．编写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-6中的任一个数字）：

输入1： InitList

2： ListInsert

3： ListPrint

4： ListDelete

5： GetElem

6： Exit

实验三顺序表（三）

一、实验目的

掌握顺序表的定义、存储结构及其基本操作。

二、实验内容

在实验二的基础上，继续完成如下实验内容。

在main函数中分别调用initList和ListInsert函数生成2个按值非递减有序的线性表La和Lb，然后再调用MergeList函数完成将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。最后输出LC。

1．编写函数，void  MergeList（SqList *La, SqList *Lb，SqList  *Lc）。（参考教材P21）

2．编写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-7中的任一个数字）：

输入1：InitList

2：ListInsert

3：ListPrint

4：ListDelete

5：GetElem

6：Merge

7：Exit

实验四单链表（一）

一、实验目的

掌握单链表的定义、存储结构及其基本操作。

二、实验内容 

   已知线性表的单链表存储结构为

typedef  struct  LNode{

int  data；

sturct  LNode  *next；

}LNode ，*LinkList

在主程序中调用如下函数 实现单链表的建立，在单链表中中插入结点，最后输出单链表。

1. 编写函数，void CreateList(LinkList  *L，int n)  动态生成一个单链表。（L为单链表的头指针，它指向表中的第一个结点。）

2. 编写函数，Status  ListInsert(LinkList  L , int i , int e) 实现在单链表L中第i个位置之前插入新的数据元素e。若插入成功返回OK，否则返回ERROR。

3. 编写函数，void  ListPrint（LinkList  L）实现将单链表的元素依次输出到屏幕上。

4．编写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-4中的任一个数字）：

输入  1：CreateList

2：ListInsert

3：ListPrint

4：Exit

实验五单链表（二）

一、实验目的

掌握单链表的定义、存储结构及其基本操作。

二、实验内容 

   在实验四的基础上，继续完成如下实验内容，在已存在的单链表中删除结点，将2个有序链表合并成一个有序链表。

1. 编写函数，void  ListDelete(LinkList  L，int i，int * e)  在单链表L中删除第i个元素，并由e返回其值。若删除成功返回OK（1），否则返回ERROR（0）。

2. 编写函数，void  Merge（LinkList  La，LinkList  Lb，LinkList  *Lc），完成已知两个按值非递减有序排列的单链表La和Lb，归并La和Lb得到一个新的单链表Lc，Lc的元素也按值非递减有序排列。（参考教材P31）

3．改写int Menu（），输出菜单项

请选择你要进行的操作（请输入1-6中的任一个数字）：

输入  1：CreateList

2：ListInsert

3：ListPrint

4：ListDelete

5：Merge

6：Exit

实验六栈（一）

一、实验目的

掌握栈的定义、栈的顺序存储结构及其基本操作。

二、实验内容 

   已知栈的顺序存储表示

#define  STACK_INIT_SIZE  100

#define  STACKINCREMENT  10

typedef  struct

{int  *base;

 int  *top;

 int  stacksize;

}SqStack;

在主程序中调用如下函数实现栈的初始化，在栈中插入数值，最后输出栈中元素。

1. 编写函数，Status  InitStack(SqStack  *S) ，构造一个空栈，成功返回OK，否则返回ERROR。

2. 编写函数，Status  Push（SqStack  *S，int e），在栈顶中插入元素e，成功返回OK，否则返回ERROR。

4. 编写函数，void  StackPrint（SqStack  S），实现在屏幕上输出栈中的元素。

5. 编写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-5中的任一个数字）：

输入  1：InitStack

2：Push

3：StackPrint

4：Exit

实验七栈（二）

一、实验目的
掌握栈的定义、栈的顺序存储结构及其基本操作。
二、实验内容 
       在实验六的基础上，继续完成如下实验内容，

1. 编写函数，Status  Gettop（SqStack  S，int  *e），实现若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR。
2. 编写函数，Status  Pop（SqStack  *S， int* e），实现若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR。
3. 编写函数，Status  Matching（char exp[ ]），实现判断S栈中所存储的表达式中的两种括号：圆括号和方括号是否匹配。如果匹配，返回OK，否则返回ERROR。（参考教材P49）
4. 改写函数，int  Menu（），输出菜单项
请选择你要进行的操作（请输入1-7中的任一个数字）：
输入  1：InitStack
         2：Push
         3：StackPrint
         4：Gettop
         5：Pop
         6：Matching
         7：Exit

实验八队列

一、实验目的

掌握队列的定义、队列的链式存储结构及其基本操作。

二、实验内容 

已知队列的链式存储表示

typedef  struct  QNode

{int  data；

 struct  QNode  *next；

 }QNode，*QueuePtr；

typedef struct

{ QueuePtr  front;

  QueuePtr  rear;  

}LinkQueue；

1. 编写函数，Status  InitQueue（LinkQueue  *Q），构造一个空队列，成功返回OK，否则返回ERROR。

2. 编写函数，Status  DestroyQueue（LinkQueue  *Q），实现销毁队列Q，成功返回OK，否则返回ERROR。

3. 编写函数，Status  EnQueue（LinkQueue *Q，int e），实现插入元素e为Q的队尾元素，成功返回OK，否则返回ERROR。

4. 编写函数，Status  DeQueue（LinkQueue *Q，int *e），实现若队列不空，则删除Q的队头元素，用e返回其值。删除成功返回OK，否则返回ERROR。

5. 编写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-5中的任一个数字）：

输入  1：InitQueue

2：DestroyQueue

3：EnQueue

4：DeQueue

5：Exit

实验九  数组

一、实验目的

掌握稀疏矩阵的三元组顺序表存储表示及其基本操作。

二、实验内容

已知稀疏矩阵三元组顺序存储表示为

#define MAXSIZE  1000

typedef struct

{int  i,j；

Int e

}Triple；

typedef struct

{

Triple data[MAZSIZE+1]；

int mu，nu，tu；

}TSMatrix

1．编写函数，Status  AssignSMatrix（TSMatrix  *M），实现输入非零元生成一个稀疏矩阵。稀疏矩阵如下所示。

­

2．编写函数，void  PrintSMatrix（TSMatrix  M）,实现将稀疏矩阵输出在屏幕上，输出的样式如下：

3．编写函数，Status TransposeSMatrix（TSMatrix M ，TSMatrix *T），实现采用三元组表存储表示，求稀疏矩阵M的转置矩阵T，在main中输出T。

4．编写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-4中的任一个数字）：

输入         1：AssignSMatrix

2：PrintSMatrix

3：TransposeSMatrix

4：Exit

实验十  查找

一、实验目的

掌握静态查找表的顺序存储结构及其查找方法。

二、实验内容 

   已知静态查找表的顺序存储结构为

typedef  int  KeyType;

typedef struct

{Keytype  key

}ElemType；

typedef  struct

{  ElemType  *elem；

   int  length；

}SSTable；

1. 编写函数，Status Creat_ST(SSTable *ST)，实现构造一个顺序查找表。（查找表的长度在函数中由用户输入，然后根据用户输入的长度申请存储空间，然后逐个输入数据元素生成顺序查找表。）

提示：查找表中０号单元留空。

2. 编写函数，void  Print_ST(SSTable  ST）, 实现将顺序表ST中元素依次输出在屏幕上

3. 编写函数，int  Search_Seq (SSTable  ST ，KeyType  key）, 实现在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。

4. 编写函数，int  Search_Bin(SSTable ST , KeyType  key)，实现在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。

5. 改写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-5中的任一个数字）：

输入  1： Creat_ST

         2： Print_ST

         3： Search_Seq

         4： Search_Bin

         5： Exit

实验十一  排序

一、实验目的

掌握顺序表的排序方法及基本操作。

二、实验内容 

   已知顺序表的存储结构为

#define MAXSIZE 100

typedef  int  KeyType;

typedef struct

{Keytype  key

}RedType；

typedef  struct

{  RedType  r[MAXSIZE+1];

   int  length；

}SqList；

1. 编写函数，Status Creat_SL(SqList  *L)，实现逐个输入数据元素生成顺序表。

提示：顺序表中０号单元留空。

2. 编写函数，void  Print_SL(SqList  L）, 实现将顺序表L中元素依次输出在屏幕上

3. 编写函数，void  InsertSort (SqList  *L ), 实现对顺序表L做直接插入排序。

4. 编写函数，void  BInsertSort(SqList *L )，实现对顺序表L做折半插入排序。

5. 编写函数，void  SelectSort(SqList *L)，实现对顺序表L做简单选择排序。

6. 改写函数，int  Menu（），输出菜单项

请选择你要进行的操作（请输入1-6中的任一个数字）：

输入  1： Creat_SL

         2： Print_SL

     3.   InsertSort

         4： BInsertSort

         5： SelectSort

         6： Exit