数据结构复习提纲

《数据结构复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构复习提纲第一章绪论1．基本术语：数据，数据元素，数据对象，数据结构及其分类。数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：数据的单位，在计算机程序中通常作为一个整体进行考虑。数据对象：性质相同的数据元素的集合，是一个数据的子集。数据结构：相互之间存在一种或多种特定关系的数据元素集合数据结构分为：集合，线性结构，树形结构，图状或网状结构。2．什么是算法？算法的特性。算法：是对特定问题求解步骤的一种描述。特性：有穷性、确定性、可行性、输入、输出。3．时间复杂度及其简单计算。一般情况下，算法中基本操作重复执行的次数

2、是问题规模n的某个函数f(n)，算法的时间度量记作T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。第二章线性表1．线性表的定义，线性表的存储结构常有哪几种？各有何优缺点？线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。存储结构：顺序结构、链式结构。顺序结构：优点：逻辑相邻，物理相邻。可随机存取任一元素。存储空间紧凑。缺点：插入、删除操作需要移动大量的元素。预先分配空间需按最大空间分配，利用不充分。表容量难以扩充。链式结构：优点：便于进行插入和删除操作。缺点：不

3、能进行随机存取，查找需从第一个数据元素开始。1．顺序表的类型说明及其基本操作算法的实现#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;2．链表结构的类型说明及其基本操作算法的实现。表空条件，申请结点，插入，删除操作语句。单链表：typedefstructLNode{ElemTypedata;structLNode*next;}Lnode,*LinkList;表空条件：单链表：h->next==NULL;循环链表：h->ne

4、xt=h;双向链表：h->next=h=h->prior;申请结点：s=(LinkList)malloc(sizeof(LNode));s=(DuLinkList)malloc(sizeof(DuLNode));插入语句：s->next=p->next;p->next=s;双向链表：s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;删除语句：p->next=p->next->next;双向链表：p->prior->next=p->next;p->next->prior=p->prior;双向链表：typedefstru

5、ctDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;第一章栈和队列1．栈的定义及其特点。队列的定义及其特点。栈：是限定仅在表尾进行插入或删除操作的线性表。队列：只允许在一端进行插入而在另一端进行删除的线性表。2．顺序栈的类型说明及其算法实现。栈空，栈满条件，入栈出栈操作语句。顺序栈：typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;栈空：top=base;栈满：top-base>=stac

6、ksize;入栈：S.base=(SelemType*)realloc(S.base,(S.stacksize+STACKIMCREMENT)*sizeof(SElemType));、、、、、、、*(S.top++)=e;出栈：e=*(--S.top);1．循环队列的类型说明及其算法实现。队空，队满条件，入队出队操作，计算队列的长度语句。#defineMAXQSIZE100typedefstruct{QElemType*base;intrear;intfront;}SqQueue;队空：front=rear;队满：(rear+1)%M=front;(少用一个元素空间)入队：rea

7、r=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];计算队列长度：（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE;第五章数组与广义表1．二维数组的两种存储方式及地址计算。数组的顺序存储：1）以行序为主：LOC(i,j)=LOC(0,0)+(i*n+j)*L2）以列序为主：LOC(i,j)=LOC(0,0)+(j*m+i)*L2．矩阵的压缩存储，对称矩阵，三角矩阵的地址计算。1）对称矩阵：2）三角矩