《数据结构实用教程(C语言版)》课件第2章 线性表_第1页
《数据结构实用教程(C语言版)》课件第2章 线性表_第2页
《数据结构实用教程(C语言版)》课件第2章 线性表_第3页
《数据结构实用教程(C语言版)》课件第2章 线性表_第4页
《数据结构实用教程(C语言版)》课件第2章 线性表_第5页
已阅读5页,还剩63页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第2章线性表本章主要介绍下列内容线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构线性表的应用举例本章目录2.1线性表的基本概念1

2.2顺序表2

2.3链表32.4线性表的应用举例4

2.5本章小结5结束2.1线性表的基本概念2.1.1线性表的定义2.1.2线性表的基本操作返回到总目录2.1.1

线性表的定义1.线性表的定义线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,通常记为:(a1,a2,…ai-1,ai,ai+1,…an)

其中n为表长,当n=0时称为空表。

在线性表中相邻元素之间存在着顺序关系。如对于元素ai

而言,ai-1

称为

ai

的直接前驱,ai+1

称为

ai

的直接后继。返回到本节目录2.线性表的特点(1)有且仅有一个开始结点(a1),它没有直接前驱;(2)有且仅有一个终端结点(an),它没有直接后继;(3)除了开始结点和终端结点以外,其余的结点都有且仅有一个直接前驱和一个直接后继。2.1.1

线性表的定义返回到本节目录2.1.2

线性表的基本操作数据结构的运算是定义在逻辑结构层次上的,而运算的具体实现是建立在存储结构上的。下面定义的线性表的基本操作仅是定义在逻辑结构上的,每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。线性表的基本操作有:(1)初始化线性表InitList(L)。其作用是建立一个空表L(即建立线性表的构架,但不包含任何数据元素)。返回到本节目录(2)求线性表的长度GetLength(L)。其作用是返回线性表L的长度(即所含数据元素的个数)。(3)求线性表中第i个元素GetElem(L,i,x)。其作用是在1≤i≤GetLength(L)返回成功,并用x存储线性表L的第i个元素的值。(4)按值查找操作Locate(L,x)。在线性表L查找一个与给定值x相等的数据元素,其作用是若存在一个或多个与x相等的数据元素,则返回的元素所在位置的最小值或地址值;否则返回0或NULL值。2.1.2

线性表的基本操作返回到本节目录(5)插入操作InsElem(L,i,x)。其作用是在线性表L的第i个位置上插入一个值为

x的新元素,使线性表L由(a1,a2,…ai-1,ai,ai+1,…an)变为(a1,a2,…ai-1,x,ai,ai+1,…an)。其中1≤i≤GetLength(L)+1。(6)删除操作DelElem(L,i,x)。其作用是删除线性表L的第i个位置的数据元素并用x将其存储,使线性表L由(a1,a2,…ai-1,ai,ai+1,…an)变为(a1,a2,…ai-1,ai+1,…an)。其中1≤i≤GetLength(L)。(7)输出元素值DispList(L)。其作用是依次扫描线性表L,并输出各元素的值。2.1.2

