数据结构复习总结

数据结构复习总结第一章绪论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、顺序表（线性表的顺序存储表示）的形式描述：静态分配：#defineLISTSIZE100//线性表存储空间的初始分配量Typedefstruct{ElemTypeelem[LISTSIZE];intlength;}Sqlist;动态分配：#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量Typedefstruct{ElemType*elem;//存储空间基址，指示线性表的基地址intlength;//当前长度，实际已存元素个数intlistsize;//当前分配的存储容量,以sizeof(ElemType)为单位}Sqlist;6、构造一个空的顺序表StatusInitListSq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}7、在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回它的位序，否则返回0intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){i=1;p=L.elem;while(i=L.length&&!(*compare)(*p++,e))++i;if(i=Length)returnI;elsereturn0;}算法的时间复杂度为O(ListLength(L))8、顺序表中插入元素StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L的第i个元素之前插入新的元素e,//i的合法范围为1≤i≤L.length+1if(i1||iL.length+1)returnERROR;//插入位置不合法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]);//q指示插入位置for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;}9、顺序表中删除元素StatusListDelete_Sq(SqList&L,inti,ElemType&e){if((i1)||(iL.length))returnERROR;//删除位置不合法p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p=q;++p)*(p-1)=*p;//被删除元素之后的元素左移--L.length;//表长减1returnOK;}//ListDelete_Sq10、线性表的单链表存储结构TypedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;LinkListL；//L为单链表的头指针11、单链表中取第i个数据元素StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素p=L-next;j=1;//p指向第一个结点，j为计数器while(p&&ji){p=p-next;++j;}//顺指针向后查找，直到p指向第i个元素//或p为空if(!p||ji)returnERROR;//第i个元素不存在e=p-data;//取得第i个元素returnOK;}//GetElem_L12、单链表中在第i个位置插入数据元素StatusListInsert_L(LinkListL,inti,ElemTypee){p=L;j=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;returnOK;}算法的时间复杂度为：O(ListLength(L))13、单链表中删除数据元素StatusListDelete_L(LinkListL,inti,ElemType&e){p=L;j=0;while(p-next&&ji-1){p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;}算法的时间复杂度为：O(ListLength(L))14、重置线性表为空表voidClearList(&L){while(L-next){p=L-next;L-next=p-next;free(p);}}算法时间复杂度：O(ListLength(L))15、生成含n个数据元素的单链表voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表L=(LinkList)malloc(sizeof(LNode));L-next=NULL;for(i=n;i0;--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、链式队列的出队和入队（算法设计题，见习题）解：依题意，定义单链表节点类型如下：typedefstructlinknode{intdata;structlinknode*node;}根据单链表的特点，实现队列的五种运算的函数如下：node*front,*rear;intx;voidmakenull(front,rear){front=NULL;real=NULL;}voidfront(front,rear){if(front==NULL)printf(“队列下溢出！\n”);elsex=front-data;}voidenqueue(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;}}voiddequeue(front,rear){node*p;if(front==NULL)printf(“队列下溢出\n”);else{p=front;front=front-next;free(p);}}intempty(front){if(front==NULL)return(1);elsereturn(0);}5、顺序结构存储的队列的缺点当频繁地进行插入和删除操作后，在队列头由于多次删除数据，因而空闲了许多存储单元，而在队列尾进行插入时，可能最后没有空间产生“假”溢出错误。6、循环队列的判空和判满队空判断条件：rear==front队满判断条件：(rear+1)%MaxSize=front7、顺序栈的缺点在于当栈满时要发生溢出；链式栈便于结点的插入和删除，不存在栈满的问题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)?02、串的存储表示串的定长顺序存储表示#defineMAXSTR