動態鏈表

動態鏈表

這種鏈表在初始時必須分配足夠的空間, 也就是空間大小是靜態的, 在進行插入和刪除時則不需要移動元素, 修改指針域即可，所以仍然具有鏈表的主要優點，鏈表結構可以是動態地分配存儲的，即在需要時才開闢結點的存儲空間，實現動態鏈接。

目錄
1正文

正文

動態單鏈表
單向鏈表的數據結構可以分為兩部分：數據域和指針域，數據域存儲數據，指針域指向下一個儲存節點的地址。
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
void InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(struct LNode));
if(!*L)
exit(OVERFLOW);
(*L)->next=NULL;
}
void DestroyList(LinkList *L)
{
LinkList q;
while(L)
{
q=(*L)->next;
free(L);
*L=q;
}
}
void ClearList(LinkList L)
{
LinkList p,q;
p=L->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
L->next=NULL;
}
Status ListEmpty(LinkList L)
{
if(L->next)
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next;
while(p)
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType *e)
{
int j=1;
LinkList p=L->next;
while(p&&j < i)
{
p=p->next;
j++;
}
if(!p||j>i)
return ERROR;
*e=p->data;
return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
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)
{
LinkList q,p=L->next;
while(p->next)
{
q=p->next;
if(q->data==cur_e)
{
*pre_e=p->data;
return OK;
}
p=q;
}
return INFEASIBLE;
}
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{
LinkList p=L->next;
while(p->next)
{
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)
{
int j=0;
LinkList p=L,s;
while(p&&j < i-1)
{
p=p->next;
j++;
}
if(!p||j>i-1)
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e)
{
int j=0;
LinkList p=L,q;
while(p->next&&j< i-1)
{
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))
{
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}

基本信息

特點
在後續插入的時候需要動態申請存儲空間