线性表的基本操作返回到本节目录2.2顺序表2.2.1顺序表2.2.2顺序表的基本操作实现返回到总目录1.顺序表的定义数据结构在内存中的表示通常有两种形式,即顺序存储表示和链式存储表示。线性表的顺序存储表示又称为顺序表。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素,我们把用这种存储形式存储的线性表称为顺序表。假设顺序表(a1,a2,…ai-1,ai,ai+1,…an),每个数据元素占用d个存储单元,则元素ai的存储位置为:Loc(ai)=Loc(a1)+(i-1)×d1≤i≤n2.2.1顺序表返回到本节目录其中,Loc(a1)是顺序表第一个元素a1的存储位置,通称为顺序表的起始地址。顺序存储结构示意图如图2-1所示。顺序表的存储特点:(1)顺序表的逻辑顺序和物理顺序是一致的。(2)顺序表中任意一个数据元素都可以随机存取,所以顺序表是一种随机存取的存储结构。2.2.1顺序表返回到本节目录2.顺序表的类型定义#defineMAXLEN100/*定义常量MAXLEN为100表示存储空间总量*/#defineOK/*定义常量OK为1表示成功*/#defineERROR0/*定义常量ERROR为0表示失败*/#defineOVER-1/*定义常量OVER为-1表示结束*/typedefintElemType;/*定义ElemType为int类型*/typedefstruct/*顺序表存储类型*/{ElemTypedata[MAXLEN];/*存放线性表的数组*/intLength;/*Length是顺序表的长度*/}SeqList;2.2.1顺序表返回到本节目录2.2.2顺序表的基本操作实现1.顺序表的初始化顺序表的初始化即构造一个空顺序表L,将表L的实际长度置0,算法描述见算法2.1。算法2.1

voidInitList(SeqList*L)

{L->Length=0;

/*初始的化顺序表为空*/}返回到本节目录2.顺序表的建立初始化顺序表后向表中输入n个元素建立表L,算法描述见算法2.2。算法2.2voidCreateList(SeqList*L,intn){inti;printf("请输入各个元素值:\n");for(i=0;i<n;i++)scanf("%d",&L->data[i]);L->Length=i;}2.2.2顺序表的基本操作实现返回到本节目录3.求顺序表的长度操作返回顺序表L的Length值,算法描述见算法2.3。算法2.3intGetLength(SeqList*L){returnL->Length;}

4.查找操作顺序表的查找分为按值与按序号查找,下面将分别介绍这两种方法的实现,读者可根据具体的问题相应选择所需的查找方法。2.2.2顺序表的基本操作实现返回到本节目录(1)按号查找查找顺序表中第i个元素的值,在i无效时返回出错,有效时返回成功,并用x存储第i个元素的值,算法描述见算法2.4。算法2.4intGetElem(SeqList*L,inti,ElemType*x){if(i<1||i>L->Length)returnERROR;else{*x=L->data[i-1];returnOK;}}2.2.2顺序表的基本操作实现返回到本节目录2)按值查找操作顺序表中的按值查找是指在顺序表中查找与给定值x相等的数据元素的所在位置,算法描述见算法2.5。算法2.5intLocate(SeqList*L,ElemTypex){

inti=0;while(i<=L->Length&&L->data[i]!=x)i++;if(i>L->Length)

returnERROR;elsereturni+1;

/*返回的是元素位置*/}2.2.2顺序表的基本操作实现返回到本节目录2.2.2顺序表的基本操作实现5.插入操作线性表的插入是指在表的第i个位置上插入一个值为x的新元素,插入后使原表长增1,原顺序表如图2-2所示。返回到本节目录5.插入操作步骤如下:

(1)将an~ai之间的所有结点依次后移,为新元素让出第i个位置,如图2-3所示。返回到本节目录5.插入操作步骤如下:(2)将新结点x插入到第i个位置,如图2-4所示。(3)顺序表的长度增1,插入成功,并返回,算法描述见算法2.6。返回到本节目录5.插入操作算法2.6int

InsElem(SeqList*L,inti,ElemTypex){intj;

if(L->Length>=MAXLEN){printf("顺序表已满!");returnOVER;

/*表满,不能插入*/}if(i<1||i>L->Length+1)

/*检查给定的插入位置的正确性*/{printf("插入位置出错!");returnERROR;}if(i==L->Length+1){L->data[i-1]=x;L->Length++;returnOK;/*插入的位置为表尾,则不需移动直接插入即可*/}for(j=L->Length-1;j>=i-1;j--)

/*结点移动*/L->data[j+1]=L->data[j];L->data[i-1]=x;/*新元素插入*/L->Length++;/*顺序表长度增1*/returnOK;

/*插入成功,返回*/}返回到本节目录5.插入操作插入算法的时间性能分析:顺序表插入操作大约需移动表中一半数据元素,其时间复杂度为O(n)。返回到本节目录2.2.2顺序表的基本操作实现6.删除操作

