救急：小弟初学数据结构，小问题不知如何下手，请高手帮帮忙！！

我这个学期刚学习《数据结构》，如今遇到两个问题。请高手帮我解决一下，我想解决问题的源代码或者算法。问题如下：
1。已知 L1和 L2分别指向两个单链表的头结点，且已知长度分别为m和n，试写一算法将这两个链表链接在一起，并分析其时间复杂度。
2，某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格数量和链指针三个域。现出库（销售）M台价格为？
敬请各位帮帮忙，小弟感激不尽！！！

6 个解决方案

#1

Q1:
#ifndef LIST_H_
#define LIST_H_
#pragma warning(disable:4786)
#include <vector>
#include <bitset>
#include <complex>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <string>
#include <fstream>
#include <WTYPES.H>
#endif
using namespace std;

template <class elemType>
class list_item{
public:
//构造函数
list_item(elemType value,list_item<elemType> *item=NULL);

list_item<elemType> *getNext() {return _next;}
void setNext(list_item *link) {_next=link;}

elemType getValue(void) {return _value; }
void setValue(elemType new_value) {_value=new_value;}

private:
elemType _value;
list_item<elemType> *_next;
};

template <class elemType>
class list{
public:
//构造函数
list():_front(NULL),_end(NULL),_size(0){}

//拷贝构造函数
list(const list<elemType> &rhs);

//重载赋值操作符
list & operator= (const list<elemType> &rhs);

int getSize(void) {return _size;}
void setSize(int s) {_size=s;}

list_item<elemType> * getEnd(void) {return _end; }
void setEnd(list_item<elemType> *e) {_end=e;}

list_item<elemType> * getFront(void) {return _front; }
void setFront(list_item<elemType> *f) {_front=f;}

//在指针ptr处插入一个新的结点，其值为value
void insert(list_item<elemType> *ptr,elemType value);

//在头部插入一个新值
void insert_front(elemType value);

//在尾部插入一个新值
void insert_end(elemType value);

//删除头部元素（结点）
void remove_front(void);

//删除尾部元素
void remove_end(void);

//删除全部
void remove_all(void);

//删除结点值为value的结点
void remove(elemType value);

//删除指针处的结点
void remove(list_item<elemType> *ptr);

//翻转链表
void reverse(void);

//连接两个链表
void concat(const list &il);

//查找第一个值为value的结点
list_item<elemType> *find(elemType value);

//打印全部链表
void display(ostream &os=cout);

//插入全新元素
void insert_all(const list<elemType> &rhs);

private:
list_item<elemType> *_front;
list_item<elemType> *_end;
list_item<elemType> *_current;
int _size;
};

template <class elemType>
list_item<elemType>::list_item(elemType value,list_item<elemType> *item):_value(value)
{
if(!item)
_next=NULL;
else
{
_next=item->_next;
item->_next=this;
}
}

//------------------------------------------------------------------------

template <class elemType>
list_item<elemType> * list<elemType>::find (elemType value)
{
list_item<elemType> *ptr=_front;
while(ptr)
{
if(ptr->getValue() == value)
return ptr;
ptr=ptr->getNext ();
}
return NULL;
}

template <class elemType>
void list<elemType>::display (ostream &os/* =cout */)
{
os<<"\n( "<<_size<< " )( ";
list_item<elemType> *ptr=_front;
while(ptr){
os<<ptr->getValue ()<<" ";
ptr=ptr->getNext ();
}
os<<")\n";
}

template <class elemType>
void list<elemType>::insert (list_item<elemType> *ptr,elemType value)
{
if(!ptr)
insert_front(value);
else
{
new list_item<elemType>(value,ptr);
++_size;
}
}

template <class elemType>
void list<elemType>::insert_front(elemType value)
{
list_item<elemType> *ptr=new list_item<elemType>(value);
if(!_front)
_front=_end=ptr;
else{
ptr->setNext(_front);
_front=ptr;
}
++_size;
}

template <class elemType>
void list<elemType>::insert_end (elemType value)
{
if(!_end)
_end=_front=new list_item<elemType>(value);
else _end=new list_item<elemType>(value,_end);
++_size;
}

template <class elemType>
void list<elemType>::remove_front (void)
{
if(_front){
list_item<elemType> *ptr=_front;
_front=_front->getNext ();
--_size;
delete ptr;
}
}

template <class elemType>
void list<elemType>::remove_all (void)
{
while(_front)
remove_front();

_size=0;
_front=_end=NULL;
}

template <class elemType>
void list<elemType>::remove (list_item<elemType> *ptr)
{
list_item<elemType> *p;
p=_front;

if(!ptr)
return;
else if(p==ptr){
remove_front();
return;
}

while(p){
if(p->getNext() ==ptr){
p->setNext(ptr->getNext ()) ;
--_size;
delete ptr;
break;
}
p=p->getNext ();
}
}

template <class elemType>
void list<elemType>::remove (elemType value)
{
list_item<elemType> *ptr;
ptr=find(value);
remove(ptr);
}

template <class elemType>
void list<elemType>::remove_end (void)
{
list_item<elemType> *p;
p=_front;

if(!p)
return;

while(p->getNext ()!=_end)
p=p->getNext ();

delete p->getNext ();
_end=p;
p->setNext (NULL);
--_size;
}

