单链表操作 C实现

struct LNode { //定义一个节点

        int data; //数据域

        struct LNode *next; //指针域

};

0.初始化

typedef sturct LNode{                      //定义单链表结点类型      int date ;                //每个结点存放一个数据元素struct LNode *next;            //指针指向下一个结点
}LNodes, *LinkList;
typedef  LNode{                      //定义单链表结点类型      int date ;                //每个结点存放一个数据元素struct LNode *next;            //指针指向下一个结点
};//typedef struct LNode LNodes;
//typedef struct LNOde *LinkList;
//上面俩个是等价的1)不带头结点的单链表
bool InitList(LinkList &L)      //初始化空链表
{L = NULL;                 //空表没有任何结点return true;           
}void test()
{LinkList L ;         //声明一个指向单链表的指针//初始化一个空表InitList (L);
}判断是否为空
bool Empty(LinkList L){if(L == NULL)return true;else return false;
}
//或：
bool Empty(LinkList L){return (L == NULL);
}2)带头节的单链表
//初始化一个单链表（带头结点）
bool InitList (LinkList &L){L = (LNode * ) malloc (sizeof(LNode));        //分配一个头结点if (L == NULL)                                //内存不足分配失败return false; L->next  = NULL;return true;
}判断是否为空
bool Empty(LinkList L){if(L->next == NULL)return true;else return false;
}

1.尾插法建立链表

struct LNode *CreateLinkList1(void){  //尾插法创建链表struct LNode *head=(struct LNode *)malloc(LEN); //创建一个头节点head->next=NULL; //开始时头节点指针指向NULLstruct LNode *h=head,*s;struct LNode info;//接收从键盘输入每个节点的数据scanf("%d",&info.data);while(info.data!=0){  //创建链表，直到输入数据为0结束s=(struct LNode *)malloc(LEN);s->data=info.data;  //节点s接收输入数据h->next=s; //尾插如链表尾部h=h->next;  //保持h位于链表末尾，方便接收下一个节点数据scanf("%d",&info.data);}h->next=NULL;  //链表末尾指向NULLreturn head;
}

