单链表操作 C实现

struct LNode { //定义一个节点

        int data; //数据域

        struct LNode *next; //指针域

};

0.初始化

typedef sturct LNode{                      //定义单链表结点类型      
    int data ;                //每个结点存放一个数据元素
    struct LNode *next;            //指针指向下一个结点
}LNodes, *LinkList;
typedef  LNode{                      //定义单链表结点类型      
    int data ;                //每个结点存放一个数据元素
    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; //开始时头节点指针指向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接收输入数据
		h->next=s; //尾插如链表尾部
		h=h->next;  //保持h位于链表末尾，方便接收下一个节点数据
		scanf("%d",&info.data);
	}
	h->next=NULL;  //链表末尾指向NULL
	return head;
}

 
typedef struct LNode {
 
       int data; //数据域
 
       struct LNode *next; //指针域
 
  }LNodes,*LinkList;
 
LNodes *insertBack(LNodes *head, LNodes *tail, LNodes *newNode) 
{
    //tail = head;
    newNode->next = NULL;
    tail->next = newNode;
    tail = newNode;
    return head;
}
 
LNodes *insertBacks(LNodes *head,  LNodes *newNode) 
{
    LNodes *tail;
    LNodes *h = head;
    while(h && h->next)
        h = h->next;
    tail = h;
 
    newNode->next = NULL;
    tail->next = newNode;
    tail = 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 *insertFront(LNodes *head, LNodes *newNode) 
{
    newNode->next = head->next;
    head->next = 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; //开始时头节点指针指向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接收输入数据
		h->next=s; //尾插如链表尾部
		h=h->next;  //保持h位于链表末尾，方便接收下一个节点数据
		scanf("%d",&info.data);
	}
	h->next=NULL;  //链表末尾指向NULL
	return 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);
}

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

 
LinkList revert0(LinkList head) {
    if (head == NULL || head->next == NULL)
        return head;
    LinkList p1,p2,p3;
 
    p1 = head, p2 = head->next;
    while(p2){
        p3 = p2->next;
 
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    head->next = NULL; //important ,if not ,will has circle
    head=p1;
 
    return head;
}
 
LinkList revert1(LinkList head) {
    LinkList pRevHead = NULL;
    LinkList pPrev = NULL;
    LinkList pNodeNext;
    LinkList pNode = head;
    while (pNode) {
        pNodeNext = pNode->next;
        if (pNodeNext == NULL)
            pRevHead = pNode;
        pNode->next = pPrev;
        pPrev = pNode;
        pNode = pNodeNext;
    }
 
    return pRevHead;
}
 
void  DeleteAll(LinkList head){
    LinkList p = head;
    while (p!= NULL){
        LinkList pdel = p;
        p = p->next;
        free(pdel);
    }
}
 
void PrintList(LinkList head) {
    while(head) {
         printf("%d ", head->data);
         head = head->next;
    }
    printf("\n");
}
 
void PrintListReverse(LinkList head){
    if (head !=NULL){
        PrintListReverse(head->next);
        printf("%d ", head->data);
    }
    if (!head)
        printf("\n");
 
}
 
void insertL(void) {
    LinkList *head = (LinkList)malloc(sizeof(LinkList));
    for (int i = 0; i < 10; i++) {
       LinkList tmp = (LinkList)malloc(sizeof(LinkList));
        tmp->data = i + 1;
        tmp->next = NULL;
        if (i < 5) {
             InsertBack(head, head,tmp);
              PrintList(head);
         }
        else {
            InsertFront(head,tmp);
            PrintList(head);
        }
    }
    PrintList(head);
    PrintListReverse(head);
    printf("\n");
    LinkList rp = revert0(head);
    PrintList(rp);
    printf("\n");
    LinkList rp1 = revert1(rp);
    PrintList(rp1);
 
    DeleteAll(rp1);
}
 
int main(int argc , char *argv []){
 
    insertL();
}

头插法和尾插法详解

头插法
核心代码：
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
————————————————