转载请注明出处：http://blog.csdn.net/hongkangwl/article/details/21882459
关于静态链表的C实现，网上已经烂大街了，这里就不在废话了。对于本文，纯粹是本屌闲的蛋疼，如有异议，请轻喷。
对于每个节点，这里也不能免俗，使用结构体实现
struct staticlinklistnode
{
int data;//数据
int next;//下个数据的存储位置
bool used;//是否放在链表中了
};
静态链表的类主要仿照STL中实现了一些接口函数
class staticlinklist
{
private:
static int length;//长度
static int capacity;//容量
public:
staticlinklistnode* ptrnode;//用来存放元素
staticlinklistnode* root;//链表的头
staticlinklist()
{
length = 0;
capacity = 0;
root->next = -1;
// ptrnode = NULL;
}
staticlinklist(int n)
{
length = 0;
capacity = n;
root = new staticlinklistnode;
// staticlinklistnode* node = new staticlinklistnode[n];
// ptrnode = node;
ptrnode = new staticlinklistnode[n];
root->next = -1;
for(int i = 0; i < n; i++)
{
ptrnode[i].next = -1;
ptrnode[i].used = false;
}
// ptrnode = node;
}
int insert(staticlinklist* ptr,int pos,int n);//插入
void display(staticlinklist* ptr);//输出链表的数据
int getlength(staticlinklist* ptr);//长度
int getcapacity(staticlinklist* ptr);//返回容量
void decreaselength(staticlinklist* ptr);//减小长度
void increaselength(staticlinklist* ptr);//增加长度
void setcapacity(staticlinklist* ptr,int capa);//设置容量
int erase(staticlinklist* ptr, int pos);//删除
int getmember(staticlinklist* ptr, int pos);//取得元素
void pushback(staticlinklist* ptr,int n);//末尾插入
void pushfront(staticlinklist* ptr, int n);//前端插入
int popback(staticlinklist* ptr);//弹出最后一个元素
int popfront(staticlinklist* ptr);//弹出第一个元素
~staticlinklist()
{
}
};
其中display可以用getmember实现呢，封装一下就好，popback/popfront是erase函数的封装，pushfront/pushback是insert函数的封装，下面看每个函数的具体定义：
int staticlinklist::popfront(staticlinklist* ptr)
{
ptr->erase(ptr,0);
// ptr->length--;
return 0;
}
int staticlinklist::popback(staticlinklist* ptr)
{
ptr->erase(ptr,ptr->getlength(ptr) - 1);
// ptr->length--;
return 0;
}
void staticlinklist::pushfront(staticlinklist* ptr, int n)
{
ptr->insert(ptr,0,n);
// ptr->length++;
}
void staticlinklist::pushback(staticlinklist* ptr,int n)
{
ptr->insert(ptr,ptr->getlength(ptr),n);
// ptr->length++;
}上面四个函数很简单吧，不多说了~
重点看下插入和删除函数
int staticlinklist::insert(staticlinklist* ptr,int pos,int n)
{
if(pos > ptr->length)
{
cout<<"不合法的位置"<<endl;
return -1;
}
else
{
/*int index = ptr->getlength(ptr);
ptrnode[index].data = n;*/
int i =0;
// while((ptrnode[i++].next == -1) && (ptrnode[i].used == true));
while(ptrnode[i++].used == true);
int index = i -1 ;
ptrnode[index].data = n;
int current = root->next ;
int back;
if(root->next == -1) //链表为空
{
if(pos == 0)
{
root->next = index;
ptrnode[index].used = true;
ptr->increaselength(ptr);
return 0;
}
else
{
cout<<"oops！！存放位置不合法"<<endl;
return -1;
}
}
if(pos == 0)//链表不为空，插入第0位置
{
ptrnode[index].next = root->next;
root->next = index;
ptrnode[index].used = true;
ptr->increaselength(ptr);
return 0;
}
for(int i = 0; i < pos; i++)//链表不为空，插入位置亦不为0
{
back = current;
current = ptrnode[current].next;
}
ptrnode[back].next = index;
ptrnode[index].used = true;
ptrnode[index].next = current;
ptr->increaselength(ptr);
return 0;
}
}
插入函数花了好久，主要是对插入的元素判断是否插入判断出现问题，因为如果插入的链表的末尾的话，那么其next仍然没有指向一个节点，而没有放入静态链表的next也没有指向某个节点，这样在判断这个节点是否已经使用并放入了静态链表时会出现问题，因此，在节点结构体引入了use，如果已经使用，则为真，否则为假。
删除节点的源码
int staticlinklist::erase(staticlinklist* ptr,int pos)
{
if(pos > ptr->getlength(ptr))
{
cout<<"此位置不合法"<<endl;
return -1;
}
else
{
int current= root->next;
int back ;
if(pos == 0)
{
ptrnode[current].used = false;
root->next = ptrnode[current].next;
ptrnode[current].next = -1;
ptr->length--;
return 0;
}
else
{
for(int i = 0; i < pos; i++)
{
back = current;
current = ptrnode[current].next;
}
ptrnode[back].next = ptrnode[current].next;
ptrnode[current].next = -1;
ptrnode[current].used = false;
ptr->length--;
return 0;
}
}
}很明显，删除比插入简单了一些，程序的整体代码是：
#include <iostream>
using namespace std;
struct staticlinklistnode
{
int data;//数据
int next;//下个数据的存储位置
bool used;//是否放在链表中了
};
class staticlinklist
{
private:
static int length;//长度
static int capacity;//容量
public:
staticlinklistnode* ptrnode;//用来存放元素
staticlinklistnode* root;//链表的头
staticlinklist()
{
length = 0;
capacity = 0;
root->next = -1;
// ptrnode = NULL;
}
staticlinklist(int n)
{
length = 0;
capacity = n;
root = new staticlinklistnode;
// staticlinklistnode* node = new staticlinklistnode[n];
// ptrnode = node;
ptrnode = new staticlinklistnode[n];
root->next = -1;
for(int i = 0; i < n; i++)
{
ptrnode[i].next = -1;
ptrnode[i].used = false;
}
// ptrnode = node;
}
int insert(staticlinklist* ptr,int pos,int n);//插入
void display(staticlinklist* ptr);//输出链表的数据
int getlength(staticlinklist* ptr);//长度
int getcapacity(staticlinklist* ptr);//返回容量
void decreaselength(staticlinklist* ptr);//减小长度
void increaselength(staticlinklist* ptr);//增加长度
void setcapacity(staticlinklist* ptr,int capa);//设置容量
int erase(staticlinklist* ptr, int pos);//删除
int getmember(staticlinklist* ptr, int pos);//取得元素
void pushback(staticlinklist* ptr,int n);//末尾插入
void pushfront(staticlinklist* ptr, int n);//前端插入
int popback(staticlinklist* ptr);//弹出最后一个元素
int popfront(staticlinklist* ptr);//弹出第一个元素
~staticlinklist()
{
}
};
int staticlinklist::capacity = 0;
int staticlinklist::length = 0;
int staticlinklist::popfront(staticlinklist* ptr)
{
ptr->erase(ptr,0);
// ptr->length--;
return 0;
}
int staticlinklist::popback(staticlinklist* ptr)
{
ptr->erase(ptr,ptr->getlength(ptr) - 1);
// ptr->length--;
return 0;
}
void staticlinklist::pushfront(staticlinklist* ptr, int n)
{
ptr->insert(ptr,0,n);
// ptr->length++;
}
void staticlinklist::pushback(staticlinklist* ptr,int n)
{
ptr->insert(ptr,ptr->getlength(ptr),n);
// ptr->length++;
}
int staticlinklist::getmember(staticlinklist* ptr, int pos)
{
if(pos > ptr->getlength(ptr))
{
cout<<"位置非法"<<endl;
return -1;
}
int current = root->next;
for(int i = 0; i < pos; i++)
{
current = ptrnode[current].next;
}
return ptrnode[current].data;
}
int staticlinklist::erase(staticlinklist* ptr,int pos)
{
if(pos > ptr->getlength(ptr))
{
cout<<"此位置不合法"<<endl;
return -1;
}
else
{
int current= root->next;
int back ;
if(pos == 0)
{
ptrnode[current].used = false;
root->next = ptrnode[current].next;
ptrnode[current].next = -1;
ptr->length--;
return 0;
}
else
{
for(int i = 0; i < pos; i++)
{
back = current;
current = ptrnode[current].next;
}
ptrnode[back].next = ptrnode[current].next;
ptrnode[current].next = -1;
ptrnode[current].used = false;
ptr->length--;
return 0;
}
}
}
void staticlinklist::setcapacity(staticlinklist* ptr,int capa)
{
ptr->capacity = capa;
}
void staticlinklist::display(staticlinklist* ptr)
{
int index = root->next;
for(int i = 0; i < ptr->getlength(ptr); i++)
{
cout<<ptrnode[index].data<<" ";
index = ptrnode[index].next;
}
cout<<endl;
}
void staticlinklist::decreaselength(staticlinklist* ptr)
{
ptr->length--;
}
void staticlinklist::increaselength(staticlinklist* ptr)
{
ptr->length++;
}
int staticlinklist::getlength(staticlinklist* ptr)
{
return ptr->length;
}
int staticlinklist::getcapacity(staticlinklist* ptr)
{
return ptr->capacity;
}
int staticlinklist::insert(staticlinklist* ptr,int pos,int n)
{
if(pos > ptr->length)
{
cout<<"不合法的位置"<<endl;
return -1;
}
else
{
/*int index = ptr->getlength(ptr);
ptrnode[index].data = n;*/
int i =0;
// while((ptrnode[i++].next == -1) && (ptrnode[i].used == true));
while(ptrnode[i++].used == true);
int index = i -1 ;
ptrnode[index].data = n;
int current = root->next ;
int back;
if(root->next == -1) //链表为空
{
if(pos == 0)
{
root->next = index;
ptrnode[index].used = true;
ptr->increaselength(ptr);
return 0;
}
else
{
cout<<"oops！！存放位置不合法"<<endl;
return -1;
}
}
if(pos == 0)//链表不为空，插入第0位置
{
ptrnode[index].next = root->next;
root->next = index;
ptrnode[index].used = true;
ptr->increaselength(ptr);
return 0;
}
for(int i = 0; i < pos; i++)//链表不为空，插入位置亦不为0
{
back = current;
current = ptrnode[current].next;
}
ptrnode[back].next = index;
ptrnode[index].used = true;
ptrnode[index].next = current;
ptr->increaselength(ptr);
return 0;
}
}
int main()
{
int n;
cout<<"静态链表的容量是多大？请输入："<<endl;
cin>>n;
// slinklist->setcapacity(slinklist,n);
staticlinklist* slinklist = new staticlinklist(n);
int m;
cout<<"你要存储多少个元素？请输入："<<endl;
cin>>m;
for(int i = 0; i < m; i++)
{
slinklist->insert(slinklist,i,i);
}
slinklist->display(slinklist);
slinklist->insert(slinklist,2,100);
cout<<"在位置2上插入100后静态链表为："<<endl;
slinklist->display(slinklist);
slinklist->erase(slinklist,3);
cout<<"把位置3上面的元素删除后静态链表为："<<endl;
slinklist->display(slinklist);
slinklist->erase(slinklist,3);
cout<<"把位置3上面的元素删除后静态链表为："<<endl;
slinklist->display(slinklist);
cout<<"使用成员函数输出链表数据"<<endl;
for(int i = 0; i < slinklist->getlength(slinklist); i++)
{
cout<<slinklist->getmember(slinklist,i)<<" ";
}
cout<<endl;
slinklist->popback(slinklist);
cout<<"使用popback后静态链表为"<<endl;
slinklist->display(slinklist);
slinklist->popfront(slinklist);
cout<<"使用popfront后静态链表为"<<endl;
slinklist->display(slinklist);
slinklist->pushfront(slinklist,88);
cout<<"使用pushfront 88 后静态链表为"<<endl;
slinklist->display(slinklist);
slinklist->pushback(slinklist,99);
cout<<"使用pushback 99 后静态链表为"<<endl;
slinklist->display(slinklist);
return 0;
}
测试结果为：
经测试初步实现功能，嘎嘎~
分享到：
相关推荐
- C++的虚函数在C#中对应为接口（Interface）或抽象类（Abstract Class）。 - C++的模板函数无法直接转换，可能需要创建多个C#方法来模拟。 4. **DLL互操作**： - 提供的文件中有`.dll`文件（如：sigimplib.dll...
为了进行调用，我们需要在C#中定义与C++接口一致的委托类型和结构体类型，以匹配C++中的函数原型和数据结构。 C++动态库中，回调函数是一种特殊的函数，它的指针可以作为参数传递给其他函数，在适当的时候被调用。...
如资源名，用c实现了基于结构体的循环链表。
在C语言中，尽管结构体是用来组织数据的一种方式，它本身并不支持直接在其中定义或封装函数，就像C++中的类。然而，通过巧妙地利用函数指针，我们可以模拟类的面向对象特性，实现类似的功能。下面将详细介绍如何在...
本篇将探讨如何在C++中实现结构体与JSON和XML之间的互转，并以`bson`库在`xbson`中的支持为例进行说明。 首先，让我们了解JSON和XML的基本概念。JSON是一种轻量级的数据交换格式，其数据结构主要由对象（键值对）和...
### C#调用C++ DLL：结构体数组引用的传递及解析使用详解 #### 引言 在跨语言编程环境中，经常会遇到不同编程语言之间进行交互的需求。C#与C++之间的互操作就是一个典型场景。当C#需要调用C++开发的动态链接库...
将多个变量放到一个结构体中，减少函数传递时的多个参数传进传出的复杂性 结构体传进函数时，是以引用的形式传入的，不是以指针的形式。
标题中的“Java和C++通信结构体发送”指的是在Java和C++这两种不同的编程语言之间，通过网络进行通信时如何有效地传递结构体数据的问题。在跨语言通信中，由于二进制序列化和内存布局的差异，直接传输结构体会面临...
"C++自定义结构体排序实现" C++中的结构体排序是指对自定义结构体类型的数据...在C++中，我们可以使用重载运算符或函数对象来实现结构体的排序。排序的键值可以是结构体中的任何成员变量，以便实现不同的排序方式。
单向链表是一种基本的数据结构，它在...通过定义结构体，我们可以创建链表节点，然后使用插入函数构建链表。遍历链表则允许我们访问并处理链表中的所有元素。了解和掌握这些基础知识是成为一名熟练的程序员的必经之路。
在写C#TCP通信程序时，发送数据时，只能发送byte数组，处理起来比较麻烦不说，如果是和c++等写的程序通信的话，很多的都是传送结构体，在VC6.0中可以很方便的把...C#调用c++dll时也可以使用此函数来转换结构体或指针。
在C++中，结构体可以直接作为参数传递，而在C#中，我们通常使用类来表示结构体。C++中的指针和引用在C#中分别对应为`IntPtr`和引用类型。因此，当C++ DLL返回结构体的引用或指针时，C#需要进行相应的转换。 1. **...
在IT领域，结构体和链表是数据结构与算法中的基础概念，对于任何软件开发者，尤其是初学者，理解和掌握它们至关重要。在这个“结构体与函数、创建链表课堂举例”中，我们将深入探讨这两个主题。 首先，我们来看...
学习了C++的面向对象，最常见的和写的就是类结构体，这篇文章主要简单介绍一下结构体和类的区别。 首先类是C++中面向对象独有的，但是C和C++中都有结构体，下面我们来看一下C和C++中结构体的区别。这里主要从封装...
一个简单的C++ UDP接收结构体数据的例子，包含大小端转换说明，博客https://blog.csdn.net/guimaxingtian/article/details/100030614中的最终代码
通过以上四个操作，我们可以灵活地使用C++中的结构体来组织和操作数据。在数据结构的学习中，结构体是构建复杂数据结构（如链表、树、图等）的基础，也是理解和实现算法的关键。在实际编程中，掌握结构体及其操作将...
在C++编程中，结构体（struct）是一种用户自定义的数据类型，用于组合不同类型的数据成员。在函数调用时，我们可以传递结构体作为参数。这里主要讨论两种方式：直接传递结构体和通过结构体指针传递，这两种方式在...
本篇将深入探讨结构体的定义、使用以及与链表相关的操作，如插入和删除节点。 首先，我们来理解什么是结构体。在C/C++中，你可以通过`struct`关键字定义一个新的数据类型，然后在这个类型中包含各种不同的成员，...
以下的函数即是用于清空结构体的，需要传入的两个参数分别为结构体的起始地址和结构体的长度。 void Clear(unsigned char *Ptr, int Size ){ while(Size!=0) { *Ptr++ = 0; Size --; }} 函数的调用如下。 ...
在这个案例中，系统使用了两种不同的方法来实现：结构体数组法和链表法，这两种都是在C语言和C++中处理数据的有效方式。下面将详细讨论这两个方法以及相关的编程知识点。 1. **结构体数组法**： 在`学生成绩管理...