数据结构课堂笔记(di第一~三章)(完整版).doc

一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常有下列4类基本结构：（1）集合-数据元素仅有同属一个关系的关系（2）线性结构-结构中数据元素之间存在一个对一个的关系（3）树形结构-结构中的数据元素之间存在一个对多个的关系（4）图状结构或网状结构-结构中的数据元素之间存在多个对多个的关系五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。（2）逻辑结构六、位bit：在计算机中表示信息的最小单位是二进制的一位七、元素element/节点node：位串八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。类C语言语句：（1）预定义常量和类型：#define TRUE 1 FALSE 0#define OK 1 ERROR 0#define INFEASIBLE -1 OVERFLOW -2(2)数据元素类型ElemType(3)赋值语句：简单赋值 变量名=表达式；串联赋值 变量名1=变量名2=变量名k=表达式；成组赋值 （变量名1，变量名k）=（表达式1，表达式k）； 结构名=结构名； 结构名=（值1，值k）； 变量名=表达式； 变量名起始下标.终止下标= 变量名起始下标.终止下标；交换赋值：变量名变量名；条件赋值：变量名=条件表达式？表达式T：表达式F；（4）选择语句有条件语句1 if（表达式）语句；条件语句2 if（表达式）语句；else语句；开关语句1 switch(表达式)case值1：语句序列1；break; case值n：语句序列n；break;default:语句序列n+1;开关语句2 switch(表达式)case条件1：语句序列1；break; case条件n：语句序列n；break;default:语句序列n+1;(6)循环语句有：for语句 for（赋初值表达式序列；条件；修改表达式序列）语句；while语句 while（条件）语句；do-while语句 do 语句序列； while（条件）；（7）结束语句有函数结束语句 return表达式； return；case结束语句 break；异常结束语句 exit（异常代码）；（8）输入和输出语句有：输入语句 scanf（格式串，变量1，变量n）；输出语句 printf（格式串，表达式1，表达式n）；通常省略格式串。（9）注释单行注释/文字序列（10）基本函数有：求最大值 max（表达式1，表达式n）求最小值 min（表达式1，表达式n）求绝对值 abs（表达式）求不足整数值 floor（表达式）求进位整数值 ceil（表达式）判定文件结束 eof（文件变量）或eof判定行结束 eoln（文件变量）或eoln（11）逻辑运算约定与运算&：对于A&B，当A的值为0时，不再对B求值。或运算|：对于A|B，当A的值为非0时，不再对B求值。算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。（1）有穷性（2）确定性（3）可行性（4）输入（5）输出算法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求线性表：是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。在复杂的线性表中，一个数据元素可以由若干个数据项item组成。在这种情况下，常把数据元素称为记录record，含有大量记录的线性表又称文件file。ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1，n-1时，ai有且仅有一个直接后继，当i=1，n时，ai有且仅有一个直接前驱。线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的第i个数据元素ai的存储位置为LOC（ai）=LOC（a1）+（i-1）*L一般情况下，在第i（1=i=n）个元素之前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。一般情况下，删除第i（1=i=n）个元素时，需从第i+1至第n（共n-i）个元素向前移动一个位置。线性表的链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，成为结点（node）。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点ai(1=inext是指向第i+1个数据元素（结点ai+1）的指针。换句话说，若p-data=ai,则p-next-data=ai+1.由此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是表是非随机存取的存储结构。Status GetElem_L (LinkList L,int i,ElemType&e) /L为带头结点的单链表的头指针 /当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORP=L-next;j=1; /初始化，p指向第一个结点，j为计数器while（p&jnext;+j;If(!p|ji)return ERROR;/第i个元素不存在e=p-data;/取第i个元素不存在e=p-data;/取第i个元素return OK；/GetElem_L算法2.8：比较j和i并后移指针p在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中。根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。假设s为指向结点x指针，则上述指针修改用语句描述为：s-next=p-next;p-next=s;在线性表中删除元素b时，为在单链表中实现元素a、b和c之间的逻辑关系的变化，仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为：p-next=p-next-next；可见，在已知链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。 将两个有序链表并为一个有序链表：线性表的静态单链表存储结构#define MAXSIZE 1000 /链表的最大长度typedef struct ElemType data;int cur;component,SLinkListMAXSIZE;若S为SLinkList型变量，则S0.cur指示第一个结点在数组中的位置，若设i=S0.cur，则Si.data存储线性表的第一个数据元素，且Si.cur指示第二个结点在数组中的位置。一般情况，若第i个分量表示链表的第k个结点，则Si.cur指示第k+1个结点的位置。因此在静态链表中实现线性表的操作和动态链表相似，以整型游标i代替动态指针p，i=Si.cur的操作实为指针后移（类似于p=p-next），例如，在静态链表中实现的定位函数LocateElem 一、线性表：除表中的第一个元素外，其余元素仅有一个前驱。除表中最后一个元素外，其余元素仅有一个后二、线性表的存贮结构1.解决存贮问题2.反映元素之间关系三、线性表的操作：1.插入一个元素2.删除一个元素3.查找一个元素4.排序怎么删除ai？覆盖算不算删除？答：不算。删除正是为了得到。SeqlistDelete(A,n,i)if(in)Printf(“参数非法”);return 0;Elsefor(k=i+1;kn;k+)Ak-1=Ak;n=n-1;return n;栈（heap）五、堆栈（stack）：是一种特殊形式（表的插入和删除）的线性表限定在表的。运行作业1：线性表中元素为整型，以50为界，小于50在左，大于50在右。作业讲解：x=x and ij) j=j-1; if(Ajx) Ai=Aj; i=i+1;while(Aix and xj)i=x)Aj=Ai;jdate=a1;指针p指向对象date=a1，该对象是一个结构体，指向结构体里a1那部分删除a1并把存储空间解放：free（p）； 动态存储结构地址=malloc（大小）；字节free（p）；区别：数组：编译时确定（静态）链表：编译时确定（动态）P=(ElemType*)=malloc(sizeof(ElemType); 改为NODE* 改为NODE因为是无类型指针，所以必须强制转换。Typedef 类型定义struct node NODE（定义为新的类型）二、链表的构造q=1;i-)pdatenext=NULL;把指针设为空指针，替换为qq=p;考虑链表的头指针当ai未插入时：算法：CreatLinkList(n) 构造链表，n为节点q=1;i-)pdatenext=q;q=p;return(p);注：此时p、q一样已被赋值给对方作业4：倒过来。从前节点到后节点。头指针head p=head;从头指针出发，依次输出节点。可用for循环或while循环（不确定循环次数时用）pdata);pnext;三、链表的插入算法：假定：在表中值为x的节点前面插入一个值为y的节点。分析：1.空链2.表中第1个节点的值为x3.表中有一个值为x的节点4.表中没有值为x的节点5.表中有多个值为x的节点。NODE*InsertLinkList(head,x,y)qdatanext=NULL;if(head=NULL)headdate=x)q-next=head;head=q; elser=head;pnext;while(p-data=/x and p=NULL)pnext;if(p=NULL)q-nextnextnext=q;return(head); 假定：删除表中值为x的节点分析：1.空表； 2.第1个节点的值为x； 3.在表中有值为x的节点； 4.在表中没有值为x的节点NODE *=DeleteLinkList(head,x,t) （返回指针）a.值参 call by value b.变参call by addresssdata=x)s=head;headnext;elseq=head; （返回内容不同）pnext;while(p-data=x and p-next=NULL)q=p;pnext;if(p-data=x)snextnext;elseprintf(表中没有值为x的节点)；if(s=NULL)tdata;free(s);return(head); （返回值）四、链式存贮结构的栈五、链式存贮结构的队列六、循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。上为非空表空表循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next为空，而是它们是否等于头指针。但有时候，若在循环链表中设立尾指针而不设头指针。例如将两个线性表合并为一个表时，仅需将一个表的表尾和另一个表的表头相接。当线性表以图的循环链表作存储结构时，这个操作仅需改变两个指针值既可。 两个仅设尾指针的循环链表 两个仅设尾指针的循环链表合并后的表L=(a1,a2,an) ai存在元素双向链表在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。/-线性表的双向链表存储结构-typedef struct DuLNodeElemType data;struct DuLNode *prior;struct DuLNode *next; DuLNode,*DuLinkList;和单链的循环表类似，双向链表也可以有循环表，如图（c）链表中存有两个环，（b）只有一个表头结点的空表。在双向链表中，若d为指向表中某一结点的指针（即d为DuLinkList型变量），则显然有d-next-prior=d-prior-next=d. 结点结构 （b）空的双向循环链表 （c）非空的双向循环列表 在双向链表中删除结点时指针变化状况 在双向链表中插入一个结点时指针变化状况链表的优点：在空间的合理利用上和插入、删除时不需要移动，是线性表的首选存储结构。 缺点：求线性表的长度时不如顺序存储结构插入：值为x的节点前面加入值为y的节点删除值为x的节点：一个指针指向一个整体，指向同个整体的必须是相同的指针，不管是P还是m。八、十字链表NODE *PoliAdd (ah,bh)Pa=ah;Pb=bh;已知头指针分别为ah和bh的两条链。PC=(NODE*)malloc(sizeof(NODE);ST=PC;while(Pa=NULL and Pb=NULL)ctexp,Pb-exp); 假定有compare比较 switch(ct)case:attach(PC,Pa-coof,Pa-exp);Panext;break;case=:mcoof+Pb-coofattach(PC,m,Pa-exp);Pbnext;break;casecoof,pb-exp);Pbnext;break;while循环可能出现一条链结束了一条链还未结束还剩下一节结点，但可能同时结束while(Pa=NULL)attach(PC,Pa-coof,Pa-exp);Panext;while(Pb=NULL)attach(PC,Pb-coof,Pb-exp);Pbnext;该部分算法将剩余部分未加的链挂上去但PC走动，ST仍指向空结点PCnext;free(ST);如图：a. 比较指数的大小b. 比较完后考虑是否相加，还是挂在一条链上从前往后产生链。产生一个结点往上挂。例题：一元多项式相加，前提：不破坏原本两条链，相加求第三条链分析：数据结构必须考虑抵消指数的情况m=0.用项对应结点Compare(a,b)if(ab)if(ab)return();else if(a=b)return(=);else return(=SMAX)printf(overlow);return 0;elseStop=x;top=top+;出栈算法：ElemType Popstack(s,top,bottom)if(top=bottom)printf(overlow);return 0;elsetop=top-1;y=QMAX)printf(Overlow);return 0;elserear=rear+1;Qrear=x;return 1