一个指针的链表，则称单链表。单链表的存储结构描述如下：
typedef struct Lnode {
Elemtype data;/*数据域*/ struct Lnode *next;/*指针域*/
}LNODE,*Linklist; /*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/
【核心算法提示】
1． 链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入” 的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。
2． 链表查找操作的基本步骤：因链表是一种\顺序存取\的结构，则要在带头结点的链表中查找到第 i个 元素，必须从头结点开始沿着后继指针依次\点数\，直到点到第 i 个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。
3． 链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。
4． 链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。 【核心算法描述】
void creat1(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用头
插法建立一个带头结点的单链表的函数*/
{ L=(Linklist)malloc(sizeof(LNODE));/*生成头结点*/ L->next=NULL;/*头结点的指针域初始为空*/ scanf(\
while(node!=0)
{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点的分配空间*/ p->data=node; /*为新结点数据域赋值*/ p->next=L->next;/*新结点指针域指向开始结点*/
L->next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/
scanf(\} }
void creat2(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用尾插
法建立一个带头结点的单链表的函数*/
{ L=(Linklist)malloc(sizeof(LNODE));/*为头结点分配空间*/ L->next=NULL; /*头结点的指针域初始为空*/ r=L; /*尾指针初始指向头结点*/
scanf(\while(node!=0)
{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点分配空间*/ p->data=node; /*新结点数据域赋值*/ p->next=NULL; /*新结点指针域为空*/ r->next=p;/*尾结点指针域指向新结点*/
11
r=p; /*尾指针指向新结点，即新结点成为尾结点*/
scanf(\ } }
status list_search(Linklist L, int i;Elemtype &e)
/*在带头结点的单链表L中查找第i个元素，如果查找成功则用e返回其值*/
{ p=L->next; /*使指针p指向第1个元素结点*/
j=1; /*计数器赋初值为1*/
while (p&& j
if (!p&& j>i)
return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK;
}
status list_insert(Linklist &L,int i;Elemtype x)
/*在带头结点的单链表L中第i个位置之前插入新元素x*/
{ p=L; j=0;
while(p!=NULL&&j 个位置*/ { p=p->next; ++j; } if(p==NULL||j>i-1) return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(Linklist)malloc(sizeof(LNODE)); /*分配一个新结点的空间*/ s->data=x; /*为新结点数据域赋值*/ /*下面两条语句就是完成修改链，将新结点s插入到p结点之后*/ s->next=p->next; /*新结点指针域指向p的后继结点*/ p->next=s; /*新结点成为p的后继结点*/ return OK; } status list_delete(Linklist &L,int i,Elemtype &x) /*在带头结点的单链表L中，删除第i个元素结点,并用x返回其值*/ { p=L;j=0; while(p->next!=NULL&&j ++j; } if (p->next==NULL||j>i-1) return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p->next; /* q指向p的后继结点*/ 12 p->next=q->next; /*q的后继结点成为p的后继结点*/ x=q->data; /*用x返回第i个位置的元素*/ free(q); /*释放q所指的被删结点的空间*/ return OK; } 3．源程序代码参考 #include struct Lnode *next; } LNODE,*Linklist; Linklist creat(Linklist L) /*单链表建立函数 */ {int node; Linklist p; L=(Linklist)malloc(sizeof(LNODE)); L->next=NULL; printf(\ \ /*请求输入线性表中各个元素，以0结束*/ scanf(\ while(node!=0) {p=(Linklist)malloc(sizeof(LNODE)); if (!p) exit(); p->data=node; p->next=L->next; L->next=p; scanf(\ } return L; } Linklist insert(Linklist L,int i,int x) /*单链表插入函数*/ { int j;Linklist p,s; p=L; j=0; while (p!=NULL&&j if (p==NULL||j>i-1) printf(\ else 13 { s=(Linklist)malloc(sizeof(LNODE)); s->data=x; s->next=p->next; p->next=s; } return L; } Linklist delete(Linklist L,int i) /*单链表删除函数*/ { int j,x; Linklist p,q; p=L; j=0; while(p->next!=NULL&&j if(p->next==NULL||j>i-1) printf(\ else { q=p->next; p->next=q->next; x=q->data; printf(\ free(q); } return L; } int search(Linklist L, int i) /*单链上的查找函数*/ { Linklist p; int j; p=L->next; j=1; while (p&& j if (!p&& j>i) return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else return(p->data); /*否则函数返回第i个元素的值*/ } 14 void display(Linklist L) /*单链表元素输出函数*/ { Linklist p; p=L->next; while(p!=NULL) { printf(\ p=p->next; } printf(\} main()/*主函数*/ {Linklist L=NULL; int i,x; L=creat(L);/*调用单链表建立函数*/ printf(\ display(L); /*调用单链表元素输出(遍历)函数*/ printf(\ you want to insert:\请求输入插入操作位置*/ scanf(\ printf(\请求输入需要插入的元素*/ scanf(\ L=insert(L,i,x);/*调用单链表插入函数*/ printf(\ display(L);/*调用单链表元素输出(遍历)函数*/ printf(\请求输入删除操作位置*/ scanf(\ L=delete(L,i); /*调用单链表删除函数*/ printf(\ display(L); /*调用单链表元素输出(遍历)函数*/ printf(\请求输入待查找元素的位置*/ scanf(\ x=search(L,i); /*调用单链表查找函数*/ if (x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf(\ the %dth elem is %d\\n\ else printf(\ the %dth elem is not exsit\\n\} 15