[原创]实现 限运算版hash setofsteak的底层 数组链表+链表 cc150题目 类似二维数组的底层
思路： 每个链表数组都指向一个链表的头节点，如果当前链表已经满 为链表数组申请空间为新列。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define clen 2 //当前最大长度
//#typedef llen 2 //当前最大长度
int llen=0;//列总长度
typedef struct no
{
int data; //初始化
no *pnext;
}node;
typedef struct
{
node head;
node tail; // 初始化
int size;
}lht;
void link_init(lht larr[])
{
llen++;
larr[llen-1].head.pnext=&larr[llen-1].tail;
larr[llen-1].tail.pnext=NULL; //构造链表数组
larr[llen-1].size=0;
}
void link_addlength(lht *p) //增加链表长度
{
lht *t=(lht *)malloc(sizeof(lht)+sizeof(node)); //在原有基础上扩展指针范围
t=p;
free(p);
p==NULL;
if(t!=NULL)
{
llen++; //列标记增加
(t+llen-1)->head.pnext=&(t+llen-1)->tail;
(t+llen-1)->tail.pnext=NULL; //初始化新列
(t+llen-1)->size=0;
}
else
link_addlength(p);//这个可能有bug 不过这条代码执行的概率不高
}
void link_adddata(lht l[],int i) //增加数据
{
node *pk=l[llen-1].head.pnext;
if(l[llen-1].size==clen) //当 当前列已经满
{
link_addlength(l);
link_adddata(l,i);
}
else
{
node *pf=NULL,*pn=pf;
pf=(node*)&l[llen-1].head;
pn=(node*)malloc(sizeof(node));
pn->data=i;
l[llen-1].size++;
// printf("%d",pn->data);
pn->pnext=pf->pnext;
pf->pnext=pn;
}
}
void link_sub(lht *p) //删除节点
{
node *pn=NULL,*pm=NULL;
pn=&(p+llen-1)->head;
//因为当前列至少有一个元素
pm=pn->pnext;
pn->pnext=pm->pnext;
free(pm);
pm=NULL;
if(pn->pnext==&(p+llen-1)->tail) //如果 当前列已经空
{
free((p+llen-1)); //删除这个列的空间
llen--; //列标记减1
}
}
void link_show(const lht larr[])
{
int i=0;
node *pn=larr[i].head.pnext;
while(i<llen)
{
pn=larr[i].head.pnext;
while(pn!=&larr[i].tail)
{
printf("%d %d ",i,pn->data);
pn=pn->pnext;
}
printf("\n");
i++;
}
}
int main(int argc, char *argv[])
{
lht larr[1]={0};
//cout<<sizeof(larr)<<endl;
link_init(larr);
//cout<<sizeof(larr)<<endl;
link_adddata(larr,5);
//cout<<sizeof(larr)<<endl;
link_adddata(larr,6);
link_adddata(larr,7);
link_adddata(larr,8);
link_adddata(larr,9);
link_adddata(larr,9);
link_adddata(larr,9);
link_adddata(larr,9);
link_show(larr);
// cout<<larr[2].head.pnext->data;
link_sub(larr);
// link_sub(larr);
cout<<"*****************"<<endl;
link_show(larr);
return 0;
}
