1987人阅读
算法设计（79）
& & & &我在之前一篇博客中《》中详细实现了不带头尾节点的双向非循环链表的很多操作。其实同单链表一样，不带头结点的链表很多操作都是比较麻烦的，常常需要对第一个节点做额外的判断，提高了出错的成本。今天我们要来实现带头结点尾结点的双向非循环链表的操作，虽然额外维护了两个节点，但是操作的简便性大大提高了。代码上传至 & 。（1）定义带头结点尾结点的非循环双向链表的节点类型typedef int elemT
typedef struct NodeList{
struct NodeList *
struct NodeList *
}N（2）初始化双链表//1.初始化带头结点和尾结点的非循环双向链表
void InitialList(Node **pHead,Node **pTail){
*pHead = (Node *)malloc(sizeof(Node));
*pTail = (Node *)malloc(sizeof(Node));
if (*pHead == NULL || *pTail == NULL) {
printf(&%s函数执行，内存分配失败，初始化双链表失败\n&,__FUNCTION__);
//这个里面是关键，也是判空的重要条件
(*pHead)-&prior = NULL;
(*pTail)-&next = NULL;
//链表为空的时候把头结点和尾结点连起来
(*pHead)-&next = *pT
(*pTail)-&prior = *pH
printf(&%s函数执行，带头结点和尾节点的双向非循环链表初始化成功\n&,__FUNCTION__);
}（3）尾插法创建双链表//2.创建带头结点和尾结点的双向非循环链表
void CreateList(Node *pHead,Node *pTail){
pInsert = (Node*)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert-&prior = NULL;
pInsert-&next = NULL;
scanf(&%d&,&(pInsert-&element));
pMove = pH
while (pInsert-&element & 0) {
pMove-&next = pI
pInsert-&prior = pM
pInsert-&next = pT
pTail-&prior = pI
pMove = pI
pInsert = (Node *)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert-&prior = NULL;
pInsert-&next = NULL;
scanf(&%d&,&(pInsert-&element));
printf(&%s函数执行完成，带头节点和尾结点的双向非循环链表创建成功\n&,__FUNCTION__);
}（4）正序打印链表//3.正序打印链表
void PrintList(Node *pHead,Node *pTail){
pMove = pHead-&
while (pMove != pTail) {
printf(&%d &,pMove-&element);
pMove = pMove-&
printf(&\n%s函数执行，正序打印带头结点尾结点的双向非循环链表创建成功\n&,__FUNCTION__);
}（5）逆序打印链表//4.逆序打印链表
void PrintReverseList(Node *pHead,Node *pTail){
pMove = pTail-&
while (pMove != pHead) {
printf(&%d &,pMove-&element);
pMove = pMove-&
printf(&\n%s函数执行，逆序打印带头结点尾结点的双向非循环链表创建成功\n&,__FUNCTION__);
}（6）清空节点，使成为空表//5.清除链表中的所有元素，使成为空表
void ClearList(Node *pHead,Node *pTail){
pMove = pHead-&
while (pMove != pTail) {
pHead-&next = pMove-&
pMove-&next-&prior = pH
free(pMove);
pMove = pHead-&
printf(&%s函数执行，双向非循环链表清空成功\n&,__FUNCTION__);
}（7）计算链表长度//6.计算链表的长度
int SizeList(Node *pHead,Node *pTail){
int i = 0;
pMove = pHead-&
while (pMove != pTail) {
pMove = pMove-&
printf(&%s函数执行，链表的长度为%d\n&,__FUNCTION__,i);
}（8）判断链表是否为空//7.判断带头结点尾结点的双向非循环链表是否为空,为空返回1，否则返回0
int IsEmptyList(Node *pHead,Node *pTail){
if (pHead-&next == pTail) {
printf(&%s函数执行，当前链表为空\n&,__FUNCTION__);
printf(&%s函数执行，当前链表不为空\n&,__FUNCTION__);
}（9）返回链表中pos位置的元素//8.返回链表中第pos个结点中的元素，若返回-1，表示没有找到
int GetElement(Node *pHead,Node *pTail,int pos){
int i = 1;
pMove = pHead-&
while (pMove != pTail) {
if (i == pos) {
printf(&%s函数执行，第pos=%d位置的元素为%d\n&,__FUNCTION__,pos,pMove-&element);
return pMove-&
pMove = pMove-&
printf(&%s函数执行，查找第pos=%d位置元素失败\n&,__FUNCTION__,pos);
return -1;
}（10）查找值为x的节点，如果存在则返回地址//9.从链表中查找给定值x的第一个元素，并返回data域的内存地址，否则返回NULL
int *GetElemAddr(Node *pHead,Node *pTail,int x){
pMove = pHead-&
while (pMove != pTail) {
if (pMove-&element == x) {
printf(&%s函数执行，值为%d的元素内存地址为0x%x\n&,__FUNCTION__,x,&(pMove-&element));
return &(pMove-&element);
pMove = pMove-&
printf(&%s函数执行，查找值为%d的元素地址失败\n&,__FUNCTION__,x);
return NULL;
}（11）把pos节点的值改为x//10.把链表中第pos个节点的值修改为x
int ModifyElem(Node *pHead,Node *pTail,int pos,int x){
int i = 1;
pMove = pHead-&
while (pMove != pTail) {
if (i == pos) {
pMove-&element =
printf(&%s函数执行，修改pos=%d位置值为%d成功\n&,__FUNCTION__,pos,x);
pMove = pMove-&
printf(&%s函数执行，修改pos=%d位置元素失败\n&,__FUNCTION__,pos);
return -1;
}（12）表头插入一个元素//11.向链表的表头插入一个元素
int InsertHeadList(Node *pHead,Node *pTail,int x){
pInsert = (Node *)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert-&element =
pInsert-&prior = NULL;
pInsert-&next = NULL;
pInsert-&next = pHead-&
pHead-&next-&prior = pI
pHead-&next = pI
pInsert-&prior = pH
printf(&%s函数执行，在表头插入%d成功\n&,__FUNCTION__,x);
}（13）表尾插入一个元素//12.向链表的表尾插入一个元素
int InsertTailList(Node *pHead,Node *pTail,int x){
pInsert = (Node *)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert-&element =
pInsert-&prior = NULL;
pInsert-&next = NULL;
pTail-&prior-&next = pI
pInsert-&prior = pTail-&
pInsert-&next = pT
pTail-&prior = pI
printf(&%s函数执行，在表尾插入%d成功\n&,__FUNCTION__,x);
}（14）测试代码int main(int argc, const char * argv[]) {
Node *pH//头结点
Node *pT//尾结点
InitialList(&pHead, &pTail);
CreateList(pHead, pTail);
PrintList(pHead, pTail);
PrintReverseList(pHead,pTail);
SizeList(pHead, pTail);
IsEmptyList(pHead,pTail);
GetElement(pHead, pTail, 2);
GetElemAddr(pHead, pTail, 5);
ModifyElem(pHead, pTail, 2, 111);
PrintList(pHead, pTail);
InsertHeadList(pHead,pTail,100);
PrintList(pHead, pTail);
InsertTailList(pHead,pTail,900);
PrintList(pHead, pTail);
ClearList(pHead,pTail);
PrintList(pHead, pTail);
IsEmptyList(pHead,pTail);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1681582次
积分：23348
积分：23348
排名：第283名
原创：623篇
转载：36篇
评论：476条
文章：19篇
阅读：56670
文章：19篇
阅读：35162
文章：11篇
阅读：15572
阅读：40772
文章：60篇
阅读：113630
文章：79篇
阅读：186992
文章：220篇
阅读：681509
文章：51篇
阅读：173650
Android应用：
Github主页:
(1)(7)(10)(7)(5)(4)(7)(7)(5)(15)(4)(8)(10)(4)(24)(29)(10)(22)(33)(106)(130)(79)(132)3165人阅读
算法设计（79）
& & & &链表在数据结构和算法中的重要性不言而喻。这里我们要用C来实现链表（单链表）中的基本操作。对于链表的基本概念请参考《》这篇博客。示例代码上传至 &。在本案例中的单链表，都是没有头结点的，头指针直接指向第一个节点。带头结点的实例我会在之后进行讲解。（1）定义单链表的节点类型typedef int elemT
// 定义单链表结点类型
typedef struct ListNode{
struct ListNode *
}N（2）初始化线性表// 1.初始化线性表，即置单链表的表头指针为空
void initList(Node *pNode){
pNode = NULL;
printf(&%s函数执行，初始化成功\n&,__FUNCTION__);
}当声明一个头结点后，把该头结点设置为空，即把数据域和地址域都设为空，即可完成该链表的初始化。（3）创建线性表// 2.创建线性表，此函数输入负数终止读取数据
Node *creatList(Node *pHead){
Node *p1;//表头节点，始终指向头结点
Node *p2;//表尾节点，始终指向链表的最后一个元素
p1 = p2 = (Node *)malloc(sizeof(Node)); //申请新节点,分配空间
if(p1 == NULL || p2 == NULL){
printf(&内存分配失败\n&);
memset(p1,0,sizeof(Node));
scanf(&%d&,&p1-&element);
//输入新节点的值
p1-&next = NULL;
//新节点的指针置为空
while(p1-&element & 0){
//输入的值大于0则继续，直到输入的值为负
if(pHead == NULL){
//空表，接入表头
pHead = p1;
//直接把p1作为头结点，也可以理解为把pHead头结点指向p1
p2-&next = p1;
//非空表，接入表尾
//p1插入后，p1就是尾结点，所以p2要指向尾结点
p1 = (Node *)malloc(sizeof(Node));
//再重申请一个节点
if(p1 == NULL || p2 == NULL){
printf(&内存分配失败\n&);
memset(p1,0,sizeof(Node));
scanf(&%d&,&p1-&element);
p1-&next = NULL;
printf(&%s函数执行，链表创建成功\n&,__FUNCTION__);
//返回链表的头指针
}我这里使用手动的方式输入元素，直到输入0或者负数停止。（4）打印链表// 3.打印链表，链表的遍历
void printList(Node *pHead){
if(NULL == pHead){
//链表为空
printf(&%s函数执行，链表为空\n&,__FUNCTION__);
while(NULL != pHead){
printf(&%d &,pHead-&element);
pHead = pHead-&
printf(&\n&);
}使用地址域顺序打印即可。（5）清空链表// 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表
void clearList(Node *pHead){
//定义一个与pHead相邻节点,理解为当前节点的下一个节点
if(pHead == NULL){
printf(&%s函数执行，链表为空\n&,__FUNCTION__);
while(pHead-&next != NULL){
pNext = pHead-&//保存下一结点的指针
free(pHead);
//释放当前节点
pHead = pN
//指向下一个节点
printf(&%s函数执行，链表已经清除\n&,__FUNCTION__);
}想要检验是否清空成功，可以使用（4）中的链表打印检验即可。（6）计算链表长度// 5.返回单链表的长度
int sizeList(Node *pHead){
int size = 0;
while(pHead != NULL){
pHead = pHead-&
printf(&%s函数执行，链表长度 %d \n&,__FUNCTION__,size);
//链表的实际长度
}也就是计算有多少个节点。（7）判断链表是否为空// 6.检查单链表是否为空，若为空则返回１，否则返回０
int isEmptyList(Node *pHead){
if(pHead == NULL){
printf(&%s函数执行，链表为空\n&,__FUNCTION__);
printf(&%s函数执行，链表非空\n&,__FUNCTION__);
}（8）查找链表某个位置元素// 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行
void getElement(Node *pHead, int pos){
int i = 0;
if(pos & 1){
printf(&%s函数执行，pos值非法\n&,__FUNCTION__);
if(pHead == NULL){
printf(&%s函数执行，链表为空\n&,__FUNCTION__);
while(pHead != NULL){
if(i == pos){
pHead = pHead-&
//移到下一结点
if(i & pos){
//pos值超过链表长度
printf(&%s函数执行，pos值超出链表长度\n&,__FUNCTION__);
printf(&%s函数执行，位置 %d 中的元素为 %d\n&,__FUNCTION__,pos,pHead-&element);
}（9）返回某元素值在链表中的内存地址// 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL
elemType* getElemAddr(Node *pHead, elemType x){
if(NULL == pHead){
printf(&%s函数执行，链表为空\n&,__FUNCTION__);
return NULL;
while((pHead-&element != x) && (NULL != pHead-&next)) {//判断是否到链表末尾，以及是否存在所要找的元素
pHead = pHead-&
if((pHead-&element != x) && (pHead != NULL)){
//当到达最后一个节点
printf(&%s函数执行，在链表中未找到x值\n&,__FUNCTION__);
return NULL;
if(pHead-&element == x){
printf(&%s函数执行，元素 %d 的地址为 0x%x\n&,__FUNCTION__,x,&(pHead-&element));
return &(pHead-&element);//返回元素的地址
}（10）修改某个节点的值// 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０
int modifyElem(Node *pNode,int pos,elemType x){
int i = 0;
if(NULL == pNode){
printf(&%s函数执行，链表为空\n&,__FUNCTION__);
if(pos & 1){
printf(&%s函数执行，pos值非法\n&,__FUNCTION__);
while(pNode != NULL){
if(i == pos){
pNode = pNode-& //移到下一结点
if(i & pos) {
//pos值大于链表长度
printf(&%s函数执行，pos值超出链表长度\n&,__FUNCTION__);
pNode-&element =
printf(&%s函数执行\n&,__FUNCTION__);
}（11）表头插入一个节点// 10.向单链表的表头插入一个元素
int insertHeadList(Node **pNode,elemType insertElem){
pInsert = (Node *)malloc(sizeof(Node));
memset(pInsert,0,sizeof(Node));
pInsert-&element = insertE
pInsert-&next = *pN
*pNode = pI
//头节点*pNode指向刚插入的节点，注意和上一行代码的前后顺序；
printf(&%s函数执行，向表头插入元素成功\n&,__FUNCTION__);
}（12）表尾插入一个节点// 11.向单链表的末尾添加一个元素
int insertLastList(Node **pNode,elemType insertElem){
pHead = *pN
pInsert = (Node *)malloc(sizeof(Node)); //申请一个新节点
memset(pInsert,0,sizeof(Node));
pInsert-&element = insertE
while(pHead-&next != NULL){
pHead = pHead-&
pHead-&next = pI
//将链表末尾节点的下一结点指向新添加的节点
printf(&%s函数执行，向表尾插入元素成功\n&,__FUNCTION__);
（13）测试函数int main(int argc, const char * argv[]) {
//声明头结点
initList(pList);
//链表初始化
printList(pList);
//遍历链表，打印链表
pList = creatList(pList); //创建链表
printList(pList);
sizeList(pList);
//链表的长度
printList(pList);
isEmptyList(pList);
//判断链表是否为空链表
getElement(pList,3);
//获取第三个元素，如果元素不足3个，则返回0
printList(pList);
getElemAddr(pList,5);
//获得元素5的内存地址
modifyElem(pList,4,1);
//将链表中位置4上的元素修改为1
printList(pList);
insertHeadList(&pList,5);
//表头插入元素5
printList(pList);
insertLastList(&pList,10);
//表尾插入元素10
printList(pList);
clearList(pList);
//清空链表
printList(pList);
}本文参考：/renyuan/archive//3091506.html
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1681583次
积分：23348
积分：23348
排名：第283名
原创：623篇
转载：36篇
评论：476条
文章：19篇
阅读：56670
文章：19篇
阅读：35162
文章：11篇
阅读：15572
阅读：40772
文章：60篇
阅读：113630
文章：79篇
阅读：186992
文章：220篇
阅读：681509
文章：51篇
阅读：173650
Android应用：
Github主页:
(1)(7)(10)(7)(5)(4)(7)(7)(5)(15)(4)(8)(10)(4)(24)(29)(10)(22)(33)(106)(130)(79)(132)带头节点：head-& p1-&p2-&p3 -&p1-&p2-&p3-& p1.....不带头节点： p1-&p2-&p3 -&p1-&p2-&p3-& p1.....却别还不明显吗？带头节点可以方便，快速的定位第1个节点比如循环的时候，删除p1 的时候:head-&next = p2;p3-&next = head-& ok?free(p1);思路很清晰，开始的第1个节点现在就是head-&next 即 p2否则没有头节点:p3-&next = p1-&free(p1); 会不会有一种链表第1个节点到底是哪个的感觉？当然单向循环这个不明显，如果你写个双向循环，就会很方便，麻烦，我就写单向吧``就是方便，清晰，明了，也不是一定要用，要看情况，看需要对链表做什么操作，来决定要不要带头节点。你不写几个链表没法体会的。
在带头节点的单链表中,头指针只有一个域,即链指针,它指向头节点,头节点有两个域,一个是数据域,值为0&& (NULL),还有一个域,链指针,这个指针链指向单链表的第一个数据元素
&而在不带头节点的单链表中,头节点也只有一个链指针,但它指向单链表的第一个数据元素
什么时候要使用带头节点的单链表?
为了在第一个数据元素前面加入新元素或者删除第一个节点时头指针的值不变,在第一个数据前面要加一个所谓的头节点
带头结点初始化Node *& //声明头结点&&&&&
&void InitList(Node *head){&
head=(Node *)malloc( sizeof(Node));&
&head-&next=NULL;&
带头结点尾插入，统一操作。
&void CreatList(Node **head){&
&Node *r=*head,*s;&
while(scanf("%d",&a)){&
if(a!=0){&
s=(Node *)malloc(sizeof(Node));&
s-&value=a;&
r-&next=s;&
&r=s;&&&&&
&else{&&&&&
&r-&next=NULL;&
调用CreatList(&head);
void CreatList(Node *head){&
Node *r=head,*s;&
... //下面的都一样&
调用CreatList(head);
不带头结点初始化方式一：
void InitList(Node **head){&
*head=NULL;&
调用InitList(&head);
void InitList(Node *head){&
head=NULL;&
调用InitList(head);
不带头结点尾插入，第一个节点与其他节点分开操作。
void CreatList(Node& **head){&
Node *p,*t;&&&&&&&& /*p工作指针,t临时指针*/
int a,i=1;&
&while(scanf("%d",&a)){&
&if(a!=0){&
&t=(Node *)malloc(sizeof(Node));&
&t-&value=a;&
& if(i==1){&
*head=t;&&&&&
&& p-&next=t;&
&&& else{&&&&&
&&&& p-&next=NULL;&
&&&& i++;&
调用CreatList(&head);
两种初始化方法的区别不带头结点的单链表对于第一个节点的操作与其他节点不一样，需要特殊处理，这增加了程序的复杂性和出现bug的机会，因此，通常在单链表的开始结点之前附设一个头结点。 带头结点的单链表，初始时一定返回的是指向头结点的地址，所以一定要用二维指针，否则将导致内存访问失败或异常。 带头结点与不带头结点初始化、插入、删除、输出操作都不样，在遍历输出链表数据时，带头结点的判断条件是while(head-&next!=NULL)，而不带头结点是while(head!=NULL)，虽然头指针可以在初始时设定，但是如1所述，对于特殊情况如只有一个节点会出现问题。 为什么不带头结点初始化有2种方式，而带头结点只有1种方式呢？因为不带头结点声明Node *head 时，C编译器将其自动初始化为NULL，于是根本不需要调用InitList(head); 也即不带头结点的初始化是个伪操作。而带头结点的初始化在堆开辟了一段内存，需要修改head指针变量指向的地址(即head的值)，所以要修改head的值，必须传保存head变量的地址(即二维指针)。而直接调用CreatList(head);相当于传head变量的值，函数修改的是head的副本，无法真正改变head的值。
注：这里可以将head指针看成一个变量(不管它保存的是地址)，就比较好理解了。
这其实本质上还是传值，传址的问题，只不过指针本身保存的地址，让这个过程变得有点纠结。在函数调用需要修改指针变量的指向(value)时，应该传递指针变量的地址(address)。
另外，对于函数的形参是指针时，只要该参数不在左边（即都是右值操作），二维指针(形参)就可以简化为一维指针。如上面带头结点的尾插简化版本。
阅读(...) 评论()