#include <stdlib.h>
//定義單鏈表結構類型
typedef struct linknode
{
int data;
struct linknode *next;
}LNode,*LinkList;
//單鏈表初始化(帶頭節點)
LinkList Inithead_LL(void)
{
LinkList head;
head=(LinkList)malloc(sizeof(LNode));
if(head==NULL)
{
printf("申請內存出錯\n");
return NULL;
}
head->next=NULL;//表頭指向空
return head;
}
//求單鏈表長度
int Length_LL(LinkList phead)
{
int count=0;//初始化計數器
while (phead !=NULL)
{
phead=phead->next;
count ++;
}
return (count);//返回表長
}
//打印單鏈表
void Printf_LL(LinkList phead)
{
while(phead !=NULL)
{
printf("%d",phead->data);
phead=phead->next;
if(phead!=NULL)
printf(",");
}
printf("\n");
}
//釋放資源
void Free_LL(LinkList *phead)
{
LinkList p;
p=*phead;
while(p !=NULL)
{
*phead=(*phead)->next;//表頭後移壹個
free(p);//釋放
p=*phead;//指向表頭,釋放下壹個
}
}
//插入新節點:按升序插入
//x為插入值
int InsertOrder_LL(LinkList *phead,int x)
{
LinkList s; //s是新節點指針
LinkList p,pre; //p是準備插入節點指針,pre是p的前趨指針
//生成壹個新節點
s=(LinkList)malloc(sizeof(LNode));
if(s==NULL)
{
printf("申請內存出錯\n");
return 0;
}
s->data=x;
s->next=NULL;//新節點後繼指向空
p=pre=*phead;
//如果表頭為空,直接將s設置表頭.
if(p==NULL)
{
s->next=NULL;
*phead = s;
return 1;
}
//在單鏈表插入位置,由p指向
while (p !=NULL && p->data < x)//尋找不小於x的節點位置
{
pre=p;
p=p->next;
}
if(pre==p)//如果是在第壹個節點前插入,修改頭指針
{
s->next=p; //新節點後續指向p
*phead=s; //第壹節點為s
}
else
{
s->next=p; //新節點後續指向p
pre->next = s; //pre後續指向新節點
}
return 1;
}
//刪除節點 刪除值為x的節點
int Delete_LL(LinkList *phead,int x)
{
LinkList p,q;//p為值是x的節點,q是p的前壹個節點
if(*phead == NULL)//如果鏈表為空，做下溢處理
{
printf("單鏈表為空!\n");
return 0;
}
if((*phead)->data == x) //如果表頭值為x，刪除表頭
{
p=*phead;
*phead=(*phead)->next;
free(p);//釋放表頭
}
else //從第二個節點查找值是x的
{
q=*phead;
p=(*phead)->next;
//註意先p !=NULL，否則因沒有於x等值的節點將出現非法訪問操作
while(p !=NULL && p->data!=x )
{
q=p;
p=p->next;
}
if(p!=NULL)//找到了
{
q->next=p->next;//讓前壹個節點指向p的後繼節點
free(p);//刪除節點p
}
else
{
printf("未找到值為%d的節點.\n",x);
return 0;
}
}
return 1;
}
int Creat_LL(LinkList *phead)
{
int i;//循環變量
int n=5;//元素個數
for (i=1;i<=n;i++)
//if(Insert_LL(&head,i,i)!=1)
if(InsertOrder_LL(phead,i)!=1)
return 0;
return 1;
}
//查找數據,成功返回地址,失敗返回NULL
LinkList Find_LL(LinkList phead,int x)
{
if(phead==NULL)
return NULL;
while(phead!=NULL&&phead->data!=x)
phead=phead->next;
return phead;
}
//反序鏈表
int Reverse_LL(LinkList *phead)
{
LinkList p,q,t;//q是p的後續
if((p=*phead)==NULL)
{
printf("單鏈表為空!\n");
return 0;
}
q=p->next;//q為第二節點
while(q != NULL)
{
t=q->next;//中間變量
q->next=p;//進行反序,p和q各向後移動
p=q;
q=t;
}
(*phead)->next = NULL;//表尾設置為空
*phead=p;//重新設置表頭
return 1;
}
int main(void)
{
LinkList head;//定義單鏈表表頭(初始化NULL)
LinkList fp;
int n1=9;
//單鏈表初始化
head=Inithead_LL();
//形成單鏈表
printf("形成單鏈表\n");
if(Creat_LL(&(head->next))!=1)
return 1;
//打印鏈表
Printf_LL(head->next);
printf("在第1個節點和第11個節點插入值\n");
InsertOrder_LL(&(head->next),9);
InsertOrder_LL(&(head->next),11);
//打印鏈表
Printf_LL(head->next);
//求單鏈表長度
printf("單鏈表長度:%d\n",Length_LL(head->next));
//刪除節點
printf("刪除節點\n");
if(Delete_LL(&(head->next),n1)!=1)
return 1;
//打印鏈表
Printf_LL(head->next);
//反序單鏈表
printf("反序單鏈表\n");
if(Reverse_LL(&(head->next))!=1)
return 1;
//打印鏈表
Printf_LL(head->next);
//查找數據
printf("查找數據\n");
fp=NULL;
if((fp=Find_LL(head,3))!=NULL)
printf("查找成功\n");
else
printf("查找失敗\n");
return 0;
}