线性表的删除操作是指将第i个元素从顺序表中去掉,删除后顺序表表长减1,原顺序表如图2-5所示。返回到本节目录6.删除操作步骤如下:(1)将要删除的元素值赋给指针变量*x,如图2-6所示返回到本节目录6.删除操作步骤如下:(2)将ai+1~an之间的结点依次顺序向前移动,如图2-7所示。(3)顺序表的长度减1,删除成功,并返回,算法描述见算法2.7。返回到本节目录6.删除操作算法2.7intDelElem(SeqList*L,inti,ElemType*x)

{int

j;if(L->Length==0){printf("顺序表为空!");returnERROR;

/*表空,不能删除*/}if(i<1||i>L->Length)

/*检查是否空表及删除位置的合法性*/{printf("不存在第i个元素");returnERROR;}*x=L->data[i-1];/*用指针变量*x返回删除的元素值*/for(j=i;j<=L->Length-1;j++)

/*结点移动*/L->data[j-1]=L->data[j];L->Length--;

/*顺序表长度减1*/returnOK;

/*删除成功,返回*/}返回到本节目录6.删除操作删除算法的时间性能分析:与插入操作相同,其时间主要消耗在了移动表中元素上,(大约需要移动表中一半的元素),显然该算法的时间复杂度为O(n)。返回到本节目录2.2.2顺序表的基本操作实现7.顺序表的输出操作扫描顺序表L,输出各元素的值,算法描述见算法2.8。算法2.8voidDispList(SeqList*L){inti;for(i=0;i<L->Length;i++)printf("%5d",L->data[i]);}返回到本节目录2.3链表2.3.1单链表2.3.2单链表的基本操作实现2.3.3链表的变形返回到总目录2.3.1单链表1.单链表的定义线性表的链式存储结构是指用一组任意的存储单元(可以连续,也可以不连续)存储线性表中的数据元素。为了反映数据元素之间的逻辑关系,对于每个数据元素不仅要表示它的具体内容,还要附加一个表示它的直接后继元素存储位置的信息,这样构成的链表称为线性单向链接表,简称单链表,其结点结构如图2-8所示。数据域后继指针域datanext图2-8单链表的结点示意图其中,data部分称为数据域,用于存储一个数据元素(结点Node)的信息。next部分称为指针域,用于存储其直接后继的存储地址的信息。返回到本节目录2.3.1单链表单链表分为带头结点(其next域指向链表第一个结点的存储地址)和不带头结点两种类型。在许多情况下,带头结点的链表中每个结点的存储地址均放在其前驱结点中,这样算法对所有的结点处理可一致化,因此,本节讨论的单链表均指带头结点的单链表。带头结点的单链表如图2-9所示。

图2-9带头结点的单链表其中,头结点的数据域可以不存储任何信息,也可以存放特殊的信息;头结点的指针域存储链表中第一个结点的地址。当头结点的指针域为空(即NULL或用∧表示),则此表为空表。在非空表中,当某个结点的指针域为空,表示它为链表的最后一个结点。返回到本节目录2.3.1单链表链式存储特点:线性表的链式存储结构是通过指针来表示元素之间的逻辑关系,不再有逻辑顺序与物理存储顺序一致的特点,是非顺序存储结构。返回到本节目录2.3.1单链表2.单链表的类型定义#defineOK1#defineERROR0#defineOVER-1typedefcharElemType;/*定义ElemType为char类型*/typedefstructnode/*单链表存储类型*/{ElemTypedata;/*定义结点的数据域*/structnode*next;/*定义结点的指针域*/}LinkList;返回到本节目录2.3.2单链表的基本操作实现1.单链表的初始化单链表的初始化即构造一个仅包含头结点的空单链表L,算法描述见算法2.9。算法2.9

