用C++编写完整的异质链表。整数、浮点数、字符串等不同类型的对象都可以放在同一个链表上。
list.h
#ifndef _LIST_H
#define _LIST_H
#include"utili.h"
typedef int ElemType;
template
class List;
template
class ListNode
{
friend class List;
public:
ListNode():prev(NULL),next(NULL),data(Type())
{}
ListNode(Type d,ListNode *p = NULL,ListNode *n = NULL):data(d),prev(p),next(n)
{}
private:
ListNode *prev;
ListNode *next;
Type data;
};
template
class List
{
public:
List()
{
first = last = new ListNode;
size = 0;
first->prev = last;
last->next = first;
}
~List()
{
}
public:
bool Is_Empty() //判断是否为空
{
if(first->next == first)
return true;
else
return false;
}
void push_back(const ElemType &e) //后插
{
ListNode *p = new ListNode(e);
p->prev = last;
p->next = first;
last->next = p;
first->prev = p;
last = p;
++size;
}
void show_list() //打印函数
{
ListNode<Type> *p = first->next;
while(p != first)
{
cout<<p->data<<"-->";
p = p->next;
}
cout<<"Over!"<<endl;
}
void push_front(const ElemType &e) //头插函数
{
ListNode<Type> *p = new ListNode<Type>(e);
p->next = first->next;
first->next->prev = p;
first->next = p;
p->prev = first;
if(0 == size)
last = p;
++size;
}
ListNode<Type>* find(const ElemType &e) //查找函数
{
ListNode<Type> *p = first->next;
while(p != NULL && p->data != e)
{
p = p->next;
}
return p;
}
void pop_back() //尾删
{
if(Is_Empty() == true)
return;
else
{
ListNode<Type> *p = last->prev;
p->next = first;
first->prev = p;
delete last;
last = p;
--size;
}
}
void pop_front() //头删函数
{
if(Is_Empty() == true)
return;
else
{
ListNode<Type> *q,*p = first;
q = p->next;
p->next = q->next;
q->next->prev = p;
if(size == 1)
last = first;
--size;
}
}
bool insert_val(const Type &x) //按值插入
{
ListNode<Type> *q,*p = new ListNode<Type>(x);
q = first->next;
while(q != first && q->data > x)
q = q->next;
p->prev = q;
p->next = q->next;
q->next->prev = p;
q->next = p;
++size;
return true;
}
bool delete_val(const Type &x) //按值删除
{
if(Is_Empty() == true)
return true;
ListNode<Type> *t,*p = first->next;
while(p->data != x && p != first)
p = p->next;
if(p == first)
return false;
else
{
if(p == last)
pop_back();
else if(p == first->next)
pop_front();
else
{
t = p->prev;
t->next = p->next;
p->next->prev = t;
delete p;
--size;
}
return true;
}
}
void clear() //清空函数
{
ListNode<Type> *p = first->next,*q;
while(p != first)
{
q = p->next;
delete p;
p = q;
}
first->next = first;
first->prev = first;
last = first;
size = 0;
}
void insert(ListNode<Type> *p)
{
ListNode<Type> *t = first;
while(t->next != first && t->next->data < p->data)
t = t->next;
if(t->next == first)
last = p;
else
t->next->prev = p;
p->next = t->next;
t->next = p;
p->prev = t;
}
void sort() //排序函数
{
ListNode<Type> *p = first->next,*q = p->next;
p->next = first;
last = p;
while(q != first)
{
p = q;
q = p->next;
insert(p);
}
}
void reverse() //转置函数
{
ListNode<Type> *p = first->next,*q = p->next;
p->next = first;
last = p;
while(q != first)
{
p = q;
q = p->next;
push_front(p->data);
delete p;
}
}
private:
ListNode *first;
ListNode *last;
size_t size;
};
#endif
main.cpp
#include"list.h"
int main()
{
List mylist;
int select = 1;
ElemType Item;
int postion,value;
while(select)
{
cout<<"******************************************"< cout cout cout cout cout cout cout cout cout";
cin>>select;
switch(select)
{
case 1:
cout<<"input data(-1 Over):>";
while(cin>>Item,Item != -1)
mylist.push_back(Item);
break;
case 2:
cout<<"input data(-1 Over):>";
while(cin>>Item,Item != -1)
mylist.push_front(Item);
break;
case 3:
mylist.show_list();
break;
case 4:
mylist.pop_back();
break;
case 5:
mylist.pop_front();
break;
case 6:
cout<<"输入要插入的元素:>";
cin>>Item;
mylist.insert_val(Item);
break;
case 7:
cout<<"请输入要删除的值:";
cin>>Item;
if(mylist.delete_val(Item))
cout<<"删除成功"<<endl;
else
cout<<"删除失败"<<endl;
break;
case 8:
cout<<"请输入要查找的值:"<<endl;
cin>>Item;
if(mylist.find(Item) == NULL)
cout<<"没有找到"<<endl;
else
cout<<"找到"<<endl;
case 9:
mylist.clear();
break;
case 10:
mylist.sort();
break;
case 11:
mylist.reverse();
break;
case 12:
if(mylist.Is_Empty() == true)
cout<<"空"<<endl;
else
cout<<"不空"<<endl;
default:
break;
}
}
return 0;
}
utili.h
#ifndef _UTULI_H
#define _UTULI_H
#include
using namespace std;
#endif
// LinkList.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
//追加末尾节点
CLType * CltAddEnd(CLType *head, Data nodeData) {
CLType *temp, *node;
node = (CLType *)malloc(sizeof(CLType));
node->nodeData = nodeData;
node->nextNode = NULL;
if (head == NULL) {
head = node; //此处head指向内存地址会改变，因此需要函数返回指针
return head;
}
temp = head;
while (temp->nextNode != NULL){
temp = temp->nextNode;
}
temp->nextNode = node;
return head;
}
//中间插入节点
void InsertNode(CLType *head, char findKey, Data data) {
CLType *node = (CLType *)malloc(sizeof(CLType));
CLType *temp = head;
node->nodeData = data;
while (temp->nodeData.key != findKey) {
if (temp->nextNode != NULL) {
temp = temp->nextNode;
}
else
{
break;
}
}
node->nextNode = temp->nextNode;
temp->nextNode = node;
}
//随机生成数据
Data RandMakeData() {
Data data;
data.age = rand()%100;
data.key = rand()%100;
data.name = rand()%100;
return data;
}
int main(){
CLType *node, *head = NULL;
for (int i = 0; i < 10; i++) {
head = CltAddEnd(head, RandMakeData());
}
node = head;
while (node->nextNode != NULL) {
cout << node->nodeData.age << node->nodeData.key << endl;
node = node->nextNode;
}
cout << "输入想插入的位置：" << endl;
char a;
cin >> a;
InsertNode(head, a, RandMakeData());
cout << "插入后：" << endl;
node = head;
while (node->nextNode != NULL) {
cout << node->nodeData.age << node->nodeData.key << endl;
node = node->nextNode;
}
system("pause");
return 0;
}