c++学习笔记—单链表基本操作的实现
用c++语言实现的单链表基本操作,包括单链表的创建(包括头插法和尾插法建表)、结点的查找、删除、排序、打印输出、逆置、链表销毁等基本操作。
IDE:vs2013
具体实现代码如下:
- #include "stdafx.h"
- #include <malloc.h>
- #include <iostream>
- using namespace std;
- typedef struct Lnode
- {
- int data;
- struct Lnode *next;
- }*node;
- node head_creat() //头插法建立单链表
- {
- node head = (struct Lnode *)malloc(sizeof(struct Lnode));
- head->next = NULL;
- node p;
- int temp;
- while (cin >> temp)
- {
- p = (node)malloc(sizeof(struct Lnode));
- p->data = temp;
- p->next = head->next;
- head->next=p;
- }
- return head;
- }
- bool search(node h, int target) //查找某元素是否在链表中
- {
- int flag = 0;
- node p = h->next;
- if (h->next == NULL)
- return false;
- for (; p != NULL;)
- {
- if (p->data == target)
- {
- flag = 1;
- break;
- }
- else
- p++;
- }
- if (flag)
- return true;
- else
- return false;
- }
- node back_creat() //尾插法建立单链表
- {
- node head = (struct Lnode *)malloc(sizeof(struct Lnode));
- head->next = NULL;
- node p;
- node r = head;
- int temp;
- while (cin >> temp)
- {
- p = (node)malloc(sizeof(struct Lnode));
- p->data = temp;
- r->next=p;
- r = p;
- }
- r->next = NULL;
- return head;
- }
- void print(node h) //打印单链表
- {
- node p = h->next;
- while (p)
- {
- cout << p->data << endl;
- p = p->next;
- }
- }
- node delete_node(node h,int del_val) //删除指定值的节点
- {
- node p = h->next;
- node q = h;
- node r=NULL;
- while (p)
- {
- if (p->data == del_val)
- {
- r = p;
- p = p->next;
- q->next = p;
- free(r);
- }
- else
- {
- q = p;
- p = p->next;
- }
- }
- return h;
- }
- node sort(node h) //对链表进行排序(降序)
- {
- node p=h->next;
- if (p->next == NULL)
- return h;
- for (; p != NULL; p = p->next)
- {
- for (node q = p->next; q != NULL; q = q->next)
- {
- int temp;
- if (p->data > q->data)
- {
- temp = p->data;
- p->data = q->data;
- q->data = temp;
- }
- }
- }
- return h;
- }
- node reverse(node h) //逆置链表
- {
- node p, q;
- p = h->next;
- h->next = NULL;
- while (p)
- {
- q = p;
- p = p->next;
- q->next = h->next;
- h->next = q;
- }
- return h;
- }
- void destroy_List(node head) //销毁链表
- {
- if (NULL == head)
- {
- return;
- }
- if (NULL == head->next)
- {
- free(head);
- head = NULL;
- return;
- }
- node p = head->next;
- while (NULL != p)
- {
- node tmp = p;
- p = p->next;
- free(tmp);
- }
- free(head);
- head = NULL;
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- cout << "---------------构造链表-------------" << endl;
- node h = back_creat();
- cout << "---------------打印链表-------------" << endl;
- print(h);
- //cout << "-----------删除指定值后打印链表-----" << endl;
- //h = delete_node(h, 2);
- //print(h);
- cout << "-----------排序后打印链表------------" << endl;
- h = sort(h);
- print(h);
- cout << "-----------逆置后打印链表------------" << endl;
- h = reverse(h);
- print(h);
- destroy_List(h);
- return 0;
- }
运行结果:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。