计算机软件技术基础教程课件-7第七章-线性表

第七章线性表7.1线性表的基本概念及运算线性表是计算机程序设计中最常遇到的一种操作对象，也是数据结构中最简单、最重要的结构形式之一。实际上，线性表结构在程序设计中大量使用，它对我们来说并不是一个陌生的概念。在这一章里，我们将从一个新的角度来更加系统地讨论它。7.1线性表的基本概念及运算7.1.1线性表的逻辑结构定义学生成绩登记表

线性表是由n（n≥0）个数据元素a1,a2,…,an构成的有限序列。其中，将数据元素的个数n定义为表的长度。当n=0时称为空表，通常将非空的线性表（n>0）记作：（a1,a2,…,an）。7.1线性表的基本概念及运算7.1.2线性表的运算1.置空表SETNULL(L)2.求长度LENGTH(L)3.取结点GET(L,i)4.定位LOCATE(L,x)5.插入INSERT(L,x,i)6.删除DELETE(L,i)7.取直接前趋PRIOR(L,ai)8.取直接后继NEXT(L,ai)7.1线性表的基本概念及运算7.1.2线性表的运算[例7.1]利用线性表的基本运算清除表Ｌ中多余的重复结点。7.1线性表的基本概念及运算7.1.2线性表的运算PURGE(L) /*删除线性表Ｌ中重复出现的多余结点*/Linear_list*L; {inti=1,j,x,y; while(i<LENGTH(L))/*每次循环使当前第i个结点是无重复值的结点*/{x=GET(L,i);/*取当前第i个结点*/j=i+1;while(j<=LENGTH(L)){y=GET(L,j); /*取当前第j个结点*/if(x==y)DELETE(L,j); /*删除当前第j个结点*/elsej++;}i++;}} /*PURGE*/7.2线性表的顺序存储结构7.2.1顺序表Loc (ai+1)=Loc (ai)+cLoc (ai)=Loc (a1)+(i

1)

c1≤i≤n7.2线性表的顺序存储结构7.2.2顺序表的基本运算1．插入运算2.删除运算7.2线性表的顺序存储结构7.2.2顺序表的基本运算1．插入运算我们在线性表的第i (1≤i≤n+1)个位置上，插入一个

新结点x，使长度为n的线性表

（a1,…,ai

1,ai,…,an）变成长度为n+1的线性表

（a1,…,ai

1,x,ai,…,an）7.2线性表的顺序存储结构7.2.2顺序表的基本运算1．插入运算7.2线性表的顺序存储结构7.2.2顺序表的基本运算2．删除运算线性表的删除运算是指将表的第i（1≤i≤n）个结点

删去，使长度为n的线性表

（a1,…,ai

1,ai,ai+1,…,an）变成长度为n

1的线性表

（a1,…,ai

1,ai+1,…,an）7.2线性表的顺序存储结构7.2.2顺序表的基本运算2．删除运算7.3线性表的链式存储结构上一节研究了线性表的顺序存储结构，它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。这一特点使得顺序表具有如下的优缺点，其优点是：可以随机存取表中任意元素；其存储位置可用一个简单直观的公式来表示。然而，这一特点也铸成了这种存储结构的三个缺点：第一，在进行插入或删除运算时，需移动大量元素；第二，在给长度变化较大的线性表预先分配空间时，必须按最大空间分配，使存储空间不能得到充分利用；第三，表的容量难以扩充。7.3线性表的链式存储结构为了克服顺序表的缺点，可以采用链接方式存储线性表，通常我们将链接方式存储的线性表称为链表（LinkedList）。从实现的角度看，链表可分为动态链表和静态链表。静态链表是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。动态链表是用内存申请函数动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。7.3线性表的链式存储结构7.3.1单链表结点结构：data域：数据域next域：指针域7.3线性表的链式存储结构7.3.2单链表的基本运算1．建立单链表 1）头插法建表 2）尾插法建表2．插入及删除运算 1）插入运算 2）删除运算2．查找运算 1）按序号查找 2）按值查找7.3线性表的链式存储结构7.3.2单链表的基本运算1.建立单链表-头插法建表7.3线性表的链式存储结构7.3.2单链表的基本运算linklist

