数据结构C语言版-线性表的单链表存储结构表示和实现

#include<stdio.h>

#include<mallocoh>

#include(stdlib.h>

/*

数据结构C语言版线性表的单链表存储结构表示和实现

P28—31

编译环境：Dev-C++4o9o9o2

日期：2011年2月10日

*/

typedefintElemType;

//线性表的单链表存储结构

typedefstructLNode

(

ElemTypedata;〃数据域

structLNode*next；〃指针域

}LNode,*LinkList；

//typedefstructLNode*LinkList；//另一种定义LinkList的方法

//构造一个空的线性表L

intInitList(LinkList*L)

(

/*

产生头结点L,并使L指向此头结点，头节点的数据域为空，不放数据的。

void*malloc(size_t)

这里对返回值进行强制类型转换了，返回值是指向空类型的指针类型.

*/

(*L)=(LinkList)malloc(sizeof(structLNode));

if(!(*L))

exit(0)；//存储分配失败

(*L)->next=NULL；//指针域为空

return1；

)

//销毁线性表L,将包括头结点在内的所有元素释放其存储空间。

intDestroyList(LinkList*L)

(

LinkListq;

//由于单链表的每一个元素是单独分配的，所以要一个一个的进行释放

while(*L)

(

q=(*L)—〉next;

free(夫L)；〃释放

*L=q;

return1；

}

将L重置为空表，即将链表中除头结点外的所有元素释放其存

储空间，但是将头结点指针域置空，这和销毁有区别哦。不改变L,所以

不需要用指针。

*/

intClearList(LinkListL)

(

LinkListp,q；

p=L—>next；〃p指向第一个结点

while(p)//没到表尾则继续循环

(

q=p->next;

free(p)；〃释放空间

P二q；

)

L—>next=NULL;//头结点指针域为空，链表成了一个空表

return1;

)

//若L为空表(根据头结点L-〉next来判断，为空则是空表)，则返回1,

//否则返回0.

intListEmpty(LinkListL)

(

if(L—>next)〃非空

return0;

else

return1；

)

//返回L中数据元素个数。

intListLength(LinkListL)

(

inti=0;

LinkListp=L一〉next；〃p指向第一个结点

while(p)//没到表尾，则继续循环

(

i++；

p=p->next;

)

returni；

)

//算法2o8P29

〃L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并

//返回1,否则返回0o

intGetElem(LinkListL,inti,ElemType*e)

intj=1；〃j为计数器

LinkListp=L一〉next；//p指向第一个结点

while(p&&j<i)//顺指针向后查找，直到p指向第i个元素或p为空

{

p=p—>next;

j++；

)

if(!plIj)i)//第i个元素不存在

return0;

*e=p—)data；//取第i个元素

return1;

}

//返回L中第1个与e满足关系compare()的数据元素的位序。

//若这样的数据元素不存在，则返回值为0

intLocateElem(LinkListL,ElemTypee,int(compare)(ElemType,ElemType))

(

inti=0;

LinkListp=L——>next；

while(p)〃将链表的每一个元素进行对比

(

i++；

if(compare(p一〉data,e))//找到这样的数据元素

returni；

p=p->next；

)

return0;

)

//若cuje是L的数据元素，且不是第一个，则用pre_e返回它的前驱，

〃返回1；否则操作失败，pre_e无定义，返回

intPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)

(

LinkListq,

p=L—)next；〃p指向第一个结点

while(p->next)〃p所指结点有后继

(

q=p—〉next;〃q为p的后继

if(q->data==cur_e)

(

*pre_e=p—>data;

return1;

}

p=q；//p向后移

)

return-1;

)

〃若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继,

〃返回1；否则操作失败，next_e无定义，返回-1

intNextElem(LinkListL,ElemTypecur_e,ElemType*next_e)

(

LinkListp=L一〉next;//p指向第一个结点

while(p->next)〃p所指结点有后继

(

if(p—>data==cur_e)

{

*next_e=p-〉next-)data;

return1;

)

p=p->next;

)