LinkList*InitList(){/*申请一块LinkList类型的存储单元的操作,并将其地址赋值给头指针变量L*/LinkList*L;

L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL;returnL;/*头结点L指针域为空,表示空链表*/}返回到本节目录2.3.2单链表的基本操作实现2.单链表的建立(1)头插法建表在初始化链表后,每读取有效的数据都为其生成新结点s,并将读取的数据存放到新结点s的数据域中,然后将新结点插入到当前链表L的表头上,直到循环结束为止,算法描述见算法2.10。算法2.10voidCreateList(LinkList*L){LinkList*s;charch;while((ch=getchar())!='#')/*判断输入数据是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点*/s->data=ch;/*将数据放入新结点的数据域*/s->next=L->next;/*将新结点的指针域存放头结点的指针域*/L->next=s;/*将新结点插入头结点之后*/}}返回到本节目录2.3.2单链表的基本操作实现(2)尾插法建表头插法建立链表虽然算法简单易理解,但生成的链表中结点的次序和原输入的次序相反。而尾插法建立链表可实现次序的一致,该算法依旧在初始化链表后,但需增加一个尾指针last,使其指向当前链表的尾结点,算法描述见算法2.11。算法2.11voidCreateList(LinkList*L){LinkList*s,*last;charch;last=L;/*last始终指向尾结点,开始时指向头结点*/while((ch=getchar())!='#')/*判断输入数据是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点*/s->data=ch;/*将数据放入新结点的数据域*/s->next=NULL;/*将新结点的指针域为空*/last->next=s;/*将新结点插入表尾*/last=s;/*将last指针指向表尾结点*/}}返回到本节目录2.3.2单链表的基本操作实现3.求单链表的长度求长度就是求单链表中数据元素的个数。求带头结点的单链表L的长度需设一个动态指针p指向头结点,计数器j初始值为0,p指针所指结点后面若还有结点,p就向后移动,每次移动一次,计数器j值增1,直到p所指结点后面为空结束,则计数器j的值即为表的长度,算法描述见算法2.12。算法2.12intGetLength(LinkList*L){LinkList*p;intj=0;p=L;/*p指向链表的头结点*/while(p->next!=NULL)/*判断p所指结点后面是否为空*/{p=p->next;/*p向所指结点的后面移动*/j++;/*计数器值增1*/}returnj;/*计数器j的值为表长度*/}返回到本节目录2.3.2单链表的基本操作实现4.查找操作单链表的查找分为按值与按序号查找,下面将分别介绍这两种方法的实现,读者可根据具体的问题相应选择所需的查找方法。(1)按值查找算法思路:从链表的第一个元素结点开始,由前向后依次比较单链表中各结点数据域中的值,若某结点数据域中的值与给定的值x相等,则返回该结点的指针值p;否则继续向后比较直到表结束。若整个单链表中没有这样的结点,则返回空NULL值,算法描述见算法2.13。算法2.13LinkList*Locate(LinkList*L,ElemTypex){LinkList*p;p=L->next;/*p指向链表的第一个结点*/while(p!=NULL&&p->data!=x)p=p->next;returnp;}返回到本节目录2.3.2单链表的基本操作实现(2)按序号查找算法思路:从链表的头结点开始,判断当前结点序号是否是第i个,若是,则返回该结点指针值p;否则继续向后查找直到表结束。若没有第i个结点,则返回空NULL值,算法描述见算法2.14。算法2.14LinkList*GetList(LinkList*L,inti){LinkList*p;intj=0;p=L;/*p指向链表的头结点*/while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)/*判断与给定的序号是否相等*/returnp;elsereturnNULL;}返回到本节目录2.3.2单链表的基本操作实现5.插入操作顺序表的插入操作需要移动大量的数据元素,而链表的插入只需修改指针而无需移动原表元素,那链表的插入操作是如何实现呢?(1)在已知结点p之后插入一新结点s已知结点p为链表中任意结点,先创建一个以x为值的新结点s,则插入操作步骤如下:先将结点s的指针域指向结点p的下一个结点(执行语句s->next=p->next)。再将结点p的指针域改为指向新结点s(执行语句p->next=s)。返回到本节目录5.插入操作插入结点的过程如图2-10所示,算法描述见算法2.15。注:插入操作的①与②语句执行顺序不能颠倒,否则原p指针其后的链表将丢失。算法2.15voidIns_Elem(LinkList*p,ElemTypex){LinkList*s;s=(LinkList*)malloc(sizeof(LinkList));/*生成新结点s*/s->data=x;/*将数据x放入新结点的数据域*/s->next=p->next;/*将新结点s的指针域与p结点后面元素相连*/p->next=s;/*将p与新结点s链接*/}返回到本节目录5.插入操作(2)在第i个位置插入新结点s由于单链表的结点结构是单向后指的,因此要完成此操作需要找到第i结点的前驱结点即第i-1结点的指针p,此时可调用按序号查找GetList()函数求出p指针地址,然后在调用在已知结点p后方插入新结点Ins_Elem()函数操作即可,算法描述见算法2.16。算法2.16intInsElem(LinkList*L,inti,ElemTypex){LinkList*p;p=GetList(L,i-1);/*调用按序号查找函数GetList(),求出第i-1个元素地址p*/if(p!=NULL)/*判断查找的元素地址p是否存在*/{Ins_Elem(p,x);/*调用在已知结点p后插入结点函数Ins_Elem()*/returnOK;}elsereturnERROR;}返回到本节目录5.插入操作插入算法的时间性能分析:链表插入操作主要时间耗费在查找操作上,其时间复杂度为O(n)。返回到本节目录2.3.2单链表的基本操作实现6.删除操作顺序表的删除操作同样需要移动大量的数据元素,而链表的删除只需修改指针而无需移动原表元素,那链表的删除操作是如何实现呢?(1)删除已知结点p之后结点s已知结点p为链表中除终端结点以外的任意结点,先将结点s中的数据域中的值赋给指针变量*x,则删除操作步骤如下:结点p指针域指向结点s下一个结点(执行语句p->next=s->next)。②释放s结点空间(执行语句free(s))。返回到本节目录6.删除操作删除结点的过程如图2-11所示,算法描述见算法2.17。

