数据结构知识点汇总.doc

《数据结构知识点汇总.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章2.1线性表的概念及其抽象数据类型的定义2.1.1线性表的逻辑结构线性表的定义线性表是n个类型相同的数据元素的有限序列，对n>0,除第一个元素无直接前驱，最后一个元素无直接后继外，其余的每个数据元素只有一个直接前驱和一个直接后继。线性表的特点：1）同一性：线性表有同类元素数据组成，每一个必须属于同一数据类型。2）有穷性：线性表由有限个数据元素组成，表长就是表中数据元素的个数。3）有序性：线性表中相邻数据元素之间存在着序偶关系。2.1.2线性表的抽象数据类型定义抽象数据类型定义：见课本。2.2线性表的顺序存储2.2.1

2、线性表的顺序存储结构顺序存储结构的定义线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。将线性表归纳为：关系线性化，节点顺序存。假定顺序表中有个元素，每个元素占个单元，第一个元素的地址为，则可通过如下公式计算出第个元素的地址：其中，称为基地址。线性存储结构的C语言定义#defineMAXSIZE100typedefstruct{E

3、lemTypeelem[MAXSIZE];/*ElemType可为int，char等*/intlast;/*记录线性表中最后一个元素在数组elem[]中的位置(下标值)*/}Seqlist;上述为定义一个结构体，结构名为Seqlist。知识延伸（typedef）（C课本用typedef声明新类型名）2.2.2线性表顺序存储结构上的基本运算线性表的基本运算1、查找操作2、插入操作3、删除操作4、顺序表合并算法线性表顺序存储结构的优缺点分析2.3线性表的链式存储链表定义：采用链式存储结构的线性表称为链表。链表的分类：1）按实现

4、角度看：链表可分为动态链表和静态链表。2）按链接方式的角度看：链表可分为单链表、循环链表和双链表。2.3.1单链表2.3.2单链表上的基本操作线性表的基本运算1、初始化单链表InitList(LinkList*L){*L=(LinkList)malloc(sizeof(Node));/*建立头结点*/(*L)->next=NULL;/*建立空的单链表L*/}注意：L是指向单链表的头结点的指针，用来接收主程序中带初始化单链表的头指针变量的地址，*L相当于主程序中带初始化单链表的头指针变量。2、建立单链表1）头插法建表算法描述

5、：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头节点之后，直至读入结束标志为止。单链表的存储结构：typedefstructNode/*结点类型定义，结构体名为Node*/{ElemTypedata;structNode*next;}Node,*Linklist;/*LinkList为结构指针类型*/LinkList与Node*同为结构指针类型，这两种类型是等价的。通常习惯上用LinkList说明指针变量，强调他是某个单链表的头指针变量。例如，使用定义LinkL

6、istL，则L为单链表的头指针，从而提高程序的可读性。用Node*来定义指向单链表中节点的指针，例如，Node*p，则p为指向单链表中节点的指针变量。算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*Linklist;voidCreatFromHead(LinkListL){Node*s;charc;intflag=1;while(flag){c=getchar();if(c!='$'){s=(Node*)malloc(sizeof(Node));s->dat

7、a=c;s->next=L->next;L->next=s;}elseflag=0;}}2）尾插法建表算法描述：头插法建立链表虽然简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者相同，可采用尾插法建表。该方法是将新节点插到当前单链表的尾上。为此需增加一个尾指针r，使之指向当前单链表的结尾。算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*Linklist;voidCreatFromHead(LinkListL){Node*s,*r;r=L;charc

8、;intflag=1;while(flag){c=getchar();if(c!='$'){s=(Node*)malloc(sizeof(Node));s->data=c;r->next=s;r=s;}else{flag=0;r->next=NULL;}}}1、单链表查找1）按序号查找算法描述：设带头结