#include <stdio.h>
#include <iostream>
using namespace std;
typedef int DataType;
#define Node ElemType
#define ERROR NULL
//构建一个节点类
class Node {
public:
int data; //数据域
Node* next;//指针域
};
//构建一个单链表
class LinkList {
public:
LinkList();//构造一个单链表
~LinkList();//析构
void CreateLinkList(int n);//创建单链表
int GetLength();//获取线性表长度
bool IsEmpty();//判断链表是否为空
ElemType* Find(DataType data);//查找节点
void InsertElemAtEnd(DataType data);//在尾部插入指定的元素
void InsertElemAtIndex(DataType data, int n);//指定位置插入指定元素
void InsertElemAtHead(DataType data);//在头部插入元素
void DeleteElemAtEnd();//在尾部插入元素
void DeleteAll();//删除所有的元素
void DeleteElemAtPoint(DataType data);//删除指定的数据
void DeleteElemAtHead();//在头部删除节点
void TravalLinkList();
private:
ElemType* head;
};
//初始化单链表
LinkList::LinkList() {
head = new ElemType;
head->data = 0;
head->next = NULL;
}
//销毁单链表
LinkList::~LinkList() {
delete head;
}
//创建一个单链表
void LinkList::CreateLinkList(int n) {
ElemType* pnew, * ptemp;
ptemp = head;
if (n < 0) {
printf("输入的节点个数有误");
//exit(EXIT_FAILURE);
}
for (int i = 0; i < n; i++) {
//将值一个个插入单链表中
pnew = new ElemType;
printf("请输入第%d个值\n", i + 1);
cin >> pnew->data;
pnew->next = NULL;//新的节点的下一个地址为NULL
ptemp->next = pnew;//当前界定啊的下一个地址设为新的节点
ptemp = pnew; //将当前节点设置为新的节点
}
}
//遍历单链表
void LinkList::TravalLinkList() {
if (head == NULL || head->next == NULL) {
printf("链表为空\n");
}
ElemType* p = head;
while (p->next != NULL) {
p = p->next;
cout << p->data << " ";
}
}
//获取单链表的长度
int LinkList::GetLength() {
int count = 0; //定义count 计数
ElemType* p = head->next; //定义p指向头节点
while (p != NULL) {
count++;
p = p->next;
}
return count;
}
//判断单链表是否为空
bool LinkList::IsEmpty() {
if (head->next == NULL) {
return true;
}
return false;
}
//查找节点
ElemType* LinkList::Find(DataType data) {
ElemType* p = head;
if (p == NULL) {//当链表为空时报异常
cout << "此链表为空" << endl;
return ERROR;
}
else {
while (p->next != NULL) { //返回每一个节点
if (p->data == data) {
return p; //返回指针域
}
p = p->next;
}
return NULL; //未查找到结果
}
}
//在指定的位置插入指定元素
void LinkList::InsertElemAtIndex(DataType data, int n) {
if (n <1 || n >GetLength()) {//输入有误报异常
printf("输入的值有误\n");
}
else {
ElemType* ptemp = new ElemType;//创建一个新的节点
ptemp->data = data;
ElemType* p = head;
int i = 1;
while (n > i) {
p = p->next;
i++;
}
ptemp->next = p->next;//将新的节点插入指定位置
p->next = ptemp;
}
}
void LinkList::InsertElemAtHead(DataType data) {
ElemType* newNode = new ElemType; //定义一个指定Node节点指针newNode
newNode->data = data;
ElemType* p = head;//定义指针p指向头节点
if (head == NULL) {
head = newNode;
}
newNode->next = p->next;
p->next = newNode;
}
//在尾部插入指定的元素
void LinkList::InsertElemAtEnd(DataType data) {
ElemType* newNode = new ElemType; //定义一个Node结点指针newNode
newNode->next = NULL; //定义newNode的数据域和指针域
newNode->data = data;
ElemType* p = head; //定义指针p指向头结点
if (head == NULL) { //当头结点为空时，设置newNode为头结点
head = newNode;
}
else //循环知道最后一个节点，将newNode放置在最后
{
while (p->next != NULL)
{
p = p->next;
}
p->next = newNode;
}
}
//在尾部删除元素
void LinkList::DeleteElemAtEnd() {
ElemType* p = head; //创建一个指针向头节点
ElemType* ptemp = NULL; //创建一个占位节点
if (p->next == NULL) {
printf("单链表为空\n");
}
else {
while (p->next != NULL) {
ptemp = p;
p = p->next;
}
delete p;
p = NULL;
ptemp->next = NULL;
}
}
void LinkList::DeleteAll() {
ElemType* p = head->next;
ElemType* ptemp = new ElemType;
while (p != NULL) {//在头节点的下一个节点逐个删除节点
ptemp = p;
p = p->next;
head->next = p;
ptemp->next = NULL;
delete ptemp;
}
head->next = NULL;//头节点的下一个节点指向NULL
}
//删除指定的数据
void LinkList::DeleteElemAtPoint(DataType data) {
ElemType* ptemp = Find(data);//查找到指定数据的节点位置
if (ptemp == head->next) {//判断是不是头节点的下一个系欸DNA，如果是就从头部删除了它
DeleteElemAtHead();
}
else {
ElemType* p = head; //p 指向头节点
while (p->next != ptemp) {//p循环到指定位置的前一个啊节点
p = p->next;
}
p->next = ptemp->next;//删除指定位置的节点
delete ptemp;
ptemp = NULL;
}
}
//在头部删除节点
void LinkList::DeleteElemAtHead() {
ElemType* p = head;
if (NULL == p || NULL == p->next) {//判断是否为空表，报异常
printf("该链表为空\n");
}
else {
ElemType* ptemp = NULL;//创新一个占位节点
p = p->next;
ptemp = p->next;//将头节点的下下个节点指向占位节点
delete p;
p = NULL;
head->next = ptemp;//头节点的指针更换
}
}
//测试函数
int main() {
LinkList l;
int i;
cout << "1.创建单链表\n2.遍历单链表\n3.获取单链表的长度\n4.判断单链表是否为空\n5.获取节点\n";
cout << "6.在尾部插入指定元素\n7.在指定位置插入指定元素\n8.在头部插入指定元素\n";
cout << "9.在尾部删除元素\n10.删除所有元素\n11.删除指定元素\n12.在头部删除元素\n0.退出" << endl;
do {
cout << "请输入要执行的操作" << endl;
cin >> i;
switch (i) {
case 1: {
int n;
cout << "请输入单链表的长度：" << endl;
cin >> n;
l.CreateLinkList(n);
break;
}
case 2: {
l.TravalLinkList();
break;
}
case 3: {
cout << "该链表的长度为" << l.GetLength() << endl;
break;
}
case 4: {
if (l.IsEmpty() == 1) {
cout << "该链表是为空表" << endl;
}
else {
cout << "该链表不是为空表" << endl;
}
break;
}
case 5: {
DataType data;
cout << "请输入要获取节点的值" << endl;
cin >> data;
cout << "该节点的值为" << l.Find(data)->data << endl;
break;
}
case 6: {
DataType endData;
cout << "请输入要在尾部插入的值" << endl;
cin >> endData;
l.InsertElemAtEnd(endData);
break;
}
case 7: {
DataType pointData;
int index;
cout << "请输入要插入的数据:" << endl;
cin >> pointData;
cout << "请输入要插入数据的位置：" << endl;
cin >> index;
l.InsertElemAtIndex(pointData, index);
break;
}
case 8: {
DataType headData;
cout << "请输入要在头部插入的值" << endl;
cin >> headData;
l.InsertElemAtHead(headData);
break;
}
case 9: {
l.DeleteElemAtEnd();
break;
}
case 10: {
l.DeleteAll();
break;
}
case 11: {
DataType pointDeleteData;
cout << "请输入要删除的数据" << endl;
cin >> pointDeleteData;
l.DeleteElemAtPoint(pointDeleteData);
break;
}
case 12: {
l.DeleteElemAtHead();
break;
default:
break;
}
}
} while (i != 0);
return 0;
}
c++小学期的链表作业
您必须 登录 才能发表评论