#include<stdio.h>
#include<stdlib.h>
#define ElemType int
typedef struct LNode //定义单链表节点类型
{
ElemType data; //每个节点存放下一个数据元素
struct LNode* next;//指针指向下一个结点
}LNode, * LinkList;
1.要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个结点
//LNode * L;//声明一个指向单链表第一个结点的指针 想强调是一个结点
//LinkList L;//声明一个指向单链表第一个结点的指针 想强调是一个单链表
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 != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
bool InitList(LinkList& L)
{
L = (LNode*)malloc(sizeof(LNode));//分配一个头结点
if (L == NULL) //内存不足分配失败
return false;
L->next = NULL; //头结点之和暂时还没有结点
return true;
}
void test()
{
LinkList L;//声明指向一个单链表的指针
//初始化一个表
InitList(L);
//。。。。。后续代码。。。。。。
}
// 2.//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i < 1)
return false;
LNode* p;//指针指向当前扫描的结点
int j = 0;//当p指向的是第几个结点
p = L;//L指向头结点，头结点是第0个节点（不存数据）
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;//这两步不可以颠倒
p->next = s;
return true;
}
//3.在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i < 1)
return false;//（不带头结点区别->）
if (i == 1) //插入第1个结点的操作与其他结点操作不同
{
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s; //头指针指向的新结点
return true;
}//（<-不带头结点区别）
LNode* p;//指针指向当前扫描的结点
int j = 1;//当p指向的是第几个结点*****(区别）
p = L;//L指向头结点，头结点是第0个节点（不存数据）
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;//这两步不可以颠倒
p->next = s;
return true;
}
//4.插入函数 封装
bool InsertLNode(LNode* p, ElemType e)
{
if (p == NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s == NULL)
return false;
s->data = e;
s->next = p->next;//这两步不可以颠倒
p->next = s;
return true;
}
//5.前插操作：在p结点之前插入元素e
bool InsertpriorLNode(LNode* p, ElemType e)
{
if (p == NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s == NULL)
return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
//6.按位删除（带头结点的）
bool ListDelete(LinkList& L, int i, ElemType &e)
{
if (i < 1)
return false;
LNode* p;//指针指向当前扫描的结点
int j = 0;//当p指向的是第几个结点
p = L;//L指向头结点，头结点是第0个节点（不存数据）
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
if (p->next == NULL)
return false;
LNode* q = p->next;//令q指向被删除的结点
e = q->data;//用e返回元素的值
q->next = p->next;
free(q);
return true;
}
//7.按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i)
{
if (i < 0)
return NULL;
LNode* p;
int j = 0;
p = L;
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
//8. 按值查找，找到数据域 ==e 的结点
LNode* LocateElse(LinkList L, ElemType e)
{
LNode* p = L->next;
//从第1个结点开始查找数据域为e 的结点
while (p != NULL && p->data != e)
{
p = p->next;
}
return p;
}
//9.尾插法建立单链表
LinkList List_Tailsert(LinkList& L)
{
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode* s, * r = L;
scanf("%d", &x);
while (x != 9999)
{
s= (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
return L;
}
//10,头插法建立单链表
LinkList List_Headlnsert(LinkList& L)
{
LNode* s;
int x;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d", &x);
while (x != 9999)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}//头插法重要应用：链表的逆置