单链表 |
您所在的位置：网站首页 › 初始化包括什么 › 单链表 |
单链表
|
文章目录
单链表的定义单链表上的操作初始化建立单链表头插法建立单链表尾插法建立单链表
遍历单链表求单链表的长度查找操作按值查找按位查找
插入操作删除操作判空操作
完整代码及实例
单链表的定义
由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。 单链表的特点： 单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。对于每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。 单链表中结点类型的描述： typedef struct LNode{ //定义单链表结点类型 int data; //数据域，可以是别的各种数据类型，本文统一用int类型 struct LNode *next; //指针域 }LNode, *LinkList; 单链表上的操作 初始化 通常会用头指针来标识一个单链表，头指针为NULL时表示一个空表。但是，为了操作方便，会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。如下图所示： 所谓头插法建立单链表是说将新结点插入到当前链表的表头，即头结点之后。如图所示：
实现代码： //头插法建立单链表 LinkList HeadInsert(LinkList &L){ InitList(L); //初始化 int x; cin>>x; while(x!=9999){ //输入9999表示结束 LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; cin>>x; } return L; }需要指出的是，头插法建立的单链表中结点的次序和输入数据的顺序不一致，是相反的。若希望两者的顺序是一致的，则可采用尾插法建立单链表。 尾插法建立单链表 所谓尾插法建立单链表，就是将新结点插入到当前链表的表尾。如下图所示： 实现代码： //尾插法建立单链表 LinkList TailInsert(LinkList &L){ InitList(L); LNode *s,*r=L; int x; cin>>x; while(x!=9999){ s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; cin>>x; } r->next = NULL; return L; } 遍历单链表算法思想：声明一个指针p，从头结点指向的第一个结点开始，如果p不为空，那么就输出当前结点的值，并将p指向下一个结点，直到遍历到最后一个结点为止。 实现代码： //遍历操作 void PrintList(LinkList L){ LNode *p = L->next; while(p){ cout len++; p = p->next; } return len; } 查找操作 按值查找查找值x在单链表L中的结点指针。 算法思想：从单链表的第一个结点开始，依次比较表中各个结点的数据域的值，若某结点数据域的值等于x，则返回该结点的指针；若整个单链表中没有这样的结点，则返回空。 实现代码： //按值查找：查找x在L中的位置 LNode *LocateElem(LinkList L, int x){ LNode *p = L->next; while(p && p->data != x){ p = p->next; } return p; } 按位查找查找单链表L中第 i 个位置的结点指针。 算法思想：从单链表的第一个结点开始，顺着指针域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点的指针域NULL。 实现代码： //按位查找：查找在单链表L中第i个位置的结点 LNode *GetElem(LinkList L, int i){ int j=1; LNode *p = L->next; if(i==0)return L; if(i LNode *p = GetElem(L,i-1); LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = p->next; p->next = s; } 删除操作将单链表的第 i 个结点删除。 算法思想：先检查删除位置的合法性，然后从头开始遍历，找到表中的第 i-1 个结点，即被删除结点的前驱结点*p，被删除结点为*q，修改*p的指针域，将其指向*q的下一个结点，最后再释放结点*q的存储空间。 实现代码： //删除操作:将单链表中的第i个结点删除 void Delete(LinkList &L, int i){ if(iLength(L)) cout cout int data; struct LNode *next; }LNode, *LinkList; //初始化 void InitList(LinkList &L){ L = (LNode *)malloc(sizeof(LinkList)); L->next = NULL; } //遍历操作 void PrintList(LinkList L){ LNode *p = L->next; while(p){ cout len++; p = p->next; } return len; } //头插法建立单链表 LinkList HeadInsert(LinkList &L){ InitList(L); //初始化 int x; cin>>x; while(x!=9999){ LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; cin>>x; } return L; } //尾插法建立单链表 LinkList TailInsert(LinkList &L){ InitList(L); LNode *s,*r=L; int x; cin>>x; while(x!=9999){ s = (LNode *)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; cin>>x; } r->next = NULL; return L; } //按值查找：查找x在L中的位置 LNode *LocateElem(LinkList L, int x){ LNode *p = L->next; while(p && p->data != x){ p = p->next; } return p; } //按位查找：查找在单链表L中第i个位置的结点 LNode *GetElem(LinkList L, int i){ int j=1; LNode *p = L->next; if(i==0)return L; if(i LNode *p = GetElem(L,i-1); LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = p->next; p->next = s; } //删除操作:将单链表中的第i个结点删除 void Delete(LinkList &L, int i){ if(iLength(L)){ cout |
头结点和头指针的区分：不管带不带头结点，头指针始终指向单链表的第一个结点，而头结点是带头结点的单链表中的第一个结点，结点内通常不存储信息。 那么单链表的初始化操作就是申请一个头结点，将指针域置空。
算法思想：首先初始化一个单链表，其头结点为空，然后循环插入新结点*s：将s的next指向头结点的下一个结点，然后将头结点的next指向s。
算法思想：首先初始化一个单链表，然后声明一个尾指针r，让r始终指向当前链表的尾结点，循环向单链表的尾部插入新的结点*s，将尾指针r的next域指向新结点，再修改尾指针r指向新结点，也就是当前链表的尾结点。最后别忘记将尾结点的指针域置空。【本文地址】
今日新闻 |
推荐新闻 |