| 单向链表和双向链表的原理及其相关实现 | 您所在的位置：网站首页 › 链表实例中的常见问题及特点 › 单向链表和双向链表的原理及其相关实现 |
单向链表和双向链表的原理及其相关实现
|
其实要解决一个问题得从以下几个方面入手？即在日常生活中的几大“w”，链表是什么？它有什么作用？怎么实现？在日常生活中有哪些实际应用？只要解决了这些问题，那么链表这个问题就会很清晰明了了。 （一）什么是链表？ 链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。 所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。 1、那么先从单向链表着手，先看看单向链表的模拟图：
单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。 2、双向链表：
从上图可以很清晰的看出，每个节点有2个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空值或空列表），另一个则指向后一个节点（当此链接为最后一个链接时，指向的是空值或空列表）。意思就是说双向链表有2个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针。 3、循环链表：
循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点，反之亦然。 参考：http://zh.wikipedia.org/wiki/链表 （二）链表有什么作用？ 链表本质上就是一种数据结构，主要用来动态放置数据。也可用来构建许多数据结构，比如堆栈、队列及它们的派生。 （三）链表的实现？ 1、单向链表的实现 （1）单向链表的创建过程： 第一步：定义节点的数据结构； 第二步：创建一个空表。 第三步：利用malloc（）向系统申请分配一个节点。 第四步：将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点连接到表尾。 第五步：判断是否有后续节点，如有则转入第三步，否则结束。 （2）单向链表的输出过程： 第一步：找到表头。 第二步：若为非空表，则输出节点的值成员，是空表则退出。 第三步：跟踪链表，找到下一节点的地址。 第四步：转到第二步。 #include #include struct date//申明结构体 { char str; date *prior; date *next;//用来指向下一个结构体指针 }; int main() { date *pS,*pE,*head;//定义三个结构体指针,head用来保存链头,pE保存链尾 date *Rhead = NULL;//定义读取结构体指针 pE = head;//刚开始没有任何结点,指向表头 char temp; scanf("%c",&temp); if(temp != '#') { head = new date;//新建结点 head->str = temp;//给新结点赋值数据 head->prior = NULL; head->next = NULL; pS = head; } scanf("%c",&temp); while (temp != '#') { pS = new date;//新建结点 pS->str = temp;//给新结点赋值数据 pS->prior = pE; pS->next = NULL;//让指向下一个为空(新结点,也就是新链尾) pE->next = pS;//把新结点连接到链尾 pE = pS;//新结点成为了新的链尾 } printf("\n刚才输入的是:\n"); Rhead = head;//取得链头 /* 当然也可以直接用head不过这样就会改变其值,而无法再次查找链表 切忌链头的重要性,只要找不到链头,整条链表就没用! */ while (Rhead != NULL)//循环到链尾 { printf("%c",Rhead->str); if (Rhead!=NULL) { Rhead = Rhead->next;//让其指向下一个链表 } } printf("\n"); getch(); return 0; } 以上程序代码参考http://blog.csdn.net/duke56/article/details/5764614，比起其他实现，这个很直观明了。2、双向链表的实现 #include"stdio.h" #include"stdlib.h" typedef int DataType;//双向链表中数据的类型 typedef struct DNode { DataType element; struct DNode *prior,*next; }DNode,*DoubleList;//定义双向链表中一个节点 DoubleList createDList()//创建双向链表 { DoubleList head,p1,p2; DataType data; scanf("%d",&data); if(data!=0)//初始化头结点 { head=(DoubleList)malloc(sizeof(DNode)); head->element=data; // head head->prior=NULL; //---------------------- head->next=NULL; //|prior| data | next | p1=head; // ----------------------- } // p1 else { return NULL;//如果是0的话，直接跳出去，后面的工作一律不再进行 } scanf("%d",&data); while(data!=0) { // head p2 p2=(DoubleList)malloc(sizeof(DNode));//----------------- ----------------- p2->element=data; //|prior|data|next|-->|prior|data|next| p2->prior=p1; //----------------- ----------------- p2->next=NULL; // p1 p1->next=p2; p1=p2; scanf("%d",&data); //其实p1的作用就是为了把后面的 } //节点依次连接到双向链表的尾部 return head; } DoubleList delDList(DoubleList head,DataType data)//删除链表某个节点，该节点的值等于data { DoubleList p; if(head==NULL) { return NULL; } if(data==0) { printf("please input the data which will be deleted!\n"); scanf("%d",&data); } p=head;//让p指向头结点，p在双向链表上移动，完成相应的操作 while(p!=NULL&& p->element!=data)//用p->element!=data而不是p->element=data， { //是想让p在循环的控制下，在双向链表上不断移动 p=p->next; } if(p!=NULL) { if(p==head)//如果第一次的时候就跳出来的话，p肯定指向的是head { head=p->next;//删除头结点 head->prior=NULL; free(p); } else { if(p->next==NULL)//已经找到最后一个节点了才找到 { (p->prior)->next=NULL; free(p); } else //中间某个节点上找到了要删除的节点 { p->prior->next=p->next; //语句1 1和2次序很关键，绝对不能颠倒 p->next->prior=p->prior;//语句2 free(p); } } } else { printf("we can not find the element that you want to find!\n"); } return head; } void printDList(DoubleList head) { DoubleList p=head; while(p!=NULL) { printf("%d\t",p->element); p=p->next; } printf("\n"); } void freeDList(DoubleList head) { DoubleList p; if(head==NULL) { return; } while(head!=NULL) { p=head->next; free(head); head=p; } } int main(void) { DoubleList head; printf("please input the interge,and create the Doublelist! \n"); head=createDList(); printf("print the Doublelist you have created!\n"); printDList(head); printf("delete the Doublelist!\n"); head=delDList(head,0);//delDList()函数有返回值 printf("print the Doublelist you have deleted!\n"); printDList(head); freeDList(head); }以上经Cfree5验证通过了的。
|
【本文地址】