数据结构知识点汇总.doc

《数据结构知识点汇总.doc》由会员分享，可在线阅读，更多相关《数据结构知识点汇总.doc（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、*记录线性表中最后一个元素在数组elem 中的位置(下标值)*/Seqlist;上述为定义一个结构体，结构名为Seqlist。知识延伸（typedef）（C课本用typedef声明新类型名）2.2.2 线性表顺序存储结构上的基本运算线性表的基本运算1、 查找操作2、 插入操作3、 删除操作4、 顺序表合并算法线性表顺序存储结构的优缺点分析2.3 线性表的链式存储链表定义：采用链式存储结构的线性表称为链表。链表的分类：1） 按实现角度看：链表可分为动态链表和静态链表。2） 按链接方式的角度看：链表可分为单链表、循环链表和双链表。2.3.1 单链表2.3.2 单链表上的基本操作线性表的基本运算1、

4、 初始化单链表 InitList(LinkList *L) *L=(LinkList)malloc(sizeof(Node); /*建立头结点*/ (*L)-next=NULL;/*建立空的单链表L*/ 注意：L是指向单链表的头结点的指针，用来接收主程序中带初始化单链表的头指针变量的地址，*L相当于主程序中带初始化单链表的头指针变量。2、 建立单链表1）头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头节点之后，直至读入结束标志为止。单链表的存储结构：typedef struct Node /*结点类型定义，结构体名

5、为Node*/ElemType data;struct Node * next;Node,*Linklist; /*LinkList为结构指针类型*/LinkList与Node *同为结构指针类型，这两种类型是等价的。通常习惯上用LinkList说明指针变量，强调他是某个单链表的头指针变量。例如，使用定义LinkList L，则L为单链表的头指针，从而提高程序的可读性。用Node *来定义指向单链表中节点的指针，例如，Node *p，则p为指向单链表中节点的指针变量。算法：typedef struct NodeElemType data;struct Node * next;Node,*Lin

6、klist;void CreatFromHead(LinkList L)Node *s;char c;int flag=1;while(flag)c=getchar();if(c!=$)s=(Node *)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;else flag=0;2） 尾插法建表算法描述：头插法建立链表虽然简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者相同，可采用尾插法建表。该方法是将新节点插到当前单链表的尾上。为此需增加一个尾指针r，使之指向当前单链表的结尾。算法：typedef struct NodeElem

7、Type data;struct Node * next;Node,*Linklist;void CreatFromHead(LinkList L)Node *s,*r;r=L;char c;int flag=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)开始顺着链域扫描，用指针

