|
方便学习c++类和链表的结合
目录
一.单链表的数据结构
二.单链表的创建和销毁
三.单链表的插入
四.单链表的销毁
一.单链表的数据结构
单链表是一种常用的的链式存储线性数据结构，它用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点有数据域和指针域组成。链表正是通过每个结点的指针域将表中数据元素按其逻辑顺序链接在一起的。头指针指向指向单链表中的第一个结点，这是单链表操作的入口点，唯一标记一个单链表。
代码：
#include<iostream>
using namespace std;
struct LinkNode{
int dt;
struct LinkNode*next;
};
class LinkList{
public:
LinkList(){}
~LinkList(){}
};
int main()
{
return 0;
}
二.单链表的创建和销毁
在单链表的开始结点之前附设一个类型相同的结点，称之为头结点。头结点的数据域可以不存储任何信息。它的作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元素结点进行统一处理，免去对链表第一个结点的特殊处理，编程更方便。
代码：
#include <iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
typedef struct LinkNode
{
ElemType data;
struct LinkNode *next;
}LinkNode;
class LinkList
{
public:
LinkList();
~LinkList();
void Traverse()const;
protected:
LinkNode *head;
};
//此处添加代码
LinkList::LinkList()
{
head=(LinkNode*)malloc(sizeof(LinkNode));
head->data=0;
head->next=NULL;
}
LinkList::~LinkList()
{
free(head);
}
void LinkList::Traverse()const
{
LinkNode *p=head;
while(p!=NULL)
{
cout<<p->data<<endl;
p=p->next;
}
}
int main()
{
LinkList L;
L.Traverse();
return 0;
}
三.单链表的插入
已知单链表数据结构， 声明和定义在带头结点的单链表L中第pos个数据元素之前插入数据元素e的算法Insert。插入成功，则输出"OK"，插入失败(在小于等于0 或者大于n+1的位置上执行插入操作)则输出"ERROR"。
代码：
#include <iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
typedef struct LinkNode
{
ElemType data;
struct LinkNode *next;
}LinkNode;
class LinkList
{
public:
LinkList();
~LinkList();
void Traverse()const;
protected:
LinkNode *head;
};
//此处添加代码
LinkList::LinkList()
{
head=(LinkNode*)malloc(sizeof(LinkNode));
head->data=0;
head->next=NULL;
}
LinkList::~LinkList()
{
free(head);
}
void LinkList::Traverse()const
{
LinkNode *p=head;
while(p!=NULL)
{
cout<<p->data<<endl;
p=p->next;
}
}
int main()
{
LinkList L;
L.Traverse();
return 0;
}
四.单链表的销毁
已知单链表数据结构， 声明和定义在带头结点的单链表L中删除第pos个数据元素算法Delete。删除成功，则输出"OK"，删除失败(在小于1 或者大于n的位置上执行删除操作)则输出"ERROR"。
代码：
#include <iostream>
#include <cstdlib>
using namespace std;
typedef int ElemType;
typedef struct LinkNode
{
ElemType data;
struct LinkNode *next;
}LinkNode;
class LinkList
{
public:
LinkList();
~LinkList();
//请在此处输入Delete的声明
bool Delete(int pos);
bool Insert(int pos, ElemType e);
void Traverse()const;
protected:
LinkNode *head;
};
LinkList::LinkList()
{
head = new LinkNode;
head->data = 0;
head->next = NULL;
}
LinkList::~LinkList()
{
LinkNode *p = head;
while(head)
{
p = head;
head = head->next;
delete p;
}
head = NULL;
}
void LinkList::Traverse() const
{
LinkNode *p = head;
while(p)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
bool LinkList::Insert(int pos, ElemType e)
{
int i;
LinkNode *p, *q;
if(pos <= 0)
return false;
i = 0;
p = head;
while(i < pos-1 && p != NULL)
{
p = p->next;
i++;
}
if(p == NULL)
return false;
q = new LinkNode;
q->data = e;
q->next = p->next;
p->next = q;
return true;
}
//请在此处输入Delete的定义
bool LinkList::Delete(int pos)
{
int i;
LinkNode*p,*q;
if(pos<=0)
{
return false;
}
i=0;
p=head;
while(i=pos&&p!=NULL)
{
p=p->next;
i++;
}
if(p==NULL)
{
return false;
}
p=p->next;
q=q->next;
p->next=p->next->next;
delete p;
q=NULL;
return true;
}
int main()
{
LinkList L;
for(int i = 1; i <= 5; i++)
{
L.Insert(i, i);
L.Traverse();
}
int pos, e;
cin>>pos>>e;
//请在此处添加代码
if(L.Delete(pos)==1)
{
cout<<"OK"<<endl;
}
else
{
cout<<"ERROR"<<endl;
}
L.Traverse();
return 0;
}
|