数据结构考研笔记整理(全).pdfVIP

数据结构考研笔记整理(全)--第1页

数据结构考研笔记整理（全）

一、第二章线性表

●考纲内容

●一、线性表的基本概念

●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑

结构，实现线性表的存储结构为顺序表或者链表

●二、线性表的实现

●1、顺序表

●定义(静态分配)

●#defineMaxSize50\typedefstruct{\ElemTypedata[MaxSize];\int

length;\}SqList;

●定义(动态分配)

●#defineMaxSize50\typedefstrcut{\EleType*data;//指示动态非配

数组的指针\intMaxSize,length;\}SqList;

●c的动态分配语句为

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

●c++动态分配语句为L.data=newElemType[InitSize];

●插入操作

●删除操作

●按值寻找

●2、链表

●单链表

●单链表的定义

●

●头插法建立单链表

●

数据结构考研笔记整理(全)--第1页

数据结构考研笔记整理(全)--第2页

●尾插法建立单链表

●

●按序号查找getElem(LinkListL,inti)和按值查找locateElem(LinkList

L,ElemTypee)

●插入结点（后插）

●p=getElem(L,i-1);//查找插入位置的前驱结点\s.next=p.next;\

p.next=s;

●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s

和p的数据域

●s.next=p.next;\p.next=s.next;\temp=p.data;\p.data=s.data;\

s.data=temp;

●删除结点

●p.getElem(L,i-1);\q=p.next;\p.next=q.next;\free(q);

●双链表（结点中有prior指针和next指针）

●循环链表

●静态链表

数据结构考研笔记整理(全)--第2页

数据结构考研笔记整理(全)--第3页

●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一

个元素的数组下标

●三、线性表的应用

●使用的时候如何选择链表还是顺序表？

●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询

比较多——顺序表

●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法

和查找算