CREATLISTF(){charch; /*逐个输入字符，以“$”为结束符，返回单链表头指针*/linklist

head,

s;head=NULL; /*链表开始为空*/ch=getchar(); /*读入第一个结点的值*/while(ch!='$'){s=(linklist

)malloc(sizeof(linklist));/*生成新结点*/s－>data=ch; /*将输入数据放入新结点的数据域中*/s－>next=head;head=s; /*将新结点插入到表头上*/ch=getchar(); /*读入下一个结点的值*/}returnhead; /*返回链表头指针*/} /*CREATLISTF*/7.3线性表的链式存储结构7.3.2单链表的基本运算1.建立单链表-尾插法建表7.3线性表的链式存储结构7.3.2单链表的基本运算linklist

CREATLISTR()/*尾插法建立单链表，返回表头指针*/{charch;linklist

head,

s,

r;head=NULL;/*链表初值为空*/r=NULL;/*尾指针初值为空*/ch=getchar();/*读入第一个结点值*/while(ch!=′$′)/*以“$”为输入结束符*/{s=(linklist

)malloc(sizeof(linklist));/*生成新结点

s*/s－>data=ch;if(head==NULL)head=s;/*新结点

s插入空表*/elser－>next=s;/*非空表，新结点

s插入到尾结点*/ r=s;/*尾指针r指向新的表尾*/ch=getchar( );/*读入下一结点值*/}if(r!=NULL)r－>next=NULL;/*对非空表，将尾结点的指针域置空*/returnhead;/*返回单链表头指针*/} 7.3线性表的链式存储结构7.3.2单链表的基本运算简化后的尾插法-附加头节点7.3线性表的链式存储结构7.3.2单链表的基本运算linklist

CREATLISTR1()/*尾插入法建立带头结点的单链表，返回表头指针*/{charch;linklist

head,

s,

r;head=(linklist

)malloc(sizeof(linklist));/*生成头结点head*/r=head;

/*尾指针指向头结点*/ch=getchar();while(ch!=′$′) /*“$”为输入结束符*/{s=(linklist

)malloc(sizeof(linklist));

/*生成新结点*s*/s－>data=ch;r－>next=s; /*新结点插入表尾*/r=s; /*尾指针r指向新的表尾*/ch=getchar(); /*读入下一个结点的值*/}r－>next=NULL;returnhead; /*返回表头指针*/} /*CREATLISTR1*/简化后的尾插法-附加头节点7.3线性表的链式存储结构7.3.2单链表的基本运算2.插入与删除-插入运算7.3线性表的链式存储结构7.3.2单链表的基本运算2.插入与删除-插入运算INSERTAFTER (linklist

p,datatypex) /*将值为x的新结点插入

p之后*/{linklist

s;s=(linklist

) malloc (sizeof (linklist)); /*生成新结点

s*/s－>data=x;s－>next=p－>next;p－>next=s;/*将*s插入*p之后*/} /*INSERTAFTER*/7.3线性表的链式存储结构7.3.2单链表的基本运算[例7.2]

在单链表上，将值为x的新结点插入在结点

p前。7.3线性表的链式存储结构7.3.2单链表的基本运算/*在带头结点的单链表head中，将值为x的新结点插入

p之前*/INSERTBEFORE(linklist

head,linklist

p,datatypex){linklist

s,

q;s=(linklist

)malloc(sizeof(linklist)); /*生成新结点*s*/s－>data=x;q=head; /*从头指针开始*/while(q－>next!=p)q=q－>next;/*查找

p的前趋结点

q*/s－>next=p;q－>next=s;/*将新结点

s插入

p之前*/} /*INSERTBEFORE*/7.3线性表的链式存储结构7.3.2单链表的基本运算[例7.3]

在单链表上实现线性表的插入运算INSERT(L,x,i)。INSERT(linklist

L,datatypex,inti){linklist

p;intj;j=i

1;p=GET(L,j); /*找第i

1个结点

p*/if(p==NULL)print(″error″); /*i<1或i>(n+1)*/elseINSERTAFTER(p,x);/*将值为x的新结点插到

p之后*/} /*INSERT*/7.3线性表的链式存储结构7.3.2单链表的基本运算2.插入与删除-删除运算7.3线性表的链式存储结构7.3.2单链表的基本运算2.插入与删除-删除运算DELETE(linklist

p,linklist

head)/*删去单链表head的结点

p*/{linklist

q;q=head;while(q－>next!=p)q=q－>next;/*查找

p的前趋结点

q*/q－>next=p－>next; /*删除结点

p*/free(p); /*释放结点

p*/} /*DELETE*/7.3线性表的链式存储结构7.3.2单链表的基本运算[例7.4]

