如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
(完整word版)数据结构(C语言版)期末复习汇总(完整word版)数据结构(C语言版)期末复习汇总PAGE\*MERGEFORMAT19(完整word版)数据结构(C语言版)期末复习汇总数据结构(C语言版)期末复习汇总绪论数据结构:是一门研究非数值计算程序设计中的操作对象,以及这些对象之间的关系和操作的学科。数据结构是一门综合性的专业课程,是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。数据:是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。数据的逻辑结构划分:线、树、图算法的定义及特性算法:是为了解决某类问题而规定的一个有限长的操作序列。五个特性:有穷性、确定性、可行性、输入、输出评价算法优劣的基本标准(4个):正确性、可读性、健壮性、高效性及低存储量第二章线性表线性表的定义和特点:线性表:由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度,n=0时称为空表。非空线性表或线性结构,其特点:(1)存在唯一的一个被称作“第一个”的数据元素;(2)存在唯一的一个被称作“最有一个”的数据元素;(3)除第一个之外,结构中的每个数据元素均只有一个前驱;(4)除最后一个之外,结构中的每个数据元素均只有一个后继。顺序表的插入:n个元素在i位插入,应移动(n-i+1)位元素。顺序表存储结构的优缺点:优点:逻辑相邻,物理相邻;可随机存取任一元素;存储空间使用紧凑;缺点:插入、删除操作需要移动大量的元素;预先分配空间需按最大空间分配,利用不充分;表容量难以扩充;线性表的应用:一般线性表的合并:★★★算法2.1:LA=(7,5,3,11)LB=(2,6,3)合并后LA=(7,5,3,11,2,6)算法思想:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素,并依值在线性表LA中进行查访,若不存在,则插入之。有序表的合并:★★★算法2.2:LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则LC=(2,3,5,6,8,9,11,11,15,20)算法思想:首先创建一个空表LC,通过比较指针pa和pb所指向的元素的值,依次从LA或LB中“摘取”元素值较小的结点插入到LC表的最后,当其中一个表变空是,说明此表的元素已归并完,则只要将另一个非空表的剩余结点依次插入在LC表的最后即可。线性链表:线性链表的插入:插入元素师,指针的指向变化:上述指针修改用语句描述即为:s->next=p->next;p->next=s;单链表的插入:★★★voidinsertnode(linklisthead,datetypex,inti){listnode*p,*q;p=getnode(head,i-1);if(p==NULL)error(〝positionerror〞);q=(listnode*)malloc(sizeof(listnode));q–>data=x;q–>next=p–next;p–>next=q;}课本中:s=newLNode;s->data=e;s->next=p->next;p->next=s;线性链表的删除:删除元素,指针的指向变化:上述指针修改用语句描述即为:p->next=p->next->next;单链表的删除:★★★voiddeletelist(linklisthead,inti){listnode*p,*r;p=getnode(head,i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}课本中:q=p->next;p->next=q->next;单链表特点:它是一种动态结构,整个存储空间为多个链表共用;不需预先分配空间;指针占用额外存储空间;不能随机存取,查找速度慢。第三章栈和队列栈的类型定义:栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