下图就是最简单最一般的单向链表：
还有这种：
多一个Tail指针，好处就是能很方便地找到末尾。
留一个终始标志，这个节点作为一个标志，不用于存储数据，链表末尾指向这个节点，形成一个“环形链表”，这样无论在链表的哪里插入新的元素，操作都一致了，不必判断头和尾的特殊性。数组的好处就是链表的坏处，数组的坏处就是链表的好处，链表插入删除方便，遍历麻烦；数组遍历方便，插入删除都要移动。
因为需要从头开始找，没办法像数组那样直接跳到那个地址。而插入元素，就比数组方便了，如果你已经得知了要插入的地址的话，不过还要注意哦，是“后插入”（Insert After）：
有“后插入”，那就有“前插入”（Insert Before），两者对单向链表来说真的不一样，下图描述了“前插入”：
由于指针向后不向前，我们不知道要插入位置的前一个节点是什么，只能从头找，所以比较麻烦。
#include <stdio.h>struct node{ int data; struct node *next;};typedef struct node Node;#define SIZE sizeof(Node)//创建节点Node* creteNode(int d){ Node* pn=malloc(SIZE); pn->data=d; pn->next=NULL; return pn;}//创建链表void creatList(Node** h){ Node* pn=NULL; Node* p=NULL; int d; PRintf("请输入数据/n"); scanf("%d",&d); pn=creteNode(d); *h=pn; p=*h; while(1) { printf("请输入数据/n"); scanf("%d",&d); if(d==0) break; pn=creteNode(d); p->next=pn; p=p->next; }}这就是上面函数创建的
createNode函数创建一个个的节点，createList将一个个节点串起来。//查找某个节点的位置Node* findNode(Node* h,int n){ int i; if((h==NULL)||(n<0)) { printf("查找位置不合法||链表为空！/n"); return NULL; } if(n==1) { return h; } for(i=1;i<=n;i++) { h=h->next; if(h==NULL) break; } return h;}findNode函数是为了查找某个节点，在插入和删除时使用这个函数方便。//末尾增加一个新的节点int addBack(int d,Node* h){ Node *pn=NULL; pn=creteNode(d); Node* p=h; while(p->next) { p=p->next; } p->next=pn; pn->next=NULL;}
在末尾插入一个节点，先要遍历到最后一个节点，然后将新节点放在后面。//头插法int addFont(int d,Node** h)//修改头节点 传入二级指针{ Node* pn=NULL; pn=creteNode(d); pn->next=*h; *h=pn;}同尾插法一样，在头节点位置插入一个元素。只是不需要遍历。//插入int insertNode(int n,int d,Node** h)//在n位置插入d{ if((n<1)||(*h==NULL)) { printf("插入位置不合法||链表为空!/n"); return 0; } Node* pn=creteNode(d);//创建新的节点 //插入位置为1，即插入头节点的位置 if(n==1) { Node* pn=NULL; pn=creteNode(d); pn->next=*h; *h=pn; return 0; } else { Node* pf=findNode(h,n-1); //得到插入位置的前一个节点 pn->next=pf->next; pf->next=pn; return 1; }}
首先我们用findNode函数找到插入位置的前一个节点，插入的时候要记得先要断开以前的连接，删除也是的，先要断开连接再进行操作。//删除第n个位置的元素int deleteNode(int n,Node** h){ //判断头节点是否为空，位置是不是合法 if((*h==NULL)||(n<1)) { printf("删除的链表为空||删除的位置不合法！/n"); return 0; } Node* pd=NULL; //判断是否只有一个头节点 if(((*h)->next)==NULL) { printf("只用一个节点/n"); return 0; } //删除头节点 if(n==1) { pd=*h; *h=pd->next; free(pd); pd=NULL; return 1; } //删除 //判断节点是否存在 if(NULL==findNode(*h,n-1)) { printf("删除节点不存在/n"); return 0; } //找到要删除的节点的前一个节点 Node* pf=findNode(*h,n-1); pd=pf->next;//将要删除的节点的给pd pf->next=pd->next; free(pd); pd=NULL; pf=NULL; return 1;}
也是用findNode函数找到前一个节点的位置，然后先断开删除节点位置和后面一个节点的位置。
//打印链表void print(Node* h){ printf("list:/n"); while(h) { printf("%d ",h->data); h=h->next; } printf("/n");}int main(){ Node* head=NULL; creatList(&head); print(head); Node* p=findNode(head,0); printf("%d/n",p->data); deleteNode(2,&head); print(head); return 0;}
新闻热点
疑难解答
