首页 > 代码库 > 算法实例_链表结构 By:比方

算法实例_链表结构 By:比方

2024-07-15 00:49:47   237人阅读

前一章，我们说到了顺序表结构，而顺序表也存在一些的缺点。

 

在插入或者删除节点的时候，需要移动的数据比较大，如果顺序表结构比较大，有时候比较难以分配足够的连续存储空间，可能会导致内存分配失败，而导致无法存储。

 

而今天我们讲解的链表结构则可以很好的解决这个问题，链表的结构是一种动态存储分配的结构形式，可以根据需要动态申请所需的内存单元。

 

一．什么是链表结构？

a)         我们用head来表示头节点。

b)         数据部分保存的是存储的数据，地址地方指向下一个数据的起始部分，依次向下类推，一环套用一环，所以称之为链表。

c)         如果想查找值得的节点，则必须从链表头开始找起，这也算链表的不足之处吧。

d)         链表有多种结构，一种是单链表，而另外一种则是双链表，单链表如下图所示

e)         单链表只指向下一个节点，而双链表则拥有两个指针，一个分别指向他的下一个数据地址，另一个指向他的上一个数据节点。

 

首先是数据的准备，然后是定义一个节点结构和链表的结构，

其次是追加节点，插入节点，删除节点，计算链表的长度等

 1 // Listed.cpp : Defines the entry point for the console application. 2 // 3  4 #include "stdafx.h" 5 #include <stdlib.h> 6 #include <string.h> 7  8  9 typedef struct   //定义数据10 {11     char Key[12];12     char Name[20];13     int  Age;14 }Data;15 16 typedef struct  Node//定义链表的结构 17 {18     Data NodeData;   //数据链表19     struct Node *NextNode;20 21 }LType;

添加一个新的数据到链表中//尾部插入数据

 1 LType *ListAddEnd(LType *Head,Data NodeData) 2 { 3     LType *Node,*htemp; 4     if (!(Node = (LType*)malloc(sizeof(LType))))//申请需要的内存空间 5     { 6         printf("申请内存失败\r\n"); 7         return NULL; 8     } 9     else10     {11         Node->NodeData = http://www.mamicode.com/NodeData;                 //保存数据12         Node->NextNode = NULL;                     //设置为节点表尾为空13         if (Head == NULL)      //判断链表是不是空链表，头指针14         {15             Head = Node;16             return Head;17         }18         htemp = Head;19         while (htemp->NextNode != NULL)           //查找链表的最后一个20         {21             htemp = htemp->NextNode;22         }23         htemp->NextNode = Node;24         return Head;25     }26 27 }

添加一个新的数据到链表中//头部插入数据

 1 LType *ListAddFrist(LType *Head,Data NodeData) 2 { 3     LType *Node; 4     if (!(Node = (LType*)malloc(sizeof(LType))))//申请需要的内存空间 5     { 6         printf("申请内存失败\r\n"); 7         return NULL; 8     } 9     else10     {11         Node->NodeData = http://www.mamicode.com/NodeData;   //保存数据12         Node->NextNode = Head;       //指向头结点所指节点13         Head = Node;                 //头指针指向新增节点14 15         return Head;16     }17 }

//查找节点，比较关键字，从头指针开始查找

 1 LType *ListFindNode(LType *Head,char *Key)   //查找节点 2 { 3     LType *htemp; 4     htemp = Head;                                  //保存链表的头指针 5     while(htemp)                                   //继续向下寻找 6     {             7         if (strcmp(htemp->NodeData.Key,Key) == 0)  // 比较节点关键字是否相同 8         { 9             return htemp;                          // 返回该节点指针10         }11         htemp = htemp->NextNode;                   //返回下一个节点12     }13     return NULL;                                   //返回一个空的指针14 }

//在指定的节点那里插入新的节点,让原先的下一个节点指向新的节点头部，让新节点的下一个地址指向原先的下一个节点的头部

 1 LType *ListInstNode(LType *Head,char *FindKey,Data NodeData)   2 { 3     LType *Node,*Nodetemp; 4     if (!(Node = (LType*)malloc(sizeof(LType))))//申请需要的内存空间 5     { 6         printf("申请内存失败\r\n"); 7         return NULL; 8     } 9     10     Node->NodeData = http://www.mamicode.com/NodeData;                  //保存节点的数据11     Nodetemp = ListFindNode(Head,FindKey);      //如果找到了我们需要的数据，就在这里开始插入我们的新数据12     if (Nodetemp)13     {14         Node->NextNode = Nodetemp->NextNode;    //新插入的节点指关键节点的下一个节点。15         Nodetemp->NextNode = Node;              //设置关键节点指向新插入的节点。16     }17     else18     {19         printf("未找到插入的位置\r\n");20         free(Node);21     }22     return Head;23 }

//删除一个节点

 1 int ListDelect(LType *Head,char *Key) 2 { 3     LType *Node,*hTemp; 4     hTemp = Head;  //当前头指针赋值给零时变量 5     Node = Head; 6     while(hTemp) 7     { 8         if (strcmp(hTemp->NodeData.Key,Key) == 0)         //找到关键词 9         {10             Node->NextNode = hTemp->NextNode;              //前一个节点指向当前节点的下一个节点上去。11             free(hTemp);                                  //把找到的这个节点释放掉12             return 1;13         }14         else15         {16             Node = hTemp;                                 //指向当前节点17             hTemp = hTemp->NextNode;                      //指向下一个节点18         }19     }20     return 0; //未能删除掉节点21 22 }

//计算链表的长度

 1 int ListGetLength(LType *Head) 2 { 3     LType *hTemp; 4     int Len = 0; 5     hTemp = Head; 6     while(hTemp)                   //遍历整个链表 7                                                  8     { 9         Len++;10         hTemp = hTemp->NextNode;11     }12     return Len;                     //返回节点的数量13 14 }
 1 void ListAllNode(LType *Head)  //遍历所有的链表 2 { 3     LType *hTemp; 4     Data NodeData; 5     hTemp = Head; 6     printf("当前链表共有%d个节点,链表所有数据如下:\r\n",ListGetLength(Head)); 7     while(hTemp) 8     { 9         NodeData = http://www.mamicode.com/hTemp->NodeData;10         printf("关键词 : %s 名称 : %s 年龄 : %d\r\n",NodeData.Key,NodeData.Name,NodeData.Age);   //打印链表里面内容信息11         hTemp = hTemp->NextNode;12 13     }14 }

主函数测试代码

 1 int main(int argc, char* argv[]) 2 { 3     LType *Node,*Head = NULL; 4     Data NodeData; 5     char Key[10],FindKey[10]; 6  7     printf("链表测试案例 插入新的节点，输入(标识,名字，年龄)\r\n"); 8     do  9     {10         fflush(stdin);11         scanf("%s ",NodeData.Key);12         if (strcmp(NodeData.Key,"0") == 0)13         {14             break;15         }16         else{17             scanf("%s %d",NodeData.Name,&NodeData.Age);18             Head = ListAddEnd(Head,NodeData);19 20         }21     } while (1);22 23     ListAllNode(Head);  //显示所有节点24 25     26 27     printf("插入节点（关键字 标识 姓名 年龄）用空格分开\r\n");28     scanf("%s %s %s %d",&FindKey,NodeData.Key,NodeData.Name,NodeData.Age);29     ListAllNode(Head);  //显示所有节点30 31 32     system("pause");33     return 0;34 }

 附件地址:http://pan.baidu.com/s/1mgmguRA


联系
我们