图2-11在结点p之后删除结点s算法2.17voidDel_Elem(LinkList*p,ElemType*x){LinkList*s;s=p->next;/*s为要删除结点*/*x=s->data;/*将要删除的数据放入指针变量*x中*/p->next=s->next;/*将p结点的指针域与s结点后面元素相连*/free(s);/*释放结点s*/}返回到本节目录6.删除操作(2)删除未知结点(如第i个结点)s首先求出第i结点的前驱结点(第i-1结点)p的地址,可调用按序号查找GetList()函数求出p指针地址,然后再调用删除已知结点p之后结点s的DelList()函数操作即可。算法中注意if(p!=NULL&&p->next!=NULL)语句,只有当第i-1结点存在即(p!=NULL)而又不是终端结点即(p->next!=NULL)时,才能确定被删除结点存在,算法描述见算法2.18。算法2.18intDelElem(LinkList*L,inti,ElemType*x){LinkList*p;p=GetList(L,i-1);/*调用按序号查找第i-1个元素地址p函数*/if(p!=NULL&&p->next!=NULL){Del_Elem(p,x);/*调用删除已知结点p之后结点函数*/returnOK;}elsereturnERROR;}返回到本节目录6.删除操作删除算法的时间性能分析:链表删除操作也主要时间耗费在查找操作上,其时间复杂度为O(n)。返回到本节目录2.3.2单链表的基本操作实现7.单链表的输出操作扫描单链表L,输出各元素的值,算法描述见算法2.19。算法2.19voidDispList(LinkList*L){LinkList*p;p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}}返回到本节目录2.3.3链表的变形1.循环单链表循环链表是另一种形式的链式存储结构。对于单链表而言,最后一个结点的指针域为空,如果将该链表中最后一个结点的指针域指向头结点,整个链表形成一个环,就构成了循环单链表,如图2-12所示。由此,从表中的任意结点出发均可找到表中的其他结点。在循环单链表上的操作基本上与非循环的单链表相同,只是将原来判断指针是否为NULL,改为是否是头指针L即可。图2-12带头结点的循环单链表返回到本节目录2.3.3链表的变形2.双链表(1)双链表的定义在单链表结点中只有一个指向直接后继的指针域next,这样从某个结点出发只能顺指针方向寻找它的后继结点。若要寻找结点的直接前驱,则需从头指针出发查找前驱。若希望能够快速查找一个结点的直接前驱,则可以再增加一个指向其直接前驱的指针域prior,这样就构成了双向链接表,简称双链表,其结点结构如图2-13所示。图2-13双链表的结点示意图其中,data部分称为数据域,用于存储一个数据元素(结点Node)的信息。prior部分称为前驱指针域,用于存储其直接前驱的存储地址的信息。next部分称为后继指针域,用于存储其直接后继的存储地址的信息。前驱指针域数据域后继指针域priordatanext返回到本节目录2.双链表(2)双链表的类型定义typedefcharElemType;/*定义ElemType为char类型*/typedefstructdunode/*双链表存储类型*/{ElemTypedata;/*定义结点的数据域*/structdunode*prior;/*定义结点的前驱指针域*/structdunode*next;/*定义结点的后继指针域*/}DuLinkList;返回到本节目录2.双链表为了算法对所有的结点处理可一致化,与单链表一样,本章讨论的双链表均指带头结点的双链表。带头结点的双链表如图2-14所示。其中,头结点的数据域可以不存储任何信息,也可以存放特殊的信息,头结点的前驱指针域为空(即NULL或用∧表示),后继指针域存储链表中第一个结点的地址。当头结点的后继指针域为空(即NULL或用∧表示),则此表为空表。在非空表中,当某个结点的后继指针域为空,表示它为链表的最后一个结点。返回到本节目录2.双链表(3)双链表的基本运算在双链表中,有些操作(如求链表的长度、查找某个结点等)仅涉及一个方向的指针,其算法与单链表的操作相同,但在插入和删除操作时却有很大的区别。①在双链表中p指针指向的结点前插入新结点s操作先创建一个以x为值的新结点s,在p结点之前插入结点s,则插入操作步骤如下:将结点s的prior域指向结点p的前一个结点(执行语句s->prior=p->prior)。将结点p的前一个结点的next域指向结点s(执行语句p->prior->next=s)。将结点s的next域指向p结点(执行语句s->next=p)。将结点p的prior域指向结点s。(执行语句p->prior=s)。返回到本节目录2.双链表插入结点的过程如图2-15所示,算法描述见算法2.20。注:以上操作的步骤的顺序不是唯一的,但a操作步骤必须放在d操作步骤的前面完成,否则结点p的前驱结点的指针将丢失。返回到本节目录2.双链表算法2.20voidDuIns_Elem(DuLinkList*p,ElemTypex){DuLinkList*s;s=(DuLinkList*)malloc(sizeof(DuLinkList));/*生成新结点s*/s->data=x;s->prior=p->prior;/*对应图2-15中的a*/p->prior->next=s;/*对应图2-15中的b*/s->next=p;/*对应图2-15中的c*/p->prior=s;/*对应图2-15中的d*/}返回到本节目录2.双链表②在双链表中删除p指针指向的结点操作先保证删除位置的正确性。在双链表上找到删除位置结点地址,由p指向,先将结点p中的数据域中的值赋给指针变量*x,则删除操作步骤如下:将结点p前一个结点的next域指向结点p的next域(执行语句p->prior->next=p->next)。将结点p后一个结点的prior域指向结点p的prior域(执行语句p->next->prior=p->prior)。释放结点p空间。(执行语句free(p))。返回到本节目录2.双链表删除结点的过程如图2-16所示,算法描述见算法2.21。算法2.21voidDuDel_Elem(DuLinkList*p,ElemType*x){*x=p->data;p->prior->next=p->next;/*对应图2-16中的a*/p->next->prior=p->prior;/*对应图2-16中的b*/free(p);}返回到本节目录2.3.3链表的变形3.循环双链表与循环单链表一样,也可以使用循环双链表。对于双链表而言,头结点的前驱指针域与最后一个结点的后继指针域均为空。如果将该链表中最后一个结点的后继指针域指向头结点,头结点的前驱指针域指向最后一个结点,整个链表形成两个环,就构成了循环双链表,如图2-17所示带头结点的循环双链表。在循环双链表上的操作基本与双链表相同。图2-17带头结点的循环双链表