template <class elemType>
void list<elemType>::concat (const list<elemType> &il)
{
if(!_end){
_front=il._front ;
_size=il._size;
}
else{
_end->setNext (il._front) ;
_size+=il._size ;
}
_end=il._end ;
}

template <class elemType>
void list<elemType>::reverse(void)
{
list_item<elemType> *ptr=_front;
list_item<elemType> *prev=NULL;

_front=_end;
_end=ptr;

while(ptr!=_front)
{
list_item<elemType> *tmp=ptr->getNext ();
ptr->setNext (prev);
prev=ptr;
ptr=tmp;
}

_front->setNext (prev);
}

template <class elemType>
void list<elemType>::insert_all (const list<elemType> &rhs)
{
list_item<elemType> *ptr=rhs._front ;
while (ptr) {
insert_end(ptr->getValue());
ptr=ptr->getNext();
}
}

template <class elemType>
list<elemType>::list (const list<elemType> &rhs):_front(NULL),_end(NULL),_size(0)
{
insert_all(rhs);
}

template <class elemType>
list<elemType> & list<elemType>::operator = (const list<elemType> &rhs)
{
if(this!=&rhs){
remove_all();
insert_all(rhs);
}
return *this;
}

int main()
{
list<int> mylist;

for (int ix=0;ix<5;ix++){
mylist.insert_front (ix);
if(ix!=0) mylist.insert_end (-ix);
}

cout<<"原始链表：";
mylist.display ();

cout<<"在4的后面插入400：";
mylist.insert (mylist.find (4),400);

list_item<int> *ptr;
ptr=mylist.getFront ();
mylist.insert (ptr,20);
mylist.insert_end (-50);
mylist.insert_front (100);
cout<<"在头元素后面插入20，尾部插入-50，再将100添到表头部：";
mylist.display ();

ptr=mylist.getEnd ();
list_item<int> *pnew=new list_item<int>(1981,ptr);
mylist.setEnd(pnew);
mylist.setSize (mylist.getSize ()+1);
cout<<"在尾部插入1981";
mylist.display ();

mylist.remove_front ();
cout<<"删除头部：";
mylist.display ();

ptr=mylist.getFront ();
ptr=ptr->getNext ()->getNext ();
mylist.remove (ptr);
cout<<"删除第3个元素：";
mylist.display ();

mylist.remove_end ();
cout<<"删除尾部：";
mylist.display ();

cout<<"删除0、20、9（如果没有，则不删除）：";
mylist.remove (0);
mylist.remove (20);
mylist.remove (9);
mylist.display ();

mylist.insert (mylist.find (400),4000);
cout<<"在400的后面插入4000（如果找不到的话则放头部）：";
mylist.display ();

list<int> mylist2;
mylist2.insert_front(300);
mylist2.insert_front (301);
mylist2.insert_end(299);
mylist.concat (mylist2);
cout<<"连接两个链表：";
mylist.display ();

mylist.reverse ();
cout<<"翻转链表：";
mylist.display ();

mylist.remove_end ();
cout<<"删除尾部：";
mylist.display ();

list<int> mylist3;
mylist3=mylist;
cout<<"链表的赋值：";
mylist3.display ();

list<int> mylist4(mylist);
cout<<"链表的拷贝构造函数：";
mylist4.display ();

mylist.remove_all ();
cout<<"删除整个链表：";
mylist.display ();

return 0;
}

#2

我倒、。。。

#3

谢谢你－－bugzhao(阿辉）
非常的感谢~~~~~~~~~!
不过我还是有点不明白,希望能再请教你,就是上面的程序源代码如果在VC6.0环境下或者TC环境下能正常运行吗?
因为我看过你的源程序,语句不太象C++语言.

#4

一楼的代码够吓人的，我不懂C++，就不看了。

第一题：
不懂你说的头结点是单独的头结点还是第一个结点，我假设是第一个结点。
假设你的链表是C语言的结构实现的。

/*把L2接到L1的末端*/
while(L1->next)
L1 = L1->next;
L1->next = L2;

时间复杂度m或2m看你怎么算。

第二题：没看懂题目。

#5

发送者：huangyi_234 发送时间：2006-3-13 23:34:37 删除回复
接受者：feny911 重要性：重要性：1 非常不重要重要性：2 不重要重要性：3 一般重要性：4 重要重要性：5 非常重要
内容第二题修改如下：
某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格数量和链指针三个域。现出库（销售）M台价格为n电视机，试编写算法修改原链表．
请帮我再看看．
谢谢!!!!

////////////////////////////////////////////////////
设链表结点类型为 struct tvNode
struct tvNode * tv 指向表头

struct tvNode * temp = 0;
while(tv->next->price != n)
tv = tv->next;

tv->next->number -= M;
if(tv->next->number == 0) {
temp = tv->next;
tv->next = temp->next;
free(temp);
temp = 0;
}

注1：仅仅描述算法，不考虑代码健壮性。（比如是否存在价格为n的电视机）
注2：如果楼主对我的答案满意，请尽快结贴。呵呵

秒客网

救急：小弟初学数据结构，小问题不知如何下手，请高手帮帮忙！！

6 个解决方案

#1

#2

#3

#4

#5

#6

#1

#2

#3

#4

#5

#6

相关文章