线性表的链式存储结构之单链表

链式存储结构之单链表"/>

线性表的链式存储结构之单链表

线性表的链式存储结构称为链表。即每个存储结点不仅包含元素本身的信息（数据域），还包含表示元素之间的逻辑关系的信息，这部分在C语言中采用指针来实现，称为指针域

单链表，即每个结点中除包含有数据域以外只设置一个指针域，用于指向其后继结点。通常每个链表带有一个头结点，并通过头结点的指针唯一标识该链表，称为头指针，相应的指向首结点的指针称为首指针，指向尾结点的指针称为尾指针。如下图所示，head指向头结点，每个结点由两部分组成——数据域和指针域。

整体创建链表有两种方法：头插法和尾插法，现简单介绍以下头插法：

void CreateListR(LinkNode *&L,ElemType a[],int n)  //用头插法创建单链表 {LinkNode *s;L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点，其next域设置为NULLL->next=NULL;for(int i=0;i<n;i++){                       //循环建立数据结点 s=(LinkNode *)malloc(sizeof(LinkNode)); //创建数据结点ss->data=a[i];     s->next=L->next;       //将s结点插入到原结点之前，头结点之后 } }

由于每个新数据结点都插在头结点之后，所以在采用头插法建表时单链表中数据结点的顺序与数组a中元素的顺序相反！

 C语言代码实现如下（使用尾插法）：

注：尾插法建表是很多复杂算法的基础，需牢固掌握！

#include <stdio.h>
#include <stdlib.h>
#define Maxsize 50
typedef char ElemType;
typedef struct LNode
{ElemType data;         //存放数据元素的值 struct LNode *next;   //定义一个结构指针，指向后继结点（即存放下一个结点的地址） 
}LinkNode;                //单链表结点的类型void CreateListR(LinkNode *&L,ElemType a[],int n)  //用尾插法创建单链表 {LinkNode *s,*r;L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点r=L;                 //r始终指向尾结点，初始时指向头结点 for(int i=0;i<n;i++){                       //循环建立数据结点 s=(LinkNode *)malloc(sizeof(LinkNode)); //创建数据结点ss->data=a[i];     r->next=s;       //将s结点插入到r结点之后 r=s;             //让r指向当前尾结点 } r->next=NULL;       //尾结点的next域设置为 NULL }void InitList(LinkNode *&L)            //初始化单链表 {L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点,其next域设置为NULL L->next=NULL; }void DestroyList(LinkNode *&L)        //销毁单链表 {LinkNode *pre=L,*p=L->next;  //pre指向结点p的前驱结点 while(p!=NULL){free(pre);             //释放结点 pre pre=p;                //pre，p同步向后移动一个结点p=pre->next; }free(pre);             //循环结束时pre指向尾结点，释放pre }bool ListEmpty(LinkNode *L)      //判断是否为空表 {return(L->next==NULL);}int ListLength(LinkNode *L)      //求单链表长度 
{int n=0;LinkNode *p=L;                //p指向头结点 while(p->next!=NULL){n++;p=p->next;}return n;             //循环结束，返回结点个数n 
}void PrintList(LinkNode *L)  //输出单链表 {LinkNode *p=L->next;      //p指向首结点 while(p!=NULL)            //p不为NULL，输出p结点的data域 {printf("%c ",p->data);p=p->next;           //p移向下一个结点 }}ElemType Get(LinkNode *L,int i)  //找单链表中第i个数据元素的值 {int j=0;LinkNode *p=L;if(i<=0){                    //i错误返回假 return false;}while(j<i && p!=NULL){       //找第i个结点p j++;p=p->next;}if(p==NULL){return false;           //不存在返回false }else{return(p->data);        //找到了返回第i个结点的数据元素值 }}
int Locate(LinkNode *L,ElemType e)
{int i=1;LinkNode *p=L->next;while(p!=NULL && p->data!=e)       //查找data值为e的结点，其序号为i {p=p->next;i++;}if(p==NULL){return(0);              //不存在返回0 }else{return(i);              //找到了返回其逻辑序号i }
}
bool ListInsert(LinkNode *&L,int i,ElemType e)
{int j=0;LinkNode *p=L,*s;  //p指向头结点 if(i<=0){return false;}while(j<i-1 &&p!=NULL){  //查找第i-1个结点p j++;p=p->next;}if(p==NULL){return false;}else{s=(LinkNode *)malloc(sizeof(LinkNode));  //创建新结点s，data域为e s->data=e;                               //将s结点插入到p结点之后 s->next=p->next;p->next=s;return true;}} bool ListDelete(LinkNode *&L,int i,ElemType &e){int j=0;LinkNode *p=L,*q;if(i<=0){return false;}while(j<i-1 && p!=NULL){   //查找第i-1个结点 j++;p=p->next;}if(p==NULL){               //未找到返回false return false;}else{                          q=p->next;              //找到让q指向第i个结点p if(q==NULL){            //若不存在第i个结点，返回false return false;}e=q->data;               p->next=q->next;       //删除结点q    free(q);               //释放q结点的空间 return true;           //成功删除第i个结点 }} char a[Maxsize];LinkNode *h;int n;int main()
{char e;               //存放数据元素 printf("请输入需要输入的数:");scanf("%d",&n);getchar();for(int i=0;i<n;i++){scanf("%c",&a[i]);getchar();}InitList(h);CreateListR(h,a,n);printf("输出单链表h:\n");PrintList(h);printf("\n输出该单链表长度:\n");printf("%d",ListLength(h));ListEmpty(h)?(printf("\n该单链表为空\n")):(printf("\n该单链表不为空\n")); printf("\n输出单链表第3个元素：\n");printf("%c",Get(h,3));printf("\n输出元素a的位置：\n");printf("%d",Locate(h,'a'));printf("\n在第4个位置上插入f：\n");ListInsert(h,4,'f');PrintList(h);printf("\n删除第3个元素\n");ListDelete(h,3,e);PrintList(h);DestroyList(h); ListEmpty(h)?(printf("\n销毁失败！\n")):(printf("\n已成功销毁该单链表！\n"));return 0;
}