複製鏈接
請複製以下鏈接發送給好友

動態鏈表

鎖定
這種鏈表在初始時不一定分配足夠的空間, 但是在後續插入的時候需要動態申請存儲空間,並且存儲空間不一定連續, 在進行插入和刪除時則不需要移動元素, 修改指針域即可,所以仍然具有鏈表的主要優點,鏈表結構可以是動態地分配存儲的,即在需要時才開闢結點的存儲空間,實現動態鏈接 [1] 
中文名
動態鏈表
所屬學科
計算機
特    點
在後續插入的時候需要動態申請存儲空間
動態單鏈表
單向鏈表數據結構可以分為兩部分:數據域和指針域,數據域存儲數據,指針域指向下一個儲存節點的地址。
/*線性表的單鏈表存儲結構*/
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

/*帶有頭結點的單鏈表的基本操作(12個)*/
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");
}
參考資料