转载请注明出处：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#表达，很强大。
如资源名，用c实现了基于结构体的循环链表。
结构体可以看做是C语言中的类 但是结构体中不能封装函数，只能有数据成员 这个程序演示了如何像c++的类一样在结构体中增加函数 如果有错误，欢迎交流
单向链表(一) 结构体、创建链表、遍历链表
将多个变量放到一个结构体中，减少函数传递时的多个参数传进传出的复杂性 结构体传进函数时，是以引用的形式传入的，不是以指针的形式。
c#调用C++动态库、执行回调函数，并回传结构体参数数据。vs2017环境编写C#和C++动态库，这个为完整工程例子，可供相关人员学习参考。
在写C#TCP通信程序时，发送数据时，只能发送byte数组，处理起来比较麻烦不说，如果是和c++等写的程序通信的话，很多的都是传送结构体，在VC6.0中可以很方便的把...C#调用c++dll时也可以使用此函数来转换结构体或指针。
资源代码演示的是c#代码调用c++ DLL 的方式。该演示为原创，绝非搬砖。解决了c# 调用 C++ Dll获取相关信息之如何传递结构体数组引用以及如何处理获取到的结构体数组数据的问题。
用于在C++结构体和json/xml之间互相转换, bson在xbson中支持。 只需要头文件, 无需编译库文件。 具体可以参考example的例子
学习了C++的面向对象，最常见的和写的就是类结构体，这篇文章主要简单介绍一下结构体和类的区别。 首先类是C++中面向对象独有的，但是C和C++中都有结构体，下面我们来看一下C和C++中结构体的区别。这里主要从封装...
一个简单的C++ UDP接收结构体数据的例子，包含大小端转换说明，博客https://blog.csdn.net/guimaxingtian/article/details/100030614中的最终代码
本程序采用链表的形式处理学生信息，所以用结构体储存学生的信息，每个函数模块都相互独立，源代码简单易懂，可以方便的删除、修改、添加模块，便于根据各种情况对程序升级，以完成任务。 感谢使用啊！
1，结构体。 2，链表。 3，结构体与链表的应用。
C++中自定义结构体选择一个键值 调用sort qsort排序
以下的函数即是用于清空结构体的，需要传入的两个参数分别为结构体的起始地址和结构体的长度。 void Clear(unsigned char *Ptr, int Size ){ while(Size!=0) { *Ptr++ = 0; Size --; }} 函数的调用如下。 ...
C++语法和结构体，相当好的东西，值得参考！
c++调用dll ，指针结构体参数传递，--改造了csdn 上的一个程序。
C++结构体参数与结构体指针参数区别Demo(资源包括C++源程序和编译好的exe文件)
关于C/C++的结构体说明，一些常用的插入，删除方法
c、c++如果在日志中查看某个结构字段信息，只能通过printf逐个格式化，工作量大； 该dll库通知pdb文件分析结构体字段位置，并根据类型格式一个完整字符串，极大降低了开发者工作量。 1、可通过cdump\Release\...