#include "stdlib.h"
typedef int ElemType//元素类型
typedef struct DuLNode
{//双向链表
ElemType data
struct DuLNode *prior, *next
}DuLNode,*DuLinkList
int Create(DuLinkList &L)
{//建立双向链表
DuLinkList p,q
ElemType n,i
L = (DuLinkList) malloc (sizeof(DuLNode))
L->next = NULL
q = L
printf("输入数据个数:")
scanf("%d",&n)
printf("输入数据元素:")
for ( i = 0i <ni++)
{
p = (DuLinkList) malloc (sizeof(DuLNode))
scanf("%d",&p->data)//插入数据
p->prior = q
q->next = p
p->next = 0
q = q->next
}
return 1
}
int Visit(DuLinkList &L)
{//遍历双向链表
DuLinkList p
p = L->next
printf("双向链表为:")
while (p)
{
printf("%4d",p->data)
p = p->next
}
printf("\n")
return 1
}
int Clear(DuLinkList &L)
{
DuLinkList p
p = L->next
while(p)
{
L->next = p->next
free(p)
p = L->next
}
return 1
}
main()
{
int i,e,s,num
char c='y'
DuLinkList L
Create(L)
Visit(L)
while (c=='y')
{
printf("\n\n\n1.双向链表插入元素\n2.双向链表中删除元素\n")
printf("3.判断双向链表元素是否对称\n")
printf("4.双向链表中奇数排在偶数前面\n")
printf("5.建立递增链表并有序插入元素\n\n")
printf("选择需要的操作\n\n")
scanf("%d",&num)
switch(num)
{
case 1:
printf("输入插入元素位置以及元素:\n")
scanf("%d%d",&i,&e)
ListInsert(L, i, e)
Visit(L)
break
case 2:
printf("输入删除元素位置:")
scanf("%d",&i)
Delete(L,i,s)
printf("删除的元素为:%d\n",s)
Visit(L)
break
case 3:
if(Same(L)) printf("链表对称\n")
else printf("链表不对称\n")
break
case 5:
printf("清空原链表，建立递增链表:\n")
XCreate(L)
Visit(L)
break
case 4:
printf("奇数放在偶数前面:\n")
Jiou(L)
Visit(L)
break
}
printf("继续操作(y/n):\n")
scanf("%s",&c)
}
}
//Node.h 声明类Node#ifndef Node_H
#define Node_H
template <class T>
class LinkList //为是Node类的友员类而声明
template <class T>
class Node
{
public:
friend class LinkList<T> //将LinkList类设为友元类
private:
T data
Node<T>*next
}
#endif
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。//LinkList.h 声明类LinkList
#ifndef LinkQueue_H
#define LinkQueue_H
#include "Node.h"
template <class T>
class LinkList
{
public:
LinkList( ) //建立只有头结点的空链表
LinkList(T a[], int n) //建立有n个元素的单链表
~LinkList( ) //析构函数
int Length( ) //求单链表的长度
T Get(int i) //取单链表中第i个结点的元素值
int Locate(T x) //求单链表中值为x的元素序号
void Insert(int i, T x) //在单链表中第i个位置插入元素值为x的结点
T Delete(int i) //在单链表中删除第i个结点
void PrintList( ) //遍历单链表，按序号依次输出各元素
private:
Node<T>*first //单链表的头指针
}
#endif
。。。。。。。。。。。。。。。。。。。
//LinkList.cpp
#include "LinkList.h"
/*
*前置条件：单链表不存在
*输入：无
*功能：构建一个单链表
*输出：无
*后置条件：构建一个单链表
*/
template <class T>
LinkList<T>:: LinkList( )
{
first=new Node<T>first->next=NULL
}
/*
*前置条件：单链表不存在
*输入：顺序表信息的数组形式a[],单链表长度n
*功能：将数组a[]中元素建为长度为n的单链表
*输出：无
*后置条件：构建一个单链表
*/
template <class T>
LinkList<T>:: LinkList(T a[ ], int n)
{
first=new Node<T> //生成头结点
Node<T>*r,*s
r=first //尾指针初始化
for (int i=0i<ni++)
{
s=new Node<T>s->data=a[i] //为每个数组元素建立一个结点
r->next=sr=s //插入到终端结点之后
}
r->next=NULL //单链表建立完毕，将终端结点的指针域置空
}
/*
*前置条件：无
*输入：无
*功能：无
*输出：无
*后置条件：无
*/
template <class T>
LinkList<T>:: ~LinkList()
{
}
/*
*前置条件：单链表存在
*输入：查询元素位置i
*功能：按位查找位置为i的元素并输出值
*输出：查询元素的值
*后置条件：单链表不变
*/
template <class T>
T LinkList<T>::Get(int i)
{
Node<T>*pint j
p=first->next j=1 //或p=first j=0
while (p &&j<i)
{
p=p->next //工作指针p后移
j++
}
if (!p) throw "位置"
else return p->data
}
/*
*前置条件：单链表存在
*输入：查询元素值x
*功能：按值查找值的元素并输出位置
*输出：查询元素的位置
*后置条件：单链表不变
*/
template <class T>
int LinkList<T>::Locate(T x)
{
Node<T>*pint j
p=first->nextj=1
if(p&&p->next){
while(p->data!=x)
{
p=p->next
j++
}
return j
}
else throw "位置"
}
/*
*前置条件：单链表存在
*输入：插入元素x,插入位置i
*功能：将元素x插入到单链表中位置i处
*输出：无
*后置条件：单链表插入新元素
*/
template <class T>
void LinkList<T>::Insert(int i, T x)
{
Node<T>*pint j
p=first j=0 //工作指针p初始化
while (p &&j<i-1)
{
p=p->next //工作指针p后移
j++
}
if (!p) throw "位置"
else {
Node<T>*s
s=new Node<T>
s->data=x //向内存申请一个结点s，其数据域为x
s->next=p->next //将结点s插入到结点p之后
p->next=s
}
}
/*
*前置条件：单链表存在
*输入：无
*功能：输出单链表长度
*输出：单链表长度
*后置条件：单链表不变
*/
template <class T>
int LinkList<T>::Length( )
{
Node <T>*p = first->next
int i = 0
while(p)
{
p = p->next
i++
}
return i
}
/*
*前置条件：单链表存在
*输入：要删除元素位置i
*功能：删除单链表中位置为i的元素
*输出：无
*后置条件：单链表删除元素
*/
template <class T>
T LinkList<T>::Delete(int i)
{
Node<T>*pint j
p=first j=0 //工作指针p初始化
while (p &&j<i-1) //查找第i-1个结点
{
p=p->next
j++
}
if (!p || !p->next) throw "位置" //结点p不存在或结点p的后继结点不存在
else {
Node<T>*qint x
q=p->nextx=q->data //暂存被删结点
p->next=q->next //摘链
delete q
return x
}
}
/*
*前置条件：单链表存在
*输入：无
*功能：单链表遍历
*输出：输出所有元素
*后置条件：单链表不变
*/
template <class T>
void LinkList<T>::PrintList( )
{
Node<T>*p
p=first->next
while (p)
{
cout<<p->data<<endl
p=p->next
}
}
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。#include<iostream.h>
#include"LinkList.cpp"
#include"Node.h"
void main( )
{
LinkList <int>a
cout<<"执行插入操作:"<<endl
try
{
a.Insert(1,4)
a.Insert(2,5)
a.Insert(3,6)
}
catch(char* wrong)
{
cout <<wrong//如失败提示失败信息
}
cout<<"已经插入“4，5，6”"<<endl
cout<<"单链表a的长度为:"<<endl
cout<<a.Length()<<endl//返回单链表长度
cout<<endl
cout<<"单链表a的元素为:"<<endl
a.PrintList() //显示链表中所有元素
cout<<endl
cout<<"按位查找第二个元素:"<<endl
cout<<"第二个元素为:"
cout<<a.Get(2)<<endl //查找链表中第二个元素
cout<<endl
cout<<"按值查找5"<<endl
cout<<"值为5的元素位置为:"
cout<<a.Locate(5)<<endl //查找元素5，并返回在单链表中位置
cout<<endl
cout<<"执行删除4的操作"<<endl
a.Delete(1) //删除元素4
cout<<"已删除成功，单链表a的长度为"
cout<<a.Length()<<endl
cout<<endl
cout<<"链表a中的元素为:"<<endl
a.PrintList()
int r[ ]={1,2,3,4,5}
LinkList <int>b(r,5)//根据数组创建顺序表
cout<<"执行插入操作前单链表b为:"<<endl
b.PrintList() //输出单链表所有元素
cout<<"插入前单链表b的长度为:"
cout<<b.Length()<<endl
try
{
b.Insert(3,8)
}
catch(char* wrong)
{
cout <<wrong//如失败提示失败信息
}
cout<<"执行插入操作后单链表b为:"<<endl
b.PrintList() //输出单链表b所有元素
cout<<"插入后单链表b的长度为:"
cout<<b.Length()<<endl
cout<<endl
try
{
if(a.Length()){
cout<<"执行删除第一个元素操作:"<<endl
cout<<endl
b.Delete(1) //删除b中第一个元素
cout<<"已删除成功，单链表b的长度为:"
cout<<b.Length()<<endl
}
else{
cout<<"顺序表b长度为0"<<endl
}
}
catch(char* wrong)
{
cout <<wrong//如失败提示失败信息
}
cout<<"执行插入操作后单链表b为:"<<endl
b.PrintList() //输出单链表所有元素
}