return—1；

)

//算法2.9P30

//在带头结点的单链线性表L中第i个位置之前插入元素e

intListInsert(LinkLisl*L,inii,ElemTypee)

(

intj=0；

LinkListp=*L,s；

while(p&&j<i-l)//寻找第i—l个结点

(

p=p->next；

j++；

}

if(!p||j)i-D〃i小于1或者大于表长

return0;

s=(LinkList)malloc(sizeof(structLNode));//生成新结点

s->data=e；//插入L中

s—>next=p->next；

p-〉next=s；

return1；

)

//算法2。10P30

//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

intListDelete(LinkListinti,ElemType*e)

(

intj=O；

LinkListp=*L,q；

while(p-)next&&j<i-l)//寻找第i个结点，并令p指向其前趋

p=p-)next;

j++；

)

if(!p一〉next|Ij>i-1)//删除位置不合理

return0;

q=p—〉next;//删除并释放结点

p—〉next=q->next；

*e=q—〉data；

free(q)；

return1；

)

//依次对L的每个数据元素调用函数vi()

intListTraverse(LinkListL,void(*vi)(ElemType))

(

LinkListp=L->next；

〃对所有元素调用函数vi

while(p)

(

vi(p—〉data);

p=p->next；

)

printf

return1：

}

//在按非降序排列的线性表L中按非降序插入新的数据元素e

voidInsertAscend(LinkListL,ElemTypee)

(

LinkListq=L,

p=L—〉next；

while(p&&e>p—〉data)

(

q=p；

p=p-)next;

)

q->next=(LinkList)malloc(sizeof(structLNode))；//eqJo

q—〉next—〉data=e；

q->next—〉next=p；

)

//按非升序排列的线性表L中按非升序插入新的数据元素e

voidInsertDescend(LinkListL,ElemTypee)

(

LinkListq=L,p=L-〉next;

while(p&&e<p—>data)

q二p；

p=p-〉next；

)

q一〉next=(LinkList)malloc(sizeof(structLNode))；//e插在q后

q一〉next—>data=e；

q—>next->next=p；

)

//L的头部插入新的数据元素e,作为链表的第一个元素

intHeadInsert(LinkListL,ElemTypee)

(

LinkLists;

s=(LinkList)malloc(sizeof(structLNode))；//生成新结点

s—>data=e;//给结点赋值

s-)next=L一>next;//插在表头

L-)next=s；

return1；

)

〃在L的尾部插入新的数据元素e,作为链表的最后一个元素

intEndInsert(LinkListL,ElemTypee)

(

LinkListp=L；

while(p->next)〃使p指向表尾元素

p=p—〉next；

p一〉next=(LinkList)malloc(sizeof(structLNode))；//在表尾生成新结点

p—>next—〉data=e；//给新结点赋值

p一〉next-)next=NULL；//表尾

return1;

}

〃删除L的第一个数据元素，并由e返回其值

intDeleteFirst(LinkListL,ElemType*e)

(

LinkListp=L—〉next；

if(p)

{

*e=p—>data；

L->next=p-〉next;

free(p)；

return1;

)

else

return0；

}

〃删除L的最后一个数据元素，并用e返回其值

intDeleteTail(LinkListL,ElemType*e)

LinkListp=L,q;

if(!p—>next)//链表为空

return0;

while(p—〉next)

(

q=p；

p=p—>next；

)

q—〉next=NULL;//新尾结点的next域设为NULL

*e=p—〉data；

free(p);

return1;

}

//删除表中值为e的元素，并返回1;如无此元素,则返回0

intDeleteElem(LinkListL,ElemTypee)

(

LinkListp=L,q;

while(p)

(

q=p-〉next；

if(q&&q—〉data==e)

{

p-)next=q—>next；

free(q)；

return1；

)

p=q；

)

return0；

)

//用e取代表L中第i个元素的值

intReplaceElem(LinkListL,inti,ElemTypee)

(

LinkListp=L；

intj=0；

〃找到第i个元素的位置给p

while(p-)next&&j<i)

