使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的有点，同时由于增加了指针域，空间开销较大。不过这在算法与数据结构领域是很常见的，用空间换时间，毕竟鱼和熊掌不可兼得。
我的链表数据结构是使用C语言来实现的，那么下面来看一下链表的头文件定义了哪些操作。
下面是对于头结点的实现文件，末尾的 main 函数中还有针对各类函数的测试方法。
这个是我们数据结构上机实验的链表问题，#include<stdio.h>
#include<malloc.h>
#define
LEN
sizeof(LinkNode)
typedef
int
Datatype
typedef
int
Status
typedef
struct
LinkNode{
Datatype
data
struct
LinkNode
*next
}
LinkNode,*LinkList
typedef
struct
OrderedList
{
LinkNode
*head,*tail
int
Listsize
}
OrderedList//有序循环链表的头节点head,尾接接节点
tail及长度Listsize
Status
InitList(OrderedList
*List)//生成循环链表头节点
{
List->tail=List->head=(LinkList)malloc(LEN)
if(List->head==NULL)
return
0
else
{
List->head->next=List->tail
List->tail->next=List->head
List->Listsize=0
return
1
}
}
void
OrderedInsert(OrderedList
*List,Datatype
data)//每调用一次有序插入data形成有序的(从小到大)的链表
{
LinkNode
*p
,*q
if(List->head==List->tail->next)
{
p=(LinkNode*)malloc(LEN)
p->data
=
data
List->head->next=p
p->next=List->tail
List->Listsize++
}
else
{
p=List->head->next
q
=
List->head
while(p->data<data&&p!=List->tail)
{
q
=
p
p=p->next
}
if(p->data==data)
{printf("YOu
have
input
the
same
datas
%d\n\t
YOu
should
input
another
data
\n",data)
scanf("%d",&data)
OrderedInsert(List,data)
}
else
{
p=(LinkNode*)malloc(LEN)
p->data
=
data
p->next
=
q->next
q->next
=
p
List->Listsize++
}
}
}
void
Creatset(OrderedList
*List)//多次调用OrderedInsert()生成有序链表即集合List
{
Datatype
data
int
setsize
,
i=0
printf("Please
input
the
setsize
you
want
to
creat:\n")
scanf("%d",&setsize)
InitList(List)
if(setsize==0)
printf("You
needen't
input
any
data\n")
else
if(setsize==1)
printf("Please
input
a
single
data\n")
else
printf("Please
input
%d
different
datas\n",setsize)
while(i<setsize||setsize>List->Listsize)//当循环次数i小于setsize或者集合内实际元素数List.Listsize小于setsize时一直循环下去
{
scanf("%d",&data)
OrderedInsert(List,data)
i++
}
}
void
Append(OrderedList
*List,Datatype
data)//在循环链表的最后面追加
一个data
{
LinkNode
*p
p=(LinkNode*)malloc(LEN)
p->data=data
List->tail=List->tail->next=p
List->tail->next=List->head
List->Listsize+=1
}
void
MergeList(OrderedList
La,OrderedList
Lb,OrderedList
*Lc)//有序循环链表ListLa,ListLb求并集生成ListLc
{
LinkList
Pa,Pb
Pa=La.head->nextPb=Lb.head->next
while(Pa!=La.tail&&Pb!=Lb.tail)
{
if(Pa->data<=Pb->data)
{
Append(Lc,Pa->data)
Pa=Pa->next
}
else
{
Append(Lc,Pb->data)Pb=Pb->next
}
}
while(Pa!=La.tail)
{
Append(
Lc,Pa->data)Pa=Pa->next}
while(Pb!=Lb.tail)
{
Append(Lc,Pb->data)Pb=Pb->next}
}
void
Print(OrderedList
List)
{
LinkNode
*p
p=List.head->next
if(p->next==List.head)
printf("No
Elem\n")
while(p!=List.head)
{
printf("%5d",p->data)p=p->next
}
printf("\n")
}
void
main()
{
OrderedList
ListLa,ListLb,ListLc
Creatset(&ListLa)
Creatset(&ListLb)
InitList(&ListLc)
MergeList(ListLa,ListLb,&ListLc)
printf("The
orgnial
list
ListLa,ListLb:\n")
Print(ListLa)
Print(ListLb)
printf("The
Merge
list
ListLc\n")
Print(ListLc)
}
