2 u012753970 u012753970 于 2014.11.20 13:57 提问

ARM开发中,用C语言 实现双向链表

各位前辈
你们好!

如题,我在ARM开发中,需要用到双向链表来管理接受到的数据。
我对双向链表不是很理解,在实际编程的时候遇到一些问题。
希望得到各位的帮助。
我本来打算用数组来做的。但是发现添加数据和删除数据都比较麻烦。
最后决定用双向链表来完成。

使用双向链表的目的
1,链表可以接受不超过64个的数据(结构体)
2,在链表中查询数据ID,可以进行添加和删除还有覆盖相同ID的数据
3,遍历链表中的数据ID,调用数据信息。

项目管理是一个外国人,我看他用链表不用malloc和free,我也想按照他的写法去找列子,
但是国内的列子都是有带malloc和free的。

因为时限快到了,我又学艺不精,所以向各位求教相应的信息或者实现的代码。

谢谢!

7个回答

zcwme
zcwme   2014.11.20 15:56

节点创建都要malloc的,你纠结这些有用么?

zcwme
zcwme   2014.11.20 15:56

节点创建都要malloc的,你纠结这些有用么?

zcwme
zcwme   2014.11.20 15:56

节点创建都要malloc的,你纠结这些有用么?

u012753970
u012753970 那个外国人的代码里没有用到malloc,他固定了一个Head,所以我郁闷了。。。
接近 3 年之前 回复
tigerjb
tigerjb   Rxr 2014.11.21 14:11

纠正一个问题。用链表必须使用malloc和free去动态申请节点空间,最后要释放掉。你可以去参考下linux内核中的链表实现,很经典。这是我以前写的一篇分析文章,希望对你有用:http://blog.csdn.net/tigerjibo/article/details/8299599

u012753970
u012753970 谢谢您的回答!那个老外对我说,,并且在这个ARM系列中用的固定长memory pool,并且,OS是iTronOS先用的这个系列的OS是OS的使用手册中,并没有提倡用malloc和free,因为得不到保证,所以就没有用malloc和free。我也是恍然大悟。
接近 3 年之前 回复
YKDSea
YKDSea   Rxr 2014.11.24 16:28

不用Malloc/free,那就是一开始申请了大量的节点作为pool(可以用数组来申请),用的时候去其中拿,用完再放回去

zhao4zhong1
zhao4zhong1   Rxr 2014.11.25 15:41
//将c:\\tmp文件夹下的所有文件的内容全部放到用malloc分配的内存中

