6.带头双向循环链表的实现（接口实现代码）
6.1 带头双向循环链表的定义
typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; //前驱 LTDataType data; struct ListNode* next; //后继 }ListNode;
6.2 带头双向循环链表的初始化
ListNode* ListInit() //初始化链表 { ListNode *head = (ListNode*) malloc(sizeof (ListNode)); if(head == NULL) { perror("初始化开辟空间失败"); exit(-1); } head->data = -1; head->prev = head; head->next = head; return head; }
6.3 带头双向循环链表的销毁
void ListDestory(ListNode* pHead) //销毁 { int len = ListSize(pHead) + 1; while (len--) ListPopFront(pHead); }
6.4 带头双向循环链表的打印
void ListPrint(ListNode* phead) //打印 { assert(phead); ListNode *phead_next = phead->next; printf("phead <-> "); while(phead_next != phead) { printf("%d <-> ",phead_next->data); phead_next = phead_next->next; } printf("phead\n"); }
6.5 带头双向链表的增加节点
ListNode* BuyListNode(LTDataType x) //增加节点 { ListNode *newnode = (ListNode*) malloc(sizeof (ListNode)); if(newnode == NULL) { perror("增加节点开辟空间失败"); exit(-1); } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
6.6 带头双向循环链表的在pos之前插入
void ListInsert(ListNode* pos,LTDataType x)//在pos位置之前插入 { assert(pos); ListNode *newnode = BuyListNode(x); ListNode *pos_prev = pos->prev; pos_prev->next = newnode; newnode->prev = pos_prev; newnode->next = pos; pos->prev = newnode; }
6.7 带头双向循环链表删除pos位置
void ListErase(ListNode* pos)//删除pos位置的节点 { assert(pos); ListNode *pos_next = pos->next; ListNode *pos_prev = pos->prev; pos_prev->next = pos_next; pos_next->prev = pos_prev; free(pos); }
6.8 带头双向循环链表的尾插尾删
void ListPushBack(ListNode* phead,LTDataType x)//尾插 { assert(phead); ListInsert(phead,x); } void ListPopBack(ListNode* phead)//尾删 { assert(phead); ListErase(phead->prev); }
6.9 带头双向循环链表的头插头删
void ListPushFront(ListNode* phead,LTDataType x)//头插 { assert(phead); ListInsert(phead->next,x); } void ListPopFront(ListNode* phead)//头删 { assert(phead); ListErase(phead->next); }
6.10 带头双向循环链表的长度求解
int ListSize(ListNode* phead)//求链表的长度 { assert(phead); int len = 0; ListNode *phead_next = phead->next; while(phead != phead_next) { len++; phead_next = phead_next->next; } return len; }
6.11 带头双向循环链表的寻找某一节点
ListNode*ListFind(ListNode* phead, LTDataType num)//寻找某一个节点 { assert(phead); ListNode *find = phead->next; while(find != phead) { if(find->data == num) { return find; } find = find->next; } return NULL; }
7. 顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
存储空间上 |
物理上一定连续 | 逻辑一定连续，物理不一定 |
任意位置插入或者删除 元素 |
需要覆盖数据 | 通过指针就能找到 |
插入 |
动态顺序表需要扩容 | 没有容量概念，需要一个给一个 |
缓存利用率 |
高 | 低 |
