个人收集整理 仅供参考学习第一章 绪论掌握 基本概念1、元素：数据基本单位。2、逻辑结构 定义：元素及关系，与计算机无关，只是实际问题的数学抽象表示。 分类：集合、线性结构、树、图3、存储结构 定义：逻辑结构在计算机中的表示（内存） 分类：顺序存储（数组）、链式存储（链表）4、算法及效率 常见的基础算法 定义：（计算机）解决问题的有限步骤 效率度量：时间复杂度、空间复杂度第二章 线性表第一节 线性表逻辑结构1、 定义：由n（n=0）个元素组成的有限序列。n为0，空表，n0时，Lists=(a1,a2,an),ai称为元素，称为序偶，或前驱和后继关系2、 操作：插入、删除、排序、查找等第二节 顺序表1、 定义：用物理地址连续的一段内存存储线性表中逻辑相邻的元素，这种存储结构称为顺序表。2、 C+的存储实现const int MaxSize=100; /表示表中存储元素的最大值T dataMaxSize; /数组data用来存储元素，以整型为例int length; /length值记录表data中存储元素的实际个数3、 操作（常见算法）1） 插入：已知表中length个元素已经存在，实现在表的i位置插入x算法基本思想：A） 表满不插入B） 位置i是否合法C） an，ai依次后移D） x插入E） n值加1算法实现：C+描述（函数）templat void List:Insert（int i， int x） int j； if （length=MaxSize） throw“表满，不能插入”； if (ilength+1) throw“插入位置不合法”； for (j=length-1;j=i-1;j-) dataj+1=dataj; /元素后移 ri=x; /元素插入 length+; /表长增1算法效率：表长为n的顺序表，i位置插入数据，需要（n-i+1）个元素后移等概率插入条件下，平均移动元素的次数=PiMi=1/(n+1)(n+(n-1)+1+0)=n/2即：算法的平均时间复杂度为O(n);2） 删除：已知表中n个元素已经存在，实现在表的i位置删除略3）逆置：将表中元素反向存储template void List:Reverse（） int low,high;low=0;high=length-1;while(lowhigh) T t; t=datalow; datalow=datahigh; datahigh=t; low+； high-; 第三节 链式存储1、定义：用物理（内存）地址任意的存储单元存储逻辑相邻的元素，元素间的逻辑关系通过各个结点的指针信息来体现。2、C+存储实现（以单向链表为例）结点结构如下(C+结构类型)：datanext其中data存储元素信息，next存储逻辑关系的后继结点地址非空表firsta1a2an/空表first除特殊说明外，一般均以带头结点的链表为例实现相关操作，算法设计简单first为头指针，用来指示头结点地址。结点（结构类型）的C+描述：template struct NodeT data；/data存储元素信息Node *next；/next存储逻辑关系的后继结点地址;4、 算法设计举例1） 链表的遍历：按逻辑次序依次输出表中元素template void LinkList:Visit( )Node *p;p=first-next;while(p!=NULL) coutdatanext;2） 链表插入(在非递增有序表中插入元素x，使序列仍然有序)算法基本思想：a） 查找插入位置*p（在其后插入）b） 插入xtemplate void LinkList:Insert(T x) Node *p,*s; p=first; while(p-next &p-next-data=x) p=p-next; /查找插入位置 s= new Node; /为x元素申请结点空间 s-data=x; s-next=p-next; /在结点*p后插入结点*s p-next=s;引申：有序链表的构造(删除)template void LinkList:Create( ) int n=10; for(int i=1;i=n;i+) int x; coutx; Insert(x); 3） 逆置算法：将表中元素逆序存储template void LinkList:Reverse( ) Node*p,*s; p=first-next; first-next=NULL;/拆开 while(p!=NULL) s=p; /1 p=p-next; /2 指针后移 s-next=first-next; /3 *first后插入*s first-next=s; /4 4） 假设链表元素为正整型，删除所有偶数思考：设表中元素为字符，删除所有元素值为大写字母的结点 template void LinkList:Delete( ) Node*p,*s; p=first; while (p-next) if （p-next-data%2）/判断*p的后继结点，若为奇数p=p-next; /保留结点，指针后移 else /偶数删除 s=p-next; /删除*p的下一个结点 p-next=s-next; delete s; /释放s所指结点所占内存 5）已知一个正整数链表，将链表分解，其中一个表A全为奇数，另一个表B为偶数/Separate 设置为类LinkList的友元函数template void LinkList:Seperate(LinkList &A,LinkList &B)/ 链表的拆分Node*p,*s; p=A.first; while (p-next) if （p-next-data%2）/判断*p的后继结点，若为奇数p=p-next; /保留A表中，指针后移 else /从A中删除结点，插入到B表头结点之后 s=p-next; /（1）偶数结点从A中删除 p-next=s-next; /(2) s-next=B.first-next; /(3)插入B表头后 B.first-next=s; /(4) （6）将两个非递减有序表A,B合并为一个有序表A/Merge设置为类LinkList的友元函数template void LinkList:Merge(LinkList &A,LinkList &B)/链表合并 Node *s1,*s2,*rear; s1=A.first-next;s2=B.first-next;A.first-next=NULL;B.first-next=NULL;rear=A.first;while(s1&s2)/当两个表均非空时if(s1-datadata)rear-next=s1; s1=s1-next;rear=rear-next; elserear-next=s2; s2=s2-next;rear=rear-next;if(s1)/s1中剩余一些大的结点rear-next=s1; /链接表尾elserear-next=s2;（7）完整的程序示例#include using namespace std;template struct NodeT data; /data存储元素信息Node *next; /next存储逻辑关系的后继结点地址;template class LinkListpublic:LinkList() /构造仅有头结点的 空表first=new Node;first-next=NULL;void Visit();void Insert(T x);void Delete();void Create();void Reverse(); private:Node *first;/1）链表的遍历：按逻辑次序依次输出表中元素template void LinkList:Visit( )Node *p;p=first-next;while(p!=NULL)coutdatanext;coutendl;/2）链表插入(在非递增有序表中插入元素x，使序列仍然有序)template void LinkList:Insert(T