在循环双链表中,若p为指向表中某一个结点的指针,则有:p->prior->next=p=p->next->prior返回到本节目录2.4线性表的应用举例

【例2.1】建立一个对线性表操作的综合程序。在该程序中,包括顺序表的建立、插入、删除、查找等各种操作。并在主函数内设计一个菜单,实现反复操作,完整程序算法描述见算法2.22。算法2.22/**************各种常量及结构体类型定义*********************/#defineMAXLEN100/*顺序表存储空间的总分配量*/#defineOK1#defineERROR0#defineOVER-1typedefintElemType;/*定义ElemType为int类型*/typedefstruct/*存储类型*/{ElemTypedata[MAXLEN];/*存放线性表的数组*/intLength;/*Lengthgth是顺序表的长度*/}SeqList;返回到总目录2.4线性表的应用举例/********************建立线性表函数************************/voidcreate(SeqList*L,intn){inti;printf("请输入各个元素值:\n");for(i=0;i<n;i++)scanf("%d",&L->data[i]);L->Length=i;}/********************显示输出表中信息函数********************/voidDispList(SeqList*L){inti;for(i=0;i<L->Length;i++)printf("%5d",L->data[i]);}返回到本节目录2.4线性表的应用举例/********************插入元素函数***********************/intInsElem(SeqList*L,inti,ElemTypex){intj;if(L->Length>=MAXLEN){printf("表已满!");returnOVER;/*表满,不能插入*/}if(i<1||i>L->Length+1)/*检查给定的插入位置的正确性*/{printf("插入位置出错!");returnERROR;}if(i==L->Length+1){L->data[i-1]=x;L->Length++;returnOK;/*插入的位置为表尾,则不需移动直接插入即可*/}for(j=L->Length-1;j>=i-1;j--)/*结点移动*/L->data[j+1]=L->data[j];L->data[i-1]=x;/*新元素插入*/L->Length++;/*表长度增1*/returnOK;/*插入成功,返回*/}返回到本节目录2.4线性表的应用举例/**********************删除元素函数**********************/intDelElem(SeqList*L,inti,ElemType*x){intj;if(L->Length==0){printf("顺序表为空!");returnERROR;/*表空,不能删除*/}if(i<1||i>L->Length)/*检查空表及删除位置的合法性*/{printf("不存在第%d个元素",i);returnERROR;}*x=L->data[i-1];/*用指针变量x返回删除的元素值*/for(j=i;j<=L->Length-1;j++)/*结点移动*/L->data[j-1]=L->data[j];L->Length--;/*顺序表长度减1*/returnOK;/*删除成功,返回*/}返回到本节目录2.4线性表的应用举例/*********************在表中按值查找函数*******************/intLocate(SeqList*L

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论