用C++设计一个整型链表类list,能够实现链表结点的插入（insert）、删除（delete），

#include<iostream>using namespace stdstruct node { int datanode *L,*Rnode(int val):data(val),L(0),R(0){}node::~node() { L=NULLR=NULL} }class list { public: list(){first=0last=0} void push_back(int val)void insert(int i,int x)void DELETE(int i) void display()private: node *first,*last}void list::push_back(int val) { node *p=new node(val)if(NULL==first) { first=plast=p} else { last->R=pp->L=lastlast=last->R} } void list::insert(int i,int x) { node *p=firstint j=0while(p&&j<i-1) { p=p->Rj++} if(!p) throw"位置"else { node *s=new node(x)s->L=ps->R=p->Rp->R->L=sp->R=s} } void list::DELETE(int i) { node *p=firstint j=0while(p&&j<i-1) { p=p->Rj++} if(!p) throw"位置"else { p->L->R=p->Rp->R->L=p->L} } void list::display() { node *p=firstwhile(p!=NULL) { cout<<p->data<<"\t"p=p->R} cout <<endl} void text() { list lfor(int i=0i<10i++) { l.push_back(rand()%100)} l.display()l.insert(3,100)l.display()l.DELETE(2)l.display()} int main() { text()return 0}

何在指针q指向的结点后面插入结点。该过程的步骤如下：

（1）先创建一个新结点，并用指针p指向该结点。

（2）将q指向的结点的next域的值（即q的后继结点的指针）赋值给p指向结点的next域。

（3）将p的值赋值给q的next域。

通过以上3步就可以实现在链表中由指针q指向的结点后面插入p所指向的结点。可以通过图1-5形象地展示出这一过程。

图1-5

向链表插入结点过程

下面给出代码描述：

1.void

insertList(LinkList

*list,LinkList

q,ElemType

e)

/*当链表为空时*/

10.

else

16.}

上面的这段代码描述了如何在指针q指向的结点后面插入结点的过程。其过程包括以下几步。

（1）首先生成一个新的结点，大小为sizeof(LNode)，用LinkList类型的变量p指向该结点。将该结点的数据域赋值为e。

（2）接下来判断链表是否为空。如果链表为空，则将p赋值给list，p的next域的值置为空。否则，将q指向的结点的next域的值赋值给p指向结点的next域，这样p指向的结点就与q指向结点的下一个结点连接到了一起。

（3）然后再将p的值赋值给q所指结点的next域，这样就将p指向的结点插入到了指针q指向结点的后面。

其实通过上面这段算法描述可以看出，应用这个算法同样可以创建一个链表。这是因为当最开始时链表为空，即list==NULL，该算法可自动为链表创建一个结点。在下面的创建其他结点的过程中，只要始终将指针q指向链表的最后一个结点，就可以创建出一个

链表。

注意：函数insertList()的参数中有一个LinkList

*list，它是指向LinkList类型的指针变量，相当于指向LNode类型的指针的指针。这是因为在函数中要对list，也就是表头指针进行修改，而调用该函数时，实参是&list，而不是list。因此必须采取指针参数传递的办法，否则无法在被调函数中修改主函数中定义的变量的内容。以下的代码也有类似的情况。

正确的代码和运行结果:

#include <iostream>

#include <string>

using namespace std

template<typename T>class Node//节点类的声明

template<typename T>class List//链表类的声明

template<typename T>class Node

{

public:

Node()

Node(const T &data)

void InsertAfter(Node<T>*p)

Node<T>*RemoveAfter()

friend class List<T>

private:

T data//节点数据

Node<T>*next//节点指针

}

template<typename T>Node<T>::Node()

{

next = NULL

}

template<typename T>Node<T>::Node(const T &data)

{

this->data = data

this->next = NULL

}

template<typename T>void Node<T>::InsertAfter(Node<T>*p)

{

p->next = this->next

this->next = p

}

template<typename T>Node<T>*Node<T>::RemoveAfter()

{

if (this->next == NULL) //尾节点，无可删

return NULL

Node<T>*p = this->next

this->next = p->next

return p

}

template<typename T>class List

