线性表——单向循环链表的设计思路与实现

user等级-LV9-津桥芝士平台6个月前更新
280

单向循环链表的基本结构定义：

单向循环链表的结构定义与普通的链式存储结构的链表的结构一样。

//定义了循环链表的结构体 
typedef struct Node{
	ElemType data;
	struct Node *next;
}Node, *LinkList;

我们假定有：

#define MAXSIZE 260
typedef struct{
	char name[MAXSIZE];
	char id[MAXSIZE];
}stu; 

typedef stu ElemType;
bool cmp(ElemType e1, ElemType e2)
{
	if(strcmp(e1.name, e2.name) == 0 && strcmp(e1.id, e2.id) == 0)
	    return true;
	return false;
}

单向循环链表的初始化：

  • 先对头结点分配内存，如果分配失败则头结点为NULL
  • 分配内存成功则将头节点的next指针指向头节点。
  • 最后返回分配好内存的地址。
Node *InitLinkList(LinkList L)        //创建一个头结点
{
  	L = (Node *)malloc(sizeof(Node));
  	if(L == NULL) 
  	{
    	return NULL;
  	}
  	L->next = L;//初始化头指针 
  	return L;
}

尾插法：

  • 设置一个节点指向头节点，通过循环将节点指向最后一个节点。
  • 再对一个节点进行分配内存，并将数据存储进数据域。
  • 将新节点的指针的后继指针指向尾节点的后继指针指向的地址。
  • 尾节点的后继节点指针指向新的节点。
Node *InsertListTail(LinkList L, ElemType data)      //尾插法 
{
  	Node *r = L;
  	while(r->next != L)
      	r = r->next;
  	Node *p = (Node *)malloc(sizeof(Node));
    if(p == NULL)
        return NULL;
  	p->data = data;
  	p->next = r->next;
  	r->next = p;
  	return p;
}

头插法：

  • 对一个节点进行内存分配，分配成功后，将数据存储进数据域。
  • 将新节点的指针域指向头节点的后继指针指向的地址。
  • 将头节点的指针域指向新节点的地址。
Node *InsertListHead(LinkList L, ElemType data)      //头插法 
{
  	Node *p = (Node *)malloc(sizeof(Node));
  	if(p == NULL)
      	return NULL;
  	p->data = data;
  	p->next = L->next;
  	L->next = p;
  	return p;
}

按位插入：

  • 先进行位置判断，看是否越界。
  • 接着将作为缓冲的节点指针指向插入位置的前一个位置。
  • 将数据存储进数据域
  • 将新节点的后继指针指向缓冲指针的后继节点指针指向的地址
  • 将缓冲节点的后继节点指针指向新节点的地址。
Node *Insert(LinkList L, int pos, ElemType e)      //在指定位置插入一个元素 
{
  	if(pos < 1 || pos > Size(L))
    	return NULL;
  
  	Node *p = L;
  	int count = 0;
  	for(count = 1; count < pos; ++count)
      	p = p->next;
  	Node *q = (Node *)malloc(sizeof(Node));      //分配内存空间 
  	if(q == NULL)
      	return NULL;
  	q->data = e;
  	q->next = p->next;
  	p->next = q;
  	return q;
}

 

按位删除：

  • 先判断删除位置是否合法。
  • 接着将缓冲节点1指向待删除位置的前一个位置。
  • 将缓冲节点2指向待删除的位置
  • 将缓冲节点的后继节点指针指向待删除节点的后继节点指针指向地址。
  • 释放掉缓冲节点2的内存（释放掉待删除的节点的内存）。
bool DeletePos(LinkList L, int pos)      //按位删除
{
  	if(pos < 1 || pos > Size(L))
      	return false;
  	Node *p = L, *q = NULL;
  	int n;
  	for(n = 1; n < pos; n++)
      	p = p->next;
  	q = p->next;
  	p->next = q->next;
  	free(q);
  	return true;
}

按值删除：（设待删除节点为p）

  • 遍历整个链表，遍历时进行比较。
  • 如果是需要删除的值。则将待删除节点的前驱节点的后继节点指针指向待删除节点后继指针指向的地址。
  • 否则向后移动一个节点。
