1.单链表的存储结构
typedef struct Node//结点类型定义
{
ElemType data;
struct Node *next;
}Node,*LinkList;//LinkList为结构体指针类型
?2.初始化单链表
InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node));//建立头结点
(*L)->next=NULL;//建立空的单链表
}
/*L是指向单链表的头结点的指针，用来接收主程序中待初始化单链表的头指针变量的地址，*L相当于主程序中待初始化单链表的头指针变量*/?
3.建立单链表
（1）用头插法建立单链表
?
void CerateFromHead(LinkList L)
//L是带头结点的空链表头指针，通过键盘输入表中元素值，利用头插法建立单链表L
{
?? ?Node*s;
?? ?char c;
?? ?int flag=1;
?? ?while(flag)//flag初值为1，当输入$时置flag为0，建表结束
?? ?{
?? ??? ?c=getchar();
?? ??? ?if(c!='$')
?? ??? ?{
?? ??? ??? ?s=(Node*)malloc(sizeof(Node));//建立新节点
?? ??? ??? ?s->data=c;
?? ??? ??? ?s->next=L->next;//将s插入表头
?? ??? ??? ?L->next=s;
?? ??? ?}
?? ??? ?else
?? ??? ??? ?flag=0;
?? ?}
}
（2）尾插法建立单链表
?
void CreateFromTail(LinkList L)
//L是带头结点的空链表头指针，通过键盘输入表中元素值，利用尾插法建立单链表L
{
?? ?Node *r,*s;
?? ?int flag=1;//设置一个标志，flag初值为1，当输入$时置flag为0，建表结束
?? ?r=L;//r指针动态指向链表的当前表尾，以便于做尾插，其初值指向头结点
?? ?while(flag)//循环输入表中元素值，将建立的新结点s插入表尾
?? ?{
?? ??? ?c=getchar();
?? ??? ?if(c!='$')
?? ??? ?{
?? ??? ??? ?s=(Node *)malloc(sizeof(Node));
?? ??? ??? ?s->data=c;
?? ??? ??? ?r->next=s;
?? ??? ??? ?r=s;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?flag=0;
?? ??? ??? ?r->next=NULL;//将最后一个结点的next链域置为空，表示链表的结束
?? ??? ?}
?? ?}
?? ?
}3.查找
(1)按序号查找
Node* Get（LinkList L,int i)
//在带头结点的单链表中查找第i个结点，若找到（1<=i<=n),则返回该结点的存储位置，否则则返回NULL
{
?? ?int j;
?? ?Node *p;
?? ?if(i<=0)
?? ??? ?return NULL;
?? ?p=L;j=0;//从头结点开始扫描
?? ?while(p->next!=NULL&&j<i)
?? ?{
?? ??? ?p=p->next;
?? ??? ?j++;
?? ?}
?? ?if(i=j)
?? ??? ?return p;
?? ?else
?? ??? ?return NULL;
}
(2)按值查找
Node* Locate(LinkList L,ElemType e)
//在带头结点的单链表L中查找其结点值等于key的第一个结点，若找到则返回结点的位置，否则，则返回NULL
{
?? ?Node *p;
?? ?p=L->next;//从表中第一个结点开始
?? ?while(p!=NULL)//当前表未查完
?? ?{
?? ??? ?if(p->data!=key)
?? ??? ??? ?p=p->next;
?? ??? ?else
?? ??? ??? ?break;//找到结点=key时退出循环
?? ?}
?? ?return p;
}
4.求单链表长度
int Listlength(LinkList L)
//求带头结点的单链表L的长度
{
?? ?Node *p;
?? ?p=L->next;
?? ?j=0;//用来存放单链表的长度
?? ?while(p!=NULL)
?? ?{
?? ??? ?p=p->next;
?? ??? ?j++;
?? ?}
?? ?return j;//j为所求得的单链表长度
}
5.单链表插入操作
?
void InsertList(LinkList L,int i,ElemType e)
//在带头结点的单链表的第i个位置插入值为e的新结点
{
?? ?Node *pre,*s;
?? ?int k;
?? ?if(i<=0)
?? ??? ?return ERROR;
?? ?pre=L;k-0;//从头开始，查找第i-1个结点
?? ?while(pre->next!=NULL&&k<i-1)
?? ?{
?? ??? ?pre=pre->next;
?? ??? ?k++;
?? ?}//查找第i-1个结点
?? ?if(pre==NULL)//当前位置pre=NULL,表示已查找完，但仍未找到第i个位置，说明插入位置不合理
?? ?{
?? ??? ?printf("插入位置不合理");
?? ??? ?return ERROR;
?? ?}
?? ?s=(Node *)malloc(sizeof(Node));
?? ?s->data=e;
?? ?s->next=pre->next;
?? ?pre->next=s;
?? ?return OK;
}
6.单链表删除操作
?
int Delete(LinkList L,int i,ElemType *e)
//在带头结点的单链表中删除第i个元素，并将删除的元素保存到变量*e中
{
?? ?Node *pre,*r;
?? ?int k=0;
?? ?pre=L;
?? ?while(pre->next!=NULL&&k<i-1)
?? ?{
?? ??? ?pre=pre->next;
?? ??? ?k++;
?? ?}//查找第i-1个结点
?? ?if(pre->next=NULL)
?? ??? ?//while循环是因为p->next=NULL或i<1而退出的，因为pre->next=NULL,没有找到合法的前驱位置，说明输入的删除位置不合法
?? ?{
?? ??? ?printf("删除位置不合法");
?? ??? ?return ERROR;
?? ?}
?? ?r=pre->next;
?? ?pre->next=r->next;
?? ?*e=r->data;
?? ?free(r);//释放被删除结点所占的内存空间
?? ?return OK;
}7.例题：合并两个有序的单链表
LinkList MergeLinkList(LinkList LA,LinkList LB)
//将递增有序的两个单链表LA,LB合并成一个递增有序的单链表LC
{
?? ?Node *pa,*pb;
?? ?LinkList LC;
?? ?/*将LC初始置空表，pa,pb分别指向LA和LB中的第一个结点,r初值为LC且始终指向LC的表尾
?? ?*/
?? ?pa=LA->next;
?? ?pb=LB->next;
?? ?LC=LA;
?? ?LC->next=NULL;
?? ?r=LC;
?? ?/*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中*/
?? ?while(pa!=NULL&&pb!=NULL)
?? ?{
?? ??? ?if(pa->data<=pb->data)
?? ??? ?{
?? ??? ??? ?r->next=pa;
?? ??? ??? ?r=pa;
?? ??? ??? ?pa=pa->next;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?r->next=pb;
?? ??? ??? ?r=pb;
?? ??? ??? ?pb=pb->next;
?? ??? ?}
?? ??? ?if(pa)//若表LA未完，将表LA中后续元素链到新表LC表尾
?? ??? ??? ?r->next=pa;
?? ??? ?else
?? ??? ??? ?r->next=pb；//否则将表LB中后续元素链到新表LC表尾
?? ?}
?? ?free(LB);
?? ?return (LC);
}