數據結構與算法：2線性表的鏈式存儲

上一節講述了線性表的順序存儲，對於線性表的順序存儲出現的問題，需要分配一整段連續的存儲空間失敗的可能性較之於鏈式存儲大，同時進行數據插入和刪除的時候可能造成需要移動整個線性表。下面要說的線性表的鏈式存儲很好的解決了上述出現的問題，相比較於順序存儲鏈式存儲稍微難理解一些，編程的難度也稍微大一些。

下面講述線性錶鏈式存儲的一些函數：

初始化線性表

List * ListInit();

銷燬線性表

int ListDestroy(List *list);

設置線性表為空

int ListClear(List *list);

獲取線性表的長度

int ListLength(pList list);

判斷線性表是否為空

int ListEmpty(pList list);

獲取線性表的對應位置的值

int GetElem(pList list,int index);

獲取此線性表中是否存在此數據，存在返回此數據在線性表中的位置

int LocateElem(pList list,int data);

判斷此數據是線性表中若不是線性表首數據返回前驅值，如果是返回空

int PreElem(pList list,int data);

判斷此數據是線性表中若不是線性表尾數據返回後繼值，如果是返回空

int SuccElem(pList list,int data);

在線性表的指定位置插入數據

int ListInsert(pList list,int index,int data);

在線性表的制定位置刪除數據

int ListDel(pList list,int index);

輸出線性表的數據

void ListDisplay(pList list);

源程序：

list.h

#ifndef _LIST_H
#define _LIST_H
#define LIST_ERR -1
#define LIST_OK 0
typedef struct{
 int data;
 struct ListNode * next;
}ListNode,*plistnode;
typedef struct{
 plistnode head;
 unsigned int length;
}List,*pList;
/**初始化線性表*/
List * ListInit();
/**銷燬線性表*/
int ListDestroy(List *list);
/**設置線性表為空*/
int ListClear(List *list);
/**獲取線性表的長度*/
int ListLength(pList list);
/**判斷線性表是否為空*/
int ListEmpty(pList list);
/**獲取線性表的對應位置的值*/
int GetElem(pList list,int index);
/**獲取此線性表中是否存在此數據，存在返回此數據在線性表中的位置*/
int LocateElem(pList list,int data);
/**判斷此數據是線性表中若不是線性表首數據返回前驅值，如果是返回空*/
int PreElem(pList list,int data);
/**判斷此數據是線性表中若不是線性表尾數據返回後繼值，如果是返回空*/
int SuccElem(pList list,int data);
/**在線性表的指定位置插入數據*/
int ListInsert(pList list,int index,int data);
/**在線性表的制定位置刪除數據*/
int ListDel(pList list,int index);
/**輸出線性表的數據*/
void ListDisplay(pList list);
#endif

list.c