{

public:

List()

~List()

void MakeEmpty()

Node<T>*Find(T data)

int Length()

void PrintList()

void InsertFront(Node<T>*p)

void InsertRear(Node<T>*p)

void InsertOrder(Node<T>*p)

Node<T>*CreateNode(T data)

Node<T>*DeleteNode(Node<T>*p)

private:

Node<T>*head

Node<T>*tail

}

template<typename T>List<T>::List()

{

head = tail = new Node<T>()

}

template<typename T>List<T>::~List()

{

MakeEmpty()

delete head

}

template<typename T>void List<T>::MakeEmpty()

{

Node<T>*p

while (head->next != NULL)

{

p = head->next

head->next = p->next

delete p

}

tail = head

}

template<typename T>Node<T>*List<T>::Find(T data)

{

Node<T>*p = head->next

while (p != NULL &&p->data != data)

p = p->next

return p

}

template<typename T>int List<T>::Length()

{

Node<T>*p = head->next

int len = 0

while (p != NULL)

{

p = p->next

len++

}

return len

}

template<typename T>void List<T>::PrintList()

{

Node<T>*p = head->next

while(p != NULL)

{

cout <<p->data <<'\t'

p = p->next

}

cout <<endl

}

template<typename T>void List<T>::InsertFront(Node<T>*p)

{

p->next = head->next

head->next = p

if (tail == head)

{

tail = p

}

}

template<typename T>void List<T>::InsertRear(Node<T>*p)

{

p->next = tail->next

tail->next = p

tail = p

}

template<typename T>void List<T>::InsertOrder(Node<T>*p)

{

Node<T>*pp = head->next

Node<T>*pq = head

while (pp != NULL)

{

if (p->data <pp->data)

break

pq = pp

pp = pp->next

}

pq->InsertAfter(p)

if (tail == pq)

tail = pq->next

}

template<typename T>Node<T>*List<T>::CreateNode(T data)

{

Node<T>*newNode = new Node<T>(data)

return newNode

}

template<typename T>Node<T>*List<T>::DeleteNode(Node<T>*p)

{

Node<T>*pp = head

while (pp->next != NULL &&pp->next != p)

pp = pp->next

if (pp->next == tail)

tail = pp

return pp->RemoveAfter()

}

int main(void)

{

Node<int>*P

List<int>list1, list2, list3

int a[16], i, j

cout <<"请你输入16个整数" <<endl

for (i = 0i <16i++)

cin >>a[i]

for (i = 0i <16i++)

{

//头插法构造链表

P = list1.CreateNode(a[i])

list1.InsertFront(P)

//尾插法构造链表

P = list2.CreateNode(a[i])

list2.InsertRear(P)

}

cout <<"list1 的当前状态为: " <<endl

list1.PrintList()

cout <<"list1 的长度为: " <<list1.Length() <<endl

cout <<"list2 的当前状态为: " <<endl

list2.PrintList()

cout <<"list2 的长度为: " <<list1.Length() <<endl

cout <<"请输入一个要删除的整数" <<endl

cin >>j

P = list1.Find(j)

if (P != NULL)

{

P = list1.DeleteNode(P)

delete P

cout <<"list1 的当前状态为: " <<endl

list1.PrintList()

cout <<"list1 的长度为: " <<list1.Length() <<endl

}

else

{

cerr <<"未找到该节点" <<endl

}

list1.MakeEmpty()

for (i = 0i <16i++)

{

//构建升序链表

P = list3.CreateNode(a[i])

list3.InsertOrder(P)

}

cout <<"list3 的当前状态为: " <<endl

list3.PrintList()

cout <<"list3 的长度为: " <<list1.Length() <<endl

return 0

}

运行结果:

请你输入16个整数

1 2 3 4 5 6 7 7 5 4 4 43 5 566 67 7 55 5 56 7 7 7 6 56 4 5645 6546 756 756 7567 54 6 43 654

list1 的当前状态为:

7 67 566 5 43 4 4 5 7 7 65 4 3 2 1

list1 的长度为: 16

list2 的当前状态为:

1 2 3 4 5 6 7 7 5 4 443 5 566 67 7

list2 的长度为: 16

请输入一个要删除的整数

未找到该节点

list3 的当前状态为:

1 2 3 4 4 4 5 5 5 6 77 7 43 67 566

list3 的长度为: 0

---