第四周项目四建设双链表算法库

1.头文件：dlinklist.h，包含定义双链表数据结构的代码、宏定义、要实现算法的函数的声明；

#ifndef DLINKLIST_H_INCLUDED#define DLINKLIST_H_INCLUDEDtypedef int ElemType;typedef struct DNode//定义双链表结点类型{ElemType data;struct DNode *prior; //指向前驱结点struct DNode *next;//指向后继结点} DLinkList;void CreateListF(DLinkList *&L,ElemType a[],int n);//头插法建双链表void CreateListR(DLinkList *&L,ElemType a[],int n);//尾插法建双链表void InitList(DLinkList *&L); //初始化双链表void DestroyList(DLinkList *&L); //销毁双链表bool ListEmpty(DLinkList *L); //判断链表是否为空int ListLength(DLinkList *L); //求链表的长度void DispList(DLinkList *L); //输出链表bool GetElem(DLinkList *L,int i,ElemType &e); //获取节点的值int LocateElem(DLinkList *L,ElemType e); //查找一个节点bool ListInsert(DLinkList *&L,int i,ElemType e) ;//插入一个节点bool ListDelete(DLinkList *&L,int i,ElemType &e); //删除一个节点#endif // DLINKLIST_H_INCLUDED

2.源文件：linklist.cpp，，包含实现各种算法的函数的定义

#include <stdio.h>#include <malloc.h>#include "dlinklist.h"void CreateListF(DLinkList *&L,ElemType a[],int n)//头插法建双链表{DLinkList *s;int i;L=(DLinkList *)malloc(sizeof(DLinkList)); //创建头结点L->prior=L->next=NULL;for (i=0; i<n; i++){s=(DLinkList *)malloc(sizeof(DLinkList));//创建新结点s->data=a[i];s->next=L->next;//将*s插在原开始结点之前,头结点之后if (L->next!=NULL) L->next->prior=s;L->next=s;s->prior=L;}}void CreateListR(DLinkList *&L,ElemType a[],int n)//尾插法建双链表{DLinkList *s,*r;int i;L=(DLinkList *)malloc(sizeof(DLinkList)); //创建头结点L->prior=L->next=NULL;r=L;//r始终指向终端结点,开始时指向头结点for (i=0; i<n; i++){s=(DLinkList *)malloc(sizeof(DLinkList));//创建新结点s->data=a[i];r->next=s;s->prior=r; //将*s插入*r之后r=s;}r->next=NULL;//终端结点next域置为NULL}void InitList(DLinkList *&L){L=(DLinkList *)malloc(sizeof(DLinkList)); //创建头结点L->prior=L->next=NULL;}void DestroyList(DLinkList *&L){DLinkList *p=L,*q=p->next;while (q!=NULL){free(p);p=q;q=p->next;}free(p);}bool ListEmpty(DLinkList *L){return(L->next==NULL);}int ListLength(DLinkList *L){DLinkList *p=L;int i=0;while (p->next!=NULL){i++;p=p->next;}return(i);}void DispList(DLinkList *L){DLinkList *p=L->next;while (p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}bool GetElem(DLinkList *L,int i,ElemType &e){int j=0;DLinkList *p=L;while (j<i && p!=NULL){j++;p=p->next;}if (p==NULL)return false;else{e=p->data;return true;}}int LocateElem(DLinkList *L,ElemType e){int n=1;DLinkList *p=L->next;while (p!=NULL && p->data!=e){n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);}bool ListInsert(DLinkList *&L,int i,ElemType e){int j=0;DLinkList *p=L,*s;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL) //未找到第i-1个结点return false;else//找到第i-1个结点*p{s=(DLinkList *)malloc(sizeof(DLinkList)); //创建新结点*ss->data=e;s->next=p->next;//将*s插入到*p之后if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return true;}}bool ListDelete(DLinkList *&L,int i,ElemType &e){int j=0;DLinkList *p=L,*q;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL)//未找到第i-1个结点return false;else//找到第i-1个结点*p{q=p->next;//q指向要删除的结点if (q==NULL)return false;//不存在第i个结点e=q->data;p->next=q->next;//从单链表中删除*q结点if (p->next!=NULL) p->next->prior=p;free(q);//释放*q结点return true;}}

3.在建立算法库过程中，为了完成测试，再同一项目（project）中建立一个源文件(如main.cpp)，编制main函数，完成相关的测试工作。测试工作可以采用“渐进”的思路，每次涉及的函数应该尽可能少。

#include <stdio.h>#include "dlinklist.h"int main(){DLinkList *A;ElemType a[]= {1, 3, 2, 9, 0, 4, 5 ,6, 7, 8};InitList(A);CreateListF(A, a, 10);printf("length: %d\n", ListLength(A));ListInsert(A, 4, 12);printf("After Insert: ");DispList(A);DestroyList(A);return 0;}

运行结果：

知识点总结：

学会了如何建立双链表算法库。

学习心得：

在长时间练习下，我觉得编程越来越得心应手了。

当一个人真正觉悟的一刻，他放弃追寻外在世界的财富，而开始追寻他内心世界的真正财富

相关文章：

你感兴趣的文章：

标签云：