数据结构与算法：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;
}