北京林业大学数据结构

2022-10-09

第一篇：北京林业大学数据结构

中国地质大学(武汉)数据结构报告

Practice Report for Data Structures and Algorithm Analysis

Data Structures Course Report

Candidate:

吴泽光

Student Number: 20121001873 Major :

Communication Engineering Supervisor :

Wu rangzhong

China University of Geosciences(Wuhan) Wuhan, Hubei 430074, P. R. China

October 18, 2012

China University of Geosciences, Faculty of Mechanics and Electronic Information

一、线性表(用链表实现):

1、目的：

通过程序的运用，使得线性表的插入、删除等功能更加容易实现，节约了时间和精力。

2、程序说明：

typedef struct LNode * LinkList; typedef int Status; struct LNode { int data; struct LNode * next; }; void Insert(LinkList &L,int i,int b); void Delete(LinkList &L,int i); int Length(LinkList &L); void Print_LinkList(LinkList &L); 插入函数：

void Insert(LinkList &L,int i,int x) { LinkList p, q; p=L; q=(LinkList)malloc(sizeof(LNode)); q->data=x; if(i==1) {

q->next=p; L=q; } else

定义结构体。插入函数。删除函数。输出长度。输出线性表内容。

} {

} while(--i>1) p=p->next; q->next=p->next;p->next=q;

3、运行过程：

二、堆栈和队列

1、目的：

通过程序的运用，使得队列的插入、删除等功能更加容易实现，节约了时间和精力。

2、程序说明：

struct My_Queue {

int Element[MaxLength]; int Length; int head; int rear; }; 定义结构体。 int Head_Queue(My_Queue &Que); 功能：返回队列头结点的值

参数：Que，引用类型，指向队列的头。

void Print_Queue(My_Queue &Que); 输出队列的内容。 void In_Queue(My_Queue &Que,int Element); 输入队列。 void Out_Queue(My_Queue &Que, int &Element); 输出队列。主函数： void main() {

} My_Queue My_Fst_Que; My_Fst_Que.Length = 0; int data = 0; My_Fst_Que.head = My_Fst_Que.rear =0; Input_Queue(My_Fst_Que, 2); Print_Queue(My_Fst_Que); Input_Queue(My_Fst_Que, 4); Print_Queue(My_Fst_Que); Input_Queue(My_Fst_Que, 6); Print_Queue(My_Fst_Que); Input_Queue(My_Fst_Que, 8); Print_Queue(My_Fst_Que); Input_Queue(My_Fst_Que, 10); Print_Queue(My_Fst_Que);

Out_Queue(My_Fst_Que, data); Print_Queue(My_Fst_Que); Out_Queue(My_Fst_Que, data); Print_Queue(My_Fst_Que); Out_Queue(My_Fst_Que, data); Print_Queue(My_Fst_Que); Out_Queue(My_Fst_Que, data); data = Head_Queue(My_Fst_Que); Print_Queue(My_Fst_Que);

3、运行过程：

三、字符串的模式匹配

1、目的：

输入目标串和模式串，运用KMP算法判断是否匹配。

2、程序说明：

typedef struct String String_KMP; struct String { char * data; int length; }; 定义结构体。

int KMPMatch (String_KMP &s, String_KMP &t , int next[]); 功能：用于检测返回值情况。主函数： void main() {

String_KMP s, p1; int *next_KMP, position=0; p1.data = "&&aaaaa";

} p1.length = strlen(p1.data); s.data ="&&&aaaaabaabcwwww"; s.length = strlen(s.data); next_KMP=(int *) malloc(sizeof(int) * strlen(p1.data)); next( p1, next_KMP); position = KMPMatch (s, p1 , next_KMP); if (position == 0) printf("No match! "); else printf("The match position is %d ", position);

3、运行过程：

1、匹配成功：

2、不能匹配：

四、稀疏矩阵(表示转置和乘法)

1、目的：

通过对矩阵的基本操作，了解多维数组的逻辑结构和存储结构。本程序是用三元数组表示矩阵，并进行相关的操作，将矩阵表示出来，以及快速转置的应用。

2、程序说明：

typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; } TSMatrix;

