数据结构实验报告

数

据 结 构 实 验 报 告 姓名:wangqiang 学号：*********

实验名称线性表的应用 1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现； 实 验 目 的 及 要 求 2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3. 掌握线性表的动态分配顺序存储结构的定义和基本实现； 4. 通过对本章实验帮助学生加深对C语言的使用（特别是函数参数调用、指针类型的应用和链表的建立等各种基本操作） 5. 要求用顺序表和链表分别实现约瑟夫问题； 6. 完成，严禁抄袭； 7. 上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。 8. 。 1线性表的应用

#include #include typedef struct node{ int value; struct node *next; }NODE;

NODE *createlink(int n){

NODE *head=NULL,*p=NULL,*q=NULL;

int i=1;

head=p=(struct node*)malloc(sizeof(struct node)); p->value=i; for(i=2;i<=n;i++){

q=(struct node*)malloc(sizeof(struct node)); if(q==0) return 0; p->next=q; p=q; p->value=i; }

p->next=head; return head; }

void jose(NODE *p,int n,int m){ int i,j,g=0; NODE *q=NULL; for(i=1;i<=n;i++){ for(j=1;jnext;} q=p->next; p->next=q->next; if(g%5==0)

{g++;printf(\"\\n\");} else g++;

printf(\"%3d:%3dout \ free(q); }

printf(\"\\n\");

p->next=NULL; }

int main( ){ int m=0; int n=0;

scanf(\"%d\ scanf(\"%d\ NODE *head=NULL; head=createlink(n); jose(head,n,m); return 0;

2栈和队列的应用

实验名称 栈和列队的应用 1. 熟练掌握栈和列队的结构，以及这两种数据结构的特点； 2. 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空时的判断条件和描述方法； 3. 熟练掌握链队列和循环列表的基本运算，特别注意队列满和队列空时的判断条件和描述方法。 4. 要求用栈实现表达式求值问题； 5. 完成，严禁抄袭； 6. 上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。 实 验 目 的 及 要 求 实 验 内 容 表达式求值的实现：输入一个包含正整数和圆括号的合法表达式，确定括号是否配对正确 1 括号的配对； #include\"stdio.h\" #include\"string.h\" #include\"stdlib.h\"

#define StackSize 100 //假定预分配的栈空间最多为100个元素 #define MaxLength 100 //最大的字符串长度

typedefint DataType; //假定栈元素的数据类型为整数 typedefstruct {

DataType data[StackSize];

int top; }SeqStack;

void Initial(SeqStack*S); int IsEmpty(SeqStack*S); int IsFull(SeqStack*S);

void Push(SeqStack*S, DataType x); DataType Pop(SeqStack*S); DataType Top(SeqStack*S);

void PrintMatchedPairs(char *expr); void main(void) {

char expr[MaxLength];

printf(\"请输入符号个数小于%d的表达式：\\n\",MaxLength);

gets(expr);

printf(\"括号对是：\\n\");

PrintMatchedPairs(expr);

return; }

//置栈空

void Initial(SeqStack*S) {

S-> top= -1; }

//判断栈是否空

int IsEmpty(SeqStack*S) {

return S-> top== -1; }

//判断栈是否满

int IsFull(SeqStack*S) {

return S-> top== StackSize-1; }

//进栈

void Push(SeqStack*S, DataType x) {

if(IsFull(S))

{

printf(\"栈上溢!\"); exit(1); }

S-> data[++ S-> top]= x;

return; }

//出栈

DataType Pop(SeqStack*S) {

if(IsEmpty(S)) {

printf(\"栈为空！\"); return -1; }

return S-> data[S-> top--];//栈顶指针加1后将x入栈 }

//取栈顶元素

DataType Top(SeqStack*S) {

if(IsEmpty(S)) {

printf(\"栈为空！\"); exit(1); }

return S-> data[S-> top]; }

//括号匹配

void PrintMatchedPairs(char *expr) {

SeqStack S;

int i , j , length= strlen(expr);

Initial(&S);

for(i= 1 ; i<= length ; i++) {

if(expr[i- 1]== '(') {

Push(&S,i); }

else if(expr[i- 1]== ')') {

j= Pop(&S); if(j== -1) {

printf(\"没有对应第%d个右括号的左括号\\n\", i); } else {

printf(\"%d %d\\n\",i,j); } } }

while(!IsEmpty(&S)) {

j= Pop(&S);

printf(\"没有对应第%d个左括号的右括号\\n\", j); } }

3数组的应用

实验名称数组的应用 实 验 目 的 及 要 求 实 验 内 容 1. 掌握数组的两种存储表示方法； 2. 掌握对特殊矩阵进行压缩存储时的下标变换公式； 3. 掌握稀疏矩阵的两种压缩存储方法的特点和适用范围。 4. 已知某一稀疏矩阵的三元顺序表，由其直接得到其转置矩阵的三元顺序表； 5. 完成，严禁抄袭； 6. 上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。 稀疏矩阵转置的实现:用三元组顺序表做存储结构，实现稀疏矩阵的转置。 #include #include

Sturct tuple3tp /*稀疏矩阵的建立和转置*/ { Int i,j; Int v; }

Sturct sparmattp{ Int mu, nu,tu;

Sturct tuple3tp data[31]; }

Struct sparmattp a,b; Void crt_sparmat() { Int i;

Printf(\"输入稀疏矩阵行值，列值，最大非零元个数：\"); Scanf(\"%d%d%d\For(\"i=1;i<=a.tu;i++){

Printf(\"输入行坐标，列坐标，非零元\"）;

Scanf(\"%d%d%d\} }

Void trans_sparmat() {

Int col,p,q; B.mu=a.nu; B.nu=a.mu; B.tu=a.tu;

If(b.tu！=0）{ Q=1;

For(col=1;col<=a.nu;col++)

For(p=1;p<=a.tu;p++) 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++; } } }

Out(struct sparmattp x) {

Int i,j,k,flag;

For(i=1;i<=x.mu;i++){ For(j=1;j<=x.nu;j++){ Flag=0;

For(k=1;k<=x.tu;k++){

If(((x.data[k].i)==i)&&((x.data[k].j)==j)){ Flag=1;

Printf(\"%5d\} }

If(flag==0)printf(\" 0\"); }

Printf(\"\\n\"); } }

Main( ) {

Printf(\"稀疏矩阵的建立与转置\\n\"); Crt_sparmat(); Trans_sparmat();

Printf(\"原矩阵为:\\n\");

Out(a);

Printf(\"转置矩阵为:\\n\"); Out(b); }

4数和二叉树的应用

实验名称树和二叉树的应用 实 验 目 的 及 要 求 1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； 2. 重点掌握二叉树的生成、遍历及求深度等算法； 3. 掌握哈夫曼树的含义及其应用； 4. 掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。 5. 上交实验报告。 6. 完成，严禁抄袭。 7. 实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。 实 验 内 容 二叉树采用二叉链表作存储结构，试编写程序实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目。 4. #include

#include #define maxsize 100 typedef char datatype;

typedef struct node /*二叉树结点类型*/ {

datatype data;

struct node *lchild,*rchild; } bitree;

bitree *Q[maxsize]; /*用于创建二叉树*/ bitree *CREATREE(); /*函数声明*/ int depth(bitree *); void print(bitree *); void print1(bitree *); void print3(bitree *); int main() /*主函数*/ {

bitree *Bitree; char ch; while(1) {

printf(\" @@@@@@@@@@@@@@@@本程序的功能是输出普通二叉树的深度@@@@@@@@@@@@@@@\\n\"); printf(\"

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@02-12-07 23:01@@@@@@\\n\");

Bitree = CREATREE(Bitree); /*生成一棵二叉树*/ printf(\"前序打印：\");

print(Bitree); /*打印二叉树*/ printf(\"\\n中序打印：\"); print2(Bitree); printf(\"\\n后序打印：\"); print3(Bitree);

printf(\"\\n此二叉树的深度为：\"); printf(\"%d\\n\

printf(\"Input 'q' to quit and 'c' run again:\"); do{

if((ch = getchar()) == 'q' || ch == 'Q') exit(0);

}while((ch!='C') && (ch!='c')); system(\"cls\"); } return 1; }

bitree *CREATREE()/*建立二叉树*/ {

char ch; int front,rear; bitree *root,*s; root = NULL; front = 1; rear = 0;

printf(\"请按完全二叉树的层次（不是完全二叉树的空结点用'@'补全）从左到右的顺序输入，\\n详细请参考help.doc.最后用'#'结束：\\n\");

ch = getchar(); /*按完全二叉树的层次输入，不是完全二叉树的空节点用’@‘补全，最后用’#‘结束*/ while(ch != '#') {

s = NULL;

if(ch !='@') /*节点不为空*/ {

s = malloc(sizeof(bitree)); if(!s) {

printf(\"内存分配失败!\\n\"); exit(0); } s->data = ch; s->lchild = NULL; s->rchild = NULL;

} rear++;

Q[rear] = s; /*Q[rear]指向新分配的节点，Q[front]指向上一个的节点*/ if(rear == 1)

root = s; /*S为根*/ else {

if(s && Q[front]) /*若S为孩子*/ if(rear%2 == 0)

Q[front]->lchild = s; /*S为左孩子*/ else

Q[front]->rchild = s; /*S为右孩子*/ if(rear%2 == 1) front++; }

ch = getchar(); }

return root; }

void print(bitree *t) /*先序形式输出二叉树*/ { if (t) {

printf(\" %c\ print(t->lchild); print(t->rchild); } else return; }

print2(bitree *t)/*中序递归遍历二叉树*/ { if(t) {

print2(t->lchild); printf(\" %c\ print2(t->rchild); } else

return; }

void print3(bitree *t) /*后序形式输出二叉树*/ { if (t) {

print3(t->lchild); print3(t->rchild); printf(\" %c\ } else

return; }

int depth(bitree *t) /*求二叉树深度的算法*/ {

int dep1, dep2;

if (t == NULL) return 0;/*空树*/ else {

dep1 = depth(t->lchild); /*遍历左子树*/ dep2 = depth(t->rchild); /*遍历右子树*/ if (dep1 > dep2) /*取深度大者*/ return (dep1 + 1); else

return (dep2 + 1); } }

5图的应用

实验名称 图的应用 实 验 目 的 及 要 求 实 验 内 容 1. 熟练掌握图的邻接矩阵和邻接表的存储方式； 2. 实现图的一些基本运算，特别是深度遍历和广度遍历； 3. 掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。 4.上交实验报告。 5.完成，严禁抄袭。 6.实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述， 算法描述，程序清单，测试结果，算法分析）。 1. 由给定的顶点和边的信息构造图的邻接矩阵存储； 2. 对该图进行深度优先搜索，输出搜索得到的结点序列； 3. 以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树。 #include #include #include

struct road{ int st; int ed; int w;}; road all[900];

int A[30];

int cmp(const void *a,const void *b) { return (*(road *)a).w - (*(road *)b).w;} int find(int x)

{ if (x != A[x]) A[x] = find(A[x]); return A[x];} int main()

{ int i,j,k,q,p,m,n,sum; char s,e;

while (scanf(\"%d\ { if (n == 0) break;

memset(A,0,sizeof(int)); for (i = 1;i <= n;i++) A[i] = i; m = 0; for (i = 1;i < n;i++)

{ scanf(\" %c%d\ while (p--) {

scanf(\" %c%d\

all[m].st = s - 'A';

all[m].ed = e - 'A'; all[m].w = q; m++; } }

qsort(all,m,sizeof(all[0]),cmp); k = 0;sum = 0; while (k < m) {

all[k].st = find(all[k].st); all[k].ed = find(all[k].ed); if (all[k].st != all[k].ed) {

sum += all[k].w; A[all[k].st] = all[k].ed; } k++; }

printf(\"%d\\n\ }

system(\"pause\"); return 0;

}

6查找表的应用

实验名称 数组的应用 实 验 目 的 及 要 求 实 验 内 容 1. 熟悉掌握静态查找表的构造方法和查找算法； 2. 熟练掌握二叉排序树的构造和查找方法； 3. 熟练掌握哈希表的构造和处理冲突的方法； 4. 上交实验报告。 5. 完成，严禁抄袭。 6. 实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。 1. 要求将二叉排序树的建立、插入、删除、显示等算法合并在一个综合程序中、用户可以通过菜单选择方式运行各种操作算法； 2. 一直哈希表的表为m，哈希函数为H(key)=key MOD p,用开放定址法（增量序列采用线性探测再散列）解决冲突，试编写构造哈希表的程序。 #include \"stdio.h\" #include \"stdlib.h\" #include \"string.h\" #define MAX_NAME_SIZE 100 #define STU_ID_SIZE 10 struct Stu {

char name[MAX_NAME_SIZE];//学生名字 char sex; //学生性别

char stu_id[STU_ID_SIZE]; //学生证号id };

class MyList { public: MyList();

bool AppendKey(char *name,int sex,char *stuid); //往链表中添加元素 void DeleteKey(char *stuid); //删除表中key的元素 bool FindKey(char *stuid); //判断表中是否含key的元素 void ShowList(); //显示表中的所有元素 ~MyList(); private:

struct LNode {

struct Stu stu; struct LNode *next; } *m_Head; //表头 };

//构造函数 MyList::MyList() {//初始化表头 m_Head = NULL; }

//析构函数 MyList::~MyList() {//释放申请的内存空间

struct LNode *pNode = m_Head; while(pNode) {

m_Head = m_Head->next; delete pNode; pNode = m_Head; } }

bool MyList::AppendKey(char *name,int sex,char *stuid) {

struct LNode *pNode; pNode = m_Head; while(pNode)//遍历链表 {

if(!strcmp(pNode->stu.stu_id,stuid))//先查找表中有无相同的值，如果有相同的就返回false

return false; pNode = pNode->next; }

//把新的节点插入表头 pNode = new struct LNode; pNode->next = m_Head;

strcpy(pNode->stu.name,name); pNode->stu.sex = sex;

strcpy(pNode->stu.stu_id,stuid); m_Head = pNode; return true; }

void MyList::DeleteKey(char *stuid) {

struct LNode *pNode,*pPrev; pNode = m_Head; pPrev = NULL;

while(pNode)//遍历整个表 {

if(!strcmp(pNode->stu.stu_id,stuid)) {

if(pPrev == NULL) {//要删除的是头节点

m_Head = m_Head->next; delete pNode; }else {//非头节点

pPrev->next = pNode->next; delete pNode; } break; }

pPrev = pNode; pNode = pNode->next;

} }

bool MyList::FindKey(char *stuid) {

struct LNode *pNode; pNode = m_Head; while(pNode)//遍历整个表 {

if(!strcmp(pNode->stu.stu_id,stuid))//找到值相同的元素，返回true return true; pNode = pNode->next; }

return false;// }

void MyList::ShowList() {

struct LNode *pNode; pNode = m_Head; while(pNode) {

printf(\"%s\\ pNode = pNode->next; }

printf(\"\\n\\n\"); }

void main() {

MyList list;

list.AppendKey(\"aaa\ list.DeleteKey(\"3106001771\"); }

7排序算法的应用

实验名称数组的应用 有如下数据： 成75 87 68 92 88 61 77 96 80 72 实 验 目 的 及 要 求 绩 姓名 王华 李燕 张萍 陈涛 刘丽 章强 孙军 朱彬 徐伟 曾亚 以成绩做关键字，试编写程序实现如下基本操作： 1. 用冒泡排序对上面数据按成绩非递减排列，并分析时空复杂度； 2. 用简单选择排序对上面数据按成绩非递减排列，并分析时空复杂度； 3. 用快速排序对上面数据按成绩非递减排列，并分析时空复杂度。 4. 上交实验报告。 5. 完成，严禁抄袭。 6. 实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。 有如下数据： 成绩 75 87 68 92 88 61 77 96 80 72 实 验 内 容 姓名 王华 李燕 张萍 陈涛 刘丽 章强 孙军 朱彬 徐伟 曾亚 以成绩做关键字，试编写程序实现如下基本操作： 7. 用冒泡排序对上面数据按成绩非递减排列，并分析时空复杂度； 8. 用简单选择排序对上面数据按成绩非递减排列，并分析时空复杂度； 9. 用快速排序对上面数据按成绩非递减排列，并分析时空复杂度。 #include #include #include

void shell_sort(int arr[],int size) {

int i,j,k,temp; for(i=size/2;i>0;i/=2) { for(j=i;jfor(k=j-i;k>=0&&temp}/* for(i=0;ivoid bubble_sort(int arr[],int size) { int i,j,k;

for(i=size-1;i>0;i=k) { for(j=0,k=0;jarr[j+1])

{ arr[j]^=arr[j+1]^=arr[j]^=arr[j+1]; k=j; } }

} /* for(i=0;ivoid insert_sort(int arr[],int size) {int i,j,temp; for(i=1;ifor(j=i-1;j>=0&&temp{ arr[j+1]=arr[j]; }

arr[j+1]=temp; }/* for(i=0;ivoid select_sort(int arr[],int size) { int i,j,min;

for(i=0;i{ arr[min]^=arr[i]^=arr[min]^=arr[i]; } } /*

for(i=0;ivoid main() {

longstart_select,end_select,start_insert,end_insert,start_bubble,end_bubble,start_shell,end_shell;

int select[15000],insert[15000],bubble[15000],shell[15000]; int i,j;

srand((int)time(0)); select[0]=rand()%25000+1; for(i=1;i<15000;i++)

{ select[i]=rand()%25000+1; for(j=0;jfor(i=0;i<15000;i++)

{ shell[i]=bubble[i]=insert[i]=select[i];}//printf(\"%d \ printf(\"下面是选择排序：\"); start_select=clock(); select_sort(select,15000); end_select=clock();

printf(\"\\n所用的时间是%ld毫秒\\n\printf(\"\\n下面是插入排序：\"); start_insert=clock(); insert_sort(insert,15000); end_insert=clock();

printf(\"\\n所用的时间是%ld毫秒\\n\printf(\"\\n下面是冒泡排序：\"); start_bubble=clock(); bubble_sort(bubble,15000); end_bubble=clock();

printf(\"\\n所用的时间是%ld毫秒\\n\ printf(\"\\n下面是希尔排序：\"); start_shell=clock(); shell_sort(shell,15000); end_shell=clock(); printf(\"\\n

所用的时间是%ld

毫秒\\n\