计算机软件基础(自考本科)(1.8)

计算机软件基础(自考本科)(1.8)一、线性表的概念1.线性表的逻辑结构（1）线性表：是由n（n≥0）个数据节点a0，a1,…，an-1组成的有限序列。（2）线性表的逻辑结构特征：①对于非空线性表：有且仅有一个开始节点，该节点有且仅有一个直接的后继；有且只有一个终结节点，该节点有且仅有一个直接的前驱；其余内部节点有且仅有一个直接前驱和一个直接后继。一、线性表的概念（2）线性表的逻辑结构特征：②同一个线性表中的数据节点具有相同的属性。③线性表长度：线性表中数据节点的个数。2.线性表的存储结构（1）顺序存储结构：顺序表结构；（2）链式存储结构：链表结构；二、顺序表1.顺序表（1）顺序表：把线性表中的数据节点按其逻辑顺序依次存放到计算机内存中的一连续空间中，将这一连续空间称为顺序表。（2）顺序表中数据节点地址的计算Loc(ai)=loc(a0)+i*d(0≤i≤n-1)二、顺序表1.顺序表（3）顺序表C语言描述：structsequenlist{datatypea[listsize];//表示线性表有（a0，a1，...，an-1）intlength;//length表示线性表的实际长度};二、顺序表2.顺序表的基本运算——查找structsequenlist/*构建sequenlist型*/{datatypedata[listsize];intlength;};structsequenlistL;/*定义sequenlist变量L*/intfind(structsequenlistL,datatypex)/*定义find函数*/{inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)return(i);/*如果找到了，则返回数值i*/elsereturn(0);/*如果找不到，则返回数值0*/}二、顺序表一个完整的查找程序：#include<stdio.h>#definelistsize50structsequenlist/*构建sequenlist型*/{ intdata[listsize]; intlength;};structsequenlistL;/*定义sequenlist变量L*/intfind(structsequenlistL,intx)/*定义find函数*/{ inti=0; while(i<L.length&&L.data[i]!=x) i++; if(i<L.length)return(i); elsereturn(0);}二、顺序表一个完整的查找程序（续）：main(){ inti,j,y; structsequenlista; scanf("%d",&a.length);/*输入实际表长*/ scanf("%d",&j);/*输入要查找的数据*/ for(i=0;i<a.length;i++) scanf("%d",&a.data[i]); y=find(a,j); if(y)printf("%d\n",y); elseprintf("nofind");}二、顺序表顺序表查找运算的结论：（1）查找成功的平均查找次数为：(表长+1)/2。（2）时间复杂度：表长越长，查找所消耗时间越多，所以，时间复杂度与n有关，即：T(n)=O(n)。二、顺序表3.顺序表的基本运算——插入step1:判断表是否满？如果已满，则输出“表满”；否则进行第二步；step2:判断要插入的位置是否在表内？如果不在，则输出“位置不对”；否则进行第三步；step3:从第n-1个节点到第i个节点全部后移1位；step5:将顺序表的表长加1；step4:在顺序表的第i个位置插入x；二、顺序表插入运算的类C语言算法：voidinsert(structsequenlistL,datatypex,inti)/*定义insert函数*/{ intj; if(L.length>=listsze)printf("overflow\n"); elseif((i<0)||(i>L.length))printf("positionisnocorrect\n"); else { for(j=L.length-1;j>=i;j--) { L.data[j+1]=L.data[j]; } L.data[i]=x; L.length++; }}二、顺序表一个完整的插入运算程序#include<stdio.h>#definelistsze10structsequenlist/*构建sequenlist型*/{ intdata[listsze]; intlength;};structsequenlistL;二、顺序表一个完整的插入运算程序（续）voidinsert(structsequenlistL,intx,inti)/*定义insert函数*/{ intj; if(L.length>=listsze)printf("overflow\n"); elseif((i<0)||(i>L.length))printf("positionisnocorrect\n"); else { for(j=L.length-1;j>=i;j--) { L.data[j+1]=L.data[j]; } L.data[i]=x; L.length++; for(j=0;j<L.length;j++) printf("%d,",L.data[j]); }}二、顺序表一个完整的插入运算程序（续）main(){ inti,j,y; structsequenlista; scanf("%d",&a.length);/*输入实际表长*/ scanf("%d",&y);/*输入要插入的数据*/ scanf("%d",&j);/*输入要插入数据的位置*/ for(i=0;i<a.length;i++) scanf("%d",&a.data[i]); insert(a,y,j);}二、顺序表顺序表插入运算的结论：（1）在线性表中插入一个数据节点需要移动顺序表的一半节点，即：n/2。（2）时间复杂度：插入运算的时间复杂度与n有关，即：T(n)=O(n)。二、顺序表3.顺序表的基本运算——删除step1:判断表是否为空？如果为空，则输出“无法删除”；否则进行第二步；step2:判断要删除的位置是否在表内？如果不在，则输出“位置不对”；否则进行第三步；step3:从第i+1个节点到第n-1个节点全部前移1位（采用覆盖的形式删除）；step4:将顺序表的表长减去1；二、顺序表删除运算的类C语言算法：voiddelete(structsequenlistL,inti)/*定义delete函数*/{intj;if(L.length==0)printf("Emptylist,cannotdelete!\n");elseif((i<0)||(i>=L.length))printf("positionisnocorrect\n");else { for(j=i+1;j<L.length;j++) { L.data[j-1]=L.data[j]; } L.length--;}二、顺序表一个完整的删除运算程序#include<stdio.h>/*调用头文件“stidio.h”*/#definelistsze10structsequenlist/*构建sequenlist型*/{intdata[listsze];intlength;};structsequenlistL;/*定义sequenlist变量L*/二、顺序表一个完整的删除运算程序（续）voiddelete(structsequenlistL,inti)/*定义delete函数*/{intj;if(L.length==0)printf("Emptylist,cannotdelete!\n");elseif((i<0)||(i>=L.length))printf("positionisnocorrect\n");else{for(j=i+1;j<L.length;j++){ L.data[j-1]=L.data[j];}L.length--;for(j=0;j<L.length;j++)printf("%d,",L.data[j]);}}二、顺序表一个完整的删除运算程序（续）main()/*定义主函数*/{inti,j;structsequenlista;/*定义顺序表a*/scanf("%d",&a.length);/*输入实际表长*/scanf("%d",&j);/*输入要删除数据的位置*/for(i=0;i<a.length;i++)/*依次输入顺序表a的各节点*/scanf("%d",&a.data[i]);delete(a,j);/*调用delete()函数*/}二、顺序表顺序表删除运算的结论：（1）在线性表中删除一个数据节点需要移动顺序表的一半节点，即：n/2。（2）时间复杂度：删除运算的时间复杂度与n有关，即：T(n)=O(n)。三、线性表的链式存储结构1.线性表顺序存储结构与链式存储结构的异同点顺序存储结构链式存储结构存储空间连续的存储空间可以连续，可以不连续（分散）的存储空间节点间的相邻关系逻辑上的相邻关系与存储结构上的相邻关系一致。逻辑上是相邻的，在存储结构上是不相邻的。空间使用在使用前，事先分配存储空间。只在使用时才申请存储空间，使用过后其存储空间可以删除。三、线性表的链式存储结构2.单链表的形态非空表：…abm头节点第一个数据节点最后一个数据节点head空表：头节点headData域next域三、线性表的链式存储结构3.单链表类型定义structnode{ datatypedata;//节点的数据域

structnode*next;//节点的指针区}；5.求单链表的表长(1)单链表的表长：单链表中数据节点的个数（不包括头节点）。(2)算法：intlength(head)//head是指向单链表的头指针{intn=0;//节点个数计数器赋初值0structnode*p;//定义一个node型指针pp=head;//p指针指向表头节点while(p->next!=null)//p指针所指节点不是链表的最后一个节点{p=p->next;//p指针前进一个节点n++;//节点个数加1}return(n)//返回表长n}6.查找运算（find）structnode*find(head,x){structnode*p;p=head->next;//p指针指向第一个数据节点while((p->next!=null)&&(p-data!=x))//p指针所节点不是最后节点，而且其data域的值不为x{p=p->next;//p前进一个节点}if(p->data==x)return(p);//找到了该节点，则返回对应p指针的值elsereturn(null);//没找到该节点，则返回null（空）}7.插入运算（insert）----插入已知地址的节点如：在p指针所指节点后面插入已知地址为s的节点pP->nexts(1)s->next=p->next;(2)p->next=s;7.插入运算（insert）----插入已知内容的节点如：在p指针所指节点后面插入已知内容为x的节点pP->nexts(1)s->next=p->next;(2)P->next=s;s=(structnode)malloc(sizeof(structnode));s->data=x;x8.删除运算（delete）如：删除p指针所指节点的下一个节点pp->next->nextp->nextq=p->next;qq->nextp->next=p->next->next;（或p->next=q->next）free(q);四、单循环链表1.单循环链表的形态非空表：…abmhead空表：headr注意：单链表只能沿着链表从前向后访问表中的各节点，无法找到某节点前面的其他节点；单循环链表可以通过任一节点访问表中的其他节点。四、单循环链表2.单循环链表的删除运算例如：一个单循环链表，没有头指针只有尾指针r，试写出删除尾指针r的前一个节点。a1an-2anra0…an-1四、单循环链表2.单循环链表的删除运算a1an-2anra0…an-1Step1：找出r节点前前的那个节点p；Step2：让q指向p的下一个节点；Step3：从链表中删除q所指向的节点；Step3：回收q。pp->nextqp->next->next四、单循环链表2.单循环链表的删除运算voiddelete(r){structnode*p,*q;//定义两个node型指针p和qp=r->next;//让p指向r的后继节点（给p赋初值）while(p->next->next!=r)//找r节点的前前节点{p=p->next;}q=p->next;//将要删除节点的地址保存到q中p->next=r;//从链表中删除qfree(q);//回收被删除节点q的空间}五、双循环链表1.双循环链表的形态habc非空表：h空表：五、双循环链表2.双循环链表的类型定义每个节点有3个成员：priordatanextprior：左链域，存放直接前驱节点的地址；next：右链域，存放直接后继节点的地址；data：数据域，存放本节点的信息内容。五、双循环链表2.双循环链表的类型定义structnode{datatypedata;//节点的数据域structnode*prior,*next;//直接前驱、后继的指针}3.双循环链表的特点:p->prior->next=p->next->prior=p五、双循环链表4.双循环链表的基本运算----插入例如：在p所指节点的前面插入地址为s的节点。mnxpp->priors(2)(1)(3)(4)五、双循环链表4.双循环链表的基本运算----插入例如：在p所指节点的前面插入地址为s的节点。(1)s->prior=p-prior;(2)s->next=p;(3)p-prior-next=s;(4)p-prior=s;五、双循环链表4.双循环链表的基本运算----删除例如：删除p指针所指的节点pp->priorp->next(1)(2)(1)p->prior->next=p->ne