标题:求数据结构c语言(严蔚敏,吴伟民) 电子书 下载
只看楼主
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 
、总结

抽象数据类型定义

抽象数据类型实现方法:一、类C语言实现 二、C语言实现


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:20
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 

第三课

本课主题: 算法及算法设计要求

教学目的: 掌握算法的定义及特性,算法设计的要求

教学重点: 算法的特性,算法设计要求

教学难点: 算法设计的要求

授课内容:

一、算法的定义及特性

1、定义:

ispass(int num[4][4])

{ int i,j; for(i=0;i<4;i++)

for(j=0;j<4;j++)

if(num[i][j]!=i*4+j+1)/*一条指令,多个操作*/

return 0;

return 1; }/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作;此外,一个算法还具有下列五个重要特性:

2、算法的五个特性:

有穷性

一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有穷时间内完成;

确定性

算法中每一条指令必须有确切的含义,读者理解时不会产生二义性。有任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。

可行性

一个算法是能行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

输入

一个算法有零个或多个的输入,这些输入取自于某个特定的对象的集合。

输出

一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。

例:

有穷性

haha() {/*only a joke,do nothing.*/ } main() {printf("请稍等...您将知道世界的未日..."); while(1) haha(); }

确定性

float average(int *a,int num) {int i;long sum=0; for(i=0;i<num;i++) sum+=*(a++); return sum/num; } main() {int score[10]={1,2,3,4,5,6,7,8,9,0}; printf("%f",average(score,10); }

可行性

输入

输出

getsum(int num) { int i,sum=0; for(i=1;i<=num;i++) sum+=i; } /*无输出的算法没有任何意义,


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:20
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 

二、算法设计的要求

1、正确性

算法正确性的四个层次

程序不含语法错误。

max(int a,int b,int c) { if (a>b) {if(a>c) return c; else return a; } }

程序对于几组输入数据能够得出满足规格说明要求的结果。

max(int a,int b,int c) { if (a>b) {if(a>c) return a; else return c; } } /* 8,6,7 */ /* 9,3,2 */

程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。

max(int a,int b,int c) { if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; } }

程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

2、可读性

3、健壮性

4、效率与低存储量需求

效率指的是算法执行时间。对于解决同一问题的多个算法,执行时间短的算法效率高。

存储量需求指算法执行过程中所需要的最大存储空间。

两者都与问题的规模有关。

算法一

算法二

在三个整数中求最大者

max(int a,int b,int c) {if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; }/*无需额外存储空间,只需两次比较*/

max(int a[3]) {int c,int i; c=a[0]; for(i=1;i<3;i++) if (a[i]>c) c=a[i]; return c; } /*需要两个额外的存储空间,两次比较,至少一次赋值*/ /*共需5个整型数空间*/

求100个整数中最大者

同上的算法难写,难读

max(int a[100]) {int c,int i; c=a[0]; for(i=1;i<100;i++) if (a[i]>c) c=a[i]; return c; } /*共需102个整型数空间*/

三、总结

1、算法的特性

2、算法设计要求:正确性、可读性、健壮性、效率与低存储量需求。


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:21
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 

第四课

本课主题: 算法效率的度量和存储空间需求

教学目的: 掌握算法的渐近时间复杂度和空间复杂度的意义与作用

教学重点: 渐近时间复杂度的意义与作用及计算方法

教学难点: 渐近时间复杂度的意义

授课内容:

一、算法效率的度量

算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣,可以在相同的规模下,考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法:

1、事后统计的方法。

缺点:不利于较大范围内的算法比较。(异地,异时,异境)

2、事前分析估算的方法。

程序在计算机上运行所需时间的影响因素

算法本身选用的策略

问题的规模

规模越大,消耗时间越多

书写程序的语言

语言越高级,消耗时间越多

编译产生的机器代码质量

机器执行指令的速度

综上所述,为便于比较算法本身的优劣,应排除其它影响算法效率的因素。

从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法的时间量度。(原操作在所有该问题的算法中都相同)

T(n)=O(f(n))

上示表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:21
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 

求4*4矩阵元素和,T(4)=O(f(4))

f=n*n;

sum(int num[4][4])

{ int i,j,r=0; for(i=0;i<4;i++)

for(j=0;j<4;j++)

r+=num[i][j]; /*原操作*/

return r; }

最好情况: T(4)=O(0)

最坏情况: T(4)=O(n*n)

ispass(int num[4][4])

{ int i,j; for(i=0;i<4;i++)

for(j=0;j<4;j++)

if(num[i][j]!=i*4+j+1)

return 0;

return 1; }

