ADT线性表Data {a1,a2,…,an},每个数据元素类型为DataType，除第一个（最后一个）元素，每个元素有且仅有一个直接前驱（后继）元素，数据元素之间的关系是一对一的关系.Operation InitList(*L) ListEmpty(L) ClearList(*L) GetElem(L,i,*e) …endADF线性表顺序存储结构-数组链式存储结构单链表静态链表循环链表双向链表
#includestdio.h#includestdlib.h#includetime.h#defineMAXSIZE20#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintStatus;typedefintElemType;typedefstruct//顺序储存结构{ElemTypedata[MAXSIZE];intlength;}SqList;StatusGetElem(SqListL,inti,ElemType*e)//顺序储存结构获得元素操作，用e返回L中第i个数据元素的值{if(L.length==0
i1
iL.length)returnERROR;*e=L.data[i-1];returnOK;}StatusListInsert(SqList*L,inti,ElemTypee)//插入操作，在L中第i个位置之前插入新的数据元素e，L的长度加1{intk;if(L-length==MAXSIZE)returnERROR;//顺序线性表已满if(i1
iL-length+1)returnERROR;//i不在合理范围内if(i=L-length)//若插入数据不在表尾{for(k=L-length-1;k=i-1;k--)L-data[k+1]=L-data[k];}L-data[i-1]=e;L-length++;returnOK;}StatusListDelete(SqList*L,inti,ElemType*e)//删除L的第i个数据元素，并用e返回其值，L长度减1{intk;if(L-length==0)returnERROR;//线性表为空if(i1
iL-length)returnERROR;//删除位置不正确*e=L-data[i-1];if(iL-length)//如果删除不是最后的位置{for(k=i;kL-length;k++)L-data[k-1]=L-data[k];}L-length--;returnOK;}//线性表的单链表储存结构typedefstructNode{ElemTypedata;structNode*next;}Node;typedefstructNode*LinkList;//定义LinklistStatusGetElemN(LinkListL,inti,ElemType*e)//用e返回L中第i个数据元素的值{intj;LinkListp;//声明一结点pp=L-next;//让p指向链表L的第一个结点j=1;//j为计数器while(pji)//p不为空或者j还没有等于i，循环继续{p=p-next;//让p指向下一个结点++j;}if(!p
ji)returnERROR;//第i个元素不存在*e=p-data;//获得第i个元素的数据returnOK;}StatusLinkInsertN(LinkList*L,inti,ElemTypee)//在L中第i个位置之前插入新的元素e，L的长度加1{intj;LinkListp,s;p=*L;j=1;while(pji)//寻找第i个结点{p=p-next;++j;}if(!p
ji)returnERROR;//第i个元素不存在s=(LinkList)malloc(sizeof(Node));//生成新结点ss-data=e;s-next=p-next;p-next=s;returnOK;}StatusListDeleteN(LinkList*L,inti,ElemType*e)//删除L的第i个数据元素，并用e返回其值，L的长度减1{LinkListp,q;intj=1;p=*L;while(pji)//找到第i个结点{p=p-next;++j;}if(!p
ji)returnERROR;//第i个元素不存在q=p-next;p-next=q-next;//将第i-1个元素的后继变为第i+1个元素*e=q-data;//用e返回被删除的元素的值free(q);//回收删除结点，释放内存returnOK;}//随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）voidCreateListHead(LinkList*L,intn){LinkListp;inti;srand(time(0));//初始化随机数种子*L=(LinkList)malloc(sizeof(Node));(*L)-next=NULL;//先建立一个带头结点的单链表for(i=0;in;i++){p=(LinkList)malloc(sizeof(Node));//生产新结点p-data=rand()%+1;//随机生成以内的数字p-next=(*L)-next;(*L)-next=p;//插入到表头}}//随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）voidCreateListTail(LinkList*L,intn){LinkListp,r;inti;srand(time(0));*L=(LinkList)malloc(sizeof(Node));r=*L;for(i=0;in;i++){p=(Node*)malloc(sizeof(Node));//生产新结点p-data=rand()%+1;r-next=p;r=p;}r-next=NULL;}StatusClearList(LinkList*L)//将L重置为空表{LinkListp,q;p=(*L)-next;//p指向第一个结点while(p){q=p-next;free(p);p=q;}(*L)-next=NULL;//头结点指针域为空returnOK;}//静态链表#defineMAXSIZES0typedefstruct{ElemTypedata;intcur;//游标（Cursor），为0时表示无指向}Component,StaticLinkList[MAXSIZES];intListLength(StaticLinkListL){intj=0;inti=L[MAXSIZES-1].cur;while(i){i=L.cur;j++;}returnj;}//将一维数组space中各分量链成一备用链表//space[0].cur为头指针，“0”表示空指针StatusInitList(StaticLinkListspace){inti;for(i=0;iMAXSIZES-1;i++)space.cur=i+1;space[MAXSIZES-1].cur=0;//目前静态链表为空，最后一个元素的cur为0returnOK;}//静态链表的插入操作//建立备用空间链表，若备用空间链表非空，则返回分配的结点下标，否则返回0intMalloc_SLL(StaticLinkListspace){inti=space[0].cur;//当前数组第一个元素的cur存的值,就是要返回的第一个备用空闲的下标if(space[0].cur)space[0].cur=space.cur;returni;}//Free_SLL将下标为k的空闲结点回收到备用链表voidFree_SSL(StaticLinkListspace,intk){space[k].cur=space[0].cur;//把第一个元素cur值赋给要删除的分量space[0].cur=k;//把要删除的分量下标赋给第一个元素的cur}//在L中第i个元素之前插入新的数据元素eStatusListInsertS(StaticLinkListL,inti,ElemTypee){intj,k,l;k=MAXSIZES-1;//k首先是最后一个元素的下标if(i1
iListLength(L))returnERROR;j=Malloc_SLL(L);//获得空闲分量的下标if(j){L[j].data=e;for(l=1;l=i-1;l++)//找到第i个元素之前的位置k=L[k].cur;L[j].cur=L[k].cur;//把第i个元素之前的cur赋值给新元素的curL[k].cur=j;//把新元素的下标赋值给第i个元素之前的元素的curreturnOK;}returnERROR;}//静态链表的删除操作//删错在L中第i和数据元素eStatusListDeleteS(StaticLinkListL,inti){intj,k;if(i1
iListLength(L))returnERROR;k=MAXSIZES-1;for(j=1;j=i-1;j++)//找到第i个元素之前的位置k=L[k].cur;j=L[k].cur;L[k].cur=L[j].cur;Free_SSL(L,j);returnOK;}//循环链表代码略//双向链表typedefstructDulNode{ElemTypedata;structDulNode*prior;structDulNode*next;}DulNode,*DuLinkList;
#数据结构与算法/《大话数据结构》#
预览时标签不可点收录于话题#个上一篇下一篇