单链表的链式储存特点：
链表是一种顺序存取结构，按位置访问链表中第i个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时间复杂度为O(n), 即取值操作的效率低。但在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针， 时间复杂度为0(1)。
若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时， 宜采用顺序表作为存储结构。 对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。
代码如下：
其中单链表的基本操作包括：
1.头插法，尾插法
2.删除
3.查找
4.排序
#include<cmath> #include<iostream> using namespace std; #define Status int #define ElemType int //单链表结点数据结构 typedef struct LNode { ElemType data;//数据域 struct LNode *next;//指针域 }LNode,*LinkList; //**************************基本操作函数***************************// //初始化函数 Status InitList(LinkList &L) { L = new LNode;//生成头结点 这样删除等操作就不必分第一个结点和其他了 L->next = NULL; return 1; } //获取单链表长度 头结点无数据，不算 int ListLength(LinkList L) { LinkList p=L;int sum=0; while(p) { sum++; p=p->next; } return sum-1;//去除头结点 } //哪种插入法？？？？ bool ListInsert(LinkList &L,int i,ElemType e) { LNode* s;LinkList p=L;int j=0; while(p&&(j<i-1))//j 指到 i-1 位置或者 p 已经到最后时跳出 { p=p->next; ++j; } if(!p||j>i-1)//i<1 或者 i>ListLength(L)+1 时,插入位置无效 不调用 ListLength,提高效率 { printf("插入位置无效！！！\n"); return false; } s=new LNode; s->data=e; s->next=p->next; p->next=s; return true; } bool ListInsert2(LinkList &L,int i,ElemType e) { LNode* s;LinkList p=L;int j=0; while(p&&(j<i-1))//j 指到 i-1 位置或者 p 已经到最后时跳出 { p=p->next; ++j; } if(!p||j>i-1)//i<1 或者 i>ListLength(L)+1 时,插入位置无效 不调用 ListLength,提高效率 { printf("插入位置无效！！！\n"); return false; } s=new LNode; s->data=e; s->next=L->next; L->next=s; return true; } //删除函数 删除位置 i 的结点 即删除 i-1 之后的结点 bool ListDelete(LinkList &L,int i) { LNode* s;LinkList p=L;int j=0; LinkList q; while(p&&(j<i-1))//j 指到 i-1 位置 { p=p->next; ++j; } if(!(p->next)||j>i-1)//i<1 或者 i>ListLength(L)时,删除位置无效 { printf("删除位置无效！！！\n"); return false; } q=p->next; p->next=q->next; free(q);//释放空间 return true; } //查找函数 按值查找 查找第一个等于 e 的结点 成功返回该结点指针，否则返回 NULL LNode *LocateElem(LinkList L,ElemType e) { LNode *p=L; while(p&&(p->data!=e)) { p=p->next; } return p; } //**************************功能实现函数**************************// //遍历输出函数 void PrintList(LinkList L) { LinkList p=L->next;//跳过头结点 if(ListLength(L)) { printf("当前单链表所有元素:"); while(p) { printf("%d ",p->data); p=p->next; } printf("\n"); } else { printf("当前单链表已空！\n"); } } //插入功能函数 调用 ListInsert 插入 void Insert(LinkList &L) { int place;ElemType e;bool flag; printf("请输入要插入的位置(从 1 开始)及元素:\n"); scanf("%d%d",&place,&e); flag=ListInsert(L,place,e); if(flag) { printf("插入成功！！！\n"); PrintList(L); } } void Insert2(LinkList &L) { int place;ElemType e;bool flag; printf("请输入要插入的位置(从 1 开始)及元素:\n"); scanf("%d%d",&place,&e); flag=ListInsert2(L,place,e); if(flag) { printf("插入成功！！！\n"); PrintList(L); } } //删除功能函数 调用 ListDelete 删除 void Delete(LinkList L) { int place;bool flag; printf("请输入要删除的位置(从 1 开始):\n"); scanf("%d",&place); flag=ListDelete(L,place); if(flag) { printf("删除成功！！！\n"); PrintList(L); } } //查找功能函数 调用 LocateElem 查找 void Search(LinkList L) { ElemType e;LNode *q; printf("请输入要查找的值:\n"); scanf("%d",&e); q=LocateElem(L,e); if(q) { printf("找到该元素！\n"); } else printf("未找到该元素！\n"); } //菜单 void menu() { printf("********1.插入(1) 2.删除*********\n"); printf("********3.查找 4.输出*********\n"); printf("********6.插入(2) 7.排序*********\n"); printf("********5.退出 *********\n"); } void swap(LNode *m,LNode *n) { int t; t=m->data; m->data=n->data; n->data=t; } void qsort(LinkList L) { LinkList p=L->next; LinkList q=p->next; while(q!=NULL) { L->data=q->data; while(p!=q) { if(p->data<=L->data)p=p->next; else{ swap(p,q); p=p->next; } } q=q->next; p=L->next; } PrintList(L); } //主函数 int main() { LinkList L;int choice; InitList(L); while(1) { menu(); printf("请输入菜单序号：\n"); scanf("%d",&choice); if(choice==5) break; switch(choice) { case 1:Insert(L);break; case 2:Delete(L);break; case 3:Search(L);break; case 4:PrintList(L);break; case 6:Insert2(L);break; case 7:qsort(L);break; default:printf("输入错误！！！\n"); } } return 0; }
?代码运行结果如下：
?