常州模板网站建设价格,什么是网站维护费,贵阳哪家网站建设公司好,中装建设吧引言#xff1a; 链表是一种常见的数据结构#xff0c;它由一系列节点组成#xff0c;每个节点包含一个数据元素和一个指向下一个节点的指针。相比于数组#xff0c;链表具有动态性和灵活性#xff0c;可以高效地进行插入和删除操作#xff0c;但是查找操作的时间复杂度较…引言 链表是一种常见的数据结构它由一系列节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。相比于数组链表具有动态性和灵活性可以高效地进行插入和删除操作但是查找操作的时间复杂度较高。在C中我们可以通过定义一个节点结构体和一个链表类来实现链表。
技术实现 首先我们定义一个节点结构体Node包含一个数据元素data和一个指向下一个节点的指针next。这里使用了模板typename Element表示可以存储任意类型的数据元素。
templatetypename Element
struct Node
{Element data;NodeElement* next;
};接下来我们定义一个链表类LinkList包含一些常用的操作函数。构造函数LinkList()用于创建一个空链表构造函数LinkList(Element a[], int n)用于创建一个包含n个元素的链表析构函数~LinkList()用于释放链表的内存空间。getlenth()函数用于获取链表的长度getItem(int i)函数用于获取链表中第i个元素locate(Element x)函数用于查找元素x在链表中的位置insert(int i, Element x)函数用于在链表中第i个位置插入元素xremove(int i)函数用于删除链表中第i个元素empty()函数用于判断链表是否为空printList()函数用于打印链表中所有元素。
templatetypename Element
class LinkList
{
public:LinkList();LinkList(Element a[], int n);~LinkList();int getlenth();Element getItem(int i);int locate(Element x);void insert(int i, Element x);Element remove(int i);bool empty();void printList();
private:NodeElement* head;
}; 在LinkList类的实现中我们需要注意一些细节。首先在构造函数LinkList()中我们需要将头指针head初始化为空指针。在构造函数LinkList(Element a[], int n)中我们需要依次创建n个节点并将它们连接起来。在析构函数~LinkList()中我们需要依次删除所有节点并释放它们的内存空间。在insert(int i, Element x)函数中我们需要先找到第i-1个节点然后插入新节点并将它的next指针指向第i个节点。在remove(int i)函数中我们需要先找到第i-1个节点然后将它的next指针指向第i1个节点并删除第i个节点。
templatetypename Element
LinkListElement::LinkList() {head new NodeElement;head-next nullptr;
}//头插法初始化
templatetypename Element
LinkListElement::LinkList(Element a[], int n) {head-next nullptr;for (int i 0; i n; i) {LinkList s;s-data a[i];s-next head-next;head-next s;}
}templatetypename Element
LinkListElement::~LinkList() {while (head-next ! nullptr) {Element* p head-next;head-next p-next;delete p;}
}templatetypename Element
int LinkListElement::getlenth() {int count 0;LinkList* p head-next;while (p ! nullptr) {count;p p-next;}return count;
}templatetypename Element
Element LinkListElement::getItem(int i) {int j 0;LinkList* p head-next;while (j i) {j;p p-next;if (p nullptr) {printf( 不存在\n);break;}}return p-data;
}templatetypename Element
int LinkListElement::locate(Element x) {LinkList* p head-next;int j 0;while (p ! nullptr) {j;p p-next;if (p -data x) {return j;}}}templatetypename Element
void LinkListElement::insert(int i, Element x) {LinkList* p head;int j 0;while (p ! nullptr j i - 1) {p p-next;j;}if (p nullptr) printf(插入位置异常\n);else {LinkList s;s-data x;s-next p-next;p-next s;}
}templatetypename Element
Element LinkListElement::remove(int i) {LinkList p head;int j 0;while (p ! nullptr j i - 1) {p p-next;j;}if (p nullptr || p-next nullptr) {printf( 删除位置异常\n);}else {LinkList q p-next;int x q-data;p-next q-next;delete q;return x;}
}templatetypename Element
bool LinkListElement::empty() {return head-next nullptr;
}templatetypename Element
void LinkListElement::printList() {LinkList p head-next;while (p ! nullptr ) {printf(%d , p-data);p p-next;}printf( \n);
}最后我们可以在主函数中进行链表的测试。例如创建一个包含5个元素的链表插入一个元素删除一个元素并打印链表中所有元素。
int main()
{int a[] { 1, 2, 3, 4, 5 };LinkListint list(a, 5);list.printList(); // 1 2 3 4 5list.insert(3, 6);list.printList(); // 1 2 6 3 4 5list.remove(4);list.printList(); // 1 2 6 4 5return 0;
}
结尾 以上就是C实现链表的全部内容。链表是一种基础的数据结构掌握它的实现方法对于编写高效的算法和程序非常重要。
