数据结构 课件 第2章 线性表(2链表)

线性表中每个元素有唯一的前驱元素和后继元素。2.3.1

单链表的定义1.链表概述1/552.3线性表的链式表示每个物理结点增加一个指向后继结点的指针域

单链表。每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域

双链表。2/55学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901设计链式存储结构时，每个逻辑元素用一个结点单独存储，为了表示逻辑关系，增加指针域。线性表(a0,a1,…,ai,…,an-1

)映射逻辑结构存储结构带头结点单链表示意图a1a2an∧…L3/55typedefstructLNode//声明单链表结点类型{inflistdata;

structLNode*next;//指向后继结点}LinkNode;typedefstructinf{ intnum; charname[8];

charsex[4];

intglassno;}inflist;线性表(a0,a1,…,ai,…,an-1

)映射逻辑结构存储结构带头结点双链表示意图a1an∧…La24/55顺序表：需要平均移动半个表的元素。链表：只需修改相关结点的指针域即可，这样既方便又省时。插入或删除操作5/55链表和顺序表的比较顺序表：具有随机存取特性。链表：不具有随机存取特性。6/55随机存取特性（查找序号i的元素的时间为O(1)）一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1（100%），而链表的存储密度小于1。存储密度=结点数据本身占用的空间结点占用的空间总量a18个字节4个字节存储密度=8/12=67%例如7/55存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比，即：顺序表：存储密度高。链表：存储密度相对较低。8/55存储密度单链表中结点类型LinkNode的声明如下:

typedefstructLNode

//声明单链表结点类型{intdata;

structLNode*next;//指向后继结点}

LinkNode;a9/552.3.2单链表上基本操作的实现a1a2an∧…第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理。无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。单链表增加一个头结点的优点：带头结点单链表头结点首结点尾结点10/55当访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。ab…p…p是指针，*p是p指向的结点，为了简单，称p指向的结点为p结点11/55单链表的特点插入操作：将值为x的新结点s插入到p结点之后。特点：只需修改相关结点的指针域，不需要移动结点。（1）插入结点操作12/551、插入结点和删除结点操作abx…p…s

s->next=p->next

p->next=s插入操作语句描述如下：

s->next=p->next;

p->next=s;单链表插入结点演示p结点next的修改尽可能放在后面执行13/55删除操作：删除p结点之后的一个结点。特点：只需修改相关结点的指针域，不需要移动结点。14/55（2）删除结点操作abx…p…p->next=p->next->next删除操作语句描述如下：

p->next=p->next->next;

free(p->next);为了释放被删除结点，操作语句描述如下：

