单链表

1、基本组成

一个链表包含若干个结点，每一个结点由数据域和指针域组成

单链表的结点结构

typedef struct node { DataType data;//数据域 struct node *next;//指针域 }Node,*Link;

next指针域用来指向另一个相同结构的结点

使用Node,*Link，可以方便我们以后定义指针和结点

Node st; //等价于struct node st; Link p; //等价于struct node *p; 要使p指向st结构体变量 p=&st;

之后再需要申请结点的时候就可以直接写

p=(Link)malloc(sizeof(Node)); //也可以直接写 p=(struct node*)malloc(sizeof(Node));

如果想访问结点的数据域和指针域

//数据域 p->data //指针域 p->next

-------------------------------------------------------- 有两种链表，一种是第一个节点数据部分为空。另一种是第一个节点就存放数据。 两种方式的编程是有点不同的： 第一种方式，不管怎样对链表进行增加修改和删除，head的位置都不会变化，head的值只需要传入到函数中，不需要返回。 第二种方式，如果数据插入到第一个节点，head存储的地址会发生变化。这种方式的链表在定义函数时，需要返回链表的head。 推荐使用第一种,本文也是用的是第一种

--------------------------------------------------------

2、链表的基本操作

（1）单链表的遍历

操作接口

void displayNode(Link head)

具体代码

void displayNode(Link head) { p=head->next; while(p!NULL) { printf("%d",p->data); p=p->next; } }

注意：这里不能使用p++ 因为链表的存储是不连续的，p++会到指针的下一块内存，而不是链表的指针域所指向的内存

（2）求单链表元素个数

操作接口

int length(Link head);

具体代码

int length(Link head) { p=head->next; count=0; while(p!=NULL) { p=p->next; count++; } return count; }

（3）单链表的查找

操作接口

int queryNode(Link head,DataType x)

x是准备查找的数据，应该和数据域对应的数据类型一致

具体代码

int queryNode(Link head,DataType x) { p=head->next; count=0; while(p!=NULL) { if(p->data==x) { print(data); return true; } p=p->next; } return false;//如果循环结束了，说明没有找到 }

（4）单链表的插入

不论插入的位置在表头、表中、表尾，代码全都适用

bool insertNode(Link head,int i,DataType x) { p=head; count=0; while(p!=NULL&&count<i-1) { p=p->next; count++; } if(p==NULL) { return false; } else { node=(Link)malloc(sizeof(Node)); node->data=x; node->next=p->next;//先和下一个结点相连 p->next=node;//再和上一个结点相连。原来中间的连接关系自动断开 return true; } }

（5）创建一个单链表—头插法

操作接口

Link newList(DataType a[],int n)

将待插入的结点插入到头结点的后面

最好每次创建一个结点，就马上把他的next域设置为NULL

具体代码

Link newList(DataType a[],int n) { //创建头结点 head=(Link)malloc(sizeof(Node)); head->next=NULL; //创建后续结点 for(i=0;i<n;i++) { node=(Link)malloc(sizeof(Node)); node->data=a[i]; node->next=head->next; head->next=node; } return head; }

（6）创建一个单链表—尾插法

操作接口

Link newList(DataType a[],int n)

具体代码

Link newList(DataType a[],int n) { head=(Link)malloc(sizeof(Node)); head->next=NULL; rear=head; for(i=0;i<n;i++) { node=(Link)malloc(sizeof(Node)); node->data=a[i]; //node->next=NULL; near->next=node; rear=node; } rear->next=NULL;//这个语句很容易被忽略，或者在前面加一句node->next=NULL return head; }

(7)单链表结点的删除

操作接口

bool deleteNode(Link head,Datatype x)

具体代码

bool deleteNode(Link head,Datatype x) { ///判断是否是空表 if(head==NULL||head->next==NULL) { return false; } p=head->next; q=head; while(p!=NULL) { if(p->data==x) { q->next=p->next; free(p); return false; } else { q=p; p=p->next; } } //如果循环结束了，说明没有找到与x相等的数据 return false; }

（8）单链表的释放

操作接口

void clearLink(Link head)

具体代码

void clearLink(Link head) { while(head->next!=NULL) { q=head; head=head->next; free(p); } }