计算机软件基础chapter2.2.4-5

特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。线性表最常用的链式存储方式如下图所示：354196∧60…..head由于线性表的这种链式存储结构通过指针域将所有元素关联成为一个长链，因此称为单链表。2.2.4链式存储线性表的基本运算链表中的基本概念：•头指针：存放链表第一个结点内存地址的指针变量，链表的关键数据；•头结点：为了方便链表操作，在链表的第一个实际结点之前附设的结点，该结点只使用指针域；•首元结点：链表中的第一个实际结点；a1a2an∧a3head…..带头结点的单链表a1a2an∧a3…..不带头结点的单链表head头指针头结点首元结点structnodetype{ElemTypedata；/*data数据项用于存放结点的数据值*/structnodetype*next；/*next数据项存放下一个结点的指针*/}；•线性表的链式存储结构可用C语言中的“结构指针”来描述•注：后面讨论具体算法实现时，以ElemType为整型为例进行介绍,即有typedefElemTypeint。datanext•具体实现过程如下：第一步：申请头结点空间，用head变量记下头结点空间的内存地址；第二步：给头结点的指针数据项（next数据项）赋值为空指针。第三步：将单链表的头指针（head变量的值）返回给主调函数。初始化操作是建立一个空链表。即链表中仅有一个头结点，且头结点的指针域为空。head∧带头结点的空链表2.2.4.1单链表的初始化运算具体算法如下：typedefstructnodetypenodetype;nodetype*initl(){nodetype*head;head=(nodetype*)malloc(sizeof(nodetype))；/*为头结点申请空间*/if(head!=NULL)head-next=NULL；return(head);/*将头结点的指针域初始化为NULL*/}初始化操作是建立一个空链表。即链表中仅有一个头结点，且头结点的指针域为空。head∧带头结点的空链表2.2.4.1单链表的初始化运算尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。·····a1a2ak∧head尾结点p2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2ak∧head尾结点新结点申请新结点空间ps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2ak∧head尾结点新结点ak+1对其data数据项进行初始化ps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2ak∧head尾结点新结点ak+1∧对其next数据项进行初始化，使之为空NULLps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2akhead尾结点新结点ak+1∧将新结点链接到链表尾结点之后，即p-next=s;ps尾接法：从空链表开始，将各结点从链表的尾部依次链接到链表中；由于该方法是将数据元素从链表的尾部接入，因此，需用一个变量记住当前尾结点，修改尾结点的指针域使其指向新结点。2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。·····a1a2akhead尾结点ak+1∧插入的新结点成为新链表的尾结点psnodetype*creatL1()/*建立一个头为head的带头结点的单链表*/{nodetype*head,*p,*s;ElemTypex;head=initl();/*链表初始化*/p=head;/*尾结点初始化为头结点*/scanf(“%d”,&x);while(x!=-1){s=(nodetype*)malloc(sizeof(nodetype));/*申请新结点空间*/s-data=x;/*给新结点的数据域赋值*/s-next=NULL;/*将新结点的指针域初始化为空*/p-next=s;/*将新结点链接到表尾*/p=s;/*新结点成为新链表的尾结点*/scanf(“%d”,&x);}returnhead;}尾接法创建链表的具体算法头插法:将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。a1∧head2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。头插法:将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。a1∧head2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。a2新结点申请新结点空间并对其数据域进行初始化S头插法:将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。a1∧head2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。a2新结点S给新结点的指针域赋值为链表首元结点的地址头插法:将数据元素依次插到链表头结点的后面。头插法建立的链表元素的输入顺序与在链表中的顺序相反。a1∧head2.2.4.2单链表的创建运算创建单链表方法有两种：尾接法和头插法。a2新结点S将新结点链到头结点之后nodetype*creatL2(){nodetype*head,*s；ElemTypex；head=initl()；/*链表初始化*/scanf(“%d”,&x);while(x!=-1){s=(nodetype*)malloc(sizeof(nodetype))；/*为新结点s申请空间，*/s-data=x；/*给新结点的数据域赋值*/s-next=head-next；/*将新结点链到首元结点之前*/head-next=s；/*将新结点链到头结点之后*/scanf(“%d”,&x);}return（head)；}头插法创建链表的具体算法基本思想：从链表的第一个实际结点出发，从前向后在整个链表范围内逐个结点进行关键字比较。若查找成功，则返回该结点的地址；若查找失败，则返回空指针。·····887264∧head·····85例如：在如图所示的单链表中查找关键字值为85的元素，对查找过程进行演示。2.2.4.3单链表的查找运算•链表查找具体过程：·····887264∧head·····85p将p首先定位在首元结点处查找值为85的元素，若当前结点值不等于85，则继续向后找•链表查找具体过程：·····887264∧head·····85p•链表查找具体过程：·····887264∧head·····85p查找值为85的元素，若当前结点值不等于85，则继续向后找•链表查找具体过程：·····887264∧head·····85p查找值为85的元素，若当前结点值不等于85，则继续向后找•链表查找具体过程：·····887264∧head·····85p查找值为85的元素，若当前结点值不等于85，则继续向后找•链表查找具体过程：·····887264∧head·····85p查找值为85的元素，若当前结点值不等于85，则继续向后找•链表查找具体过程：·····887264∧head·····85p查找值为85的元素，若当前结点值不等于85，则继续向后找•链表查找具体过程：·····887264∧head·····85p查找成功查找值为85的元素，若当前结点值不等于85，则继续向后找nodetype*searchL(nodetype*head,KeyTypex)/*在带头结点的单链表head中查找元素x*/{nodetype*p;p=head-next;/*从第一个结点开始找*/while(p!=NULL&&p-data!=x)/*逐个往后查找*/p=p-next;returnp;}•链表查找具体算法：·····887264∧head·····85pnodetype*searchL(nodetype*head,KeyTypex)/*在带头结点的单链表head中查找元素x*/{nodetype*p;p=head-next;/*从第一个结点开始找*/while(p!=NULL&&p-data!=x)/*逐个往后查找*/p=p-next;returnp;}•链表查找具体算法：·····887264∧head·····85pX=85nodetype*searchL(nodetype*head,KeyTypex)/*在带头结点的单链表head中查找元素x*/{nodetype*p;p=head-next;/*从第一个结点开始找*/while(p!=NULL&&p-data!=x)/*逐个往后查找*/p=p-next;returnp;}•链表查找具体算法：·····887264∧head·····85pnodetype*searchL(nodetype*head,KeyTypex)/*在带头结点的单链表head中查找元素x*/{nodetype*p;p=head-next;/*从第一个结点开始找*/while(p!=NULL&&p-data!=x)/*逐个往后查找*/p=p-next;returnp;}•链表查找具体算法：·····887264∧head·····85pX=85nodetype*searchL(nodetype*head,KeyTypex)/*在带头结点的单链表head中查找元素x*/{nodetype*p;p=head-next;/*从第一个结点开始找*/while(p!=NULL&&p-data!=x)/*逐个往后查找*/p=p-next;returnp;}•链表查找具体算法：·····887264∧head·····85pnodetype*searchL(nodetype*head,KeyTypex)/*在带头结点的单链表head中查找元素x*/{nodetype*p;p=head-next;/*从第一个结点开始找*/while(p!=NULL&&p-data!=x)/*逐个往后查找*/p=p-next;returnp;}•链表查找具体算法：·····887264∧head·····85pnodetype*searchL(nodetype*head,KeyTypex)/*在带头结点的单链表head中查找元素x*/{nodetype*p;p=head-next;/*从第一个结点开始找*/while(p!=NULL&&p-data!=x)/*逐个往后查找*/p=p-next;returnp;}•链表查找具体算法：·····887264∧head·····85p查找成功！算法要求：将新元素x插入到单链表中关键字值为k的元素之后。解题思想：首先在单链表中查找到关键字为k的元素，然后进行新元素的插入。·····8864∧head·····85p例如：在下面链表中关键字为85的结点之后插入新元素99，假定已查找到关键字为85的元素，现对插入过程进行演示。762.2.4.4单链