void DeleteValue(LinkList L, ElemType e)    //删除指定的值 
{
  	Node *p = L->next, *q = L;
  	int j = 0;
  	while(p != L)
  	{
    	if(cmp(p->data, e))
    	{
      		q->next = p->next;
      		free(p);
      		p = q->next;
    	}
    	else
    	{
      		p = p->next;
      		q = q->next;
    	}
  	}
}

销毁链表：

  • 将作为缓冲的节点1指向头节点的后一个节点
  • 在循环中，将缓冲节点2指向缓冲节点1，再将缓冲节点1指向其next指针指向的节点
  • 释放缓冲节点2指向的地址的内存。
  • 最后释放缓冲节点1指向的地址的内存。
void DestoryList(LinkList* L)      //销毁循环链表
{
  	if(L == NULL || *L == NULL)
  	    return;
  	Node *p = (*L)->next, *q = NULL;
  	while(p != *L)
  	{
  		q = p;
  		p = p->next;
  		free(q);
	}
	free(p);
	*L = NULL;
}

修改元素：

  • 首先判断位置是否合法
  • 合法就遍历N次链表，将缓冲指针指向待修改的位置。
  • 修改数据域即可。
bool ChangeElem(LinkList L, int pos, ElemType e)      //将指定位置的值修改 
{
  	if(pos < 1 || pos > Size(L))
    	return false;
  
  	Node *p = L->next;
  	int count;
  	for(count = 1; count < pos; ++count)
      	p = p->next;
  	p->data = e;
  	return true;
}

查询链表的节点数量：

  • 将缓冲指针指向头节点的next指针指向的地址。
  • 遍历整个链表，每次循环就将用于计数的变量+1；
  • 最后回到头节点时返回计数。
int Size(LinkList L)    //查询循环链表的元素个数 
{
  	Node *p = L->next;
    int count = 0;
    while(p != L)
    {
      	++count;
      	p = p->next;
  	}
  	return count;
}

 

查询单项循环链表是否为空：

  • 判断头节点的next指针是否指向它本身，如果指向头节点，则说明为空。
bool EmptyList(LinkList L)      //判断循环链表是否为空 
{
  	if(L->next == L)
      	return true;
  	return false;
}

获取指定位置的节点：

  • 先判断位置是否合法，不合法则返回
  • 接着遍历N次链表即可，最后的缓冲节点的数据域就是需要查询的位置的值
void GetElem(LinkList L, int pos, ElemType *buffer)      //按位查找, rear为尾指针,i为查找的位置 
{
  	if(pos < 1 || pos > Size(L))
  	{
    	buffer = NULL;
    	return;
  	}
      
  	Node *p = L->next;
  	int count;
  	for(count = 1; count < pos; ++count)
      	p = p->next;
  	*buffer = p->data;
  	return;
}

 

按值查找（第一个目标值）：

  • 将一个作为缓冲的节点指向头节点，接着进入循环遍历它。
  • 循环时，比较待查询的数据与缓冲节点的数据域中的数据是否相等，相等就返回用于计数的变量。
  • 否则返回-1，表明未找到。
int GetValuePosition_First(LinkList L, ElemType e)    //按值查找, rear为尾指针， e为查找的值 
{
  	int count = 0;        //count用于计数 
  	Node *p = L->next;
  	while(p != L)
  	{
    	++count;
    	if(cmp(p->data, e))
      		return count;
    	p = p->next;  
  	}
  	return -1;
}

 

总的实现代码如下：

// 单向循环链表
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#include <string.h>

#define MAXSIZE 260
typedef struct{
	char name[MAXSIZE];
	char id[MAXSIZE];
}stu; 

typedef stu ElemType;

//定义了循环链表的结构体 
typedef struct Node{
  ElemType data;
  struct Node *next;
}Node, *LinkList;

bool cmp(ElemType e1, ElemType e2)
{
	if(strcmp(e1.name, e2.name) == 0 && strcmp(e1.id, e2.id) == 0)
	    return true;
	return false;
}
// 查
int Size(LinkList L)    //查询循环链表的元素个数 
{
  	Node *p = L->next;
    int count = 0;
    while(p != L)
    {
      	++count;
      	p = p->next;
  	}
  	return count;
}

bool EmptyList(LinkList L)      //判断循环链表是否为空 
{
  	if(L->next == L)
      	return true;
  	return false;
}