原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。

语句

频度

时间复杂度

{++x;s=0;}

1

O(1)

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

{++x;s+=x;}

n

O(n)

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

for(k=1;k<=n;++k)

{++x;s+=x;}

n*n

O(n*n)

O(log n)

基本操作的执行次数不确定时的时间复杂度

平均时间复杂度

依基本操作执行次数概率计算平均

最坏情况下时间复杂度

在最坏情况下基本操作执行次数

二、算法的存储空间需求

类似于算法的时间复杂度,空间复杂度可以作为算法所需存储空间的量度。

记作:

S(n)=O(f(n))

若额外空间相对于输入数据量来说是常数,则称此算法为原地工作

如果所占空间量依赖于特定的输入,则除特别指明外,均按最坏情况来分析。

三、总结

渐近时间复杂度

空间复杂度


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:21
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 

第五课

本课主题: 线性表的类型定义

教学目的: 掌握线性表的概念和类型定义

教学重点: 线性表的类型定义

教学难点: 线性表的类型定义

授课内容:

复习:数据结构的种类

线性结构的特点:

在数据元素的非空有限集中,

(1)存在唯一的一个被称做“第一个”的数据元素;

(2)存在唯一的一个被称做“最后一个”的数据元素;

(3)除第一个之外,集合中的每个数据元素均只有一个前驱;

(4)除最后一个之外,集合中每个数据元素均只有一个后继。

一、线性表的定义

线性表是最常用且最简单的一种数据结构。

一个线性表是n个数据元素的有限序列。

数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。

线性表例:

1、

1

2

3

4

5

6

7

2、

3、

学号

姓名

语文

数学

C语言

6201001

张三

85

54

92

6201002

李四

92

84

64

6201003

王五

87

74

73

6201004

 

 

 

...

 

 

 

数据元素也可由若干个数据项组成(如上例3)。这时常把数据元素称为记录。含有大量记录的线性表又称文件

线性表中的数据元素类型多种多样,但同一线性表中的元素必定具有相同特性,即属同一数据对象,相邻数据元素之间存在着序偶关系。

a1

...

ai-1

ai

ai+1

...

an

ai是ai+1的直接前驱元素,ai+1是ai的直接后继元素。

线性表中元素的个数n定义为线性表的长度,为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素,把i称为数据元素ai在线性中的位序


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:22
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 

二、线性表的类型定义

1、抽象数据类型线性表的定义如下:

ADT List{

数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}

数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}

基本操作:

InitList(&L) DestroyList(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) LocateElem(L,e,compare()) PriorElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) ListDelete(&L,i,&e) ListTraverse(L,visit()) union(List &La,List &Lb)

}ADT List

2、部分操作的类C实现:

InitList(&L)

{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=LIST_INIT_SIZE;

return OK;

}//InitList

GetElem(L,i,&e)

{*e=L.lem[i]

}//GetElem

ListInsert(List &L,int i,ElemType e)

{if(i<1||i>L.length+) return ERROR;

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;

*q=e;

++L.length;

return OK;

}//ListInsert

void union(List &La,List &Lb)

{La_len=ListLength(La);Lb_len=ListLength(Lb);

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

GetElem(Lb,i,e);

if(!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);

}//union

void MergeList(List La,List Lb,List &Lc)

{InitList(Lc);

i=j=1;k=0;

La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<Lb_len)){

GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){ListInsert(Lc,++k,ai);++i;}

else{ListInsert(Lc,++k,bj);++j;}

}

while(k<=La_len){

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

while(j<=Lb_len){

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

}//MergeList


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:22
ysfabm
Rank: 1
等 级:新手上路
威 望:1
帖 子:274
专家分:0
注 册:2004-11-9
得分:0 

先发到这吧,我要下班了!

请到这个网址:http://www.vchome.net/tech/datastruct/datasf29.htm


精诚所至,
       金石为开!
      PLM技术社区: [url=http://www.]www.[/url] 最专业的PLM技术讨论社区。
2004-12-06 16:24
xiehongyou
Rank: 1
等 级:新手上路
帖 子:84
专家分:0
注 册:2004-8-29
得分:0 
这里有:打开网页快下:http://neweb.dhcn.net/ebook/C-Cpp/879.asp
2004-12-06 19:03
seykaola
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2004-12-4
得分:0 
多谢你们了,真的对我帮助很大,虽然我还没有仔细看.
2004-12-06 23:52



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-8870-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.712664 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved