计算机软件基础(自考8)

计算机软件基础第二篇数据结构基础第八章

线性表（linearlist）一、线性表的概念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）用一维数组描述顺序表#defineM100/*假定顺序表最大长度为M*/struct{int

data[M];

/*假定各数据节点均为整型*/

int

n;

/*n代表线性表表长*/}L;/*用L代表线性表*/二、顺序表2.顺序表的基本运算——查找intloca(L[],n){i=0;

while(L[i]!=x&&i<=n-1)i++;

if(i>n-1)return(-1);/*找不到x*/

elsereturn(i);/*找到了x，返回下标位置i*/}例8-1在长度为n的线性表L中顺序查找内容为X的节点。要求：写出类C语言算法，求成功的平均查找长度及时间复杂度T(n)。二、顺序表一个完整的查找程序：#include<stdio.h>#definelistsize50struct

sequenlist

/*构建sequenlist型*/

{

int

data[listsize];

intlength;};struct

sequenlistL;/*定义sequenlist变量L*/int

find(struct

sequenlistL,intx)/*定义find函数*/{

inti=0;

while(i<L.length&&L.data[i]!=x) i++;

if(i<L.length)return(i); elsereturn(0);}二、顺序表一个完整的查找程序（续）：main(){

int

i,j,y;

struct

sequenlista;

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；二、顺序表例8-2在长度为n的线性表L中第i(0≤i≤n)个位置上插入内容为x的数据节点。要求：写出类c语言算法，求节点平均移动次数及时间复杂度T(n)。voidinse(L[]，i，x){if(n==m)满，无法插入；

else{for(k=n-1；k>=i；k--)L[k+1]=L[k]；/*后移*/

L[i]=x；/*插入x*/

n++；/*表长加1*/

}}二、顺序表一个完整的插入运算程序#include<stdio.h>#definelistsze10struct

sequenlist

/*构建sequenlist型*/

{

int

data[listsze];

intlength;};struct

sequenlistL;二、顺序表一个完整的插入运算程序（续）voidinsert(struct

sequenlistL,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(){

int

i,j,y;

struct

sequenlista;

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；二、顺序表

例8-3在表长为n的线性表L中删除第i(0≤i≤n一1)个节点。要求：写出类c语言算法，求节点平均移动次数及时间复杂度T(n)。

voiddele(L[],i){if(n==0)表空，无法删；

else{for(k=i+1；k<=n-1；k++)L[k-1]=L[k]；/*前移*/

n--;/*表长减1*/

}}二、顺序表一个完整的删除运算程序#include<stdio.h>/*调用头文件"stidio.h"

*/#definelistsze10struct

sequenlist

/*构建sequenlist型*/

{

int

data[listsze];

intlength;};struct

sequenlistL;/*定义sequenlist变量L*/二、顺序表一个完整的删除运算程序（续）voiddelete(struct

sequenlistL,inti)/*定义delete函数*/{

intj;

if(L.length==0)printf("Empty

list,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()/*定义主函数*/{

int

i,j;

struct

sequenlista;/*定义顺序表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.单链表的形态非空表：…abm头节点第一个数据节点最后一个数据节点head空表：头节点headData域next域三、线性表的链式存储结构2.线性表顺序存储结构与链式存储结构的异同点顺序存储结构链式存储结构存储空间连续的存储空间可以连续，可以不连续（分散）的存储空间节点间的相邻关系逻辑上的相邻关系与存储结构上的相邻关系一致。逻辑上是相邻的，在存储结构上是不相邻的。空间使用在使用前，事先分配存储空间。只在使用时才申请存储空间，使用过后其存储空间可以删除。三、线性表的链式存储结构3.单链表运算符号的说明1）p->data，p指针所指节点的data值2）p->next，p指针所指节点的next值，即下一个节点的地址3）p->next->data

，p的下一个节点的data值4）p->next->next

，p的下下个节点的地址5）p=p->next，让p指针指向下一个节点（p指针前进一个节点)6）p->next==null，p所指节点为单链表的最后一个节点7）p=(类型名*)malloc(sizeof(类型名));申请节点空间，p指向其首地址8）free(p)回收p所指节点的空间4.单链表上的简单运算例8-4求单链表的表长（不包括表头节点）。intlength(head)//head是指向单链表的头指针{

intn=0;//节点个数计数器赋初值0

structnode*p;//定义一个node型指针pp=head;//p指针指向表头节点

while(p->next!=null)//p不为最后一个节点就循环

{p=p->next;//p指针前进一个节点n++;//节点个数加1}return(n)//返回表长n}例8-5在单链表中查找内容为x的节点（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：让p指向q的下一个节点；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;//从链表中删除q

free(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->next;(2)p->next->prior=p->prior;(3)free(p);六、链表的建立1.尾插法依次输入abc时，以尾插法建立的单链表为：headab2.头插法依次输入abc时，以头插法建立的单链表为：cheadcba例8-10依次输入一串字符"abc"，以"*"作为结束标志，建立并输出如下单链表：#defineLENsizeof(structstu10)#include<stdi0.h>structstu10/*定义一个具有data域和next域的单链表节点结构*/{chardata；

structstul0*next；}*head，*P；/*为指向单链表头节点的指针，P为指向各节点的指针*/Structstu10*f810()/*定义一个返回单链表头地址的指针函数*/{stmctstul0*r；/*r为指向单链表各节点的指针*/Charch;head=(structstu10*)malloc(LEN)；/*申请一个表头节点head*/r=head；/*开始r指向head所指节点，即表头节点*/六、链表的建立while((ch=getchar())!=‘*')/*输入字符*/{P=(structstu10*)malloc(LEN)；/*申请一个节点P*/

p->data=ch；/*把ch存入data域*/

p->next=NULL；/*P的链域置空*/

r->next=P：/*把P链入r的链中*/

r=P;/*r下移一个节点*/retum(head)；/*返回单链表表头节点地址*/}voidprint()/*输出单链表各节点的data值*/{P=head->next；

while(P!=NULL){printf("%c"，p->data)；

p=p->next；

}}

六、链表的建立

例8-11依次输人一串字符"abc"，以"*"为结束标记，建立并输出如下单链表：

structstu10*f811(){charch；head=(structstu10*)malloc(LEN)；/*申请头节点*/head->next=NULL；/*头节点链域置空*/while((ch=getchar())!='*'){p=(structstu10*)malloc(LEN)；

p->data=ch；

p->next=head->next；/*把head的下一个节点地址存入P的链*/

head->next=P；/*把P节点的地址存入head的链*/