在单链表上实现线性表的删除运算DELETE(L,i)。DELETE(linklist

L,inti)/*删去带头结点的单链表L的第i个结点*/{linklist

p,

r;intj;j=i

1;p=GET(L,j); /*找到第i

1个结点*/if((p!=NULL)&&(p－>next!=NULL)){r=p－>next; /*

r为结点

p的后继*/p－>next=r－>next; /*将结点

r从链表上摘下*/free(r); /*释放结点

r*/}else /*i<1或i>n*/printf(″error″)} /*DELETE*/7.3线性表的链式存储结构7.3.2单链表的基本运算[例7.5]

将两个递增单链表合并为一个递增单链表，要求不另开辟空间。UNION(linklist

la,linklist

lb);/*合并递增单链表la和lb*/{linklist

p,

q,

r,

u;p=la－>next;q=lb－>next;r=la; /**r为*p的直接前趋*/while((p!=NULL)&&(q!=NULL)){if(p－>data>q－>data){u=q－>next;r－>next=q;r=q;q－>next=p;q=u;}else{r=p;p=p－>next;}}if(q!=NULL)r－>next=q;} /*UNION*/7.3线性表的链式存储结构7.3.2单链表的基本运算3.查找运算-按序号查找/*在带头结点的单链表head中查找第i个结点，若找到，则返回该结点的存储位置；否则返回NULL*/linklist

GET(linklist

head,inti){intj;linklist

p;p=head;j=0; /*从头结点开始扫描*/while((p－>next!=NULL)&&(j<i)){p=p－>next; /*扫描下一个结点*/j++; /*已扫描结点计数器*/}if(i==j)returnp; /*找到了第i个结点*/elsereturnNULL; /*找不到，i≤0或i>n*/} /*GET*/7.3线性表的链式存储结构7.3.2单链表的基本运算3.查找运算-按值查找/*在带头结点的单链表head中查找其结点值等于key的结点，若找到则返回该结点的位置p；否则返回NULL*/linklist

LOCATE(linklist

head,datatypekey){linklist

p; p=head－>next; /*从开始结点比较*/while(p!=NULL)if(p－>data!=key)p=p－>next; /*没找到，继续循环*/if(p==NULL)returnNULL;elsereturnp;

/*找到结点key，退出循环*/} /*LOCATE*/7.3线性表的链式存储结构7.3.3循环链表单循环链表7.3线性表的链式存储结构7.3.3循环链表仅设尾指针rear的单循环链表7.3线性表的链式存储结构7.3.3循环链表[例7.6]

在循环链表的第i个元素之后插入元素x。INSERT(linklist

head,datatypex,inti)/*在循环链表第i个元素之后插入元素x*/{linklist

s; intj;s=(

linklist)malloc(sizeof(linklist));s－>data=x; /*生成值为x的新结点*/p=head;j=0;while((p－>next!=head)&&(j<i)){p=p－>next;j++;}if(i=j){s－>next=p－>next;p－>next=s;}/*插入操作*/elseprintf(″error″);} /*INSERT*/7.3线性表的链式存储结构7.3.3循环链表[例7.7]

一元多项式的表示及相加。多项式结点形式多项式的循环链式存储结构7.3线性表的链式存储结构7.3.3循环链表polynode*polyadd(polynode

pa,polynode

pb); /*多项式相加运算A=A+B*/{polynode

p,

q,

r,

s; folatx; p=pa－>next;q=pb－>next; s=pa; /**s为*p的直接前趋*/ while((p!=pa)&&(q!=pb)) {if(p－>exp<q－>exp){s=p;p=p－>next;} /*p指针后移*/if(p－>exp>q－>exp){r=q－>next;q－>next=p;s－>next=q;s=q;q=r;}else{