线性链表的实现
1、头文件及函数引用：
//------------------------------------------------------------------------
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}list,*plist;
//创建空链表
plist creatHead(); //ok
//初始化链表
plist creatList(plist head); // ok
//遍历
void traverseList(plist head); // ok
//判断是否为空
bool isEmpty(plist head); // ok
//获取链表的长度
int getLength(plist head); //ok
//对链表进行排序
void sortList(plist head); //ok
//在链表中插入元素
bool insertList(plist head,int position,int value); //ok
//删除链表中的元素
bool deleteList(plist head,int position,int *value); // 0k
//分配内存的方法,相当于new
plist oS(); //ok
//未分配到内存报错方法
void er(); //ok
//------------------------------------------------------------------------
2、主函数：
//入口函数
void main()
{
plist head=creatHead();
if(isEmpty(head))
printf("该链表为空");
else
printf("该链表不为空\n");
head=creatList(head);
printf("创建后的链表为\n");
traverseList(head);
printf("排序后的链表为：\n\n");
sortList(head);
if(isEmpty(head))
printf("该链表为空");
else
printf("该链表不为空\n");
printf("该链表的长度为:%d\n\n",getLength(head));
insertList(head,2,124);
printf("插入元素后的链表为：\n\n");
traverseList(head);
int value;
deleteList(head,2,&value);
printf("删除元素后的链表为：\n\n");
printf("删除的元素为%d\n",value);
traverseList(head);
}
//入口函数结束
3、函数体：
plist creatHead()
{
plist head=oS();
if(head==NULL)
er();
head->next=NULL;
return head;
}
plist oS()//obtainSpace
{
plist p=(plist)malloc(sizeof(list));
if(p == NULL)
er();
return p;
}
bool isEmpty(plist head)
{
if(head->next == NULL)
return true;
else
return false;
}
plist creatList(plist head)
{
plist tail=oS();
tail=head;
tail->next=NULL;
int i;
int value;
int len;
printf("请输入初始长度:");
scanf("%d",&len);
for(i=0;i<len;i++)
{
plist pnew=oS();
if(pnew== NULL)
er();
printf("请输入第%d个元素：",i+1);
scanf("%d",&value);
pnew->data=value;
tail->next=pnew;
pnew->next=NULL;
tail=pnew;
}
return head;
}
void er()
{
printf("分配内存失败，即将退出。");
exit(-1);
}
void traverseList(plist head)
{
int i=1;
if(isEmpty(head))
{
printf("该链表为空,无法遍历");
exit(-1);
}
plist p=head;
while(p->next != NULL)
{
printf("第%d元素为%d:\n",i++,p->next->data);
p=p->next;
}
}
int getLength(plist head)
{
int len=0;
plist p=head->next;
while(p!=NULL)
{
len++;
p=p->next;
}
return len;
}
void sortList(plist head)
{
int len=getLength(head);
int i,j,t;
plist p,q;
for(i=0,p=head->next;i<len-1;i++,p=p->next)
{
for(j=i+1,q=p->next;j<len;j++,q=q->next)
{
if(p->data >q->data)
{
t=q->data;
q->data=p->data;
p->data=t;
}
}
}
}
bool insertList(plist head,int position,int value)
{
int i=0;
plist p=head;
while(p != NULL && i<position-1)
{
p=p->next;
i++;
}
if(p == NULL || i>position-1)
{
return false;
}
plist pnew=oS();
if(pnew==NULL)
{
er();
}
plist t=p->next;
pnew->data=value;
p->next=pnew;
pnew->next=t;
return true;
}
bool deleteList(plist head,int position, int *value)
{
int i=0;
plist p=head;
while(p!= NULL && i<position-1)
{
p=p->next;
i++;
}
if(p==NULL || i>position-1)
{
return false;
}
plist t=p->next;
*value=p->next->data;
p->next=p->next->next;
free(t);
return true;
}