网站设计大作业,毕业设计查资料的网站,淘宝页面设计模板,上海市工程建设目录
链表的分类
带头双向循环链表的实现
带头双向循环链表的结构
带头双向循环链表的结构示意图
空链表结构示意图
单结点链表结构示意图 多结点链表结构示意图
链表创建结点
双向链表初始化
销毁双向链表
打印双向链表 双向链表尾插
尾插函数测试
双向链表头插
…目录
链表的分类
带头双向循环链表的实现
带头双向循环链表的结构
带头双向循环链表的结构示意图
空链表结构示意图
单结点链表结构示意图 多结点链表结构示意图
链表创建结点
双向链表初始化
销毁双向链表
打印双向链表 双向链表尾插
尾插函数测试
双向链表头插
头插函数测试 双向链表尾删
尾删函数测试
双向链表头删
头删函数测试
双向链表查找
双向链表pos位置前插
插入函数测试 双向链表删除pos位置的结点
删除函数测试
利用 ListInsert()函数改造头插尾插函数
尾插函数改造版本
头插函数改造版本
利用ListEarse()函数改造头删 尾删函数
头删函数改造版本
尾删函数改造版本
计算双向链表长度 链表的分类
单向/双向 单向列表每一个结点结构中只保存下一结点的地址所以很难从后一结点找到前一节点 双向列表每一个结点结构中不仅保存下一结点的地址还保存上一节点的地址方便寻找前一节点和后一节点 带头/不带头 带头在头结点之前有一个哨兵位结点哨兵位的数据域不存储有效数据指针域指向头结点 不带头没有哨兵位结点尾插尾删考虑头结点情况 循环/非循环 循环头结点与尾结点相连 非循环头结点与尾结点不相连 上述情况相互组合共有8种情况, 实际中使用的链表数据结构都是带头双向循环链表带头双向循环链表虽然结构复杂但是其结构具有很多优势实现反而简单 带头双向循环链表的实现
带头双向循环链表的结构
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//前址域-存放前一个结点的地址LTDataType data;//数据域struct ListNode* next;//后址域-存放后一个结点的地址
}ListNode;
逻辑图 物理图 带头双向循环链表的结构示意图 空链表结构示意图 由图可知head-prevhead; head-nexthead; 单结点链表结构示意图 由图可知 head-nextFirstNode; head-prevFirstNode; FirstNode-prevhead; FirstNode-nexthead; 多结点链表结构示意图 由图可知: head-nextfirstnode; head-prevtail; tail-nexthead; firstnode-prevhead; 链表创建结点
//创建链表结点,返回链表结点地址
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc failed:);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}
双向链表初始化 注函数调用时得到动态开辟的链表空间起始地址的两种方案如下 方案一 当传参时为链表结点的地址函数的形参设计为二级指针只有通过传址调用可以将动态开辟的链表的起始地址带出函数 方案二 设计函数的返回类型为结点指针返回动态开辟的链表结点指针如此可以得到链表空间的起始地址 //初始化链表(空链表)
ListNode* ListInit()
{//创建哨兵位结点ListNode* head BuyListNode(0);//0不是有效数据//初始化哨兵位结点的指针域head-next head;head-prev head;return head;
}
销毁双向链表 循环遍历释放结点包含哨兵位结点释放前保存下一结点地址避免地址丢失 //销毁链表,包含哨兵位结点
void DestoryList(ListNode* phead)
{assert(phead);//创建寻址指针ListNode* cur phead;//断开循环链表phead-prev-next NULL;while (cur ! NULL){//记录下一结点地址ListNode* next cur-next;//释放当前结点free(cur);//寻找下一节点cur next;}return;
}
打印双向链表 循环遍历链表打印数据不显示哨兵位结点的数据域以哨兵位头结点作为结束标志 void PrintList(ListNode* phead)
{assert(phead ! NULL);ListNode* cur phead-next;printf(phead);while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
} 双向链表尾插 尾插先找尾哨兵位的前址域即为尾结点即tailhead-prev;当链表为空时连接的逻辑关系相同创建三个指针变量按照新结点的前址域指向谁谁指向新结点新结点的后址域指向谁谁指向新结点进行连接 void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);//寻找尾结点ListNode* tail phead-prev;//创建新结点ListNode* newnode BuyListNode(x);//尾插newnode-prev tail;tail-next newnode;newnode-next phead;phead-prev newnode;
}
尾插函数测试
void Test1()
{ListNode* plistListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);PrintList(plist);
}
int main()
{Test1();return 0;
}
运行结果 双向链表头插 头插前先保存哨兵位结点的下一节点即原先真正的首节点按照按照新结点的前址域指向谁谁指向新结点新结点的后址域指向谁谁指向新结点进行连接从而实现头插链表为空时头插逻辑仍然相同 //链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);//保存原先的首节点ListNode* firstnode phead-next;//创建新结点ListNode* newnode BuyListNode(x);//头插newnode-prev phead;phead-next newnode;newnode-next firstnode;firstnode-prev newnode;
}头插函数测试
void Test2()
{ListNode* plist ListInit();ListPushFront(plist, 10);ListPushFront(plist, 20);ListPushFront(plist, 30);ListPushFront(plist, 40);ListPushFront(plist, 50);PrintList(plist);}
int main()
{Test2();return 0;
}
运行结果 双向链表尾删 链表中只剩哨兵位结点此时链表为空不再进行尾删尾删前记录前一节点的地址方便修改逻辑关系 //链表尾删
void ListPopBack(ListNode* phead)
{assert(phead);//链表中只剩哨兵位的情况assert(phead-next ! phead);//查找尾结点ListNode* tail phead-prev;//保存尾结点的上一节点ListNode* tailprev tail-prev;//尾删free(tail);//建立链接关系tailprev-next phead;phead-prev tailprev;}
尾删函数测试
void Test3()
{ListNode* plist ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);PrintList(plist);ListPopBack(plist);PrintList(plist);ListPopBack(plist);PrintList(plist);ListPopBack(plist);PrintList(plist);}
int main()
{Test3();return 0;
}
运行结果 双向链表头删 链表中只剩哨兵位结点此时链表为空不再进行头删头删前记录下一节点的地址方便修改逻辑关系 //链表头删
void ListPopFront(ListNode* phead)
{assert(phead);//只剩哨兵位,不再头删assert(phead-next ! phead);//保存原先的首节点ListNode* head phead-next;//保存首结点的下一节点ListNode* headnext phead-next-next;//头删free(head);//建立链接关系headnext-prev phead;phead-next headnext;}
头删函数测试
void Test4()
{ListNode* plist ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);PrintList(plist);ListPopFront(plist);PrintList(plist);ListPopFront(plist);PrintList(plist);ListPopFront(plist);PrintList(plist);
}
int main()
{Test4();return 0;
}
运行结果 双向链表查找 循环遍历链表从首节点开始遍历以哨兵位头结点作为结束标志根据数据域进行查找找到返回数据域的结点地址找不到返回空指针 ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);//创建遍历指针ListNode* cur phead-next;//遍历链表while (cur ! phead){if ((cur-data) x){//找到返回下标return cur;}cur cur-next;}//没找到返回空指针return NULL;
}
双向链表pos位置前插 前插时保存pos位置的前一个节点方便修改逻辑关系按照按照新结点的前址域指向谁谁指向新结点新结点的后址域指向谁谁指向新结点进行链接 void ListInsert(ListNode* pos, LTDataType x)
{assert(pos ! NULL);//创建新结点ListNode* newnode BuyListNode(x);//保存pos位置的前一个结点ListNode* posprev pos-prev;//前插newnode-prev posprev;posprev-next newnode;newnode-next pos;pos-prev newnode;
}
插入函数测试
void Test5()
{ListNode* plist ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);int x 0;printf(请输入查找的数值:);scanf(%d, x);ListNode* pos ListFind(plist, x);if (pos NULL){printf(要查找的值不存在\n);return;}//在查找到数值前插入100ListInsert(pos, 100);PrintList(plist);}
int main()
{Test5();return 0;
}
运行结果 双向链表删除pos位置的结点 链表删除pos位置处的结点前先保存前结点和后结点的地址方便处理链接关系 //双向链表删除pos位置
void ListEarse(ListNode* pos)
{assert(pos);//保存pos位置处的前一个和后一个结点;ListNode* posprev pos-prev;ListNode* posnext pos-next;//删除pos位置结点free(pos);//建立前后节点的链接关系posprev-next posnext;posnext-prev posprev;}
删除函数测试
void Test6()
{ListNode* plist ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);PrintList(plist);int x 0;printf(请输入删除的数值:);scanf(%d, x);ListNode* pos ListFind(plist, x);if (pos NULL){printf(要删除的值不存在\n);return;}ListEarse(pos);PrintList(plist);
}
int main()
{Test6();return 0;
}
运行结果 利用 ListInsert()函数改造头插尾插函数 尾插函数改造版本
void Listpushback(ListNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
} 头插函数改造版本
void Listpushfront(ListNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
}
利用ListEarse()函数改造头删 尾删函数 头删函数改造版本
void Listpopfront(ListNode* phead)
{assert(phead);//只剩哨兵位,不再头删assert(phead-next ! phead);ListEarse(phead-next);
} 尾删函数改造版本
void Listpopback(ListNode* phead)
{assert(phead);//链表中只剩哨兵位的情况assert(phead-next ! phead);ListEarse(phead-prev);
}
计算双向链表长度
int ListLength(ListNode* phead)
{assert(phead);int size 0;ListNode* cur phead-next;while (cur ! phead){size;cur cur-next;}return size;
}