8、p指向当前扫描到的结点，初值指向头结点,用j做计数器，累计当前扫描过的结点数(初值为0)，当j=i时，指针p所指的结点就是要找的第i个结点。算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;Node * Get(LinkList L,int i)int j=0;Node *p;p=L:if(inext!=NULL)&(jnext;j+;if(p-next=NULL) return NULL; /*找不到i*/else return i; /*找到了i*/2） 按值查找算法描述：按值查找是指在单链表中查找是

9、否有节点值等于e的结点，若有的话，则返回首次找到的其值等于e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。 算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;Node *Locate(LinkList L,ElemType key)Node *p;p=L-next;while(p!=NULL)if(p-data=key)return p; /*找到了key*/p=p-next;return NULL; /*没有找到了key*/ 4、 单

10、链表插入操作问题要求：在线性表的第个位置之前插入一个新元素e。算法思想：查找：在单链表中找到第i-1个结点并有指针pre指示。申请：申请新节点s，将其数据域的值置为e；插入挂链：通过修改指针域将新节点s挂入单链表L。 算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;void Inslist(ElemType e,int i,LinkList L)Node *pre,*s;int k;if(i=0) return ERROR;pre=L;k=0;while(pre!=NULL&knext;k+;if(k=

11、i)s=(Node *)malloc(sizeof(Node);s-data=e;s-next=pre-next;pre-next=s;return OK;elseprintf(插入位置不合理);return ERROR;5、 单链表删除问题要求：将线性表的第个元素e删除算法思想：查找：通过计数方式找到第i-1个结点并由指针pre指示；删除第i个结点并释放结点空间。结果：将长度为n的线性表变成长度为n-1 的线性表算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;void DelList(LinkList

12、 L,int i,ElemType *e)Node *pre,*s;int k;if(inext!=NULL&knext;k+;if(pre-next=NULL)printf(删除位置错误);return ERROR;s=pre-next; /*使得删除得第i个位置的指针为s*/pre-next=s-next;*e=s-data;free(s); /*释放被删除的结点所占的内存空间*/return OK;算法应用举例1、 求单链表的长度算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点，从第一个元素开始“数”，一直“数”到最后一个结点(p-next=NULL).算法

13、：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;int ListLength(LinkList L)Node *p;int k=0;p=L:while(p-next!=NULL)p=p-next;k+;return k;2、 求两个集合的差已知：以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在

14、与e相同的元素，则从LA中将其删除。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;void Difference(LinkList LA,LinkList LB)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=

15、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中的元素结点空间，而不要额外申请结点空间。例如，则。算法思想：要求利用现有的表LA和LB中的结点空间来建立新表LC，可通过更改结点的next域来重建新的元素之间的线性关系。为包证新表仍然递增有序，可以利用尾插法建立单

16、链表的方法，只是新表中的结点不用malloc，而只要从表LA和LB中选择合适的点插入新表LC即可。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;LinkList MergeLinkList(LinkList LA,LinkList LB)Node *pa,*pb,*pc;LinkList LC;/*pa和pb分别指向两个单链表LA和LB中的将要判断的结点，pc初值为LC且pc始终指向LC的表尾*/pa=LA-next;pb=LB-next;LC=LA;LC-next=NULL;/*将LC初始置为空表*

17、/pc=LC; /*pc始终指向LC的表尾*/*当两表均未处理完时，选择较小者*/while(pa!=NULL&pb!=NULL)if(pa-datadata)pc-next=pa;pc=pc-next;pa=pa-next;elsepc-next=pb;pc=pc-next;pb=pb-next;if(pa=NULL)/*表B未处理完*/pc-next=pb;else /*表A未处理完*/pc-next=pa;free(LB); /*表C是以表A为基础，所以释放表B*/return LC;2.3.3 循环链表循环链表：循环链表是一个首尾相接的链表。特点：将单链表最后一个结点的指针域由NULL

18、改为指向头结点或线性表中的第一个结点，就得到了单链表形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。 带头结点的循环链表的算法和带头结点的单链表的算法的区别仅在与算法中判别当前结点p是否为尾结点。单链表判别条件为，而循环单链表的判别条件为。例题：有两个带头结点的循环单链表LA、LB，编写算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。算法思想：先找到两个链表LA、LB的表尾，并分别由指针p，q指向它们，然后将第一个链表的尾与第二个链表的第一个结点链接起来，并修改第二表的表尾q，使它指向第一个表的头结点。算法：typedef struct NodeEle

19、mType data;struct Node * next;Node,*LinkList;LinkList merge_1(LinkList LA,LinkList LB)Node *p,*q;p=LA;q=LB;/*寻找A的尾结点，并置为p*/while(p-next!=LA)p=p-next;/*寻找B的尾结点，并置为q*/while(q-next!=LB)q=q-next;/*修改A的尾指针，并使之为B的第一节点*/p-next=LB-next;/*修改B的尾指针，并使之为A的头结点*/q-next=LA;free(LB);return LA;采用上面的方法，需要遍历链表，找到表尾，其执

20、行时间为。若循环单链表设置为尾指针表示，在实现上述合并时，无需循环遍历找尾结点，只需直接修改尾结点的指针域，其执行时间是。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;LinkList merge_2(LinkList RA,LinkList LB)Node *p;p=RA-next; /*记录A的头结点*/RA-next=RB-next-next;free(RB-next);RB-next=p;return RB; /*返回新循环链表的尾指针*/2.3.4 双向链表双向链表：给单链表的每个结点里再增

21、加一个指向其前驱的指针域prior。双链表的结点的结构如下图： prior 前驱指针域数据域后继指针域 data next双链表的结构定义如下：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;设指针p指向双链表中某一点，则有下式成立：1、 双向链表的前插操作算法思想：欲在双向链表第i个结点之前插入一个新的结点，则指针的变化情况如下图：算法： typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleL

22、ist;int DlinkIns(DoubleList L,int i,ElemType e)DNode *p,*s;int k;if(i=0)return ERROR;p=L;k=0;while(p!=NULL&knext;k+;if(p=NULL)printf(插入位置不合理);return ERROR;s=(DNode *)malloc(sizeof(DNode);s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return OK; 2、 双向链表的删除操作算法思想：欲删除双向链表中的第i个结点，则指针的变化情况如下图

23、所示：算法：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;int DlinkDel(DoubleList L,int i,ElemType *e)/*将删除的元素保存到*e中*/DNode *p;int k;if(i=0)return ERROR;p=L;k=0;while(p!=NULL&knext;k+;if(p=NULL)printf(插入位置错误);return ERROR;*e=p-data;p-prior-next=p-next;p-next=p-prior;free(p)

24、;return OK;3、 应用举例例题：已知：设一个循环双链表编写一个算法将链表转换为。算法思想：实际上是交换表中前两个元素的次序。算法：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;void swep(DLinkList L)DNode *p,*q,*r;p=L-next;q=p-next;r=p-prior;p-next=q-next;q-next-prior=p;p-prior=q;q-next=p;q-prior=r;L-next=q;return L;2.4 一元多项式的表

25、示及相加2.4.1 一元多项式的表示一元多项式可按升幂的形式写成：其中，为第项的指数，是指数的项的系数，且。假设是一个一元多项式，则它可以用一个线性表来表示。即：若假设，则两个多项式相加的结果，也可以用线性表来表示：2.4.2 一元多项式的存储1、一元多项式的顺序存储表示2、一元多项式的链式存储表示在链式存储中，对一元多项式只存非零项，则该多项式中每一项由两部分组成(指数项和系数项)，用单链表存储表示的结点结构如下图：系数coef 指数exp指针next结点结构定义如下： typedef struct Polynode int coef; int exp; struct Polynode *n

26、ext; Polynode,* Polylist;建立多项式链表：算法描述：通过键盘输入一组多项式的系数和指数，用尾插法建立一元多项式链表。以输入系数0为结束标志，并约定建立多项式链表时，总是按指数由小到大的顺序排列。算法：typedef struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;Polylist PolyCreate()Polynode *head,*rear,*s;int c,e;/*申请头结点*/head=(Polynode *)malloc(sizeof(Polynode);rear=head;

27、/*rear始终指向最后一个结点*/scanf(%d%d,&c,&e);while(c!=0)/*申请一个新的结点*/s=(Polynode *)malloc(sizeof(Polynode);s-coef=c;s-exp=e;rear-next=s; /*将链表连接起来*/rear=s; /*链表的结尾后移一位*/scanf(%d%d,&c,&e);rear-next=NULL;/*结束链表*/return head;/*返回链表的头结点*/3、 两个多项式相加运算规则：指数相同项的对应系数相加，若不为0，则构成“和多项式”中的一项； 指数不相同的项均按升幂顺序复制到“和多项式” 中。算法思

28、想：设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到以下运算规则： 若，则结点p所指的一项应该是“和多项式”中的一项，令指针p后移。 若，则将两个结点的指数相加，当和不为0时，修改结点p的系数域，释放q结点；当和为0时，应该从polya中删去p结点，同时释放p和q结点。 当，则结点q所指的一项应该是“和多项式”中的一项，将结点q插入在p之前，同时令指针q后移。算法：typedef struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;void PolyAdd(Polylist p

29、olya,Polylist polyb)/*p指向polya的当前比较点，q指向polyb的当前比较点tail指向和多项式的末尾点*/Polynode *p,*q,*tail,*temp;int sum;p=polya-next;q=polyb-next;tail=polya;while(p!=NULL&q!=NULL)if(p-expexp)tail-next=p;tail=p;p=p-next;else if(p-exp=q-exp)sum=p-coef+q-coef;if(sum=0)temp=p;p=p-next;free(p);temp=q;q=q-next;free(q);elsep-coef=sum;tail-next=p;tail=p;p=p-next;temp=q;q=q-next;free(temp);elsetail-next=q;tail=q;q=q-next;if(p!=NULL)tail-next=p;elsetail-next=q;return polya;假设A多项式有M项，B多项式有N项，则上述算法的时间复杂度为。2.5 顺序表和链表的综合比较2.5.1 顺序表和链表的比较