数据结构C语言版 静态链表实现集合运算.doc

#include<>/* 数据结构C语言版静态链表实现集合运算 P33-34 编译环境:Dev-C++ 日期:2011年2月10日*/typedefcharElemType;#defineMAXSIZE100//链表的最大长度//线性表的静态单链表存储结构typedefstruct{ ElemTypedata; //存储数据,数据域 intcur; //游标指示器cur,ponent,SLinkList[MAXSIZE];////将一维数组L中各分量链成一个备用链表,L[0].cur为头指针,//L[0]无数据域。“0”表示空指针voidInitSpace(SLinkListL){ inti; for(i=0;i<MAXSIZE-1;i++) L[i].cur=i+1; L[MAXSIZE-1].cur=0;}////若备用链表非空,则返回分配的结点下标(备用链表的第一个结点),否则返回0intMalloc(SLinkListspace){ inti=space[0].cur; if(i) //备用链表非空//备用链表的头结点指向原备用链表的第二个结点,因为第一个结点//已经被使用了,不加入备用链表中 space[0].cur=space[i].cur; returni;//返回新开辟结点的坐标}//构造一个空链表,返回值为空表在数组中的位序intInitList(SLinkListL){ inti; i=Malloc(L); //调用Malloc(),简化程序 L[i].cur=0; //空链表的表头指针为空(0),头指针无数据域 returni;}//将此表重置为空表,即将这个链表转化为备用表的一部分intClearList(SLinkListL,intn){ intj,k, i=L[n].cur;//链表第一个结点的位置 L[n].cur=0;//将链表置空 k=L[0].cur;//备用链表第一个结点的位置 L[0].cur=i;//把链表的结点连到备用链表的表头 while(i)//没到链表尾 { j=i; i=L[i].cur;//指向下一个元素 } L[j].cur=k;//把原备用链表的第一个结点接到原链表的尾部, //最终构成的备用链表为以原来链表的头结点为第一个结点的备用 //链表(即原链表+原备用链表) return1;}//判断L中表头位序为n的链表是否空,若是空则是空表返回1;否则返回0intListEmpty(SLinkListL,intn){ if(L[n].cur==0)//空表 return1; else return0;}//返回L中表头位序为n的链表的数据元素个数intListLength(SLinkListL,intn){ intj=0, i=L[n].cur;//i指向第一个元素 while(i)//没到静态链表尾 { i=L[i].cur;//指向下一个元素 j++; } returnj;}//用e返回L中表头位序为n的链表的第i个元素的值intGetElem(SLinkListL,intn,inti,ElemType*e){ intl, k=n;//k指向表头序号 if(i<1||i>ListLength(L,n))//i值不合理 return0; for(l=1;l<=i;l++)//移动i-1个元素 k=L[k].cur; *e=L[k].data; //此时k指向第i个元素的位置 return1;}//在L中表头位序为n的静态单链表中查找第1个值为e的元素。//若找到,则返回它在L中的位序,否则返回0intLocateElem(SLinkListL,intn,ElemTypee){ inti=L[n].cur; //i指示表中第一个结点 while(i&&L[i].data!=e) //在表中顺链查找(e不能是字符串) i=L[i].cur; returni;}//若cur_e是此单链表的数据元素,且不是第一个intPriorElem(SLinkListL,intn,ElemTypecur_e,ElemType*pre_e){ intj,i=L[n].cur;//i为链表第一个结点的位置 do {//先向后移动结点,然后再进行判断 j=i; i=L[i].cur; }while(i&&cur_e!=L[i].data); if(i)//找到该元素 { *pre_e=L[j].data; return1; } return0;}//若cur_e是此单链表的数据元素,且不是最后一个intNextElem(SLinkListL,intn,ElemTypecur_e,ElemType*next_e){ inti; i=L