完整版数据结构知识点汇总

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

2、序存储结构是指用一组地址连续的存储单元依次存 储线性表中的各个元素,使得线性表中在逻辑上相邻的数据元素存储 在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反 映数据元素之间逻辑上的相邻关系.采用顺序存储结构的线性表通常 称为顺序表.将线性表归纳为：关系线性化,节点顺序存.假定顺序表中有个元素,每个元素占k个单元,第一个元素的 地址为 c(q),那么可通过如下公式计算出第i个元素的地址 Loccii)：Zz?c(a,) = Loc(a1) + (z 1) x其中,c(4)称为基地址.线性存储结构的C语言定义#define MAXSIZE 100typedef stmct(ElemTy

3、pe elemMAXSIZE; /*ElemType 可 '为 mt, chai 等*/int last; /*记录线性表中最后一个元素在数组elem中的位置(下标值)*/ JSeqlist;上述为定义一个结构体,结构名为Seqhst.知识延伸(typedef) (C课本鸟3.用typedef声明新类型名)2.2.2 线性表顺序存储结构上的根本运算线性表的根本运算1、查找操作2、插入操作3、删除操作4、顺序表合并算法线性表顺序存储结构的优缺点分析2.3 线性表的链式存储链表定义：采用链式存储结构的线性表称为链表.链表的分类:1按实现角度看：链表可分为动态链表和静态链表.2按链接方式的角

