《数据结构》实验指导书 - 图文

2012 《数据结构》实验指导书 王中国 编 南阳师范学院 2012-2-20

《数据结构》实验指导书

《数据结构》实验指导书 ........................................................................ 2 实验一 时间复杂度计算 .......................................................................... 3 实验二 顺序存储线性表操作 .................................................................. 4 实验三 链式存储线性表的操作 ............................................................ 10 实验四 顺序栈的基本操作 .................................................................... 14 实验五 顺序队列的基本操作 ................................................................ 17 实验六 数组、字符串的基本操作 ........................................................ 19 实验七 查找的基本操作 ........................................................................ 21 实验八 排序的基本操作（一） ............................................................ 25 实验九 排序的基本操作（二） ............................................................ 28

实验一 时间复杂度计算

一、

实验目的：

1. 掌握使用Turbo C2.0上机调试线性表的基本方法； 2. 熟练掌握C语言的指针和结构体相关知识点； 3. 理解数据结构的基本概念； 4. 掌握时间复杂度的计算方法。

二、 实验内容：

1. 熟悉实验用的C语言上机环境；

2. 计算程序中指定的语句的执行频率，计算时间复杂度。

三、 实验要求：

1. 编程实现对第一章绪论中的编程项目1、2、3、4个题目的时间复杂度运算； 2. 记录程序的运行结果，并结合程序进行分析；

3. 编写程序计算下列语句中“x++”的执行频率并将结果输出。

x++;

for(int i=1;i<=n;i++) x++; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) X++;

四、 实验学时：2学时

实验二 顺序存储线性表操作

一、

实验目的：

1. 掌握顺序表的基本概念；

2. 掌握顺序表的建立、遍历、插入和删除等方法； 3. 掌握顺序表的基本算法。

二、 实验内容：

1. 建立、遍历线性表；

2. 编写C程序完成线性表的插入和删除。

三、 实验要求：

1. 认真阅读、掌握和上机运行本实验的程序； 2. 记录程序的运行结果，并结合程序进行分析； 3. 参照示例程序，完成相应功能的C程序设计编写。

四、 五、

实验学时：2学时 实验步骤：

1． 实验准备：

(1)针对第二章课后编程项目的第1-4题，完成编程； (2)理解函数功能，并运行程序得到正确结果。

2． 拓展练习：阅读下列两个函数，写出该函数的功能，写出运行结果。 (1)程序如下：

#define m 100 typedef struct

{ int elem[m]; int len;}sqlist; void creatsqlist(sqlist *l)

{ int i; scanf(\

for(i=0;ilen;i++) scanf(\}

void ins(sqlist *l,int k) { int j;

for(j=l->len-1;j>=k;j--) { l->elem[j+1]=l->elem[j]; } l->elem[k]=99; l->len++; }

main()

{ int i; sqlist *l,L; l=&L; clrscr(); creatsqlist(l); for(i=0;ilen;i++) printf(\ printf(\ ins(l,2);

for(i=0;ilen;i++) printf(\} (2)程序如下：

typedef struct lnode

{ int data; struct lnode *next; }node,*nodeptr; nodeptr creat()

{ nodeptr l,p,q; int i ,n,e;

l=(nodeptr)malloc (sizeof(node)); q=l; q->next=0; scanf(\ for(i=1;i<=n;i++)

{ p=(nodeptr)malloc(sizeof(node)); scanf(\

p->data=e; q->next=p; q=p; }

q->next=0; return l; }

void out(nodeptr l)

{ nodeptr p; p=l->next;

while(p) {printf(\}

main()

{ nodeptr l; l=creat(); out(l); }

3． 实验内容：阅读、理解、调试下列程序，并得到正确执行结果。

/* 定义ElemType为int类型 */

/*顺序表存储空间的总分配量*/ #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 /* 顺序存储类型 */ typedef int ElemType; typedef struct

node{ int data[MAXSIZE]; /*存放线性表的数组*/

int length; /* length是顺序表的长度*/

}SeqList;

SeqList SeqListCreate(int a[10]) {

SeqList L; int i;

L.length=10;

for(i=0;i

void SeqListPrint(SeqList L) {

int i;

for(i=0;i

ElemType ListGet(SeqList L,int i) {

ElemType e; e=L.data[i];