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

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; }