// linklist.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>

#include<malloc.h>

#define MAXSIZE 100

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define NULL 0

//定义结构体类型LNode
struct LNode

{

int data;

struct LNode *next;

};

//定义Link,Position为LNode结构体指针类型
typedef LNode  *Link,*Position;


//定义LinkList结构体类型
typedef struct

{

Link head,tail; //定义head,tail变量，其类型为link结构体指针类型

int len;

}LinkList;


//创建一个节点,值为e
int MakeNode(Link &p,int e)

{ 

//分配由p指向的值为e的结点,并返回OK; 若分配失败,则返回ERROR

if(!(p=(Link)malloc(sizeof( Link ))))return ERROR;

p->data=e;

p->next=NULL;

return OK;

}


void FreeNode(Link &p)

{

//释放p所指的结点

free(p);

p=NULL;

}


int InitList(LinkList &L)

{

//构造一个空的线性链表L

L.tail=NULL;
L.head=NULL;

L.len=0;

return OK;

}




int InsFirst(LinkList &L,Link h,Link s)

{

// 已知h指向线性链表的第一元素结点,将s所指结点插入在第一个结点之前

if(!s)return ERROR;

s->next=h;

L.head=s;

if (L.tail==NULL) L.tail=s;

L.len++;

return OK;

}


int DelFirst(LinkList &L,Link &q)

{

//删除链表中的第一个结点并以q返回

if(!L.head)return ERROR;

q=L.head;

L.head=q->next;

if(q==L.tail)
{

L.tail=NULL;
L.head=NULL;
}

L.len--;

return OK;

}



int Append(LinkList &L,Link s)

{

//将指针s所指的一串结点链接在线性链表L的最后一个结点

if(!s)return ERROR;

L.tail->next=s;

L.len++;

while(s->next)

{

s=s->next;

L.len++;

}

L.tail=s;

return OK;

}

//
int Remove(LinkList &L,Link &q)

{
//删除线性链表L中的尾结点并以q返回,改变链表L的尾指针指向新的尾结点

if(!L.len) return ERROR;

Link p;

p=L.head;

while( p->next != L.tail) p=p->next;
q=p->next;

p->next=NULL;

L.tail=p;

L.len--;

return OK;

}

int LocatePos(LinkList L,int i,Link &p)

{

//返回p指示线性链表L中第i个结点的位置并返回OK，i 值不合法时返回ERROR

int j;

if(i<0||i>L.len)return ERROR;

p=L.head;

for(j=1;j<i;j++)

p=p->next;

return OK;

}



Position PriorPos(LinkList L, Link p)

{

//已知p指向线性链表中的一个结点，返回p所指结点的直接前驱的位置，若无前驱，则返回NULL

if(p==L.head->next)return NULL;

Link q;

q=L.head->next;

while(q->next!=p)

q=q->next;

return q;

}


Position NextPos(LinkList L, Link p)

{

//已知p指向线性链表中的一个结点，返回p所指结点的直接后继的位置，若无后继则返回NULL

return p->next;

}


int InsBefore(LinkList &L,Link &p,Link s)

{

//已知p指向线性链表L中的一个结点,将 s 所指结点插入在 p 所指的结点之前

if(!s||!p)return ERROR;

Link q;

q=PriorPos(L, p);

if(!q)

q=L.head;

q->next=s;

s->next=p;

//p=s;

L.len++;

return OK;

}


int InsAfter(LinkList &L,Link &p,Link s)

{

// 已知p指向线性链表L中的一个结点,将s所指结点插入在p所指的结点之后

if(!s||!p)return ERROR;

if(p==L.tail) L.tail=s;

s->next=p->next;

p->next=s;

L.len++;

return OK;

}


Position GetHead(LinkList L)

{

//返回线性链表L中头结点的位置

return L.head;

}


Position GetLast(LinkList L)

{

//返回线性链表L中最后一个结点的位置

return L.tail;

}

void Display(LinkList L) 
//输出链表各个节点值，并输出头尾指针所指元素值
{

int i;

Link p=L.head;

for(i=1; i<=L.len;i++)

{

printf("%d ",p->data);

p=p->next;

}

printf("\n");

printf("head value :%d \n",L.head->data);
printf("tail value :%d \n",L.tail->data);
}


int main()

{

int i;

Link p;

Link q;

LinkList La,Lb;

if(!InitList(La))return(OVERFLOW); //初始化La;

for(i=7;i>=1;i=i-1) //生成链表La;

{

MakeNode(p,i);

InsFirst(La,La.head,p); 

}

printf("\t线性链表综合操作修订版\n");
printf("\t修改了若干函数的错误，包括原来的指针错误提示\n");
printf("\temail:xiaojihai@126.com\n");

printf("===========================================\n");

printf("链表La为: "); //输出链表 La;

Display(La);

if(!InitList(Lb))return(OVERFLOW); //初始化La;

for(i=17;i>10;i=i-1) //生成链表Lb;

{

MakeNode(p,i);

InsFirst(Lb,Lb.head,p); 

}

printf("链表Lb为: "); //输出链表 Lb;
Display(Lb);

printf("两个线性链表相连接La+Lb:\n");
Append(La,Lb.head );

//输出链表La;
Display(La);


//删的首节点值
DelFirst(La,q);
printf("被删的首节点值：%d\n",q->data);
q=NULL;
free(q);


//删的尾节点值
Remove( La, p ); //删除La中的最后一个结点

printf("删除链表L中的最后一个结点:%d\n",p->data);

printf("此时的链表L为: "); //输出链表La

//输出链表La;
Display(La);

//定位第六个元素节点，并返回P
LocatePos(La,6,p);

printf("链表L中第6个结点的值为:%d\n",p->data);

//前驱
q=PriorPos(La,p);

printf("链表L中第6个结点的前驱的值为:%d\n",q->data);

//后继
q=NextPos(La,p);

printf("链表L中第6个结点的后继的值为:%d\n",q->data);

//在第6个结点前插入值2
MakeNode(q,2);
InsBefore(La,p,q);

//在第6个结点后插入值4
MakeNode(q,4);
InsAfter(La,p,q);

printf("在第6个结点前、后分别插入值为2、4的结点:");

//输出新链表La;
Display(La);

//输出链表尾
q=GetLast(La);

printf("链表L中最后结点的值为:%d\n",q->data);

//输出链表头
q=GetHead(La);

printf("链表L中头结点的值为:%d\n",q->data);

return OK;


}