4、度看：链表可分为单链表、循环链表和双链表.2.3.1 单链表2.3.2 1单链表结点:存储线性表的每个数据元素值的信息与元素间逻 辑关系即后继结点地址信息的两局部存储映象 单链表：每个结点只有一个指针域的链表.包括数据域和指针域至储结点的值洱数据域指针域U存储数据匹素的直受型的地理 头指针：指向链表头结点的霜针QH 小,b1cQ-dCE>fA单链表的存储结构描述typedef struct Node ElemType data；struct Node * next；Node, *L i nkLi st；2.3.3 单链表上的根本操作线性表的根本运算1、初始化单链表IiutList(Lii

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

6、mType data;stiuct Node * next;Node,*Luiklist; /*LmkList 为结构指针类型*/LinkList与Node *同为结构指针类型,这两种类型是等价的.通常习惯上用 LmkList说明指针变量,强调他是某个单链表的头指针变量.例如,使用定义 LmkListL,那么L为单链表的头指针,从而提升程序的可读性.用Node*来定义 指向单链表中节点的指针,例如,Node *p,那么p为指向单链表中节点的指针变 量.算法：typedef stmct Node(ElemType data;stmct Node * next;Node,*LHiklist;voi

7、d CreatFroniHead(LinkList L)(Node *s;chai c;int flag=l;vvhile(flag)(c=getcharO；if(c!=$)(s=(Node *)malloc(sizeof(Node);s->data=c;s->next=L->next;L->next=s;)else flag=0;2)尾插法建表算法描述：头插法建立链表虽然简单,但生成的链表中结点的次 序和输入的顺序相反.假设希望二者相同,可采用尾插法建表.该方法 是将新节点插到当前单链表的尾上.为此需增加一个尾指针r,使之 指向当前单链表的结尾.算法：typedef

8、stnict NodeElemType data; stiuct Node * next;Node,*Lniklist;void CieatFroniHead(LiiikList L)(Node *s,*r;r=L;chai c;int flag=l;wliile(flag)(c=getcharO； if(c!=$) (s=(Node 31 )malloc(sizeof(Node);s->data=c;r->next=s;r=s;)else(flag=0;r->next=NULL;) 3、单链表查找1)按序号查找算法描述：设带头结点的单链表的长度为n,要查找表中第1个结 点,

9、那么需要从单链表的头指针L出发,从头结点(L>next)开始顺着链 域扫描,用指针p指向当前扫描到的结点,初值指向头结点,用j做计 数器,累计当前扫描过的结点数(初值为0),当户】时,指针p所指的 结点就是要找的第1个结点.算法：typedef stmct Node(ElemType data;stmct Node * next;Node,*Luiklist;Node * Get(LmkList Lant i)mt j=0;Node *p;p=Lif<i<=0) letuin NULL; /* 找的序号太小*/ wlule(p->next!=NULL)&&

10、;(j<i)(p=p->next;if(p->next=NULL) reuun NULL; /*找不到 i*/elsereturn i; /*找到了 i*/2)按值查找算法描述：按值查找是指在单链表中查找是否有节点值等于e的 结点,假设有的话,那么返回首次找到的其值等于e的结点的存储位置, 否那么返回NULL.查找过程从单链表的头指针指向的头结点出发,顺 着链逐个将结点的值和给定值e作比较.算法：typedef stnict Node(ElemType data;stnict Node * next;Node,*Luiklist;Node *Locate(LinkList L

11、.ElemType key)(Node *p;p=L->next;wlule(p?=NULL)(if(p->data=key)retuin p; /*找到了 key*/ p=p->next;)i-eturn NULL; /*没有找到 了 key*/问题要求：在线性表的第Q</</? + 1个位置之前插入一个新元素eo算法思想：查找：在单链表中找到第卜1个结点并有指针pie指示.申请：申请新节点s,将其数据域的值置为e；0插入挂链：通过修改指针域将新节点s挂入单链表L.算法：typedef stnict Node(ElemType data;stnict Node

12、* next;Node,*Luiklist;void Iiislist(ElemType e.mt uLiiikList L) (Node *pre/s;int k.if(i<=0) letuin ERROR,pre=L;k=0;while(pre?=NULL&&k<i-1) (pre=pre->next;k十十；if(k=i)(s=(Node *)malloc(sizeof(Node);s->data=e;s->next=pie->next;pie->next=s; renirn OK; else(pnntf("插入位置不合

13、理);return ERROR,)问题要求：将线性表的第汜+1个元素e删除算法思想：查找：通过计数方式找到第il个结点并由指针pre指示；删除第1个结点并释放结点空间.结果：将长度为n的线性表q,L变成长度为nl的线性表,L必_9+工,算法:typedef stnict Node(ElemType data;stiuct Node * next;Node,*Luiklist;void DelList(LmkList L,mt tEleinType *e)(Node *pre,*s;int k.if(i<=0) letuin ERROR,pre=L;k=0;/*按序号查找第1个位置*/ v

14、vhile(pie->next! =NULL&&k<i)(pie=pre->next;k"if(pie->next=NULL)pimtfC删除位置错误renun ERROR,s=pre->next; /*使得删除得第i个位置的指针为s*/ pie-iiext=s-> next;*e=s->data;frees; /*释放被删除的结点所占的内存空间*/ return OK:算法应用举例1、求单链表的长度算法描述：可以采用“数结点的方法来求出单链表的长度,用指针P依次 指向各个结点,从第一个元素开始“数,一直“数到最后一个结 点(

15、p->next=NULL).算法：typedef stnict NodeElemType data;stnict Node * next;Node,*LuikList;int ListLength(LinkList L)(Node *p;int k=0;P=L-while(p->next !=NULL) (p=p->next;k+;)retxnn k;)2、求两个集合的差：以单链表表示集合,假设集合A用单链表LA表示,集合 B用单链表LB表示,设计算法求两个集合的差,即AB.算法思想：由集合运算的规那么可知,集合的差A-B中包含所有属于集合A而 不属于集合B的元素.具体做法是

16、,对于集合A中的每个元素e,在 集合B的链表LB中进行查找,假设存在与e相同的元素,那么从LA中 将其删除.算法：typedef stmct NodeElemType data;stmct Node * next;Node,*LuikList;void Difference(LnikList LA,LuikList LB)(Node *p,*q,*pre,*r;pre=LA;p=LA->next;vvhile(p?-NULL)(q=LB->next;while(p->data! =q->data&&q!=NULL) /* 查找有无相同元素*/ q=q-&

17、gt;next;ife>data=q->data) /* 有相同元素*/r=p；pie->next=p>next;/* 本来 pie->next=p,现改为 pie->next=p->next*/ p=p->next; /* F 一 次判断 p->next*/ free(r); /*释放被删除的元素的空间*/)else( pre=p; /* 也可写 为 pie=pre->next*/ p=p->next;)3、有两个单链表LA和LB,其元素均为非递减有序排列,编写一个算法,将他们合并成一个单链表LC,要求LC也是非递减有序排列.

18、要求：新表LC利用现有的表LA和LB中的元素结点空间,而 不要额外申请结点空间.例如L4 = (2,2,3)" = (133,4),那么 3 = (122,3,3,3,4).算法思想：要求利用现有的表LA和LB中的结点空间来建立新表LC,可通过更改结点的next域来重建新的兀素之间的线性关系.为包证新表仍然递增有序,可以利用尾插法建立单链表的方法,只是 新表中的结点不用malloc,而只要从表LA和LB中选择适宜的点插 入新表LC即可.算法：typedef stmct Node(ElemType data;stmct Node * next;Node,*LuikList;LnikLi

19、st MergeLHikList(LnikList LA.LnikList LB)(Node *pa/ pb/pc;LiiikList LC;/*pa和pb分别指向两个单链表LA和LB中的将要判断 的结点,pc初值为LC且pc始终指向LC的表尾*/ pa=LA->next;pb=LB->next;LC=LA;LC->next=NULL; /*将LC初始置为空表*/pc=LC; /*pc始终指向LC的表尾*/*当两表均未处理完时,选择较小者*/while(pa ,=NULL&&pb! =NULL)(if(pa->data<=pb->data)p

20、c->next=pa;pc=pc->next;pa=pa->next; elsepc->next=pb;pc=pc->next;pb=pb->next;)ifQa=NULL)/*表B未处理完*/ pc->next=pb;else/*表A未处理完*/pc->next=pa;fiee(LB);/*表C是以表A为根底,所以释放表B*/ return LC;)2.3.4 循环链表循环链表：循环链表是一个首尾相接的链表.特点：将单链表最后一个结点的指针域由NULL改为指向头结 点或线性表中的第一个结点,就得到了单链表形式的循环链表,并称 为循环单链表.在循

21、环单链表中,表中所有结点被链在一个环上.带头结点的循环链表的算法和带头结点的单链表的算法的区别 仅在与算法中判别当前结点P是否为尾结点.单链表判别条件为 p! = NULL or p- > next! = NULL ,而循环单链表的判别条件为p = L or p-> next ? = L o例题：有两个带头结点的循环单链表LA、LB,编写算法,将两 个循环单链表合并为一个循环单链表,其头指针为LA.算法思想：先找到两个链表LA、LB的表尾,并分别由指针p, q 指向它们,然后将第一个链表的尾与第二个链表的第一个结点链接起 来,并修改第二表的表尾q,使它指向第一个表的头结点.算法:t

22、ypedef stnict Node(ElemType data;stnict Node * next;Node,*LnikList;LiiikList merge_ 1 (LnikList LA.LnikList LB)(Node *pq,p=LA;q=LB;/*寻找A的尾结点,并置为p*/while(p->next!=L A)p=p->next;/*寻找B的尾结点,并置为q*/ while(q->next?=LB)六修改A的尾指针,并使之为B的第一节点*/p->next=LB->next;/*修改B的尾指针,并使之为A的头结点*/q->next=LA.

23、fiee(LB);retimi LA;采用上面的方法,需要遍历链表,找到表尾,其执行时间为.().假设循环单链表设置为尾指针表示,在实现上述合并时,无需循环 遍历找尾结点,只需直接修改尾结点的指针域,其执行时间是.(1).算法：typedef stmct Node(ElemType data;stmct Node * next;Node,*LnikList;LnikList merge_2(LmkList RAXinkList LB)(Node *p;p=RA >next; /*记录A的头结点*/RA->next=RB >next->next;fiee(RB->n

24、ext);RB->next=p;letuniRB. /*返回新循环链表的尾指针*/2.3.5 双向链表双向链表：给单链表的每个结点里再增加一个指向其前驱的指针 域prior.双链表的结点的结构如以下图:双链表的结构定义如下：typedef stmct DNode(ElemType data;stmct DNode *:pnoi;*next; DNode/DoubleList;设指针p指向双链表中某一点,那么有下式成立:p- > prior- > next = p <p p-> next- > prior1、双向链表的前插操作算法思想：欲在双向链表第i个结点之

25、前插入一个新的结点,那么指针的变化情况如以下图：算法：typedef stmct DNode(ElemType data;stmct DNode " pnor/next; DNode,*DoubleList;int DluikIns(DoubleList Ljnt hElemType e) (DNode *p,*s;int k,if(i<=0)renirn ERROR;p=L;k=0;vvlule(p! =NULL&&k<i)(p=p->next;k+；)if(p=NULL)printf("插入位置不合理"); lenun ERR

26、OR.)s=(DNode *)malloc(sizeof(DNode);s->data=e;s->piior=p->pnoi;p->prior->next=s;s->next=p;p->pnor=s;letuin OK,)2、双向链表的删除操作算法思想；欲删除双向链表中的第i个结点,那么指针的变化情况如以下图所示:算法：typedef stnict DNode(ElemType data;stnict DNode *pnot,*next; DNode,* DoubleList;int DlmkDel(DoubleList Ljnt i,ElemType

27、 *e)/*将删除的元素保存到*e中*/(DNode *p;mt k;renun ERROR.p=L;k=0;vvhile(p !=NULL&&k<i) (p=p->next;k-K-;)if(p=NULL)pnntfC插入位置错误)return ERROR.)*e=p->data;p->prior->next=p->next;p->next=p->piioi;free(p);retuin OK;)3、应用举例例题：设一个循环双链表L = 力cd)编写一个算法将链表 转换为 L = (b,a,c,d).算法思想：实际上是交换表中前

28、两个元素的次序.算法：typedef stmct DNode(ElemType data;stmct DNode *pnor,*next; DNode,*DoubleList;void swep(DLiiikList L)(DNode *p,*q,*r;p=L->next;q=p->next;r=p->pnor;p->next=q->next;q->next->pnor=p;p->pnoi-q;q->next=p;q->pnor=r;L->next=q;letuin L;2.4 一元多项式的表示及相加2.4.1 一元多项式的表示

29、一元多项式可按开耳的形式写成:P (X) = Po + M + Pl + L + P“x其中,为第i项的指数,P,是指数,的项的系数,且l<e. <e. <L <e 假设&*是一个一元多项式,那么它可以用一个线性表.来表示.即:0 = %M,%,l 4假设假设用,那么两个多项式相加的结果4.=匕.+.“3,也可 以用线性表R来表示：R = (Po + %Pi + 4,P2 + %,L,+%, P,iL,p“)2.4.2 一元多项式的存储1、一元多项式的顺序存储表示,只存储各项的系数,存储位置下标对应其指数项 一适于非零系数多的多项式系数与指数均存入顺序表旦一适于

30、零项很多,且指数较大 p2 22、一元多项式的链式存储表示在链式存储中,对元多项式只存非零项,那么该多项式中每项由两局部组成指数项和系数项,用单链表存储表示的结点结构如卜 图：系数coef指数exp指针next结点结构定义如下：typedef stiuct Polyiiodemt coef;mt exp;stmct Polyiiode *next;Polynode,* Polylist;建立多项式链表：算法描述：通过键盘输入一组多项式的系数和指数,用尾插法建 立一元多项式链表.以输入系数0为结束标志,并约定建立多项式链 表时,总是按指数由小到大的顺序排列.算法：typedef stmct Po

31、lynodeint coef;int exp;Polyiiode *next; Polyiiode/1 Polvlist;Polylist PolyCreate()Polyiiode *head/reai;*s;int c,e;/*申请头结点*/head=(Polyiiode *)malloc(sizeof(Polyiiode);real-head, /*reai始终指向最后一个结点*/scanf(1,%d%d,&c,&e);while© =0)(/*申请一个新的结点7s=(Polyiiode *)malloc(sizeof(Polyiiode);s->coef

32、=c;s->exp=e;rear->next=s; /*将链表连接起来*/ rear=s; /*链表的结尾后移一位*/scanf(M%d%du,&c,&e);)ieai->next=NULL;/* 结束链表*/ renmi head;/*返回链表的头结点*/ 3、两个多项式相加运算规那么：指数相同项的对应系数相加,假设不为0,那么构成“和 多项式中的一项；指数不相同的项均按升基顺序复制到“和多项式 中.算法思想：设p、q分别指向单链表polya和polyb的当前项,比 较p、q结点的指数项,由此得到以下运算规那么： 假设p->cxp V 4-exp,那么

33、结点p所指的一项应该是“和多项 式中的一项,令指针p后移. 假设p->exp = 4->exp,那么将两个结点的指数相加,当和不为 0时,修改结点p的系数域,释放q结点；当和为0时,应该从polya 中删去p结点,同时释放p和q结点.当> uxp > q > exp, 那么结点q所指的一项应该是“和多项 式中的一项,将结点q插入在p之前,同时令指针q后移.算法：typedef stmet Polynode(int coef;uit exp,Polynode *next;Polynode,*Polylist;void PolyAdd(Polylist polya,P

34、olylist polyb)(/*p指向polva的当前比较点,q指向polyb的当 前比较点tail指向和多项式的末尾点*/Polynode *p,!kq,*tail,*temp;uit sum;p=polya->next;q=polyb->next;tail=polya;while(pf=NULL&&q?=NULL)if(p->exp<q->exp)(tail->next=p;tail=p;p=p->next;)else if(p->exp=q->exp)(sum=p>coef-q->coef;if(sum=

35、0)(temp=p;p=p->next;fiee(p);temp=q;q=q->next;fiee(q);)else(p->coef=sum;tail->next=p;tail=p;p=p->next;temp=q;q=q->next; fiee(temp);)else(tail->next=q, tail=q;q=q->next;)if(p!=NULL)tail->next=p;elsetail->next=q;return polya;假设A多项式有M项,B多项式有N项,那么上述算法的时间复 杂度为O(M + N).2.5 顺序表

36、和链表的综合比较2.5.1 顺序表和链表的比较(课本基于空间的考虑顺序表的存储空间是静态分配的,在程序执行之前必须明确规定它 的存储规模.在静态链表中,初始存储池虽然也是静态分配的,但假设同 时存在假设干个结点类型相同的链表,那么它们可以共享空间,动态链表的 存储空间是动态分配的,只要内存空间尚有空闲,就不会产生溢出.因此,当线性表的长度变化较大,难以估计其存储规模时,采用动 态链表作为存储结构较好.存储密度(Storage Density)是指结点数据本身所占的存储曷和 整个结点结构所占的存储量之比.一般地,存储密度越大,存储空间的 利用率就高.显然,顺序表的存储密度为1,而链表的存储密度小

37、于1基于时间的考虑顺序表是由向量实现的,它是一种随机存取结构,对表中任一结点 都可以在0 (1)时间内直接地存取,而链表中的结点,需从头指针起顺 假设疑找才能取得,因此,假设线性表的操作主要是进行查找,很少做插入 和删除时,宜采用顺序表做存储结构.在链表中的任何位置上进行插入和删除,都只需要修改指针a而在 顺序表中进行插入和删除,平均要移动表中近一半的结点,尤其是当每 个结点的信息量较大时,移动结点的时间开销就相当可观因此,对于 频繁进行插入和删除的线性表,宜采用链表做存储结构.假设表的插入和 删除主要发生在表的首尾两端,那么宜采用尾指针表示的单循环链表0基于语言的考虑在没有提供指针类型的高级

38、语言环镜中,假设要采用链表结构,那么可 以使用光标实现的静态链表.虽然静态链关在存储分配上有缺乏之处, 但它是和动态链表一样,具有插入和删除方便的特点.值得指出的是,即使是对那些具有指针类型的语言,静态链表也有 其用武之地.特别是当线性表的长度不变,仅需改变结点之间的相对关 系时,静态链表比动态链表可能更方便.2.5.2 线性表链式存储方式的比较作名称找首元素结点找表尾结点找P结点前驱结点带头结点单伍表LL->next时间消耗0.一重循环时间消耗0 5顺P结点的ne x t域无法 找到P结点的前驱带头结点循环单 徒表头指针LL->next 时间消耗.一重循环时间消耗0n顺P结点的n

39、ext域可以 找到P结点的前驱时间消耗0.带尾指针的循环单链表RR->next0(1)R时间消耗0 0顺P结点的next域可以 找到P结点的前驱时间消耗0M带头结点双向循 环佳表LL->next0(1)L->pr ior 时间消耗0P->pr ior 时间消耗0(1)2.6 总结与提升2.6.1 主要知识点线性表的特征线性表中每个数据元素有且仅有一个直接前驱和直接后继,第一 个结点无前驱,最后一个结点无后继.线性表的存储方式线性表在计算机中的存储方式有顺序存储和链式存储.线性表的顺序存储顺序表：采用静态分配方式,借助于C语言 的数组类型,申请一组连续的地址空间,依次存放

40、表中元素,其逻辑 次序隐含在存储顺序中.线性表的链式存储链表：采用动态分配方式,借助于C语言的 指针类型,动态申请与动态释放地址空间,故链表中的各结点的物理 存储可以是不连续的.单链表的操作特点1顺链操作技术：从“头开始,访问单链表L中结点ip 指向该结点时,由于第1个结点的地址在第个结点pre指向该结 点,为p的前驱的指针域中存放,查找必须从单链表的“首结点 开始p=L;通过p=p->next并辅助计数器来实现.2指针保存技术：通过对第i个结点进行插入、删除等操作 时,需要对第1-1个结点的指针域进行链址操作pre,iiext,因此在 处理过程中始终需要维持当前指针p与其前驱指针pre

41、的关系,将这 种技术简称为“指针保存技术.链表处理中的相关技术1单链表与多重链表的差异在于指针域的个数.（2） 一般链表与循环链表的差异在于是否首尾相接,将非空表、 空表等多种情况统一处理,以方便运算.3判断当前结点p是否是表尾.一般链表中,p结点是表尾 结点的条件是：该结点的后继指针值为空指针,即p->next=NULL; 循环链表中,p结点是表尾结点的条件是：该结点的后继指针值为头 指针值,即 p->next=head.4链表的表长度并未显示保存.由于链表是动态生成的结构, 其长度要通过顺链行找到表尾得到.因此在处理链表时,往往是以当 前处理位置是否是表尾作为限制条件,而不是以表长度n作为限制条 件.2.6.2 典型例题例1：分解顺序表为奇偶两局部顺序表L中的数据元素类型为int.设计算法将其调整为左 右两局部,左边的元素即排在前面的均为奇数,右边的所有元素即 排在后面的)均为偶数,并要求算法的时间复杂度为O(n),空间复杂度 为0.问题分析：将位于表尾左半局部的偶数与位于表右半局部的奇数通过一个 辅助变量进行交换.设置两个位置指示器i和j, i的初值为0, j的初值为LAlast.当为偶数,为奇数是,那么将L->elem国与L->elemj交换否那么,L>elemi为奇数,i-H-, 1>©1601口为偶数,).这样既可