1_单链表的基本操作：
1.1_表的声明
typedef int ElemType;
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
1.2_头插法(可以实现表的逆置)
//头插法 实现的是倒叙输出
LinkList List_HeadInsert(LinkList &L){
LNode *s;
int x;
L=(LinkList) malloc (sizeof(LNode));
L->next = NULL;
scanf("%d",&x);
while(x!=999){
s = (LNode*) malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d",&x);
}
return L;
}
程序输入：
1 2 3 4 5 999
程序输出：
5 4 3 2 1
1.3_尾插法(正向建立单链表)
//尾插法 也就是在最后的一个元素插入
LinkList List_TailInsert(LinkList &L){
int x;
L = (LinkList) malloc(sizeof (LNode));
LNode *s,*r = L;
scanf("%d",&x);
while (x!=999){
s = (LinkList) malloc(sizeof (LNode));
s->data = x; //声明一个内存放数据元素
r ->next = s; //使我们的r的next指向s [rs] => [r]->[s]
r = s; //然后又让我们的rs呆在一起继续合作[r]->[s]=>[rs]即指向尾节点
scanf("%d",&x);
}
r->next=NULL; //r最后指向NULL 即为为尾节点
return L; //给用户返回单链表
}
程序输入：
1 2 3 4 5 999
程序输出：
1 2 3 4 5
1.4_指定位序插入
//插入元素 在指定的位置插入
void Insert(LinkList &L,int i,ElemType E){
LNode *p;
LNode *s = (LNode*)malloc(sizeof (LNode));
s->data = E;
s->next = NULL;
p = GetElem(L,i-1);
if(p!=NULL){
s->next = p->next;
p->next = s;
}else{
cout<<"插入值非法"<<endl;
}
}
程序输入：
1 2 3 4 5 999
程序输出：
5 4 3 2 1
在第三个位置插入元素10
5 4 10 3 2 1
1.5_查找第i个元素(位序查找)
//查找第i个元素值
LNode *GetElem(LinkList L,int i){
int j = 1;
LNode *p = L->next;
if (i == 0){
return L;
}
if (i < 1){
return NULL;
}
while (p->next!=NULL&&j<i)
{
p=p->next;
j++;
}
return p;
}
程序输入：
1 2 3 4 5 999
程序输出：
5 4 3 2 1
这是按位序查找,查找(位序为1)的元素的值:5
1.6_指定元素查找
//找到指定元素的位序
//int e就是我们需要找到的元素如果有返回数据[data[next]]
LNode *FindByEle(LinkList L,int e){
LNode *p = L->next;
while(p!=NULL && p->data!=e){
p = p->next;
}
return p;
}
程序输入：
1 2 3 4 5 999
程序输出：
5 4 3 2 1
找到元素为三的元素:3
1.7_打印单链表
//打印单链表
void PrintLinkList(LinkList L){
LNode *tmp = L->next; //这里我们开始第一个元素
if (tmp == NULL){ //如果第一个元素的值为null即为空
printf("链表为空");
}
while(tmp != NULL){ //循环取数据
cout<<tmp->data<<" ";
tmp = tmp->next;
}
}
1.8_按位序删除某个节点
//按位序删除节点
void Delete_LinkList(LinkList &L,int i,ElemType &e){
//p所指的节点是q所指的节点的前驱节点
LNode *p;
LNode *q = (LNode*) malloc(sizeof (LNode));
p = GetElem(L,i-1); //我们调用了上面GetElem但是实际上我们取的是第i-1个元素
if(p==NULL || p->next==NULL){
cout<<"非法删除"<<endl;
free(q);
}
q=p->next; //我们从上面的i-1得到第i-1个元素
e = q->data; //取出删除节点的数据
p->next = q->next; //声明一个新节点接受i-1的next 也就是我们要删除的节点
free(q); //我们再free之前就先把i-1的next指向i的next就很OK!
程序输入：
1 2 3 4 5 999
程序输出：
5 4 3 2 1
这是按位序删除(位序为2),被删除的元素值:4
5 3 2 1
1.9_删除某个节点的时间复杂度为O(1)的
bool DeleteNode(LNode *p){
if(p==NULL){
return false;
}
LNode *q = p->next; //令q指向*p的后继节点
p->data=p->next->data; //和后继节点交换数据
p->next=q->next; //将*q节点从链中"断开"
free(p); //释放
return true;
}
注释：
我们想要删除
[1]->[2]->[3]->[4]....
通过上面的GetElem得到想要删除的节点p。在这里我们假设是第三个
1、那么平时的做法就是头开始遍历。使得[2]->next = [3]->next 即是[2]->[4] 释放[3]就可以了
2、这个做法是我们虽然不能移动指针但是数据可以移动。即将[4]的数据转移到[3]上来 释放[4]即可
那么[3]->data = [4]->data也就是我们上面的[p[3]->data=[p->next][4]->data]。断开[4]
即是[p[3]->next=q[4]->next]。为了方便理解我们假设在[4]后有一个[5].那么[4]->next = [5]不是吗？是不是特别容易理解！
我可真聪明哈哈哈哈！
2_全部代码
#include <stdio.h>
#include "iostream"
using namespace std;
typedef int ElemType;
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
//头插法 实现的是倒叙输出
LinkList List_HeadInsert(LinkList &L){
LNode *s;
int x;
L=(LinkList) malloc (sizeof(LNode));
L->next = NULL;
scanf("%d",&x);
while(x!=999){
s = (LNode*) malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d",&x);
}
return L;
}
//打印单链表
void PrintLinkList(LinkList L){
LNode *tmp = L->next;
if (tmp == NULL){
printf("链表为空");
}
while(tmp != NULL){
cout<<tmp->data<<" ";
tmp = tmp->next;
}
}
//找到指定元素的位序
LNode *FindByEle(LinkList L,int e){
LNode *p = L->next;
while(p!=NULL && p->data!=e){
p = p->next;
}
return p;
}
//查找第i个元素值
LNode *GetElem(LinkList L,int i){
int j = 1;
LNode *p = L->next;
if (i == 0){
return L;
}
if (i < 1){
return NULL;
}
while (p->next!=NULL&&j<i)
{
p=p->next;
j++;
}
return p;
}
//按位序删除节点
void Delete_LinkList(LinkList &L,int i,ElemType &e){
//p所指的节点是q所指的节点的前驱节点
LNode *p;
LNode *q = (LNode*) malloc(sizeof (LNode));
p = GetElem(L,i-1);
if(p==NULL || p->next==NULL){
cout<<"非法删除"<<endl;
free(q);
}
q=p->next; //我们从上面的i-1得到第i-1个元素
e = q->data;
p->next = q->next; //然后在声明一个新节点接受i-1的next 也就是我们要删除的节点
free(q); //我们再free之前就先把i-1的next指向i的nextfree就没事啦
}
//插入元素 在指定的位置插入
void Insert(LinkList &L,int i,ElemType E){
LNode *p;
LNode *s = (LNode *)malloc(sizeof (LNode));
s->data = E;
s->next = NULL;
p = GetElem(L,i-1);
if(p!=NULL){
s->next = p->next;
p->next = s;
}else{
cout<<"插入值非法"<<endl;
}
}
//尾插法 也就是在最后的一个元素插入
LinkList List_TailInsert(LinkList &L){
int x;
L = (LinkList) malloc(sizeof (LNode));
LNode *s,*r = L;
scanf("%d",&x);
while (x!=999){
s = (LinkList) malloc(sizeof (LNode));
s->data = x; //声明一个内存放数据元素
r ->next = s; //使我们的r的next指向s [rs] => [r]->[s]
r = s; //然后又让我们的rs呆在一起继续合作 [r]->[s] => [rs] 即指向尾节点
scanf("%d",&x);
}
r->next=NULL; //r最后指向NULL 即为为尾节点
return L; //给用户返回单链表
}
int main() {
LinkList L;
List_HeadInsert(L);
PrintLinkList(L);
int e;
Delete_LinkList(L,2,e);
cout<<"\n"<<"这是按位序删除(位序为2),被删除的元素值:"<<e<<endl;
PrintLinkList(L);
//查找第i个元素
cout<<"\n"<<"这是按位序查找,查找(位序为1)的元素的值:"<<GetElem(L,1)->data<<endl;
LNode *pNode = FindByEle(L, 3);
cout<<"找到元素为三的元素:"<<pNode->data<<endl;
//在第三个位置插入元素10
cout<<"在第三个位置插入元素10"<<endl;
Insert(L,3,10);
PrintLinkList(L);
return 0;
LinkList TailL;
List_TailInsert(TailL);
PrintLinkList(TailL);
}
程序输入：
1 2 3 4 5 999
程序输出：
5 4 3 2 1
这是按位序删除(位序为2),被删除的元素值:4
5 3 2 1
这是按位序查找,查找(位序为1)的元素的值:5
找到元素为三的元素:3
在第三个位置插入元素10
5 3 10 2 1