int InputMatrix(TSMatrix &M); void PrintM(TSMatrix M); void PrintM3(TSMatrix M); void trantup(TSMatrix M, TSMatrix &T); 主函数： void main() {

} int a; TSMatrix M,T; a=InputMatrix(M); printf(" 按三元组方式输出: "); PrintM3(M); printf(" 下面进行矩阵转置的操作： "); system("PAUSE"); system("cls"); printf(" 要转置的矩阵为: "); PrintM(M); trantup(M,T); printf(" 转置后的矩阵为: "); PrintM(T);

3、运行过程：

五 AVL树实现

1、目的：

通过程序的运用，使得树的相关功能更加容易实现，节约了时间和精力。

2、程序说明：

求根深度的实现所用到的：

Status InitBiTree(SqBiTree T); Status CreateBiTree(SqBiTree T); Status BiTreeEmpty(SqBiTree T); int BiTreeDepth(SqBiTree T); Status Root(SqBiTree T,TElemType *e);

3、运行过程：

六、图的实现：

1、目的：

通过程序的运用，使得图的有关功能更加容易实现，节约了时间和精力。

2、程序说明：

实现图的输出和遍历用到的: void CreateGraph(Graph *ga) ; void DFS(Graph g,int i,bool visited[]) ; void DFSTraverse(Graph g) ; void BFSTraverse(Graph g,Queue *que) ;

3、运行过程：

七、排序(希尔排序与归并排序)：

1、目的：

通过程序的运用，使得数据的排序更加容易实现，节约了时间和精力。

2、程序说明：