(

j++；

p=p-〉next；

)

if(j==i)

p—〉data=e；

return1；

)

else//表中不存在第i个元素

return0；

)

//按非降序建立n个元素的线性表

intCreatAscend(LinkList*L,intn)

(

intj;

LinkListp,q,s；

if(n(=0)

return0；

InitList(L);

printf("请输入％d个元素：(空格)\n"，n);

s=(LinkList)malloc(sizeof(structLNode));//第一个结点

scanf("%d”,&s—>data);

s—〉next=NULL;

(*L)—〉next=s；

for(j=l；j<n;j++)

(

s=(LinkList)malloc(sizeof(structLNode));//其余结点

scanf(''%cT,&s—〉data);

q=*L;

p=(*L)—〉next；

while(p&&p-)data<s~~>data)〃p没到表尾，且所指元素值小于新值

(

q二p；

p=p—〉next；//指针后移

}

s->next=q—)next;//元素插在q的后面

q—〉next=s；

)

return1；

)

//按非升序建立n个元素的线性表

intCreatDescend(LinkList*L,intn)

(

intj;

LinkListp,q,s；

if(n<=0)

return0;

InitList(L)；

printf("请输入％d个元素：(空格)\n"，n)；

s=(LinkList)malloc(sizeof(structLNode))；//第一个结点

scanf("%d”,&s-〉data)；

s—〉next=NULL；

(*L)一>next=s;

for(j=l；j<n；j++)

(

s=(LinkList)malloc(sizeof(structLNode));//其余结点

scanf("%d”,&s-〉data)；

q=*L；

p=(*L)—〉next；

while(p&&p—〉data)s—>data)〃p没到表尾，且所指元素值大于新值

(

q=p；

p=p->next；//指针后移

)

s-〉next=q一〉next；//元素插在q的后面

q->next=s；

}

return1；

)

//返回表头元素的值

intGetFirstElem(LinkListL，ElemType*e)

(

LinkListp=L->next;〃第一个结点给p

if(!p)〃空表

return0；

else//非空表

*e=p-〉data；

return1；

)

//算法2.11P30

//逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L

voidCreateList(LinkList*L,intn)

(

inti；

LinkListp；

//先建立一个带头结点的空单链表,相当于初始化单链表

*L=(LinkList)malloc(sizeof(structLNode))；

(*L)—〉next=NULL；

printf("请输入％d个数据\n"，n)；

for(i=n;i>0;------i)

(

p=(LinkList)malloc(sizeof(structLNode))；//生成新结点

scanf("%d,\&p一〉data);//输入元素值

p—>next=(*L)—>next；//插入到表头

(*L)->next=p;

)

)

//正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表

voidCreateList2(LinkList*L,intn)

(

inti；

LinkListp,q;

//先建立一个带头结点的空单链表，相当于初始化单链表

*L=(LinkList)malloc(sizeof(structLNode))；//生成头结点

(*L)—>next=NULL；

q=*L；

printf("请输入％d个数据\n"，n);

for(i=l;i<=n；i++)

(

p=(LinkList)malloc(sizeof(structLNode))；

scanf("％d”,&p—〉data);

q—>next=p;

q=q—〉next；

)

p—〉next=NULL;

)

/*

用单链表重写算法2。2供参考

已知线性表La和Lb中的数据元素按值非递减排列.

归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列

voidMergeList(LinkListLa,LinkListLb,LinkList*Lc)

(

inti=l,j=l,k=O；

intLa_len,Lb」en；

ElemTypeai,bj;

InitList(Lc);

La_len=ListLength(La)；

Lb_len=ListLength(Lb)；

while(i(=La_len&&j<=Lb_len)//表La和表Lb均非空

(

GetElem(La,i,&ai)；

GetElem(Lb,j,&bj)；

if(ai<=bj)

(

Listinsert(Lc,++k,ai);

++i;

else

ListInsert(Lc,++k,bj)；

++j；

)

)

while(i<=La_len)II表La非空且表Lb空

(

GetElem(La,i++,&ai)；

Listinsert(Lc,++k,ai);

)

while(j<=Lb_len)//表Lb非空且表La空

(

GetElem(Lb,j++,&bj)；

Listinsert(Lc,++k,bj);

}

)

*/

//算法2.12P31

//已知单链线性表La和Lb的元素按值非递减排列。

//归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列

voidMergeList(LinkListLa,LinkList*Lb,LinkList*Lc)

(

LinkListpa=La—〉next,pb=(*Lb)->next,pc；

*Lc=pc=La;〃用La的头结点作为Lc的头结点

while(pa&&pb)

(

if(pa—〉data(=pb—〉data)

(

pc—〉next=pa；

*Lc=pa;

pa=pa—〉next；

)

else

(

pc—〉next=pb;

pc=pb；

pb=pb-〉next;

)

}

pc->next=pa?pa：pb;//插入剩余段

free"Lb)；//释放Lb的头结点

Lb=NULL;

//判断是否相等的函数,Union()用到

intequal(ElemTypec1,ElemTypec2)

(

if(cl==c2)

return1;

else

return0；

}

//算法2.1

//将所有在线性表Lb中但不在La中的数据元素插入到La中

voidUnion(LinkListLa,LinkListLb)

(

ElemTypee;

intLa_len,Lb_len；

inti；

La_len=ListLength(La)；//求线性表的长度

Lb_len=ListLength(Lb)；

for(i=l;i<=Lb_len；i++)

(

GetElem(Lb,i,&e);//取Lb中第i个数据元素赋给e

if(!LocateElem(La,e,equal))//La中不存在和。相同的元素,则插入之

Listinsert(&La,++La_len,e)；

)

}

//数据元素判定函数(相等为1,否则为0)

intcomp(ElemTypecl,ElemTypec2)

{

if(cl==c2)

return1；

else

return0;

}

voidvisit(ElemTypec)

(

printf("％d”,c);

)

intmain()

(

LinkListL,La,Lb,Lc；

ElemTypee,eO,d;

inti,j,n,k；

〃初始化一个单链表

i=InitList(&L)；

〃通过插入操作创建一个单链表

for(j=l；j<=5；j++)

i=ListInsert(&L,l,j)；

〃调用visit函数，对单链表进行遍历

printf("在L的表头依次插入1〜5后:L=");

ListTraverse(L,visit)；//依次对元素调用visit(),输出元素的值

〃判断单链表是否为空

i=ListEmpty(L);

printf("L是否空：i=%d(l:是0：否)\n"，i)；

//清空单链表

i=ClearList(L)；

printf("清空L后:L=")；

ListTraverse(L,visit);

〃判断单链表是否为空

i=ListEmpty(L);

printf("L是否空：i=%d(1：是0：否)\n”,i);

〃再次通过插入操作创建一个单链表

for(j=l;j<=10；j++)

Listinsert(&L,j,j)；

printf(w在L的表尾依次插入1〜10后：L=")；

ListTraverse(L,visit)；

〃取得单链表的第5个元素

GetElem(L,5,&e)；

printf("第5个元素的值为：％d\n"，e);

〃在单链表中找到和j满足comp函数关系的元素

for(j=O;j(=1；j++)

(

k=LocateElem(L,j,comp)；

if(k)

printf("第%(1个元素的值为％d\n"，k,j)；

else

printf("没有值为％<1的元素\n”,j);

)

〃找到某个元素的前驱

for(j=l；j<=2；j++)〃测试头两个数据

(

GetElem(L,j,&e0)；//把第j个数据赋给eO

i=PriorElem(L,e0,&e)；//求eO的前驱

if(i==-1)

printf("元素％d无前驱\n”,eO);

else

printf("元素％€1的前驱为：%d\n"，e0,e);

}

〃找到某个元素的后继

for(j=ListLength(L)-1;j<=ListLength(L)；j++)//测试最后两个数据

GetElem(L,j,&eO)；〃把第j个数据赋给eO

i=NextElem(L,eO,&e)；//求eO的后继

if(i==—1)

printf("元素％d无后继\n",eO);

else

printf("元素％d的后继为:％d\n”,eO,e)；

}

〃求单链表的表长

k=ListLength(L)；〃k为表长

〃删除操作

for(j=k+l；j>=k；j—)

(

i=ListDelete(&L,j,&e)；〃删除第j个数据

if(i==0)

printf("删除第％d个数据失败\n”,j)；

else

printf("删除的元素为：％d\n",e)；

}

printf("依次输出L的元素:“)；

ListTraverse(L,visit)；

〃销毁单链表

DestroyList(&L)；

printf("销毁L后:L=%u\n\n",L)；

printf(w按非降序建立n个元素的线性表L,请输入元素个数n：");

scanf&n)；

CreatAscend(&L,n)；

printf("依次输出L的元素：”)；

ListTraverse(L,visit);

//按非降序插入元素10

InsertAscend(L,l0);

printf("按非降序插入元素10后，线性表L为：")；

ListTraverse(L,visit)；

〃在L的头部插入12

HeadInsert(L>12)；

〃在L的尾部插入9

Endinsert(L,9)；

printf("在L的头部插入12,尾部插入9后，线性表L为:");

ListTraverse(L,visit);

i=GetFirstElem(L,&e)；

printf("第1个元素是：%d\n",e);

prinlf("请输入要删除的元素的值：”)；

scanf("%d''，&e)；

i=DeleteElem(L,e)；

if(i)

printf("成功删除％d!\n",e)；

else

printf("不存在元素％d!\n”,e)；

printfC线性表L为：”)；

ListTraverse(L,visit)；

printf("请输入要取代的元素的序号元素的新值：”);

scanfT%d%d”,&n,&e)；

ReplaceElem(L,n,e)；

printf("线性表L为：“);

ListTraverse(L,visit)；

DestroyList(&L)；

printf("销毁L后，按非升序重新建立n个元素的线性表L,请输入”

”元素个数n(〉2)：(');

scanf("%d”,&n);

CreatDescend(&L,n)；

printf("依次输出L的元素：")；

ListTraverse(L,visit)；

//按非升序插入元素10

InsertDescend(L,10);

printf("按非升序插入元素10后,线性表L为：”)；

ListTraverse(L,visit);

printf("请输入要删除的元素的值：”)；

scanff'%d"，&e)；

i=DeleteElem(L,e);

if(i)

printf("成功删除%(1!\n",e)；

else

printf("不存在元素%d!\n”,e)；

printfC线性表L为:")；

ListTraverse(L,visit)；

DeleteFirst(L,&e);

DeleteTail(L,&d);

printf("删除表头元素％d和表尾元素％d后,线性表L为:"，e,d)；

ListTraverse(L,visit);

,,,,

printf(\n);

//测试算法2.11

n=3；

CreateList2(&La,n);//正位序输入n个元素的值

printf("正位创建后La=")；//输出链表La的内容

ListTraverse(La,visit)；

CreateList(&Lb,n)；〃逆位序输入n个元素的值

printf("逆位创建后Lb*；//输出链表Lb的内容

ListTraverse(Lb,visit)；

DestroyList(&La)；

DestroyList(&Lb)；

//测试算法2。12

//初始化一个单链表La

i=InitList(&La);

〃通过插入操作创建一个单链表

for(j=2；j(=10;j+=2)

i=ListInsert(&La,1,j);

printf("La=M);//输出链表La的内容

ListTraverse(La,visit)；

〃初始化一个单链表

i=InitList(&Lb)；

〃通过插入操作创建一个单链表

for(j=l；j<=10；j+=2)

i=ListInsert(&Lb,l,j)；

printf("Lb=")；〃输出链表Lb的内容

ListTraverse(Lb,visit)；

〃按非递减顺序归并La和Lb,得到新表Lc

MergeList(La,&Lb,&Lc)；

printf("合并La和Lb后，Lc=M)；