#include 
#include "list.h"
static ListNode *Getindex(pList list,int index);
List * ListInit()
{
 List *list=NULL;
 printf("開始分配地址\n");
 if(NULL==(list=(ListNode *)malloc(sizeof(List))))
 {
 printf("分配地址空間失敗\n");
 return LIST_ERR;
 }
 printf("分配的地址為%u\n",list);
 list->head=NULL;
 list->length=0;
 return list;
}
int ListDestroy(List * list)
{
 int status;
 status=ListClear(list);
 if(status)
 {
 printf("釋放空間失敗\n");
 }
 else
 {
 printf("釋放空間成功\n");
 free(list);
 }
 return status;
}
int ListClear(List *list)
{
 if(list)
 {
 plistnode current,next;
 unsigned len;
 current=list->head;
 len=list->length;
 while(len--)
 {
 next=current->next;
 free(current);
 current=next;
 }
 list->head=NULL;
 list->length=0;
 return LIST_OK;
 }
 else
 {
 return LIST_ERR;
 }
 
}
int ListLength(pList list)
{
 if(list)
 {
 return list->length;
 }
 else
 {
 return LIST_ERR;
 }
 
}
int ListEmpty(pList list)
{
 if(list)
 {
 return list->length;
 }
 else
 {
 return LIST_ERR;
 }
 
}
int GetElem(pList list,int index)
{
 if(list)
 {
 if(index>list->length-1||index<0)
 {
 return LIST_ERR;
 }
 else
 {
 int i=0;
 plistnode node;
 node=Getindex(list,index);
 if(!node)
 {
 return LIST_ERR;
 }
 return node->data;
 }
 }
 return LIST_ERR;
}
int LocateElem(pList list,int data)
{
 if(list)
 {
 int i=0;
 plistnode node=NULL;
 node=list->head;
 for(i=0;ilength;i++)
 {
 if(!node)
 {
 return LIST_ERR;
 }
 if(node->data==data)
 {
 break;
 }
 node=node->next;
 }
 if(i==list->length)
 {
 return LIST_ERR;
 }
 else
 {
 return i;
 }
 }
 else
 {
 return LIST_ERR;
 }
 
}
int PreElem(pList list,int data)
{
 int index=LocateElem(list,data);
 if(index>0)
 {
 return GetElem(list,index-1);
 }
 else
 {
 return LIST_OK;
 }
 
}
int SuccElem(pList list,int data)
{
 int index=LocateElem(list,data);
 if((list->length-1)>index)
 {
 return GetElem(list,index+1);
 }
 else
 {
 return LIST_OK;
 }
}
int ListInsert(pList list,int index,int data)
{
 if(list)
 {
 if(list->length>=index&&index>=0)
 {
 ListNode *node=NULL;
 ListNode *current=NULL;
 if(NULL!=(node=(plistnode)malloc(sizeof(ListNode))))
 {
 node->data=data;
 node->next=NULL;
 if(index==0)
 {
 node->next=list->head;
 list->head=node;
 }
 else
 {
 current=Getindex(list,index-1);
 if(!current&&(index!=list->length))
 {
 return LIST_ERR;
 }
 node->next=current->next;
 current->next=node;
 }
 list->length++;
 return LIST_OK;
 }
 else
 {
 return LIST_ERR;
 }
 
 }
 else
 {
 return LIST_ERR;
 } 
 }
 else
 {
 return LIST_ERR;
 }
 
}
int ListDel(pList list,int index)
{
 if(0==list->length)
 {
 return LIST_ERR;
 }
 else
 {
 if(index>list->length||index<0)
 {
 return LIST_ERR;
 }
 else
 {
 ListNode *current=NULL;
 ListNode *before=NULL;
 before=Getindex(list,index-1);
 if(!before)
 {
 return LIST_ERR;
 }
 current=before->next;
 if(!current&&(index!=list->length))
 {
 return LIST_ERR;
 }
 before->next=current->next;
 free(current);
 list->length--;
 return LIST_OK;
 }
 }
}
void ListDisplay(pList list)
{
 if(list)
 {
 unsigned int len;
 ListNode *node;
 node=list->head;
 unsigned int i=0;
 len=list->length;
 while((len--)&&node)
 {
 printf("The %d is %d\n",i,node->data);
 node=node->next;
 i++;
 }
 }
 
}
ListNode *Getindex(pList list,int index)
{
 if(list&&list->length>index)
 {
 ListNode *node=NULL;
 int i;
 node=list->head;
 for(i=0;inext;
 }
 return node;
 }
 else
 {
 return NULL;
 }
 
}

main.c

#include 
#include "list.h"
int main(void)
{
 List * list=NULL;
 int status=-1;
 list=ListInit(list);
 if(!list)
 {
 printf("初始化失敗\n");
 }
 else
 {
 printf("初始化成功\n");
 printf("list的內存地址為 %u\n",list);
 }
 status=ListInsert(list,0,45);
 status=ListInsert(list,1,55);
 status=ListInsert(list,2,66);
 status=ListInsert(list,3,77);
 status=ListInsert(list,4,88);
 if(!status)
 {
 printf("插入數據成功\n");
 }
 else
 {
 printf("插入數據失敗\n");
 }
 ListDisplay(list);
 status=LocateElem(list,77);
 printf("The 77 is at %d\n",status);
 status=LocateElem(list,100);
 printf("The 100 is at %d\n",status);
 status=GetElem(list,2);
 printf("鏈表的第3個數據為%d\n",status);
 status=GetElem(list,8);
 printf("鏈表的第9個數據為%d\n",status);
 status=ListDel(list,-1);
 printf("鏈表的第-1個數據為%d\n",status);
 status=ListDel(list,0);
 if(!status)
 {
 printf("刪除數據成功\n");
 }
 else
 {
 printf("刪除數據失敗\n");
 }
 status=PreElem(list,88);
 printf("數據88的前一個數據是%d\n",status);
 status=PreElem(list,45);
 printf("數據45的前一個數據是%d\n",status);
 status=SuccElem(list,88);
 printf("數據88的後一個數據是%d\n",status);
 status=SuccElem(list,45);
 printf("數據45的後一個數據是%d\n",status);
 status=ListEmpty(list);
 printf("鏈表是否為空的狀態%d\n",status);
 ListDisplay(list);
 status=ListLength(list);
 printf("線性表的長度為%d\n",status);
 ListClear(list);
 status=ListLength(list);
 printf("線性表的長度為%d\n",status);
 list=ListDestroy(list);
 if(list)
 {
 printf("釋放失敗\n");
 printf("失敗狀態值為%d\n",status);
 }
 else
 {
 printf("釋放成功\n");
 }
 return 0;
}