第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
02331数据结构复习总结.doc
数据结构复习总结
第一章 绪论
1、数据：是对客观事物的符合表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理
的符合的总成。
2、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3、数据项：是数据的不可分割的最小单位。（一个数据元素可由若干个数据项组成）
4、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
5、数据的逻辑结构（即数据之间的相互关系）：线性结构、树形结构、图状结构、集合。（4 种）
6、数据的存储结构（物理结构）：顺序存储结构、链式存储结构。（2 种）
7、数据的四种基本的存储方法：顺序存储方法、链式存储方法、索引存储方法、散列存储方法。
8、数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据（逻辑）
结构，而算法的实现依赖于采用的存储结构。
9、存取结构：与存储结构是两个不同的概念。存取结构是在一个数据结构上对查找操作的时间性能的
一种描述，通常有两种存取结构：随机存取结构（例如顺序表）和顺序存取结构（例如单链表）
10、 算法的特征：有穷性、确定性、可行性、输入和输出。
11、 算法的时间复杂度（计算）
第二章 线性表
1、线性结构（这里指线性表的逻辑结构）的特点：在数据元素的非空有限集中，（1）存在唯一的“第
一元素”（2）存在唯一的“最后元素”（3）除“第一元素”外，集合中的每个元素均只有一个前驱
（4）除“最后元素”外，集合中的每个元素均只有一个后继
2、线性表：是具有相同数据类型的 n(n>=0)个数据元素的有限序列，是最简单、最基本、也是最常用的
一种线性结构。
（1）表中元素具有逻辑上的顺序性；
（2）表中元素个数有限；
（3）表中元素都是数据元素；
（4）表中元素的数据类型都相同；
（5）表中元素具有抽象性。
3、线性表的长度：线性表中元素的个数 n(n>=0)定义为线性表的长度，n=0 时成为空表。
4、线性表的存储结构（物理结构）有
顺序存储结构：顺序表（具有按数据元素的序号随机存取的特点，时间复杂度为 O(1)）
链式存储结构：单链表（数据的存取方式为顺序存取）
其它存储结构：循环链表、双向链表、静态链表
5、顺序表（线性表的顺序存储表示）的形式描述：
静态分配： #define LISTSIZE 100
//线性表存储空间的初始分配量
Typedef struct{
ElemType elem[LISTSIZE];
int length;
}Sqlist;
动态分配： #define LIST_INIT_SIZE 100
//线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
Typedef struct{
//存储空间基址，指示线性表的基地址
ElemType *elem;
int length;
int listsize; //当前分配的存储容量,以 sizeof(ElemType)为单位
//当前长度，实际已存元素个数
} Sqlist;
6、构造一个空的顺序表
Status InitList Sq(SqList &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;
}
7、在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回它的位序，否则返回 0
int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)){
i=1;
p=L.elem;
while(i<=L.length&&!(*compare)(*p++,e)) ++i;
if(i<=Length) return I;
else return 0;
}
算法的时间复杂度为 O( ListLength(L) )
8、顺序表中插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
// 在顺序表 L 的第 i 个元素之前插入新的元素 e,
// i 的合法范围为 1≤i≤L.length+1
if (i < 1 || i > L.length+1) return ERROR;
if (L.length >= L.listsize) {
// 插入位置不合法
// 当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase) exit(OVERFLOW);
// 存储分配失败
L.elem = newbase;
L.listsize += LISTINCREMENT; // 增加存储容量
// 新基址
}
q = &(L.elem[i-1]);
for (p = &(L.elem[L.length-1]); p >= q;
// q 指示插入位置
--p)
*(p+1) = *p;
// 插入位置及之后的元素右移
*q = e;
++L.length;
return OK;
// 插入 e
// 表长增 1
}
9、顺序表中删除元素
Status ListDelete_Sq (SqList &L, int i, ElemType &e) {
// 删除位置不合法
return ERROR;
// p 为被删除元素的位置
// 被删除元素的值赋给 e
// 表尾元素的位置
*(p-1) = *p;
// 被删除元素之后的元素左移
if ((i < 1) || (i > L.length))
p = &(L.elem[i-1]);
e = *p;
q = L.elem+L.length-1;
for (++p; p <= q; ++p)
--L.length;
return OK;
// 表长减 1
} // ListDelete_Sq
10、 线性表的单链表存储结构
Typedef struct LNode {
ElemType
struct Lnode
data;
*next;
// 数据域
// 指针域
} LNode, *LinkList;
LinkList L； // L 为单链表的头指针
11、 单链表中取第 i 个数据元素
Status GetElem_L(LinkList L, int i, ElemType &e) {
// L 是带头结点的链表的头指针，以 e 返回第 i 个元素
p = L->next;
// p 指向第一个结点，j 为计数器
while (p && jnext; ++j;
j = 1;
}
// 顺指针向后查找，直到 p 指向第 i 个元素
// 或 p 为空
if ( !p || j>i )
return ERROR;
// 第 i 个元素不存在
e = p->data;
return OK;
} // GetElem_L
// 取得第 i 个元素
12、 单链表中在第 i 个位置插入数据元素
Status ListInsert_L(LinkList L,int i,ElemType e){
return ERROR;
p=L; j=0;
while(p&&jnext; ++j; }
if(!p || j>i-1)
s=(LinkList) malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
算法的时间复杂度为：O(ListLength(L))
13、 单链表中删除数据元素
Status ListDelete_L(LinkList L,int i,ElemType &e){
j=0;
free(q);
return ERROR;
p=L;
while(p->next&&jnext; ++j;}
if(!(p->next) || j>i-1)
q=p->next; p->next=q->next;
e=q->data;
return OK;
}
算法的时间复杂度为：O(ListLength(L))
14、 重置线性表为空表
void ClearList(&L){
while(L->next){
p=L->next; L->next=p->next;
free(p);
}
}
算法时间复杂度：O(ListLength(L))
15、 生成含 n 个数据元素的单链表
void CreateList_L(LinkList &L,int n){
//逆序输入 n 个数据元素，建立带头结点的单链表
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
for(i=n;i>0;--i){
p=(LinkList)malloc(sizeof(LNode));
scanf(&p->data);
p->next=L->next; L->next=p;
}
}
时间复杂度为：O(Listlength(L))
16、
第三章 栈和队列
1、栈和队列的操作过程
2、栈的应用
a) 栈在递归过程中作为工作栈的使用，栈在表达式计算中从中缀表示转后缀表示，栈在括号配对
中的应用，栈在数制转换中的应用
b) 双栈共用一个数组的进栈、退栈、置空栈算法及栈满、栈空条件，使用两个栈模拟一个队列时
的进队列和出队列算法。
3、队列的应用
a) 队列在分层处理中的使用，包括二叉树、树、图等 层次遍历过程中的使用
b) 队列在对数据循环处理过程中的使用，例如约瑟夫问题、归并排序
c) 队列在调度算法中的使用
4、链式队列的出队和入队（算法设计题，见习题）
解：依题意，定义单链表节点类型如下：
typedef struct linknode
{
int data;
struct linknode *node;
}
根据单链表的特点，实现队列的五种运算的函数如下：
node * front,*rear;
int x;
void makenull(front,rear)
{
front = NULL;
}
void front(front,rear)
real = NULL;
printf(“队列下溢出！\n”);
{
if(front = = NULL)
else x=front->data;
}
void enqueue(front,rear,x)
{
node *p;
if(rear = = NULL)
{
rear=(node * ) malloc(sizeof(node));
rear->data=x;
front=rear;
}
else
{
p=(node * )malloc(sizeof(node));
p->data=x;
rear->next=p;
rear=p;
}
}
void dequeue(front,rear)
{
node *p;
if(front = = NULL) printf(“队列下溢出\n”);
else
{
p=front;
front=front->next;
free(p);
}
}
int empty(front)
{
if(front = = NULL)
else return(0);
}
return(1);
5、顺序结构存储的队列的缺点
当频繁地进行插入和删除操作后，在队列头由于多次删除数据，因而空闲了许多存储单元，而在队
列尾进行插入时，可能最后没有空间产生“假”溢出错误。
6、循环队列的判空和判满
队空判断条件：rear = = front
队满判断条件：(rear+1)%MaxSize=front
7、顺序栈的缺点在于当栈满时要发生溢出；链式栈便于结点的插入和删除，不存在栈满的问题
8、为了消除顺序队列在进、出队列过程中可能产生的“假溢出”现象，通常把顺序队列的存储数组设想
成一个环形数组（称为循环队列）
第四章 串
1、串的基本操作（13 种）
StrAssign、StrCopy、StrDestroy、StrEmpty、StrCompare、StrLength、StrConcat、StrSubString、StrIndex、
StrReplace、StrInsert、StrDelete、StrClear
在上述抽象数据类型定义的 13 种操作中，
串赋值 StrAssign、串复制 Strcopy、
串比较 StrCompare、求串长 StrLength、
串联接 Concat 以及求子串 SubString
等六种操作构成串类型的最小操作子集。
即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除 ClearString 和串销毁
DestroyString 外）可在这个最小操作子集上实现。
例如，可利用串比较、求串长和求子串等操作实现定位函数 Index(S,T,pos)
基本思想：StrCompare(SubString(S, i, StrLength(T)),T )
? 0
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