1)希尔排序的具体实现: void ShellSort(RecType R[],int n) { int i,j,gap,k; RecType tmp; gap=n/2; while (gap>0) { for (i=gap;i

{ tmp=R[i];

j=i-gap;

while (j>=0 && tmp.key

{ R[j+gap]=R[j];

j=j-gap; }

R[j+gap]=tmp;

j=j-gap; }

printf("gap=%d:",gap);

for (k=0;k

printf("%d ",R[k].key); printf(" "); gap=gap/2; } } 2)归并排序：

归并排序的实现所用到的：

int randGenerator(double vArray[],int n); int Merge(double vArray[],double Lr[],int i,int m,int n); int Msort(double vArray[],double Lr[],int s,int t);

3、运行过程：

总结

通过本次的实习，使我掌握了模块化设计方法，理解和运用结构化程序设计的思想和方法。提高了利用C语言进行程序设计能力。

第一次设计这么多程序，感觉压力很大，很难完成，虽然看起来设计流程感觉很轻松，但是正真完成的时候并不能通过程序表达出来。通过同学和老师的帮助最终还是完成了自己的程序设计，虽然程序还不是很完美，但能满足题目的各项要求，相信以后再次进行程序设计的时候会得心应手。

第二篇：南京工业大学数据结构作业答案作业3（推荐）

第三次作业

1.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性?

2. 顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?

3. 设循环队列的容量为40(序号从0到39)，现经过一系列的入队和出队运算后，有

① front=11，rear=19;② front=19，rear=11;问在这两种情况下，循环队列中各有元素多少个?

4. 试将下列递归过程改为非递归过程。

void test(int &sum){

int x;

Sanf(x);

if(x= =0) sum=0;

else {test(sum);sum+=x;}

printf(sum);

}

答：线性表是随机存储，可以实现，靠循环变量(j--)从表尾开始打印输出;

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可;

队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。(但堆栈是先减后压还是„„)

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。

2. 顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。

采用循环队列是解决假溢出的途径。

另外，解决队满队空的办法有三：

① 设置一个布尔变量以区别队满还是队空;

② 浪费一个元素的空间，用于区别队满还是队空。

③ 使用一个计数器记录队列中元素个数(即队列长度)。

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。

判断循环队列队空标志是： f=rear队满标志是：f=(r+1)%N

3. 设循环队列的容量为40(序号从0到39)，现经过一系列的入队和出队运算后，有

① front=11，rear=19;② front=19，rear=11;问在这两种情况下，循环队列中各有元素多少个?

答：用队列长度计算公式：(N+r-f)% N

① L=(40+19-11)% 40=8② L=(40+11-19)% 40=32

4. 参考程序：

void test(int &sum){

Stack S;

int x;

Sanf(x);

InitStack(S);

While(x){

Push(S,x);

Scanf(x);

}

sum=0;

printf(sum);

while(Pop(S,x)){

sum+=x;

printf(sum);

}

第三篇：信息工程大学博士考试大纲数据结构和算法分析

信息工程大学2013年博士研究生考试大纲

学科名称：081200计算机科学与技术(工学)、083500软件工程(工学)、110505密码学(军

事学)

考试科目：2004-数据结构和算法分析

类型：专业基础课

试卷分值：100分

参考书目：

1、《数据结构-用C语言描述》唐策善，高等教育出版社

2、《算法设计和分析》舒辉，自编。

考试要求：

1、熟练掌握常用数据结构(线性表、栈和队列、串、树、图等)的逻辑结构、存储结

构及在其上的基本运算的实现算法;10—30%

2、能结合排序、查找、集合运算等实际问题，选择较好的数据结构，给出问题求解算

法的实现思想及算法描述;10----30%

3、能熟练运用算法分析技术(方法)，对其算法的时间复杂度(空间复杂度)进行分

析、给出较准确的分析结果;10----30%

4、能用非形式化(或形式化)的语言，对算法的正确性、最优性给出论证或说明;0----10%

5、对求解问题的不同算法，能洞察其各算法的优缺点，提出改进意见，给出“改进算

法”的实现思想及算法描述;0----10%

6、对一般问题，能综合运用算法设计方法(分治法，回溯法，贪心法，动态规划法等)，

设计求解问题的算法;10----20%

7、对“算法设计与分析”研究领域的新技术、新方法有所了解和思考。

0----10%

第四篇：大学生消费结构

1. 什么是消费结构?

消费结构(consumption structure)是在一定的社会经济条件下，人们(包括各种不同类型的消费者和社会集团)在消费过程中所消费的各种不同类型的消费资料(包括劳务)的比例关系。有实物和价值两种表现形式。实物形式指人们在消费中，消费了一些什么样的消费资料，以及它们各自的数量。价值形式指以货币表示的人们在消费过程中消费的各种不同类型的消费资料的比例关系。在现实生活中具体的表现为各项生活支出。

2. 调查目的(必要性)：

通过分析大学生的消费结构，了解大学生消费结构及其家庭条件和社会环境因素的关系，以便有针对性的对学生消费提出合理化的建议。

3. 大学生消费结构中普遍存在的问题(看法·认识)：

大学生没有经济来源，经济独立性差，消费没有基础，经济的非独立性决定了大学生自主消费经验少，不能理性地对消费价值与成本进行衡量。

大学生对品牌的忠诚度很高。

学生思想活跃，对新事物有强烈的求知欲，喜欢追求新潮，并敢于创新，消费的趋附性强，娱乐消费占全部消费额的比重很大。

4. .针对消费的不合理现象，我们提出以下建议(对策·应对方法·解决方案)：

社会和学校应引导学生在校期间正确消费;

在校生活消费必须与家庭收入相适应;

物质消费与精神消费协调发展

改变落后的生活习惯，，提高消费的科学性;

树立正确消费观点，发扬艰苦奋斗、勤俭节约的精神。;

5.需要加强的教育(学校的作为)：

校风建设范畴中普遍缺少倡导大学生勤俭节约生活消费观的内容。大学生的消费心理和行为除了在个人喜好、穿着打扮等较少方面比较注重突出个性以外，对于时尚品牌、基本生活用品、生活费用的额度等主要消费内容都具有群体从众心理。高校校风主要体现的正是学生的群体心理和行为特征。在校风建设上注重塑造和强化学生良好的消费意识和消费行为，培养学生良好的消费习惯，这是高校思想政治教育一个非常重要的内容。

6. 给我们的启示(收获)：

注重精神消费，养成健康习惯。对于尚未有固定经济来源的大学生而言，精神消费不但能弥补物质生活上的不足，还能让大学生有更深的精神内涵和更丰富的精神生活。所以，大学生应通过各种教育和文化活动，把娱乐和知识摄取结合进行，以陶冶性情，获取知识。另外，要注意强调绿色消费，反对不利于保护生态环境的消费行为。