数据结构与算法基础（青岛大学-王卓）(2)
第二弹火爆来袭中 这波是单链表的内容整理，废话不多说，上小龙虾呀(又到了龙虾季节了，哎，口水直流了~~)
的分割线
文章目录 ... TO BE ...
… 线性表的链式表示 定义
用一组物理位置任意的存储单元来存放线性表的数据元素，存储单元对连续性没要求，可零散分布，链表的每个节点由 数据+指针 组成
eg: 26个英文字母小写存储
链表种类
单链表，双链表，循环链表
链表的表示
头结点的数据域可以为空，也可以放线性表长度等附加信息，但此节点不能计入链表长度值。
链表的特点 单链表 表示方法
单链表由表头唯一确定，可以用头指针的名字来命名，头指针为L则把链表称为表L.
存储结构
typedef struct Lnode{ //声明结点的类型和指向结点的指针类型ElemType data; //结点的数据域struct Lnode *next; //结点的指针域(嵌套了)
}Lnode,*LinkList; //LinkList为指向结构体Lnode的指针类型LinkList L; //定义链表L
Lnode *p; //定义节点指针p (可以用linkList p 但是不推荐)
例子：存储学生的学号，姓名，成绩的单链表
// 通常定义法
typedef Struct {char num[8]; //数据域char name[8]; //数据域int score; //数据域
} ElemType;typedef struct Lnode{ElemType data; //数据域struct Lnode *next; //指针域
}Lnode, *LinkList
L;
单链表的初始化
Status InitList_L(LinkList &L){L=new LNode; // C++ or C语言 L=(LinkList) malloc (sizeof (LNode))L->next=NULL;return OK;
}
判断链表是否为空
int ListEmpty(LinkList L){ //空表返回1，否则返回0if(L->next) //非空return 0;elsereturn 1;
}
单链表的销毁(头结点也不存在了)
Status DestroyList_L(LinkList &L){Lnode *p;while(L){p=L;L=L->next;delete p; // C++ 用法 or C用法： free p;}return OK;
}
清空单链表(头指针和头结点还在)
依次从首元结点开始释放所有节点，最后将头结点的指针域设为空
Status EmptyList_L(LinkList &L){Lnode *p,*q;p=L->next;while (p){q=p->next;delete p;p=q;}L->next=NULL;return OK;
}
求单链表的表长
int List_Length(LinkList L){Lnode *p;p=L->next; //p指向第一个节点（首元结点）i=0;while (p){ //遍历单链表，统计节点数i++;p=p->next}return OK;
}
取单链表中第i个元素的内容
思路：从头指针触发，顺着链域next逐个往下搜索，直到搜索到第i个节点为止，因此链表不是随机存取结构，需判断找不到的情况和i的正确取值情况。
Status GetElem_L(LinkList L, int i, ElemType &e){p=L->next;j=1; //初始化，p指向首元结点，j来累计遍历过的位置while (!p && jnext;++j; //注意这里是前加加，返回的是自增后的j, j++ 后加加是返回自增前的j}if (!p || j > i) return ERROR; //p指向空节点或者i各元素不存在时，返回ERRORe=p->data;return OK;
}//GetElem_L
单链表中的按值查找 单链表的插入操作
在第i个节点前插入值为e的新节点 - 找前趋
//单链表的插入操作，在第i个位置插入元素数据域为e的元素
Status ListInset_L(LinkList &L, int i, ElemType e){p=L;j=0 //初始化p指向头结点，计数器为0while (p && jnext; ++j;} //寻找i-1节点if (!p || j>i-1) return ERROR; //当p为空时，p已经指向了表长+1的节点位置，此时插入位置变为表长+2，这种情况不允许，所以这里排除掉了插入位置大于表长+1位置和i小于1的不合理情况。s=new Lnode;s->data=e; // 创建即将插入的新节点ss->next=p->next; // s指向原来的i节点p->next=s; //i-1节点指向新节点sreturn OK;
}//ListInset_L
单链表的删除操作
删除第i各元素 - 找前趋
Status List_Delete_L(LinkList &L, int i, ElemType &e){p=L;j=0; Lnode *q; //初始化，p指向头结点，计数器清零while(p->next && jnext; ++j;} //寻找i-1元素，注意此处判定改为了p->next, 当p->next为NULL时，说明i-1个元素已经是表的最后一个元素,那么要删除的i元素就是表长+1的元素，而它是不存在的if(!p->next || j>i-1) return ERROR; // 排除不合理的i元素q=p->next; e=q->data; //将待删除元素信息做保留p->next=q->next; // i-1元素指向i+1元素delete q; //删除指针return OK;
}//ListDelete_L
单链表的查找、插入、删除时间效率 单链表的建立
//头插法创建单链表Void CreateList_H(LinkList &L, int n){L=new Lnode; L->next=NULL; //建立一个带头结点的单链表for (i=n;i>0;--i){ //循环倒序插入所有元素p=new Lnode; //生成(C)新节点p=(Lnode*)malloc(sizeof(Lnode));cin>>p->data; //输入(C)元素值scanf(&p->data)p->next=L->next;L->next=p;}}//CreateList_H
尾插法 - 新元素正序依次插入末尾
//尾插法创建单链表Void CreateList_R(LinkList &L, int n){L=new Lnode; L->next=NULL; //创建空单链表r=L; // 尾指针初始化等于头结点for (i=0;i>p->data;p->next=NULL; //新节点的指针域置空作为新的尾结点 r->next=p; //新节点链接前一个节点r=p; //尾指针移动到新尾结点}}//CreateList_R
… TO BE …
