#include<iostream>
using namespace std;
//定义
typedef struct _LinkNode
{
int data;//结点的数据域
struct _LinkNode*next;//结点的指针域
}LinkNode,Linklist;
//初始化
bool InitList(Linklist*&L)
{
L=new LinkNode;
if(!L)return false;
L->next=NULL;
return true;
}
//头插法
bool ListInsert_front(Linklist* &L,LinkNode *node)
{
if(!L||!node)return false;
node->next=L->next;
L->next=node;
return true;
}
//尾插法
bool ListInsert_back(Linklist*&L,LinkNode*node)
{
LinkNode*last=NULL;
if(!L||!node)return false;
last=L;
while(last->next)
last=last->next;
node->next=NULL;
last->next=node;
return true;
}
//任意位置插入 O(n)
bool ListInsert(Linklist*&L,int i,int e)
{
if(!L)return false;
int j=0;
Linklist*p,*s;
p=L;
while(p&&j<i-1)
{
p=p->next;
j++;
}
if(!p||j>i-1)
return false;
s=new LinkNode;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
//单链表按位置取值
bool Link_GetElem(Linklist *&L, int i, int& e) {
//在带头节点的单链表L中查找第i个元素
//用e记录L中第i个元素的值
int index;
Linklist* p;
if (!L || !L->next) return false;
p = L->next;
index = 1;
while (p && index < i) {//链表向后扫描,直到p指向第i个元素或者p为空
p = p->next;
index++;
}
if (!p || index > i) return false;//i值不合法,i>n或i<=0;
e = p->data;
return true;
}
//按值取位
bool Linklist_FindElement(Linklist*L,int e,int &index)
{
Linklist*p;
p=L->next;
index=1;
if(!L||!L->next)
{
index=-1;
return false;
}
while(p&&p->data!=e)
{
p=p->next;
index++;
}
if(!p)
{
index=-1;
return false;
}
return true;
}
//删除结点O(n)
bool LinklistDelete(Linklist*L,int i)
{
Linklist*p,*q;
p=L;
int index=0;
if(!L||!L->next)return false;
while((p->next)&&(index<i-1))
{
index++;
p=p->next;
}
if(!p->next||index>i-1)
return false;
q=p->next;
p->next=q->next;
delete q;
return false;
}
//销毁链表
void LinklistDestroy(Linklist*&L)
{
Linklist*p=L;
while(p)
{
p=L;
delete p;
L=L->next;
}
}
//销毁链表
void LinklistDestroy(Linklist*&L)
{
Linklist*p=L;
while(p)
{
p=L;
delete p;
L=L->next;
}
}
//键盘输入
bool scanfList(Linklist*&L){
int n;
int i = 1;
cin>>n;
while (n)
{
int e;
cin>>e;
if (!ListInsert(L, i, e)) return false;
n--;
}
return true;
}
int main(){
int n;
Linklist* L=NULL;
Linklist* s = NULL;
//1.初始化一个空的链表
InitList(L);
//2.使用前插法插入数据
cout << "前插法创建单链表" << endl;
cout << "请输入插入的个数n:";
cin >> n;
while (n > 0) {
s = new LinkNode;//生成新结点s
cin >> s->data;
ListInsert_front(L, s);
n--;
}
//3.使用尾插法插入数据
cout << "尾插法创建单链表" << endl;
cout << "请输入插入的个数n:";
cin >> n;
while (n > 0) {
s = new LinkNode;//生成新结点s
cin >> s->data;
ListInsert_back(L, s);
n--;
}
//4.单链表的输出
LinkPrint(L);
//5.任意位置插入元素
for (int j = 0; j < 3; j++) {
int i, x;
cout << "请输入插入元素的位置及值:";
cin >> i >> x;
if (ListInsert(L, i, x)) {
cout << "插入成功" << endl;
}
else {
cout << "插入失败" << endl;
}
LinkPrint(L);
}
//6.单链表取值
int element;
cout << "请输入你要获取值的位置" ;
cin >> n;
if (Link_GetElem(L, n, element)) {
cout << "第" << n << "元素的值为:" << element << endl;
}
else {
cout << "第" <<n<< "个元素的值获取失败!" << endl;
}
//7.单链表按值查找
int index = 0;
cout << "输入你要查询值的位置:";
cin >> n;
if (Linklist_FindElement(L, n, index)){
cout<<"你查询值为"<<n<<"的位置为"<<index<<endl;
}
else {
cout << "你查询值为" << n << "的位置为" << index << endl;
}
//8.单链表的删除元素
cout << "请输入你要删除第几个元素:";
cin >> n;
if (LinklistDelete(L, n)) {
cout << "删除第" << n << "元素成功!" << endl;
LinkPrint(L);
}
else {
cout << "删除第" << n << "元素失败!" << endl;
}
//9.销毁单链表
LinklistDestroy(L);
return 0;
}
标签:index,结点,单链,return,cout,int,c++,next,Linklist From: https://blog.csdn.net/2301_79727388/article/details/142579878