用C++语言和类实现单链表,含头结点
属性包括:data数据域、next指针域
操作包括:插入、删除、查找
注意:单链表不是数组,所以位置从1开始对应首结点,头结点不放数据
类定义参考
- #include
- using namespace std;
- #define ok 0
- #define error -1
-
- // 链表结点定义
- class ListNode
- {
- public:
- int data;
- ListNode *next;
- ListNode() {next = NULL;}
- };
- // 带头结点的单链表类定义
- class LinkList
- {
- public:
- ListNode *head;
- int len;
- // 操作定义
- LinkList();
- ~LinkList();
- ListNode *LL_index(int i); // 返回第i个结点的指针,如果不存在返回NULL
- int LL_get(int i); // 获取第i个元素的数据
- int LL_insert(int i, int item); // 把数值item插入第i个位置
- int LL_del(int i); // 删除第i个结点
- void LL_display(); // 输出单链表的内容
- };
- LinkList::LinkList()
- {
- head = new ListNode();
- len = 0;
- }
- LinkList::~LinkList()
- {
- ListNode *p, *q;
- p = head;
- while(p != NULL)
- {
- q = p;
- p = p->next;
- delete q;
- }
- len = 0;
- head = NULL;
- }
- void LinkList::LL_display()
- {
- ListNode *p;
- p = head->next;
- while(p)
- {
- cout << p->data << ' ';
- p = p->next;
- }
- cout << endl;
- }
数据之间用空格隔开,
第1行输出创建后的单链表的数据
每成功执行一次操作(插入或删除),输出执行后的单链表数据
每成功执行一次查找,输出查找到的数据
如果执行操作失败(包括插入、删除、查找等失败),输出字符串error,不必输出单链表
- #include
- using namespace std;
- #define ok 0
- #define error -1
-
- // 链表结点定义
- class ListNode
- {
- public:
- int data;
- ListNode* next;
- ListNode() { next = NULL; }
- };
- // 带头结点的单链表类定义
- class LinkList
- {
- public:
- ListNode* head;
- int len;
- // 操作定义
- LinkList();
- ListNode* LL_index(int i) {}; // 返回第i个结点的指针,如果不存在返回NULL
- void LL_get(int i) {
- if (i <= 0 || i > len ) {
- cout << "error" << endl;
- }
- else {
- ListNode* p;
- p = head;
- for (int j = 0; j < i; j++) {
- p = p->next;
- }
- cout << p->data << endl;
- }
- }; // 获取第i个元素的数据
- void LL_insert(int i, int item) {
- if (i <= 0 || i > len + 1) {
- cout << "error" << endl;
- }
- else {
- ListNode* p;
- p = head;
- for (int j = 1; j < i; j++) {
- p = p->next;
- }
- ListNode* s = new ListNode;
- s->data = item;
- s->next = p->next;
- p->next = s;
- p = s;
- len++;
- LL_display();
- }
- }; // 把数值item插入第i个位置
- void LL_del(int i) {
- if (i <= 0 || i > len) {
- cout << "error" << endl;
- }
- else {
- ListNode* p;
- p = head;
- for (int j = 1; j < i; j++) {
- p = p->next;
- }
- p->next = p->next->next;
- LL_display();
- len--;
- }
- }; // 删除第i个结点
- void LL_display(); // 输出单链表的内容
- };
- LinkList::LinkList()
- {
- head = new ListNode();
- len = 0;
- }
- void LinkList::LL_display()
- {
- ListNode* p;
- p = head->next;
- while (p)
- {
- cout << p->data << ' ';
- p = p->next;
- }
- cout << endl;
- }
-
- int main() {
- int t;
- int data;
- cin >> t;
- LinkList L;
- ListNode* p;
- p = L.head;
- while (t--) {
- ListNode* s = new ListNode;
- L.len++;
- cin >> data;
- s->data = data;
- s->next = p->next;
- p->next = s;
- p = p->next;
- }
- L.LL_display();
- int i, item;
- cin >> i >> item;
- L.LL_insert(i, item);
- cin >> i >> item;
- L.LL_insert(i, item);
- cin >> i;
- L.LL_del(i);
- cin >> i;
- L.LL_del(i);
- cin >> i;
- L.LL_get(i);
- cin >> i;
- L.LL_get(i);
- }