单链表的几类操作介绍(头结点没有数据)

1.定义一个单链表的结构体

typedef struct _Node { int data; struct _Node *next; }node;

2.创建一个链表，这里分为头插法和尾插法

node *CreatNode_Head(int n) { int i=0; node *head,*p; head=(node*)malloc(sizeof(node)); if(head==NULL) return NULL; head->next=NULL; srand(time(0)); for(int i=0;i<n;++i) { p=(node*)malloc(sizeof(node)); p->data=rand()0+1; printf("p->data:%d\t",p->data); p->next=head->next; head->next=p; } return head; } node *CreatNode_Tail(int n) { int i=0; node *head,*p,*q; head=(node*)malloc(sizeof(node)); if(head==NULL) return NULL; head->next=NULL; q=head; srand(time(0)); for(int i=0;i<n;++i) { p=(node*)malloc(sizeof(node)); p->data=rand()0+1; p->next=NULL; printf("p->data:%d\t",p->data); q->next=p; q=p; } return head; }

3.获取链表的长度

由于头结点没有数据，所以循环从头结点->next开始遍历，直到遇到NULL为止。最后返回链表的长度

int length(node *p) { if(p==NULL) return -1; int len=0; while(p->next!=NULL) { len++; p=p->next; } return len; }

4.打印链表中存储的数据

这个其实和获取链表的长度一样的道理，都是需要遍历链表，但是在遍历前需要判断链表是否为空，若为空，立即返回，不为空开始遍历，直到遇到NULL为止。

void printnode(node *p) { if(p==NULL) return; node *q; if(p->next==NULL) { printf("the node is empty:\n"); return; } else { q=p->next; while(q!=NULL) { printf("%d\t",q->data); q=q->next; } } printf("\n"); }

5.链表的定位

   链表的定位返回值分两种，一种可以返回定位到某个节点的数据，另一种是返回以此节点的地址

   两个函数传入的参数都是一样，一个参数是需要操作的链表，另一个参数是节点在链表中的位置

int SearchNode(node *head,int pos) { if(head==NULL) return -1; if(pos<=0) { printf("the pos can not smaller than 0\n"); return -1; } else if(head->next==NULL) { printf("the node is empty\n"); return -1; } else if(pos>length(head)) { printf("the pos over the length of the node\n"); return -1; } else { while(pos--) { head=head->next; } } return head->data; } node * SearchNode1(node *head,int pos) { if(pos<0) { printf("the pos can not smaller than 0\n"); return NULL; } else if(head->next==NULL) { printf("the node is empty\n"); return NULL; } else if(pos>length(head)) { printf("the pos over the length of the node\n"); return NULL; } else { while(pos--) { head=head->next; } } return head; }

6.删除链表中的节点

   先找到要删除节点的前一个节点，如果已经到了尾节点，则不能删除

bool DeleteNode(node *head,int pos,int &data) { if(head==NULL) return false; node *item=NULL; node *p=head; node *q=SearchNode1(head,pos-1); if((!q)||(!q->next)) { printf("delete failed:\n"); return false; } item=q->next; data=item->data; q->next=item->next; free(item); item=NULL; printf("Delete success:\n"); return true; }

7.插入节点

先找到要插入节点的前一个节点

bool InsertNode(node *head,int pos,int data) { if(head==NULL) return false; node *item=NULL; node *p=head; node *q=SearchNode1(head,pos-1); if(!q) { printf("Insert failed:\n"); return false; } item=(node*)malloc(sizeof(node)); item->data=data; item->next=q->next; q->next=item; printf("Insert success:\n"); return true; }

8.逆置操作

void ReverseNode(node *head) { if(head==NULL) return ; if(head->next==NULL) return ; node *p,*q,*r; p=head->next; q=p->next; p->next=NULL; while(q!=NULL) { r=q->next; q->next=p; p=q; q=r; } head->next=p; }

完整程序如下：

#include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> typedef struct _Node { int data; struct _Node *next; }node; node *CreatNode_Head(int n) { int i=0; node *head,*p; head=(node*)malloc(sizeof(node)); if(head==NULL) return NULL; head->next=NULL; srand(time(0)); for(int i=0;i<n;++i) { p=(node*)malloc(sizeof(node)); p->data=rand()0+1; printf("p->data:%d\t",p->data); p->next=head->next; head->next=p; } return head; } node *CreatNode_Tail(int n) { int i=0; node *head,*p,*q; head=(node*)malloc(sizeof(node)); if(head==NULL) return NULL; head->next=NULL; q=head; srand(time(0)); for(int i=0;i<n;++i) { p=(node*)malloc(sizeof(node)); p->data=rand()0+1; p->next=NULL; printf("p->data:%d\t",p->data); q->next=p; q=p; } return head; } int length(node *p) { if(p==NULL) return -1; int len=0; while(p->next!=NULL) { len++; p=p->next; } return len; } void printnode(node *p) { if(p==NULL) return; node *q; if(p->next==NULL) { printf("the node is empty:\n"); return; } else { q=p->next; while(q!=NULL) { printf("%d\t",q->data); q=q->next; } } printf("\n"); } int SearchNode(node *head,int pos) { if(head==NULL) return -1; if(pos<=0) { printf("the pos can not smaller than 0\n"); return -1; } else if(head->next==NULL) { printf("the node is empty\n"); return -1; } else if(pos>length(head)) { printf("the pos over the length of the node\n"); return -1; } else { while(pos--) { head=head->next; } } return head->data; } node * SearchNode1(node *head,int pos) { if(pos<0) { printf("the pos can not smaller than 0\n"); return NULL; } else if(head->next==NULL) { printf("the node is empty\n"); return NULL; } else if(pos>length(head)) { printf("the pos over the length of the node\n"); return NULL; } else { while(pos--) { head=head->next; } } return head; } bool DeleteNode(node *head,int pos,int &data) { if(head==NULL) return false; node *item=NULL; node *p=head; node *q=SearchNode1(head,pos-1); if((!q)||(!q->next)) { printf("delete failed:\n"); return false; } item=q->next; data=item->data; q->next=item->next; free(item); item=NULL; printf("Delete success:\n"); return true; } bool InsertNode(node *head,int pos,int data) { if(head==NULL) return false; node *item=NULL; node *p=head; node *q=SearchNode1(head,pos-1); if(!q) { printf("Insert failed:\n"); return false; } item=(node*)malloc(sizeof(node)); item->data=data; item->next=q->next; q->next=item; printf("Insert success:\n"); return true; } void ReverseNode(node *head) { if(head==NULL) return ; if(head->next==NULL) return ; node *p,*q,*r; p=head->next; q=p->next; p->next=NULL; while(q!=NULL) { r=q->next; q->next=p; p=q; q=r; } head->next=p; } int main() { int len=0; node *head,*head1; node *head2=NULL; printf("please input some date and creat a node\n"); head=CreatNode_Head(10); printnode(head); printf("the length of the list is:%d\n",length(head)); head1=CreatNode_Tail(10); printnode(head1); printf("the length of the list is:%d\n",length(head1)); for(int i=0;i<length(head1);i++) { printf("SearchNode:index:%d,data:%d\n",i+1,SearchNode(head1,i+1)); printnode(SearchNode1(head1,i+1)); } InsertNode(head1,1,101); printnode(head1); InsertNode(head1,13,102); printnode(head1); int data=0; DeleteNode(head1,1,data); printf("the data is:%d\n",data); printnode(head1); DeleteNode(head1,12,data); printf("the data is:%d\n",data); printnode(head1); ReverseNode(head1); printnode(head1); return 0; }