C语言中链表主要应用于哪些实际问题的解决？

链表可以解决很多实际问题，比如数据结构课程上讲的多项式运算、求解约瑟夫问题， *** 作系统原理中的内存管理器实现等等。举一个在Windows通过链表搜索文件的实例，代码如下(vc6.0中编译通过)。

#include <stdio.h>

#include <windows.h>

struct DirList{

char table[256]

DirList *pNext

}

DirList *first,*newlist,*last

//加入文件夹链表

void AddList(char *list)

{

newlist=new DirList

strcpy(newlist->table,list)

newlist->pNext=NULL

//假如文件链表为空，那么第一个和最后一个节点都指向新节点

if(first==NULL)

{

first=newlist

last=newlist

}

//不为空，则原来最后一个节点指向新节点

else

{

last->pNext=newlist

last=newlist

}

}

//查找文件，并把找到的文件夹加入文件夹链表

void 册御FindFile(char *pRoad,char *pFile)

{

char FileRoad[256]={0}

char DirRoad[256]={0}

char FindedFile[256]={0}

char FindedDir[256]={0}

strcpy(FileRoad,pRoad)

strcpy(DirRoad,pRoad)

strcat(DirRoad,"\\*.*")

WIN32_FIND_DATA findData

HANDLE hFindFile

hFindFile=FindFirstFile(DirRoad,&findData)

if(hFindFile!=INVALID_HANDLE_VALUE)

{

do

{

if(findData.cFileName[0]=='.')

continue

//假如是文件夹，则假如文件夹列表

if(findData.dwFileAttributes&FILE_ATTRIBUTE_DIRECTORY)

{

strcpy(FindedDir,pRoad)

strcat(FindedDir,"\\")

strcat(FindedDir,findData.cFileName)

//加入文件夹列表

AddList(FindedDir)

memset(FindedDir,0x00,256)

}

//继续查找

}while(FindNextFile(hFindFile,&携衡findData))

}

strcat(FileRoad,"\\")

strcat(FileRoad,pFile)

//查找要查找的文件

hFindFile=FindFirstFile(FileRoad,&findData)

if(hFindFile!=INVALID_HANDLE_VALUE)

{

do

{ 

strcpy(FindedFile,pRoad)

strcat(FindedFile,"\\")

strcat(FindedFile,findData.cFileName)

//输出查找到的文件

printf("%s\n",FindedFile)

memset(FindedFile,0x00,256)

}while(FindNextFile(hFindFile,&findData))

}

}

int SeachFile(char *Directory,char *SeachFile)

{

DirList NewList

strcpy(NewList.table,Directory)

NewList.pNext=NULL

last=&NewList

first=&NewList 

while(true)

{

DirList *Find

//假如链表不为空，提取链表中的第一个节点，并把第一个节点指向原来第二个

if(first!=NULL)

{

//提取节点

Find=first

//并把第一个节点指向原来第二个

first=first->pNext

//在提取的节点的目录下查找辩姿做文件

FindFile(Find->table,SeachFile)

}

//为空则停止查找

else

{

printf("文件搜索完毕\n")

return 0

}

}

return 0

}

int main(int argc, char* argv[])

{

if (argc!=3) {

printf("程序名 文件目录 要搜索的文件名\n")

return 0

}

SeachFile(argv[1],argv[2])

return 0

}

执行效果如下，测试搜索c:\windows目录中的记事本程序notepad.exe。

顺序表

长度固定，必须在分配内存之前确定数组的长度。

存储空间连续，即允许元素的随机访问。

存储密度大，内存中存储的全部是数据元素。

要访问特定元素，可以使用索引访问，时间复杂度为 $O(1)$。

要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为 $O(n)$。

顺序表最主要的问题就是要求长度是固定的，可以使用倍增-复制的办法来支持动态扩容，将顺序表变成“可变长度”的。

这个办法不可避免的会浪费一些内存，因为数组的容量总是倍增的。而且每次扩容的时候，都需要将旧的数据全部复制一份，肯定会影响效率。不过实际上，这样做还是直接使用链表的效率要高。

链表

长度不固定，可以任意增删。

存储空间不连续，数据元素之间使用指针相连，每个数据元素只能访问周围的一个元素（根据单链表还是双链表有所不同）。

存储密度小，因为每个数据元素，此悉轿都需要额外存储一个指向下一元素的指针（双链表则需要两个指针）。

要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为 $O(n)$。在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动，因此时间复杂度为 $O(1)$。双链表还允许在特定的数据元素之前插入或删除元素。

静态链森肆表

为了弥补链表在内存分配上的不足，出现了静态链表这么一个折中的办法。静态链表比较类似于内存池，它会预先分配一个足够长的数组，之后链表节点都会保存在这个数组里，这样就不陆敏需要频繁的进行内存分配了。

当然，这个方法的缺点是需要预先分配一个足够长的数组，肯定会导致内存的浪费。数组不够长到不是什么大不了的，使用第一节的动态扩容方法就是了。

静态链表一般是由两个链表组成，一个保存数据的链表，一个空闲节点的链表，如图 所示。

块状链表

块状链表则是链表和顺序表的结合体，将多个顺序表以链表连接起来，如图 4所示。

这种数据结构的优点是结合了顺序表和链表的优点，长度可变，而且插入、删除也比较迅速（不必移动全部元素，只需要移动某一个或几个块中的元素），时间复杂度约为 $O(\sqrt n)$，内存的占用也不会像链表那么多。

但是缺点也很明显，就是实现起来过于复杂，要想让时间复杂度达到 $O(\sqrt n)$，需要令块的个数和每块中存储的元素个数都接近 $\sqrt n$ 才行，这进一步限制了块状链表的应用。

STL 中的 deque 结构比较类似于块状链表，只不过它记录每一块使用的仍然是数组，而不是链表。同时 deque 只允许在两端进行插入和删除，实现上就容易很多。

参考资料

CSDN：https://www.cnblogs.com/cyjb/p/Lists.html

链表和队列可以用于"饭店点菜"激贺乎,"ktv点歌",点好菜拍圆,"饭店点菜"的时候可以更新自己的订菜信息或取消定单,先点先上

栈可以用在"集装箱货物提取"中,新到的货物很有可能压在之前的货物上,取货物必须先拿下最上面的货物,体现了所谓"后进先出"的思想,也可以用"从运钞车中取钱"这些事情来明悉体现栈

---