C 语言静态链表实现
可运行源代码 staticlink.h
#include <stdio.h> #include <stdlib.h> #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define MAX_SIZE 100 typedef int Status; typedef int ElementType; typedef struct StaticLinkList { ElementType data; int cur; }component,SLinkList[MAX_SIZE]; int Malloc(SLinkList space); void Free(SLinkList space,int k); void initList(SLinkList l); void ClearList(SLinkList l); Status GetElement(SLinkList l,int i,ElementType *e); int LocateElement(SLinkList l,ElementType e); Status PriorElement(SLinkList l,ElementType cur_e,ElementType *pre_e); Status NextElement(SLinkList l,ElementType cur_e,ElementType *next_e); Status ListInsert(SLinkList l,int i,ElementType e); Status ListDelete(SLinkList l,int i,ElementType *e); void ListTraverse(SLinkList l, void (*visit)(ElementType)); void print1(ElementType e);
staticlink.c
#include <stdio.h> #include "staticlink.h" //备用链表不为空返回分配的结点下标 int Malloc(SLinkList space) { int i = space[0].cur; if(i) space[0].cur = space[i].cur;//备用链表的头结点指向原备用链表的第二个空闲结点 return i; } //将下标为k的结点回收到备用链表中 void Free(SLinkList space,int k) { space[k].cur = space[0].cur;//回收结点游标指向备用链表的第一个结点 space[0].cur = k;//备用链表的头结点指向新回收的结点 } /*构造一个空的链表l，表头为l，最后一个单元l[MAX_SIZE - 1]，其他单元链成一个备用 链表，表头为l的第一个单元l[0],"0" 表示空指针 */ void initList(SLinkList l) { int i; l[MAX_SIZE - 1].cur = 0;//最后一个单元为空链表的表头 //其他单元链接成以l[0]为表头的备用链表 for(i = 0; i < MAX_SIZE - 2;i++) { l[i].cur = i+1; } } //清空链表 void ClearList(SLinkList l) { int j,k,i=l[MAX_SIZE-1].cur;//i指向链表的第一个结点 l[MAX_SIZE-1].cur=0;//第一个结点为头结点表示链表为空 k=l[0].cur;//备用链表第一个结点的位置即第一个空闲结点的位置 l[0].cur = i; while(i){ j = i; i=l[i].cur; } l[j].cur = k; } Status ListEmpty(SLinkList l) { if(l[MAX_SIZE-1].cur == 0) return TRUE; else return FALSE; } int ListLength(SLinkList l) { int j = 0,i=l[MAX_SIZE -1].cur; while(i) { i = l[i].cur; j++; } return j; } Status GetElement(SLinkList l,int i,ElementType *e) { int m,k=MAX_SIZE-1; if(i<1||i>ListLength(l)) return ERROR; for(m=1;m<=i;m++) k=l[k].cur; *e = l[k].data; return OK; } int LocateElement(SLinkList l,ElementType e){ int i = l[MAX_SIZE-1].cur; while(i && l[i].data !=e) i = l[i].cur; return i; } Status PriorElement(SLinkList l,ElementType cur_e,ElementType *pre_e){ int j,i=l[MAX_SIZE -1].cur; do{ j = i; i = l[i].cur; }while(i && cur_e!=l[i].data); if(i) { *pre_e=l[j].data; return OK; }else return ERROR; } Status NextElement(SLinkList l,ElementType cur_e,ElementType *next_e){ int j,i=LocateElement(l,cur_e); if(i) { j=l[i].cur; if(j) { *next_e=l[j].data; return OK; } } return ERROR; } Status ListInsert(SLinkList l,int i,ElementType e){ int m,j,k=MAX_SIZE-1; if(i < 1 || i > ListLength(l) + 1 ) return ERROR; j=Malloc(l); if(j) { l[j].data = e; for(m =1;m<i;m++) k=l[k].cur; l[j].cur=l[k].cur; l[k].cur = j; return OK; } return ERROR; } Status ListDelete(SLinkList l,int i,ElementType *e){ int j,k=MAX_SIZE-1; if(i < 1||i> ListLength(l)) return ERROR; for(j =1;j<i;j++) k=l[k].cur; j=l[k].cur; l[k].cur=l[j].cur; *e=l[j].data; Free(l,j); return OK; } void print1(ElementType e){ printf("%3d",e); } void ListTraverse(SLinkList l, void (*visit)(ElementType)){ int i = l[MAX_SIZE -1].cur; while(i){ visit(l[i].data); i=l[i].cur; } printf(" "); }
staticlinkmain.c
#include <stdio.h> #include "staticlink.h" int main(void){ SLinkList l; int i,k,j; ElementType e0,e1,e; initList(l); for(i=1;i<=5;i++) ListInsert(l,i,i); k=ListEmpty(l); printf("表为空?k=%d(1:是0:否)",k); printf(" "); ListTraverse(l,print1); printf("链表的长度%d",ListLength(l)); printf(" "); printf("清空链表 "); ClearList(l); printf("清空后"); ListTraverse(l,print1); printf("再次判断是否为空 "); k=ListEmpty(l); printf("表为空?k=%d(1:是0:否)",k); printf(" "); printf("再次插入元素 "); for(i=1;i<=10;i++) ListInsert(l,i,i); ListTraverse(l,print1); printf("链表的长度%d",ListLength(l)); printf(" "); printf("前驱判断 "); for(i=1;i<=10;i++){ GetElement(l,i,&e0); k=PriorElement(l,e0,&e1); if(k==ERROR) printf("元素%d无前驱 ",e0); else printf("元素%d的前驱是%d ",e0,e1); } printf(" "); printf(" "); printf("后继判断 "); for(i=1;i<=10;i++) { GetElement(l,i,&e0);//把L中的第i个元素的值赋给e0 k=NextElement(l,e0,&e1);//求e0的前驱，成功的话赋给e1 if(k==ERROR) printf("元素%d无后继 ",e0); else printf("元素%d的后继%d ",e0,e1); } printf(" 删除元素 "); k=ListLength(l); for(j=k+1;j>0;j--) { i=ListDelete(l,j,&e);//删除第j个元素 if(i==ERROR) printf("删除第%d个元素失败 ",j); else printf("删除第%d个元素成功,其值为%d ",j,e); } return 0; }
编译运行
gcc staticlink.h staticlink.c staticlinkmain.c -o staticlinkmain
运行结果
表为空?k=0(1:是0:否)
1 2 3 4 5
链表的长度5
清空链表
清空后
再次判断是否为空
表为空?k=1(1:是0:否)
再次插入元素
1 2 3 4 5 6 7 8 9 10
链表的长度10
前驱判断
元素1无前驱
元素2的前驱是1
元素3的前驱是2
元素4的前驱是3
元素5的前驱是4
元素6的前驱是5
元素7的前驱是6
元素8的前驱是7
元素9的前驱是8
元素10的前驱是9
后继判断
元素1的后继2
元素2的后继3
元素3的后继4
元素4的后继5
元素5的后继6
元素6的后继7
元素7的后继8
元素8的后继9
元素9的后继10
元素10无后继
删除元素
删除第11个元素失败
删除第10个元素成功,其值为10
删除第9个元素成功,其值为9
删除第8个元素成功,其值为8
删除第7个元素成功,其值为7
删除第6个元素成功,其值为6
删除第5个元素成功,其值为5
删除第4个元素成功,其值为4
删除第3个元素成功,其值为3
删除第2个元素成功,其值为2
删除第1个元素成功,其值为1