q=p->next;p->next=q->next;free(q);15/55单链表删除结点演示16/55structstudent*createlist(){structstudent*head;structstudent*q;//指向当前链表的最后一个结点structstudent*p;//新建结点intdata;head=(structstudent*)malloc(sizeof(structstudent));head->next=NULL;q=head;scanf("%d",&data);while(data!=9999){p=(structstudent*)malloc(sizeof(structstudent));//新建结点p->data=data;

p->next=q->next;q->next=p;//插入结点q=q->next;//保证q的逻辑完整性，q指向前链表的最后一个结点scanf("%d",&data);}returnhead;}整体建立单链表先考虑如何整体建立单链表。

a[0..n-1]带头结点的单链表L整体创建建立单链表的常用方法有两种。17/552、整体建立单链表从一个空表开始，创建一个头结点。依次读取字符数组a中的元素，生成新结点将新结点插入到当前链表的表头上，直到结束为止。注意：链表的结点顺序与逻辑次序相反。18/55（1）头插法建表voidList_Head(LNode*&L)//头插法{ LNode*s;intx; L=(LNode*)malloc(sizeof(LNode)); L->next=NULL; scanf("%d",&x); while(x!=9999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=L->next; L->next=s; scanf("%d",&x); }}19/55头插法建表算法如下：注意：链表的结点顺序与逻辑次序相同。从一个空表开始，创建一个头结点。依次读取字符数组a中的元素，生成新结点将新结点插入到当前链表的表尾上，直到结束为止。增加一个尾指针r，使其始终指向当前链表的尾结点20/55（2）尾插法建表voidList_Tail(LNode*&L)//尾插法

{ intx; L=(LNode*)malloc(sizeof(LNode)); LNode*s,*r=L; scanf("%d",&x); while(x!=9999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; scanf("%d",&x); } r->next=NULL;}21/55尾插法建表算法如下：（1）初始化线性表InitList(&L)

该运算建立一个空的单链表，即创建一个头结点。voidInitList(LinkNode*&L)

{L=(LinkNode*)malloc(sizeof(LinkNode));

//创建头结点

L->next=NULL;}∧L22/553、线性表基本运算在单链表上的实现

（2）销毁线性表DestroyList(&L)

释放单链表L占用的内存空间。即逐一释放全部结点的空间。

voidDestroyList(LinkNode*&L){

LinkNode*pre=L，*p=L->next;

//pre指向p的前驱结点

初始时L∧…prep23/55while(p!=NULL) //扫描单链表L

{free(pre); //释放pre结点

pre=p; //pre、p同步后移一个结点

p=pre->next;

}

free(pre); //循环结束时，p为NULL，pre指向尾结点，释放它}循环结束时L∧prep=NULL…24/55

（3）判断线性表是否为空表ListEmpty(L)

若单链表L没有数据结点，则返回真，否则返回假。

boolListEmpty(LinkNode*L){

return(L->next==NULL);}∧L空表的情况25/55（4）求线性表的长度ListLength(L)

返回单链表L中数据结点的个数。

intListLength(LinkNode*L){

intn=0;

LinkNode*p=L; //p指向头结点，n置为0（即头结点的序号为0）

初始时L∧…pn=026/55while(p->next!=NULL)

{ n++; p=p->next;

}

return(n); //循环结束，p指向尾结点，其序号n为结点个数}循环结束时L∧pn为结点个数…27/55

（5）输出线性表DispList(L)

逐一扫描单链表L的每个数据结点，并显示各结点的data域值。

voidDispList(LinkNode*L){LinkNode*p=L->next; //p指向开始结点

while(p!=NULL) //p不为NULL，输出p结点的data域

{printf("%d"，p->data);

p=p->next; //p移向下一个结点

}

printf("\n");}L∧p…28/55

（6）求线性表L中位置i的数据元素GetElem(L，i，&e)

在单链表L中从头开始找到第i个结点，若存在第i个数据结点，则将其data域值赋给变量e。29/55boolGetElem(LinkNode*L，inti，ElemType&e){intj=0;

LinkNode*p=L; //p指向头结点，j置为0（即头结点的序号为0）

while(j<i&&p!=NULL)

{ j++; p=p->next;

}找第i个结点p循环结束时Lean∧…i…p30/55if(p==NULL) //不存在第i个数据结点，返回false

returnfalse;

else

//存在第i个数据结点，返回true

{e=p->data;

returntrue;

}}Lean∧…i…p算法的时间复杂度为O(n)

不具有随机存取特性31/55（7）按元素值查找LocateElem(L，e)

在单链表L中从头开始找第一个值域与e相等的结点，若存在这样的结点，则返回位置，否则返回0。intLocateElem(LinkNode*L，ElemTypee){inti=1;

LinkNode*p=L->next; //p指向开始结点，i置为1

while(p!=NULL&&p->data!=e)

{p=p->next; //查找data值为e的结点，其序号为ii++;

}

循环结束时Le∧…i…p32/55Le∧…i…if(p==NULL)

//不存在元素值为e的结点，返回0return(0);

else

//存在元素值为e的结点，返回其逻辑序号i

return(i);}33/55

（8）插入数据元素ListInsert(&L，i，e)

先在单链表L中找到第i-1个结点p，若存在这样的结点，将值为e的结点结点s插入到其后。boolListInsert(LinkNode*&L，inti，ElemTypee){intj=0;

LinkNode*p=L，*s; //p指向头结点，j置为0

while(j<i-1&&p!=NULL)

{ j++; p=p->next;

}查找第i-1个结点L∧…i-1…p34/55if(p==NULL) //未找到第i-1个结点，返回falsereturnfalse;

else

//找到第i-1个结点p，插入新结点并返回true

{ s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=e; //创建新结点s，其data域置为e s->next=p->next; //将s插入到p之后

p->next=s; returntrue;

}}插入L∧…i-1…pes35/55（9）删除数据元素ListDelete(&L，i，&e)

先在单链表L中找到第i-1个结点p，若存在这样的结点，且也存在后继结点，则删除该后继结点。

boolListDelete(LinkNode*&L，inti，ElemType&e){intj=0;

LinkNode*p=L，*q; //p指向头结点，j置为0

while(j<i-1&&p!=NULL) //查找第i-1个结点

{ j++; p=p->next;

}查找第i-1个结点L∧…i-1…p36/55if(p==NULL) //未找到第i-1个结点，返回false returnfalse;

else

//找到第i-1个结点p

{q=p->next; //q指向第i个结点

if(q==NULL) //若不存在第i个结点，返回false

returnfalse;

e=q->data;

p->next=q->next; //从单链表中删除q结点

free(q); //释放q结点

returntrue; //返回true表示成功删除第i个结点

}}删除第i个结点L∧…i-1…p37/55例2.3以单链表作为存储结构，设计和实现某班某门课程成绩管理的完整程序。程序要求完成如下功能：（1）创建成绩链表，学生数据包含学生的学号、姓名和成绩。（2）可以在指定学号学生前插入学生成绩数据。（3）可以删除指定学号的学生数据。（4）可以计算学生的总数。（5）可以按学号和姓名查找学生。（6）可以显示所有学生的成绩。（7）可以把学生成绩按从高到低的顺序排列。38/554、单链表的应用示例#include<string.h>#include<malloc.h>#include<stdlib.h>#include<stdio.h>

typedefstructStudent/*学生类型定义*/{intscore;/*成绩*/charsno[5],sname[8];/*学号,姓名*/}Student;

typedefstructNode/*结点类型定义*/{StudentstudentInfo;/*学生信息*/structNode*next;/*指向后继元素的指针域*/}LinkList;

voiddisplay(LinkList*p)/*在屏幕上显示一个学生的成绩信息*/{printf("\n\n\nno\t\tname\t\tscore:");printf("\n%s",p->studentInfo.sno);/*打印学号*/printf("\t\t");printf("%s",p->studentInfo.sname);/*打印姓名*/printf("\t\t");printf("%-4d\n",p->studentInfo.score);/*打印成绩*/}39/55voiddisplayAll(LinkList*L)/*在屏幕上显示所有学生的成绩信息*/{LinkList*p;p=L->next;printf("\n\n\nno\t\tname\t\tscore:");while(p){printf("\n%s",p->studentInfo.sno);/*打印学号*/printf("\t\t");printf("%s",p->studentInfo.sname);/*打印姓名*/printf("\t\t");printf("%-4d\n",p->studentInfo.score);/*打印成绩*/p=p->next;}}

40/55LinkList*inputdata()/*输入学生信息*/{LinkList*s=NULL;/*s是指向新建结点的指针*/charsno[5];/*存储学号的数组*/printf("\n");printf("sno:");scanf("%s",sno);/*输入学号*/if(sno[0]=='#')/*#结束输入*/returns;s=(LinkList*)malloc(sizeof(LinkList));strcpy(s->studentInfo.sno,sno);if(strlen(sno)>4)/*如果sno字符个数大于等于5，因为字符串没有'\0'结束标志，

在读数据时将把姓名字符一起读到sno数组，因此做了如下处理*/s->studentInfo.sno[4]='\0';printf("name:");scanf("%s",s->studentInfo.sname);/*输入姓名*/printf("score:");scanf("%d",&s->studentInfo.score);/*输入成绩*/returns;}41/55LinkList*createTailList()/*以尾插法建立带头结点的学生信息单链表*/{LinkList*L,*s,*r;/*L头指针，r尾指针，s是指向新建结点的指针*/L=(LinkList*)malloc(sizeof(LinkList));/*建立头结点，申请结点存储空间*/r=L;/*尾指针指向头结点*/printf("请输入学生成绩，当学号no为#时结束：\n");while(1)/*逐个输入学生的成绩*/{s=inputdata();if(!s)break;/*s为空时结束输入*/r->next=s;/*把新结点插入到尾指针后*/r=s;/*r指向新的尾结点*/}r->next=NULL;/*尾指针的指针域为空*/displayAll(L);/*显示所有学生信息*/returnL;}

42/55voidlocateElemByno(LinkList*L,charch[5])/*按学号查找学生的算法*/{LinkList*p=L->next;/*从第一个结点开始查找*/while(p&&(strcmp(p->studentInfo.sno,ch)!=0))/*p不空且输入学号与链表中学号不等*/p=p->next;if(!p){printf("\n\n\tDon'tfindthestudent!\n");}else{display(p);/*显示查找到的学生信息*/}}

voidlocateElemByname(LinkList*L,charsname[8])/*按姓名查找学生的算法*/{LinkList*p=L->next;/*从第一个结点开始查找*/while(p&&(strcmp(p->studentInfo.sname,sname)!=0))p=p->next;if(!p){printf("\n\n\tDon'tfindthestudent!\n");}else{display(p);/*显示查找到的学生信息*/}}

43/55intlengthList(LinkList*L)/*求学生总人数的算法*/{LinkList*p=L->next;/*p指向第一个结点*/intj=0;while(p){p=p->next;j++;}/*p所指的是第j个结点*/returnj;}

voidinsertElem(LinkList*L,charch[5])/*在指定学号前插入学生*/{LinkList*p,*s;p=L;/*从头结点开始查找学号为ch的结点的前趋结点p*/while((p->next)&&(strcmp(p->next->studentInfo.sno,ch)!=0))p=p->next;s=inputdata();/*输入欲插入学生信息*/s->next=p->next;p->next=s;}

44/55voiddeleteElem(LinkList*L,charch[5])/*删除给定学号的学生信息的算法*/{LinkList*p,*q;p=L;while((p->next)&&(strcmp(p->next->studentInfo.sno,ch)!=0)){p=p->next;/*从头结点开始查找学号为ch的结点的前趋结点p*/}if(!p->next)/*已经扫描到表尾也没找到*/{printf("\n\n\tDon'tfindthestudent!\n");}else{q=p->next;/*q指向学号为ch的结点*/printf("\n\ndeletedstudent'sinformation:");display(q);p->next=q->next;/*改变指针*/free(q);/*释放q占用空间*/printf("\n\nallstudent'sinformation:");displayAll(L);}}

45/55voidinsertSort(LinkList*L)/*用直接插入排序思想把学生的成绩按从高到低排序，结果保存在新有序链表中，原链表不变*/{LinkList*L1,*p;/*L1有序链表的表头，p插入位置前结点*/LinkList*q,*s;/*q欲插入L1中的结点*/intlen;len=lengthList(L);L1=(LinkList*)malloc(sizeof(LinkList));/*建立头结点，申请结点存储空间*/if(L->next)/*链表L非空*/{/*生成有序链表的第一个结点*/s=(LinkList*)malloc(sizeof(LinkList));/*建立结点*/strcpy(s->studentInfo.sno,L->next->studentInfo.sno);strcpy(s->studentInfo.sname,L->next->studentInfo.sname);s->studentInfo.score=L->next->studentInfo.score;s->next=NULL;L1->next=s;/*只有原单链表的第一个结点的有序链表L1*/q=L->next->next;/*原单链表的第二个结点，q即要插入有序链表L1中的结点*/}else{printf("\nthestudentlinklistisempty\n");return;}//下页续46/55while(q)/*链表L中有结点*/{p=L1;/*从链表L1的第一个结点开始比较*/while((p->next)&&(p->next->studentInfo.score>=q->studentInfo.score))p=p->next;/*查找插入位置前结点*//*生成欲插入有序链表中的结点*/s=(LinkList*)malloc(sizeof(LinkList));/*建立新结点*/strcpy(s->studentInfo.sno,q->studentInfo.sno);strcpy(s->studentInfo.sname,q->studentInfo.sname);s->studentInfo.score=q->studentInfo.score;if(!p->next)/*p是有序链表的最后一个结点*/{s->next=NULL;p->next=s;}else{s->next=p->next;p->next=s;}q=q->next;/*下一个欲插入有序链表的结点*/}/*while(!q)*/displayAll(L1);/*显示生成的有序链表*/}

47/55intmain(){printf("=============================================\n\n");printf("带头结点的学生成绩管理程序\n\n");printf("=============================================\n\n");LinkList*L;charch[5],sname[8];intb=1;while(b){inta;printf("\n\n");printf("<1>创建（带头尾插）<2>指定学号前插入<3>按学号删除\n");printf("<4>计算学生总数<5>按学号查找<6>按姓名查找\n");printf("<7>显示所有学生<8>成绩排序<9>退出\n");printf("\n请输入功能选项：");scanf("%d",&a);switch(a){case1:L=createTailList();break;case2:printf("\n输入欲在哪个学号前插入数据:");scanf("%s",ch);insertE