当前位置：首页 > news >正文

商业网站的建设流程/市场营销公司排名

news 2025/8/19 16:04:09

商业网站的建设流程,市场营销公司排名,长沙零基础学快速建站,软件开发工程师级别最近在看算法导论， 觉得有些东西可以记录下-》这篇文章只是为了记录。 1. 链表的特点链表是一个非常常用的数据结构，其有如下几个基本特点： 1. 其内存空间是线性但是非连续的。 2. 对于插入和删除有O(1)的时间复杂度 3. 不能被索引化 4. 查找…

最近在看算法导论，觉得有些东西可以记录下-》这篇文章只是为了记录。

1. 链表的特点

链表是一个非常常用的数据结构，其有如下几个基本特点：

1. 其内存空间是线性但是非连续的。

2. 对于插入和删除有O(1)的时间复杂度

3. 不能被索引化

4. 查找慢

2. 简单的链表实现

2.1 链表的内存模型

一个典型的双向链表包含一个关键字域，一个前驱，一个后继。

其结构源码如下所示：

 typedef struct _List 
{_List*	prev;int		value;_List*	next;
}List;

2.2 链表的创建

下面是一个创建n个节点的链表。

 List* list_create( int n)
{List *head , *current;head = new List;head->value = 0;current = head;current->prev = NULL;List* temp;for (int i = 1; i < n; ++i){// i0temp =  new List;temp->value = i;temp->prev = current;current->next = temp;//i1current = current->next;}current->next = NULL;return head;
}

2.3 节点的查找

 List* list_find(List*list, int value)
{List* current = list;while (current->next != NULL && current->value != value)current = current->next;return current;
}

时间复杂度为O(n), 这里能看出链表的查找为什么慢了。

2.4 链表的插入

 List* list_insert(List* list, List* current, List* node)
{if (current->prev == NULL){current->prev = node;node->prev = NULL;node->next = current; return node;}else if (current->next == NULL){current->next = node;node->prev = current;node->next =NULL;}else{List* temp = current->next; node->prev =current;node->next = temp; current->next = node; temp->prev = node;}return list;
}

时间复杂度为O(1).

2.5 链表的删除

 void list_delete(List*node)
{if (node->prev == NULL){	node->next->prev = NULL;node->next = NULL;delete node;}else if (node->next == NULL){node->prev->next = NULL;node->prev = NULL;delete node;}else{node->prev->next = node->next;node->next->prev = node->prev;node->prev = NULL;node->next = NULL;delete node;}
}

时间复杂度为O(1);

2.6 测试代码

 #include "stdafx.h"
#include "List.h"
#include <iostream>
using namespace std; int _tmain(int argc, _TCHAR* argv[])
{//test for createList* listnode = list_create(10); //test for findcout<< "find" <<endl;List* findnode = list_find(listnode, 5);cout<< findnode->value<<endl; // test for insertList* newnode = new List;newnode->value    = 100;cout << "insert middle" <<endl;List* newlsit = list_insert(listnode,findnode, newnode); cout << "insert begin"<<endl;newlsit = list_insert(listnode,listnode,newnode);for (int i = 0; i < 11; ++i){cout<<newlsit->value<<endl;newlsit = newlsit->next;}//test for deletecout <<"delete"<<endl;list_delete(findnode);for (int i = 0; i < 11; ++i){cout<<listnode->value<<endl;listnode = listnode->next;}return 0;
}