#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
typedef char ElemType;
typedef struct LNode
{
ElemType data; //存储数据元素
struct LNode * next;
}LNode, *LinkList;
//头插法建立单链表
void CreateListF(LinkList &L, ElemType a[], int n)
{
LNode * s;
L=new LNode; //创建头结点
L->next=NULL;
for (int i=0;i<n;i++)
{
s=new LNode;//创建新结点s
s->data=a[i];
s->next=L->next; //将结点s插在原开始结点之前，头结点之后
L->next=s;
}
}
//尾插法建立单链表
void CreateListR(LinkList &L, ElemType a[], int n)//可以改用LinkList &L
{
LNode * s, *r;
L=new LNode; //创建头结点
L->next=NULL;
r=L;//r始终指向尾结点，开始时指向头结点
for (int i=0;i<n;i++)
{
s=new LNode;//创建新结点s
s->data=a[i];
r->next=s; //结点s插入r结点之后
r=s;
}
r->next=NULL;//尾结点next域置为空
}
//初始化
void InitList(LinkList &L)
{
L=new LNode;//创建头结点
L->next = NULL;//置为空表
}
//销毁
bool DestroyList(LinkList &L)
{
LNode * p;
while(L)//当L指向的当前结点非空时
{
p=L;//让p指向L指向的当前结点
L=L->next;//L后移指向当前结点的后继结点
delete p; //删除当前结点
}
return true;
}
//判断是否为空表
int ListEmpty(LinkList L)
{//若L为空表，则返回1，否则返回0
if(L->next) //L->next不是NULL,链表非空
return 0;
else
return 1;
}
//求表长,返回L中数据元素的个数
int ListLength(LinkList L)
{
int i=0;
LNode * p=L->next; //p指向首元结点
while(p!=NULL) //遍历单链表，统计结点数
{
i++;
p=p->next;
}
return i ;
}
//输出
void DispList(LinkList L)
{
LNode * p=L->next; //p指向首元结点
while(p!=NULL)
{
printf("%c",p->data); //p不为NULL,输出p结点的data域
p=p->next; //p移向下一个结点
}
}
//求第i个元素值
bool GetElem(LinkList L,int i,ElemType &e)
{
LNode *p=L->next;
int j=1; //初始化
while(p && j<i) //向后扫描，直到p指向第i个元素或p为空
{
p=p->next;
++j;
}
if(!p || j>i)
return false; //第i个元素不存在
e=p->data; //取第i个元素
return true;
}
//查找第一个值域为e的元素序号（逻辑序号）
int LocateElem(LNode *L, ElemType e)
{ int i=1;
LNode *p=L->next; //p指向首元结点，i置为1，即首元结点的序号为1
while(p!=NULL&&p->data!=e) //查找data值为e的结点
{
p=p->next;
i++;
}
if (p==NULL)
return 0;
else
return i; //存在值为e的结点，返回其逻辑序号i
}
//插入
bool ListInsert(LinkList &L,int i,ElemType e)
{
int j=0;
LNode * p=L; //p指向头结点，j置为0，即头结点的序号为0
if(i<=0)
return false; //i值不合法，返回false
while(j<i-1 && p!=NULL) //查找第i-1个结点
{
j++;
p=p->next;
}
if (p==NULL)
return false;
else //可以不要else
{
LNode *s =new LNode; //创建新结点，并用指针s指向该结点
s->data=e; //将s指向的结点的data域置为e
s->next=p->next;
p->next=s; //将s指向的结点插入链表L并插在p指向的结点之后
return true;
}
}
//删除
bool ListDelete(LinkList &L, int i, ElemType &e)
{
int j=0;
LNode * p=L;
LNode *q; //p指向头结点，j置为0，即头结点的序号为0
if(i<0)
return false; //i值不合法
while(j<i-1 && p!=NULL) //查找第i-1个结点
{
j++;
p=p->next;
}
if (p==NULL)
return false; //未找到第i-1个结点，返回false
else //找到LNode *第i-1个结点p，可以不要else
{
q=p->next; //q指向第i个结点
if (q==NULL)
return false; //若不存在第i个结点，返回false
e=q->data;
p->next=q->next; //从单链表中删除q结点
delete(q); //释放q结点
return true; //返回true表示成功删除
}
}
int main()
{
LinkList L;//LinkNode *L;
ElemType e;
printf("单链表的基本运算如下:\n");
printf(" (1)初始化单链表L\n");
InitList(L);
printf(" (2)依次采用尾插法插入U,V,W,X,Y元素\n");
ListInsert(L,1,'U');
ListInsert(L,2,'V');
ListInsert(L,3,'W');
ListInsert(L,4,'X');
ListInsert(L,5,'Y');
ListInsert(L,6,'Z');
printf(" (3)输出单链表L:");
DispList(L);
printf("\n");
printf(" (4)单链表L长度:%d\n",ListLength(L));
printf(" (5)单链表L为%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf(" (6)单链表L的第3个元素：%c\n",e);
printf(" (7)元素U的位置:%d\n",LocateElem(L,'U'));
printf(" (8)在第4个元素位置上插入A元素\n");
ListInsert(L,4,'A');
printf(" (9)输出单链表L:");
DispList(L);
printf("\n");
printf(" (10)单链表L长度:%d\n",ListLength(L));
printf(" (11)删除L的第3个元素\n");
ListDelete(L,3,e);
printf(" (12)输出单链表L:");
DispList(L);
printf("\n");
printf(" (13)释放单链表L\n");
DestroyList(L);
return 0;
}
评论0