typedef struct Node{
ElemType data
struct Node *next
} *LNode, *LinkList
//----------线性表的单链表基本 *** 作------------
LinkList InitList(void)//构造一个空的线性表
void DestroyList(LinkList *L)//初始条件:线性表L已存在。 *** 作结果:销毁线性表L。
LinkList MakeEmpty(LinkList L)//初始条件:线性表L已存在。 *** 作结果:将线性表L重置为空表。
int IsEmpty(LinkList L)//初始条件:线性表L已存在。 *** 作结果:判断线性表是否为空表。
int ListLength(LinkList L)//初始条件:线性表L已存在。 *** 作结果:返回线性表L结点的个数。
LNode IsLast(LinkList L)//初始条件:线性表L已存在。 *** 作结果:返回线性表L的最后一个结点(尾结点)。
LNode NewLNode(ElemType X)//构造一个数据域为X的新结点
LNode FindPrefious(ElemType X, LinkList L)//初始条件:线性表L已存在。 *** 作结果:在线性表L中寻找值为X的结点,若找到则返回该结点的前驱,否则返回NULL。
void ListDelete(LNode Pre)//初始条件:线性表L中结点P已找到。 *** 作结果:删除该结点。
void ListInsert(LNode Pre, LNode S)//初始条件:线性表L中结点P已找到,新结点S已构造。 *** 作结果:在该结点之前插入新结点X。
----------线性表的单链表基本 *** 作的算法实现------------
//我给链表设置了一个头结点,虽然它的数据域毫无意义,但它作为一个指针却意义非凡!
//它的作用我们在下面的例程中可以领教
LinkList InitList(void) //构造一个空的线性表
{
LNode Head
Head = (LNode)malloc(sizeof(struct Node))//为链表的头结点分配空间
if(!Head)
{
printf("Out of space!")
return NULL
}
Head->next = NULL
return Head//返回头结点
}
void DestroyList(LinkList *L)//初始条件:线性表L已存在。 *** 作结果:销毁线性表L。
{
LNode Head, P
if(*L)//若线性表L已存在
{
Head = *L
P = Head->next
while(!P) //把链表中除头结点外的所有结点释放
{
free(Head)
Head = P
P = Head->next
}
free(Head)//释放头结点
}
}
LinkList MakeEmpty(LinkList L)//初始条件:线性表L已存在。 *** 作结果:将线性表L重置为空表。
{
LNode Head, P
Head = *L
P = Head->next
while(!P)//把链表中除头结点外的所有结点释放
{
free(Head)
Head = P
P = Head->next
}
return (Head)//返回头结点
}
int IsEmpty(LinkList L)//初始条件:线性表L已存在。 *** 作结果:判断线性表是否为空表。
{
return L->next == NULL
}
int ListLength(LinkList L)//初始条件:线性表L已存在。 *** 作结果:返回线性表L结点的个数。
{
LNode P = L->next
int num = 0
while(P) //累积线性表L结点的个数
{
num++
P = P->next
}
return num//返回线性表L结点的个数
}
//初始条件:线性表L已存在。 *** 作结果:返回线性表L的最后一个结点(尾结点)。
LNode IsLast(LinkList L)
{
LNode P = L->next
if(P)
{
while(P->next) //遍历线性表L
P = P->next
}
return P//返回线性表L的最后一个结点,若为空表则返回NULL
}
LNode NewLNode(ElemType X)//构造一个数据域为X的新结点
{
LNode S
S = (LNode)malloc(sizeof(struct Node))//为新结点分配空间
if(!S)
{
printf("Out of space!")
return NULL
}
S->data = X
S->next = NULL
return S//返回新结点
}
//线性表L已存在。 *** 作结果:在线性表L中寻找值为X的结点,若找到则返回该结点的前驱,否则返回NULL。
LNode FindPrefious(ElemType X, LinkList L)
{
LNode P = L
while(P->next &&P->next->data != X)//遍历链表寻找值为X的结点
P = P->next
if(!P->next) //如果找不到值为X的结点,返回NULL
return NULL
else //若找到则返回该结点的前驱P
return P
}
void ListDelete(LNode Pre)//初始条件:线性表L中结点P已找到。 *** 作结果:删除该结点。
{
LNode P = Pre->next
Pre->next = P->next
free(P)
}
//初始条件:线性表L中结点P已找到,新结点S已构造。。 *** 作结果:在该结点之前插入新结点X。
void ListInsert(LNode Pre, LNode S)
{
S->next = Pre->next
Pre->next = S
}
如果还没解决你的问题,可以加我百度HI账号。
二、单链表的基本运算
建立了一个单链表之后,如果要进行一些如插入、删除等 *** 作该怎么办?所以还须掌握一些单链表的基本算法,来实现这些 *** 作。单链表的基本运算包括:查找、插入和删除。下面我们就一一介绍这三种基本运算的算法,并结合我们建立单链表的例子写出相应的程序。
1、查找
对单链表进行查找的思路为:对单链表的结点依次扫描,检测其数据域是否是我们所要查好的值,若是返回该结点的指针,否则返回NULL。
因为在单链表的链域中包含了后继结点的存储地址,所以当我们实现的时候,只要知道该单链表的头指针,即可依次对每个结点的数据域进行检测。
以下是应用查找算法的一个例子:
#include
#include
#include /*包含一些字符串处理函数的头文件*/
#define N 10
typedef struct node
{
char name[20]
struct node *link
}stud
stud * creat(int n) /*建立链表的函数*/
{
stud *p,*h,*s
int i
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!")
exit(0)
}
h->name[0]='\0'
h->link=NULL
p=h
for(i=0i<ni ) {
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!")
exit(0)
}
p->link=s
printf("请输入第%d个人的姓名",i 1)
scanf("%s",s->name)
s->link=NULL
p=s
}
return(h)
}
stud * search(stud *h,char *x) /*查找链表的函数,其中h指针是链表的表头指针,x指针是要查找的人的姓名*/
{
stud *p/*当前指针,指向要与所查找的姓名比较的结点*/
char *y/*保存结点数据域内姓名的指针*/
p=h->link
while(p!=NULL)
{
y=p->name
if(strcmp(y,x)==0) /*把数据域里的姓名与所要查找的姓名比较,若相同则返回0,即条件成立*/
return(p)/*返回与所要查找结点的地址*/
else p=p->link
}
if(p==NULL)
printf("没有查找到该数据!")
}
main()
{
int number
char fullname[20]
stud *head,*searchpoint/*head是表头指针,searchpoint是保存符合条件的结点地址的指针*/
number=N
head=creat(number)
printf("请输入你要查找的人的姓名:")
scanf("%s",fullname)
searchpoint=search(head,fullname)/*调用查找函数,并把结果赋给searchpoint指针*/
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)