|
单向链表
单向链表（又名单链表、线性链表， 英語：singly linked list）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下讀取。 数据结构一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
動態單鏈表（C语言）單向鏈表的數據结構可以分為兩部分：數據域和指针域，數据域存儲數據，指针域指向下一個儲存節點的地址。 存储结构/* c2-2.h 线性表的单链表存储结构 */
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
基本操作/* bo2-2.c 带有头结点的单链表(存储结构由c2-2.h定义)的基本操作(12个),包括算法2.8,2.9,2.10 */
void InitList(LinkList *L)
{ /* 操作结果：构造一个空的线性表L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点，并使L指向此头结点 */
if(!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next=NULL; /* 指针域为空 */
}
void DestroyList(LinkList *L)
{ /* 初始条件：线性表L已存在。操作结果：销毁线性表L */
LinkList q;
while(*L)
{
q=(*L)->next;
free(*L);
*L=q;
}
}
void ClearList(LinkList L) /* 不改变L */
{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
LinkList p,q;
p=L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; /* 头结点指针域为空 */
}
Status ListEmpty(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if(L->next) /* 非空 */
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
int i=0;
LinkList p=L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
{ /* L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */
int j=1; /* j为计数器 */
LinkList p=L->next; /* p指向第一个结点 */
while(p&&j<i) /* 顺指针向后查找，直到p指向第i个元素或p为空 */
{
p=p->next;
j++;
}
if(!p||j>i) /* 第i个元素不存在 */
return ERROR;
*e=p->data; /* 取第i个元素 */
return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(compare(p->data,e)) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件: 线性表L已存在 */
/* 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
/* 返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE */
LinkList q,p=L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
q=p->next; /* q为p的后继 */
if(q->data==cur_e)
{
*pre_e=p->data;
return OK;
}
p=q; /* p向后移 */
}
return INFEASIBLE;
}
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
/* 返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */
LinkList p=L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
if(p->data==cur_e)
{
*next_e=p->next->data;
return OK;
}
p=p->next;
}
return INFEASIBLE;
}
Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */
{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
int j=0;
LinkList p=L,s;
while(p&&j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j++;
}
if(!p||j>i-1) /* i小于1或者大于表长 */
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改变L */
{ /* 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1) /* 寻找第i个结点，并令p指向其前岖 */
{
p=p->next;
j++;
}
if(!p->next||j>i-1) /* 删除位置不合理 */
return ERROR;
q=p->next; /* 删除并释放结点 */
p->next=q->next;
*e=q->data;
free(q);
return OK;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同 */
{ /* 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() */
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
静态单链表（C语言）// 线性表的静态单链表存储结构
#define MAX_SIZE 100 // 链表的最大长度
typedef struct {
ElemType data; //此處的ElemType可以自由代換（如int/float等）
int cur;
} component, SLinkList[MAX_SIZE];
// 一个数组只生成一个静态链表的基本操作(11个)
#define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的
void InitList(SLinkList L) {
// 构造一个空的链表L，表头为L的最后一个单元L[MAX_SIZE-1]，其余单元链成
// 一个备用链表，表头为L的第一个单元L[0]，“0”表示空指针
int i;
L[MAX_SIZE - 1].cur = 0; // L的最后一个单元为空链表的表头
for (i = 0; i < MAX_SIZE - 2; i++) // 将其余单元链接成以L[0]为表头的备用链表
L[i].cur = i + 1;
L[MAX_SIZE - 2].cur = 0;
}
void ClearList(SLinkList L) {
// 初始条件：线性表L已存在。操作结果：将L重置为空表
int i, j, k;
i = L[MAX_SIZE - 1].cur; // 链表第一个结点的位置
L[MAX_SIZE - 1].cur = 0; // 链表空
k = L[0].cur; // 备用链表第一个结点的位置
L[0].cur = i; // 把链表的结点连到备用链表的表头
while (i) { // 没到链表尾
j = i;
i = L[i].cur; // 指向下一个元素
}
L[j].cur = k; // 备用链表的第一个结点接到链表的尾部
}
Status ListEmpty(SLinkList L) {
// 若L是空表，返回TRUE；否则返回FALSE
if (L[MAX_SIZE - 1].cur == 0) // 若为空表
return TRUE;
else
return FALSE;
}
int ListLength(SLinkList L) {
// 返回L中数据元素个数
int j = 0, i = L[MAX_SIZE - 1].cur; // i指向第一个元素
while (i) { // 没到静态链表尾
i = L[i].cur; // 指向下一个元素
j++;
}
return j;
}
Status GetElem(SLinkList L, int i, ElemType *e) {
// 用e返回L中第i个元素的值
int l, k = MAX_SIZE - 1; // k指向表头序号
if (i < 1 || i > ListLength(L))
return ERROR;
for (l = 1; l <= i; l++) // 移动到第i个元素处
k = L[k].cur;
*e = L[k].data;
return OK;
}
int LocateElem(SLinkList L, ElemType e) { // 算法2.13(有改动)
// 在静态单链线性表L中查找第1个值为e的元素。若找到，则返回它在L中的
// 位序，否则返回0。(与其它LocateElem()的定义不同)
int i = L[MAX_SIZE - 1].cur; // i指示表中第一个结点
while (i && L[i].data != e) // 在表中顺链查找(e不能是字符串)
i = L[i].cur;
return i;
}
Status PriorElem(SLinkList L, ElemType cur_e, ElemType *pre_e) {
// 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
// 否则操作失败，pre_e无定义
int j, i = L[MAX_SIZE - 1].cur; // i指示链表第一个结点的位置
do { // 向后移动结点
j = i;
i = L[i].cur;
} while (i && cur_e != L[i].data);
if (i) { // 找到该元素
*pre_e = L[j].data;
return OK;
}
return ERROR;
}
Status NextElem(SLinkList L, ElemType cur_e, ElemType *next_e) {
// 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继
// 否则操作失败，next_e无定义
int j, i = LocateElem(L, cur_e); // 在L中查找第一个值为cur_e的元素的位置
if (i) { // L中存在元素cur_e
j = L[i].cur; // cur_e的后继的位置
if (j) { // cur_e有后继
*next_e = L[j].data;
return OK; // cur_e元素有后继
}
}
return ERROR; // L不存在cur_e元素，cur_e元素无后继
}
Status ListInsert(SLinkList L, int i, ElemType e) {
// 在L中第i个元素之前插入新的数据元素e
int l, j, k = MAX_SIZE - 1; // k指向表头
if (i < 1 || i > ListLength(L) + 1)
return ERROR;
j = Malloc(L); // 申请新单元
if (j) { // 申请成功
L[j].data = e; // 赋值给新单元
for (l = 1; l < i; l++) // 移动i-1个元素
k = L[k].cur;
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
return ERROR;
}
Status ListDelete(SLinkList L, int i, ElemType *e) {
// 删除在L中第i个数据元素e，并返回其值
int j, k = MAX_SIZE - 1; // k指向表头
if (i < 1 || i > ListLength(L))
return ERROR;
for (j = 1; j < i; j++) // 移动i-1个元素
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
*e = L[j].data;
Free(L, j);
return OK;
}
void ListTraverse(SLinkList L, void(*vi)(ElemType)) {
// 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi()
int i = L[MAX_SIZE - 1].cur; // 指向第一个元素
while (i) { // 没到静态链表尾
vi(L[i].data); // 调用vi()
i = L[i].cur; // 指向下一个元素
}
printf("\n");
}
|
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
