免登录购买

数据结构（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;

单链表的插入：★★★

void  insertnode(linklist  head，datetype  x，int  i){

       listnode  * p，*q;

       p=getnode(head，i-1);

       if(p==NULL)

           error(〝position  error〞);

        q=(listnode *)

       malloc(sizeof(listnode));

        q–>data=x;

        q–>next=p–next;

         p–>next=q;

      }

课本中：

s=new LNode;

s->data =e;

s->next=p->next;

p->next=s;

线性链表的删除：删除元素，指针的指向变化：

上述指针修改用语句描述即为：p->next=p->next->next;

单链表的删除：★★★

void  deletelist(linklist head， int i)

   {  listnode * p， *r;

      p=getnode(head，i-1);

      if(p= =NULL ||

        p–>next= =NULL)

      return ERROR;

      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的次序进栈，退栈的第一个元素应为栈顶元素。即，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。