数据结构知识点汇总

第二章2.1线性表的概念及其抽象数据类型的定义2.1.1线性表的逻辑结构线性表的定义线性表是n个类型相同的数据元素的有限序列，对n0,除第一个元素无直接前驱，最后一个元素无直接后继外，其余的每个数据元素只有一个直接前驱和一个直接后继。线性表的特点：1）同一性：线性表有同类元素数据组成，每一个ia必须属于同一数据类型。2）有穷性：线性表由有限个数据元素组成，表长就是表中数据元素的个数。3）有序性：线性表中相邻数据元素之间存在着序偶关系1,iiaa。2.1.2线性表的抽象数据类型定义抽象数据类型定义：见课本3938~PP。2.2线性表的顺序存储2.2.1线性表的顺序存储结构顺序存储结构的定义线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。将线性表归纳为：关系线性化，节点顺序存。假定顺序表中有n个元素，每个元素占k个单元，第一个元素的地址为)(1aLoc，则可通过如下公式计算出第i个元素的地址)(iaLoc：kiaLocaLoci)1()()(1其中，)(1aLoc称为基地址。线性存储结构的C语言定义#defineMAXSIZE100typedefstruct{ElemTypeelem[MAXSIZE];/*ElemType可为int，char等*/intlast;/*记录线性表中最后一个元素在数组elem[]中的位置(下标值)*/}Seqlist;上述为定义一个结构体，结构名为Seqlist。知识延伸（typedef）（C课本326330~PP用typedef声明新类型名）2.2.2线性表顺序存储结构上的基本运算线性表的基本运算1、查找操作2、插入操作3、删除操作4、顺序表合并算法线性表顺序存储结构的优缺点分析2.3线性表的链式存储链表定义：采用链式存储结构的线性表称为链表。链表的分类：1）按实现角度看：链表可分为动态链表和静态链表。2）按链接方式的角度看：链表可分为单链表、循环链表和双链表。2.3.1单链表2.3.2单链表上的基本操作线性表的基本运算1、初始化单链表InitList(LinkList*L){*L=(LinkList)malloc(sizeof(Node));/*建立头结点*/(*L)-next=NULL;/*建立空的单链表L*/}注意：L是指向单链表的头结点的指针，用来接收主程序中带初始化单链表的头指针变量的地址，*L相当于主程序中带初始化单链表的头指针变量。2、建立单链表1）头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头节点之后，直至读入结束标志为止。单链表的存储结构：typedefstructNode/*结点类型定义，结构体名为Node*/{ElemTypedata;structNode*next;}Node,*Linklist;/*LinkList为结构指针类型*/LinkList与Node*同为结构指针类型，这两种类型是等价的。通常习惯上用LinkList说明指针变量，强调他是某个单链表的头指针变量。例如，使用定义LinkListL，则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-data=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;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;}}}3、单链表查找1）按序号查找算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点(L-next)开始顺着链域扫描，用指针p指向当前扫描到的结点，初值指向头结点,用j做计数器，累计当前扫描过的结点数(初值为0)，当j=i时，指针p所指的结点就是要找的第i个结点。算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*Linklist;Node*Get(LinkListL,inti){intj=0;Node*p;p=L:if(i=0)returnNULL;/*找的序号太小*/while((p-next!=NULL)&&(ji)){p=p-next;j++;}if(p-next==NULL)returnNULL;/*找不到i*/elsereturni;/*找到了i*/}2）按值查找算法描述：按值查找是指在单链表中查找是否有节点值等于e的结点，若有的话，则返回首次找到的其值等于e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*Linklist;Node*Locate(LinkListL,ElemTypekey){Node*p;p=L-next;while(p!=NULL){if(p-data==key)returnp;/*找到了key*/p=p-next;}returnNULL;/*没有找到了key*/}4、单链表插入操作问题要求：在线性表的第(11)iin个位置之前插入一个新元素e。算法思想：查找：在单链表中找到第i-1个结点并有指针pre指示。申请：申请新节点s，将其数据域的值置为e；插入挂链：通过修改指针域将新节点s挂入单链表L。算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*Linklist;voidInslist(ElemTypee,inti,LinkListL){Node*pre,*s;intk;if(i=0)returnERROR;pre=L;k=0;while(pre!=NULL&&ki-1){pre=pre-next;k++;}if(k==i){s=(Node*)malloc(sizeof(Node));s-data=e;s-next=pre-next;pre-next=s;returnOK;}else{printf(插入位置不合理);returnERROR;}}5、单链表删除问题要求：将线性表的第(11)iin个元素e删除算法思想：查找：通过计数方式找到第i-1个结点并由指针pre指示；删除第i个结点并释放结点空间。结果：将长度为n的线性表11(,,,,,)iinaaaa变成长度为n-1的线性表111(,,,,,)iinaaaa算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*Linklist;voidDelList(LinkListL,inti,ElemType*e){Node*pre,*s;intk;if(i=0)returnERROR;pre=L;k=0;/*按序号查找第i个位置*/while(pre-next!=NULL&&ki){pre=pre-next;k++;}if(pre-next==NULL){printf(删除位置错误);returnERROR;}s=pre-next;/*使得删除得第i个位置的指针为s*/pre-next=s-next;*e=s-data;free(s);/*释放被删除的结点所占的内存空间*/returnOK;}算法应用举例1、求单链表的长度算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点，从第一个元素开始“数”，一直“数”到最后一个结点(p-next=NULL).算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*LinkList;intListLength(LinkListL){Node*p;intk=0;p=L:while(p-next!=NULL){p=p-next;k++;}returnk;}2、求两个集合的差已知：以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*LinkList;voidDifference(LinkListLA,LinkListLB){Node*p,*q,*pre,*r;pre=LA;p=LA-next;while(p!=NULL){q=LB-next;while(p-data!=q-data&&q!=NULL)/*查找有无相同元素*/q=q-next;if(p-data==q-data)/*有相同元素*/{r=p;pre-next=p-next;/*本来pre-next=p,现改为pre-next=p-next*/p=p-next;/*下一次判断p-next*/free(r);/*释放被删除的元素的空间*/}else{pre=p;/*也可写为pre=pre-next*/p=p-next;}}}3、有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将他们合并成一个单链表LC，要求LC也是非递减有序排列。要求：新表LC利用现有的表LA和LB中的元素结点空间，而不要额外申请结点空间。例如(2,2,3),(1,3,3,4)LALB，则(1,2,2,3,3,3,4)LC。算法思想：要求利用现有的表LA和LB中的结点空间来建立新表LC，可通过更改结点的next域来重建新的元素之间的线性关系。为包证新表仍然递增有序，可以利用尾插法建立单链表的方法，只是新表中的结点不用malloc，而只要从表LA和LB中选择合适的点插入新表LC即可。算法：typedefstructNode{ElemTypedata;structNode*next;}Node,*LinkList;LinkListMergeLinkList(LinkListLA,LinkListLB){Node*pa,*pb,*pc;LinkListLC;/*pa和pb分别指向两个单链表LA和LB中的将要判断的结点，pc初值为LC且pc始终指向LC的表尾*/pa=LA-next