单链表中重复元素删除8817.doc

《单链表中重复元素删除8817.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、单链表中重复元素的删除(8817)一、题目1、问题描述按照数据输入的顺序建立一个单链表，并将单链表中重复的元素删除(值相同的元素只保留最初输入的一个)。2、输入第一行输入元素个数n；第二行输入n个整数；处理到文件结束。3、输出第1行输出删除重复元素后的单链表元素个数；第2行输出删除重复元素后的单链表；4、输入例10213014553263113055305、输出例721301455326311二、算法指导1、数据结构根据题目要求，数据要存储于单链表，首先要确定建立的单链表的结点类型，结点类型可为：typedefstructnode{intd

2、ata;node*next;}*linklist;这里的linklist为指针类型，其变量为指向node的结点。2、算法思路(1)设计初始化单链表的函数intinitlist_l(linklist&l)；以建立带头结点的空单链表。intinitlist_l(linklist&l){//构造一个带头结点的空单链表l，l是引用参数，是变参，其值其他函数要用。}3(2)设计建立有n个结点的单链表函数voidcreatelist_l(linklistl，intn)。可用后插法建立单链表。这里的l开始时已指向单链表的头结点，l的值已不会变，所以只要值

3、参就可以。n为要建立的非降序排列单链表的结点个数，由主函数传入。voidcreatelist_l(linklistl，intn){for(n次重复做){输入数据d；产生新结点p，并把d赋值给p；把新结点p链接到链表l的尾部；}}(3)输出单链表。voidprint(linklistl){//按输出格式要求输出单链表l中结点的值}(4)设计单链表中重复元素的删除的函数voiddele(linklistla,int&n)，la为单链表，n为la中的结点个数，删除重复结点后，n的值要减小，其值要函数外面要用，所以用引用参数。其算法思想是从la的第

4、一个结点开始的各结点，依次与其后面的各个结点比较，若其值相等，则将其后面的结点删除。要注意到删除结点时，不要断链，既要删除结点，也要抓住被删除结点的后面的结点，以便继续处理。voiddele(linklistla,int&n){p指向la表的第一个结点；//从la的第一个结点开始的各结点while(p不空)//扫描la表中的各结点{p2指向p的下一个结点；//准备扫描p的后续结点p1取p的值；//p1跟在p2的后面，准备链接被删结点的后一结点；while(p2不空)//扫描p的各后续结点{if(p所指结点的值等于p2所指结点的值)//找到重

5、复结点{p2所指结点的后一结点链接在p1结点后面；//绕过重复结点p2指向其下一结点；//为继续扫描准备3删除重复结点(原p2所指结点)；链表的结点数减一；}else｛p2指向其下一个结点；//准备扫描下一个结点p1跟在p2的后面；}}p指向其下一个结点；//准备检查下一个结点是否有重复结点}}3、主函数main(){调用initlist_l()，初始化单链表la；调用createlist_l()，建立有n个结点的单链表la；调用dele()，删除la中的重复结点；输出删除la中结点后的结点个数；调用print()，输出删除重复结点后的单链

6、表la；}3