没有合适的资源?快使用搜索试试~ 我知道了~
首页[PDF] Fundamentals of Data Structure in C
[PDF] Fundamentals of Data Structure in C
需积分: 50 69 下载量 66 浏览量
更新于2023-03-16
评论 1
收藏 1.18MB PDF 举报
pdf版的数据结构必读书 Data structure + Algorithm = Programming The tools and techniques to design and implement large-scale computer systems: Data abstraction Algorithm specification Performance analysis Performance measurement
资源详情
资源评论
资源推荐
Fundamentals of
Data Structure in C
Ellis Horowitz
University of southern California
Chapter 1.
BASIC CONCEPT
Data structure + Algorithm = Programming
The tools and techniques to design and implement large-
scale computer systems:
Data abstraction
Algorithm specification
Performance analysis
Performance measurement
1.1 System life cycle
(the system development process)
requirement
analysis
design
coding
verification
the purpose of the project
(input, output )
break the problem down into manageable pieces
Bottom - up (unstructed)
Top - down (structed)
data object + operations
<---language independanc
abstract data type
algorithm specification
choose concrete representation for data objects
and write algorithm for each operatios on them
developing correctness for programs
testing the program with variety of input data
removing errors
*correctness running time
1.2 Algorithm Specification
【definition】An
algorithm
is a finite set of instructions that, if followed, accomplishes a
particular task, In addition, all algorithms must satisfy the following criteria:
(1) Input.
There are zero or more quantities that are externally applied.
(2) Output.
At least one quantity is produced
.
(3) Definiteness.
Each instruction is clear and unambiguous.
(4) Finiteness.
If we trace out the instructions of an algorithm. then for all
cases, the algorithm terminates after finite number of steps.
(5) Effectiveness.
Every instruction must be basic enough to be carried
out, in principle, by a person using only pencil and paper, It is not
enough that each operation be definite as in (3); it also must be
feasible.
The distinguishes between an algorithm and a program:
Program----- does not have to satisfy(4)
(operation system)
a programming language
algorithm----may was natural language、graphic、a programming
language
〖example1〗selection sort
algorithm:
for (i=0; i<n; i++) {
examine list[i] to list[n-1] and suppose that the
smallest integer is at list[min];
interchange list[i] and list[min];
}
Program:
for interchanging:
1. macro version
#define swap (x, y, t ) (( t ) = ( x ), ( x ) = ( y ), ( y ) = ( t ))
2. function version swap ( int *a, *b);
void swap ( int *x, int *y ) /* both parameters are pointers
to ints */
{ int temp = *x ; /* declares temp as an int and assigns
to it the contents of what x points to */
*x = *y; /* stores what y points to into the location
where x points*/
*y = temp; /*places the contents of temp in location
pointed to by y*/
}
#include<stdio.h>
#include<math.h>
#define MAX_SIZE 101
#define SWAP(x, y, t) ((t) = (x),(x) = (y), (y) = (t))
void sort ( int [ ], int ); /*selection sort*/
void main (void)
{
int i,n;
int list [MAX_SIZE];
printf ("Enter the number of numbers to generate; ");
scan ("%d", &n);
if ( n < 1 || n > MAX_SIZE) {
printf (stderr, "Improper value of n\n");
exit (1);
}
for (i = 0; i < n; i++) { /* randomly generate numbers*/
list [ i ] = rand ( ) % 1000;
printf ("%d ",list [ i ]);
}
sort ( list , n ) ;
printf ( " \n Sorted array: \n ");
for ( i = 0 ; i < n ; i++ ) /*print out sorted numbers */
printf ( "%d ", list [ i ] );
printf ( " \n " );
}
void sort ( int list [ ] ,int n )
{
int i, j, min, temp;
for ( i = 0; i < n-1; i++ ) {
min = i;
for ( j = i + 1; j < n; j++ )
if ( list [ j ] <list [ min ] )
min = j;
SWAP ( list [ i ] , list [ min ], temp );
}
}
〖
example2
〗
Binary search
given: a sorted list list [ n ]
serach number searchnum
return: i if list [ i ] = serachnum
-1 not present in the list
Algorithm:
while ( there are more integers to check ) {
middle = (lift +right )/2;
if ( serchnum < list[middle] )
right = middle - 1;
else if ( serchnum == list[middle])
return middle;
else left = middle + 1;
}
left(0)
middle
right(n-1)
list[middle]
searchnum
~
=
>
i
right=middle -1
lefit=middle +1
<
program:
for comparing:
1. macro version
#define compare(x,y) ((x) < (y)? -1:((x) == (y)) ? 0:1)
2. function version
int compare ( int x, int y );
{ /* compare x and y, return -1 for less than, 0 for equal, 1 for
greater*/
if ( x < y ) return -1;
else if ( x == y ) return 0;
else return 1;
}
int binsearch ( int list [ ], int searchnum , int left, int right )
{ /* search list [ 0 ] <= list [ 1 ] <= ··· <= list [ n-1 ] for searchnum.
Return its position if found . Otherwise return -1*/
int middle ;
while ( left <= right ) {
middle = ( left + right ) / 2;
剩余201页未读,继续阅读
weixin_40187574
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 27页智慧街道信息化建设综合解决方案.pptx
- 计算机二级Ms-Office选择题汇总.doc
- 单链表的插入和删除实验报告 (2).docx
- 单链表的插入和删除实验报告.pdf
- 物联网智能终端项目设备管理方案.pdf
- 如何打造品牌的模式.doc
- 样式控制与页面布局.pdf
- 武汉理工Java实验报告(二).docx
- 2021线上新品消费趋势报告.pdf
- 第3章 Matlab中的矩阵及其运算.docx
- 基于Web的人力资源管理系统的必要性和可行性.doc
- 基于一阶倒立摆的matlab仿真实验.doc
- 速运公司物流管理模式研究教材
- 大数据与管理.pptx
- 单片机课程设计之步进电机.doc
- 大数据与数据挖掘.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0