#include
#include
#include
#include
struct FB {
char fn[256];
size_t fl;
char b;
struct FB *next;
struct FB *prev;
} *fh,*fb,*ft;
char ln[256];
char fpn[256];
FILE *af;
FILE *f;
int L,n;
int main() {
system("dir /b /a-d c:\tmp\
.* >c:\allfn.txt");
af=fopen("c:\allfn.txt","r");
if (NULL==af) {
printf("Can not open file c:\allfn.txt!\n");
return 1;
}
fh=NULL;
fb=NULL;
n=0;
while (1) {
if (NULL==fgets(ln,256,af)) break;
L=strlen(ln);
if ('\n'==ln[L-1]) ln[L-1]=0;
printf("read %s\n",ln);
strcpy(fpn,"c:\tmp\");
strcat(fpn,ln);
ft=(struct FB *)malloc(sizeof(struct FB));
if (NULL==ft) {
printf("Can not malloc ft!\n");
fclose(af);
return 2;//之前的malloc在main退出后由操作系统自动free
}
printf("ft[%d]==%p\n",n,ft);
strcpy(ft->fn,fpn);
f=fopen(fpn,"rb");
if (NULL==f) {
printf("Can not open file %s!\n",fpn);
fclose(af);
return 3;//之前的malloc在main退出后由操作系统自动free
}
ft->fl=_filelength(fileno(f));
ft->b=malloc(ft->fl);
if (NULL==ft->b) {
printf("Can not malloc ft->b!\n");
fclose(f);
fclose(af);
return 4;//之前的malloc在main退出后由操作系统自动free
}
printf("ft[%d]->b==%p\n",n,ft->b);
if (ft->fl!=fread(ft->b,1,ft->fl,f)) {
printf("fread error!\n");
fclose(f);
fclose(af);
return 5;//之前的malloc在main退出后由操作系统自动free
}
fclose(f);
ft->next=NULL;

    if (NULL==fh) {
        ft->prev=NULL;
        fh=ft;
    } else {
        fb->next=ft;
        ft->prev=fb;
    }
    fb=ft;
    n++;
}
fclose(af);
printf("-----list-----\n");
for (ft=fh;NULL!=ft;ft=ft->next) {
    printf("%8d %s\n",ft->fl,ft->fn);
    if (NULL!=ft) fb=ft;
}
printf("-----free-----\n");
n--;
if (NULL!=fh) {
    for (ft=fb->prev;NULL!=ft;ft=ft->prev) {
        if (NULL!=ft->next->b) {
            printf("ft[%d]->b==%p\n",n,ft->next->b);
            free(ft->next->b);
        }
        if (NULL!=ft->next) {
            printf("ft[%d]==%p\n",n,ft->next);
            free(ft->next);
        }
        n--;
    }
    if (NULL!=fh->b) {
        printf("ft[0]->b==%p\n",fh->b);
        free(fh->b);
    }
    printf("ft[0]==%p\n",fh);
    free(fh);
}
return 0;

}
//C:\tmp\tmp\Debug>dir /a-d c:\tmp
// 驱动器 C 中的卷是 C_HD5_1
// 卷的序列号是 1817-D526
//
// c:\tmp 的目录
//
//找不到文件
//
//C:\tmp\tmp\Debug>tmp
//找不到文件
//-----list-----
//-----free-----
//
//C:\tmp\tmp\Debug>dir /a-d c:\tmp
// 驱动器 C 中的卷是 C_HD5_1
// 卷的序列号是 1817-D526
//
// c:\tmp 的目录
//
//2011-06-30 18:04 44,840 my_c.rar
//2011-06-30 17:18 1,036 err.frm
//2011-06-30 14:32 14,243 出租.txt
//2011-06-28 12:08 23,681 MSDN98书签.txt
// 4 个文件 83,800 字节
// 0 个目录 17,041,870,848 可用字节
//
//C:\tmp\tmp\Debug>tmp
//read my_c.rar
//ft[0]==00421800
//ft[0]->b==00520068
//read err.frm
//ft[1]==00421670
//ft[1]->b==0052AFC0
//read 出租.txt
//ft[2]==00421530
//ft[2]->b==00378F28
//read MSDN98书签.txt
//ft[3]==004213F0
//ft[3]->b==0052B3F8
//-----list-----
// 44840 c:\tmp\my_c.rar
// 1036 c:\tmp\err.frm
// 14243 c:\tmp\出租.txt
// 23681 c:\tmp\MSDN98书签.txt
//-----free-----
//ft[3]->b==0052B3F8
//ft[3]==004213F0
//ft[2]->b==00378F28
//ft[2]==00421530
//ft[1]->b==0052AFC0
//ft[1]==00421670
//ft[0]->b==00520068
//ft[0]==00421800
//
//C:\tmp\tmp\Debug>

codehat
codehat   2014.12.04 19:50

有些嵌入式系统确实malloc不到比较大的空间,但却可以定义很大的静态空间。
你完全可以定义一个静态的大数组,比如:
static typeof_list list_array[1024];

然后将malloc的语句改成从数组中取用元素。
当然,你得自己管理哪个元素已经使用了,哪个没有使用,简单的说就是自己实现一个类似malloc的功能。
这样的好处是显而易见的,静态空间得内存是专用的,不存在申请不到的情况,而且事实证明使用静态空间比malloc具有更高的执行速度。

原理就是这样了,具体的实现实在是不想动手,LZ也别做伸手党,习惯了难改。。。

Csdn user default icon
上传中...
上传图片
插入图片