单链表.docx

1、单链表线性表操作在单链表上的实现如前所述，单链表可以由静态或动态产生的独立结点构成，也可以由静态或动态产生的数组中的元素结点构成，下面分别对每一种情况给出操作实现，最后给出简单应用举例。 每个单链表都有一个表头指针，假定用HL表示，由表头指针可以访问到单链表中的任何结点，所以要对单链表进行操作，必须给出表头指针。假定以HL为表头指针的单链表是由LNode类型的动态结点所组成，并且不带有表头附加结点，下面给出对线性表抽象数据类型中列举的每一操作在单链表上的具体实现(即C+算法)。1初始化单链表void lnitList(LNode*&HA)HL=NULL；/将单链表置空2删除单链表中的所有结点，

2、使之成为一个空表 删除单链表中的所有结点，需要遍历单链表，通过delete操作释放被访问的每一个结点，然后把表头指针置为空。 void ClearList(LNode*&HL)LNode *cp，*np； /用cp作为指向当前结点(即待处理结点)的指针 /(currentpointer)，用叩作为指向当前结点 /的后继结点的指针(nextpointer)cp=HL； /表头指针赋给cpwhile(cp!=NULL)/遍历单链表，向系统交回每一个结点np=cp-next；/保存下一个结点的指针delete cp；/删除当前结点 cp=np；/使下一个结点成为当前结点HL=null;/置单链表为空

3、 3得到单链表的长度由于在单链表的构成中，没有给出单链表的长度，所以此算法需要遍历单链表，对被访问的结点进行计数，最后返回这个计数值。 intListSize(LNode*&HL)形参HL最好采用值参，因为算法中不需要。 /修改HL所对应的实参，另外，调用时只需要复制一个指针(即4 /个字节)，它同使用引用参数传送时需要复制一个实参地址的工 /作量相同，由此没有增加值参传送的复制量LNode*p=HL； int i=0； /用来统计结点的个数while(p!=NULL) /遍历单链表，统计结点数i+；p=p-next；return i；4 检查单链表是否为空 int ListEmpty(LNo

4、de*HL)return(HL=NULL)； 5得到单链表中第pos个结点中的元素 要访问单链表中的第pos个结点，必须从表头开始依次访问过该结点之前的所有结点后才能够实现，即只能够采用顺序存取，而不能够随机存取任一个结点。 ElemType GetElem(LNodeHL，int pos) if(pos1) cerr”pos is out range!”nextif(p!=NULL) return p-data； else cerrpos is out range!endl; exit(1); 6遍历一个单链表假定在遍历一个单链表时是打印出每个结点的值。void TraverseList(L

5、Node *&HL)LNode* p=HL；while(p!=NULl) coutdata”；coutdata=item) item=p-data; return 1； else p=p-next;return 0；8.更新单链表中具有给定值的第一个元素int Update(LNode*&HL，const ElemType&item)LNode* p=HL； while(p!=NULL)/查找元素 if(p-data=item) break；else p=p-next；if(p=NULL) return0;/没有被更新的元素，返回0else/更新元素 p-data=item；return l；

6、 9向单链表的末尾添加一个元素 由于在单链表的构成中没有给出指向表尾结点的指针，所以要向表尾添加元素结点，则必须从表头开始遍历整个单链表后得到指向表尾结点的指针，然后把新结点的存储地址赋给表尾结点的指针域完成插入。void lnsertRear(LNodew&HL，const ElemType&item)LNodew newptr；newptr=new LNode； /为保存新元素分配动态结点，newptr指向这个 /结点 if(newptr=NULL)/若未分配到结点，则停止插入，退出程序运行cerr“Memory allOcation failare!data=item;newptr-ne

7、xt=NULL;if(HL=NULL)把新元素赋给动态结点 *newptr的值域/给动态结点的指针域置空HL=newptr； /向空表插入的结点为表头结点elseLNode*p=HL；while(p-next!=NULL)/从表头开始遍历到最后一个结点为止p=p-next； p-next=newptr；/把新结点链接到表尾10向单链表的表头插入一个元素此操作不需要像顺序裘(即顺序存储的线性表)那样移动所有元素，只需修改新元素结点的指针域，使之指向原有单链表，修改表头指针，使之指向新元素结点。 void lnsertFront(LNode*&HL，const ElemType&item)if(n

8、ewptr=NULL)/若未分配到结点，则停止插入，退出程序运行cerrMemory allocation failare!”data=item；newptr-next=HL；HL=newptr；11向单链表中满足条件的位置插入一个元素其插入过程为：(1)为新元素动态分配结点并赋值；(2)从表头开始顺序查找新元素的插入位置，在查找过程中必须保留待查结点的前驱的指针，以便插入使用；(3)在插入位置上完成插入操作，插入位置是否在表头，应进行不同处理。 void Insert(LNode*&HL，const ElemType&item)/实现第(1)步操作 LNode*newptr； newptr=

9、new LNode； if(newptr=NULL)cerrdata=item；/实现第(2)步操作 LNode*cp；/用cp指向当前结点(即待查结点)LNode* ap；/用ap作为指向当前结点的前驱结点的指针(ahead /pointer) ap=NULL；cp=HL； /令当前结点为表头结点，此时无前驱结点，所以置ap指针为空 whilecp！=NULL) if(itemdata) break； else/使当前结点成为前驱结点，使当前结点的后继成为当前结点 /从而实现顺序向后比较 ap=cp；cp=cp-next；/实现第(3)步操作if(ap=NULL) /把新结点插入到表头，包括

10、原表为空的情况 newptr-next=HL；HL=newptr；/把新结点插入到非表头位置，即插入到ap和cp结点之间 newptr-next=cp； ap-next=newptr； 12从单链表中删除表头元素 从单链表中删除表头元素既不需要查找元素，又不需要移动元素，只需要修改表头指针且p可。 ElemType DeleteFront(LNode*&HL) if(HL=NULL) cerrDeleting from an empty list!next；/使表头指针指向第2个结点ElemType temp=p-data；/暂存原表头元素，以便返回deletep； /回收被删除的表头结点re

11、turn temp；/返回第一个元素的值 13从单链表中删除等于给定值的第一个元素 删除算法的执行步骤为： (1)若单链表为空则返回假； (2)从单链表中顺序查找与给定值相等的第一个元素，直到查找成功或失败为止，在查找过程中需要保留待比较结点(即当前结点)的前驱结点的指针，以便删除结点时使用； (3)如果查找失败则返回假； (4)删除查找到的结点，对表头结点和非表头结点要做不同处理； (5)回收被删除的结点； (6)返回真表明删除成功。 int Delete(LNode*&HL，const ElemType&item)/实现第(1)步操作if(HL=NULL) cerrHL iS NULL!d

12、ata=item) break；else/使前驱指针和当前指针均指向下一个结点ap=cp；cp=cp-next；/实现第(3)步操作if(cp=NULL) cerrDeleted element iS not exist!next;else /由cP指向的被删除结点是非表头结点 ， ap-next=cp-next； /实现第(5)步操作delete cp;/实现第六步操作return 1;14利用单链表进行数据排序假定待排序的n个数据存在于一维数组。an中，当利用单链表进行排序时，从空单链表开始，每次调用Insert算法向单链表中插入数组a中的一个元素，经n次调用后，单链表成为包含有数组a中n个元素的有序表，最后遍历单链表，把每个结点的值依次写入到数组avoid LinkSort(ElemType a，int n)LNode*head =NULL;int i;for(i=0；idata；p=p-next；(End)第1页第2页第3页第4页