一、基础知识：链表（线性表的链式存储结构）

（1）特点：逻辑关系相邻，物理位置不一定相邻。

（2）分类：

a.不带头节点

b.带头节点

（3）单链表的存储结构：

typedefstructSListNode{DataTypedata;structSListNode*next;}SListNode;

二、代码实现(因避开使用二级指针，所以代码中使用了c++中的引用)：此处构造的为不带头节点的链表

(1)sList.h

#pragmaoncetypedefintDataType;typedefstructSListNode{DataTypedata;structSListNode*next;}SListNode;voidPushBack(SListNode*&pHead,DataTyped);voidPopBack(SListNode*&pHead);voidPushFront(SListNode*&pHead,DataTyped);voidPopFront(SListNode*&pHead);voidPrintList(SListNode*pHead);SListNode*Find(SListNode*&pHead,DataTyped);voidInsert(SListNode*&pos,DataTyped);

(2)sList.cpp

#include<stdio.h>#include<malloc.h>#include<assert.h>#include"sList.h"SListNode*MakeNode(DataTyped){SListNode*tmp=(SListNode*)malloc(sizeof(SListNode));tmp->data=d;tmp->next=NULL;returntmp;}voidPushBack(SListNode*&pHead,DataTyped){//1.空//2.不空if(pHead==NULL){pHead=MakeNode(d);}else{//先找尾，再插入新节点SListNode*tail=pHead;while(tail->next!=NULL){tail=tail->next;}tail->next=MakeNode(d);}}voidPopBack(SListNode*&pHead){//1.空//2.一个节点//3.多个节点if(pHead==NULL){return;}elseif(pHead->next==NULL){free(pHead);pHead=NULL;}else{SListNode*tail=pHead;SListNode*prev=NULL;while(tail->next!=NULL){prev=tail;tail=tail->next;}prev->next=NULL;free(tail);}}voidPushFront(SListNode*&pHead,DataTyped){if(pHead==NULL){pHead=MakeNode(d);}else{SListNode*tmp=pHead;pHead=MakeNode(d);pHead->next=tmp;}}voidPopFront(SListNode*&pHead){if(!pHead){printf("Listisempty!");return;}else{SListNode*tmp=pHead;pHead=pHead->next;free(tmp);}}SListNode*Find(SListNode*&pHead,DataTyped){SListNode*find=pHead;while(find){if(find->data==d)returnfind;find=find->next;}returnNULL;}voidInsert(SListNode*&pos,DataTyped){assert(pos);/*方法一：SListNode*tmp=MakeNode(d);tmp->next=pos->next;pos->next=tmp;*///方法二：SListNode*next=pos->next;pos->next=MakeNode(d);pos->next->next=next;}voidErase(SListNode*&pHead,SListNode*&pos){assert(pos&&pHead);SListNode*prev=pHead;while(prev->next!=pos){prev=prev->next;}prev->next=pos->next;free(pos);pos=NULL;}voidPrintList(SListNode*pHead){SListNode*tmp=pHead;while(tmp){printf("%d->",tmp->data);tmp=tmp->next;}printf("NULL\n");

（3）test.cpp

#include"sList.h"#include<stdio.h>#include<stdlib.h>voidtest1(){//不带头节点SListNode*list=NULL;PushBack(list,1);PushBack(list,2);PushBack(list,3);PushBack(list,4);//PushFront(list,0);//PopFront(list);//PopBack(list);SListNode*ret=Find(list,2);if(ret==NULL){printf("NoExist!\n");return;}//Insert(ret,4);Erase(list,ret);PrintList(list);}intmain(){test1();system("pause");return0;