void GetElem(LinkList L, int pos, ElemType *buffer)      //按位查找, rear为尾指针,i为查找的位置 
{
  	if(pos < 1 || pos > Size(L))
  	{
    	buffer = NULL;
    	return;
  	}
      
  	Node *p = L->next;
  	int count;
  	for(count = 1; count < pos; ++count)
      	p = p->next;
  	*buffer = p->data;
  	return;
}

int GetValuePosition_First(LinkList L, ElemType e)    //按值查找, rear为尾指针， e为查找的值 
{
  	int count = 0;        //count用于计数 
  	Node *p = L->next;
  	while(p != L)
  	{
    	++count;
    	if(cmp(p->data, e))
      		return count;
    	p = p->next;  
  	}
  	return -1;
}

//增 
Node *InitLinkList(LinkList L)        //创建一个头结点
{
  	L = (Node *)malloc(sizeof(Node));
  	if(L == NULL) 
  	{
    	return NULL;
  	}
  	L->next = L;//初始化头指针 
  	return L;
}

Node *InsertListHead(LinkList L, ElemType data)      //头插法 
{
  	Node *p = (Node *)malloc(sizeof(Node));
  	if(p == NULL)
      	return NULL;
  	p->data = data;
  	p->next = L->next;
  	L->next = p;
  	return p;
}

Node *InsertListTail(LinkList L, ElemType data)      //尾插法 
{
  	Node *r = L;
  	while(r->next != L)
      	r = r->next;
  	Node *p = (Node *)malloc(sizeof(Node));
    if(p == NULL)
        return NULL;
  	p->data = data;
  	p->next = r->next;
  	r->next = p;
  	return p;
}

Node *Insert(LinkList L, int pos, ElemType e)      //在指定位置插入一个元素 
{
  	if(pos < 1 || pos > Size(L))
    	return NULL;
  
  	Node *p = L;
  	int count = 0;
  	for(count = 1; count < pos; ++count)
      	p = p->next;
  	Node *q = (Node *)malloc(sizeof(Node));      //分配内存空间 
  	if(q == NULL)
      	return NULL;
  	q->data = e;
  	q->next = p->next;
  	p->next = q;
  	return q;
}

bool DeletePos(LinkList L, int pos)      //按位删除
{
  	if(pos < 1 || pos > Size(L))
      	return false;
  	Node *p = L, *q = NULL;
  	int n;
  	for(n = 1; n < pos; n++)
      	p = p->next;
  	q = p->next;
  	p->next = q->next;
  	free(q);
  	return true;
}

void DeleteValue(LinkList L, ElemType e)    //删除指定的值 
{
  	Node *p = L->next, *q = L, *s = NULL;
  	int j = 0;
  	while(p != L)
  	{
    	if(cmp(p->data, e))
    	{
      		q->next = p->next;
      		free(p);
      		p = q->next;
    	}
    	else
    	{
      		p = p->next;
      		q = q->next;
    	}
  	}
}

void DestoryList(LinkList* L)      //销毁循环链表
{
  	if(L == NULL || *L == NULL)
  	    return;
  	Node *p = (*L)->next, *q = NULL;
  	while(p != *L)
  	{
  		q = p;
  		p = p->next;
  		free(q);
	}
	free(p);
	*L = NULL;
} 

//改
bool ChangeElem(LinkList L, int pos, ElemType e)      //将指定位置的值修改 
{
  	if(pos < 1 || pos > Size(L))
    	return false;
  
  	Node *p = L->next;
  	int count;
  	for(count = 1; count < pos; ++count)
      	p = p->next;
  	p->data = e;
  	return true;
}

void Display(LinkList L)
{
	Node* p = L->next;
	while(p != L)
	{
		printf("name: %10s\tid: %10s\n", p->data.name, p->data.id);
		p = p->next;
	}
	return;
}

int main()      //主函数 
{

    return 0;
}
评分
欢迎为Ta评分
赞赏
分享
请登录后发表评论

    没有回复内容

发布文章发布帖子
在手机上浏览此页面
工作时间
全周无休：9:00-23:00
欢迎大家骚扰
zibll子比主题
本站同款主题模板
zibll子比主题是一款漂亮优雅的网站主题模板，功能强大，配置简单。
查看详情