C++程序设计——手写链表（链表创建遍历与删除结点的相关源代码）
一些手写链表的初阶程序源代码：一、链表的建立与访问二、链表添加与遍历三、 链表-正负值判断四、单向链表删除重复节点五、删除所有数据为e的元素
学校程序设计课程在教完指针、struct结构体之后，紧接着教了链表的实现~
前言
本篇博客并不是聚焦于手写链表的相关知识，而是将学完链表之后的相关课后作业的源代码搬运上来，关于链表的创建、遍历、元素删除等等，通过阅读代码即可很好掌握。
一、链表的建立与访问
【问题描述】1）编写链表创建函数node* CreateList(int array[], int n)，根据数组array创建一个链表，并返回链表头节点指针；2）编写链表插入函数node* Insert(node* head, int a, int e)，在节点 a 前面插入节点 e，若a不存在，则不插入。
#include <iostream>
using namespace std;
struct node
{
int data;
node* next;
};
node* CreateList(int array[], int n);
void PrintList(node* head);
node* Insert(node* head, int a, int e);
int main()
{
// 输入数据
int array[100], n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> array[i];int a, e;
cin >> a >> e;
// 创建链表
node* h = CreateList(array, n);
// 插入节点
h = Insert(h, a, e);
PrintList(h);
return 0;
}
node* CreateList(int array[], int n)
{
}
void PrintList(node* head)
{
for (node* pi = head; pi != NULL; pi = pi->next)
cout << pi->data << "->";
cout << endl;
}
node* Insert(node* head, int a, int e)
{
}输入输出样例：1组
#1
- 样例输入：
4 10 20 30 40 10 15- 样例输出：
15->10->20->30->40->
#include <iostream>
using namespace std;
struct node
{
int data;
node* next;
};
node* CreateList(int array[], int n);
void PrintList(node* head);
node* Insert(node* head, int a, int e);
int main()
{
// 输入数据
int array[100], n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> array[i];
//cout<<array[i]<<' ';
}
int a, e;
cin >> a >> e;
//cout<<a<<' '<<e<<'\n';
// 创建链表
node* h = CreateList(array, n);
// 插入节点
h = Insert(h, a, e);
PrintList(h);
return 0;
}
node* CreateList(int array[], int n)
{
node* head=NULL;
node* tail=NULL;
for(int i=0;i<n;++i)
{
node* tmp=new node;
tmp->data=array[i];
tmp->next=NULL;
if(tail==NULL)
{
head=tail=tmp;
}
else
{
tail->next=tmp;
tail=tmp;
}
}
return head;
}
void PrintList(node* head)
{
for (node* pi = head; pi != NULL; pi = pi->next)
cout << pi->data << "->";
cout << endl;
}
node* Insert(node* head, int a, int e)
{
node* tmp=new node;
tmp->data=e;
if(head->data==a)
{
tmp->next=head;
head=tmp;
return head;
}
for(node* index=head;index->next!=NULL;index=index->next)
{
if(index->next->data==a)
{
tmp->next=index->next;
index->next=tmp;
return head;
}
}
return head;
}二、链表添加与遍历
【问题描述】1）编写链表添加函数void Insert(node* head, int data)，为数据data创建一个节点并将该节点添加到以head为头节点的链表最末尾；2）编写链表打印函数Print(node* head)，顺序打印以head为头节点的链表；3）编写测试函数main()从键盘读入一组数据，然后调用Insert函数用这些数据创建一个链表，再调用Print函数输出刚刚创建的链表
【输入样例】
5
1 3 5 7 9
【输出样例】
1 3 5 7 9
输入输出样例：1组
#1
- 样例输入：
5 1 3 5 7 9- 样例输出：
1 3 5 7 9
#include<iostream>
#include<cstdio>
using namespace std;
struct Node{
int value;
Node* next;
};
int main()
{
int n;
cin>>n;
int m;
Node* head=NULL;
Node* tail=NULL;
for(int i=0;i<n;++i)
{
cin>>m;
Node* tmp=new Node;
tmp->value=m;
if(tail==NULL)
{
head=tail=tmp;
}else{
tail->next=tmp;
tail=tmp;
tail->next=NULL;
}
}
for(Node* index=head;index!=NULL;index=index->next)
{
cout<<index->value<<" ";
}
return 0;
} PS:这题好像没按照要求编写函数~
三、 链表-正负值判断
【题目描述】
#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int data;
struct node *nextPtr;
};
void computingList(node * head)
{
int positive=0,negtive=0,zero=0;
/**********Program**********/
/********** End **********/
}
struct node *createList(void)
{
node *head=NULL, *p1, *p2;
int i;
int a[10] = {-1,3,4,0,9,4,11,-6,2,-10};
head=p2=p1= new node;
p1->data = a[0];
for (i=1; i<10; i++)
{
p1= new node;
p1->data = a[i];
p2->nextPtr=p1;
p2=p1;
}
p2->nextPtr=NULL;
return (head);
}
int main()
{
struct node *head;
head = createList();
computingList(head);
return 0;
}
请编写函数void computingList(node * head)，对head
指向的单向链表，分别统计结点的data成员值为负数、0、
正数的结点个数分别存入变量negtive、zero、positive中
分别输出negtive、zero、positive的值。
由于答案是固定的，请忽略样例中的输入输出
输入输出样例：1组
#1
- 样例输入：0
- 样例输出：0
#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int data;
struct node *nextPtr;
};
void computingList(node * head)
{
int positive=0,negtive=0,zero=0;
/**********Program**********/
for(node* index=head;index!=NULL;index=index->nextPtr)
{
if(index->data<0)negtive++;
else if(index->data>0)positive++;
else zero++;
}
cout<<negtive<<' '<<zero<<' '<<positive;
/********** End **********/
}
struct node *createList(void)
{
node *head=NULL, *p1, *p2;
int i;
int a[10] = {-1,3,4,0,9,4,11,-6,2,-10};
head=p2=p1= new node;
p1->data = a[0];
for (i=1; i<10; i++)
{
p1= new node;
p1->data = a[i];
p2->nextPtr=p1;
p2=p1;
}
p2->nextPtr=NULL;
return (head);
}
int main()
{
struct node *head;
head = createList();
computingList(head);
return 0;
}
四、单向链表删除重复节点
删除单向链表中的重复结点，如果链表中存在重复结点（除next指针
外的其它数据成员的值相同）时，保留离链首最近
的结点。该链表中固定只有8个元素， 输入是八个整数。
注意看链表的创建函数
Node * createList(int a[], int len)
{
Node *head = NULL;
if(len<1)
return head;
for(int i=0;i<len;i++)
{
Node *tmp = new Node;
tmp->num = a[i];
tmp->next = head;
head = tmp;
}
return head;
}输入输出样例：1组
#1
- 样例输入：
2 6 4 2 7 9 5 12- 样例输出：
12 5 9 7 2 4 6
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#include<stack>
#include<cstdlib>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
struct Node{
Node* next;
int num;
};
Node * createList(int a[], int len)
{
Node *head = NULL;
if(len<1)
return head;
for(int i=0;i<len;i++)
{
Node *tmp = new Node;
tmp->num = a[i];
tmp->next = head;
head = tmp;
}
return head;
}
int a[8];
Node *deleteMultiElement(Node* head)
{
bool in[100005];
memset(in,false,sizeof(in));
Node* i=head,*j=head;
while(true)
{
in[i->num]=true;
j=j->next;
while(j!=NULL&&in[j->num])
{
j=j->next;
}
i->next=j;
i=j;
if(i==NULL)break;
}
return head;
}
void printList(Node *head)
{
Node *index=head;
while(index!=NULL)
{
cout<<index->num<<' ';
index=index->next;
}
}
int main()
{
for(int i=0;i<8;++i)cin>>a[i];
Node *head=createList(a,8);
Node *head2=deleteMultiElement(head);
printList(head2);
return 0;
}五、删除所有数据为e的元素
【问题描述】1）编写链表创建函数node* CreateList(int array[], int n)，根据数组array创建一个链表，并返回链表头节点指针；2）编写链表删除函数node* Delete(node* head, int e)，删除所有数据为e的元素。
#include <iostream>
using namespace std;
struct node
{
int data;
node* next;
};
node* CreateList(int array[], int n);
void PrintList(node* head);
node* Delete(node* head, int e);
int main()
{
// 输入数据
int array[100], n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> array[i];
int e;
cin >> e;
// 创建链表
node* h = CreateList(array, n);
// 删除节点
h = Delete(h, e);
PrintList(h);
return 0;
}
node* CreateList(int array[], int n)
{
}
void PrintList(node* head)
{
for (node* pi = head; pi != NULL; pi = pi->next)
cout << pi->data << "->";
cout << endl;
}
node* Delete(node* head, int e)
{
}
输入输出样例：1组
#1
- 样例输入：
5 10 20 30 20 40 20- 样例输出：
10->30->40->
#include <iostream>
using namespace std;
struct node
{
int data;
node* next;
};
node* CreateList(int array[], int n)
{
node* head=new node;
head->next=NULL;
node* ptrList=head;
for(int i=0;i<n;++i)
{
node* index=new node;
index->next=NULL;
index->data=array[i];
ptrList->next=index;
ptrList=ptrList->next;
}
return head->next;
}
void PrintList(node* head)
{
node* ptrList=head;
while(ptrList!=NULL)
{
cout<<ptrList->data<<"->";
ptrList=ptrList->next;
}
}
node* Delete(node* head, int e)
{
node* i=head;
while(i!=NULL&&i->data==e)
{
i=i->next;
}
node* head2=i;
node* j=i;
while(true)
{
j=j->next;
while(j!=NULL&&j->data==e)
{
j=j->next;
}
i->next=j;
i=j;
if(j==NULL)break;
}
return head2;
}
int main()
{
// 输入数据
int array[100], n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> array[i];
int e;
cin >> e;
// 创建链表
node* h = CreateList(array, n);
// 删除节点
h = Delete(h, e);
PrintList(h);
return 0;
}
/*
node* CreateList(int array[], int n)
{
}
void PrintList(node* head)
{
for (node* pi = head; pi != NULL; pi = pi->next)
cout << pi->data << "->";
cout << endl;
}
node* Delete(node* head, int e)
{
}
*/总结
以上就是课后安排的五道题目。
手写链表的创建、遍历、删除等等，对咱们新手来说还是比较难的，遇到指针出现死循环、错误访问等等情况也都是很常见的错误。
其实原本想把课上的知识点予以整理，奈何我太懒了，知识点也比较碎，链表也主要是数据结构而不是语法的知识（是为了练习指针才安排的），因此没有进行知识整理。
如果能帮到你，点个赞呗~
如果文章内容有误，请及时跟蒟蒻说哦~ 蒟蒻一直也在努力！
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
1
0- 0
已为社区贡献5条内容
所有评论(0)