声明的结构体叫“结点”,这个结点中放了数据和表明结点关系的指针
单链表:只有一个表示它直接后继结点的指针域
关于头结点,如果没有头结点,在添加删除到第一个结点时,处理会很不方便,所以大家都是用有头结点的
同样分一个.h和一个.c文件
LinList.h
//结点只一个数据域和一个指针域
typedef struct Node
{
DataType data;
struct Node *next;
}SLNode;
//这样,头结点就有它的空间了,只不过它的data没赋值,next为NULL
void ListInitiate(SLNode **head) //**的用法
{
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) /*malloc 函数返回的是 void * 类型,通过 (int *) 来将强制转换 */
exit(1);
(*head)->next=NULL;
}
//得到链表的元素个数
int ListLength(SLNode *head)
{
SLNode *p=head;
int size=0;
while(p->next!=NULL) //只要p的next不是空,它后面就还有元素
{
p=p->next;
size++;
}
return size;
}
//把x插入到i位置
int ListInsert(SLNode *head,int i,DataType x)
{
SLNode *p,*q;
int j;
p=head;
j=-1;
while(p->next!=NULL&&j<i-1) //如果现在是最后一个元素,那就不用j++了,直接插在后边就行,
//不然呢,得到要插入位置的前一个元素,因为要使前一个元素的next指向它
{
p=p->next;
j++;
}
if(j!=i-1)
{
printf("error");
return 0;
}
if((q=(SLNode *)malloc(sizeof(SLNode)))==NULL) //新生成一个结点,准备插入
exit(1);
q->data=x; //data=x
q->next=p->next; //现在插入的这个结点的next指向原本是它前面那个结点所指的位置
p->next=q; //将p->next也就插入点前面那一个结点的next指向我们现在插入的这个结点
return 1;
}
int ListDelete(SLNode *head,int i,DataType *x)//删除和插入作个相反的动作
{
SLNode *p,*s;
int j;
p=head;
j=-1;
//删除时,所删结点前面那个结点的next要指向所删结点后面的那个结点去,p->next是所删结点,p->next->next才是正确位置
while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)
{
p=p->next;
j++;
}
if(j!=i-1)
{
printf("error");
return 0;
}
s=p->next; //s来暂时存放我们要删除的结点
*x=s->data; //得到这个结点的数据
p->next=p->next->next; //指针域一换,它就可以解放了
free(s); //解放,解放的是原来的p->next(即所删结点)
return 1;
}
int ListGet(SLNode *head,int i,DataType *x)
{
SLNode *p;
int j;
p=head;
j=-1;
while(p->next!=NULL&&j<i) //这次要得到的就是 i 结点,不是再找它前面的那个结点了
{
p=p->next;
j++;
}
if(j!=i)
{
printf("error");
return 0;
}
*x=p->data;
return 1;
}
void Destroy(SLNode **head)
{
SLNode *p,*p1;
p=*head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
*head=NULL;
}
然后是
linList.c
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int DataType;
#include "LinList.h" //同样,这里有个顺序问题
void main(void)
{
SLNode *head; //定义一个头指针
int i,x;
ListInitiate(&head); //经头指针一个实实在在的地址
for(i=0;i<10;i++)
{
if(ListInsert(head,i,i+1)==0)
{
printf("ERROR!");
return;
}
}
if(ListDelete(head,4,&x)==0)
{
printf("ERROR!");
return;
}
for(i=0;i<ListLength(head);i++)
{
if(ListGet(head,i,&x)==0)
{
printf("ERROR!");
return;
}
else
printf("%d ",x);
}
Destroy(&head);
}
结果如下,后面一个是注释掉删除的结果
评论