typedef struct LNode {int data; //数据域struct LNode *next; //指针域}LNodes,*LinkList;LNodes *insertFront(LNodes *head, LNodes *newNode) 
{newNode->next = head->next;head->next = newNode;return head;
}

2.头插法建立链表

struct LNode *CreateLinkList2(void){  //头插法创建链表struct LNode *head=(struct LNode *)malloc(LEN);head->next=NULL;struct LNode *h=head,*s;struct LNode info;scanf("%d",&info.data);while(info.data!=0){  //创建链表，直到输入数据为0结束s=(struct LNode *)malloc(LEN);s->data=info.data;//节点s接收输入数据s->next=h->next;  //头插插入头节点尾部，插入节点要始终跟着头节点后面h->next=s; scanf("%d",&info.data);}return head;
}

typedef struct LNode {int data; //数据域struct LNode *next; //指针域}LNodes,*LinkList;LNodes *insertBack(LNodes *head, LNodes *tail, LNodes *newNode) 
{newNode->next = NULL;tail->next = newNode;tail = newNode;return head;
}

3.链表结点删除操作

struct LNode *Delete(struct LNode *head,int x){ //删除链表中值为x的节点struct LNode *p=head->next,*pre=head,*q;while(p!=NULL){if(p->data==x){q=p;pre->next=p->next;p=p->next;free(q);}else{pre=p;p=p->next;}}return head;
}

4.在有序链表中插入一个结点

struct LNode *Insert(struct LNode *head,int x){  //创建一个递增链表，将x插入链表，并保持有序struct LNode *p=head->next,*pre=head,*q;while(p!=NULL){if(x<p->data){q=(struct LNode *)malloc(LEN);  //为插入值分配一个节点空间q->data=x;pre->next=q;q->next=p;break;}else{pre=p;p=p->next;}}return head;
}

5.遍历

void print(struct LNode *head){ //遍历链表并输出各个节点的数据struct LNode *p=head->next;while(p!=NULL){printf("%d->",p->data);p=p->next;}printf("NULL\n");
}

运行程序结果：

尾插法：1 2 3 4 6 7 8 9 0
1->2->3->4->6->7->8->9->NULL
头插法：1 2 3 4 6 7 8 9 0
9->8->7->6->4->3->2->1->NULL
删除节点8：1->2->3->4->6->7->9->NULL
插入节点5：1->2->3->4->5->6->7->9->NULL
Press any key to continue...

完整的代码如下：

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct LNode)  //LEN表示一个节点大小
struct LNode{  //定义一个节点int data; //数据域struct LNode *next; //指针域
};
struct LNode *CreateLinkList1(void){  //尾插法创建链表struct LNode *head=(struct LNode *)malloc(LEN); //创建一个头节点head->next=NULL; //开始时头节点指针指向NULLstruct LNode *h=head,*s;struct LNode info;//接收从键盘输入每个节点的数据scanf("%d",&info.data);while(info.data!=0){  //创建链表，直到输入数据为0结束s=(struct LNode *)malloc(LEN);s->data=info.data;  //节点s接收输入数据h->next=s; //尾插如链表尾部h=h->next;  //保持h位于链表末尾，方便接收下一个节点数据scanf("%d",&info.data);}h->next=NULL;  //链表末尾指向NULLreturn head;
}
struct LNode *CreateLinkList2(void){  //头插法创建链表struct LNode *head=(struct LNode *)malloc(LEN);head->next=NULL;struct LNode *h=head,*s;struct LNode info;scanf("%d",&info.data);while(info.data!=0){  //创建链表，直到输入数据为0结束s=(struct LNode *)malloc(LEN);s->data=info.data;//节点s接收输入数据s->next=h->next;  //头插插入头节点尾部，插入节点要始终跟着头节点后面h->next=s; scanf("%d",&info.data);}return head;
}
struct LNode *Delete(struct LNode *head,int x){ //删除链表中值为x的节点struct LNode *p=head->next,*pre=head,*q;while(p!=NULL){if(p->data==x){q=p;pre->next=p->next;p=p->next;free(q);}else{pre=p;p=p->next;}}return head;
}
struct LNode *Insert(struct LNode *head,int x){  //创建一个递增链表，将x插入链表，并保持有序struct LNode *p=head->next,*pre=head,*q;while(p!=NULL){if(x<p->data){q=(struct LNode *)malloc(LEN);  //为插入值分配一个节点空间q->data=x;pre->next=q;q->next=p;break;}else{pre=p;p=p->next;}}return head;
}
void print(struct LNode *head){ //遍历链表并输出各个节点的数据struct LNode *p=head->next;while(p!=NULL){printf("%d->",p->data);p=p->next;}printf("NULL\n");
}
int main(void){struct LNode *p1,*p2,*q,*y;printf("尾插法：");p1=CreateLinkList1(); //p1接收尾插法传回的头节点print(p1);printf("头插法：");p2=CreateLinkList2(); //p2接收头插法传回的头节点print(p2);printf("删除节点8：");q=Delete(p1,8);print(p1);printf("插入节点5：");y=Insert(p1,5);print(y);
}

头插法和尾插法详解

头插法
核心代码：
head->next = NULL;
s->next = head->next;
head->next = s;

单个结点

原始状态

第一个元素插入的过程（注意：1和2的顺序不能颠倒，不然会导致链表缺失）

第一个元素插入后

第二个元素插入的过程（其余元素插入的过程也类似）

第二个元素插入后

尾插法
核心代码：
tail = head;
s->next = NULL;
tail->next = s;
tail = s;

原始状态

第一个元素插入的过程（注意：2和3的顺序不能颠倒，不然会导致链表的生成出错）

第一个元素插入后

第二个元素插入的过程（其余元素插入的过程也类似）

第二个元素插入后

头插法和尾插法的对比
头插法建立链表的算法简短易懂，但是生成链表的结点顺序与原来输入的顺序相反，而用尾插法建立链表可使输入和生成的结点顺序相同

为什么会这样呢？
根据上面的头插法和尾插法的算法，我们很容易知道，当用头插法依次插入值分别为1,2,3,4,5的结点（也叫做元素）后，单链表会如下图所示：

但是用尾插法同样插入值分别为1,2,3,4,5的结点后，单链表却会如下图所示：

而在这两个链表中，输出链表中各个元素的值只能从已知的头结点head开始遍历，所以分别用头插法和尾插法创建链表后，依次输出的元素的值刚好是相反的

验证小例子：

#include <stdio.h>
#include <malloc.h>typedef struct node
{struct node* next;int data;}LinkList; //定义LinkList为struct node类型，即struct node可直接用LinkList来表示，方便定义//头插法创建单链表 
int main (void)
{int i, len = 5;
//len表示链表的长度	LinkList* head, * s;
//head为LinkList*类型的指针变量，表示头指针head = (LinkList*)malloc (sizeof (LinkList));
//malloc (sizeof (LinkList))意思是让系统分配内存大小为sizeof (LinkList)的空间head->next = NULL;
//令头指针的所指向结点的指针域为空for (i = 0; i < len; i++){s = (LinkList*)malloc (sizeof (LinkList));printf ("请输入该元素的值:");scanf ("%d", &s->data);s->next = head->next;head->next = s;}
//以下代码是为了将单链表中各个元素的值依次打印出来	LinkList* q;q = (LinkList*)malloc (sizeof (LinkList));q = head->next;while (q != NULL){printf ("%d", q->data);q = q->next;}return 0;
}

结果:
请输入该元素的值:1
请输入该元素的值:2
请输入该元素的值:3
请输入该元素的值:4
请输入该元素的值:5
54321

#include <stdio.h>
#include <malloc.h>typedef struct node
{struct node* next;int data;}LinkList; //尾插法创建单链表
int main (void)
{int i, len = 5;LinkList* head,* s,* tail;
//tail表示尾指针	head = (LinkList*)malloc (sizeof (LinkList));tail = head;for (i = 0; i < len; i++){s = (LinkList*)malloc (sizeof (LinkList));printf ("请输入该元素的值：");scanf ("%d", &s->data); s->next = NULL;tail->next = s;tail = s;}//以下代码是将单链表中各个元素的值依次打印出来   LinkList* q;q = head->next;while (q != NULL){printf ("%d", q->data);q = q->next;}return 0;} 

结果：
请输入该元素的值：1
请输入该元素的值：2
请输入该元素的值：3
请输入该元素的值：4
请输入该元素的值：5
12345
————————————————