#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
struct ListNode
{
int m_iData;
ListNode* m_pNext;
};
//头插法建表，把要插入的数字放在头节点的后面，都往前插。
void CreateListF(ListNode *&L, ElemType a[], int n)
{
ListNode *s;
L = (ListNode *)malloc(sizeof(ListNode));
L->m_pNext = NULL;
for (int i = 0; i < n; i++)
{
s = (ListNode*)malloc(sizeof(ListNode));
s->m_iData = a[i];
s->m_pNext = L->m_pNext;
L->m_pNext = s;
}
}
//尾插法，每个元素都插在链表的最后面，需要一个尾指针
void CreateListT(ListNode *&L, ElemType a[], int n)
{
ListNode *s,*r;
L = (ListNode*)malloc(sizeof(ListNode));
L->m_pNext = NULL;
r = L;//r是尾指针，它开始指向头节点
for (int i = 0; i < n; i++)
{
s = (ListNode*)malloc(sizeof(ListNode));
s->m_iData = a[i];
r->m_pNext = s;//将*s插入*r之后
r = s;
}
r->m_pNext = NULL;//尾结点next域置为NULL
}
//链表的初始化
void InitList(ListNode *&L)
{
L = (ListNode*)malloc(sizeof(ListNode));
L->m_pNext = NULL;
}
//销毁单链表
void Destroy(ListNode *&L)
{
ListNode *pre = L;
ListNode *p = L->m_pNext;//pre指向*p的前驱节点
while (p != NULL)//扫描单链表L
{
free(pre);//释放*pre节点
pre = p;//pre、p同步后移一个节点
p = pre->m_pNext;
}
free(pre);//循环结束时，P为NULL，pre指向尾结点，释放它
}
//判空
bool ListEmpty(ListNode *L)
{
if (L->m_pNext == NULL)
return true;
else
return false;
}
//求表长
int ListLength(ListNode *L)
{
int n=0;
ListNode *r;
r = L;
while (r->m_pNext != NULL)
{
n++;
r = r->m_pNext;
}
return n ;//循环结束，p指向尾结点，其序号n为节点个数
}
//打印链表内容
void DisplayList(ListNode *L)
{
ListNode *p = L->m_pNext;//p指向开始节点
while (p!= NULL)//p不为NULL的时候，输出它的数据域
{
printf("%d ", p->m_iData);
p = p->m_pNext;//p移向下一个节点
}
printf("\n");
}
//求表L中位置i的数据元素GetElem(L,i,&e)
//思路：在单链表L中从头开始找到第i个节点，若存在第i个数据节点，则将其data域值赋给变量e.
bool GetElem(ListNode *L,int i, ElemType &e)
{
int j = 0;
ListNode *p = L;
while (j < i&&p!= NULL)//找第i个节点*p
{
j++;
p = p->m_pNext;
}
if (p == NULL)//不存在第i个数据节点，返回false
{
return false;
}
else //存在第i个数据节点，返回true
{
e = p->m_iData;
return true;
}
}
//定位：按元素查找LocateElem(L,e)
//思路：在单链表L中从头开始找第一个值域与e相等的节点，若存在这样的节点，则返回位置，否则返回0.
int LocateElem(ListNode *L, ElemType e)
{
int i = 1;
ListNode *p = L->m_pNext;//p指向开始节点，i置为1
while (p != NULL && p->m_iData != e)
{
i++;
p = p->m_pNext;
}
if (p == NULL)
{
return -1;
}
else
return i;
}
//插入数据元素ListInsert(&L,i,e),在第i个位置插入元素e
//思路：先在单链表L中找到第i-1个节点*p,若存在这样的节点，将值为e的节点*s插入到其后
bool ListInsert(ListNode *&L, int i, ElemType e)
{
ListNode *s;
int j = 0;
ListNode *p = L;
while (j < i - 1 && p!= NULL)
{
j++;
p = p->m_pNext;
}
if (p == NULL||j>i-1)
{
return false;
}
else
{
s = (ListNode*)malloc(sizeof(ListNode));//创建新节点*s,其data域置为e
s->m_iData = e;
s->m_pNext = p->m_pNext;//将*s插入到*p之后
p->m_pNext = s;
return true;
}
}
//删除数据元素ListDelete(&L,i,&e),删除第i个位置的元素
//思路：先在单链表L中找到第i-1个节点*p,若存在这样的节点，且也存在后继节点，则删除该后继节点
//找第i-1个节点的原因是删除后便于进行节点指针的变换
bool ListDelete(ListNode *&L, int i, ElemType *e)
{
ListNode *p = L;
int j = 0;
while (j < i-1&&p != NULL)
{
j++;
p = p->m_pNext;
}
if (p == NULL)
{
return false;
}
else
{
if (p->m_pNext == NULL)
{
return false;
}
*e = p->m_pNext->m_iData;
p->m_pNext = p->m_pNext->m_pNext;
return true;
}
}
//从尾到头打印链表
void Listprint_rear_to_head(ListNode *L)
{
ListNode *p = L->m_pNext;
if (p != NULL)
{
if(p->m_pNext != NULL)
{
Listprint_rear_to_head(p);
}
printf("%d ", p->m_iData);
}
}
int main()
{
ListNode *L,*L1;
ElemType e,e1;
int a[10] = { 2,2,3,4,5,4,3,2,2,1 };
CreateListT(L1, a, 10);
CreateListF(L, a, 10);
DisplayList(L);
DisplayList(L1);
if (GetElem(L, 3, e) == true)
{
printf("第三个元素位置为;");
printf("%d\n", e);
}
printf("元素5的位置为;");
printf("%d\n",LocateElem(L, 5));
printf("从尾到头打印链表为;");
Listprint_rear_to_head(L);
printf("\n");
if (ListInsert(L, 4, 8) == true)
{
printf("插入后链表元素为;");
DisplayList(L);
}
if (ListDelete(L, 5, &e1) == true)
{
printf("删除后链表元素为;");
DisplayList(L);
}
return 0;
}
